 |
Сортировка Защита и сокрытие информации. Атаки и взлом Сжатие информации и кодирование. СRC Графика и обработка изображений. Фракталы Поиск в строках, массивах,последовательностях
Разбор выражений.Компиляторы и интерпретаторы
Cтруктуры данных.Хранение информации
AI, ГА, Нейронные сети Вейвлеты Игры, и все с ними связанное Олимпиадные задачи РазноеСофт: просмотр PS и PDF файлов
Написать веб-мастеру
Почитать историю сайта
Поиск в строках, массивах, последовательностях:
Точный поиск подстроки в строке.
В данном обзоре мне хотелось бы рассмотреть наиболее известные алгоритмы поиска. На самом деле их гораздо больше, однако многие мне показались уж слишком неоптимальными.Описание алгоритмов я перевел, взяв статью 'EXACT STRING MATCHING ALGORITHMS' авторов Christian Charras - Thierry Lecroq.
Оригинал статьи находится на http://www-igm.univ-mlv.fr/~lecroq/string/index.html
Данные алгоритмы ищут все вхождения подстроки в текст.
Для практических целей рекомендуются в первую очередь улучшения Боуера-Мура:
Боуер-Мур-Хорспул, Быстрый поиск, Оптимальное несовпадение, Максимальный сдвиг и Турбо-БМ,
а также несколько специфичные Турбо-обращение сегмента и Сдвиг-Или.
Обозначения и определения.
Термины не обязательно запоминать: будут в алгоритме - вернетесь.
Искомый образец - строка x = x [ 0 ... m - 1 ]; его длина m.Текст - строка y = y [ 0 ... n - 1 ]; его длина n.
Алфавит ( множество символов, из которых составлены текст и образец ) - S, в нем s символов.
Слово u - префикс cлова w, если существует слово v : w = uv.
Слово v - суффикс cлова w, если существует слово u : w = uv.
Слово z - подстрока слова w, если существуют u и v : w = uzv.
Слово u - период слова w, если w - префикс слова uk для целого k. Наименьший период мы далее и будем называть периодом и обозначать per(w).
Cлово w длины l - периодичное, если длина per(w) <= l/2, в противном случае оно непериодичное.
Слово называется фундаментальным, если оно не может быть записано в виде степени другого слова, то есть не существует z : w = zl.
Cлово z - граница слова w, если существуют u и w : w = uz = zv, z - одновременно префикс и суффикс w.
Обращение слова w длины l обозначается wR - зеркальный образ w; wR = w[ l-1 ]w[ l-2 ] ... w[1]w[0].
В программах будут использованы следующие функции и константы:
константа ASIZE - размер алфавита,
константа WORD - размер компьютерного слова в битах, обычно 16
константа XSIZE - размер образца,
функция ERROR сообщает об ошибке,
функции MIN / MAX - минимум / максимум,
функция OUTPUT возвращает позицию начала совпадения относительно начала текста.
В остальном же все, я надеюсь, следует стандарту Aнси - Си.
Алгоритмы.
Алгоритм |
Время на пред. обработку |
Среднее время поиска |
Худшее время поиска |
Затраты памяти |
Примечания |
Нет |
2*n |
O(n*m) |
Нет |
Mалые трудозатраты на программу |
|
O(s+m) |
O(n) |
O(n) |
O(s*m) |
- |
|
Нет |
O(n+m) |
O(n*m) |
Нет |
- |
|
O(s+m) |
O(n) |
O(n) |
- |
Хорош, если длина |
|
O(m) |
O(n+m) |
O(n+m) |
O(m) |
- |
|
O(m) |
O(n+m) |
O(n+m) |
O(m) |
- |
|
O(1) |
O(n+m) |
O(n*m) |
O(1) |
Время и место для |
|
O(m+s) |
O(n+m) |
O(n*m) |
O(m+s) |
Алгоритмы этой группы наиболее эффективны в обычных ситуациях. Быстродействие повышается при увеличении образца или алфавита. |
|
O(m+s) |
O(n+m) |
2*n |
O(m+s) |
Улучшение предыдущего алгоритма. |
|
O(m+s) |
O(n+m) |
O(n*m) |
O(m+s) |
Легок в реализации. Так же эффективен, как и БМ. |
|
O(m+s) |
O(n+m) |
O(n*m) |
O(m+s) |
Очень быстрый алгоритм для обычных текстов и поиска. Эффективность падает с увеличением длины образца, но возрастает - с увеличением алфавита. |
|
O ( m ) |
O(n(logsm)/m) |
O(n*m) |
O ( m ) |
- |
|
O ( m ) |
O(n(logsm)/m) |
2n |
O ( m ) |
маленький алфавит и длинный образец |
|
O(m+s) |
O(n+m) |
O(n*m) |
O(m+s) |
Очень быстрый алгоритм для обычных текстов и поиска. Большой объем предварительных вычислений. |
|
O(m+s) |
O(n+m) |
O(n*m) |
O(m+s) |
Очень быстрый алгоритм для обычных текстов и поиска. Большой объем предварительных вычислений. |
Вверх по странице, к оглавлению и навигации