Znajdowanie podobnych stringów

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

08:34
Sun
22
Feb 2009

Znajdowanie podobnych stringów

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 (0) | Tags: webdev algorithms | Author: Adam Sawicki | Share

Comments

(No comments)

Post comment

Nick *
Your name or nickname
E-mail
Your contact information (optional, will not be shown)
Text *
Content of your comment
Calculate *
(* - required field)
STAT NO AD [Stat] [Admin] [STAT NO AD] [pub] [Mirror] Copyright © 2004-2016 Adam Sawicki
Copyright © 2004-2016 Adam Sawicki