Levenshteyn masofasi - Levenshtein distance - Wikipedia

Yilda axborot nazariyasi, tilshunoslik va Kompyuter fanlari, Levenshteyn masofasi a mag'lubiyat metrikasi ikki ketma-ketlik orasidagi farqni o'lchash uchun. Norasmiy ravishda, ikki so'z o'rtasidagi Levenshtein masofasi bitta so'zni boshqasiga o'zgartirish uchun zarur bo'lgan bitta belgidan iborat tahrirlarning (qo'shimchalar, o'chirishlar yoki almashtirishlar) minimal sonidir. Sovet matematikasi nomi bilan atalgan Vladimir Levenshtein, bu masofani 1965 yilda ko'rib chiqqan.[1]

Levenshtein masofasi deb ham atash mumkin masofani tahrirlash, garchi bu atama masofaviy ko'rsatkichlarning katta oilasini ham birgalikda ma'lum bo'lsa ham masofani tahrirlash.[2]:32 Bu bilan chambarchas bog'liq qatorli hizalamalar.

Ta'rif

Levenshteinning ikki tor orasidagi masofasi (uzunlik va mos ravishda) tomonidan berilgan qayerda

qaerda bir nechta mag'lubiyat ning birinchi belgisidan tashqari hamma qatori va bo'ladi mag'lubiyatning belgisi , 0 belgisidan boshlab.

E'tibor bering, minimal elementdagi birinchi element o'chirishga to'g'ri keladi (dan ga ), ikkinchisini qo'shishga, uchinchisini almashtirishga.

Ushbu ta'rif to'g'ridan-to'g'ri mos keladi sodda rekursiv dastur.

Misol

O'zgartirish qiymati 1 va o'chirish yoki qo'shish qiymati 0,5 ga teng bo'lgan ikki so'z uchun masofa matritsasini tahrir qiling.

Masalan, "mushukcha" va "o'tirish" orasidagi Levenshteyn masofasi 3 ga teng, chunki quyidagi uchta tahrir bir-birini boshqasiga o'zgartiradi va uchdan kam tahrir bilan buni amalga oshirishning iloji yo'q:

  1. kitten → sitten ("s" ni "k" ga almashtirish)
  2. o'tirishen → o'tirishmenn ("i" ni "e" ga almashtirish)
  3. sittin → sitting (oxirida "g" qo'shilishi).

Yuqori va pastki chegaralar

Levenshtein masofasi bir necha oddiy yuqori va pastki chegaralarga ega. Bunga quyidagilar kiradi:

  • Bu hech bo'lmaganda ikkita torning o'lchamlari farqidir.
  • Bu eng uzun ipning uzunligidir.
  • Agar satrlar teng bo'lsa va u nolga teng bo'lsa.
  • Agar iplar bir xil o'lchamda bo'lsa, Hamming masofasi Levenshtein masofasining yuqori chegarasi. Hamming masofasi - bu ikkita satrda tegishli belgilar har xil bo'lgan pozitsiyalar soni.
  • Levenshteinning ikki tor orasidagi masofasi ularning Levenshteinning uchinchi ipdan masofalarining yig'indisidan katta emas (uchburchak tengsizligi ).

Uzunligi bir xil bo'lgan ikkita tor orasidagi Levenshtein masofasi Xamming masofasidan qat'iyan kamroq bo'lganligi misolida "nuqson" va "maysazor" juftligi keltirilgan. Bu erda Levenshtein masofasi 2 ga teng (old tomondan "f" ni o'chiring; oxiriga "n" ni qo'ying). The Hamming masofasi 4.

Ilovalar

Yilda taxminiy satrlarni moslashtirish, Maqsad - ko'pgina farqli o'laroq kutilgan vaziyatlarda, uzunroq matnlardagi qisqa satrlar uchun mosliklarni topish. Qisqa torlar, masalan, lug'atdan kelib chiqishi mumkin. Bu erda iplarning biri odatda qisqa, ikkinchisi o'zboshimchalik bilan uzun. Bu juda ko'p dasturlarga ega, masalan, imlo tekshirgichlari, uchun tuzatish tizimlari optik belgilarni aniqlash va tabiiy tilda tarjima qilishga yordam beradigan dasturiy ta'minot tarjima xotirasi.

Levenshtein masofasini ikkita uzunroq iplar orasida ham hisoblash mumkin, ammo uni hisoblash uchun xarajatlar, bu ikki chiziq uzunligining hosilasi bilan mutanosib bo'lib, buni amaliy emas. Shunday qilib, yordam berish uchun foydalanilganda loyqa satrlarni qidirish kabi dasturlarda yozuvlarni bog'lash, taqqoslangan satrlar odatda qisqa bo'lib, taqqoslash tezligini oshirishga yordam beradi.[iqtibos kerak ]

Tilshunoslikda Levenshteyn masofasi miqdorini aniqlash uchun metrik sifatida ishlatiladi lingvistik masofa, yoki ikki til bir-biridan qanday farq qiladi.[3] Bu bilan bog'liq o'zaro tushunarli, lingvistik masofa qanchalik baland bo'lsa, o'zaro tushunarlilik past bo'ladi va lingvistik masofa qanchalik past bo'lsa, o'zaro tushunarli bo'ladi.

Boshqa tahrirlash masofasi ko'rsatkichlari bilan aloqasi

Boshqa mashhur choralari mavjud masofani tahrirlash, boshqa tahrir qilingan operatsiyalar to'plami yordamida hisoblangan. Masalan; misol uchun,

Masofani tahrirlash odatda ma'lum bir ruxsat berilgan tahrirlash operatsiyalari to'plami bilan hisoblangan parametrlashtiriladigan o'lchov sifatida aniqlanadi va har bir operatsiyaga xarajat (ehtimol cheksiz) belgilanadi. Bu DNK tomonidan yanada umumlashtiriladi ketma-ketlikni tekislash kabi algoritmlar Smit-Waterman algoritmi, bu operatsiya narxini uning qo'llanilish joyiga bog'liq.

Levenshtein masofasini hisoblash

Rekursiv

Bu to'g'ridan-to'g'ri, ammo samarasiz, rekursivdir Xaskell amalga oshirish l masofa ikkita satrni oladigan funktsiya, s va t, ularning uzunligi bilan birga va Levenshtein masofasini qaytaradi:

l masofa :: ( Tenglama a ) => [a] -> [a] -> Intl masofa [] t = uzunlik t   - Agar s bo'sh bo'lsa, bu masofa tdagi belgilar sonil masofa s [] = uzunlik s   - Agar t bo'sh bo'lsa, masofa sdagi belgilar sonil masofa (a:s) (b:t ') =  agar    a == b  keyin    l masofa s t '         - Agar birinchi belgilar bir xil bo'lsa, ularni e'tiborsiz qoldirish mumkin  boshqa    1 + eng kam             - Aks holda barcha uchta harakatlarni sinab ko'ring va eng yaxshisini tanlang      [ l masofa (a:s) t ' - Belgilar kiritildi (b kiritildi)      , l masofa s (b:t ') - Belgilar o'chirildi (o'chirildi)      , l masofa s t '     - Belgini almashtirish (b bilan almashtirish)      ]

Ushbu dastur juda samarasiz, chunki u bir xil pastki chiziqlarning Levenshtein masofasini ko'p marta hisoblab chiqadi.

Keyinchalik samarali usul hech qachon bir xil masofani hisoblashni takrorlamaydi. Masalan, barcha mumkin bo'lgan prefikslarning Levenshtein masofasi massivda saqlanishi mumkin qayerda bu oxirgisi orasidagi masofa simli belgilar s va oxirgi simli belgilar t. Jadvalni 0-qatordan boshlab bir vaqtning o'zida bitta qator qurish oson, butun jadval tuzilgach, kerakli masofa oxirgi satr va ustundagi jadvalda joylashgan bo'lib, barcha belgilar orasidagi masofani bildiradi. s va barcha belgilar t.

To'liq matritsa bilan takrorlanadigan

Izoh: Ushbu bo'limda 0 asosidagi satrlar o'rniga 1 asosidagi satrlar ishlatiladi

Levenshtein masofasini hisoblash, agar biz zaxira qilsak, kuzatishga asoslanadi matritsa Levenshtein masofasini hammasi o'rtasida ushlab turish prefikslar birinchi qator va ikkinchisining barcha prefikslari, keyin biz matritsadagi qiymatlarni a-da hisoblashimiz mumkin dinamik dasturlash moda va shuning uchun oxirgi to'liq qiymat sifatida ikkita to'liq satr orasidagi masofani toping.

Ushbu algoritm, pastdan yuqoriga misol dinamik dasturlash, 1974 yilgi maqolada, variantlari bilan muhokama qilingan The String-to-string tuzatish muammosi Robert A. Vagner va Maykl J. Fischer tomonidan.[4]

Bu to'g'ridan-to'g'ri psevdokod funktsiya uchun amalga oshirish Levenshtein masofasi ikkita ipni oladi, s uzunlik mva t uzunlik nva Levenshtein masofasini qaytaradi:

funktsiya Levenshtein masofasi(char s[1..m], char t[1..n]):  // hamma uchun i va j, d [i, j] Levenshtein masofasini ushlab turadi  // s ning birinchi i belgisi va t ning birinchi j belgisi  e'lon qiling int d[0..m, 0..n]   o'rnatilgan har biri element yilda d ga nol   // manba prefikslari bo'sh satrga aylantirilishi mumkin  // barcha belgilarni tashlash  uchun men dan 1 ga m:      d[men, 0] := men   // maqsadli prefikslarga bo'sh manba prefiksidan erishish mumkin  // har bir belgini qo'shish orqali  uchun j dan 1 ga n:      d[0, j] := j   uchun j dan 1 ga n:      uchun men dan 1 ga m:          agar s[men] = t[j]:            almashtirish qiymati := 0          boshqa:            almashtirish qiymati := 1          d[men, j] := eng kam(d[men-1, j] + 1,                   // o'chirish                             d[men, j-1] + 1,                   // qo'shish                             d[men-1, j-1] + almashtirish qiymati)  // almashtirish   qaytish d[m, n]

Olingan matritsaning ikkita misoli (belgilangan raqam ustiga o'tsangiz, ushbu raqamni olish uchun qilingan operatsiya aniqlanadi):

The o'zgarmas algoritm davomida saqlanib qolgan, biz dastlabki segmentni o'zgartira olamiz s[1..men] ichiga t[1..j] minimal yordamida d[men,j] operatsiyalar. Oxirida massivning o'ng pastki elementi javobni o'z ichiga oladi.

Ikki matritsali qator bilan takrorlanadigan

Ma'lum bo'lishicha, agar tahrirlangan kirish satrlarini qayta tiklashni istamasa (avvalgi satr va joriy qator hisoblansa), qurilish uchun jadvalning atigi ikki qatori kerak bo'ladi.

Levenshtein masofasini quyidagi algoritm yordamida takroriy hisoblash mumkin:[5]

funktsiya Levenshtein masofasi(char s[0..m-1], char t[0..n-1]):    // butun masofaning ikkita ish vektorini yarating    e'lon qiling int v0[n + 1]    e'lon qiling int v1[n + 1]    // v0 ni ishga tushiring (oldingi qatorlar qatori)    // bu qator A [0] [i]: bo'sh s uchun tahrir qilish masofasi    // masofa faqat t dan o'chirib tashlanadigan belgilar soni    uchun men dan 0 ga n:        v0[men] = men    uchun men dan 0 ga m-1:        // oldingi v0 qatoridan v1 (joriy qator masofalari) ni hisoblang        // v1 ning birinchi elementi A [i + 1] [0]        // tahrir qilish masofasi s dan (i + 1) gacha bo'lgan belgilarni bo'sh t ga moslashtirish uchun        v1[0] = men + 1        // qatorning qolgan qismini to'ldirish uchun formuladan foydalaning        uchun j dan 0 ga n-1:            // A [i + 1] [j + 1] uchun xarajatlarni hisoblash            o'chirish qiymati := v0[j + 1] + 1            kiritish qiymati := v1[j] + 1            agar s[men] = t[j]:                almashtirish qiymati := v0[j]            boshqa:                almashtirish qiymati := v0[j] + 1;            v1[j + 1] := eng kam(o'chirish qiymati, kiritish qiymati, almashtirish qiymati)        // keyingi takrorlash uchun v1 (oldingi satr) ni v0 (oldingi satr) ga nusxalash        // v1-dagi ma'lumotlar doimo bekor qilinganligi sababli, nusxasiz almashtirish yanada samarali bo'lishi mumkin        almashtirish v0 bilan v1    // oxirgi almashtirishdan so'ng, v1 natijalari endi v0 ga teng    qaytish v0[n]

Ushbu ikkita satr varianti suboptimaldir - kerakli xotira hajmi bir qatorga va bitta (indeks) so'zga kamaytirilishi mumkin, chunki keshning joylashuvi yaxshilanadi.[6]

Xirshberg algoritmi ushbu usulni birlashtiradi bo'ling va zabt eting. U tahrirlash masofasini emas, balki tahrirlashning optimal ketma-ketligini bir xil asimptotik vaqt va makon chegaralarida hisoblashi mumkin.[7]

Adaptiv variant

Dinamik variant ideal dastur emas. Moslashuvchan yondashuv talab qilinadigan xotira hajmini kamaytirishi va eng yaxshi holatda vaqtni murakkabligini chiziqli chiziqqa qadar qisqartirishi va eng yomon holatda eng qisqa satr uzunligida kvadratikdan oshmasligi mumkin. . Fikr shundaki, kutubxonaning samarali funktsiyalaridan foydalanish mumkin (std :: mos kelmaslik) umumiy prefikslar va qo'shimchalarni tekshirish va faqat mos kelmaslik sababli DP qismiga sho'ng'ish.[6]

Avtomatlar

Levenshtein avtomatlari mag'lubiyatning berilgan qatordan berilgan doimiydan pastroq tahrir masofasi bor-yo'qligini samarali aniqlash.[8]

Yaqinlashish

Levenshtein uzunligining ikki ipi orasidagi masofa n bolishi mumkin taxminiy bir omil ichida

qayerda ε > 0 vaqt ichida sozlanishi kerak bo'lgan bepul parametr O(n1 + ε).[9]

Hisoblashning murakkabligi

Levenshteynning ikki uzunlikdagi masofa ekanligi ko'rsatilgan n vaqtida hisoblash mumkin emas O(n2 - ε) noldan katta bo'lgan har qanday ε uchun kuchli eksponent vaqt gipotezasi yolg'ondir.[10]

Shuningdek qarang

Adabiyotlar

  1. ^ Vladiymir I. Levenshteyn (1965). Dvichchee kody s ispravleniem vypadeniy, vstavok i zameshcheniy simvolov [O'chirish, qo'shish va qaytarishni to'g'rilashga qodir bo'lgan ikkilik kodlar]. Doklady Akademiy Nauk SSSR (rus tilida). 163 (4): 845–8. Ingliz tilida: Levenshtein, Vladimir I. (1966 yil fevral). "O'chirishni, qo'shib qo'yishni va bekor qilishni tuzatishga qodir bo'lgan ikkilik kodlar". Sovet fizikasi Dokladiy. 10 (8): 707–710. Bibcode:1966SPhD ... 10..707L.
  2. ^ Navarro, Gonsalo (2001). "Taxminan mag'lubiyatni moslashtirish uchun ekskursiya" (PDF). ACM hisoblash tadqiqotlari. 33 (1): 31–88. CiteSeerX  10.1.1.452.6317. doi:10.1145/375360.375365. S2CID  207551224.
  3. ^ Yan D. ten Tije; Ludger Zeevaert (2007 yil 1-yanvar), Qabul qiluvchi ko'p tillilik: lingvistik tahlillar, til siyosati va didaktik tushunchalar, John Benjamins Publishing Company, 2007 yil, ISBN  978-90-272-1926-8, ... Tushunuvchanlik lingvistik masofaga teskari bog'liq deb o'ylasak ... tarkibidagi so'zlar qarindoshlarning foiz nisbati (bevosita yoki sinonim orqali bog'liq) ... leksik yaqinlik ... grammatik yaqinlik ...
  4. ^ Vagner, Robert A.; Fischer, Maykl J. (1974), "String-stringni tuzatish muammosi", ACM jurnali, 21 (1): 168–173, doi:10.1145/321796.321811, S2CID  13381535
  5. ^ Xjelmqvist, Sten (2012 yil 26 mart), Tez, xotirani tejaydigan Levenshtein algoritmi
  6. ^ a b "Clearer / Iosifovich: juda tez levenshtein masofa funktsiyasi". Arxivlandi asl nusxasi 2018 yil 12-iyun kuni. Bu oladi [sic] juda kam xotiradan foydalanish tezligi, ko'pincha buferni to'liq keshda saqlash va xarajatlarni oshirmaydigan har qanday prefiks va postfiksni o'tkazib yuborish orqali ish hajmini kamaytirish. [...] Gap shundaki, siz matritsadagi katakchani yangilashni xohlaganingizda uchta qiymatni bilishingiz kerak va siz ulardan ikkitasini buferda saqlashingiz mumkin, uchinchi qiymatni esa belgilangan joyda saqlang. Yashaydigan nasl kodi
  7. ^ Xirshberg, D. S. (1975). "Maksimal umumiy ketma-ketlikni hisoblash uchun chiziqli kosmik algoritm" (PDF). ACM aloqalari (Qo'lyozma taqdim etilgan). 18 (6): 341–343. CiteSeerX  10.1.1.348.4774. doi:10.1145/360825.360861. JANOB  0375829. S2CID  207694727.
  8. ^ Shuls, Klaus U.; Mixov, Stoyan (2002). "Levenshtein-Automata yordamida torlarni tezkor tuzatish". Xalqaro hujjatlarni tahlil qilish va tan olish jurnali. 5 (1): 67–85. CiteSeerX  10.1.1.16.652. doi:10.1007 / s10032-002-0082-8. S2CID  207046453.
  9. ^ Andoni, Aleksandr; Krautgamer, Robert; Onak, Kshishtof (2010). Tahrirlash masofasi va assimetrik so'rovlarning murakkabligi uchun poliografitik yaqinlashish. IEEE simptomi. Informatika asoslari (FOCS). arXiv:1005.4033. Bibcode:2010arXiv1005.4033A. CiteSeerX  10.1.1.208.2079.
  10. ^ Backurs, Arturs; Indik, Piotr (2015). Masofani tahrirlash kuchli kvadratik vaqt ichida amalga oshirilmaydi (agar SETH noto'g'ri bo'lsa). Hisoblash nazariyasi simpoziumida (STOC) qirq yettinchi yillik ACM. arXiv:1412.0348. Bibcode:2014arXiv1412.0348B.

Tashqi havolalar