232

単純なあいまい文字列比較を実行できるPythonモジュールを探しています。具体的には、文字列がどれだけ似ているかをパーセンテージで示したいと思います。私はこれが潜在的に主観的であることを知っているので、とりわけ、位置の比較や最長の類似した文字列の一致を実行できるライブラリを見つけたいと思っていました。

基本的に、単一のパーセンテージを生成するのに十分シンプルでありながら、実行する比較のタイプを指定できるように十分に構成可能なものを見つけたいと思っています。

4

12 に答える 12

249

difflibはそれを行うことができます。

ドキュメントからの例：

>>> 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']

見てみな。それはあなたが何かカスタムを構築するのを助けることができる他の機能を持っています。

于 2009-03-25T16:34:09.017 に答える
164

レーベンシュタイン Python 拡張機能と C ライブラリ。

https://github.com/ztane/python-Levenshtein/

レーベンシュタイン Python C 拡張モジュールには、次の高速計算のための関数が含まれています - レーベンシュタイン (編集) 距離、および編集操作 - 文字列の類似度 - 文字列の中央値の近似値、および一般的な文字列の平均化 - 文字列のシーケンスとセットの類似度 通常の文字列と Unicode 文字列の両方をサポートします。

$ pip install python-levenshtein
...
$ python
>>> import Levenshtein
>>> help(Levenshtein.ratio)
ratio(...)
    Compute similarity of two strings.

    ratio(string1, string2)

    The similarity is a number between 0 and 1, it's usually equal or
    somewhat higher than difflib.SequenceMatcher.ratio(), becuase it's
    based on real minimal edit distance.

    Examples:
    >>> ratio('Hello world!', 'Holly grail!')
    0.58333333333333337
    >>> ratio('Brian', 'Jesus')
    0.0

>>> help(Levenshtein.distance)
distance(...)
    Compute absolute Levenshtein distance of two strings.

    distance(string1, string2)

    Examples (it's hard to spell Levenshtein correctly):
    >>> distance('Levenshtein', 'Lenvinsten')
    4
    >>> distance('Levenshtein', 'Levensthein')
    2
    >>> distance('Levenshtein', 'Levenshten')
    1
    >>> distance('Levenshtein', 'Levenshtein')
    0
于 2009-03-26T07:18:51.370 に答える
70

noskloが言ったように、Python 標準ライブラリ のdifflibモジュールを使用します。

difflib モジュールは、 SequenceMatcher()オブジェクトのratio()メソッドを使用して、シーケンスの類似度の尺度を返すことができます。類似度は、0.0 から 1.0 の範囲の float として返されます。

>>> import difflib

>>> difflib.SequenceMatcher(None, 'abcde', 'abcde').ratio()
1.0

>>> difflib.SequenceMatcher(None, 'abcde', 'zbcde').ratio()
0.80000000000000004

>>> difflib.SequenceMatcher(None, 'abcde', 'zyzzy').ratio()
0.0
于 2010-03-10T17:03:57.327 に答える
39

Jellyfishは、音声マッチングを含む多くの文字列比較メトリックをサポートする Python モジュールです。レベンスタイン編集距離の純粋な Python 実装は、Jellyfish の実装と比較してかなり遅いです。

使用例:

import jellyfish

>>> jellyfish.levenshtein_distance('jellyfish', 'smellyfish')
2 
>>> jellyfish.jaro_distance('jellyfish', 'smellyfish')
0.89629629629629637
>>> jellyfish.damerau_levenshtein_distance('jellyfish', 'jellyfihs')
1
>>> jellyfish.metaphone('Jellyfish')
'JLFX'
>>> jellyfish.soundex('Jellyfish')
'J412'
>>> jellyfish.nysiis('Jellyfish')
'JALYF'
>>> jellyfish.match_rating_codex('Jellyfish')
'JLLFSH'`
于 2011-12-03T19:20:23.713 に答える
23

私はnoskloの答えが好きです; もう 1 つの方法は、ダメラウ レーベンシュタイン距離です。

「情報理論とコンピュータ サイエンスでは、ダメラウ レーベンシュタイン距離は 2 つの文字列間の '距離' (文字列メトリック)、つまり、ある文字列を別の文字列に変換するのに必要な操作の最小数を数えることによって与えられる、シンボルの有限シーケンスです。操作は、1 文字の挿入、削除、置換、または 2 文字の転置として定義されます。」

Wikibooksからの Python での実装:

def lev(a, b):
    if not a: return len(b)
    if not b: return len(a)
    return min(lev(a[1:], b[1:])+(a[0] != b[0]), \
    lev(a[1:], b)+1, lev(a, b[1:])+1)

Wikibooks からの詳細、これにより、最長共通部分文字列 (LCS)の長さが得られます。

def LCSubstr_len(S, T):
    m = len(S); n = len(T)
    L = [[0] * (n+1) for i in xrange(m+1)]
    lcs = 0
    for i in xrange(m):
        for j in xrange(n):
            if S[i] == T[j]:
                L[i+1][j+1] = L[i][j] + 1
                lcs = max(lcs, L[i+1][j+1])
    return lcs
于 2009-03-25T16:46:32.327 に答える
18

Google 独自のgoogle-diff-match-patchもあります (「現在 Java、JavaScript、C++、および Python で利用可能」)。

（私は自分でpythonのdifflibしか使用していないため、コメントできません）

于 2009-03-25T17:47:33.910 に答える
8

Another alternative would be to use the recently released package FuzzyWuzzy. The various functions supported by the package are also described in this blogpost.

于 2011-08-29T18:41:14.373 に答える
5

私は魔法のように機能するダブルメタフォンを使用しています。

例：

>>> dm(u'aubrey')
('APR', '')
>>> dm(u'richard')
('RXRT', 'RKRT')
>>> dm(u'katherine') == dm(u'catherine')
True

更新: Jellyfish にもあります。フォネティック エンコーディングに分類されます。

于 2011-12-16T06:30:54.423 に答える
4

私は、Seat Geek の Fuzzy Wuzzy を使用して大きな成功を収めています。

https://github.com/seatgeek/fuzzywuzzy

具体的にはトークンセット比率機能...

彼らはまた、ファジー文字列マッチングのプロセスについても素晴らしい記事を書いています。

http://seatgeek.com/blog/dev/fuzzywuzzy-fuzzy-string-matching-in-python

于 2013-08-14T03:07:38.193 に答える
3

これは、2 つの単語で最も長い共通部分文字列を計算するための Python スクリプトです (複数単語のフレーズで機能するように調整する必要がある場合があります)。

def lcs(word1, word2):

    w1 = set(word1[i:j] for i in range(0, len(word1))
             for j in range(1, len(word1) + 1))

    w2 = set(word2[i:j] for i in range(0, len(word2))
             for j in range(1, len(word2) + 1))

    common_subs = w1.intersection(w2)

    sorted_cmn_subs = sorted([
        (len(str), str) for str in list(common_subs)
        ])

    return sorted_cmn_subs.pop()[1]
于 2009-04-20T16:32:11.190 に答える
3

Charicar の simhash を使用して行う方法は次のとおりです。これは長いドキュメントにも適しています。ドキュメント内の単語の順序を変更した場合にも 100% の類似性を検出します。

http://blog.simpliplant.eu/calculating-similarity-between-text-strings-in-python/

于 2011-11-19T11:21:00.343 に答える
2

Fuzzyモジュールを見てみましょう。これは、soundex、NYSIIS、および double-metaphone 用の高速な (C で記述された) ベースのアルゴリズムを備えています。

良い紹介はhttp://www.informit.com/articles/article.aspx?p=1848528にあります。

于 2012-04-03T12:12:54.937 に答える