c - 在 Burrows-Wheeler 变换之前分析字符串？

Question

如果我们将其aaabccba视为输入字符串，baaacacb则将是对输入应用 Burrows-Wheeler 变换后的输出字符串。观察输出你会发现两个聚集在一起c是分开的。很明显，输入字符串会比输出产生更好的压缩效果。

如何决定是否对输入字符串应用 Burrows-Wheeler 变换？我们可以做一些快速分析来做出决定吗？

Answer 1

试着用比 BWT 快得多的东西来压缩它，例如lz4，看看它压缩了多少。然后，您可以根据您为应用程序得出的任何标准，通过实验设置应用 BWT 的比率阈值。

Answer 2

最简单的解决方案是实际压缩每个字符串，并查看哪个导致最小的压缩。

如果您不想这样做，您可以计算每个组的长度：

aaabccba -> aaa b cc b a

    aaa has length 3
    b has length 1
    cc has length 2
    b has length 1
    a has length 1

    there where 3 groups of length 1
    there where 1 group of length 2
    there where 1 group of length 3
                ^

    -> [3, 1, 1]

baaacacb -> b aaa c a c b

    b has length 1
    aaa has length 3
    c has length 1
    a has length 1
    c has length 1
    b has length 1

    there where 5 groups of length 1
    there where 0 groups of length 2
    there where 1 group of length 3
                ^

    -> [5, 0, 1]

• 按字典顺序比较列表：3 < 5所以[3, 1, 1] < [5, 0, 1]- 选择最小的一个。

• 或者，您可以颠倒列表：[1, 1, 3] > [1, 0, 5]— 选择最大的一个。

• 另一种比较它们的方法是总计数：3+1+1=5 < 5+0+1=6. — 选择总和较小的那个。