b'\n_START_ARTICLE_\nLeven\xc5\xa1teino atstumas\n_START_SECTION_\nApibr\xc4\x97\xc5\xbeimas\n_START_PARAGRAPH_\nMatemati\xc5\xa1kai, Leven\xc5\xa1teino atstumas tarp a ir b aibi\xc5\xb3 yra skai\xc4\x8diuojamas , kur  _NEWLINE_ _NEWLINE_kur kai  indikacijos funkcija yra padidinama 1, o kitu atveju, kai  indikacijos funkcija b\xc5\xabna lygi 0 ir  yra atstumas tarp pirmojo   elemento aib\xc4\x97s  ir pirmojo  elemento i\xc5\xa1  aib\xc4\x97s\n_START_SECTION_\nPritaikymai\n_START_PARAGRAPH_\nPagrindinis apytikslis tekstini\xc5\xb3 aibi\xc5\xb3 lyginimas yra surasti sutapimus trumpi\xc5\xb3 aibi\xc5\xb3 ilguose tekstuose, kur yra tikimasi ma\xc5\xbe\xc5\xb3 neatitikim\xc5\xb3. Originali (tikslioji) aib\xc4\x97 gali b\xc5\xabti laikoma \xc5\xbeodynu, kuris yra jau suvestas ir yra lyginamas su neoriginaliu tekstu. \xc5\xa0itai turi ypatingai plat\xc5\xb3 pritaikym\xc4\x85, puikiai visiems \xc5\xbeinomas pavyzdys yra teksto tikrinimo ir taisymo sistemos sistemos, vizualios \xc5\xbeenkl\xc5\xb3 atpa\xc5\xbeinimo sistemos ir programin\xc4\x97 \xc4\xafranga kuri padeda tiesiogiai ver\xc4\x8diamai kalbai b\xc5\xabti tiksliau atpa\xc5\xbeinama._NEWLINE_Leven\xc5\xa1teino atstumas gali b\xc5\xabti taip pat naudojamas lyginti ir ilgoms aib\xc4\x97ms, bet resurs\xc5\xb3 kaina reikalinga t\xc4\x85 pasiekti yra apytiksliai proporcinga dviej\xc5\xb3 aibi\xc5\xb3 ilgi\xc5\xb3 sumai. \xc5\xa0i neigiama savyb\xc4\x97 padaro \xc5\xa1\xc4\xaf metod\xc4\x85 neprakti\xc5\xa1ku. B\xc5\xabtent lyginti ilgoms aib\xc4\x97ms yra labiau renkamasi Fuzzy algoritmas, kuris \xc5\xa1iuo atveju yra greitesnis ir tikslesnis.\n_START_SECTION_\nRekursija\n_START_PARAGRAPH_\nTai yra pats papras\xc4\x8diausia, bet pats ne efektyviausias b\xc5\xabdas skai\xc4\x8diuoti. Pavyzdyje yra pateiktas C kalbos funkcijos pavyzdys, kuri pasima dvi tekst\xc5\xb3 aibes, j\xc5\xb3 ilgius ir gra\xc5\xbeina atstum\xc4\x85 tarp j\xc5\xb3_NEWLINE_// 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){ _NEWLINE_  int cost;_NEWLINE__NEWLINE_  /* base case: empty strings */_NEWLINE_  if (len_s == 0) return len_t;_NEWLINE_  if (len_t == 0) return len_s;_NEWLINE__NEWLINE_  /* test if last characters of the strings match */_NEWLINE_  if (s[len_s-1] == t[len_t-1])_NEWLINE_      cost = 0;_NEWLINE_  else_NEWLINE_      cost = 1;_NEWLINE__NEWLINE_  /* return minimum of delete char from s, delete char from t, and delete char from both */_NEWLINE_  return minimum(LevenshteinDistance(s, len_s - 1, t, len_t    ) + 1,_NEWLINE_                 LevenshteinDistance(s, len_s    , t, len_t - 1) + 1,_NEWLINE_                 LevenshteinDistance(s, len_s - 1, t, len_t - 1) + cost);}_NEWLINE__NEWLINE_\xc5\xa0is b\xc5\xabdas yra neefektyvus, nes jis daugyb\xc4\x99 kart\xc5\xb3 perskai\xc4\x8diuoja atstum\xc4\x85 su tomis pa\xc4\x8diomis tekst\xc5\xb3 aibes. Efektyvesnis b\xc5\xabdas b\xc5\xabt\xc5\xb3 niekada nekartoti t\xc5\xb3 pa\xc4\x8di\xc5\xb3 skai\xc4\x8diavim\xc5\xb3. Pavyzd\xc5\xbeiui visos galimos pakeitimo reik\xc5\xa1m\xc4\x97s b\xc5\xabt\xc5\xb3 saugomos masyve d[][], kur d[i][j] yra atstumas tarp pirm\xc5\xb3 i \xc5\xbeenkl\xc5\xb3 \xc5\xbeodyje s ir pirm\xc5\xb3 j \xc5\xbeenkl\xc5\xb3 \xc5\xbeodyje t. Lentel\xc4\x99 yra ypa\xc4\x8d paprasta suformuoti pradedant nuo pirm\xc5\xb3j\xc5\xb3 \xc5\xbeenkl\xc5\xb3. Kai visa lentel\xc4\x97 yra suformuota, tai m\xc5\xabs\xc5\xb3 norimas atstumas yra d[len_s][len_t].\n_START_SECTION_\nDviej\xc5\xb3 matricos eilu\xc4\x8di\xc5\xb3 iteracija\n_START_PARAGRAPH_\nPasirodo norint sukonstruoti matric\xc4\x85 reikia tik dviej\xc5\xb3 eili\xc5\xb3 nenorint rekonstruoti redaguotas tekstines aibes. Leven\xc5\xa1teino atstum\xc4\x85 galim\xc4\x85 paskai\xc4\x8diuoti iteruojant pavyzdyje pateikt\xc4\x85 funkcij\xc4\x85:_NEWLINE_int LevenshteinDistance(string s, string t){_NEWLINE_    // degenerate cases_NEWLINE_    if (s == t) return 0;_NEWLINE_    if (s.Length == 0) return t.Length;_NEWLINE_    if (t.Length == 0) return s.Length;_NEWLINE__NEWLINE_    // create two work vectors of integer distances_NEWLINE_    int[] v0 = new int[t.Length + 1];_NEWLINE_    int[] v1 = new int[t.Length + 1];_NEWLINE__NEWLINE_    // initialize v0 (the previous row of distances)_NEWLINE_    // this row is A[0][i]: edit distance for an empty s_NEWLINE_    // the distance is just the number of characters to delete from t_NEWLINE_    for (int i = 0; i < v0.Length; i++)_NEWLINE_        v0[i] = i;_NEWLINE__NEWLINE_    for (int i = 0; i < s.Length; i++)_NEWLINE_    {_NEWLINE_        // calculate v1 (current row distances) from the previous row v0_NEWLINE__NEWLINE_        // first element of v1 is A[i+1][0]_NEWLINE_        //   edit distance is delete (i+1) chars from s to match empty t_NEWLINE_        v1[0] = i + 1;_NEWLINE__NEWLINE_        // use formula to fill in the rest of the row_NEWLINE_        for (int j = 0; j < t.Length; j++)_NEWLINE_        {_NEWLINE_            var cost = (s[i] == t[j]) ? 0 : 1;_NEWLINE_            v1[j + 1] = Minimum(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost);_NEWLINE_        }_NEWLINE__NEWLINE_        // copy v1 (current row) to v0 (previous row) for next iteration_NEWLINE_        for (int j = 0; j < v0.Length; j++)_NEWLINE_            v0[j] = v1[j];_NEWLINE_    }_NEWLINE__NEWLINE_    return v1[t.Length];}_NEWLINE_Hirschberg algoritmas\xc2\xa0sujungia Leven\xc5\xa1teino atstum\xc4\x85 su skaldyk ir valdyk teorija. Jis gali sugeneruoti ne tik atstum\xc4\x85, bet ir optimali\xc4\x85 sek\xc4\x85 tokiame pa\xc4\x8diame asimptotiniame laike ir erdv\xc4\x97je.\n_START_SECTION_\nAproksimacija\n_START_PARAGRAPH_\nAtstumas tarp dviej\xc5\xb3 tekstini\xc5\xb3 aibi\xc5\xb3 yra , kur\xc4\xaf gali nustatyti , kur  yra laisvasis parametras, kur\xc4\xaf galima redaguoti laike\n_START_SECTION_\nGeneravimo sunkumas\n_START_PARAGRAPH_\nYra \xc4\xafrodyta, jog Leven\xc5\xa1teino atstumas tarp dviej\xc5\xb3 tekstini\xc5\xb3 aibi\xc5\xb3 negali b\xc5\xabti nustatytas laike, kai  nebent eksponentin\xc4\x97 laiko hipotez\xc4\x97 yra ne\xc4\xafrodyta.'