Учебное пособие (1077022), страница 26
Текст из файла (страница 26)
Для ее решения предлагались различные методы, напримерразбиение слов на два или три символа с их комбинаторным перебором.Но все они оказались мало эффективны.10.1 Расстояние Дамерау-ЛевенштейнаЭффективныйспособрешенияданнойзадачипредложилотечественный исследователь – Владимир Иосифович Левенштейн.Теоретические выкладки данного раздела основаны на источнике [4].209Вычисление расстояния Левенштейна (редакционного расстояния)основанонапонятииредакционногопредписания.Редакционнымпредписанием называется последовательность действий, необходимых дляполучения из первой строки второй кратчайшим образом.
Обычнодействия обозначаются так: D (англ. delete) — удалить, I (insert) — добавить, R (replace) — заменить, M (match) — совпадение.Пример редакционного предписания представлен на рис. 25:ДействиеM M IR M M R DИсходное словоП РИ М ЕРезультатП РЕ Д М ЕР ЫТРис. 25. Пример редакционного предписания.Для преобразования слова «ПРИМЕРЫ» в слово «ПРЕДМЕТ»необходимо выполнить 4 действия (добавление, удаление и две замены).Расстоянием Левенштейна называется минимальное количестводействий, необходимых для преобразования одного слова в другое.
В этомпримере расстояние Левенштейна равно 4.Преобразовать одно слово в другое можно различными способами,количество действий также может быть разным. Поэтому при вычислениирасстояния и выбирается минимальное количество действий.Если поиск производится в тексте, который набирается на клавиатуре,то вместо расстояния Левенштейна используют усовершенствованноерасстояниеДамерау-Левенштейна.ФредерикДамерау–одинизамериканских пионеров-исследователей в области обработки текстов наестественном языке.
Исследования Дамерау показали, что наиболее частойошибкой при наборе слова является перестановка двух соседних букв –210транспозиция, которая обозначается как T (transposition). Данное действиепринято называть поправкой Дамерау к расстоянию Левенштейна.В случае одной транспозиции расстояние Левенштейна равняетсядвум (две замены символа). При использовании поправки Дамераутранспозиция считается как единичное расстояние (рис.
26).Действие(расстояниеДамерау- M MTM М МЛевенштейна)Действие (расстояние Левенштейна)M M R R M М МИсходное словоП РИ М ЕРЫРезультатП РМ И ЕРЫРис. 26. Транспозиция при вычислении расстояний Левенштейна и ДамерауЛевенштейна.При использовании расстояния Дамерау-Левенштейна за единичноерасстояние принимаются следующие действия: I (insert) — добавление символа. D (delete) — удаление символа. R (replace) — замена символа. T (transposition) — перестановка двух соседних символов.10.2 Вычисление расстояния Дамерау-ЛевенштейнаПусть заданы строка S1 длиной M символов и строка S2 длиной Nсимволов.
Предполагается, что строка S1 длиннее или равна по длинестроке S2 ( ≥ ).Для вычисления расстояния Левенштейна необходимо рекуррентновычислить значения элементов матрицы [, ] размером × . Значениев правом нижнем элементе [, ] и будет являться расстояниемЛевенштейна.Расстояние Левенштейна (1 , 2 ) вычисляется на основе формулы1:211(1 , 2 ) = [, ], где0; = 0, = 0(случай 1); > 0, = 0(случай 2); = 0, > 0(случай 3)[, ] =(1)min([ − 1, ] + 1, (утверждение 1)[, − 1] + 1, (утверждение 2)[ − 1, − 1] + (1 [], 2 []) (утверждение 3); > 0, > 0(случай 4){ )Выражение m(символ1, символ2) равняется нулю, если символысовпадают и единице, если символы не совпадают (проверяется равенствоi-го символа из первой строки и j-го символа из второй строки).Рассмотрим формулу более подробно в соответствии с [4], где D(i, j) –расстояние между префиксами строк: первыми i символами строки S 1 ипервыми j символами строки S2.Редакционное расстояние между двумя пустыми строками равно нулю(случай 1).Для получения пустой строки из строки длиной i, нужно совершить iопераций удаления (случай 2).Чтобы получить строку длиной j из пустой строки, нужно провести jопераций вставки (случай 3).В случае 4 обе строки непусты.
В оптимальной последовательностиопераций, операции можно произвольно менять местами. Рассмотрим двепоследовательные операции: Две замены одного и того же символа – неоптимально (еслимы заменили x на y, потом y на z, выгоднее было сразузаменить x на z). Две замены разных символов можно менять местами.212 Два удаления или два добавления можно менять местами. Добавление символа с его последующим удалением –неоптимально (можно отменить оба действия). Удаление и добавление разных символов можно менятьместами. Добавлениесимволасегопоследующейзаменой–неоптимально (излишняя замена). Добавление символа и замена другого символа меняютсяместами. Замена символа с его последующим удалением – неоптимально (излишняя замена). Удаление символа и замена другого символа меняютсяместами.Пускай S1 заканчивается на символ «a», S2 заканчивается на символ«b».Тогдавыполняетсяодноизследующихутверждений(соответствующих утверждениям 1-3 в формуле 1):1.
Символ «а», на который кончается S1, в какой-то момент былудален. Сделаем это удаление первой операцией. Тогда мыудалили символ «a», после чего превратили первые i−1 символовS1 в S2 (на это потребовалось [ − 1, ] операций), значит, всегопотребовалось [ − 1, ] + 1 операций.2. Символ «b», на который кончается S2, в какой-то момент былдобавлен. Сделаем это добавление последней операцией. Мыпревратили S1 в первые j−1 символов S2, после чего добавили «b».Аналогично предыдущему случаю, потребовалось [, − 1] + 1операций.3.
Оба предыдущих утверждения неверны. Если мы добавлялисимволы справа от «a», то чтобы сделать последним символом«b», мы должны были или в какой-то момент добавить его (но213тогда утверждение 2 было бы верно), либо заменить на него одиниз этих добавленных символов (что тоже невозможно, потому чтодобавление символа с его последующей заменой не оптимально).Значит, символов справа от финального «a» мы не добавляли.Самого финального «a» мы не удаляли, поскольку утверждение 1неверно.
Значит, единственный способ изменения последнегосимвола – его замена. Заменять его 2 или больше разнеоптимально. Следовательно, возможны два варианта:3.1.Если «a» совпадает с «b», мы последний символ не меняли.Поскольку мы его также не стирали и не приписывали ничегосправа от него, он не влиял на наши действия, и, значит, мывыполнили [ − 1, − 1] операций, (1 [], 2 []) = 0.3.2.Если «a» не совпадает с «b», мы последний символ менялиодин раз. Сделаем эту замену первой.
В дальнейшем, аналогичнопредыдущему случаю, мы должны выполнить [ − 1, − 1]операций, значит, всего потребуется [ − 1, − 1] + 1 операций,(1 [], 2 []) = 1.ПосколькурасстояниеЛевенштейнаопределяетминимальноеколичество действий, то берется минимум из утверждений 1-3.Если вычисляется расстояние Дамерау-Левенштейна (транспозициясчитается единичным расстоянием), то на основе вычисленных элементовматрицы [, ] вычисляются элементы матрицы [, ] (формула 2).min([, ] =){; Если выполняются[, ] (расстояние Левенштейна) условия > 1, > 1,[ − 2, − 2] + (1 [], 2 [])1 [] = 2 [ − 1],(транспозиция)1 [ − 1] = 2 [][, ](2); Если условияне выполняютсяЗначение в правом нижнем элементе [, ] и будет являтьсярасстоянием Дамерау-Левенштейна.21410.3 ПримервычислениярасстоянияДамерау-ЛевенштейнаДопустим, что при вводе в справочник информационной системыоператор допустил ряд ошибок при вводе фамилии ИВАНОВ:1.
Добавление (I) буквы Н в середине слова – ИВАННОВ.2. Удаление (D) буквы И в начале слова – ВАННОВ.3. Замена (R) буквы В на Б – БАННОВ.4. Перестановка (T) букв В и О – БАННВО.Так как каждое действие увеличивает расстояние на 1, то итоговоерасстояние Дамерау-Левенштейна равно 4.Пример вычисление расстояния с помощью матрицы DT[i,j] приведенна рис. 27.ИВАНОВ0123456Б1123456А2222345Н3333234Н4444334В5545443О6655544Рис. 27. Пример вычисления расстояния Дамерау-Левенштейна.В правой нижней ячейке матрицы находится вычисленное расстояние– число 4.Таким образом, использование расстояния Дамерау-Левенштейнапозволяет находить слово даже при большом количестве опечаток.21510.4 Алгоритм Вагнера-Фишера вычисления расстоянияДамерау-ЛевенштейнаСуществуетнесколькоалгоритмоввычислениярасстоянияЛевенштейна и Дамерау-Левенштейна.Алгоритм Вагнера-Фишера – это наиболее простой алгоритм, которыйвычисляет расстояние Дамерау-Левенштейна на основе определения(формула 2).Недостатками алгоритма являются невысокая скорость работы ибольшие затраты памяти.Временная сложность алгоритма ( × ), где и – длины строк.То есть время выполнения алгоритма прямо пропорционально количествуячеек в матрице .Рассмотрим реализацию алгоритма на языке C# в соответствии сфрагментами примера 16:/// <summary>/// Вычисление расстояния Дамерау-Левенштейна/// </summary>public static int Distance(string str1Param, string str2Param){if ((str1Param == null) || (str2Param == null)) return -1;int str1Len = str1Param.Length;int str2Len = str2Param.Length;//Если хотя бы одна строка пустая,//возвращается длина другой строкиif ((str1Len == 0) && (str2Len == 0)) return 0;if (str1Len == 0) return str2Len;if (str2Len == 0) return str1Len;//Приведение строк к верхнему региструstring str1 = str1Param.ToUpper();string str2 = str2Param.ToUpper();//Объявление матрицыint[,] matrix = new int[str1Len + 1, str2Len + 1];//Инициализация нулевой строки и нулевого столбца матрицыfor (int i = 0; i <= str1Len; i++) matrix[i, 0] = i;216for (int j = 0; j <= str2Len; j++) matrix[0, j] = j;//Вычисление расстояния Дамерау-Левенштейнаfor (int i = 1; i <= str1Len; i++){for (int j = 1; j <= str2Len; j++){//Эквивалентность символов, переменная symbEqual//соответствует m(s1[i],s2[j])int symbEqual = ((str1.Substring(i - 1, 1) ==str2.Substring(j - 1, 1)) ? 0 : 1);int ins = matrix[i, j - 1] + 1; //Добавлениеint del = matrix[i - 1, j] + 1; //Удалениеint subst = matrix[i - 1, j - 1] + symbEqual; //Замена//Элемент матрицы вычисляется//как минимальный из трех случаевmatrix[i, j] = Math.Min(Math.Min(ins, del), subst);//Дополнение Дамерау по перестановке соседних символовif ((i > 1) && (j > 1) &&(str1.Substring(i - 1, 1) == str2.Substring(j - 2, 1)) &&(str1.Substring(i - 2, 1) == str2.Substring(j - 1, 1))){matrix[i, j] = Math.Min(matrix[i, j],matrix[i - 2, j - 2] + symbEqual);}}}//Возвращается нижний правый элемент матрицыreturn matrix[str1Len, str2Len];}Функция Distance принимает на вход две строки, вычисляет значенияматрицы и возвращает значение нижнего правого элемента матрицы.ВспомогательнаяфункцияWriteDistanceвыводитвконсольрезультаты вычисления расстояния Дамерау-Левенштейна:/// <summary>/// Вывод расстояния Дамерау-Левенштейна в консоль/// </summary>public static void WriteDistance(string str1Param, string str2Param){int d = Distance(str1Param, str2Param);Console.WriteLine("'" + str1Param + "','" +str2Param + "' -> " + d.ToString());}217Пример вычисления расстояния:Console.WriteLine("Добавление одного символа в начало, середину иконец строки");EditDistance.WriteDistance("пример","1пример");EditDistance.WriteDistance("пример", "при1мер");EditDistance.WriteDistance("пример", "пример1");Console.WriteLine("Добавление двух символов в начало, середину иконец строки");EditDistance.WriteDistance("пример", "12пример");EditDistance.WriteDistance("пример", "при12мер");EditDistance.WriteDistance("пример", "пример12");Console.WriteLine("Добавление трех символов");EditDistance.WriteDistance("пример", "1при2мер3");Console.WriteLine("Транспозиция");EditDistance.WriteDistance("прИМер", "прМИер");Console.WriteLine("Рассмотренный ранее пример");EditDistance.WriteDistance("ИВАНОВ", "БАННВО");Результаты вывода в консоль:Добавление одного символа в начало, середину и конец строки'пример','1пример' -> 1'пример','при1мер' -> 1'пример','пример1' -> 1Добавление двух символов в начало, середину и конец строки'пример','12пример' -> 2'пример','при12мер' -> 2'пример','пример12' -> 2Добавление трех символов'пример','1при2мер3' -> 3Транспозиция'прИМер','прМИер' -> 1Рассмотренный ранее пример'ИВАНОВ','БАННВО' -> 410.5 Контрольные вопросы к разделу 101.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
