類似の単語を探しています

Question

私はスペルチェッカーモジュールを作成しようとしています。

16mbファイルから辞書を作成し、見つかった単語が辞書の単語と似ているかどうかをチェックします（類似= 2文字まで変わります）。

今私は私が速く解決策が存在しなければならないことをかなり確信して... 3分かかります

を設定する50語のレーベンシュタイン距離アルゴリズムおよび処理を使用しています。 Profilerは私のアプリがLevenshtein Distance機能の時間の80％以上を費やしていると言ってくれました。

もっと良いソリューション/アルゴリズムはありますか？ここで

は、私が使用するアルゴリズムのバージョンで実装されています。

def levenshteinDistance(s1, s2): 
    l_s1 = len(s1) 
    l_s2 = len(s2) 
    d = [[a for a in genM(x, l_s2 + 1)] for x in xrange(l_s1 + 1)] 
    for i in xrange(1, l_s1 + 1): 
     for j in xrange(1, l_s2 + 1): 
      d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + decide_of_equality(s1[i - 1],s2[j - 1])) 
    return d[l_s1][l_s2] 

Answer 1

私はコメントで述べたNorvigのスペル修正を、使用していると、それは素晴らしいです。

しかし、あなたの問題には、動的プログラミング編集距離アルゴリズムが書かれています。あなたのアルゴリズムは、データ並列アルゴリズムになります。共有メモリの場合、つまり複数のコアを持っている場合は1台のマシン上で利用することができます。あなたはmap-reduceと呼ばれるものを知っていますか？分散していると思ってはいけません。今のところ、1つのシングルクアッドコアマシンと共有メモリを考えてみてください。ステップ1として、辞書を分割し、各スレッドに部分を割り当てることができます。これは、辞書の一部で編集距離を実行します（マップステップと同様）。後ですべてのスレッドが2の編集距離にあるすべての単語を返します（ステップを減らすのに似ています）。このようにして、プログラムはマルチコアアーキテクチャの恩恵を受けます。

私が考えることができる別のことは、あなたのpythonコードの中には、CPUの集中編集距離アルゴリズムを書くことです。つまり、Python拡張を書くことです。

Answer 2

多分問題はより高いレベルにあります。プロファイラーが、関数に多くの時間が費やされていると伝えると、それをあまりにも頻繁に呼び出すことになるかもしれません。おそらく、テキストの各単語と辞書の各単語を比較していますか？それ以外の方法で試してみてください。テキストの単語の場合は、距離が< = 2の単語を直接生成し、それらが辞書に含まれているかどうかを確認してください。