¿Verificando la subcadena difusa / aproximada existente en una cadena más larga, en Python?

Usando algoritmos como leveinstein (leveinstein o difflib), es fácil encontrar coincidencias aproximadas.

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

Las coincidencias difusas se pueden detectar al decidir un umbral según sea necesario.

Requisito actual: para encontrar una subcadena difusa basada en un umbral en una cadena más grande.

p.ej.

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

Una solución de fuerza bruta es generar todas las subcadenas de longitud N-1 a N + 1 (u otra longitud coincidente), donde N es la longitud de query_string, y usar levenstein en ellas una por una y ver el umbral.

¿Existe una mejor solución disponible en python, preferiblemente un módulo incluido en python 2.7, o un módulo externo disponible?

ACTUALIZACIÓN : El módulo de expresiones regulares de Python funciona bastante bien, aunque es un poco más lento que el módulo de re incorporado para casos de subcadenas difusas, lo que es un resultado obvio debido a las operaciones adicionales. La salida deseada es buena y el control sobre la magnitud de la borrosidad se puede definir fácilmente.

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

La nueva biblioteca de expresiones regulares que se debe reemplazar pronto incluye la coincidencia difusa.

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

La syntax de coincidencia difusa parece bastante expresiva, pero esto le daría una coincidencia con una o menos inserciones / adiciones / eliminaciones.

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

¿Qué hay de usar difflib.SequenceMatcher.get_matching_blocks ?

 >>> import difflib >>> large_string = "thelargemnhatanproject" >>> 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 

ACTUALIZAR

 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 = "thelargemnhatanproject is a great project in themanhattincity" query_string = "manhattan" print list(matches(large_string, query_string, 0.8)) 

Sobre el código impreso: ['manhatan', 'manhattn']

Utilizo fuzzywuzzy para hacer coincidencias difusas basadas en el umbral y fuzzysearch para extraer las palabras de la coincidencia.

process.extractBests toma una consulta, una lista de palabras y una puntuación de corte y devuelve una lista de tuplas de coincidencia y puntuación por encima de la puntuación de corte.

find_near_matches toma el resultado de process.extractBests y devuelve los índices de inicio y fin de las palabras. Uso los índices para construir las palabras y uso la palabra creada para encontrar el índice en la cadena grande. max_l_dist de find_near_matches es ‘Levenshtein distance’ que debe ajustarse para adaptarse a las necesidades.

 from fuzzysearch import find_near_matches from fuzzywuzzy import process large_string = "thelargemnhatanproject 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) 

Prueba;

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

Salida;
consulta: manhattan
string: thelargemnhatanproject es un gran proyecto en temática de identidad
partido: manhatan
índice: 8
partido: manhattin
índice: 49

consulta: citi
string: thelargemnhatanproject es un gran proyecto en temática de identidad
partido: ciudad
índice: 58

consulta: saludar
string: thelargemnhatanproject es un gran proyecto en temática de identidad
partido: genial
índice: 29

Recientemente he escrito una biblioteca de alineación para Python: https://github.com/eseraygun/python-alignment

Usándolo, puede realizar alineaciones globales y locales con estrategias de puntuación arbitrarias en cualquier par de secuencias. En realidad, en su caso, necesita alineaciones semi-locales ya que no le interesan las subcadenas de query_string . He simulado un algoritmo semi-local usando alineación local y algunas heurísticas en el siguiente código, pero es fácil extender la biblioteca para una implementación adecuada.

Aquí está el código de ejemplo en el archivo README modificado para su caso.

 from alignment.sequence import Sequence, GAP_ELEMENT from alignment.vocabulary import Vocabulary from alignment.sequencealigner import SimpleScoring, LocalSequenceAligner large_string = "thelargemnhatanproject 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 

La salida para minScore=5 es la siguiente.

 manha - tan manhattan Alignment score: 7 Percent identity: 88.8888888889 manhatt - i manhattan Alignment score: 5 Percent identity: 77.7777777778 manhattin manhattan Alignment score: 7 Percent identity: 88.8888888889 

Si elimina el argumento de minScore , solo obtendrá las mejores coincidencias de puntuación.

 manha - tan manhattan Alignment score: 7 Percent identity: 88.8888888889 manhattin manhattan Alignment score: 7 Percent identity: 88.8888888889 

Tenga en cuenta que todos los algoritmos de la biblioteca tienen una complejidad de tiempo O(n * m) , n y m son las longitudes de las secuencias.

Los enfoques anteriores son buenos, pero necesitaba encontrar una pequeña aguja en un montón de heno, y terminé por acercarme así:

 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 

Rendimientos:

 0.72972972973 this string is the one we wanted to find