В данном обзоре нам хотелось бы рассмотреть наиболее известные алгоритмы поиска. На самом деле их гораздо больше, однако многие нам показались уж слишком неоптимальными.
Данные алгоритмы ищут все вхождения подстроки в текст.
Для практических целей рекомендуются в первую очередь улучшения Боуера-Мура: Боуер-Мур-Хорспул, Быстрый поиск, Оптимальное несовпадение, Максимальный сдвиг и Турбо-БМ,а также несколько специфичные Турбо-обращение сегмента и Сдвиг-Или
В этом разделе :
8 Обозначения и определения.
Термины не обязательно запоминать: будут в алгоритме - вернетесь.
8 Краткий обзор алгоритмов
8 Алгоритм Хорспула
Этот алгоритм - некоторое упрощение стандартного Боуера - Мура.
8 Быстрый поиск
Сдвиг плохого символа, используемый в алгоритме Боуера - Мура, не очень эффективен для маленького алфавита, но, когда размер алфавита большой по сравнению с длиной образца, как это часто имеет место с таблицей ASCII и при обычном поиске в текстовом редакторе, он становится чрезвычайно полезен.
8 Алгоритм оптимального несовпадения
Этот вариант алгоритма быстрого поиска просматривает символы образца от наименее к наиболее частому. Таким образом мы сможем получать больше несовпадений.
8 Алгоритм максимального сдвига
Вариант алгоритма быстрого поиска, просматривающий символы образца от соответствующего наибольшему сдвигу к наименьшему.
8 Tурбо Боуер-Мур
Турбо - БМ является улучшением алгоритма Боуера - Мура.
8 Турбо - обращенние сегмента
Этот алгоритм является улучшением алгоритма обращенного сегмента уменьшающим наибольшее число сравнений до 2*n.
8 Алгоритм Сдвига-Или
Пусть R - битовый массив размера m. Вектор R i - значение массива R после обработки очередного символа. Он содержит информацию обо всех совпадениях префиксов х, которые кончаются на позиции i в тексте ( 0 <= j <= m - 1 ):
8 Алгоритм грубой силы
Этот алгоритм заключается в проверке всех позиций текста с 0 по n - m на предмет совпадения с началом образца.
8 Построение автомата
Cтроим автомат ( DFA ): A(x) = (Q, i, T, d).
8 Алгоритм Карпа-Рабина
Хеширование может позволить нам избежать квадратичного количества сравнений символов в обычных ситуациях.
8 Алгоритм Морриса-Пратта
Этот алгоритм появился в результате тщательного анализа алгоритма грубой силы.
8 Алгоритм Кнута-Морриса-Пратта
Этот алгоритм был получен благодаря глубокому анализу алгоритма Морриса-Пратта. Итак, посмотрим, что еще можно сделать, чтобы увеличить размер сдвига.
8 `Не такой уж наивный` алгоритм
8 Алгоритм Боуера-Мура
Один из наиболее известных и, эффективных ( Это особенно касается его дальнейших улучшений ) для ОБЫЧНЫХ ПРИЛОЖЕНИЙ ( то есть редакторов текста, например ) алгоритму.
8 Алгоритм обращения сегмента
Данный алгоритм имеет квадратичный худший случай, однако в среднем оптимален.
| |
*
Обратная связь