2セット間の文字列のすべてのペアを見つけるための良いアルゴリズムは、1ストリングからすべての単語がすべて第2の文字列に含まれていますか？

cs.stackexchange https://cs.stackexchange.com/questions/120658

  •  29-09-2020
  •  | 
  •  

質問

私は2つの大きな文字列を持っています（実際には製品名はあります）。 「大きい」とは数百万の弦を意味します。

例：

セット1：

Some good product
Another product
Some name
Blah
.

セット2：

Very long some product name with words blah
Another very long product name
asd asd sad sad asdsa
Blah blah blah
.

セット1には「良い」名が含まれています。セット2には「ダーティ」名が含まれています。

私は

セット2からのすべてのアイテムのために（さらに：item2）item1からのすべての単語がitem2 に含まれるように、セット1から最長の項目を見つけます（詳細：item1）。 >

与えられた例では、ペアは次のようになります。

Very long SOME product NAME with words blah => Some name
ANOTHER very long PRODUCT name              => Another product
asd asd sad sad asdsa                       => none
BLAH blah blah                              => blah
.

これまでのところ私はブルートフォースアルゴリズムよりも良いものを考えることができませんでした：

  1. セット1からの文字列を単語に分割=単語のリストを取得し、設定3
    2. に設定します。
  2. セット2から単語にすべての文字列を分割=単語のリストを取得し、設定4
    3. に設定します。
  3. SET 3から単語のリストを選択します（詳細：List3）、SET 4からの単語のリストとList3に完全に含まれているリストが見つかるまで、それをすべてのリストに比較します。

    4. しかしそれはかなり高い複雑さを持っており、かなり遅く機能します。私の単純な実装には1ペアが見つかるのに約1.8がかかります（Set 1には3mlの項目があり、セット2には4mlの項目があります）。 MySQL-FullText索引を使用して同じタスクを実装する場合（あらゆる単語を含む文字列を検索することができます）場合1検索には約0.4がかかります。だから私は小さな血液でここに適用できるいくつかの良いアプローチがあるかどうか疑問に思います:)

    私のプログラミング言語はPHP7です。データはMySQL DBに格納されています。

役に立ちましたか？

解決

実際には、実際に有効である可能性がある2つの可能なアプローチを挙げていますが、最悪の走行時間はあなたがリストされたものよりは良くはありません。

インデックス

各単語のインデックスを作成することができます。ハッシュテーブルを作成します。任意のクリーン名に表示される各単語について、ハッシュテーブルはその単語をその単語を含むすべてのダーティー名のリストにマッピングします。このハッシュテーブルは、汚れた名前のセット（SET2）のリニアスキャンで一度だけ構築できます。

その後、クリーンな名前を付けて、クリーン名の単語を繰り返します。各単語について、ハッシュテーブルで調べて、その単語を含むすべてのダーティー名を繰り返し、クリーン名と共通している単語の数を確認してください。最良の一致を保ちます。

これは少し最適化することができます。クリーン名にたくさんのダーティ名で発生する単語が含まれている場合は、その単語を処理することができます。そのため、各単語が汚れた名前（その周波数）で発生し、これをハッシュテーブルに保存する回数を見つけることができます。それから、きれいな名前を考えると、頻度を増やすためにクリーン名の単語を繰り返すことができ、これまでに見つかった最善の一致を追跡します。長さ $ \ etell $ の一致を見つけた場合は、 $ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \の長さの一致を見つけた場合は、早く早く停止することができます。 ELL-1 $ クリーン名の最高周波数単語。

は

を試す

名前の単語の順番は無関係であるため、各フレーズの単語を並べ替えます。たとえば、「いくつかの良い製品」は「良い製品のように」になります。各セットの各名前にこれを行います。

次に、良い名前のセット（Set1）を表すトライを構築します。たとえば、あなたの例では、トライは

になります 
+-- another --+-- product --+
|`-- blah --+
|`-- good --+-- product --+-- some --+
 `-- name --+-- some --+
.

今、汚れた名前を選んでください。トライからの試合を見つけたいです。私はあなたがすべての一致を見つけるために再帰的アルゴリズムを使うことを勧めます：trie $ w_1 \ cdots w_n $ "> $ t $ 、 $ t $ のルートからエッジがあるかどうかを確認します。 $ w_1 $ であれば、そのエッジで指された亜亜紀にある $ w_2 \ cdots w_n $ のすべての一致を再帰的に見つけます。また、 $ w_2 \ cdots w_n $ のすべての一致を再帰的に検索します。 $ t $ 。すべての一致を見つけたら、最長のものを保管してください。

例えば、「もう1つの非常に長い製品名」の場合、ソートした後は「もう1つの長い名前製品は非常に」になります。 Subtreie +-- product --+の「ロングネーム製品」のすべての試合を再帰的に見つけることによって、そしてメイントライの「ロングネーム製品」のすべての一致を見つけることによって、TRIEの上に見えます。

この検索プロセスは、例えば、これまでに見つかった最長の一致を追跡し、再帰的なコールが何語が一致した単語の数に基づいてより長い一致を見つけることができるかどうかを早期に停止することによって、さまざまな方法で最適化することができます。遠くの単語の残りの単語。

辞書順序で並べ替える必要はありません。一貫した限り、他の順序でソートすることができます。たとえば、データセット全体の単語の頻度（最初に最も一般的な単語に）並べ替えることができます。これは再帰呼び出しの数を減らすのに役立ちます。

ライセンス： CC-BY-SA と 帰属
所属していません cs.stackexchange
scroll top