Главная страница
russian   english
16+
<< назад

Название статьи

ЭФФЕКТИВНАЯ СТРУКТУРА ХРАНЕНИЯ СЛОВАРЯ СТРОКОВЫХ КЛЮЧЕЙ С АССОЦИИРОВАННЫМИ ЗНАЧЕНИЯМИ


Номер журнала
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