Re: qsort in BWT

Lyle wrote:
) What about as in my example...
) If the original string is fabababab$, then the two rotations:
)
) S1: ababab$fab and S2: ab$fababab will compare differently...
) According to BWT, ab$fababab is lexically greater than ababab$fab...

Remember, $ is a character smaller than all other characters.
So ab$fananan is lexically smaller than ababab$fab.
More generally, ab$<anything> is lexically smaller than ab<anything>.
So, with the addition of the EOF character, you can always stop comparing
before there is a wraparound.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
.

Relevant Pages

  • Re: qsort in BWT
    ... If the original string is fabababab$, then the two rotations: ... S1: ababab$fab and S2: ab$fababab will compare differently... ... According to BWT, ab$fababab is lexically greater than ababab$fab... ...
    (comp.compression)
  • Re: A truely BIJECTIVE BWT is here!
    ... I left the old BWT stuff since its the way you compare BWTS ... FOOBAR2000 <-- orignal input string, ... Zero as seprate cycle and it actually sorts first than current version ... character sequences. ...
    (comp.compression)
  • Re: A truely BIJECTIVE BWT is here!
    ... If you look at the BWT ... rotation of a given input to the same output string. ... shorter cycle that doesn't include all characters. ... character sequences. ...
    (comp.compression)
  • Re: A truely BIJECTIVE BWT is here!
    ... If you look at the BWT ... rotation of a given input to the same output string. ... character sequences. ... Compression speed is also likely to be worse. ...
    (comp.compression)
  • Re: A truely BIJECTIVE BWT is here!
    ... "000FOOBAR2" (see forward BWT example from the beginning). ... With "B" as the only character left we'd be done. ... An entirely different way of tackling this problem is just start with some empty buffer and add characters from the input until it breaks, i.e. the cycle would no longer end up on the first line of the BWT table. ... In order to find out if we're adding a such a string we need to know how many characters we added recently match the beginning of the string, thus we need a position marker. ...
    (comp.compression)