大規模な文字列の比較

Question

私は大きな文字列のセットで同様の文字列のペアを検索しようとしています。私は約1億の文字列を持っており、文字列の類似性は編集距離として測定されます。たとえば、「これは文章です」、「これも文章です」などが類似しています。

各2つの文字列間の類似度を計算することは現実的ではなく、結果として100M×100Mの計算が行われます。私は、最初にストリングを「おおよそ似たような」サブセットにグループ化し、その後、サブセット内の各ストリングペアを計算するための分裂征服戦略を検討しています。例えば、

str1 = "this is a sentence" 
str2 = "this is also a sentence" 
str3 = "Mary loves elephants" 
str4 = "Mary loves an elephant" 
str5 = "Mark loves elephants" 

私はサブセット[STR1、STR2]および他のサブセット[STR3、STR4、STR5]を持つように願って、私は次の5つの文字列を持っていると言います。次に、str1とstr2を比較して、それらが似ているかどうかを確認します。同様のペアを見つけるためにstr3、str4、str5も比較します。総計はC^2_5 = 10からC^2_2 + C^2_3 = 4に減少します。

分割は高速でなければならず、したがって正確である必要はありません。サブセットは重複する可能性があります。時には、同じサブセットに文字列の類似のペアが含まれていないことがある場合は受け入れ可能です。次に、近くのサブセットをスキャンします。

私は、文字列を整数に大まかにマッピングする（衝突は問題ではありません）、順序保持されたハッシュメソッドを見つけようとしていて、各文字列を近い整数で候補文字列と照合して確認しました。しかし、私はそのようなアルゴリズムを見つけることができません。

私はPythonを使用しています。解決策が別のプログラミング言語でのみ適用可能であれば、私は試してみます。

ありがとうございました。

Answer 1

並べ替え時にキー機能としてLevenshtein distanceを使用できます。

import requests 
import Levenshtein as L 

def download_moby_dick(): 
    moby_dick_url = 'https://www.gutenberg.org/files/2701/2701-0.txt' 
    return requests.get(moby_dick_url).text 

def sentences_in_book(book): 
    sentences = (s for s in re.split(r'[.;?!]\s|\r\n\r\n', moby_dick)) 
    sentences = (re.sub('\s+', ' ', s).strip() for s in sentences) 
    sentences = (s for s in sentences if len(s) > 10) 
    return list(sentences) 

sentences = sentences_in_book(download_moby_dick()) 

# sort by length 
sentences.sort(key=len) 

# median length sentence 
target = sentences[len(sentences)//2] 

# sort by levenshtein distance to target 
def keyfunc(sentence): 
    return L.distance(target, sentence) 

sentences.sort(key=keyfunc) 

これにより、類似した文章がまとめられた大雑把な順序が得られます。それをスピードアップするには、タスクをさらに分割する必要があります。たとえば、各単語の一部の文字のみを使用して入力文を短縮したり、長さがほぼ同じ検索文のみを使用したりします。