35.Levenshtein masofasi Levenshtein masofasi ikki qatorning bir-biridan qanchalik farq qilishini ko'rsatadigan raqamdir. Raqam qanchalik baland bo'lsa, ikkita satr shunchalik farq qiladi. Misol uchun, “kitten” and “sitting” o'rtasidagi Levenshtein masofasi 3 ni tashkil qiladi, chunki birini boshqasiga o'zgartirish uchun kamida 3 ta tahrir talab qilinadi.
k itten → s itten (“k” o‘rniga “s” o‘rniga qo‘yish)
sitt e n → sitt i n (“e” o‘rniga “i” ni almashtirish)
sittin → sittin g (oxirida “g” qo‘shilishi).
"Tahrirlash" belgi qo'shish, belgini o'chirish yoki belgini almashtirish bilan belgilanadi.
1965 yilda o'z algoritmini ishlab chiqqan Vladimir Levenshteynga barchamiz minnatdorchilik bildirishimiz kerak. Algoritm 50 yildan ortiq vaqt davomida yaxshilanmagan va buning sababi yaxshi.
37.Garvis(Jarvis ) algoritimi: Jarvis algoritmınıń ideyası ápiwayı, biz eń shep noqattan (yamasa minimal x koordinata ma`nisine iye noqattan ) baslaymız hám noqatlardı saat miliga keri baǵıtda orawdı dawam ettiremiz. Úlken soraw sonda, ámeldegi noqat retinde p noqatı berilgen bolsa, shıǵıw daǵı keyingi noqattı qanday tabıw múmkin? Ideya bul erda orientation () den paydalanıw bolıp tabıladı. Keyingi noqat basqa barlıq noqatlardı saat miliga keri baǵıtda uradigan noqat retinde saylanadı, yaǵnıy keyingi noqat q bolsa, basqa r noqat ushın bizde " orientatsiya (p, q, r) = saat miliga teris" bolsa.
Tómende tolıq algoritm keltirilgen.
1) p ni eń shep noqat retinde baslań.
2) Birinshi (yamasa eń shep) noqatqa qaytmagunimizcha, tómendegi ámellerdi atqarıń.
….. a) Keyingi q noqat sonday noqatki, úshlıq (p, q, r) basqa hár qanday basqa r noqat ushın saat miliga teris boladı. Bunı tabıw ushın biz q ni keyingi noqat retinde jumısqa túsiremiz, keyininen barlıq noqatlar boylap ótemiz. Hár qanday i noqat ushın, eger i saat miliga teris bolsa, yaǵnıy orientatsiya (p, i, q) saat miliga teris bolsa, ol halda biz q ni i retinde jańalaymız. Biziń juwmaqlawshı q ma`nisi saat miliga teris noqat boladı.
….. b) keyingi[p] = q (Q ni shıǵıw qabarıq korpusında p dıń keyingisi retinde saqlań ).
….. c) p = q (keyingi iteratsiya ushın p ni q retinde ornatıń ).
Waqıt quramalılıǵı : Korpus daǵı hár bir noqat ushın biz keyingi noqattı anıqlaw ushın basqa barlıq noqatlardı tekseremiz. waqıt quramalılıǵı -? (m * n) bul erda n - kirisiw noqatları sanı hám m - shıǵıw yamasa korpus noqatları sanı (m <= n). Eń jaman jaǵdayda, waqıt quramalılıǵı O (n 2 ) bolıp tabıladı. Eń jaman jaǵday, barlıq noqatlar korpusda (m = n)
