Czasem przydatną informacją jest wiedza o tym, jak bardzo dwa stringi różnią się między sobą.
Edit distance...
Chodzi mi tu oczywiście o łańcuchy znaków, a nie seksowne majteczki (przy czym seksowność uzależniona jest w znacznym stopniu od osoby noszącej). Po co coś takiego może być przydatne? Jakiś czas temu pisałem o fuzzowaniu nazw domen. Takie "porównywanie stopnia podobieństwa" może być przydatne choćby po to, by określić jak bardzo "trafiona" w trakcie fuzzowania domena jest podobna do oryginalnie podanej. Jeśli chodzi o algorytm, to akurat nie trzeba daleko szukać, bo pod hasłem edit distance znajduje się kilka algorytmów do wyboru, choć myślę, że (na razie) wystarczą trzy pierwsze:
Prawdopodobnie wykorzystam ostatni z algorytmów, z uwagi na fakt, że uwzględnia on literówki: Unlike Levenshtein distance, it counts transposition as a single edit operation, rather than two. A po co to liczyć? Na przykład po to, by listę wyników posortować od tych najbardziej do najmniej "podobnych".
Drugim przydatnym zastosowaniem może być monitorowanie podejrzanych stron i wychwytywanie w nich zmian. Tutaj jednak trzeba uważać, by nie paść ofiarą złożoności obliczeniowej...
