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ət

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.

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.^:32 Bu, sətir düzülüşləri ilə sıx bağlıdır.

Tərifi

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

\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:

anket → apket ("n" hərfini "p" ilə dəyişdirmək),
apket → aptet ("k" hərfini "t" ilə dəyişdirmək),
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:

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

İstinadlar

В. И. Левенштейн. Двоичные коды с исправлением выпадений, вставок и замещений символов [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.
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

[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.

[navarro-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.