Редакционное предписание как последовательность действий, необходимых для получения из первой строки второй кратчайшим образом. Алгоритмы Вагнера–Фишера, Хиршберга, Bitap: их структура, редакционное предписание, анализ, основная задача и применение.
1. Алгоритм Вагнера-Фишера 1.1 Редакционное предписание 1.2 Разные цены операций и транспозиция 1.3 Структура алгоритма Вагнера-Фишера 2. Нечёткий поиск 3.1 Алгоритмы нечёткого поиска без индексации 3.2 Алгоритм Bitap 3.3 Алгоритм расширения выборки Заключение Список использованных источников Введение Очень часто мы сравниваем, две строки по принципу равны/не равны, и искать строку в подстроке. Редакционное расстояние (также расстояние Левенштейна или дистанция редактирования) между двумя строками в теории информации и компьютерной лингвистике - это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую. Расстояние Левенштейна определяет, сколько раз надо добавить/удалить/заменить символ, чтобы одну строку превратить в другую. Обычно действия обозначаются так: D (англ. delete) - удалить, I (англ. insert) - вставить, R (replace) - заменить, M (match) - совпадение. Пусть S1 и S2 - две строки (длиной M и N соответственно) над некоторым алфавитом, тогда редакционное расстояние d(S1,S2).
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
