Jak znaleźć podłańcuch przy użyciu dopasowania częściowego [closed] - python, string

bigString = "AGAHKGHKHASNHADKRGHFKXXX_I_AM_THERE_XXXXXMHHGRFSAHGSKHASGKHGKHSKGHAK"
smallString = "I_AM_HERE"

Jaki efektywny algorytm powinienem użyć, aby znaleźć podciąg "bigString", który pasuje do "smallString"

output = "I_AM_THERE"

Dane wyjściowe mogą mieć kilka wstawień i usunięć w porównaniu z małymi ciągami.

Edytować: Znaleziono dobry przykład, bardzo blisko mojego problemu tutaj: Jak dodać błąd zmiennej, aby wyodrębnić wyszukiwanie rozmyte. Pyton

Odpowiedzi:

4 dla odpowiedzi № 1

Możesz użyć prawie gotowe na każdy-regex pakiet z dopasowaniem rozmytym:

>>> import regex
>>> bigString = "AGAHKGHKHASNHADKRGHFKXXX_I_AM_THERE_XXXXXMHHGRFSAHGSKHASGKHGKHSKGHAK"
>>> regex.search("(?:I_AM_HERE){e<=1}",bigString).group(0)
"I_AM_THERE"

Lub:

>>> bigString = "AGAH_I_AM_HERE_RGHFKXXX_I_AM_THERE_XXX_I_AM_NOWHERE_EREXXMHHGRFS"
>>> print(regex.findall("I_AM_(?:HERE){e<=3}",bigString))
["I_AM_HERE", "I_AM_THERE", "I_AM_NOWHERE"]

Nowy moduł regex będzie (ufnie) być częścią Python3.4

Jeśli masz pip, po prostu wpisz pip install regex lub pip3 install regex dopóki Python 3.4 nie będzie dostępny (z częścią regex ...)

---

Odpowiedz, aby skomentować Is there a way to know the best out of the three in your second example? How to use BESTMATCH flag here?

Użyj flagi najlepszego dopasowania (?b) aby uzyskać najlepszy najlepszy wynik:

print(regex.search(r"(?b)I_AM_(?:ERE){e<=3}", bigString).group(0))
# I_AM_THE

Lub połącz z difflib lub zmierz odległość z listą wszystkich dopuszczalnych dopasowań do pierwszego literału:

import regex

def levenshtein(s1,s2):
if len(s1) > len(s2):
s1,s2 = s2,s1
distances = range(len(s1) + 1)
for index2,char2 in enumerate(s2):
newDistances = [index2+1]
for index1,char1 in enumerate(s1):
if char1 == char2:
newDistances.append(distances[index1])
else:
newDistances.append(1 + min((distances[index1],
distances[index1+1],
newDistances[-1])))
distances = newDistances
return distances[-1]

bigString = "AGAH_I_AM_NOWHERE_HERE_RGHFKXXX_I_AM_THERE_XXX_I_AM_HERE_EREXXMHHGRFS"
cl=[(levenshtein(s,"I_AM_HERE"),s) for s in regex.findall("I_AM_(?:HERE){e<=3}",bigString)]

print(cl)
print([t[1] for t in sorted(cl, key=lambda t: t[0])])

print(regex.search(r"(?e)I_AM_(?:ERE){e<=3}", bigString).group(0))

Wydruki:

[(3, "I_AM_NOWHERE"), (1, "I_AM_THERE"), (0, "I_AM_HERE")]
["I_AM_HERE", "I_AM_THERE", "I_AM_NOWHERE"]

---

0 dla odpowiedzi nr 2

Oto trochę hacky sposób to zrobić difflib:

from difflib import *

window = len(smallString) + 1  # allow for longer matches
chunks = [bigString[i:i+window] for i in range(len(bigString)-window)]
get_close_matches(smallString,chunks,1)

Wydajność:

["_I_AM_THERE"]

---

0 dla odpowiedzi № 3

Być może w tym przypadku może być zastosowany problem z programowaniem dynamicznym Longest Common Substring. W zależności od twoich potrzeb i kryteriów dopasowania możesz prawdopodobnie użyć Najdłuższego Podsetułu Wspólnego

---