55

Pythonでスペルチェックプログラムをプログラミングしています。有効な単語 (辞書) のリストがあり、この辞書から、特定の無効な単語からの編集距離が 2 の単語のリストを出力する必要があります。

無効な単語から編集距離が 1 のリストを生成することから始める必要があることはわかっています (その後、生成されたすべての単語に対して再度実行します)。inserts(...)、deletions(...)、changes(...) の 3 つのメソッドがあり、編集距離が 1 の単語のリストを出力する必要があります。inserts は、すべての有効な単語を 1 つ多い文字で出力します。指定された単語、deletions はすべての有効な単語を 1 文字少なく出力し、changes はすべての有効な単語を 1 文字だけ減らして出力します。

たくさんの場所をチェックしましたが、このプロセスを説明するアルゴリズムが見つからないようです。私が思いついたアイデアはすべて、辞書リストを複数回ループする必要があり、非常に時間がかかります。誰かが洞察を提供できれば、私は非常に感謝しています。

4

9 に答える 9

73

あなたが見ているのは編集距離と呼ばれるもので、ここに wiki の素晴らしい説明があります。2 つの単語間の距離を定義する方法はたくさんあります。必要な距離はレーベンシュタイン距離と呼ばれ、Python での DP (動的プログラミング) の実装です。

def levenshteinDistance(s1, s2):
    if len(s1) > len(s2):
        s1, s2 = s2, s1

    distances = range(len(s1) + 1)
    for i2, c2 in enumerate(s2):
        distances_ = [i2+1]
        for i1, c1 in enumerate(s1):
            if c1 == c2:
                distances_.append(distances[i1])
            else:
                distances_.append(1 + min((distances[i1], distances[i1 + 1], distances_[-1])))
        distances = distances_
    return distances[-1]

さらにいくつかの実装がここにあります。

于 2015-09-14T06:52:27.437 に答える
9

これがレーベンシュタイン距離の私のバージョンです

def edit_distance(s1, s2):
    m=len(s1)+1
    n=len(s2)+1

    tbl = {}
    for i in range(m): tbl[i,0]=i
    for j in range(n): tbl[0,j]=j
    範囲内の i の場合 (1, m):
        範囲 (1, n) の j の場合:
            コスト = 0 if s1[i-1] == s2[j-1] そうでなければ 1
            tbl[i,j] = min(tbl[i, j-1]+1, tbl[i-1, j]+1, tbl[i-1, j-1]+コスト)

    tbl[i,j] を返す

print(edit_distance("Helloworld", "HelloWorld"))
于 2014-06-11T20:56:01.203 に答える
1

上記の Santoshi のソリューションに似ていますが、3 つの変更を加えました。

  1. 5 行ではなく 1 行の初期化
  2. コストを単独で定義する必要はありません (int(boolean) 0 または 1 を使用するだけです)
  3. ダブル for ループの代わりに使用する製品 (この最後のものは表面的なものであり、ダブル ループは避けられないようです)
from itertools import product

def edit_distance(s1,s2):      
   d={ **{(i,0):i for i in range(len(s1)+1)},**{(0,j):j for j in range(len(s2)+1)}}
   for i, j in product(range(1,len(s1)+1), range(1,len(s2)+1)): 
       d[i,j]=min((s1[i-1]!=s2[j-1]) + d[i-1,j-1], d[i-1,j]+1, d[i,j-1]+1)
   return d[i,j]
于 2020-11-12T14:16:25.587 に答える
0

レーベンシュタイン距離アルゴリズムを使用する代わりに、BK ツリーまたはTRIEを使用します。これらのアルゴリズムは距離を編集するよりも複雑さが少ないためです。これらのトピックをよく参照すると、詳細な説明が得られます。

このリンクは、スペル チェックの詳細に役立ちます。

于 2017-04-01T12:54:18.747 に答える