4551
правка
Последовательное точное сравнение строк: различия между версиями
Перейти к навигации
Перейти к поиску
Последовательное точное сравнение строк (посмотреть исходный код)
Версия от 15:58, 25 апреля 2019
, 25 апреля 2019→Основные результаты
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 44: | Строка 44: | ||
[https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D0%B9%D0%B5%D1%80%D0%B0_%E2%80%94_%D0%9C%D1%83%D1%80%D0%B0| Алгоритм Бойера-Мура] считается одним из самых эффективных алгоритмов решения задачи ESM. Его упрощенная версия либо весь алгоритм полностью нередко применяется в программах редактирования текстов для выполнения операций поиска и замены. | [https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D0%B9%D0%B5%D1%80%D0%B0_%E2%80%94_%D0%9C%D1%83%D1%80%D0%B0| Алгоритм Бойера-Мура] считается одним из самых эффективных алгоритмов решения задачи ESM. Его упрощенная версия либо весь алгоритм полностью нередко применяется в программах редактирования текстов для выполнения операций поиска и замены. | ||
Алгоритм сканирует символы в окне справа налево, начиная с самого правого символа. В случае несовпадения (либо полного совпадения с шаблоном) он использует две предварительно вычисляемые функции для сдвига шаблона вправо. Эти две функции сдвига носят название сдвига плохого символа и сдвига хорошего суффикса. Они основаны на следующих наблюдениях. Предположим, что несовпадение обнаруживается между символом pi = a шаблона и символом ti+j = b текста после попытки в позиции j. Тогда pi+1 … pm = ti+j+1 … tj+m = u и pi ф ti+j. Сдвиг хорошего суффикса заключается в выравнивании сегмента ti+j+1 … tj+m с его самым правым вхождением в P, предшествующим символу, отличному от pi. Еще один вариант сдвига хорошего суффикса заключается в выравнивании сегмента ti+j … tj+m с его самым правым вхождением в P. Вычисление обоих вариантов требует O(m) времени и памяти, независимо от размера алфавита. Если такого сегмента не существует, сдвиг заключается в выравнивании самого длинного суффикса v строки ti+j+1 … tj+m с совпадающим префиксом x. Сдвиг плохого символа заключается в выравнивании символа текста ti+j с его самым правым вхождением в p1 … pm-\-. Если ti+j не встречается в шаблоне и никакое вхождение P в T не перекрывает символ ti+j, тогда левый конец шаблона выравнивается с символом в позиции i + j + 1. В этом случае поиск может быть выполнен за время O(n/m) в наилучшем случае. | |||
Теорема 5 (Коул, 1994 [5, 14]). В ходе поиска непериодического шаблона P длины m (такой, что длина самой длинной границы P меньше m/2) в тексте T длины n алгоритм Бойера-Мура производит не более 3n сравнений между буквами P и T. | |||
Граница Яо может быть достигнута благодаря использованию индексной структуры для реверсивного шаблона. Это выполняется при помощи алгоритма обращения сегмента (Reverse Factor), также известного как BDM (Backward Dawg Matching, сопоставление с обращенным ОАГС). | |||
Теорема 6 (Крочмор и др., 1994 [ ]). Поиск может быть выполнен за оптимальное ожидаемое время O((log m/m) x n) с использованием суффиксного конечного автомата или суффиксного дерева реверсивного шаблона. | |||
Вместо индексной структуры может использоваться фактор-оракул, поскольку единственной строкой длины m, принимаемая оракулом строки w длины m, является сама строка w. Это выполняется при помощи алгоритма сопоставления с обращенным оракулом (Backward Oracle Matching, BOM) Аллозена, Крочмора и Раффино [ ]. На практике его поведение схоже с поведением алгоритма BDM. | |||
'''Алгоритмы, оптимальные по времени и памяти''' | |||
Алгоритмы этого типа выполняются за линейное время (это относится к предварительной обработке и поиску) и требуют константного объема памяти в дополнение к объему входных данных. | |||
Теорема 7 (Галил, Сейферас, 1983 [ ])). Поиск может быть выполнен оптимальным образом за время O(n) с использованием константного объема памяти. | |||
После первого решения Галила и Сейфераса другие варианты были предложены Крочмором и Перреном [ ] и Риттером [ ]. Алгоритмы разбивают шаблон на две части; вначале они выполняют поиск правой части шаблона слева направо, а затем, если не обнаружено несовпадений, ищут левую часть. Разбиение может представлять собой идеальную факторизацию [8] или критическую факторизацию [ ] лабо основываться на лексикографически максимальном суффиксе шаблона [ ]. Еще одно решение Крочмора [ ] представляет собой вариант KMP [ ]: оно на лету вычисляет нижние границы периодов префиксов шаблона и не требует предварительной обработки. | |||
'''Бит-параллельное решение''' | |||
Для решения задачи ESM можно применить технику битового параллелизма. | |||