Алгоритм Кнута, Морриса и Пратта

Прямой поиск строки

Часто приходится сталкиваться со специфическим поиском, так называемым поиском строки. Его можно определить следующим образом. Пусть задан массив s из N элементов и массив p из M элементов,

Вложенный цикл с предусловием начинает выполняться тогда, когда первый символ слова p совпадает с очередным, i-м, символом текста s. Этот цикл повторяется столько раз, сколько совпадает символов текста s, начиная с i-го символа, с символами слова p (максимальное количество повторений равно M). Цикл завершается при исчерпании символов слова p (перестает выполняться условие j<M) или при несовпадении очередных символов s и p (перестает выполняться условие s[i+j]=p[j]). Количество совпадений подсчитывается с использованием j. Если совпадение произошло со всеми символами слова p (т.е. слово p найдено), то выполняется условие j=M, и алгоритм завершается. В противном случае поиск продолжается до тех пор, пока не просмотренной останется часть текста s, которая содержит символов, меньше, чем есть в слове p (т.е. этот остаток уже не может совпасть со словом p). В этом случае выполняется условие i=N-M, что тоже приводит к завершению алгоритма. Это показывает гарантированность окончания алгоритма.

Алгоритм Кнута, Морриса и Пратта.

Основным отличием КМП-алгоритма от алгоритма прямого поиска является осуществления сдвига слова не на один символ на каждом шаге алгоритма, а на некоторое переменное количество символов. Таким образом, перед тем как осуществлять очередной сдвиг, необходимо определить величину сдвига. Для повышения эффективности алгоритма необходимо, чтобы сдвиг на каждом шаге был бы как можно большим.

ABCABCABAABCABD

ABCABD

A

ABC

AB

ABCABD

http://khpi-iip.mipk.kharkiv.edu/library/datastr/book_sod/guap/index2.htm

Сортировка простым выбором осуществляется следующим образом. Просмотрим элементы массива от первого до последнего, определим элемент с наименьшим значением, и обменяем это значение с первым. Затем так же выберем наименьшее значение среди A [2] ... A [n] и обменяем его со значением A [2], затем выберем следующее наименьшее и обменяем с A [3] и т.п..

Пузырьковая сортировка. Входное множество просматривается, при этом попарно сравниваются соседние элементы множества. Если порядок их следования не соответствует заданному критерию упорядоченности, то элементы меняются местами. В результате одного такого пересмотра при сортировке по возрастанию элемент с самым большим значением ключа переместится ("всплывет") на последнее место в множестве. При следующем проходе на свое место "выплывет" второй по величине ключа элемент и т.д. Для постановки на свои места N элементов следует сделать N-1 проходов. Выходная множество, таким образом, формируется конце сортуемои последовательности, при каждом проходе его объем увеличивается на 1, а объем входного множества уменьшается на 1.

Порядок пузырьковой сортировки - O (N ^ 2). Среднее число сравнений - N * (N-1) / 2 и такое же среднее число перестановок значительно хуже, чем для обменной сортировки простым выбором. Однако, то обстоятельство, что здесь всегда сравниваются и перемещаются только соседние элементы, делает пузырьковая сортировка удобно обработки связных списков. Перестановка в связных списках также выходит более экономной. Еще одно преимущество пузырьковой сортировки заключается в том, что при незначительных модификациях его можно сделать чувствительным к исходной упорядоченности входного множества.

Шейкер-сортировка. Суть его заключается в том, что направления просмотров чередуются: за просмотром от начала до конца надо сделать просмотр от конца к началу входной множества. При просмотре в прямом направлении запись с самым большим ключом ставится на свое место в последовательности, при просмотре в обратном направлении - запись с самым маленьким. Этот алгоритм достаточно эффективен для задач восстановления упорядоченности, когда исходная последовательность уже была упорядочена, но подверглась не слишком значительным изменениям. Упорядоченность в последовательности с одиночной изменением будет гарантированно восстановлена ​​всего за два прохода.

Сортировка Шелла. Это еще одна модификация пузырьковой сортировки. Суть его заключается в том, что здесь выполняется сравнение ключей, отстоящих друг от друга на некотором расстоянии d. Начальный размер d выбирается сравнимым с половиной общего размера сортуемои последовательности. Выполняется пузырьковая сортировка с интервалом сравнения d. Затем величина d уменьшается вдвое и снова выполняется пузырьковая сортировка, далее d уменьшается еще вдвое и т.д. Последнее пузырьковая сортировка выполняется при d = 1. Качественный порядок сортировки Шелла остается O (N ^ 2), среднее же число сравнений, найденное эмпирическим путем - log2 (N) ^ 2 * N. Ускорение достигается за счет того, что найденные «не на месте

Сортировка простыми вставками позволяет создать отсортированный массив из значений, читаемых например, с клавиатуры. Первое значение записывается на первое место, то есть присваивается первому элементу массива. Второе значение сравнивается с первым и, если первое меньше, то оно "вытесняется" на второе место. Иначе новое значение идет на второе место. Затем третий сравнивается со вторым и записывается либо на третье место, или вытесняет значение со второго места на третье и сравнивается с тем, что на первом месте. Например, за чтение последовательности значений 3, 1, 2 создаются последовательности значений в массиве <3>, <1, 3> <1, 2, 3>. Вообще, после чтения k-1 элемента имеем отсортированную часть массива A [1] A [2] ... A [k-1]. Новое значение v сравниваем со значением A [k-1]. Если A [k-1]> v, то значение A [k-1] сдвигаем на k-е место. После этого сравниваем v со значением A [k-1] если A [k-2]> v, то A [k-2] сдвигаем на (k-1)-е место и т.п.. Когда при очередном сравнения A [i] <= v, то v записывается на (i +1)-е место. Если все значения в массиве больше v, то они сдвигаются, а v записывается на первое место.

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

Сортировка упорядоченным бинарным деревом. Алгоритм состоит из построения упорядоченного бинарного дерева и последующего его обхода. Если нет необходимости в построении всего линейного упорядоченного списка значений, то нет необходимости и в обходе дерева, в этом случае применяется поиск в упорядоченном бинарном дереве. Отметим, что порядок алгоритма - O (N * log2 (N)), но в конкретных случаях все зависит от упорядоченности исходной последовательности, влияющим на степень сбалансированности дерева и в конечном итоге - на эффективность поиска.

Турнирное сортировки. Этот метод сортировки получил свое название из-за сходства с кубковой системе проведения спортивных соревнований: участники соревнований разбиваются на пары, среди которых разыгрывается первый тур; из победителей первого тура состоят пара для розыгрыша второго тура и т.д. Алгоритм сортировки состоит из двух этапов. На первом этапе строится дерево аналогичное схеме розыгрыша Кубка.

Следующий этап состоит в выборке значений из пирамиды и формирования из них упорядоченной последовательности. В каждой итерации цикла процедуры выбирается значение из вершины пирамиды - это наименьшее из имеющихся в пирамиде значений ключа. Узел - вершина при этом освобождается, освобождаются также и все узлы, занимаемые выбранным значением на более низких уровнях пирамиды. По узлы, освободившиеся устраивается (снизу вверх) соревнование между их потомками.

Построение дерева требует N-1 сравнений, выборка - N * log2 (N) сравнений. Порядок алгоритма, таким образом, O (N * log2 (N)). Сложность операций над связными структурами данных, однако, значительно выше, чем над статическими структурами. Кроме того, алгоритм неэкономический относительно памяти: дублирование данных на разных уровнях пирамиды приводит к тому, что рабочая область памяти содержит примерно 2 * N узлов.

Дата добавления: 2015-07-26; просмотров: 268; Нарушение авторских прав

Мы поможем в написании ваших работ!