K zamyšlení - funkce pro podobnost dvou stringů

22 Srp 2008

Občas je potřeba zjistit, nakolik si jsou 2 stringy podobné – Google tak například odhaluje překlepy a jiné služby zase například mohou zajistit, aby heslo nebylo příliš podobné uživatelskému jménu; možností využití je zkrátka hodně. Zkoušeli jste se někdy zamyslet, jak takovou funkci implementovat?

(Na úvod: několik algoritmů řešících tento problém samozřejmě existuje, ale v tomto případě jsem radši místo Googlu potrápil vlastní hlavu, protože jako aplikačnímu programátorovi se mi nestává často, že bych se setkal s funkcí, která je implementačně zajímavá a vysoce užitečná zároveň :) Pokud tedy rádi přemýšlíte nad problémy jako já, pokračujte.)

Na začátek nějaké příklady:

„abc“ ↔ „abc“ má vrátit nulu (žádné rozdíly)
„abc“ ↔ „abX“ vrátí 1 (1 rozdíl)
„abc“ ↔ „XXabc“ vrátí 2
„Johny Dep“ ↔ „Johnny Depp“ vrátí 2

Jinak (hodně matematicky a nepěkně) řečeno, máte najít počet operací přidání, odebrání nebo změny znaku, pomocí kterých lze string 1 převést na string 2.

Po určitém průzkumu možností se mi zdá, že máte 3 možnosti:

Najdete relativně jednoduchý algoritmus, o kterém si však budete jen myslet, že funguje :)
Najdete programátorsky elegantní algoritmus, který bude fungovat, ale budete mít pocit, že výpočetní složitost by mohla být lepší
Najdete algoritmus, který bude správný a současně optimální z hlediska výpočetní obtížnosti. Co jsem tak viděl, tak dosažení tohoto třetího bodu vyžaduje kousek matematické geniality a pravděpodobně se vylučuje s programátorskou elegancí, jak už to tak bývá

Dvojka pro mě byla tak akorát (a pomýšlení na trojku bych v mém případě považoval skoro za rouhání :), ale i tak jsem si cestou užil dost zábavy. Přeji příjemné řešení!

blog uživatele Borek

Zařazeno do kategorií Borkův blogovníček | Počítače

Martin (Pá, 2008-08-22 14:59):

Tak tohle jsme měli ve škole v jednom nejmenovaném předmětu. Není třeba vymýšlet něco, co už dávno někdo chytřejší vymyslel. http://en.wikipedia.org/wiki/Levenshtein_distance

V PHP je na to nečekaně funkce levenshtein :)

Kdo to nezná, dozví se to po volbě bodu nula: Ask Google.

BB: Martine, ve všem máš pravdu a v PHP jsou na to minimálně 2 dobře použitelné funkce, ale o tom zápisek není. Tvůj komentář proto činím trochu míň čitelným :)

vlko (Pá, 2008-08-22 15:26):

Moj prispevok urcite su aj kvalitnejsie algoritmy, ale tento aj mna zabavil, aj ked som mal radsej robit:)

1. vytvorim pole int velkosti prveho stringu {A[pozicia]}
2. iterujem druhy string po znaku
2.1 zober znak, a zisti index v prvom stringu {I}
2.2 ak I > 0 iteruj po A {U} za podmienky U < I
2.3.1 ak A[U] == I potom A[U] = I + 1 *(zvysenie ocakavania)*
2.4 nastavenie ocakav A[I] == I + 1
3. nastav maximum na 0
3. najdem maximum v A {C} *(pri kazdom prvku treba este od hodnoty v A odratat jeho poziciu vid zdrojovy kod)*
4. vysledok dlzka B - C


        class Program
        {
                static void Main(string[] args)
                {
                        ComputeSimilarity("abc", "abc");
                        ComputeSimilarity("abc", "abx");
                        ComputeSimilarity("abc", "xxabc");
                        ComputeSimilarity("abc", "xxxbc");
                        ComputeSimilarity("abc", "xcx");
                        ComputeSimilarity("Johny Dep", "Johnny Depp");
                        Console.Read();
                }


                private static int ComputeSimilarity(string s1, string s2)
                {
                        int result = s2.Length;
                        int[] expectations = new int[s1.Length];
                        foreach (char ch in s2)
                        {
                                int pos = s1.IndexOf(ch);
                                if (pos >= 0)
                                {
                                        for (int i = 0; i < pos; ++i)
                                        {
                                                if (expectations[i] == pos)
                                                {
                                                        expectations[i] = pos + 1;
                                                }
                                        }
                                        expectations[pos] = pos + 1;
                                }
                        }
                        int maximum = 0;
                        for (int i=0; i<expectations.Length; ++i)
                        {
                                int value = expectations[i] - i;
                                if (value > maximum)
                                        maximum = value;
                        }
                        result = s2.Length - maximum;
                        Console.WriteLine("{0} vs {1} s rozdielom {2}", s1, s2, result);
                        return result;
                }
        }

Borek (Pá, 2008-08-22 17:26):

Pokud se nepletu, tak příklad „Nigel Nessy“ ↔ „Niguel Nesy“ naznačuje, že jsi zatím na prvním stupínku :)

vlko (Pá, 2008-08-22 21:46):

jj, teraz som si uvedomil, ze tam nie je podpora ababc like stringov, mozno este porozmyslam:)

Komentáře jsou uzavřeny (blog je v read-only módu). Pokud mě chcete kontaktovat, můžete mailem.