大きなセットの単語を小さなセットのリストと照合する

Question

アルゴリズムがあるように感じますが、何が呼び出されるのか分かりません。

('apple', 'orange', 'potato', 'tomato', 'river', 'mountain', 'forest')

と要件と見なされる小さなセットのリスト、あなたは「大規模な言葉で設定したとしましょう：
[('apple'), ('potato', 'tomato'), ('cockroach', 'dynamite')]

は/事前計算をハッシュする方法はありますあなたが必要とする言葉のセットが1つずつ順番に通らなくても満たされているかを知ることができるような小さなセットのリスト？
この例では、関数は最初の2つの要件（ 'apple'）と（ 'potato'、 'tomato'）が一致したことを示します。

Answer 1

要件側の前処理は役に立たないと思います。

しかし、より大きなセット側では、制約をチェックするときにバイナリ検索を行うことができるそのリストを事前に並べ替えることができます。

大きなセットにnエレメントがあり、要件にkエレメントがある場合は、大きなセット全体をスキャンすることによって、尋ねるのはO(kn)です。ただし、バイナリ検索を使用すると、O(klog(n))の時間がかかります。両者の違いは実際には莫大です。

Answer 2

大きなリストとすべての小さなリストを並べ替えます。これは、小さいリストの文字列が順番に一致するため、大きなリストを反復処理し、小さなリストの最初の不一致の要素をチェックすることで、小さなリストを一致させることができることを意味します。

これを行うには、大きなセットに文字列が存在するかどうかを確認するハッシュセットを作成し、文字列キーから、その文字列が最初に不一致の要素であるすべての文字列リストのセットにマップするハッシュを作成します。擬似コードであなたのアルゴリズムは次のとおりです。

for each string S in large list: 
    set of lists SOL = hashmap[S] 
    for each list L in SOL: 
     remove L from SOL and remove SOL from hashmap if now empty 
     find next string S2 in L after S 
     if S2 doesn't exist (i.e. S was the last unmatched string in the small list) 
      L is a match, add to your list of matches 
     else if S2 is in largelisthashset 
      set of lists SOL2 = hashmap[S2], create if doesn't exist 
      add L to SOL2 
      hashmap[S2] = SOL2 

ステップO（1）である「Sの後にはLで次の文字列S2を見つける」ようにするには、各小リスト内の現在の位置へのポインタを維持することができます。だから、文字列リストとインデックスを持つオブジェクトを持っていれば、これらのオブジェクトのセットを各文字列のハッシュに格納することになります。セットはソートする必要はありません。

ハッシュルックアップがO（1）であると仮定して、最初のソートではO（n log（n））、一致する文字列リストではO（n * m）リスト内のすべての文字列が一致している場合にのみ、より小さいリスト内の文字列が一致するため、実際にはそれほど少なくありません。

このアルゴリズムは、より大きなリストに項目を含まないより小さいリストは決して処理されないので、チェック - 各リスト手法と比較して時間を節約します。大きなリストがはるかに大きく、小さいリストの数が少ない場合は、大きいリストのアイテムのハッシュを使用して各小さなリストをチェックするので、小さいリストのしかし、あなたのハッシュマップにリストのセットを持っているソートされたリストを維持し、大きなリストのハッシュセット（または大きなリストのインデックスへの文字列のハッシュ）を使用することでスピードアップすることができますハッシュマップにエントリを持たない外部ループ。

したがって、実際にはリストの相対的な長さ、重なり、数によって異なります。