|
|
| (не показано 39 промежуточных версий 3 участников) |
| Строка 1: |
Строка 1: |
| − | '''Расстояние Левенштейна''' (также '''редакционное расстояние''' или '''дистанция редактирования''') между двумя строками в теории информации и компьютерной лингвистике — это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.
| + | #перенаправление [[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]] |
| − | | |
| − | | |
| − | == Свойства ==
| |
| − | | |
| − | Для расстояния Левенштейна справедливы следующие утверждения:
| |
| − | * <math>\rm{d}(S_1,S_2) \ge | |S_1| - |S_2| |</math>
| |
| − | * <math>\rm{d}(S_1,S_2) \le max( |S_1| , |S_2| )</math>
| |
| − | * <math>\rm{d}(S_1,S_2) = 0 \Leftrightarrow S_1 = S_2</math>
| |
| − | где <math>\rm{d}(S_1,S_2)</math> — расстояние Левенштейна между строками <math>S_1</math> и <math>S_2</math>, а |S| - длина строки S.
| |
| − | | |
| − | == Редакционное предписание ==
| |
| − | | |
| − | ''Редакционным предписанием'' называется последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Обычно действия обозначаются так: '''D''' (англ. delete) — удалить, '''I''' (англ. insert) — вставить, '''R''' (англ. replace) — заменить, '''M''' (англ. match) — совпадение.
| |
| − | | |
| − | Например, для 2-х строк «hell123» и «hello214» можно построить следующую таблицу преобразований:
| |
| − | | |
| − | {| border="1"
| |
| − | |'''M''' ||'''M''' ||'''M''' ||'''M''' ||'''R''' ||'''M''' ||'''R''' ||'''I'''
| |
| − | |-
| |
| − | |'''h''' ||'''e''' ||'''l''' ||'''l''' ||'''1''' ||'''2''' ||'''3''' ||
| |
| − | |-
| |
| − | |'''h''' ||'''e''' ||'''l''' ||'''l''' ||'''o''' ||'''2''' ||'''1''' ||'''4'''
| |
| − |
| |
| − | |-}
| |
