 |
|
Сортировка Защита и сокрытие информации. Атаки и взлом Сжатие информации и кодирование. С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) |
Очень быстрый алгоритм для обычных текстов и поиска. Большой объем предварительных вычислений. |
Вверх по странице, к оглавлению и навигации