нштейна .
Відстань Хеммінга - число позицій, в яких відповідні символи двох слів однакової довжини різні. У більш загальному випадку відстань Хеммінга застосовується для рядків однакової довжини будь-яких q -ічних алфавітів і служить метрикою відмінності (функцією, визначальною відстань у метричному просторі) об'єктів однакової розмірності.
Спочатку метрика була сформульована Річардом Хеммінга під час його роботи в Bell Labs для визначення міри відмінності між кодовими комбінаціями (двійковими векторами) у векторному просторі кодових послідовностей, в цьому випадку відстанню Хеммінга d ( x , y ) між двома двійковими послідовностями (векторами) x і y довжини n називається число позицій, в яких вони різні - у такому формулюванні відстань Хеммінга увійшло до словника алгоритмів і структур даних національного інституту стандартів і технологій США (англ. NIST Dictionary of Algorithms and Data Structures ). При цьому відстань Хемінга є метрикою тільки на безлічі слів однакової довжини, що сильно обмежує область його застосування.
Втім, на практиці відстань Хемінга виявляється практично марним, поступаючись більш природним з точки зору людини метрикам. Однією з таких метрик є відстань Левенштейна (також редакційне відстань або дистанція редагування). Відстань Левенштейна - це мінімальна кількість операцій вставки одного символа, видалення одного символу і заміни одного символу на інший, необхідних для перетворення одного рядка в іншу. p align="justify"> Вперше задачу згадав в 1965 році радянський математик Володимир Йосипович Левенштейн при вивченні послідовностей 0 - 1. Згодом більш загальну задачу для довільного алфавіту зв'язали з його ім'ям. Великий внесок у вивчення питання вніс Гасфілд. p align="justify"> Далі вважається, що елементи рядків нумеруються з першого, як прийнято в математиці, а не з нульового, як прийнято в мови програмування.
В
Крок за i символізує видалення з першого рядка, по j вставку в перший рядок, а крок за обома індексами символізує заміну символу або відсутність змін.
Весь процес можна наступній матрицею:
В
Рис. 5. Матриця кількості перетворень одного слова в інше
Як видно з матриці, зі слова В«арештантВ» вийде слово В«дагестанВ» всього за три операції вставки, видалення, заміщення.
Використовуючи д...
