www.wikidata.uk-ua.nina.az

Відстань Левенштейна Ві дстань Левенште йна також функція Левенштейна алгоритм Левенштейна або відстань редагування у те

Відстань Левенштейна

Ві́дстань Левенште́йна (також функція Левенштейна, алгоритм Левенштейна або відстань редагування) у теорії інформації і комп'ютерній лінгвістиці міра відмінності двох послідовностей символів (рядків). Обчислюється як мінімальна кількість операцій вставки, видалення і заміни, необхідних для перетворення одної послідовності в іншу.

Метод розроблений у 1965 році радянським математиком Володимиром Йосиповичем Левенштейном і названий його іменем.

Приклад:

Щоб перетворити слово небо на слово треба необхідно зробити дві заміни та одну вставку, відповідно дистанція Левенштейна становить 3:

  1. небо -> неба (замінюємо о на а)
  2. неба -> реба (замінюємо н на р)
  3. реба -> треба (вставляємо т)

На практиці дистанція Левенштейна використовується для визначення подібності послідовностей символів, наприклад для корекції орфографії або для пошуку дублікатів.

Алгоритм Редагувати

Для розрахунку відстані Левенштейна найчастіше застосовують простий алгоритм, в якому використовується матриця розміром (n + 1) * (m + 1), де n і m - довжини порівнюваних рядків. Окрім цього вартість операцій вилучення, заміни та вставки вважається однаковою. Для конструювання матриці використовують таке рекурсивне рівняння:

У псевдокоді алгоритм виглядає так: 

int LevenshteinDistance(char str1[1..lenStr1], char str2[1..lenStr2]) // d таблиця кількість рядків = lenStr1+1 та кількість стовпців = lenStr2+1 declare int d[0..lenStr1, 0..lenStr2] // i та j використовуються для індексування позиції у str1 та у str2 declare int i, j, cost for i from 0 to lenStr1 d[i, 0] := i for j from 0 to lenStr2 d[0, j] := j for i from 1 to lenStr1 for j from 1 to lenStr2 if str1[i] = str2[j] then cost := 0 //однакові else cost := 1 //заміна d[i, j] := minimum( d[i-1, j ] + 1, // вилучення d[i , j-1] + 1, // вставка d[i-1, j-1] + cost // заміна або однакові ) return d[lenStr1, lenStr2] //значення відстані Левенштейна в останній клітинці матриці

Цей алгоритм легко реалізувати вручну, заповнивши таблицю. Наприклад, для визначення відстані між словами корабель і бал таблиця виглядатиме так:

ε - т.зв. пусте слово, без літер 

 ε К О Р А Б Е Л Ь ε 0 1 2 3 4 5 6 7 8 /* тобто відстань між пустим словом і словом КОРАБЕЛЬ = 8 (довжина слова КОРАБЕЛЬ) */ Б 1 1 2 3 4 4 5 6 7 /* між Б і КОРАБЕЛЬ відстань = 7 (літера Б в обох словах і може бути використана) */ А 2 2 2 3 3 4 5 6 7 /* між БА і КОРАБЕЛЬ відстань = 7 (лише одну з літер Б або А можна використати) */ Л 3 3 3 3 4 4 5 5 6 /* між БАЛ і КОРАБЕЛЬ відстань = 6 (можна використати дві літери (Б або А) + Л) */

Для визначення послідовності операцій, необхідних для переходу від одного слова до іншого, потрібно знайти найдешевший шлях від першої [0,0] клітинки матриці до останньої [i,j]. Як видно з прикладу існує декілька еквівалентних шляхів, і алгоритм знаходить не тільки мінімальну відстань, але й усі шляхи. На кожному наступному кроці застосовується інформація, здобута на попередньому кроці (принцип динамічного програмування).

У PHP цей алгоритм реалізовано функцією levenshtein.

Межі Редагувати

Для відстані Левенштейна існують такі верхня і нижня межі:

  • Дистанція Левенштейна не є меншою за різницю довжини рядків, що порівнюються
  • Вона не є більшою довжини найдовшого рядка
  • Вона дорівнює 0 тоді і тільки тоді, коли рядки однакові (однакові символи на однакових позиціях)

Між відстанню Левенштейна та відстанню Гемінга існують такі взаємозв'язки:

  • Для рядків однакової довжини відстань Левенштейна рівна відстані Гемінга, оскільки відстань Гемінга користується лише операцією заміни одного символу на інший і не дозволяє вставки та вилучення символів
  • Якщо рядки різної довжини, то верхньою межею є відстань Гемінга плюс різниця довжини рядків

Реалізація Редагувати

Реалізація оптимізованого алгоритму пошуку відстані Левенштейна на мові Python 3: 

def levenstein(s1,s2): n = range(0,len(s1)+1) for y in range(1,len(s2)+1): l,n = n,[y] for x in range(1,len(s1)+1): n.append(min(l[x]+1,n[-1]+1,l[x-1]+((s2[y-1]!=s1[x-1]) and 1 or 0))) return n[-1]

Подібні методи Редагувати

Примітки Редагувати

  1. . PHP Manual. The PHP Group. Архів оригіналу за 16 грудня 2017. Процитовано 19 грудня 2017.  (англ.)

Посилання Редагувати

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Vi dstan Levenshte jna takozh funkciya Levenshtejna algoritm Levenshtejna abo vidstan redaguvannya u teoriyi informaciyi i komp yuternij lingvistici mira vidminnosti dvoh poslidovnostej simvoliv ryadkiv Obchislyuyetsya yak minimalna kilkist operacij vstavki vidalennya i zamini neobhidnih dlya peretvorennya odnoyi poslidovnosti v inshu Metod rozroblenij u 1965 roci radyanskim matematikom Volodimirom Josipovichem Levenshtejnom i nazvanij jogo imenem Priklad Shob peretvoriti slovo nebo na slovo treba neobhidno zrobiti dvi zamini ta odnu vstavku vidpovidno distanciya Levenshtejna stanovit 3 nebo gt neba zaminyuyemo o na a neba gt reba zaminyuyemo n na r reba gt treba vstavlyayemo t Na praktici distanciya Levenshtejna vikoristovuyetsya dlya viznachennya podibnosti poslidovnostej simvoliv napriklad dlya korekciyi orfografiyi abo dlya poshuku dublikativ Zmist 1 Algoritm 2 Mezhi 3 Realizaciya 4 Podibni metodi 5 Primitki 6 PosilannyaAlgoritm RedaguvatiDlya rozrahunku vidstani Levenshtejna najchastishe zastosovuyut prostij algoritm v yakomu vikoristovuyetsya matricya rozmirom n 1 m 1 de n i m dovzhini porivnyuvanih ryadkiv Okrim cogo vartist operacij viluchennya zamini ta vstavki vvazhayetsya odnakovoyu Dlya konstruyuvannya matrici vikoristovuyut take rekursivne rivnyannya D 0 0 0 displaystyle D 0 0 0 nbsp D i j m i n D i 1 j 1 0 e q u a l n o c h a n g e D i 1 j 1 1 r e p l a c e D i 1 j 1 i n s e r t D i j 1 1 d e l e t e displaystyle D i j min begin cases D i 1 j 1 amp 0 rm equal nochange D i 1 j 1 amp 1 rm replace D i 1 j amp 1 rm insert D i j 1 amp 1 rm delete end cases nbsp U psevdokodi algoritm viglyadaye tak int LevenshteinDistance char str1 1 lenStr1 char str2 1 lenStr2 d tablicya kilkist ryadkiv lenStr1 1 ta kilkist stovpciv lenStr2 1 declare int d 0 lenStr1 0 lenStr2 i ta j vikoristovuyutsya dlya indeksuvannya poziciyi u str1 ta u str2 declare int i j cost for i from 0 to lenStr1 d i 0 i for j from 0 to lenStr2 d 0 j j for i from 1 to lenStr1 for j from 1 to lenStr2 if str1 i str2 j then cost 0 odnakovi else cost 1 zamina d i j minimum d i 1 j 1 viluchennya d i j 1 1 vstavka d i 1 j 1 cost zamina abo odnakovi return d lenStr1 lenStr2 znachennya vidstani Levenshtejna v ostannij klitinci matrici Cej algoritm legko realizuvati vruchnu zapovnivshi tablicyu Napriklad dlya viznachennya vidstani mizh slovami korabel i bal tablicya viglyadatime tak e t zv puste slovo bez liter e K O R A B E L e 0 1 2 3 4 5 6 7 8 tobto vidstan mizh pustim slovom i slovom KORABEL 8 dovzhina slova KORABEL B 1 1 2 3 4 4 5 6 7 mizh B i KORABEL vidstan 7 litera B v oboh slovah i mozhe buti vikoristana A 2 2 2 3 3 4 5 6 7 mizh BA i KORABEL vidstan 7 lishe odnu z liter B abo A mozhna vikoristati L 3 3 3 3 4 4 5 5 6 mizh BAL i KORABEL vidstan 6 mozhna vikoristati dvi literi B abo A L Dlya viznachennya poslidovnosti operacij neobhidnih dlya perehodu vid odnogo slova do inshogo potribno znajti najdeshevshij shlyah vid pershoyi 0 0 klitinki matrici do ostannoyi i j Yak vidno z prikladu isnuye dekilka ekvivalentnih shlyahiv i algoritm znahodit ne tilki minimalnu vidstan ale j usi shlyahi Na kozhnomu nastupnomu kroci zastosovuyetsya informaciya zdobuta na poperednomu kroci princip dinamichnogo programuvannya U PHP cej algoritm realizovano funkciyeyu levenshtein 1 Mezhi RedaguvatiDlya vidstani Levenshtejna isnuyut taki verhnya i nizhnya mezhi Distanciya Levenshtejna ne ye menshoyu za riznicyu dovzhini ryadkiv sho porivnyuyutsya Vona ne ye bilshoyu dovzhini najdovshogo ryadka Vona dorivnyuye 0 todi i tilki todi koli ryadki odnakovi odnakovi simvoli na odnakovih poziciyah Mizh vidstannyu Levenshtejna ta vidstannyu Geminga isnuyut taki vzayemozv yazki Dlya ryadkiv odnakovoyi dovzhini vidstan Levenshtejna rivna vidstani Geminga oskilki vidstan Geminga koristuyetsya lishe operaciyeyu zamini odnogo simvolu na inshij i ne dozvolyaye vstavki ta viluchennya simvoliv Yaksho ryadki riznoyi dovzhini to verhnoyu mezheyu ye vidstan Geminga plyus riznicya dovzhini ryadkivRealizaciya RedaguvatiRealizaciya optimizovanogo algoritmu poshuku vidstani Levenshtejna na movi Python 3 def levenstein s1 s2 n range 0 len s1 1 for y in range 1 len s2 1 l n n y for x in range 1 len s1 1 n append min l x 1 n 1 1 l x 1 s2 y 1 s1 x 1 and 1 or 0 return n 1 Podibni metodi RedaguvatiVidstan Gemminga Podibnist Dzharo Vinklera Vidstan Yensena Shenona Jensen Shannon distance Soundex metod Fonetichnij poshuk Zistavlyannya zi vzircem Virivnyuvannya poslidovnostejPrimitki Redaguvati levenshtein Calculate Levenshtein distance between two strings PHP Manual The PHP Group Arhiv originalu za 16 grudnya 2017 Procitovano 19 grudnya 2017 angl Posilannya RedaguvatiRizni metodi realiziciyi Arhivovano 28 chervnya 2006 u Wayback Machine Vizualizaciya algoritmu Levenshtejna Arhivovano 25 lipnya 2008 u Wayback Machine Rozrahunok vidstani mizh ryadkami Levenshtejn i Gemming Arhivovano 31 zhovtnya 2007 u Wayback Machine She odna vizualizaciya metodu Levenshtejna shvidka Arhivovano 9 lyutogo 2008 u Wayback Machine Otrimano z https uk wikipedia org w index php title Vidstan Levenshtejna amp oldid 39819963