Боуер
Cтраница 1
 |
Прибор для прямого фторирования. [1] |
Боуера и Кука [2] со специальной насадкой. [2]
Анализ поиска по Боуеру и Муру, В первоначальной публикации [1.9] алгоритма приводится детальный анализ его производительности. [3]
Ниже приводится программа с упрощенной стратегией Боуера - Мура, построенная так же, как и предыдущая программа с КМП-алгоритмом. [4]
Остроумная схема КМП-поиска дает подлинный выигрыш только тогда, когда неудаче предшествовало некоторое число совпадений. Лишь в этом случае образ сдвигается более чем на единицу. К несчастью, это скорее исключение, чем правило: совпадения встречаются значительно реже, чем несовпадения. Поэтому выигрыш от использования КМП-стратегии в большинстве случаев поиска в обычных текстах весьма незначителен. Метод же, о котором сейчас пойдет речь, в действительности не только улучшает обработку самого плохого случая, но дает выигрыш в промежуточных ситуациях. Мур приблизительно в 1975 г; мы будем называть его БМ-поиском. Вначале мы дадим упрощенную версию этого алгоритма, а затем перейдем к той, которую приводят Боуер и Мур. [5]
Страницы: 1