パターンに一致する最短文を見つけるアルゴリズム

Question

私はここで問題を解決しようとしています。

プログラムには、a - z、A - Z、0 - 9、フルストップ（。）、およびスペースの文字を含むテキストファイルが与えられます。テキストファイル内の単語は、純粋にa-z、A-Z、および0-9で構成されています。プログラムはいくつかの質問を受け取ります。各クエリは、ファイルに既に存在する完全な単語のセットで構成されています。プログラムは、すべての単語が（任意の順序で）存在するファイルから最小のフレーズを戻す必要があります。そのようなフレーズが多数ある場合は、最初のフレーズを返します。

ここは例です。私たちは、ファイルが含まれていることを言ってみましょう：

Bar is doing a computer science degree. Bar has a computer at home. Bar is now at home. 

クエリ1：

Bar computer a 

応答：

Bar has a computer 

クエリ2：

Bar home 

は応答：

home. Bar 

私はこの解決策を考えました。クエリ1では、Barが最初に検索され、Barの3つのすべての出現がリストとしてアセンブルされます。リスト内の各ノードには、最小フレーズの開始位置と合計長さも含まれます。したがって、

第1ノード「Bar、0、1」[クエリ、開始位置、全長]のようになります。 同様に2番目と3番目のノード。

次のコンピュータが検索されます。 Barの出現ごとのコンピュータの最小距離が計算されます。

1ノード "バーコンピュータ"、0、5

2ノード "バーコンピュータ"、7、4などの他のノードのための

次へ "" を検索します。検索は、各ノードに記載されている開始位置から開始しなければならず、順序が重要でないため、単語が見つかるまで左右に移動する必要があります。発生頻度の最小値を選択する必要があります。

正しい解決策ですか？私はこのようなやり方をしていると感じています。私は多くの場合に注意しなければなりません。

単語が一意であれば、それはTSPの変種になりますか？

Answer 1

TSPはこの問題を考える良い方法ではありません。 nをテキストの長さとし、mをクエリの長​​さとする。 n> mとする。ナイーブ溶液

best = infinity 
for i = 1 to n 
    for j = i to n 
    all_found = true 
    for k = 1 to m 
     found = false 
     for l = i to j 
     if text[l] == query[k] 
      found = true 
     all_found = all_found || found 
    if all_found && j - i < best 
     best = j - i 
     best_i = i 
     best_j = j 

既に有界長の単語のO（N メートル）における多項式時間です。さあ、最適化しましょう。

まず、ハッシュセットを使用して内部ループをホイストします。

best = infinity 
for i = 1 to n 
    for j = i to n 
    subtext_set = {} 
    for l = i to j 
     subtext_set = subtext_set union {text[l]} 
    all_found = true 
    for k = 1 to m 
     all_found = all_found && query[k] in subtext_set 
    if all_found && j - i < best 
     best = j - i 
     best_i = i 
     best_j = j 

我々は代わりに二分木を使用する場合、実行時間は現在O（N ）、又はO（N ログN）です。

今度は、上限が1増加するとsubtext_setを再計算するのは無駄です。

best = infinity 
for i = 1 to n 
    subtext_set = {} 
    for j = i to n 
    subtext_set = subtext_set union {text[l]} 
    all_found = true 
    for k = 1 to m 
     all_found = all_found && query[k] in subtext_set 
    if all_found && j - i < best 
     best = j - i 
     best_i = i 
     best_j = j 

我々はO（N 2 メートル）にいます。今度はsubtext_setがただ1つの要素によって増補されたときにクエリ全体を再チェックするのは無駄に思えます。

query_set = {} 
for k = 1 to m 
    query_set = query_set union {query[k]} 
best = infinity 
for i = 1 to n 
    subtext_set = {} 
    num_found = 0 
    for j = i to n 
    if text[l] in query_set && text[l] not in subtext_set 
     subtext_set = subtext_set union {text[l]} 
     num_found += 1 
    if num_found == m && j - i < best 
     best = j - i 
     best_i = i 
     best_j = j 

我々は（nは）Oにいます。 O（n）に行くには、いくつかの洞察が必要です。まずは、各部分は、たとえば

text = Bar has a computer at home. Bar 
     1 2 3 4  5 6  7 
query = Bar computer a 

# j 1 2 3 4 5 6 7 
i +-------------- 
1 | 1 1 2 3 3 3 3 
2 | 0 0 1 2 2 2 3 
3 | 0 0 1 2 2 2 3 
4 | 0 0 0 1 1 1 2 
5 | 0 0 0 0 0 0 1 
6 | 0 0 0 0 0 0 1 
7 | 0 0 0 0 0 0 1 

のために含まれているどのように多くのクエリの言葉を見てみましょう。この行列持つ非増加列と行を非減少、そしてそれは、一般的には事実です。値がmのエントリーの下側を横切りたいのは、より長い解に対応するからです。アルゴリズムは以下の通りです。現在のi、jがすべてのクエリーワードを持つ場合は、iを増やします。それ以外の場合は、jを大きくします。

私たちの現在のデータ構造では、データ構造が削除をサポートしていないため、jを増やすことはできますが、増やすことはできません。セットの代わりに、クエリワードの最後のコピーが消えたときには、マルチセットとデクリメントを維持する必要があります。num_found

best = infinity 
count = hash table whose entries are zero by default 
for k = 1 to m 
    count[query[k]] = -1 
num_found = 0 
i = 1 
j = 0 
while true 
    if num_found == m 
    if j - i < best 
     best = j - i 
     best_i = i 
     best_j = j 
    count[text[i]] -= 1 
    if count[text[i]] == -1 
     num_found -= 1 
    i += 1 
    else 
    j += 1 
    if j > n 
     break 
    if count[text[j]] == -1 
     num_found += 1 
    count[text[j]] += 1 

O（n）に到着しました。最後の漸近的に関連する最適化は、クエリ内の要素についてのみカウントを格納することによって、余分な空間の使用をO（n）からO（m）に減らすことです。私は運動としてそれを残します。 （空のクエリを処理するには、さらに注意が必要です。）

Answer 2

この種の問題については、Suffix Treesを使用することをお勧めします。