Метрики сходства строк в Python

Я хочу найти строковое сходство между двумя строками. На этой странице есть примеры некоторых из них. Python имеет реализацию алгоритма Левенштейна. Есть ли лучший алгоритм (и, надеюсь, библиотека python) под этими ограничениями.

Я хочу делать нечеткие совпадения между строками. например, спички ( "Hello, All you people", "hello, all You peopl" ) должны возвращать True
Ложные негативы приемлемы, ложные срабатывания, за исключением крайне редких случаев.
Это делается в настройках, отличных от реального времени, поэтому скорость не является (большой) проблемой.
[Edit] Я сравниваю несколько строк слов.

Будет ли что-то отличное от расстояния Левенштейна (или соотношение Левенштейна) лучшим алгоритмом для моего случая?

Ответ 1

В Университете Шеффилда есть большой ресурс для показателей сходства строк. Он имеет список различных показателей (помимо только Левенштейна) и имеет их реализацию с открытым исходным кодом. Похоже, что многие из них должны быть легко адаптированы к Python.

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

Вот немного списка:

Расстояние Хэмминга
Расстояние Левенштейна
Диалог Needleman-Wunch или Sellers Algorithm
и многое другое...

Ответ 2

Я понимаю, что это не одно и то же, но это достаточно близко:

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

Ответ 3

Этот фрагмент будет вычислять значения сходства difflib, Levenshtein, Sørensen и Jaccard для двух строк. В нижеприведенном фрагменте я повторял код, в котором интересующие строки занимали столбцы [3] и [4] tsv. (pip install python-Levenshtein и pip install distance):

import codecs, difflib, Levenshtein, distance

with codecs.open("titles.tsv","r","utf-8") as f:
    title_list = f.read().split("\n")[:-1]

    for row in title_list:

        sr      = row.lower().split("\t")

        diffl   = difflib.SequenceMatcher(None, sr[3], sr[4]).ratio()
        lev     = Levenshtein.ratio(sr[3], sr[4]) 
        sor     = 1 - distance.sorensen(sr[3], sr[4])
        jac     = 1 - distance.jaccard(sr[3], sr[4])

        print diffl, lev, sor, jac

Ответ 4

Я бы использовал расстояние Левенштейна или так называемое расстояние Дамерау (которое учитывает транспозиции), а не материал difflib по двум причинам: "достаточно быстро" (динамический алгоритм программирования) и "whoooosh" (бит- треск) C-код доступен и (2) хорошо понятное поведение, например Левенштейн удовлетворяет неравенству треугольника и, следовательно, может быть использован, например, дерево Буркхарда-Келлера.

Порог: вы должны рассматривать как "положительный" только те случаи, когда расстояние < (1 - X) * max (len (string1), len (string2)) и отрегулируйте X (коэффициент подобия), чтобы подойти самому. Один из способов выбора X - получить образец совпадений, вычислить X для каждого, игнорировать случаи, когда X < скажем, 0,8 или 0,9, затем сортируйте остаток в порядке убывания X и нарисуйте их мяч и вставьте правильный результат и вычислите меру стоимости ошибки для разных уровней X.

N.B. Пример вашего обезьяны/яблока имеет расстояние 2, поэтому X равно 0,6... Я бы использовал только пороговое значение 0,75, если я отчаянно искал что-то и имел высокий штраф с отрицательным отрицанием

Ответ 5

Это то, что вы имеете в виду?

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

Ответ 6

Я знаю, что это не одно и то же, но вы можете отрегулировать коэффициент, чтобы отфильтровать строки, которые недостаточно похожи и возвращают самое близкое соответствие строке, которую вы ищете.

Возможно, вас больше интересуют метрики сходства семантики.

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() ] )

Его примерно в 20 раз быстрее, чем у difflib.

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

Импорт Левенштейна