12

Burrows and Wheeler の論文からブロック ソート アルゴリズムを読んでいます。これはアルゴリズムのステップです:

S=アブラカダブラとする

N 個の単語 W[0, ... , N - 1] の配列 W を初期化し、W[i] に文字 S'[i, ... , i + k - 1] が含まれるようにします。単語は、k 文字列の辞書式比較と一致します。文字を単語にパックすることには 2 つの利点があります。アラインされたメモリ アクセスを使用して、一度に 2 つのプレフィックスを k バイトずつ比較でき、多くの遅いケースを排除できます。

(注:はk文字が追加されS'たオリジナルです。kは機械語に収まる文字数です (私は 32 ビット マシンを使用しているので、)SEOFk=4

EOF = '$'

私が間違っている場合は修正してください：

S'= abracadabra$$$$  
W= abra brac raca acad cada adab dabr abra bra$ ra$$ a$$$

次に、アルゴリズムは、配列にインデックスをS付けることにより、 (V という名前の)のサフィックス配列をソートする必要があると言います。W

にインデックスを付けてサフィックスをソートする方法が完全にはわかりませんW。例: ソートのある時点で、2 つの接尾辞 と を取得iしj、それらを比較する必要があるとします。にインデックスを付けているためW、一度に 4 文字をチェックしています。
最初の 4 文字が両方とも同じであるとします。次に、サフィックスごとに次の 4 文字をチェックする必要があり、W. これは正しいですか？この「文字を言葉に詰め込む」ことは本当にスピードアップするのでしょうか?

4

2 に答える 2

4

質問で説明する方法は完全に正確です。はい、あなたが言ったように、一度に 4 つの文字を比較するため、速度が向上します。

ただし、次の 2 つの注意事項があります。

  1. あなたの例のように接尾辞 i と j を比較すると、実際にエントリ W[i] と W[j] を比較します。この結果は、4 つの文字 S[i..i+3] と S[j..j+3] を辞書式に比較した場合と同じであるため、3 文字の比較に相当する計算時間を節約できます。はい、結果が 2 つの四重項が同一であることを示している場合は、W[i+1] と W[j+1] の比較を続行する必要がありますが、すぐには実行しません。彼らのアルゴリズムの仕組みは基数ソートです。つまり、最初の比較の直後に接尾辞をバケットに入れ (おそらく両方を同じバケットに入れる)、バケットを内部的に再帰的にソートします。
  2. Burrows and Wheeler による元の論文で説明されているアルゴリズム (引用元;たとえば、ここにコピーがあります) は、1994 年のものであり、最適な接尾辞配列構築アルゴリズムではありません。まず、2003 年にいくつかの O(N) 直接構築法が発見されました。第二に、それ以来、実装に対してさらに多くの改善が行われました。1994 年の論文の核心は、文字列圧縮の基礎として Burrows-Wheeler 変換を使用するという考えであり、変換自体が生成される正確な方法ではありません。
于 2012-02-24T15:14:48.093 に答える
0

配列 V はサフィックス配列ではなく、W へのインデックスの配列です。並べ替えが完了すると、V は次のように W へのインデックスを保持する必要があります。

V[i] <= V[j]

それから

 W[V[i]] <= W[V[j]].

私が正しいことを言ったことを願っています:)それらを正確に一致させることは問題ではなく、どちらの順序でも問題ありません。ポイントは、逆変換を適用する場合、元の文字列を復元するために W を復元できる必要があり、W の同一の要素が問題を引き起こすことはないということです。

于 2011-10-11T17:32:48.663 に答える