 |
Порядковые статистики
|
|
|
|
Часто бывает необходимо решить задачупоиска 
-го наименьшего элемента в последовательности. К таким задачам относится задача поиска минимального или максимального элемента в множестве, поиска медианы множества и т.д. Эта задача тесно связана с задачей сортировки. В самом деле, соответствующий элемент можно найти, отсортировав исходную последовательность и выбрав -й по счету элемент в отсортированной последовательности. Очевидно, сложность такого подхода связана со сложностью сортировки и равна 
. Но из условия задачи следует, что для ее решения необходима информация о первых 
элементах, которые меньше или равны заданному. Знание же элементов, следующих за -м наименьшим элементом ничего нам не дает. Отказ от полной сортировки исходной последовательности позволяет уменьшить сложность алгоритма до линейной функции.
Рассмотрим некоторый элемент 
исходной последовательности. Разделим исходную последовательность относительно на три части: 
- последовательность элементов, меньших 
, 
- последовательность элементов равных и 
- последовательность элементов больших . Сравнивая число элементов последовательности и 
с , можно определить какая из последовательностей содержит -ый наименьший элемент. Найдя соответствующую последовательность и скорректировав значение , сведем задачу поиска -го наименьшего элемента к подобной задаче меньшей размерности. Таким образом, алгоритм делит последовательность на три части, и далее обрабатывается только одна из частей. Процесс продолжается до тех пор, пока не получится последовательность, состоящая из небольшого числа элементов, в этом случае задача решается простой сортировкой.
|
|
|
Как и в алгоритме быстрой сортировки возникает задача выбора элемента . С точки зрения скорости работы алгоритма лучшим выбором элемента, относительно которого идет разбиение, является медиана. Худшим выбором является минимальный или максимальный элемент последовательности. Если выбирать этот элемент случайно, при помощи равномерно распределенного датчика случайных чисел, то можно доказать [4], что среднее время решения задачи оценивается как 
.
Однако можно предложить процедуру выбора, разделяющего элемента, при которой время работы алгоритма в худшем случае равно [2, 4].
Без ограничения общности можно полагать, что исходная последовательность содержит не менее 50 элементов. В противном случае задача может быть решена с использованием сортировки и сложность ее решения равна 
. Рассмотрим алгоритм поиска -го наименьшего элемента в последовательности, которая задается рекурсивной процедурой Procedure Выбор 
:
- Разбить исходную последовательность
длины 
на 
[12] групп по 5 элементов в каждой, кроме последней, которая может содержать менее 5 элементов. - Отсортировав элементы каждой групп, найти медиану. Обозначим через
медиану 
-ой группы, 
. - Рекурсивно применяя процедуру Выбор к последовательности медиан, найти медиану
этой последовательности. - Разбить исходную последовательность на две подпоследовательность
элементов меньших , 
элементов равных , 
- элементов, больших . Обозначим через 
мощность множества . - Если
, то выполнить процедуру Выбор 
, в противном случае, если 
, то решением задачи будет , в противном случае выполнить процедуру Выбор 
.
Обозначим время работы алгоритма для последовательности длины через 
. Нетрудно видеть, что временная сложность алгоритма для шагов 1,2,4 равна . Кроме того сложность выполнения шага 2 равна 
. Для того, чтобы оценить время выполнения шага 5, необходимо оценить сверху число элементов в последовательности и . Поскольку последовательность медиан состоит из элементов, то в этой последовательности не менее 
элементов больше или равны . Поскольку для каждого элемента последовательности существует по меньшей мере 3 элемента в группе, которые не меньше , то общее число элементов больших или равных в исходной последовательности 
. Тогда 
[13]. Аналогично выводится, что 
. Поэтому для некоторой константы 
имеем:
|
|
|
Решая это рекуррентное соотношение, получим 
.
Хеширование
Одним из основных недостатков последовательного поиска является зависимость времени доступа к различным элементам множества 
. Как упоминалось выше, основной причиной этого является отсутствие структурированности множества. С другой стороны массив является структурой, позволяющей, организовать прямой доступ к элементу при наличии его индекса. Но поскольку поиск обычно ведется по значению элемента, возникает задача преобразования значения элемента в индекс его местонахождения. Выше было описано, как с такой задачей справляются деревья поиска. Эта задача может быть решена при помощи специальных таблиц, преобразующих значения элементов в индексы, но тогда надо уметь решать задачу поиска в этих таблицах, и образуется заколдованный круг. Промежуточным вариантом является индексно-последовательный доступ, когда множество представляется в виде набора подмножеств и существует функция отображающая значение каждого элемента из в номер подмножества его содержащего. При такой организации множества, поиск элемента может быть сведен к поиску соответствующего подмножества с дальнейшим перебором в некотором порядке его элементов.
4.4.1. Открытое хеширование. Одной из реализаций такой идеи является таблица, строкам которой приписаны подмножества множества . Множества элементов, приписанных различным строкам таблицы, не пересекаются и каждый элемент множества принадлежит некоторой строке. Пусть строки таблицы пронумерованы и номера лежат в интервале от 0 до 
. Положим 
Пусть далее задана некоторая функция 
[14], которая называется функцией хеширования. Решение задачи поиска 
сводится к вычислению значения 
с дальнейшей проверкой предиката 
для элементов соответствующей строки. Наиболее часто используемой структурой для представления элементов строки 
является последовательный список или массив. Сочетание прямого и последовательного доступа представляет определенный компромисс между временем и объемом памяти. При этом число подмножеств множества является параметром алгоритма хеширования, выбор которого позволяет поддерживать необходимое соотношение между показателями времени и объема памяти.
|
|
|
Ниже приведен пример хеш-таблицы, в которой подмножества заданы списками:
Временная сложность одной операции поиска в худшем случае выражается как сумма 
, где первый член суммы является временем вычисления значения , а второй член временем поиска элемента 
в строке . Поскольку в неудачном случае, все элементы могут попасть в один класс, то временная сложность поиска в худшем случае составляет , где - число элементов множества [15]. Понятно, что минимизация общего времени поиска связана с минимизацией каждого слагаемого суммы 
. Поскольку 
прямо пропорционально числу элементов множества 
, то хорошие алгоритмы хеширования должны минимизировать мощность . Гораздо больший интерес представляет среднее время поиска. Средняя стоимость поиска зависит от того, насколько равномерно распределены хеш-значения по позициям таблицы. Оказывается при выполнении некоторых предположений (а именно если каждый элемент может равновероятно попасть в любую из позиций таблицы) можно оценить среднее время поиска элемента в таблице. Число 
называется коэффициентом заполнения таблицы. Пусть имеется хеш-функция равномерно распределяющая элементы множества по строкам таблицы. Тогда верна
Теорема [4] При равномерном хешировании среднее время успешного поиска в хеш-таблице с цепочками равно 
.
При этом при выполнении некоторых естественных условий среднее время можно свести к 
.
Поскольку два разных элемента 
и 
попадают в одну строку таблицы в случае 
, то следуя [14] назовем такую ситуацию коллизией. Поскольку разрешение коллизий требует дополнительного времени, при выборе подходящей хеш-функции руководствуются требованиями:
|
|
|
1. для любого 
время вычисления должно быть небольшим;
2. число коллизий должно быть минимальным.
Выбор подходящей функции, удовлетворяющей этим условиям, является достаточно сложной задачей. Подбор функции хеширования во многом зависит от элементов множества . При условии, что ключевые параметры элементов множеств и 
описываются натуральными числами, можно положить 
. Такая функция дает достаточно неплохие результаты при простых значениях 
. Если является множеством строк, то в качестве функции хеширования можно рассмотреть функцию, задаваемую процедурой
Function h(a: string): 0..d-1;
Var i, sum: integer;
begin
sum:=0;
for i=0 to length(a) do
sum:=sum+ord(a[i]);
h:=sum mod d;
end
Функция суммирует коды букв из строки с последующим вычислением остатка по модулю простого числа . Однако, как показывает анализ, это неудачный пример функции хеширования. В самом деле, если состоит из строк, начинающихся с одинаковых префиксов и имеющих одинаковые суффиксы, например строк вида str1+nom+str2, где nom – цифровая строка от нуля до , то распределение значений функции 
будет крайне неравномерным. Значения функции заполнят только около трети значений множества 
. Объясняется это тем, что константные части строк (str1 и str2) не влияют на число различных значений функции , а только производят сдвиг этих значений внутри 
, а сумма цифр чисел от 0 до принимает ограниченное число значений.
Для достижения равномерности можно использовать алгоритмы порождения равномерно распределенных псевдослучайных чисел [14, т.2]. В частности, в [7] предлагается использовать следующую функцию: Пусть не является степенью числа 10, элементы исходного множества определяются числами из интервала 
. Пусть 
такое число, что 
примерно равно 
. Положим 
, где 
- целая часть числа . Для символьных строк можно рассматривать представление строки в позиционной системе счисления с основанием 256, где каждому символу строки сопоставляется его двоичный код. Тогда в качестве значения 
можно выбрать значение числа в системе счисления с основанием 256. Например, строке 'abcd' соответствует число 
при 
.
4.4.2. Закрытое хеширование.При открытом хешировании для разрешения коллизий используются списки, содержащие элементы множества , и массив указателей на них. Рассмотрим другой вариант представления данных, когда все элементы множества хранятся в едином массиве, а при вставке элемента для разрешения коллизий применяется методика повторного хеширования. Если мы пытаемся поместить элемент в позицию массива, которая занята другим элементом, то выбирается последовательность индексов 
, 
и так далее, пока не будет найдена свободная позиция.Последовательность функций хеширования 
фиксируется заранее и не меняется в ходе работы алгоритма. Одним из наиболее простых способов определения последовательности 
является соотношение 
при фиксированном 
. Такой вариант построения последовательности называется линейным хешированием. Поиск элемента в таблице заключается в последовательном вычислении значений 
, пока не будет найдено это значение или не встретится незаполненная ячейка массива, которая является меткой конца подпоследовательности, в которой может встретиться элемент . Допустим при 
, необходимо вставить элемент , а соответствующая позиция массива содержит другой элемент 
:
|
|
|
| … |
| 
| 
| … | ||
|
| 
|
Первой свободной ячейкой в этом случае будет ячейка с адресом , куда и вставляется элемент . После вставки элемента таблица выглядит следующим образом:
| … |
|
|
| … | ||
|
|
|
|
Предложенная схема хорошо работает при последовательности операций вставки и поиска, но операция удаления элементов из таблицы создает определенные проблемы. Если понимать удаление элемента из таблицы как очистку соответствующего элемента массива, то такая операция может разбить последовательность, в которой находился соответствующий элемент на две и вторая последовательность становится недоступной при поиске . Например, удаление элемента из таблицы разобьет последовательность, начинающуюся с индекса и содержащую не менее трех элементов на две с начальными индексами и . Если удаляемый элемент не очищать, а помечать подходящим способом так, чтобы он не разрывал существующие последовательности адресов, то приведенный выше алгоритм поиска может быть использован и при операциях удаления элементов из таблицы [7].
При закрытом хешировании элементы входной последовательности могут оказаться размещенными с помощью разных хеш-функций. Поскольку конец последовательности подбора хеш-функции определяется незаполненным элементом массива, то при выборе хеш-функции необходимо добиваться, чтобы метки концов были как можно более равномерно распределены по массиву. Возникает вопрос, какова должна быть в среднем длина последовательности при включении в таблицу элемента 
? В [7] приводится анализ этой ситуации. При условии, что таблица имеет позиций, из которых ячеек заполнены, и значения хеш-функции равномерно распределены, среднее число шагов поиска при линейном хешировании незанятой позиции составляет 
. Например вставка элемента при заполненной наполовину таблицы требует в среднем 2-х попыток. Поскольку значение меняется от 0 до , то среднее число попыток на заполнение одной позиции при заполнении позиций аппроксимируется функцией 
. В частности при 
среднее число попыток вставки одного элемента равно 
, соответственно элементов - 
. При поиске элемента, которого нет в таблице, а для этого необходимо найти незаполненную позицию, требуется в среднем такое же число проб, как и при вставке нового элемента при точно таком же заполнении таблицы. Если элемент присутствует в таблице, то его поиск может закончиться как на первом, так и на втором, и на шаге, где - число заполненных позиций в таблице. Поэтому поиск требует в среднем такое же число проб, сколько необходимо для вставки всех элементов, сделанных к моменту поиска. Поскольку удаление найденного элемента требует константного времени, то среднее время на удаление совпадает со временем поиска элемента, присутствующего в таблице. Следует отметить, что удаление элемента не уменьшает среднее время поиска.
Вышеприведенный пример с последовательностью функцией 
показывает, что значения последовательности 
имеют тенденции к группировке (возникают достаточно длинные заполненные смежные фрагменты, при наличии наборов подряд идущих незаполненных ячеек). Ситуация мало меняется при выборе последовательности , где 
удовлетворяет условию 
, или любой другой, где очередная проба некоторым фиксированным образом зависит от предыдущих проб. Одним из способов борьбы с этим явлением является введение случайности в определение функций . Положим 
, где 
- случайная перестановка чисел 1,2, …, . Конечно, числа выбираются один раз и не меняются в ходе работы алгоритма.
Рассмотрим пример задачи поиска 
, где и - некоторые подмножества отрезка 
, приведенный в [22]. Пусть имеется некоторое 
упорядоченное по возрастанию конечное множество чисел из интервала [0,1]. Положим 
и 
, разделим отрезок [0,1] на равных частей, так что -я часть представляет интервал 
, 
. Положим 
и 
. Рассмотрим характеристическую функцию 
,такую что 
, если интервал 
не содержит точек из , и 
, если 
. Тогда для любого запроса 
поиск реализуется следующим образом: Вычисляется 
. Номер является номером интервала, в котором необходимо искать точку . Если , то 
, в противном случае вычисляется значение предиката 
, и в случае его истинности получаем 
.
Хеш-таблицы часто применяются в базах данных, и, особенно, в языковых процессорах типа компиляторов и ассемблеров, где они используются в таблицах идентификаторов. В таких приложениях, таблица - наилучшая структура данных.
В заключение этого раздела приведем, позаимствованную из [3] сравнительную таблицу сложностей выполнения операций вставки и поиска на множестве из элементов при применении различных структур данных.
| Используемая структура данных | Худший случай | В среднем | ||||
| вставка | поиск | Порядковая статистика | вставка | Удачный поиск | Неудачный Поиск | |
| Неупорядоченный массив | O(1) | O(n) | O(nlogn) | O(1) | O(n/2) | O(n) |
| Неупорядоченный связный список | O(1) | O(n) | O(nlogn) | O(1) | O(n/2) | O(n) |
| Упорядоченный массив | O(n) | O(n) | O(1) | O(n/2) | O(n/2) | O(n/2) |
| Упорядоченный связный список | O(n) | O(n) | O(n) | O(n/2) | O(n/2) | O(n/2) |
| Бинарный поиск (на базе упоряд. массива) | O(n) | O(logn) | O(1) | O(n/2) | O(logn) | O(logn) |
| Дерево бинарного поиска | O(n) | O(n) | O(n) | O(logn) | O(logn) | O(logn) |
| Красно-черное дерево | O(logn) | O(logn) | O(logn) | O(logn) | O(logn) | O(logn) |
| АВЛ дерево | O(logn) | O(logn) | O(logn) | O(logn) | O(logn) | O(logn) |
| Хеширование | O(1) | O(n) | O(nlogn) | O(1) | O(1) | O(1) |
Поиск подстрок
Одной из наиболее часто решаемых задач является поиск информации в текстовых файлах. С подобной задачей приходится сталкиваться в текстовых редакторах и в базах данных. Следует отметить использование алгоритмов поиска при индексации страниц поисковым роботом, где актуальность информации напрямую зависит от скорости нахождения ключевых слов в тексте. Поскольку объемы перерабатываемой информации велики, то большое значение имеет построение эффективных алгоритмов поиска в последовательных структурах. Эта задача известна как задача поиска подстрок.
Задачу поиска подстрок можно сформулировать следующим образом: во множестве всех фиксированной длины подстрок некоторой строки найти подстроку, совпадающую с определенным образцом-шаблоном. Конечно, имеется тривиальный алгоритм последовательного перебора всех подстрок, пока не будет найден объект поиска, но подобная стратегия приводит к алгоритму сложности 
, где - длина строки, в которой ведется поиск, а - длина строки – образца. С другой стороны понятно, что множество подстрок, в котором ведется поиск, организовано определенным образом, и при сравнении новой подстроки с шаблоном имеется возможность использовать информацию, полученную на предыдущих шагах поиска. Например, найдя подстроку babb и обнаружив несоответствие в четвертом символе (совпало только bab), алгоритм полного перебора начнет сравнивать образец, начиная со следующего символа текста (с подстрокой abb…), хотя видно, что этого не надо делать. Кроме того, следует отметить, что очень часто в поиске образец описан неточно (необходимо уметь найти вариант из множества возможных претендентов). Сформулируем задачу более формально:
Как и ранее будем полагать, что мы решаем задачу 
для некоторого множества и элемента из . представляет множество всех подстрок фиксированной длины некоторой строки в конечном алфавите 
. Множество образцов можно рассматривать как объединение некоторых строк. Задача заключается в нахождении всех подстрок в , совпадающих хотя бы с одним шаблоном из , и относится к классу задач распознавания объектов по заданному шаблону.
Рассмотрим задачу поиска в случае, когда содержит единственную цепочку-шаблон. Ниже разбирается алгоритм Рабина-Карпа [4], который, не являясь лучшим по сложности, представляет методологический интерес, демонстрируя как, используя числовые хеш-функции, можно в среднем улучшить работу простейшего алгоритма сравнения шаблона со всеми подстроками исходной строки.
|
|
|
