在Burrows-Wheeler轉換之前分析一個字符串？

Question

如果我們將這個aaabccba作爲我們的輸入字符串，那麼baaacacb將作爲對輸入應用Burrows-Wheeler轉換後的輸出字符串。觀察輸出，你會看到兩個分組c分開。很明顯，輸入字符串將導致比輸出更好的壓縮。

如何決定是否對輸入字符串應用Burrows-Wheeler轉換？我們可以做一些快速分析來做出決定嗎？

Answer 1

最簡單的解決方案是實際壓縮每個字符串，並查看哪個結果是最小的壓縮。

如果你不想做，你可以指望每個組的長度：

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。 —選擇一個較小的總和。

Answer 2

剛剛嘗試的東西比BWT快得多，例如壓縮它lz4，看看它壓縮多少。然後，您可以通過實驗爲該應用BWT的比率設置一個閾值，這取決於您爲應用獲得的任何標準。