問題タブ [suffix-tree]

The Algorithm Design Manualのデータ構造の章を読んでいて、Suffix Trees に出会いました。

例は次のように述べています。

入力：

出力：

指定された入力文字列からそのツリーがどのように生成されるのか理解できません。接尾辞ツリーは、特定の文字列内の特定の部分文字列を見つけるために使用されますが、特定のツリーはそれに対してどのように役立つのでしょうか? 以下に示すトライの別の例は理解できますが、下のトライが接尾辞ツリーに圧縮されると、どのように見えるでしょうか?

次のクエリをサポートするように、全長nのSドキュメントのコレクションのインデックス作成に役立つデータ構造を構築しています。2つの単語P1とP2が与えられた場合、P1を含むがP2を含まないすべてのドキュメントをカウントします。答えを完全なものにしたい（結果を見逃さないようにする）。

一般化された接尾辞木を作成し、すべてのsqrt（n）番目の葉とその祖先を選択します（そして、すべての1子ノードを削除します）。内部ノードごとにvノードuに対するクエリの回答を事前に計算します。

しかし、これにより、ノードvとuのツリーに表示される単語がクエリに含まれている場合、O（1）で答えを得ることができますが、選択したノードの1つに単語がない場合はどうすればよいですか？

^{前処理でO（n 2}）データ構造を維持し、O（1）時間検索の準備ができているすべての可能な答えを用意することで簡単にそれを行うことができますが、目標はO（n）空間でこのデータ構造を構築することです。クエリを可能な限り効率的にします。

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

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

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

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

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

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

いくつかのコードで少し問題が発生しています。私はひどいプログラマーなので、私の解決策はおそらくあまり雄弁ではないことを覚えておいてください（そしておそらく私がメモリを使い果たしている理由-私は4ギガバイトを持っていて、スクリプトはゆっくりとそれを満たします）。

ここに問題があります。ディレクトリに約3,500個のファイルがあります。各ファイルは、スペースのない比較的少数または多数の文字を含む可能性のある1行で構成されます（最小のファイルは200バイトであるのに対し、最大のファイルは1.3メガバイトです）。私がやろうとしているのは、これらのファイル間で設定された長さの2つの共通の部分文字列を見つけることです（以下のコードでは13文字です）。それらすべてに共通のサブストリングを探しているのではなく、すべてのファイルが比較されるまで2つの組み合わせを探しているので、一度に2つ実行します。つまり、ファイル間で設定された長さの共通のサブストリングであり、すべてのファイルに共通のサブストリングではありません。

C実装をラップするサフィックスツリーモジュールを使用します（ここ）。最初にディレクトリ内のすべてのファイルのリストを作成し、次にすべての組み合わせがカバーされるように2つの組み合わせを探し、一度に2つのファイルをサフィックスツリーに渡し、次に一般的なサブストリングであるシーケンスを探します。

しかし、なぜそれがゆっくりとメモリを使い果たしているのか、私にはよくわかりません。未使用のもののメモリをなんとかしてクリアするように、コードに修正を加えることができるといいのですが。もちろん、3,500ファイルの処理には長い時間がかかりますが、4ギガバイトのメモリを段階的にいっぱいにすることなく処理できることを願っています。どんな助けでも大歓迎です！これが私がこれまでに持っているコードです：

更新＃1

更新されたコードは次のとおりです。Pyrceの提案を追加しました。しかし、jogojapanがCコードのメモリリークを特定し、それが私の専門知識をはるかに超えていることを考えると、私ははるかに遅いアプローチをとることになりました。この分野に精通している人がいれば、Cコードを変更してメモリリークや割り当て解除機能を修正する方法を知りたいと思います。PythonのCサフィックスツリーバインディングは非常に価値があると思います。接尾辞木なしでこのスクリプトを介してデータを実行するにはおそらく数日かかるので、誰かが創造的な修正を持っているかどうかを確認することは間違いなくオープンです！

1行の文字列で構成される約3,500個のファイルがあります。ファイルのサイズはさまざまです（約200bから1mb）。各ファイルを他のファイルと比較して、2つのファイル間で長さが20文字の共通のサブシーケンスを見つけようとしています。サブシーケンスは、各比較中に2つのファイル間でのみ共通であり、すべてのファイル間で共通ではないことに注意してください。

私はこの問題に少し苦労しました、そして私は専門家ではないので、私は少しアドホックな解決策に行き着きました。itertools.combinationsを使用して、Pythonでリストを作成します。リストの組み合わせは約6,239,278になります。次に、ファイルを一度に2つずつ、 libstreeと呼ばれるCで記述されたサフィックスツリーライブラリのラッパーとして機能するPerlスクリプトに渡します。私はこのタイプの解決策を避けようとしましたが、Pythonで唯一の同等のCサフィックスツリーラッパーがメモリリークに悩まされています。

これが私の問題です。私はそれを計時しました、そして私のマシンでは、ソリューションは25秒で約500の比較を処理します。つまり、タスクを完了するには、約3日間の連続処理が必要になります。そして、20文字ではなく25文字を確認するために、もう一度すべてを行う必要があります。私は自分の快適ゾーンから外れていて、あまり優れたプログラマーではないことに注意してください。したがって、はるかにエレガントな方法があると確信しています。これをする。ここで質問してコードを作成し、このタスクをより速く完了する方法について誰かが提案を持っているかどうかを確認したいと思いました。

Pythonコード：

Perlコード：

インストールされていない Perl スクリプトにローカル モジュールを含めたい。以下のコードは、その目的のために機能するようです。ただし、インクルードしたいモジュールは C ライブラリのラッパーです。私は次のようにします：

Perl モジュールはTree::Suffixと呼ばれ、 libstreeのラッパーとして機能します。私の質問は、C ライブラリをローカルでも参照するにはどうすればよいかということです (インストールされていない場合)。

Perlモジュールの内部の仕組みと関係があると思いますか? 素人の質問でしたら申し訳ありません。ありがとうございました！

複数の文字列の最長の共通部分文字列を計算するために、接尾辞リンク (ここでは紙) を持つ factor-oracle を使用できますか? ここで、部分文字列とは、元の文字列の任意の部分を意味します。たとえば、「abc」は「ffabcgg」の部分文字列ですが、「abg」はそうではありません。

s12 つの文字列との共通部分文字列の最大長を計算する方法を見つけましたs2。たとえば、「$」など、文字列に含まれていない文字を使用して 2 つの文字列を連結することによって機能します。s次に、 lengthの連結文字列の各プレフィックスについて、i >= |s1| + 2その LRS (最長繰り返しサフィックス) の長さlrs[i]とsp[i](その LRS の最初の出現位置の終了位置) を計算します。最後に、答えは

私は、この方法を使用する C++ プログラムを作成しました。このプログラムは、|s1|+|s2| <= 200000オラクル因子を使用すると、ラップトップで 200 ミリ秒以内に問題を解決できます。

どちらの問題も suffix-array と suffix-tree を使用して高効率で解決できることはわかっていますが、factor oracle を使用して解決する方法はあるのでしょうか。factor oracle は簡単に構築でき (C++ で 30 行、suffix-array は約 60 行、suffix-tree は 150 行必要)、suffix-array や suffix-tree よりも高速に実行されるため、これに興味があります。

この OnlineJudgeで最初の問題の方法をテストし、ここで2 番目の問題をテストできます。

「abcabx」というテキストがあるとします。繰り返しパターン「ab」があること、それが現れるすべての場所、およびそれらの繰り返しのコンテキストが他の出現とどのように関連しているかを知りたいです。また、データ構造には、一意のパターン「c」と「x」を区別して分離する必要があります。そうしようとしてサフィックスツリーをセットアップしましたが、次のようになります( this SO answer から):

これは確かに、パターン「ab」が 2 回表示されていることを示しています。ただし、ルートの「ab」は、パターンの最初の出現のみを指します。また、そのリーフ「cabx」に別の「ab」が埋め込まれています。その「ab」(「cabx」内) を何らかの形でデータ構造の繰り返しとして認識させたい場合です。ルート「ab」の「x」リーフがそれを表していることは知っていますが、「ab」の「cabx」リーフに「ab」があることを知る必要があります。さらに、「c」と「x」という 2 つのユニークなパターンがそのエッジの一部です。さらに、そのエッジ内の位置、およびそれらの「主な定義」(ルート エッジ?) 間の相互参照。

もっと簡単に言えば、データ構造は、「ここにすべての固有のパターンがある」、「ここにすべての繰り返しパターンとそれらが発生するすべての場所がある」、「これらすべてに関連するコンテキストがある」ことを明確に示す必要があります。 .

だから私はグラフのような要素を接尾辞ツリーに探していると思います。これは、既知のパターンを分割し、それらを明示的に関連付けるものです。その過程で、ユニークなパターンが注目されます。しかし、「c」（「cabx」ではなく「c」）と「x」の両方が「ab」の後に来る、「abx」が「abc」の後に来るなど、接尾辞ツリーのコンテキスト機能が必要です。それらの後に来ました（より大きな場合）など。これを行うサフィックスツリーの適応、またはおそらく別のアルゴリズムはありますか？

文字列内で重複しない最長の繰り返し部分文字列を見つける必要があります。使用可能な文字列のサフィックス ツリーとサフィックス配列があります。

オーバーラップが許可されている場合、答えは自明です (サフィックス ツリーで最も深い親ノード)。

たとえば、String = "acaca" の場合

重複を許容する場合は「aca」、重複を許容しない場合は「ac」または「ca」となります。

アルゴリズムまたは高レベルのアイデアのみが必要です。

PS: 試してみましたが、ウェブ上で見つけられる明確な答えはありません。

S指定された長さの文字列の場合n-

• のすべての一意の部分文字列を見つけるための最適なアルゴリズムは、S未満にすることはできませんO(n^2)。したがって、最適なアルゴリズムは の複雑さを提供しO(n^2)ます。私が読んだことによると、これは のサフィックスツリーを作成することで実装できますS。

S のサフィックス ツリーは、時間内に作成できますO(n)。さて、私の質問は-

SS の接尾辞ツリーを使用して、 inの一意の部分文字列をすべて取得するにはどうすればよいO(n^2)でしょうか?