Исследование алгоритмов расчета редакционного расстояния

Дипломная работа - Компьютеры, программирование

Другие дипломы по предмету Компьютеры, программирование



Но уже при k = 2 размер такого множества будет составлять более 115 тысяч вариантов, что соответствует полному перебору небольшого словаря, либо, же 1 / 27 в нашем случае, и, следовательно, время работы будет достаточно велико. При этом не нужно забывать еще и о том, что для каждого из таких слов необходимо провести поиск на точное совпадение в словаре.

Особенности: алгоритм может быть легко модифицирован для генерации ошибочных вариантов по произвольным правилам, и, к тому же, не требует никакой предварительной обработки словаря, и, соответственно, дополнительной памяти.

Возможные улучшения: можно генерировать не всё множество ошибочных слов, а только те из них, которые наиболее вероятно могут встретиться в реальной ситуации, например, слова с учетом распространенных орфографических ошибок или ошибок набора.

Заключение

Результатом написания данной курсовой работы стала программная реализация одного из алгоритмов расчета редакционного расстояния или расстояния Левенштейна.

Данные алгоритмы широко применяются в программных средствах интернет - ресурсов, различных видах символьного поиска, а также в коррекции текста и обнаружения в нем ошибок.

Основной задачей при совершенствовании подобных алгоритмов является уменьшение ресурсоёмкости программного обеспечения, что зачастую сказывается на скорости расчета редакционного расстояния. Именно так были созданы алгоритмы нечёткого поиска. Это и является основным недостатком алгоритмов расчета расстояния Левенштейна.

В своей реализации подобного алгоритма я взял алгоритм Вагнера-Фишера.

алгоритм редакционное предписание

Список использованных источников

1. В.И. Левенштейн. Двоичные коды с исправлением выпадений, вставок и замещений символов. Доклады Академий Наук СССР, 1965

. В.И. Левенштейн, Об одном классе систематических кодов, Докл. АН СССР, 131, 5, 1960, 1011-1014

. В.И. Левенштейн, О некоторых свойствах кодовых систем, Докл. АН СССР, 140, 6, 1961, 1274-1277

. В.И. Левенштейн, Двоичные коды с исправлением выпадений, вставок и замещений символов, Докл. АН СССР, 163, 4, 1965, 845-848

. Гасфилд. Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология. Невский Диалект БВХ - Петербург, 2003

. Блейхут Р.Теория и практика кодов, контролирующих ошибки (Theory and Practice of Error Control Codes) - М.: Мир, 1986

. Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Радио и связь, 1979

8. Морелос-Сарагоса Р. . - М.: Техносфера, 2006

. Романовский И.В. Дискретный анализ, Москва, 2005

. Р. Лоуренс, Роберт А. Вагнер, Проблемы коррекции при расширении строка - в - строку, JACM, 1975

. Б.Д. Ооммен, Р.К.С. Лок, Распознавание строки с заменой, вставкой, удалением и обобщенной перестановкой