Что такое простой алгоритм сопоставления нечетких строк в Python?

Ответ 1

Мне нравится Дрю ответ.

Вы можете использовать difflib, чтобы найти самое длинное совпадение:

>>> a = 'The quick brown fox.'
>>> b = 'The quick brown fox jumped over the lazy dog.'
>>> import difflib
>>> s = difflib.SequenceMatcher(None, a, b)
>>> s.find_longest_match(0,len(a),0,len(b))
Match(a=0, b=0, size=19) # returns NamedTuple (new in v2.6)

Или выберите минимальный порог соответствия. Пример:

>>> difflib.SequenceMatcher(None, a, b).ratio()
0.61538461538461542

Ответ 2

Взгляните на эту библиотеку python, которую SeatGeek открыла вчера. Очевидно, что большинство из этих проблем очень зависимы от контекста, но это может вам помочь.

from fuzzywuzzy import fuzz

s1 = "the quick brown fox"
s2 = "the quick brown fox jumped over the lazy dog"
s3 = "the fast fox jumped over the hard-working dog"

fuzz.partial_ratio(s1, s2)
> 100

fuzz.token_set_ratio(s2, s3)
> 73

Сайт SeatGeek

и рефинансирование Github

Ответ 3

Если все, что вы хотите сделать, это проверить, соответствуют ли все слова в строке другой строке, что один лайнер:

if not [word for word in b.split(' ') if word not in a.split(' ')]:
    print 'Match!'

Если вы хотите забить их вместо бинарного теста, почему бы просто не сделать что-то вроде:

((# совпадающих слов)/(# слов в большей строке)) * ((# слов в меньшей строке)/(# слов в большей строке))

?

Если бы вы этого захотели, вы могли бы стать фаворитом и сделать нечеткое соответствие для каждой строки.

Ответ 4

Вы можете изменить алгоритм Левенштейна для сравнения слов, а не символов. Это не очень сложный алгоритм, и источник доступен на многих языках в Интернете.

Левенштейн работает, сравнивая два массива символов. Нет никакой причины, чтобы та же логика не могла применяться к двум массивам строк.

Ответ 5

Я сделал это некоторое время назад с С#, мой предыдущий вопрос здесь. Для вашего интереса есть стартовый алгоритм, вы можете легко преобразовать его в python.

Идеи, которые вы должны использовать, написание собственных алгоритм выглядит примерно так:

• У вас есть список с оригинальными "заголовками" (слова/предложения, которые вы хотите сопоставить с).
• Каждый элемент заголовка должен иметь минимальный балл матча на слово/предложение, игнорировать название также.
• Вы также должны иметь глобальный минимальный процент от конечного результата.
• Вы должны рассчитать каждое слово слово Левенштейн расстояние.
• Вы должны увеличить общий вес матча, если слова идут в том же (быстрый коричневый против быстрого коричневого цвета, должен иметь окончательно более высокий вес чем быстрый коричневый или коричневый быстро.)

Ответ 6

Вы можете попробовать FuzzySearchEngine из https://github.com/frazenshtein/fastcd/blob/master/search.py.

Этот нечеткий поиск поддерживает только поиск слов и имеет фиксированную допустимую ошибку для слова (только одна замена или транспонирование двух смежных символов).

Однако, например, вы можете попробовать что-то вроде:

import search

string = "Chapter I. The quick brown fox jumped over the lazy dog."
substr = "the qiuck broqn fox."

def fuzzy_search_for_sentences(substr, string):  
    start = None
    pos = 0
    for word in substr.split(" "):
        if not word:
            continue
        match = search.FuzzySearchEngine(word).search(string, pos=pos)
        if not match:
            return None
        if start is None:
            start = match.start()
        pos = match.end()
    return start

print(fuzzy_search_for_sentences(substr, string))

11 будет напечатано

Ответ 7

Левенштейн должен работать нормально, если вы сравниваете слова (строки, разделенные последовательностями символов остановки) вместо отдельных букв.

def ld(s1, s2):  # Levenshtein Distance
    len1 = len(s1)+1
    len2 = len(s2)+1
    lt = [[0 for i2 in range(len2)] for i1 in range(len1)]  # lt - levenshtein_table
    lt[0] = list(range(len2))
    i = 0
    for l in lt:
        l[0] = i
        i += 1
    for i1 in range(1, len1):
        for i2 in range(1, len2):
            if s1[i1-1] == s2[i2-1]:
                v = 0
            else:
                v = 1
            lt[i1][i2] = min(lt[i1][i2-1]+1, lt[i1-1][i2]+1, lt[i1-1][i2-1]+v)
    return lt[-1][-1]

str1 = "The quick brown fox"
str2 = "The quick brown fox jumped over the lazy dog"

print("{} words need to be added, deleted or replaced to convert string 1 into string 2".format(ld(str1.split(),str2.split())))