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
redaktəİki sətri arasındakı Levenşteyn məsafəsi (müvafiq olaraq və uzunluğu) ilə verilir.
Nümunə
redaktə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
redaktə- ↑ В. И. Левенштейн. Двоичные коды с исправлением выпадений, вставок и замещений символов [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.
Xarici keçidlər
redaktə- 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