Levenstein distance substring

Question

Existe-t-il un bon moyen d'utiliser la distance levenstein pour faire correspondre une chaîne particulière à n'importe quelle région d'une seconde chaîne plus longue?

Exemple:

str1='aaaaa' 
str2='bbbbbbaabaabbbb' 

if str1 in str2 with a distance < 2: 
    return True 

Ainsi, dans la partie exemple ci-dessus de la chaîne 2 est aabaa et distance(str1,str2) < 2 de sorte que la déclaration devrait revenir True. La seule façon que je peux penser à faire ceci est de prendre 5 caractères de str2 à la fois, comparez cela avec str1, puis répétez cette opération en str2. Malheureusement, cela semble vraiment inefficace et j'ai besoin de traiter une grande quantité de données de cette façon.

Answer 1

L'astuce consiste à générer toutes les sous-chaînes de longueur appropriée de b, puis de comparer chacune d'entre elles.

def lev_dist(a,b): 
    length_cost = abs(len(a) - len(b)) 
    diff_cost = sum(1 for (aa, bb) in zip(a,b) if aa != bb) 
    return diff_cost + length_cost 

def all_substr_of_length(n, s): 
    if n > len(s): 
     return [s] 
    else: 
     return [s[i:i+n] for i in range(0, len(s)-n+1)] 

def lev_substr(a, b): 
    """Gives minimum lev distance of all substrings of b and 
    the single string a. 
    """ 

    return min(lev_dist(a, bb) for bb in all_substr_of_length(len(a), b)) 

if lev_substr(str1, str2) < 2: 
    # it works! 

Answer 2

L'astuce consiste généralement à jouer avec les coûts d'insertion (pour les plus courts) ou de suppression (pour les plus longs). Vous pouvez également envisager d'utiliser Damerau-Levenshtein à la place. https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance

Answer 3

Vous pouvez jeter un oeil à la regex module qui prend en charge la correspondance floue:

>>> import regex 
>>> regex.search("(aaaaa){s<2}", 'bbbbbbaabaabbbb') 
<regex.Match object; span=(6, 11), match='aabaa', fuzzy_counts=(1, 0, 0)> 

Puisque vous êtes à la recherche sont des chaînes de longueur égale, vous pouvez également faire aa Hamming distance qui est probablement beaucoup plus rapide qu'un la distance Levenstein sur les mêmes deux cordes:

str1='aaaaa' 
str2='bbbbbbaabaabbbb' 
for s in [str2[i:i+len(str1)] for i in range(0,len(str2)-len(str1)+1)]: 
    if sum(a!=b for a,b in zip(str1,s))<2: 
     print s # prints 'aabaa'