Анализ алгоритмов быстрого поиска в словаре

1.6. 2-3-деревья.
2-3-дерево представляет собой дерево, которое может иметь узлы двух видов — 2-узлы и 3-узлы. 2-узел содержит единственный ключ К и имеет два потомка: левый дочерний узел служит корнем поддерева, все ключи в котором меньше К, а правый — корнем поддерева, все ключи в котором больше К. (Другими словами, 2-узел точно такой же, как и узел в классическом бинарном дереве поиска.) 3-узел содержит два упорядоченных ключа и { < ) и имеет три дочерних узла. Левый дочерний узел служит корнем поддерева, ключи в котором меньше , средний — корнем поддерева, ключи в котором больше и меньше , а правый — корнем поддерева, все ключи в котором больше .
Поиск заданного ключа К в 2-3-дереве достаточно прост. Он начинается с корня. Если корень представляет собой 2-узел, то мы действуем так же, как и в случае бинарного дерева поиска, — либо прекращаем поиск, если значение К равно значению ключа корня, либо продолжаем поиск в левом или правом поддереве, в зависимости от того, меньше ли значение К, чем ключ корня, или больше. Если же корень представляет собой 3-узел, то после не более чем двух сравнений мы знаем, следует ли прекратить поиск (если К равно одному из ключей 3-узла) или в каком из трех поддеревьев он должен быть продолжен.
В рассмотренном алгоритме эффективность поиска как в наихудшем, так и в среднее случае — O(logn).


1.7. Алгоритм Хорспула.
Процедура алгоритма очень простая. Сначала строится таблица смещений для каждого символа. Затем исходная строка и шаблон совмещаются по началу, сравнение ведется по последнему символу. Если последние символы совпадают, то сравнение идет по предпоследнему символу и так далее. Если же символы не совпали, то шаблон смещается вправо, на число позиций взятое из таблицы смещений для символа из исходной строки, и тогда снова сравниваются последние символы исходной строки и шаблона. И так далее, пока не шаблон полностью не совпадет с подстрокой исходной строки, или не будет достигнут конец строки.
Таблица смещений строится по принципу «пропускать столько символов, сколько возможно, но не более этого». Например, если на каком-то шаге алгоритма последние символы не совпали, и символ, находящийся в исходной строке не присутствует в шаблоне вообще, то понятно, что можно сдвинуться вправо на полную длину шаблона, без каких-либо опасений. В общем случае, каждому символу ставится в соответствие величина, равная разности длины шаблона и порядкового номера символа (если символ повторяется, то берется самое правое вхождение). Ясно, что эта величина будет в точности равна порядковому номеру символа, если считать от конца строки, что и дает возможность смещаться вправо на максимально возможное число позиций.
Далее представлен псевдокод заполнения таблицы сдвигов:

А так же псевдокод самого алгоритма Хорспула:

На простом примере можно продемонстрировать, что эффективность алгоритма Хорспула в наихудшем случае составляет в O(nm). Однако для случайных текстов эффективность алгоритма Хорспула равна O(n). Таким образом, хотя алгоритм Хорспула принадлежит к тому же классу эффективности, что и алгоритм, основанный на грубой силе, очевидно, что в среднем он превосходит последний.