Jon L. Bentley
Bell Labs, Lucent Technologies
jlb@research.bell-labs.com
Robert Sedgewick
Princeton University, Princeton, NJ
rs@cs.princeton.edu

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

http://www.cs.princeton.edu/~rs/strings

  С любезного разрешения авторов
Перевод с английского М.С.Галкиной
Под редакцией П.Н.Дубнера
infoscope@writeme.com

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

Дата последней модификации: 2 сентября 2000 г.