Peržiūrėti šaltinį Levenšteino atstumas

{{Tvarkyti|nuo=2016 m. gruodžio|netvarkingas_nuo=2016 m. lapkričio}}

[[Informacijos teorija|Informacijos teorijoje]] ir [[Kompiuterių mokslas|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 [[:en:Vladimir_Levenshtein|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 ==
Matematiškai, Levenšteino atstumas tarp '''a''' ir '''b''' aibių yra skaičiuojamas <math>lev_{a,b}(|a|,|b|)</math>, kur  

<math>\qquad\operatorname{lev}_{a,b}(i,j) = \begin{cases}
  \max(i,j) & \text{ if} \min(i,j)=0, \\
  \min \begin{cases}
          \operatorname{lev}_{a,b}(i-1,j) + 1 \\
          \operatorname{lev}_{a,b}(i,j-1) + 1 \\
          \operatorname{lev}_{a,b}(i-1,j-1) + 1_{(a_i \neq b_j)}
       \end{cases} & \text{ otherwise.}
\end{cases}</math> 

kur kai <math>a_i\neq b_j</math> indikacijos funkcija yra padidinama '''1''', o kitu atveju, kai <math>a_i=b_j</math> indikacijos funkcija būna lygi '''0''' ir <math>lev_{a,b}(i,j)</math> yra atstumas tarp pirmojo <math>i</math>  elemento aibės <math>a</math> ir pirmojo <math>j</math> elemento iš <math>b</math> aibės 

=== Pavyzdys ===
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ų:
# ka'''i'''na <math>\rightarrow</math> kana (i raidės pašalinimas)
# ka'''n'''a <math>\rightarrow</math> ka'''t'''a (n raidės pakeitimas į t raidę)
# kat'''a''' <math>\rightarrow</math> kat'''ė''' (a raidės pakeitimas į ė raidę)

=== Apatinė ir viršutinė riba ===
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 ==
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 ==

=== 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ų

<source lang="C">
// 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);
}
</source>


Š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 <code>d[][]</code>, kur <code>d[i][j]</code> yra atstumas tarp pirmų <code>i</code> ženklų žodyje <code>s</code> ir pirmų <code>j</code> ženklų žodyje <code>t</code>. Lentelę yra ypač paprasta suformuoti pradedant nuo pirmųjų ženklų. Kai visa lentelė yra suformuota, tai mūsų norimas atstumas yra <code>d[len_s][len_t]</code>.

=== Pilnos matricos iteravimas ===
Generuojant Levenšteino atstumą galime remtis tuo, jog jei mes rezervuosim [[Matrica (matematika)|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 [[Dinaminis programavimas|dinaminio programavimo]] iš apačios į viršų algoritmo pavyzdys ir jis buvo aptartas 1974 straipsnyje ''The [[:en:String-to-string_correction_problem|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ų.
<source lang="C">
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]
</source>
Pavyzdinis kodas mums gražina rezultatų matricą:
<center>
{{col-begin|width=auto}}
{{col-break}}
{|class="wikitable"
|-
| 
| 
!k
!a
!t
!ė
|-
| ||0 ||1 ||2 ||3 ||4
|-
!k
|1 ||{{H:title|'k' lygi 'k'|0}} ||1 ||2 ||3
|-
!a
|2 ||1 ||{{H:title|'a' lygi 'a'|0}} ||1 ||2
|-
!i
|3 ||2 ||1 ||{{H:title|'i' keičiame į 't'|1}} ||2
|-
!n
|4 ||3 ||2 ||2 ||{{H:title|'n' keičiame į 'ė'|2}}
|-
!a
|5 ||4 ||3 ||3 ||{{H:title|pašaliname 'a'|3}}
|}
{{col-end}}
</center>
Turint čia matricą mes galime nesunkiai transformuoti ją visą algoritmo veikimo metu segmentą <code>s[1..i]</code> į <code>t[1..j]</code> naudojant mažiausią kiekį operacijų <code>d[i,j]</code>, bet kuriuo atveju apatinis dešinys elementas bus mūsų atstumo atsakymas.

=== 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ą:
<syntaxhighlight lang="CSharp">
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];
}
</syntaxhighlight>[[:en:Hirschberg's_algorithm|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 <math>n</math>, kurį gali nustatyti <math>(log n)^{O(1/\epsilon)}</math>, kur <math>\epsilon > 0</math> yra laisvasis parametras, kurį galima redaguoti laike <math>O(n^{1+\epsilon})</math>

=== Generavimo sunkumas ===
Yra įrodyta, jog Levenšteino atstumas tarp dviejų tekstinių aibių negali būti nustatytas laike, kai <math>O(n^{2-\epsilon})</math> nebent [[:en:Exponential_time_hypothesis|eksponentinė laiko hipotezė]] yra neįrodyta.

==Taip pat skaitykite==
*[[:en:Agrep|agrep]]
*[[:en:Diff_utility|diff]]
*[[:en:MinHash|MinHash]]
*[[:en:Dynamic_time_warping|Dinaminis laiko kraipymas]]
*[[:en:Euclidean_distance|Euklido atstumas]]
*[[:en:Homology (biology)#Sequence homology|Homologinės genetinės sekos]]
*[[:en:Hunt–McIlroy_algorithm|Hunt–McIlroy algoritmas]]
*[[:en:Jaccard_index|Jaccard indeksas]]
*[[:en:Locality-sensitive_hashing|Vietai jautri maišatis]]
*[[:en:Longest_common_subsequence_problem|Ilgiausia subsekos problema]]
*[[:en:Manhattan_distance|Manhattan atstumas]]
*[[:en:Metric_space|Metrinė erdvė]]
*[[:en:Most_frequent_k_characters|Daugiausiai pasikartojantys k simboliai]]
*[[:en:Optimal_matching|Optimalaus sujungimo]] algoritmai
*[[:en:Similarity_space|Panašumų erdvė]]
*[[:en:Sørensen_similarity_index|Sørensen panašumų indeksas]]

== Nuorodos ==
*{{citation |contribution=Levenshtein distance |title=Dictionary of Algorithms and Data Structures [online] |editor-first=Paul E. |editor-last=Black |publisher=U.S. National Institute of Standards and Technology |date=14 August 2008 |accessdate=2 November 2016 |url=https://xlinux.nist.gov/dads/HTML/Levenshtein.html }}