Pytanie w sprawie levenshtein-distance, regex – Odległość Levenshteina w wyrażeniu regularnym

9

czy istnieje możliwość włączenia odległości levenshteina w zapytaniu wyrażenia regularnego?

Z wyjątkiem tworzenia związku między permutacjami. Jak szukanie „cześć” z L.d. 1

<code>.ello | h.llo | he.lo | hel.o | hell.
</code>

jest to dużo głupie i nieużyteczne dla większej liczby L.d.

Twoja odpowiedź

2   odpowiedź
5

czy istnieje możliwość włączenia odległości levenshteina w zapytaniu wyrażenia regularnego?

Nie, nie w rozsądny sposób. Wdrożenie - lub użycie istniejącego - algorytmu odległości Levenshteina jest najlepszym rozwiązaniem.

ok, poczekam, jeśli ktoś inny odpowie, w przeciwnym razie zaznaczę poprawną odpowiedź :-) zdenda.online
7

ćwiczenie dla czytelnika, ale dla wyjścia tej hipotetycznej funkcji (biorąc pod uwagę wprowadzenie „słowa”) chcesz czegoś takiego:

<code>"^(?>word|wodr|wrod|owrd|word.|wor.d|wo.rd|w.ord|.word|wor.?|wo.?d|w.?rd|.?ord)$"
</code>

W języku angielskim najpierw próbujesz dopasować słowo, a następnie każdą możliwą pojedynczą transpozycję, a następnie każdą możliwą pojedynczą wstawkę, a następnie każdą możliwą pojedynczą pominięcie lub zastąpienie (można to zrobić jednocześnie).

Długość tego ciągu, podana słowo o długości n, jest liniowa (a zwłaszcza nie wykładnicza) z n.

Myślę, że to rozsądne.

Przekazujesz to swojemu generatorowi wyrażeń regularnych (tak jak w Rubim byłoby to Regexp.new (str)) i bam, masz matcher dla DOWOLNEGO słowa z odległością Damerau-Levenshteina 1 od danego słowa.

(Odległości Damerau-Levenshteina 2 są znacznie bardziej skomplikowane.)

Zwróć uwagę na użycie konstrukcji (?> Nieodwracalnej), która oznacza kolejność poszczególnych wyrażeń | 'd w tym wyjściu.

Nie mogłem wymyślić sposobu na „skompaktowanie” tego wyrażenia.

EDIT: Mam to do roboty, przynajmniej w Elixir!https://github.com/pmarreck/elixir-snippets/blob/master/damerau_levenshtein_distance_1.exs

Jednak niekoniecznie poleciłbym to (z wyjątkiem celów edukacyjnych), ponieważ doprowadzi cię to tylko do odległości 1; legalna biblioteka D-L pozwoli ci obliczyć odległości> 1. Chociaż ponieważ jest to wyrażenie regularne, prawdopodobnie po skonstruowaniu prawdopodobnie działa dość szybko (pamiętaj, że powinieneś gdzieś zapisać „skompilowane” wyrażenie regularne, ponieważ ten kod obecnie rekonstruuje go na KAŻDYM porównaniu!)

Powiązane pytania