Po pierwsze, odległość Levenshteina jest zdefiniowana jako minimalna liczba edycji wymaganych do przekształcenia ciągu znaków A w ciąg B, gdzie edycja polega na wstawieniu lub usunięciu pojedynczego znaku lub zastąpieniu znaku innym znakiem. Jest to więc w dużym stopniu „różnica między dwoma strunami”, przy pewnej definicji odległości. =)
Wygląda na to, że szukasz funkcji odległości F(A, B), która podaje odległość między strunami A i B oraz próg N, gdzie struny o odległości mniejszej niż N są kandydatami do literówek. Oprócz odległości Levenshteina możesz również rozważyć Needleman–Wunsch . To w zasadzie to samo, ale umożliwia podanie funkcji określającej, jak blisko jest dany znak do innego znaku. Możesz użyć tego algorytmu z zestawem wag, które odzwierciedlają pozycje klawiszy na klawiaturze QWERTY, aby wykonać całkiem niezłą robotę wyszukiwania literówek. Miałoby to jednak problemy z międzynarodowymi klawiaturami.
Jeśli masz k ciągów i chcesz znaleźć potencjalne literówki, liczba porównań, które musisz wykonać, wynosi O(k^2). Ponadto każde porównanie ma wartość O(len(A)*len(B)). Więc jeśli masz milion strun, będziesz miał kłopoty, jeśli będziesz robił rzeczy naiwnie. Oto kilka sugestii, jak przyspieszyć działanie:
- Przepraszam, jeśli to oczywiste, ale odległość Levenshteina jest symetryczna, więc upewnij się, że nie obliczasz F(A, B) i F(B, A).
- abs(len(A) - len(B)) to dolna granica odległości między ciągami A i B. Możesz więc pominąć sprawdzanie ciągów, których długości są zbyt różne.
Jednym z problemów, na który możesz się natknąć, jest to, że „1st St.” ma dość dużą odległość od „First Street”, chociaż prawdopodobnie chcesz uznać je za identyczne. Najłatwiejszym sposobem radzenia sobie z tym jest prawdopodobnie przekształcenie ciągów do postaci kanonicznej przed wykonaniem porównań. Możesz więc zapisywać wszystkie ciągi małymi literami, użyć słownika, który odwzorowuje „1st” na „first” itd. Ten słownik może stać się dość duży, ale nie znam lepszego sposobu radzenia sobie z tymi problemami.
Ponieważ oznaczyłeś to pytanie php, zakładam, że chcesz do tego użyć php. PHP ma wbudowaną funkcję levenshtein(), ale oba ciągi muszą mieć 255 znaków lub mniej. Jeśli to nie wystarczy, będziesz musiał zrobić własne. Alternatywnie możesz badać używając difflib Pythona.
