👋 Nový obsah na borekb.cz

Info Tento blog je v "read-only módu" a nový obsah již nebude přibývat. O vývoji píšu na DevBlog.

Funkce pro podobnost stringů - řešení

Před pár dny jsem zde dával k zamyšlení, jak byste implementovali funkci pro podobnost dvou stringů (stejné stringy mají vrátit nulu, stringy s jedním rozdílem jedničku a tak dále).

Jak pod původním článkem správně jeden komentující poznamenal, v podstatě bylo úkolem najít funkci, která pro dva stringy vrátí tzv. Levenshteinovu vzdálenost. Výpočet je naznačen třeba na Wikipedii a charakteristické je pro něj především to, že je pro běžného smrtelníka mého ražení nevymyslitelný :) Iteruje se přes jednotlivé znaky obou stringů, postupně se plní jakási matice a po skončení tohoto procesu je hledaný výsledek v její poslední buňce. Snadné, že?

Algoritmus, který napadl mě (a který určitě není jediný), je jednoduchý:

Postupně procházej znaky prvního řetězce a když narazíš na první rozdíl, máš výsledek! Kolik? Výsledek se rovná 1 (to je ten rozdíl, na který jsme právě narazili) plus počet rozdílů ve zbytku.

Například ABCDEF ↔ ABXDEFG má vrátit 2 a pomocí našeho algoritmu k tomuto číslu dojdeme následovně: na třetí pozici narazíme na rozdíl, takže vracíme 1+počet rozdílů ve zbytku. Jak vidno, počet rozdílů ve zbytku je 1 (ono přidané géčko), takže výsledek bude 1+1=2.

Problémem je, co je vlastně ten „zbytek“. Ono totiž mohlo dojít ke třem věcem:

  1. k záměně znaku
  2. k přidání znaku
  3. k odebrání znaku

Například pokud došlo k záměně znaku, měli bychom rekurzivně zavolané funkci podšoupnout substringy začínající na pozici i+1. V našem příkladu bychom zkoumali rozdíly mezi stringy „DEF“ a „DEFG“ a shodou okolností jsme se trefili, ale ono to „X“ mohlo znamenat přidání x-ka do druhého stringu nebo odebrání céčka ze stringu prvního – to zatím nevíme. V každém ze třech případů musíme postupovat trošku jinak – rekurzivně volané funkci musíme podstrčit substring začínající na trochu jiné pozici.

Problém tedy je, že při nálezu rozdílu na určité pozici nemůžeme s jistotou říct, jestli jsme našli záměnu, přidání nebo odebrání znaku. S tím si ale poradíme – prozkoumáme všechny 3 možnosti a zajímat nás bude jen výsledek nejpříznivější, tedy nejnižší. Tím je algoritmus kompletní a v implementaci je potřeba už jen ošetřit mezní případy, jako třeba že jsme na konci stringu apod.

Kód je zhruba tento (použil jsem ActionScript, který by měl být čitelný pro kohokoliv, kdo někdy viděl JavaScript, Javu nebo C#):

public static function compareStrings(string1 : String, string2 : String) : int {

  if (string1 == string2) {
    return 0;
  }

  if (string1.length == 0) {
    return string2.length;
  }

  if (string2.length == 0) {
    return string1.length;
  }

  var differencesFound : int = 0;

  for (var i : int = 0; i < string1.length && differencesFound == 0; i++) {
    if (string1.charAt(i) != string2.charAt(i)) {
      differencesFound += 1;
      var differencesIfAddition : int = compareStrings(string1.substr(i), string2.substr(i + 1));
      var differencesIfChange : int  = compareStrings(string1.substr(i + 1), string2.substr(i + 1));
      var differencesIfRemoval : int = compareStrings(string1.substr(i + 1), string2.substr(i));
      differencesFound += Math.min(differencesIfAddition, differencesIfChange, differencesIfRemoval);
    }
  }

  if (differencesFound == 0 && string2.length > string1.length) {
    return string2.length - string1.length;
  }

  return differencesFound;

}

Jednoduché, funkční a snadno srozumitelné, algoritmus je navíc slušně efektivní pro dva podobné stringy (zkoušel jsem porovnávat stringy o délce 10 000 znaků a bez problémů). Bohužel – pro 2 rozdílné vstupy je VELMI pomalý, protože se rekurze volá úplně pořád a „zbytečně“ se prozkoumává mnoho možností. Ve výše uvedeném kódu by se nějaké optimalizace udělat dali, ale složitosti O(n*m) z Levenshtainova algoritmu bychom se stejně ani nepřiblížili.

Čili – jako mozkové cvičení to nebylo špatné, ale některé věci je lepší nechat na matematicích :)

Zařazeno do kategorií |
Martin (Út, 2008-08-26 21:35):

Problém není v algoritmu od chytrého pána. Jak už to bývá, ten algoritmus je křišťálově jasný. Problém je v bídném vysvětlení ve wikipedii. Podstatu algoritmu jde pěkně pochopit z http://odur­.let.rug.nl/~kle­iweg/lev/ V nultém řádku matice je jeden string, v nultém sloupci druhý. Jednotlivé prvky matice ukazují počet kroků, jak z jednoho podřetězce (končícího aktuálním sloupcem) udělat ten druhý (končící aktuálním řádkem). V prvním řádku a sloupci je tento počet kroků proti prazdnému stringu. Tím se triviálně vyplní první řádek i sloupec. V řádku jsou kroky na přidání znaku, v sloupci kroky na smazání. A pak už to jde jednoduše. Když chci vyplnit políčko, hledám minimum(nade mnou + cena delete,vlevo diagonálně + cena replace,vlevo + cena insert) . Přeloženo do lidské řeči: hledám nejjednodušší operaci, kterou z horního podstringu udělám levý podstring. Bohužel to líp vysvětlit neumím. Místo vymýšlení vymyšleného doporučuju vyměnit wikipedii za kvalitního učitele. Tohle by to mohlo spravit: http://www.fel­d.cvut.cz/…/p10217­.html a možná by stačilo jen koupit a nastudovat skripta. Je tam toho ještě spousta zajímavého :)

Borek (St, 2008-08-27 09:00):

Do článků jsem to nepsal, ale o Levenshteinově algoritmu jsem věděl už předtím, než jsem se do řešení problému pustil vlastní hlavou. Jakožto aplikačnímu programátorovi se mi nestává často, že bych musel řešit algoritmicky složité problémy, ale tohle mi přišlo dostatečně zajímavé, tak jsem se do toho pustil.

Mimochodem, úloha to není vůbec snadná, dával jsem ji několika známým a nikdo s úplně správným řešením nepřišel.

Martin "stibi" Stiborský (St, 2008-08-27 16:47):

Za tento blogpost děkuji, takových více!

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