問題タブ [suffix-array]

接尾辞配列は、特定の文字列リストのすべての接尾辞にインデックスを付けますが、考えられるすべての一意の部分文字列にインデックスを付けようとするとどうなるでしょうか? 私はこれに少し慣れていないので、ここに私が意味することの例を示します:

文字列を考えると

サフィックス配列のインデックス（少なくとも私の理解では）

インデックスを作成したい (すべての部分文字列)

私が探しているのは接尾辞配列ですか? もしそうなら、すべての部分文字列にインデックスを付けるにはどうすればよいですか? そうでない場合、どこを見ればよいですか？また、「すべての部分文字列」と「接尾部の部分文字列」を比較するには、何をグーグルで検索しますか?

たとえば、次の文字列リストを生成するために、特殊文字（B、C、D、F、X、Z）によってランダムに生成される文字列があります。

生成文字列に一致し、最適なパターンを返し、文字列から文字列を抽出するパターン リストもあります。

文字列パターン

例えば、

B D Z Z Z C D C Z、それはBとを持っているDCので、B D C

D B Z C F、それはBandCを持っているFので、B C F

D B Z D F、それはBとを持っているFので、B F

.......

今、私はちょうど考えますsuffix array。

1.最初に文字列を接尾辞配列オブジェクトに変換します。

2.各パターンをループし、一致するサフィックス配列を見つけます。

3.一致したすべてのパターンを比較し、最適なパターンを取得します。

このメソッドは複雑すぎると思います。パターンのツリーを構築し、それを取得してサフィックス配列と一致させる必要があります。もっとアイデアがある人はいますか?

====================アップデート

私は今、最善の解決策を得て、B、C、D、X ... の配列型のプロパティを持つ新しいクラスを作成します。各プロパティは、文字列に表示される位置を保存します。これで、文字列に B が表示されない場合は、この処理をすぐに終了できます。また、すべての C と D の位置を取得して、連続して表示できるかどうかを比較することもできます (DC、DCC、CCC....)。

Princetonの実装を使用して接尾辞配列を作成しました。ただし、私の基本的なテキストドキュメントは非常に大きく、結果の接尾辞配列のサイズは500MBを超えます。接尾辞配列を圧縮する方法はありますか？

ありがとう！

接尾辞配列を説明する優れた教育リソースを見つけることができません。「聖書」でさえそれをカバーしていません。

接尾辞配列とその使用法に関する明確で完全な説明はどこにありますか? (私は怠け者なので、ビデオ コースが理想的です。)

この問題を解決するための(パフォーマンス面での)最善のアプローチは何でしょうか? サフィックスツリーを使用することをお勧めしました。これは最善のアプローチですか？

ラテン文字の小文字で構成される文字列Sが与えられます。位置i'<iが存在する位置S[i]の最大長L[i]ごとに、s [i'.. i'+ L [i] -1] =s[i。。 i + L[i]-1]。例：s = ababaab、L={0,0,3,2,1,2,1}。時間<O（| S | ^ 2）でやりたい。問題は接尾辞配列で解決されると思いますが、どうすればよいですか？

サフィックス配列 SA と、2 つの連続するサフィックス間のLCP (最長共通プレフィックス) の長さを格納する配列 L があります。

こちらにも記載されています。

この配列 L を使用して、指定された 2 つのサフィックス x と y の間の LCP(x,y) を見つけるにはどうすればよいですか?

接尾辞配列、つまり、辞書順で文字列のすべての接尾辞の開始位置を与える整数の配列を構築したとします。

例: stringstr=abcabbcaの場合、

サフィックス配列は次のとおりです。

説明：

これが構築されたので、 （文字列自体）と他の各サフィックスの間の最長共通プレフィックス（LCP）の長さsuffixArrayを見つけたいと思います。それを行う最も効率的な方法は何ですか？str

サフィックスツリーが拡張サフィックスアレイよりも優れている場合を知りたいだけです。

「サフィックス ツリーを強化されたサフィックス アレイに置き換える」を読んだ後、サフィックス ツリーを使用する理由がわかりません。一部のメソッドは複雑になる可能性がありますが、接尾辞配列を使用してすべてを行うことができ、接尾辞ツリーで実行できることと同じ時間の複雑さを必要としますが、メモリは少なくて済みます。

ある調査では、接尾辞配列の方がキャッシュにやさしく、キャッシュミスが少ないため、より高速であることが示されました (そのため、キャッシュは再帰ツリー構造よりも配列の使用をはるかによく予測できます)。

では、サフィックス配列よりもサフィックスツリーを選択する理由を知っている人はいますか?

編集 OK、もっと知っているなら教えてください、これまでのところ:

• Suffixarray はオンライン構築を許可しません
• 一部のパターン マッチング アルゴリズムは、Suffixtree で高速に実行されます
• (追加) オンライン構築のため、hd a に保存し、既存の suffixtree を拡大することができます。SSD を使用する場合は、静かで高速である必要があります。

これはACMICPC2003の問題です。この問題は、他のユーザーからスタックフローですでに質問されています。[しかし、それは役に立たなかったので、接尾辞配列で実行したいと思います。]

サフィックス配列を使用してこの問題を解決するにはどうすればよいですか？

今まで私がしたことは??

（1）与えられた文字列がSであるとしましょう。

文字列Sをそれ自体と連結して、文字列S'を取得しました。

すなわち。S'= S+S。

（2）次に、O（nlog n）時間でS'の接尾辞配列を見つけました。

そこで、接尾辞配列SAをよく計算しました。SA[]={13,6,9,2,11,4,7,0,10,3,12,5,8,1}。

また、サフィックスごとにLCPを計算しました[この問題で必要になるとは確信していませんが]。

次に進む方法SAを使用して目的の結果を得る方法は？

非常に*小さな例での説明は非常に効果的です。

ありがとう！！