Levenşteyn məsafəsi

Levenşteyn məsafəsi — informasiya nəzəriyyəsi, dilçilik və kompüter elmində iki ardıcıllıq arasındakı fərqi ölçmək üçün sətir ölçüsü. Qeyri-rəsmi olaraq iki söz arasındakı Levenşteyn məsafəsi bir sözü digərinə dəyişdirmək üçün tələb olunan tək simvollu redaktələrin (daxiletmə, silmə və ya əvəzetmə) minimum sayıdır. O, 1965-ci ildə bu məsafəni hesablayan sovet riyaziyyatçısı Vladimir Levenşteynin şərəfinə adlandırılıb.^[1]

Levenşteyn məsafəsi "redaktə" məsafəsi də adlandırıla bilər, baxmayaraq ki, bu termin həm də ümumi olaraq redaktə məsafəsi kimi tanınan daha böyük məsafə ölçüləri ailəsini ifadə edə bilər.^[2]:32 Bu, sətir düzülüşləri ilə sıx bağlıdır.

Tərifi

İki ${\displaystyle a,b}$ sətri arasındakı Levenşteyn məsafəsi (müvafiq olaraq ${\displaystyle |a|}$ və ${\displaystyle |b|}$ uzunluğu) ${\displaystyle \operatorname {lev} (a,b)}$ ilə verilir.

${\displaystyle \operatorname {lev} (a,b)={\begin{cases}|a|&{\text{ if }}|b|=0,\\|b|&{\text{ if }}|a|=0,\\\operatorname {lev} {\big (}\operatorname {tail} (a),\operatorname {tail} (b){\big )}&{\text{ if }}\operatorname {head} (a)=\operatorname {head} (b),\\1+\min {\begin{cases}\operatorname {lev} {\big (}\operatorname {tail} (a),b{\big )}\\\operatorname {lev} {\big (}a,\operatorname {tail} (b){\big )}\\\operatorname {lev} {\big (}\operatorname {tail} (a),\operatorname {tail} (b){\big )}\\\end{cases}}&{\text{ otherwise}}\end{cases}}}$

Nümunə

Əvəzetmə dəyərini 1, silinmə və ya daxiletmə dəyərini 0,5 olaraq istifadə edərək iki söz üçün məsafə matrisi redaktəsi

Məsələn, "anket" və "aptek" sözləri arasındakı Levenşteyn məsafəsi 3-dür, çünki aşağıdakı 3 redaktə bir hərfi digərinə dəyişir və bunu 3-dən az redaktə ilə etmək mümkün deyil:

1. anket → apket ("n" hərfini "p" ilə dəyişdirmək),
2. apket → aptet ("k" hərfini "t" ilə dəyişdirmək),
3. aptet → aptek ("t" hərfini "k" ilə dəyişdirmək).

Məsafəsi 1 olan sözlərə "qaş" və "daş"ı nümunə göstərmək olar:

1. qaş → daş ("q" hərfini "d" ilə dəyişdirmək).

İstinadlar

1. В. И. Левенштейн. Двоичные коды с исправлением выпадений, вставок и замещений символов [Binary codes capable of correcting deletions, insertions, and reversals]. Доклады Академии Наук СССР (rus). 163 (4). 1965: 845–848. Appeared in English as: Levenshtein, Vladimir I. "Binary codes capable of correcting deletions, insertions, and reversals". Soviet Physics Doklady. 10 (8). February 1966: 707–710. Bibcode:1966SPhD...10..707L.
2. Navarro, Gonzalo. "A guided tour to approximate string matching" (PDF). ACM Computing Surveys. 33 (1). 2001: 31–88. CiteSeerX 10.1.1.452.6317. doi:10.1145/375360.375365. 2023-09-29 tarixində arxivləşdirilib (PDF). İstifadə tarixi: 2023-12-05.

Xarici keçidlər

• Black, Paul E., redaktorLevenshtein distance // Dictionary of Algorithms and Data Structures [online], U.S. National Institute of Standards and Technology, 14 August 2008, İstifadə tarixi: 2 November 2016
• Rosseta Code implementations of Levenshtein distance