Введение

Раздел 2 посвящен алгоритму быстрой сортировки Хоара [9] и бинарным деревьям поиска. Мы подчеркиваем хорошо известный изоморфизм, связывающий эти два подхода, и подытоживаем основные известные факты.

Алгоритмы и структуры данных для составных ключей представлены в разделе 3. Алгоритм быстрой сортировки (Multikey Quicksort) упорядочивает множество из n векторов по k компонент каждый. Как и обычный алгоритм быстрой сортировки, он делит данные на множества с ключами, большими или равными заданному значению; как и поразрядная сортировка, он переходит к следующему полю ключа, когда выясняется, что данное поле ключа текущего элемента равно этому значению. Для краткости часто упоминание о ключе опускается и говорится просто о больших, меньших и равных элементах сортируемого множества. Изоморфной структурой является троичное дерево поиска, каждый узел которого представляет разбиение подмножества векторов расщепляющим значением и тремя указателями: один к элементам, меньшим расщепляющего значения, другой - к большим (как в бинарном дереве поиска), а третий - к равным, у них потом сравниваются последующие поля ключа (как в борах). Как правило, применяемые структуры и методы стараются изложить на высоком теоретическом уровне, далеком от практических приложений. Приведенная здесь простая схема делает очевидной реализацию алгоритма.

Алгоритмы анализируются в разделе 4. Большая часть результатов оказывается новым изложением известных фактов.

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

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

В разделе 6 мы обращаемся к более трудным задачам символьного поиска. Запросы поиска частичных совпадений допускают произвольные, «не имеющие значения», символы (например, образцу «so.a», соответствуют слова soda и sofa). Основной результат в этом разделе - это реализация алгоритма поиска частичных совпадений Ривеста (Rivest) в троичном дереве и эксперименты по исследованию его эффективности. Запросы «ближайших соседей» выдают все слова, расстояние Хемминга которых от запрашиваемого слова не превосходит заданного (например, мы может искать все слова, расстояние которых от слова soda не превосходит 2). Мы даем новый алгоритм поиска ближайших соседей в строках, представляем простые реализации на Си, и описываем результаты экспериментов по исследованию их эффективности.

Выводы и итоги - раздел 7.