ЭФФЕКТИВНАЯ СТРУКТУРА ХРАНЕНИЯ СЛОВАРЯ СТРОКОВЫХ КЛЮЧЕЙ С АССОЦИИРОВАННЫМИ ЗНАЧЕНИЯМИ |
5 | |
2012 |
научная статья | 004.051 | ||
301-308 | визуальные словарь, эффективные структуры хранения, префиксное дерево, конечный автомат, вычислительная лингвистика, машинная морфология |
Предложен способ реализации словаря на основе минимальных конечных автоматов, где ключу ставится в соответствие набор значений. Показаны его преимущества в сравнении с доступными решениями в виде СУБД и классов стандартной библиотеки C++: улучшение по времени поиска составляет от 20-40 раз до порядков. При этом существенно сокращается требуемая для хранения память. |
1 . Daciuk J., Mihov S., Watson B.W., Watson R.E. Incremental construction of minimal acyclic finite-state automata // Computational Linguistics. 2000. V. 26. N.1. P. 3–16, March ‘00. 2 . Lucchesi C.L., Kowaltowski T. Applications of finite automata representing large vocabularies // Software-Practice and Experience. 1993. 23. 15–30. 3 . Ахо А.В., Лам М.С., Сети Р., Ульман Д.Д. Компиляторы: принципы, технологии и инструментарий. 2-е изд. М.: Вильямс, 2008. 4 . http://www.open-std.org/jtc1/sc22/wg21/docs/ papers/2005/n1905.pdf 5 . http://www.sqlite.org/inmemorydb.html 6 . http://www.oracle.com/technetwork/products /berkeleydb/overview/index.html 7 . Скатов Д.С. Эффективные реализации строковых словарей для решения задач компьютерной лингвистики // Интеллектуальные системы и компьютерные науки: Сб. тр. X Международ. конф. М., 2011. 8 . Кнут Д. Искусство программирования. Т. 3. Сортировка и поиск. 2-е изд. М.: Вильямс, 2007 |