54

2 つの文字列間の文字列の類似性を見つけたい。このページには、それらのいくつかの例があります。Python にはレーベンシュタイン アルゴリズムが実装されています。これらの制約の下で、より優れたアルゴリズム (およびできれば Python ライブラリ) はありますか。

  1. 文字列間のあいまい一致を実行したい。たとえば、matches('Hello, All you people', 'hello, all you people') は True を返す必要があります
  2. 偽陰性は許容されますが、非常にまれなケースを除いて、偽陽性は許容されません。
  3. これは非リアルタイム設定で行われるため、速度は (あまり) 重要ではありません。
  4. [編集] 複数の単語の文字列を比較しています。

私の場合、レーベンシュタイン距離(またはレーベンシュタイン比)以外の何かがより良いアルゴリズムでしょうか?

4

6 に答える 6

96

私はそれが同じものではないことを認識していますが、これは十分に近いです:

>>> import difflib
>>> a = 'Hello, All you people'
>>> b = 'hello, all You peopl'
>>> seq=difflib.SequenceMatcher(a=a.lower(), b=b.lower())
>>> seq.ratio()
0.97560975609756095

これを関数として作成できます

def similar(seq1, seq2):
    return difflib.SequenceMatcher(a=seq1.lower(), b=seq2.lower()).ratio() > 0.9

>>> similar(a, b)
True
>>> similar('Hello, world', 'Hi, world')
False
于 2009-09-24T13:10:55.380 に答える
25

シェフィールド大学には、文字列類似性指標に関する優れたリソースがあります。さまざまなメトリック (レーベンシュタインだけでなく) のリストがあり、それらのオープンソースの実装があります。それらの多くは、Python に簡単に適応できるはずです。

http://web.archive.org/web/20081224234350/http://www.dcs.shef.ac.uk/~sam/stringmetrics.html

リストの一部を次に示します。

  • ハミング距離
  • レーベンシュタイン距離
  • Needleman-Wunch 距離またはセラーズ アルゴリズム
  • などなど...
于 2009-09-24T12:13:28.340 に答える
9

レーベンシュタイン距離、またはいわゆるダメラウ距離 (転​​置を考慮に入れる) を、2 つの理由 (1) 「十分に速い」(動的プログラミング アルゴリズム) と「フーッ」(ビットバッシング) C のために difflib のものではなく使用します。コードが利用可能であり、(2) よく理解された動作、たとえばレーベンシュタインは三角形の不等式を満たしているため、たとえば Burkhard-Keller ツリーで使用できます。

しきい値: 距離 < (1 - X) * max(len(string1), len(string2)) の場合のみ「正」として扱い、X (類似係数) を自分に合うように調整する必要があります。X を選択する 1 つの方法は、一致のサンプルを取得し、それぞれについて X を計算し、X < 0.8 または 0.9 のケースを無視し、残りを X の降順で並べ替え、それらを目で見て、正しい結果を挿入し、いくつかを計算することです。 X のさまざまなレベルの間違いのコスト測定.

NBあなたの類人猿/リンゴの例は距離が2なので、Xは0.6です...必死に何かを探していて、偽陰性のペナルティが高い場合は、0.75という低いしきい値のみを使用します

于 2009-09-24T14:41:31.583 に答える
6

そうですか？

>>> get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy'])
['apple', 'ape']
>>> import keyword
>>> get_close_matches('wheel', keyword.kwlist)
['while']
>>> get_close_matches('apple', keyword.kwlist)
[]
>>> get_close_matches('accept', keyword.kwlist)
['except']

http://docs.python.org/library/difflib.html#difflib.get_close_matchesを見てください

于 2009-09-24T11:46:47.830 に答える
2

これが同じではないことはわかっていますが、比率を調整して、十分に類似していない文字列を除外し、探している文字列に最も近い一致を返すことができます。

おそらく、意味的類似性メトリックにもっと興味があるでしょう。

https://www.google.com/search?client=ubuntu&channel=fs&q=semantic+similarity+string+match&ie=utf-8&oe=utf-8

速度は問題ではないとおっしゃっていましたが、アルゴリズムで多くの文字列を処理している場合は、以下が非常に役立ちます。

def spellcheck(self, sentence):
    #return ' '.join([difflib.get_close_matches(word, wordlist,1 , 0)[0] for word in sentence.split()])
    return ' '.join( [ sorted( { Levenshtein.ratio(x, word):x for x in wordlist }.items(), reverse=True)[0][1] for word in sentence.split() ] )

difflib よりも約 20 倍高速です。

https://pypi.python.org/pypi/python-Levenshtein/

輸入レーベンシュタイン

于 2014-11-12T19:28:21.573 に答える