5

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

テキストをロードし、16 mb ファイルから辞書を作成し、検出された単語が辞書の単語と類似しているかどうかをチェックします (類似 = 2 文字まで変化する) 場合は、辞書の形式に変更します。

現在、レーベンシュタイン距離アルゴリズムを使用しており、50 単語セットの処理に 3 分かかります...

より迅速な解決策が必要であると確信しています。プロファイラーによると、私のアプリは時間の 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]
4

2 に答える 2

2

コメントで言及されている Norvig のスペル コレクターを使用しましたが、これは素晴らしいものです。

ただし、問題が発生すると、動的プログラミング編集距離アルゴリズムが作成されました。あなたのアルゴリズムは、データ並列アルゴリズムの資格があります。共有メモリ上、つまり単一のマシン上で、マルチコアを使用している場合はそれらを活用できます。map-reduce というものを知っていますか? 1 つのクアッド コア マシンと共有メモリを考えてみてください。ステップ 1 として、ディクショナリを分割し、ディクショナリの一部で編集距離を実行する各スレッドに部分を割り当てることができます (マップ ステップと同様)。後で、すべてのスレッドが編集距離 2 ですべての単語を返します (reduce step と同様)。このようにして、プログラムはマルチコア アーキテクチャの恩恵を受けます。

私が考えることができるもう1つのことは、Pythonコード内で、CPU集約型の編集距離アルゴリズムをCで作成することです。つまり、Python拡張機能を作成します。

于 2012-04-08T20:15:40.963 に答える
0

たぶん、問題はより高いレベルにあります。関数に多くの時間が費やされているとプロファイラーが指摘する場合、それは頻繁に呼び出している可能性があります。おそらく、テキスト内の各単語と辞書内の各単語を比較していますか? 逆の方法で試してみてください: テキスト内の単語については、距離 <= 2 の単語を直接生成し、それらが辞書にあるかどうかを確認します。

于 2012-04-08T21:06:40.953 に答える