Алгоритм Бойера-Мура — различия между версиями
Kabanov (обсуждение | вклад) |
Kabanov (обсуждение | вклад) м |
||
| Строка 1: | Строка 1: | ||
| − | Алгоритм Бойера-Мура, разработанный двумя учеными – Бойером (Robert S. Boyer) и Муром (J. Strother Moore), считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. | + | Алгоритм Бойера-Мура, разработанный двумя учеными – Бойером (Robert S. Boyer) и Муром (J. Strother Moore), считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Важной особенностью алгоритма является то, что он выполняет сравнения справа налево в отличии от многих других алгоритмов. |
| − | Важной особенностью алгоритма является то, что он выполняет сравнения справа налево в отличии от многих других алгоритмов. | + | |
| + | Алгоритм Бойера-Мура считается наиболее эффективным алгоритмом поиска шаблонов в стандартных приложениях и командах, таких как Ctrl+F в браузерах и текстовых редакторах. | ||
Алгоритм сканирует символы шаблона справа налево, начиная с самого правого, один за другим. В случае несовпадения какого-либо символа (или полного совпадения всего шаблона) он использует две предварительно вычисляемых функций, чтобы сдвинуть позицию для начала сравнения вправо. | Алгоритм сканирует символы шаблона справа налево, начиная с самого правого, один за другим. В случае несовпадения какого-либо символа (или полного совпадения всего шаблона) он использует две предварительно вычисляемых функций, чтобы сдвинуть позицию для начала сравнения вправо. | ||
| − | |||
| − | |||
==Асимптотики== | ==Асимптотики== | ||
| Строка 19: | Строка 18: | ||
==Алгоритм== | ==Алгоритм== | ||
| + | Предположим, что возникает несовпадение между символом <tex>x[i]=a</tex> шаблона и символом <tex>y[i+j]=b</tex> исходного текста при проверке в позиции <tex>j</tex>. Тогда <tex>x[i+1 .. m-1]=y[i+j+1 .. j+m-1]=u</tex> и <tex>x[i] \neq y[i+j]</tex> | ||
==Псевдо-код== | ==Псевдо-код== | ||
Версия 16:53, 9 мая 2014
Алгоритм Бойера-Мура, разработанный двумя учеными – Бойером (Robert S. Boyer) и Муром (J. Strother Moore), считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Важной особенностью алгоритма является то, что он выполняет сравнения справа налево в отличии от многих других алгоритмов.
Алгоритм Бойера-Мура считается наиболее эффективным алгоритмом поиска шаблонов в стандартных приложениях и командах, таких как Ctrl+F в браузерах и текстовых редакторах.
Алгоритм сканирует символы шаблона справа налево, начиная с самого правого, один за другим. В случае несовпадения какого-либо символа (или полного совпадения всего шаблона) он использует две предварительно вычисляемых функций, чтобы сдвинуть позицию для начала сравнения вправо.
Содержание
Асимптотики
Фаза предварительных вычислений требует времени и памяти В худшем случае поиск требует сравнений. В лучшем случае требует сравнений.
В 1991 году Р.Коул доказал следующую теорему:
| Теорема (Richard Cole): |
В худшем случае требуется сравнений в случае шаблона с периодом равным длине самого шаблона. |
| Доказательство: |
| Доказательство [1] |
Алгоритм
Предположим, что возникает несовпадение между символом шаблона и символом исходного текста при проверке в позиции . Тогда и
