Levenšteino atstumas

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
   Šį puslapį ar jo dalį reikia sutvarkyti pagal Vikipedijos standartus.
Jei galite, sutvarkykite.

Informacijos teorijoje ir kompiuterių moksle, Levenšteino atstumas yra atstumo matavimas tarp dviejų tekstinių simbolių aibių. Matavimas vyksta vienos iš aibių elementus tikrinant su kitos aibės elementais ir neatitikimus pakeičiant teisingais elementais. Skaičiavimas buvo sugalvotas 1965 metais Vladimiro Levenšteino.

Levenšteino atstumas taip pat gali būti siejamas su redagavimo atstumų šeimos grupe, kuri yra siejama tiesiogiai su aibių lyginimo ir pakeitimo metodikomis.

Apibrėžimas[redaguoti | redaguoti vikitekstą]

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

Pavyzdys[redaguoti | redaguoti vikitekstą]

Paskaičiuokime atstumą tarp žodžių "kaina" ir "katė". Šiuo metu atstumas yra lygus 3, kadangi norint gauti aibes identiškas reikia atlikti tris pakeitimo veiksmus ir nėra kito būdo tą padaryti su mažesniu kiekiu veiksmų:

  1. kaina kana (i raidės pašalinimas)
  2. kana kata (n raidės pakeitimas į t raidę)
  3. kata katė (a raidės pakeitimas į ė raidę)

Apatinė ir viršutinė riba[redaguoti | redaguoti vikitekstą]

Levenšteino atstumas turi kelias paprastas taisykles, kurios leidžia nustatyti minimalų arba didžiausią įmanomą atstumą.

  • Atstumas niekada nebus mažesnis nei žodžių ilgių skirtumas.
  • Atstumas niekada nebus didesnis nei ilgesnioji aibė.
  • Atstumas yra lygus 0 tik tuo atveju jei abi aibės yra identiškos.
  • Jeigu abi aibės yra vienodo ilgio tai ilgiausias įmanomas atstumas apskaičiuojamas pagal Hammingo atstumą.
  • Atstumas niekada nebus didesnis nei abiejų aibių atstumų suma nuo trečiosios aibės (Trikampio nelygybė).

Pritaikymai[redaguoti | redaguoti vikitekstą]

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.

Levenšteino atstumas programavime[redaguoti | redaguoti vikitekstą]

Rekursija[redaguoti | redaguoti vikitekstą]

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 respectively
int 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].

Pilnos matricos iteravimas[redaguoti | redaguoti vikitekstą]

Generuojant Levenšteino atstumą galime remtis tuo, jog jei mes rezervuosim matricą su atstumais tarp visų pirmosios aibės elementų ir visų antrosios aibės elementų, tada mes gauname reikšmes matricoje, kur atstumas tarp aibių bus paskutinė reikšmė sugeneruota.

Šis algoritmas yra dinaminio programavimo iš apačios į viršų algoritmo pavyzdys ir jis buvo aptartas 1974 straipsnyje The String-to-string correction problem parašytas Robert A. Wagner ir Michael J. Fischer.

Pavyzdyje pateiktas pseaudo kodo implementacija funkcijos kuri pasima dvi tekstų aibes, jų ilgius ir gražina atstumą tarp jų.

function LevenshteinDistance(char s[1..m], char t[1..n]):
  // for all i and j, d[i,j] will hold the Levenshtein distance between
  // the first i characters of s and the first j characters of t
  // note that d has (m+1)*(n+1) values
  declare int d[0..m, 0..n]
 
  set each element in d to zero
 
  // source prefixes can be transformed into empty string by
  // dropping all characters
  for i from 1 to m:
      d[i, 0] := i
 
  // target prefixes can be reached from empty source prefix
  // by inserting every character
  for j from 1 to n:
      d[0, j] := j
 
  for j from 1 to n:
      for i from 1 to m:
          if s[i] = t[j]:
            substitutionCost := 0
          else:
            substitutionCost := 1
          d[i, j] := minimum(d[i-1, j] + 1,                   // deletion
                             d[i, j-1] + 1,                   // insertion
                             d[i-1, j-1] + substitutionCost)  // substitution
 
  return d[m, n]

Pavyzdinis kodas mums gražina rezultatų matricą:

k a t ė
0 1 2 3 4
k 1 0 1 2 3
a 2 1 0 1 2
i 3 2 1 1 2
n 4 3 2 2 2
a 5 4 3 3 3

Turint čia matricą mes galime nesunkiai transformuoti ją visą algoritmo veikimo metu segmentą s[1..i] į t[1..j] naudojant mažiausią kiekį operacijų d[i,j], bet kuriuo atveju apatinis dešinys elementas bus mūsų atstumo atsakymas.

Dviejų matricos eilučių iteracija[redaguoti | redaguoti vikitekstą]

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[redaguoti | redaguoti vikitekstą]

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

Generavimo sunkumas[redaguoti | redaguoti vikitekstą]

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

Taip pat skaitykite[redaguoti | redaguoti vikitekstą]

Nuorodos[redaguoti | redaguoti vikitekstą]

  • Black, Paul E., ed. (14 August 2008), "Levenshtein distance", Dictionary of Algorithms and Data Structures [online], U.S. National Institute of Standards and Technology. Nuoroda tikrinta 2 lapkričio 2016