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 :)