2つのテキスト内のすべての一致するサブテキストを見つけるための簡単なアルゴリズム

私の義務により、テキスト間のすべての交点（たとえば、あるテキストから別のテキストへのすべての引用）を見つける必要があることがよくあります。 長い間、私はこれを可能にする標準的なソリューションを探していましたが、それを見つけることができませんでした-通常、完全にまたはわずかに異なるいくつかの問題が解決されます。 たとえば、Python標準ライブラリのdifflib SequenceMatcherクラスは、ハッシュ可能な要素の2つのシーケンスで最も長い共通サブシーケンスを見つけ、その左と右で再帰的に検索を繰り返します。 テキストの1つに、すでに見つかったサブシーケンス内に含まれる短いサブシーケンスが含まれている場合（たとえば、長い引用の一部が他の場所で繰り返された場合）、彼はそれをスキップします。 さらに、私が戦争と平和とアンナ・カレーニナを言葉のリストの形でそこに追い込み、最も長い部分列を見つけるための開始を求めたとき、彼は7分間考えました。 一致するすべてのブロックを要求したとき、彼は去って戻ってきませんでした（ドキュメントには平均線形時間が記載されていますが、Leo Tolstoyの散文には、最悪の場合に2次が生き返ったように見えます）。



最終的に、私は自分のアルゴリズムを思いついたので、おそらく自転車を発明したので、コメントで見たいと思っています。 アルゴリズムは私が必要とするものを正確に実行します：2つのテキストのすべての一致する単語のシーケンスを見つけ（両方のテキストの大きな一致シーケンスの一部を除く）、戦争と平和をアンナカレニーナとすぐに比較します。







原則は次のとおりです。最初に、すべてのバイグラムが各テキストから抽出され、ハッシュテーブルが作成されます。ここで、各バイグラムのシーケンス番号が示されます。 次に、短いテキストが取得され、そのバイグラムが任意の順序でソートされ、そのうちの1つが2番目のテキストの辞書にある場合、フォームのすべてのペアが個別に作成された配列に追加されます（最初の辞書のバイグラム数、2番目の辞書のバイグラム数）。 たとえば、テキスト1でバイグラム「A B」が位置1、2、3で発生し、2番目のテキストで位置17、24、56でも発生した場合、ペア（1、17）、（1、24）は配列に分類されます、（1、56）、（2、17）...これはアルゴリズムの最も弱い点です。両方のテキストが同じ単語で構成されている場合、n x mの数字のペアが配列に分類されます。 ただし、このようなテキストは私たちに出会う可能性は低く（アルゴリズムは自然言語のテキストに焦点を当てています）、意味のない一致の数を減らすために、バイグラムを任意のn-gram（必要な最小限の一致に応じて）に置き換えるか、頻度の高い単語を捨てることができます。



配列の数字の各ペアは、バイグラムレベルで一致します。 ここから一致シーケンスを取得する必要があります。「A B B C」という形式の一致がある場合、テキストのまったく同じ断片が「A B」、「B B」、「B B」tと一致するという事実。 e。は無視する必要があります。 これはすべて、適度に非自明なデータ構造（順序付きセット）を使用して、線形時間で非常に簡単に実行できます。 一定の時間内に要素を自分で配置および破棄し、要素が追加された順序を覚えている必要があります。 このようなPythonのセットの実装は次のとおりです。code.activestate.com / recipes / 576694-orderedset必要に応じて、要素を最後からだけでなく最初から吐き出すことができるはずです。 そこにホイップアップされたpopFirstメソッドを追加します。

def popFirst(self): if not self: raise KeyError('set is empty') for item in self: i = item break self.discard(i) return i
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

残りは非常に簡単です：セットから最初の要素を取り出し、一時的な配列に入れて、次のインデックスと最初と2番目のインデックスのそれぞれが前のものよりも1つ多くなるように、セットから要素を追加できます。 そのようなものがなくなったら、見つかった並列シーケンスを結果の配列に送信し、再度繰り返します。 追加されたすべての要素もセットからスローされます。 したがって、最大の並列シーケンスの長さを同時に取得し、長いシーケンスのサブシーケンスの一致を無視し、見つかったシーケンスとテキスト内の他の場所との接続を失うことはありません（このような一致は、最初または2番目のインデックスによって異なります） 最終的に、出力には配列の配列があり、各サブ配列は一致する単語のシーケンスです。 これらのサブアレイは、長さまたは開始インデックス（特定のフラグメントへのすべての平行な場所を見つけるため）でソートするか、最小長でフィルタリングできます。



OrderedSetを使用せず、バイグラムを使用したPythonコード。 compareTwoTextsはすぐに結果を返します。 テキストの特定の断片が一致するバイグラムの数で理解するには、バイグラム辞書と逆辞書（extractNGrams、getReverseDic）を個別に作成するか、単に単語のリスト（extractWords）を取得する必要があります。各バイグラムは次と同じ位置の単語で始まります彼女自身。

 from OrderedSet import OrderedSet russianAlphabet = {'', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '', ''} def compareTwoTexts(txt1, txt2, alphabet = russianAlphabet): # txt1 should be the shorter one ngramd1 = extractNGrams(txt1, alphabet) ngramd2 = extractNGrams(txt2, alphabet) return extractCommonPassages(getCommonNGrams(ngramd1, ngramd2)) def extractNGrams(txt, alphabet): words = extractWords(txt, alphabet) ngrams = [] for i in range(len(words)-1): ngrams.append( (words[i] + ' ' + words[i+1], i) ) ngramDic = {} for ngram in ngrams: try: ngramDic[ngram[0]].append(ngram[1]) except KeyError: ngramDic[ngram[0]] = [ngram[1]] return ngramDic def extractWords(s, alphabet): arr = [] temp = [] for char in s.lower(): if char in alphabet or char == '-' and len(temp) > 0: temp.append(char) else: if len(temp) > 0: arr.append(''.join(temp)) temp = [] if len(temp) > 0: arr.append(''.join(temp)) return arr def getReverseDic(ngramDic): reverseDic = {} for key in ngramDic: for index in ngramDic[key]: reverseDic[index] = key return reverseDic def getCommonNGrams(ngramDic1, ngramDic2): # ngramDic1 should be for the shorter text allCommonNGrams = [] for nGram in ngramDic1: if nGram in ngramDic2: for i in ngramDic1[nGram]: for j in ngramDic2[nGram]: allCommonNGrams.append((nGram, i, j)) allCommonNGrams.sort(key = lambda x: x[1]) commonNGramSet = OrderedSet((item[1], item[2]) for item in allCommonNGrams) return commonNGramSet def extractCommonPassages(commonNGrams): if not commonNGrams: raise ValueError('no common ngrams') commonPassages = [] temp = [] while commonNGrams: if not temp: temp = [commonNGrams.popFirst()] if not commonNGrams: break if (temp[-1][0]+1, temp[-1][1]+1) in commonNGrams: temp.append((temp[-1][0]+1, temp[-1][1]+1)) commonNGrams.discard((temp[-1][0], temp[-1][1])) else: commonPassages.append(temp) temp = [] if temp: commonPassages.append(temp) return commonPassages