7

最長共通部分文字列アルゴリズムを学習したばかりなので、この問題の特定の変形に興味がありました。次のように説明されています-：

文字列の 2 つの空でないシーケンス、X = (x1, x2, x3,....,x(n)) および Y = (y1, y2, y3,..., y(m)) が与えられます。ここで、x (i) と y(i) は文字列です。Y のすべての文字列の部分文字列である X で最も長い文字列を見つけます。

substring(x, y)x が y の部分文字列であるかどうかを表すブール値を返す関数があります。明らかに、Y のすべての文字列を連結して、たとえば B で示される 1 つの大きな文字列を形成する必要があります。次のアプローチを考えました。

  • Naive : X 内のすべての文字列を連結して、文字列 A(n) を形成することから始めます。substring(A(n), B) を適用します。これには、文字列 A(n) の逆方向の反復が含まれます。true の場合、アルゴリズムはここで終了し、A(n) を返します。または、その部分文字列に含まれる部分を返します。そうでない場合は、(A(n - 1), B) などの適用に進みます。そのような文字列が X に存在しない場合は、空の文字列を返します。

明らかに、このアプローチは、実装によってはかなりの実行時間がかかります。反復アプローチを使用すると仮定すると、反復ごとに、そのレベル/インデックスで文字列を逆方向に反復し、その後 substring() を適用する必要があります。substring() によっては、少なくとも 2 つのループとO(size(B) * maxlength(x1, x2,...))最悪の場合の時間、またはそれ以上の時間がかかります (間違っている場合は修正してください)。

サフィックスツリー/配列に基づく2番目のアプローチを考えました。

  • Generalized Suffix TreeO(maxlength(y1, y2,...) : (?)で Ukkonen のアルゴリズムを使用してシーケンス Y の GST を構築します。接尾辞ツリーに関する私の知識の欠如が噛みつきます。サフィックスツリーのアプローチは、部分文字列を見つけるための実行時間を（スペースを犠牲にして）大幅に短縮すると信じていますが、操作を実装する方法がわかりません。

より良いアプローチがあれば、知りたいです。

編集：トピックを放棄したように見えた場合はお詫び申し上げます。

GST ではなく、スタック、キュー、セット、ヒープ、プライオリティ キューなどの標準的なデータ構造を使用するとどうなりますか? シーケンス X は、当然、最大の文字列から順に並べ替える必要があります。文字列配列に格納する場合、mergesort/quicksort などの並べ替えアルゴリズムを使用する必要があります。目標は、可能な限り最も効率的な実行時間を取得することです。

X を、それ自体を構築するときに要素を自動的にソートする構造に格納することはできませんか? 最大ヒープはどうですか？

この方法で部分文字列を見つけるには、サフィックス ツリーが最適な方法のように思われます。他に使用できるデータ構造はありますか?

4

3 に答える 3

1

Here is my idea about a solution of your problem; I am not sure about everything so comments are welcome to improve it if you think it worths the effort.

Begin with computing all common substrings of all strings in Y. First take two strings, and build a tree of all common substrings. Then, for each other string in Y, remove from the map every substring that does not appear in this string. The complexity is linear with the number of strings in Y, but I can't figure out how many elements might be in the tree so I cannot draw an estimation of the final complexity.

Then find the longest string in X which is a substring of one in the tree.

There must be some improvements to do to keep the tree as small as possible, such as keeping only substrings that are not substrings of others.

于 2013-10-03T12:07:43.907 に答える
1

最初に、配列 X を最も長い文字列から短い順に並べます。このように、すべての Y 文字列の部分文字列である X の最初の文字列が解になります。

マルチプロセッサ アルゴリズムは、各 X 文字列をすべての Y 文字列ですばやくテストするという問題を解決するための最良の方法です。

于 2013-10-03T12:00:03.323 に答える
1

|Y| と書く セット Y 内の文字列の数、およびそれらの合計の長さの len(Y):

  1. Y の文字列を一般化されたサフィックス ツリーに処理します(たとえば、ウッコネンのアルゴリズムを使用します)。一定サイズのアルファベットを想定すると、時間が O(len(Y)) かかります。

  2. そのノードによって識別される文字列が Y のすべての文字列に属しているかどうかに従って、サフィックス ツリーの各ノードをマークします。時間がかかります O(|Y| len(Y))。

  3. X の各文字列について、サフィックス ツリーを調べて、ノードが Y のすべての文字列に属するものとしてマークされているかどうかを確認します。そのようにマークされた最長の文字列を出力します。時間がかかります O(len(X))。

合計時間: O(|Y| len(Y)) + O(len(X))。

于 2013-10-03T12:16:15.907 に答える