Анализ строк

Description

Классическое пособие для решения задач, встающих при обработке строк.В этой работе рассматриваются задачи анализа строк, возникающие при разработке систем обработки текстовой информации. Не ставятся целью дать точные решения всех возможных задач, а предлагаются детальные обзоры существующих алгоритмов, подходящих для подобных систем.Термин анализ строк используется здесь в довольно общем смысле и обозначает целый класс задач – таких, как локализация заданных подстрок, выделение длиннейших совпадающих подстрок двух строк, вычисление расстояния между двумя строками и т.д.Прежде всего совсем общо описывается проблема, затем приводятся точные формулировки.Обсуждаются алгоритмы анализа строк, сравниваются их возможности и эффективность. После этого идет описание основных алгоритмов.Алгоритмы: - Поиск образцов - Наивный подход - Кнут-Моррис-Пратт - Бойер-Мур - Бойер-Мур-Хорспул - Сандей: Быстрый поиск, Максимальный сдвиг, Оптимальное несовпадение - Хьюм и Сандей. Улучшенные алгоритмы Бойера-Мура и Наименьшая цена - Харрисон - Карп-Рабин - Расстояние между строками и самая длинная общая подпоследовательность - Вагнер-Фишер - Хиршберг - Хант-Шиманский - Машек-Патерсон - Укконен - Самая тяжелая общая подпоследовательность - Нечеткое сопоставление строк - k несовпадений - Ландау-Вишкин - k различий - Ландау-Вишкин - Самая длинная повторяющася подстрока - Суффиксные деревья