Czy można wyliczyć odległość edycyjną między wyrażeniem regularnym a łańcuchem?

Question

Jeśli tak, proszę wyjaśnić, w jaki sposób.

Re: co to jest odległość - "Odległość między dwoma ciągami określa się jako minimalną liczbę zmian wymaganych do przekształcenia jednej w drugą."

Na przykład, xyz do XYZ wymaga 3 edycji, więc ciąg xYZ jest bliżej XYZ i xyz.

Jeśli wzór to [0-9] {3} lub na przykład 123, to a23 byłoby bliższe wzorowi niż ab3.

Jak znaleźć najkrótszą odległość między wyrażeniem regularnym a nie pasującym łańcuchem?

Powyższy algorytm to odległość Damerau–Levenshtein.

Answer 1

Możesz używać Maszyn skończonych stanów, aby robić to efektywnie (czyli liniowo w czasie) . Jeśli używasz przetwornika, możesz nawet napisać specyfikację transformacji dość zwięźle i zrobić o wiele bardziej zniuansowane transformacje, niż po prostu wstawia lub usuwa - patrz punkt wikipedia dla Finite State Transducer jako punkt wyjścia, i oprogramowanie takie jak zestaw narzędzi FSA lub FSA6 (który ma nie do końca stabilny web-demo). Istnieje wiele bibliotek do manipulowania FSA; Nie chcę sugerować, że poprzednie dwie są twoimi jedynymi lub najlepszymi opcjami, tylko dwie, o których słyszałem.

Jeśli jednak potrzebujesz jedynie sprawnego, przybliżonego wyszukiwania, istnieje opcja mniej elastyczna, ale już zaimplementowana dla Ciebie: TRE, która ma wartość approximate matching function, która zwraca koszt dopasowania - tj. Odległość do mecz z twojej perspektywy.

Answer 2

Jeśli masz na myśli ciąg o najmniejszej odległości między najbliższym dopasowanym sznurkiem a próbką, to jestem prawie pewien, że można to zrobić, ale musisz sam przekonwertować Regex na DFA, a potem spróbować aby się dopasować, a gdy coś zawiedzie, niedeterministycznie kontynuować, jak gdyby minął i śledzić różnice liczby. możesz użyć wyszukiwania A * lub czegoś podobnego do tego, byłoby to jednak dość nieefektywne (najgorszy przypadek O (2^n)).