Levenšteino atstumas

Apibrėžimas

Matematiškai, Levenšteino atstumas tarp a ir b aibių yra skaičiuojamas , kur  
 
kur kai  indikacijos funkcija yra padidinama 1, o kitu atveju, kai  indikacijos funkcija būna lygi 0 ir  yra atstumas tarp pirmojo   elemento aibės  ir pirmojo  elemento iš  aibės

Pritaikymai

Pagrindinis apytikslis tekstinių aibių lyginimas yra surasti sutapimus trumpių aibių ilguose tekstuose, kur yra tikimasi mažų neatitikimų. Originali (tikslioji) aibė gali būti laikoma žodynu, kuris yra jau suvestas ir yra lyginamas su neoriginaliu tekstu. Šitai turi ypatingai platų pritaikymą, puikiai visiems žinomas pavyzdys yra teksto tikrinimo ir taisymo sistemos sistemos, vizualios ženklų atpažinimo sistemos ir programinė įranga kuri padeda tiesiogiai verčiamai kalbai būti tiksliau atpažinama.
Levenšteino atstumas gali būti taip pat naudojamas lyginti ir ilgoms aibėms, bet resursų kaina reikalinga tą pasiekti yra apytiksliai proporcinga dviejų aibių ilgių sumai. Ši neigiama savybė padaro šį metodą nepraktišku. Būtent lyginti ilgoms aibėms yra labiau renkamasi Fuzzy algoritmas, kuris šiuo atveju yra greitesnis ir tikslesnis.

Rekursija

Tai yra pats paprasčiausia, bet pats ne efektyviausias būdas skaičiuoti. Pavyzdyje yra pateiktas C kalbos funkcijos pavyzdys, kuri pasima dvi tekstų aibes, jų ilgius ir gražina atstumą tarp jų
// len_s and len_t are the number of characters in string s and t respectivelyint LevenshteinDistance(char *s, int len_s, char *t, int len_t){ 
  int cost;

  /* base case: empty strings */
  if (len_s == 0) return len_t;
  if (len_t == 0) return len_s;

  /* test if last characters of the strings match */
  if (s[len_s-1] == t[len_t-1])
      cost = 0;
  else
      cost = 1;

  /* return minimum of delete char from s, delete char from t, and delete char from both */
  return minimum(LevenshteinDistance(s, len_s - 1, t, len_t    ) + 1,
                 LevenshteinDistance(s, len_s    , t, len_t - 1) + 1,
                 LevenshteinDistance(s, len_s - 1, t, len_t - 1) + cost);}

Šis būdas yra neefektyvus, nes jis daugybę kartų perskaičiuoja atstumą su tomis pačiomis tekstų aibes. Efektyvesnis būdas būtų niekada nekartoti tų pačių skaičiavimų. Pavyzdžiui visos galimos pakeitimo reikšmės būtų saugomos masyve d[][], kur d[i][j] yra atstumas tarp pirmų i ženklų žodyje s ir pirmų j ženklų žodyje t. Lentelę yra ypač paprasta suformuoti pradedant nuo pirmųjų ženklų. Kai visa lentelė yra suformuota, tai mūsų norimas atstumas yra d[len_s][len_t].

Dviejų matricos eilučių iteracija

Pasirodo norint sukonstruoti matricą reikia tik dviejų eilių nenorint rekonstruoti redaguotas tekstines aibes. Levenšteino atstumą galimą paskaičiuoti iteruojant pavyzdyje pateiktą funkciją:
int LevenshteinDistance(string s, string t){
    // degenerate cases
    if (s == t) return 0;
    if (s.Length == 0) return t.Length;
    if (t.Length == 0) return s.Length;

    // create two work vectors of integer distances
    int[] v0 = new int[t.Length + 1];
    int[] v1 = new int[t.Length + 1];

    // initialize v0 (the previous row of distances)
    // this row is A[0][i]: edit distance for an empty s
    // the distance is just the number of characters to delete from t
    for (int i = 0; i < v0.Length; i++)
        v0[i] = i;

    for (int i = 0; i < s.Length; i++)
    {
        // calculate v1 (current row distances) from the previous row v0

        // first element of v1 is A[i+1][0]
        //   edit distance is delete (i+1) chars from s to match empty t
        v1[0] = i + 1;

        // use formula to fill in the rest of the row
        for (int j = 0; j < t.Length; j++)
        {
            var cost = (s[i] == t[j]) ? 0 : 1;
            v1[j + 1] = Minimum(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost);
        }

        // copy v1 (current row) to v0 (previous row) for next iteration
        for (int j = 0; j < v0.Length; j++)
            v0[j] = v1[j];
    }

    return v1[t.Length];}
Hirschberg algoritmas sujungia Levenšteino atstumą su skaldyk ir valdyk teorija. Jis gali sugeneruoti ne tik atstumą, bet ir optimalią seką tokiame pačiame asimptotiniame laike ir erdvėje.

Aproksimacija

Atstumas tarp dviejų tekstinių aibių yra , kurį gali nustatyti , kur  yra laisvasis parametras, kurį galima redaguoti laike

Generavimo sunkumas

Yra įrodyta, jog Levenšteino atstumas tarp dviejų tekstinių aibių negali būti nustatytas laike, kai  nebent eksponentinė laiko hipotezė yra neįrodyta.