回复：关于BWT算法应用于bzip2压缩的一点疑问

比如banana可以划分成[b][an][an][a]，bananas可以划分成[b][ananas]

奥，那他的大小是怎么确定的呢？比如banana变换后：[b][an][an][a],是不是b>an>an>a,
那如果取出最长的话，那ban是大于ana的，甚至于banan是大于a的。。。
是不是应该是取出最短的呢？

ban不是lyndon word，因为anb < ban
banana可以分成[b][anan][a]，也可以分成[b][anan][a]，在逆变换的时候相应改一下就行了

我看到后缀数组了！虽然不知道是神马…但班里的大神告诉我这很nb…

奥，我想错了。不好意思，白痴了。应该是每一个word内的升序排列，我误解成在整个字符串内部的块与块之间了。OK，了解其基本原理了，谢谢了。

你这个头像着实吓我一跳。。。

那bananas是不是可以分成[b][an][an][as]呢？

不能，因为按每次取最长的原则只能是[b][ananas]

奥，我似乎已经了解了。这个算法看起来消耗应该非常巨大呀。我回去研究一下他对可实现性。
但是解压时有个问题：例如banana，经过BWTS之后输出为annbaa，按不断前移排序的方法还原：
还原的结果为：
aaaaa
anana
anana
bbbbb
nanan
nanan
具体是如何找出原字符串的呢？我到现在也没想明白。。。
还有，另一种方法：
i T BWTS Next
- - ---- ----
0 A A 0
1 A N 4
2 A N 5
3 B B 3
4 N A 1
5 N A 2
The linked list has 4 cycles: (0), (1,4), (2,5), (3). Reversing the order of
the cycles and concatenating, we get (3,2,5,1,4,0). The corresponding elements
of T spell out "BANANA".
这个（0），（1，4）（2,5）（3），是如何形成的？我本来以为使用lyndon 的方法，结果发现并不是。还请RICH大神指点一二。这种东西我实在是接触的不多，谢谢了、

我头像怎么了。。。毕竟要考虑到Naboo人民的风俗习惯。。。

准备学习bzip2压缩算法，4年的老帖，能否盘活