Fast algorithms for Sorting and Searching Strings
Быстрые алгоритмы сортировки и поиска строк

Jon L. Bentley
Bell Labs, Lucent Technologies
[email protected]
Robert Sedgewick
Princeton University, Princeton, NJ
[email protected]

Presented at Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
New Orleans, January, 1997

С любезного разрешения авторов
Перевод с английского М.С.Галкиной
Под редакцией П.Н.Дубнера
[email protected]

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

Оглавление