Content deleted Content added
Rearrange and flesh out early content a bit. The "Description" section actually didn't contain a full description of the algorithm before, just an example, before the description finally came in the "Example" section, which was weird! Also we had multiple sections explaining why the algo tends to produce runs of a single character repeated many times, so I've merged them into a single such explanation. Tag: Disambiguation links added |
Remove claim about the bijective variant that appears to be false (and contradicted by the very example that followed it). See https://en.wikipedia.org/wiki/Talk:Burrows%E2%80%93Wheeler_transform#%22the_transformed_text_will_differ_from_the_result_of_BWT_by_only_one_character_per_Lyndon_word%22_-_uh,_no? |
||
Line 460:
The Burrows–Wheeler transform can indeed be viewed as a special case of this bijective transform; instead of the traditional introduction of a new letter from outside our alphabet to denote the end of the string, we can introduce a new letter that compares as preceding all existing letters that is put at the beginning of the string. The whole string is now a Lyndon word, and running it through the bijective process will therefore result in a transformed result that, when inverted, gives back the Lyndon word, with no need for reassembling at the end.
For example, applying the bijective transform gives:
{| class="wikitable"
| |||