Znajdowanie podobnych stringów

Uwaga! Informacje na tej stronie mają ponad 5 lat. Nadal je udostępniam, ale prawdopodobnie nie odzwierciedlają one mojej aktualnej wiedzy ani przekonań.

# Znajdowanie podobnych stringów

08:34
Sun
22
Feb 2009

Kiedy wpisujemy w Google jakieś słowo, które jest ewidentną pomyłką, wyszukiwarka sugeruje jego poprawną wersję (np. Programmowanie). Jak zrobić coś takiego i ogólnie jak wyszukiwać w bazie danych podobne łańcuchy, by uodpornić pisaną stronę WWW na drobne pomyłki we wprowadzonym zapytaniu albo wyświetlać sugestię poprawnej pisowni? Niedawno kolega, którego poznałem przy piwie, zdradził mi kilka ciekawych pomysłów.

Po pierwsze, łańcuch trzeba przeliczyć na Hash - inny łańcuch, który dopiero jest wyszukiwany w bazie danych. Algorytm na ten Hash może wyglądać różnie, np.:

Taki Hash wyszukiwany jest w bazie danych, przy czym z bazy pobierany jest nie jeden pasujący rekord, ale też kilka sąsiednich rekordów (poprzednich i następnych wg kolejności alfabetycznej).

Następnie każdy z wyników zwróconych z bazy danych jest porównywany z hashem słowa wejściowego algorytmem Levenshtein Distance (który zwraca podobieństwo dwóch łańcuchów, tak jakby odległość między nimi). Jego wynik mnożony jest przez częstość występowania danego słowa wyszukanego w bazie (czyli np. po prostu ilość wystąpień w skatalogowanym tekście). Np. Punkty = Częstość_słowa / Levenshtein_distance.

Na koniec wybierane jest to słowo lub słowa spośród wyszukanych z bazy danych, które mają największy ten współczynnik Punkty.

Comments | #webdev #algorithms Share

Comments

STAT NO AD
[Stat] [STAT NO AD] [Download] [Dropbox] [pub] [Mirror]
Copyright © 2004-2017