Мы представляем алгоритмы и их реализации на Си сортировки и поиска данных с составными ключами для приложений, в которых ключи являются строками символов. Алгоритм сортировки сочетает в себе свойства быстрой (Quicksort) и поразрядной (radix sort) сортировок; он не уступает самым известным кодам из стандартных программ библиотек Си. Алгоритм поиска сочетает свойства боров (TRIE-структур) и бинарных деревьев поиска; он быстрее хеширования и других широко применяемых методов поиска. Основные идеи, стоящие за этими алгоритмами, относятся как минимум к 60-м, однако их практическая ценность осталась тогда незамеченной. Мы также представляем обобщение на более сложные задачи – такие, как поиск частичных совпадений.

Оглавление

1. Введение
2. История
3. Алгоритмы
4. Анализ
5. Программы для строк
6. Более сложные алгоритмы поиска
7. Заключение
8. Приложение
9. Благодарности
10. Литература
11. Глоссарий