概要
これは、サフィックス配列構築のための O(n log n) アルゴリズムです (または、代わりに::sort2 パス バケット ソートが使用されていた場合はそうなるでしょう)。
最初に 2 グラム(*)をソートし、次に元の string の 4 グラム、次に 8 グラムというSようにソートすることで機能するため、i 番目の反復では 2 つのiグラムをソートします。明らかに、このような繰り返しは log 2 (n) 回しかありません。秘訣は、2 つの 2 iグラムの各比較がO (1) 時間 (O(2 i ) 時間ではなく)。
これはどのように行うのですか？最初の反復では、2 グラム (別名バイグラム) をソートし、辞書式の名前変更と呼ばれるものを実行します。nこれは、バイグラムごとに、バイグラムの並べ替えでのランクを格納する (長さの) 新しい配列を作成することを意味します。
辞書式の名前変更の例:いくつかの bigramsのソートされ{'ab','ab','ca','cd','cd','ea'}たリストがあるとします。次に、左から右に、ランク 0 から始めて新しいバイグラムの変更に遭遇するたびにランクをインクリメントすることによって、ランク(つまり、辞書式の名前)を割り当てます。したがって、私たちが割り当てるランクは次のとおりです。
ab : 0
ab : 0 [no change to previous]
ca : 1 [increment because different from previous]
cd : 2 [increment because different from previous]
cd : 2 [no change to previous]
ea : 3 [increment because different from previous]
これらのランクは、辞書式名として知られています。
さて、次の反復では、4-gram をソートします。これには、異なる 4 グラム間の多くの比較が含まれます。2 つの 4 グラムを比較するにはどうすればよいでしょうか。さて、それらを文字ごとに比較できます。これは、比較ごとに最大 4 つの操作になります。ただし、代わりに、前の手順で生成されたランク テーブルを使用して、それらに含まれる 2 つのバイグラムのランクを調べて比較します。そのランクは、前の 2 グラム ソートの辞書式ランクを表すため、任意の 4 グラムについて、その最初の 2 グラムのランクが別の 4 グラムの最初の 2 グラムよりも高い場合、それは辞書式に大きい必要があります。最初の 2 文字のどこかに. したがって、2 つの 4-gram で最初の 2-gram のランクが同じである場合、それらは同じでなければなりません。最初の 2 文字. つまり、 2つの 4 グラムの 4 文字すべてを比較するには、ランク テーブル内の2 回のルックアップで十分です。
ソート後、今度は 4 グラム用に新しい辞書式の名前を再度作成します。
3 回目の反復では、8 グラムでソートする必要があります。再び、前のステップからの辞書式ランク テーブルでの 2 つのルックアップは、2 つの与えられた 8 グラムの 8 文字すべてを比較するのに十分です。
などなど。各反復iには 2 つのステップがあります。
2 つのiグラムで並べ替え、前の繰り返しの辞書編集名を使用して、それぞれ 2 つのステップ (つまり、O(1) 時間) での比較を可能にします。
新しい辞書式名の作成
2 つのiグラムがすべて異なるまで、これを繰り返します。それが起これば、私たちは終わりです。すべてが異なるかどうかはどうすればわかりますか? 辞書式の名前は、0 から始まる整数の増加するシーケンスです。したがって、反復で生成された最大の辞書式の名前が と同じであるn-1場合、各 2 i -gram には、独自の異なる辞書式の名前が付けられている必要があります。
実装
コードを見て、これらすべてを確認しましょう。使用される変数は次のとおりです。sa[]は、構築中のサフィックス配列です。pos[]ランク ルックアップ テーブル (つまり、辞書式の名前を含む) です。具体的には、前のステップの - 番目の m-gram のpos[k]辞書式の名前が含まれます。の作成を支援するために使用される補助配列です。ktmp[]pos[]
コード行の間にさらに説明を加えます。
void buildSA()
{
N = strlen(S);
/* This is a loop that initializes sa[] and pos[].
For sa[] we assume the order the suffixes have
in the given string. For pos[] we set the lexicographic
rank of each 1-gram using the characters themselves.
That makes sense, right? */
REP(i, N) sa[i] = i, pos[i] = S[i];
/* Gap is the length of the m-gram in each step, divided by 2.
We start with 2-grams, so gap is 1 initially. It then increases
to 2, 4, 8 and so on. */
for (gap = 1;; gap *= 2)
{
/* We sort by (gap*2)-grams: */
sort(sa, sa + N, sufCmp);
/* We compute the lexicographic rank of each m-gram
that we have sorted above. Notice how the rank is computed
by comparing each n-gram at position i with its
neighbor at i+1. If they are identical, the comparison
yields 0, so the rank does not increase. Otherwise the
comparison yields 1, so the rank increases by 1. */
REP(i, N - 1) tmp[i + 1] = tmp[i] + sufCmp(sa[i], sa[i + 1]);
/* tmp contains the rank by position. Now we map this
into pos, so that in the next step we can look it
up per m-gram, rather than by position. */
REP(i, N) pos[sa[i]] = tmp[i];
/* If the largest lexicographic name generated is
n-1, we are finished, because this means all
m-grams must have been different. */
if (tmp[N - 1] == N - 1) break;
}
}
比較機能について
この関数sufCmpは、2 つの (2*ギャップ) グラムを辞書式に比較するために使用されます。したがって、最初の反復ではバイグラムを比較し、2 回目の反復では 4 グラム、次に 8 グラムなどを比較します。gapこれは、グローバル変数であるによって制御されます。
の単純な実装は次のsufCmpようになります。
bool sufCmp(int i, int j)
{
int pos_i = sa[i];
int pos_j = sa[j];
int end_i = pos_i + 2*gap;
int end_j = pos_j + 2*gap;
if (end_i > N)
end_i = N;
if (end_j > N)
end_j = N;
while (i < end_i && j < end_j)
{
if (S[pos_i] != S[pos_j])
return S[pos_i] < S[pos_j];
pos_i += 1;
pos_j += 1;
}
return (pos_i < N && pos_j < N) ? S[pos_i] < S[pos_j] : pos_i > pos_j;
}
これは、i 番目の接尾辞の先頭にある (2*gap)-gram とpos_i:=sa[i]、j 番目の接尾辞の先頭にあるグラムを比較しますpos_j:=sa[j]。そして、それらを文字ごとに比較します。つまり、 と比較S[pos_i]しS[pos_j]、次にS[pos_i+1]と比較しS[pos_j+1]ます。キャラが同じである限り続きます。両者が異なると、i 番目のサフィックスの文字が j 番目のサフィックスの文字より小さい場合は 1 を返し、そうでない場合は 0 を返します。return a<b(関数が返すintということは、条件が true の場合は 1 を返し、false の場合は 0 を返すことを意味することに注意してください。)
return-statement の複雑な外観条件は、(2*gap)-gram の 1 つが文字列の末尾にある場合を扱います。この場合、その時点までのすべての文字が同一であっても、すべての (2*gap) 文字が比較される前にpos_iorpos_jが到達します。Ni 番目のサフィックスが最後にある場合は 1 を返し、j 番目のサフィックスが最後にある場合は 0 を返します。すべての文字が同一である場合、短い方が辞書式に小さいため、これは正しいです。が最後に達した場合pos_i、i 番目のサフィックスは j 番目のサフィックスよりも短くする必要があります。
明らかに、この素朴な実装は O(gap) です。つまり、その複雑さは (2*gap)-gram の長さに比例します。ただし、コードで使用される関数は、辞書式の名前を使用してこれを O(1) にします (具体的には、最大 2 つの比較に減らします)。
bool sufCmp(int i, int j)
{
if (pos[i] != pos[j])
return pos[i] < pos[j];
i += gap;
j += gap;
return (i < N && j < N) ? pos[i] < pos[j] : i > j;
}
ご覧のとおり、個々の文字S[i]とを検索する代わりにS[j]、i 番目と j 番目のサフィックスの辞書式ランクをチェックします。辞書式ランクは、ギャップグラムの前の繰り返しで計算されました。したがって、 の場合pos[i] < pos[j]、i 番目の接尾辞sa[i]は、 の先頭にあるギャップグラムよりも辞書編集的に小さいギャップグラムで開始する必要がありsa[j]ます。つまり、単純に検索してpos[i]比較pos[j]するだけで、2 つのサフィックスの最初のギャップ文字を比較したことになります。
ランクが同じ場合は、 と比較pos[i+gap]して続行しpos[j+gap]ます。これは、(2*gap)-gramの次のギャップ文字、つまり後半を比較することと同じです。ランクが再び同一である場合、2 つの (2*gap)-gram は同一であるため、0 を返します。それ以外の場合、i 番目の接尾辞が j 番目の接尾辞より小さい場合は 1 を返し、そうでない場合は 0 を返します。
例
次の例は、アルゴリズムがどのように動作するかを示しており、特にソート アルゴリズムにおける辞書編集名の役割を示しています。
ソートしたい文字列はabcxabcd. このサフィックス配列を生成するには、3 回の繰り返しが必要です。各反復で、 (S文字列)、sa(サフィックス配列の現在の状態)、tmpおよびposを表示します。これらは、辞書式の名前を表します。
まず、初期化します。
S abcxabcd
sa 01234567
pos abcxabcd
最初はユニグラムの辞書式ランクを表す辞書式の名前が、文字 (つまり、ユニグラム) 自体とまったく同じであることに注意してください。
最初の反復:
バイグラムをソートsa基準として使用するソート:
sa 04156273
最初の 2 つのサフィックスは 0 と 4 です。これらはバイグラム 'ab' の位置だからです。次に 1 と 5 (bigram 'bc' の位置)、次に 6 (bigram 'cd')、次に 2 (bigram 'cx') です。次に 7 (不完全なバイグラム 'd')、次に 3 (バイグラム 'xa')。明らかに、文字のバイグラムのみに基づいて、位置が順序に対応しています。
辞書式名の生成:
tmp 00112345
説明したように、辞書式の名前は増加する整数として割り当てられます。最初の 2 つのサフィックス (両方ともバイグラム 'ab' で始まる) は 0 を取得し、次の 2 つ (両方ともバイグラム 'bc' で始まる) は 1 を取得し、次に 2、3、4、5 (それぞれ異なるバイグラム) を取得します。
最後に、 の位置に従ってこれをマッピングしてsa、 を取得しますpos。
sa 04156273
tmp 00112345
pos 01350124
(pos生成される方法は次のとおりです:sa左から右に進み、 のエントリを使用して のインデックスを定義しますpos。 の対応するエントリを使用して、そのインデックスのtmp値を定義します。から来て、値は から。)pos[0]:=0pos[4]:=0pos[1]:=1pos[5]:=1pos[6]:=2satmp
2 回目の反復:
saもう一度並べ替えて、(それぞれが元の文字列の2 つのバイグラムのposシーケンスを表す)からのバイグラムを調べます。
sa 04516273
1 5 の位置が以前のバージョンの と比べてどのように切り替わったかに注目してくださいsa。以前は 15 でしたが、現在は 51 です。これは、前の反復では の バイグラム と バイグラム が(両方pos[1]ともpos[5])であったためです。したがって、 positionはpositionの前に来ます。これは、辞書式の名前がそれぞれ元の文字列のバイグラムを表すようになったためです。したがって、一緒にそれらは を表し、一方と は を表すので、一緒にそれらは表しますbcpos[5]12pos[1]1351pos[5]bcpos[6]bcdpos[1]bcpos[2]cxbcx、これは辞書編集的に よりも大きいですbcd。
saここでも、 の現在のバージョンを左から右にスクリーニングし、 の対応するバイグラムを比較することにより、辞書式の名前を生成しposます。
tmp 00123456
posの対応するバイグラムが両方であるため、最初の 2 つのエントリは依然として同一 (両方とも 0)01です。posの他のすべてのバイグラムはそれぞれ一意であるため、残りは整数の厳密に増加するシーケンスです。
前と同じようにnew へのマッピングを実行しますpos( からインデックスを取得し、 からsa値を取得しますtmp)。
sa 04516273
tmp 00123456
pos 02460135
3 回目の反復:
sa(いつものように)のバイグラムを取得して、再度並べ替えposます。これは、元の文字列の 4 つのバイグラムのシーケンスを表します。
sa 40516273
04最初の 2 つのエントリの位置が入れ替わっていることに気付くでしょう40。これは、 のバイグラムが でpos[0]あるの02に対し、のバイグラムは でpos[4]あり01、後者は明らかに辞書編集的に小さいためです。深い理由は、これら 2 つはそれぞれabcxとabcdを表しているからです。
辞書式の名前を生成すると、次の結果が得られます。
tmp 01234567
それらはすべて異なります。つまり、最高のものは7であり、これはn-1です。これで、ソートはすべて異なる m-gram に基づいているため、これで完了です。続けても並び順は変わらない。
改善提案
各反復で2 つのiグラムを並べ替えるために使用されるアルゴリズムは、組み込みsort(またはstd::sort) のようです。これは、比較ソートであり、最悪の場合、各反復でO(n log n) 時間がかかることを意味します。最悪の場合、log n 回の反復があるため、O(n (log n) 2 ) 時間のアルゴリズムになります。ただし、並べ替えの比較に使用するキー (つまり、前のステップの辞書式の名前) は増加する整数シーケンスを形成するため、バケット並べ替えの 2 つのパスを使用して並べ替えを実行できます。したがって、これはサフィックスソートの実際の O(n log n) 時間アルゴリズムに改善される可能性があります。
述べる
これは、Manber と Myers による 1992 年の論文で提案された接尾辞配列構築の元のアルゴリズムであると思います ( Google Scholar のリンク; 最初のヒットである必要があり、そこに PDF へのリンクがある可能性があります)。これは (同時に、しかし Gonnet と Baeza-Yates による論文とは独立して) 接尾辞配列 (当時は pat 配列とも呼ばれていた) を、さらなる研究にとって興味深いデータ構造として導入したものでした。
接尾辞配列構築の最新のアルゴリズムは O(n) であるため、上記は利用可能な最良のアルゴリズムではなくなりました (少なくとも理論上の最悪の場合の複雑さに関しては)。
脚注
(*) 2-gramとは、元の文字列の連続する2 文字のシーケンスを意味します。たとえば、S=abcdeが文字列の場合ab、bc、cd、deは の 2 グラムですS。同様に、abcdとbcdeは 4 グラムです。一般に、m-gram (正の整数 m の場合) はm連続した文字のシーケンスです。1 グラムはユニグラム、2 グラムはバイグラム、3 グラムはトライグラムとも呼ばれます。四角形、五角形などを続けている人もいます。
Sその startと positionのサフィックスiは、 の (ニ) グラムであることに注意してくださいS。また、すべての m-gram (任意の m の) は、 の接尾辞のいずれかの接頭辞ですS。したがって、m-gram の並べ替え (可能な限り大きな m の場合) は、接尾辞の並べ替えに向けた最初のステップになる可能性があります。