44. Алгоритмы поиска: последовательный, бинарный, интерполяционный поиск, использование деревьев в задачах поиска; хеширование с открытой и закрытой адресацией; алгоритмы поиска подстроки в строке.

Алгоритм последовательного поиска:

R1: i = 1;

R2: если Ki = K, то УДАЧА;

R3: i = i + 1;

R4: если i <= n, то перейти к шагу R2;

иначе НЕУДАЧА.

Быстрый последовательный поиск:

B1: i = 1, Kn+1 = K;

B2: если Ki = K, то перейти к шагу B4;

B3: i = i + 1; перейти к шагу B2;

B4: если i <= n, то УДАЧА;

иначе НЕУДАЧА.

В этом алгоритме быстрее выполняется самый внутренний цикл

за счет того, что не надо выполнять проверку i <= n.

Бинарный поиск

Если массив упорядочен по возрастанию или убыванию, то можно применить более быстрые методы поиска, такие как, например, бинарный (методом деления пополам).

Интерполяционный поиск

Данный метод, также как и бинарный поиск, требует чтобы массив был упорядочен по возрастанию или убыванию. Работа этого метода также аналогична предыдущему, с той только разницей, что на каждом шаге рассматривается элемент, находящийся не в середине текущей части массива, а в позиции, которая находится от начальной на расстоянии, определяемом по формуле:

P=(r-l)(k-ai)/(ar-ai)

Здесь r и l — соответственно правая и левая граница области поиска, k — искомый элемент, al и ar - соответственно левый и правый элемент области поиска.

Если в дереве между порожденными узлами, имеющими общий исходный, считается существенным их порядок, то дерево называется упорядоченным. В задачах поиска почти всегда рассматриваются упорядоченные деревья.

Упорядоченное дерево, степень которого не больше 2 называется бинарным деревом. Бинарное дерево особенно часто используется при поиске в оперативной памяти. Алгоритм поиска: вначале аргумент поиска сравнивается с ключом, находящимся в корне. Если аргумент совпадает с ключом, поиск закончен, если же не совпадает, то в случае, когда аргумент оказвается меньше ключа, поиск продолжается в левом поддереве, а в случае когда больше ключа - в правом поддереве. Увеличив уровень на 1 повторяют сравнение, считая текущий узел корнем.

В случае открытого хеширования (другое название хеширования цепочками), мы объедением элементы, хешированные в одну и ту же ячейку, в связный список.

Так, идея достаточно проста. Если при добавлении в хеш-таблицу в заданную ячейку мы встречаем ссылку на элемент связного списка, то случается коллизия. Так, мы просто вставляем наш элемент как узел в список. При поиске мы проходим по цепочкам, сравнивая ключи между собой на эквивалентность, пока не доберёмся до нужного. При удалении ситуация такая же.

Хеширование с открытой адресацией

В случае метода открытой адресации (или по-другому: закрытого хеширования) все элементы хранятся непосредственно в хеш-таблице, без использования связанных списков. В отличии от хеширования с цепочками, при использовании метода открытой адресации может возникнуть ситуация, когда хеш-таблица окажется полностью заполненной, так что будет невозможно добавлять в неё новые элементы. Так что при возникновении такой ситуации решением может быть динамическое увеличение размера хеш-таблицы, с одновременной её перестройкой.

поиск подстроки боуера мура

На первом шаге мы строим таблицу смещений для искомого образца. Процесс построения таблицы будет

описан ниже. Далее мы совмещаем начало строки и образца и начинаем проверку с последнего символа

образца. Если последний символ образца и соответствующий ему при наложении символ строки не совпадают,

образец сдвигается относительно строки на величину, полученную из таблицы смещений, и снова проводится

сравнение, начиная с последнего символа образца. Если же символы совпадают, производится сравнение

предпоследнего символа образца и т. д. Если все символы образца совпали с наложенными символами строки,

значит мы нашли подстроку и поиск окончен. Если же какой-то (не последний) символ образца не совпадает с

соответствующим символом строки, мы сдвигаем образец на один символ вправо и снова начинаем проверку с

последнего символа. Весь алгоритм выполняется до тех пор, пока либо не будет найдено вхождение искомого

образца, либо не будет достигнут конец строки.

Величина сдвига в случае несовпадения последнего символа вычисляется исходя из следующих соображений:

сдвиг образца должен быть минимальным, таким, чтобы не пропустить вхождение образца в строке. Если данный

символ строки встречается в образце, мы смещаем образец таким образом, чтобы символ строки совпал с самым

правым вхождением этого символа в образце. Если же образец вообще не содержит этого символа, мы сдвигаем

образец на величину, равную его длине, так что первый символ образца накладывается на следующий за

проверявшимся символ строки. Величина смещения для каждого символа образца зависит только от порядка символов

в образце, поэтому смещения удобно вычислить заранее и хранить в виде одномерного массива, где каждому символу

алфавита соответствует смещение относительно последнего символа образца.

Алгоритм Рабина-Карпа

Идея, предложенная Рабином и Карпом, подразумевает поставить в соответствие каждой строке

некоторое уникальное число, и вместо того чтобы сравнивать сами строки, сравнивать числа, что

намного быстрее. Проблема в том, что искомая строка может быть длинной, строк в тексте тоже

хватает. А так как каждой строке нужно сопоставить уникальное число, то и чисел должно быть

много, а стало быть, числа будут большими (порядка Dm, где D - количество различных

символов), и работать с ними будет так же неудобно. Ниже вы узнаете, как найти выход из этого

положения, а пока смотрите реализацию для текста, состоящего только из цифр, и строки

длиной до 8 символов.

кнута-морриса-пратта

Метод использует предобработку искомой строки, а именно: на ее основе создается так

называемая префикс-функция. Суть этой функции в нахождении для каждой подстроки S[1..i]

строки S наибольшей подстроки S[1..j] (j<i), присутствующей одновременно и в начале, и в конце

подстроки (как префикс и как суффикс). Например, для подстроки abcHelloabc такой подстрокой

является abc (одновременно и префиксом, и суффиксом). Смысл префикс-функции в том, что мы

можем отбросить заведомо неверные варианты, т.е. если при поиске совпала подстрока

abcHelloabc (следующий символ не совпал), то нам имеет смысл продолжать проверку

продолжить поиск уже с четвертого символа (первые три и так совпадут).