Подтвердить что ты не робот

Проверка нечеткой/приблизительной подстроки, существующей в более длинной строке, в Python?

Используя алгоритмы типа leveinstein (leveinstein или difflib), легко найти приблизительные соответствия.

>>> import difflib
>>> difflib.SequenceMatcher(None,"amazing","amaging").ratio()
0.8571428571428571

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

Текущее требование: найти нечеткую подстроку на основе порога в большей строке.

например.

large_string = "thelargemanhatanproject is a great project in themanhattincity"
query_string = "manhattan"
#result = "manhatan","manhattin" and their indexes in large_string

Одно решение для грубой силы состоит в том, чтобы сгенерировать все подстроки длиной от N-1 до N + 1 (или другой подходящей длины), где N - длина query_string, и использовать левенштайн на них один за другим и видеть порог.

Есть ли лучшее решение, доступное в python, желательно включенный модуль в python 2.7 или внешний доступный модуль.

UPDATE: модуль регулярного выражения Python работает очень хорошо, хотя он немного медленнее, чем встроенный модуль re для случаев нечеткой подстроки, что является очевидным результатом из-за дополнительных операций. Желаемый результат хорош, и контроль над величиной нечеткости можно легко определить.

>>> import regex
>>> input = "Monalisa was painted by Leonrdo da Vinchi"
>>> regex.search(r'\b(leonardo){e<3}\s+(da)\s+(vinci){e<2}\b',input,flags=regex.IGNORECASE)
<regex.Match object; span=(23, 41), match=' Leonrdo da Vinchi', fuzzy_counts=(0, 2, 1)>
4b9b3361

ОТВЕТЫ

Ответ 1

Новая библиотека регулярных выражений, которая вскоре должна была заменить re, включает в себя нечеткое соответствие.

https://pypi.python.org/pypi/regex/

Синтаксис нечеткого соответствия выглядит довольно выразительно, но это даст вам совпадение с одним или несколькими вставками/добавлениями/удалениями.

import regex
regex.match('(amazing){e<=1}', 'amaging')

Ответ 2

Как насчет использования difflib.SequenceMatcher.get_matching_blocks?

>>> import difflib
>>> large_string = "thelargemanhatanproject"
>>> query_string = "manhattan"
>>> s = difflib.SequenceMatcher(None, large_string, query_string)
>>> sum(n for i,j,n in s.get_matching_blocks()) / float(len(query_string))
0.8888888888888888

>>> query_string = "banana"
>>> s = difflib.SequenceMatcher(None, large_string, query_string)
>>> sum(n for i,j,n in s.get_matching_blocks()) / float(len(query_string))
0.6666666666666666

UPDATE

import difflib

def matches(large_string, query_string, threshold):
    words = large_string.split()
    for word in words:
        s = difflib.SequenceMatcher(None, word, query_string)
        match = ''.join(word[i:i+n] for i, j, n in s.get_matching_blocks() if n)
        if len(match) / float(len(query_string)) >= threshold:
            yield match

large_string = "thelargemanhatanproject is a great project in themanhattincity"
query_string = "manhattan"
print list(matches(large_string, query_string, 0.8))

Над печатью кода: ['manhatan', 'manhattn']

Ответ 3

Недавно я написал библиотеку выравнивания для Python: https://github.com/eseraygun/python-alignment

Используя его, вы можете выполнять как глобальные, так и локальные выравнивания с произвольными стратегиями оценки для любой пары последовательностей. На самом деле, в вашем случае вам нужны полулокальные выравнивания, так как вам не нужны подстроки query_string. Я смоделировал полулокальный алгоритм, используя локальное выравнивание и некоторые эвристики в следующем коде, но легко расширить библиотеку для правильной реализации.

Вот пример кода в файле README, измененном для вашего случая.

from alignment.sequence import Sequence, GAP_ELEMENT
from alignment.vocabulary import Vocabulary
from alignment.sequencealigner import SimpleScoring, LocalSequenceAligner

large_string = "thelargemanhatanproject is a great project in themanhattincity"
query_string = "manhattan"

# Create sequences to be aligned.
a = Sequence(large_string)
b = Sequence(query_string)

# Create a vocabulary and encode the sequences.
v = Vocabulary()
aEncoded = v.encodeSequence(a)
bEncoded = v.encodeSequence(b)

# Create a scoring and align the sequences using local aligner.
scoring = SimpleScoring(1, -1)
aligner = LocalSequenceAligner(scoring, -1, minScore=5)
score, encodeds = aligner.align(aEncoded, bEncoded, backtrace=True)

# Iterate over optimal alignments and print them.
for encoded in encodeds:
    alignment = v.decodeSequenceAlignment(encoded)

    # Simulate a semi-local alignment.
    if len(filter(lambda e: e != GAP_ELEMENT, alignment.second)) != len(b):
        continue
    if alignment.first[0] == GAP_ELEMENT or alignment.first[-1] == GAP_ELEMENT:
        continue
    if alignment.second[0] == GAP_ELEMENT or alignment.second[-1] == GAP_ELEMENT:
        continue

    print alignment
    print 'Alignment score:', alignment.score
    print 'Percent identity:', alignment.percentIdentity()
    print

Выход для minScore=5 выглядит следующим образом.

m a n h a - t a n
m a n h a t t a n
Alignment score: 7
Percent identity: 88.8888888889

m a n h a t t - i
m a n h a t t a n
Alignment score: 5
Percent identity: 77.7777777778

m a n h a t t i n
m a n h a t t a n
Alignment score: 7
Percent identity: 88.8888888889

Если вы удалите аргумент minScore, вы получите только лучшие совпадения.

m a n h a - t a n
m a n h a t t a n
Alignment score: 7
Percent identity: 88.8888888889

m a n h a t t i n
m a n h a t t a n
Alignment score: 7
Percent identity: 88.8888888889

Обратите внимание: все алгоритмы в библиотеке имеют O(n * m) временную сложность, n и m - длины последовательностей.

Ответ 4

Я использую fuzzywuzzy для нечеткого соответствия на основе порогового значения и fuzzysearch, чтобы нечеткие слова извлекать из матча.

process.extractBests принимает запрос, список слов и оценку отсечки и возвращает список кортежей совпадения и оценка выше оценки отсечки.

find_near_matches принимает результат process.extractBests и возвращает начальные и конечные индексы слов. Я использую индексы для построения слов и использую построенное слово для поиска индекса в большой строке. max_l_dist of find_near_matches - это "расстояние Левенштейна", которое необходимо скорректировать в соответствии с потребностями.

from fuzzysearch import find_near_matches
from fuzzywuzzy import process

large_string = "thelargemanhatanproject is a great project in themanhattincity"
query_string = "manhattan"

def fuzzy_extract(qs, ls, threshold):
    '''fuzzy matches 'qs' in 'ls' and returns list of 
    tuples of (word,index)
    '''
    for word, _ in process.extractBests(qs, (ls,), score_cutoff=threshold):
        print('word {}'.format(word))
        for match in find_near_matches(qs, word, max_l_dist=1):
            match = word[match.start:match.end]
            print('match {}'.format(match))
            index = ls.find(match)
            yield (match, index)

Тест;

print('query: {}\nstring: {}'.format(query_string, large_string))
for match,index in fuzzy_extract(query_string, large_string, 70):
    print('match: {}\nindex: {}'.format(match, index))

query_string = "citi"
print('query: {}\nstring: {}'.format(query_string, large_string))
for match,index in fuzzy_extract(query_string, large_string, 30):
    print('match: {}\nindex: {}'.format(match, index))

query_string = "greet"
print('query: {}\nstring: {}'.format(query_string, large_string))
for match,index in fuzzy_extract(query_string, large_string, 30):
    print('match: {}\nindex: {}'.format(match, index))

Выход;
запрос: manhattan
string: thelargemanhatanproject - отличный проект в themanhattincity
матч: manhatan
индекс: 8
матч: manhattin
индекс: 49

запрос: citi
string: thelargemanhatanproject - отличный проект в themanhattincity
матч: город
индекс: 58

запрос: приветствие
string: thelargemanhatanproject - отличный проект в themanhattincity
матч: большой
индекс: 29

Ответ 5

Подходы, описанные выше, хороши, но мне нужно было найти небольшую иглу во множестве сена и в итоге приблизилось к ней следующим образом:

from difflib import SequenceMatcher as SM
from nltk.util import ngrams
import codecs

needle = "this is the string we want to find"
hay    = "text text lots of text and more and more this string is the one we wanted to find and here is some more and even more still"

needle_length  = len(needle.split())
max_sim_val    = 0
max_sim_string = u""

for ngram in ngrams(hay.split(), needle_length + int(.2*needle_length)):
    hay_ngram = u" ".join(ngram)
    similarity = SM(None, hay_ngram, needle).ratio() 
    if similarity > max_sim_val:
        max_sim_val = similarity
        max_sim_string = hay_ngram

print max_sim_val, max_sim_string

Урожайность:

0.72972972973 this string is the one we wanted to find