接尾辞配列は、特定の文字列リストのすべての接尾辞にインデックスを付けますが、考えられるすべての一意の部分文字列にインデックスを付けようとするとどうなるでしょうか? 私はこれに少し慣れていないので、ここに私が意味することの例を示します:
文字列を考えると
abcd
サフィックス配列のインデックス（少なくとも私の理解では）
(abcd,bcd,cd,d)
インデックスを作成したい (すべての部分文字列)
(abcd,bcd,cd,d,abc,bc,c,ab,b,a)
私が探しているのは接尾辞配列ですか? もしそうなら、すべての部分文字列にインデックスを付けるにはどうすればよいですか? そうでない場合、どこを見ればよいですか？また、「すべての部分文字列」と「接尾部の部分文字列」を比較するには、何をグーグルで検索しますか?
接尾辞配列は、すべての部分文字列がいずれかの接尾辞の接頭辞であるため、既に必要なことを実行します。具体的には、サフィックス配列が与えられた場合
abcd bcd cd d
部分文字列「bc」を探していると仮定すると、「bc」で始まるすべての接尾辞を探すことで見つけることができます (この場合、「bcd」は 1 つだけです)。接尾辞配列は辞書順にソートされるため、特定の接頭辞を共有するすべての接尾辞を見つけることは、接尾辞配列全体のバイナリ検索に対応し、結果は接尾辞配列のエントリの 1 つの連続した範囲になります。
ただし、LCP (longest-common prefix) 配列やウェーブレット ツリーなどの補助データ構造と組み合わせたサフィックス配列を使用する最適化された検索方法があります。そのような方法の説明については、Navarro の 2007 年の調査を参照してください (DOI 10.1145/1216370.1216372)。
以下のコメントを考慮して、各接尾辞をそれが表す部分文字列の数と組み合わせることをお勧めします。上記のような単純な例では、これは
4 abcd
3 bcd
2 bc
1 d
たとえば、最初のサフィックス「abcd」は、4 つの部分文字列「a」、「ab」、「abc」、「abcd」を表すためです。ただし、文字列「abcabxdabe」などのより複雑な例では、サフィックス配列の最初の 2 つのエントリは次のようになります。
10 abcabxdabe
1 abe
2 番目のエントリは部分文字列 "a"、"ab"、および "abe" を表しますが、"a" と "ab" は最初のエントリでも表されるためです。
エントリが表す部分文字列の数を計算する方法は? --> サフィックスの長さから、前のサフィックスと共通する最長のプレフィックスの長さを引いたもの。たとえば、「abe」の例では、3 (その長さ) から 2 (「ab」の長さ、前のエントリと共有する最長のプレフィックス) を引いたものです。したがって、これらの数値はサフィックス配列を介して 1 回のパスで生成でき、LCP (最長共通プレフィックス) 配列も生成した場合はさらに高速になります。
次のステップは、累積カウントを生成することです。
10 abcabxdabe
11 abe
16 abxdabe
...
そして、蓄積されたカウントを利用する効率的な方法を見つけます。たとえば、13 番目の部分文字列を辞書的に取得したい場合は、累積カウントが 13 以上の最初のエントリを見つける必要があります。これは、上記の「16 abxdabe」になります。次に、前のエントリと共有する接頭辞を削除し (「xdabe」が生成されます)、2 番目の文字の後の位置にジャンプします (前のエントリはカウント 11 を累積し、13-11==2 であるため)。 abxd" を辞書的に 13 番目の部分文字列として指定します。
すでに回答されているように、部分文字列は接尾辞の接頭辞です。場合によっては、別の方法でプレフィックスのサフィックスを取得したいことがあります。
それを超えて、「一意の部分文字列」で何を探しているのかは不明です。type、token、maximal、supermaximal という言葉を調べることをお勧めします。接尾辞配列の文献でこれらを見つけるのに問題はないはずです。
「Trie」のバリエーションを使用する必要があります。基本的に、ABCD がある場合は、パスのマージであるツリーを作成します: root->A->B->C->D、root->B->C->D、root->C->D および root ->D. ここで、すべてのノードで、文字列 root->.->.->node が観察された場所のリストを保持します。