Аннотация. Разработка и использование онтологий является необходимым элементом анализа текстов на естественном языке. При потоковой обработке текстов время поиска в онтологии является критичным параметром для обработки большого объема данных. Предложен метод поиска словоформ по точному совпадению, согласно которому сначала словоформы слов из онтологии разбиваются на части определенной длины (х-граммы), по разработанному алгоритму вычисляется индекс х-граммы и узлы словоформ организуются в префиксное дерево, каждый уровень которого представлен в виде массива. Индекс х-граммы используется в качестве ключа. Для обеспечения компактности хранения выполняется операция сжатия набора разреженных массивов. Алгоритм словарного поиска, в свою очередь, разбивает искомый токен (слово) на соответствующие ему х-граммы, вычисляет индекс каждой части и по полученным индексам в массивах, соответствующих каждому из уровней префиксного дерева, находит словоформу в онтологии последовательной выборкой. Разработанное программное обеспечение показывает для тестового набора русских словоформ скорость поиска выше на 36—50 %, по сравнению с Google dense hashmap, a объем занимаемой памяти на 12 % меньше, чем в Google sparse hashmap. Разработанный метод применим для словарного поиска по редко изменяемым наборам искомых словоформ, таким как онтология, построенная на базе Викисловаря.

Ключевые слова: поиск в словаре, онтология на основе Викисловаря, префиксное дерево, слогоделение, n-граммы, хэш-таблицы, точный поиск

Список литературы:

1. Письмак А. Е., Харитонова А. Е., Цопа Е. А., Клименков С. В. Метод автоматического формирования семантической сети из слабоструктурированных источников // Программные продукты и системы. 2016. № 3. С. 74—78.
2. Klimenkov S., Tsopa E., Pismak A., Yarkeev A. Reconstruction of Implied Semantic Relations in Russian Wiktionary // Proc. of the 8th Intern. Joint Conf. on Knowledge Discovery, Knowledge Engineering and Knowledge Management (KDIR). 2016. Vol. 2. P. 74—80.
3. Бочаров В. В., Грановский Д. В., Суриков А. В. Вероятностная модель токенизации в проекте „Открытый корпус“ // Матер. 15-го науч.-практ. семинара „Новые информационные технологии в автоматизированных системах“. М.: Моск. гос. ин-т электроники и математики, 2012.
4. Neyer M. P. A Comparison of Dictionary Implementations. 2009 [Электронный ресурс]: https://www.cs.unc.edu/~plaisted/comp550/Neyer%20paper.pdf.
5. Mehlhorn K. and Sanders P. Algorithms and Data Structures. The Basic Toolbox. Springer, 2007. 285 р.
6. Peterson W. W. Addressing for Random-Access Storage // IBM J. of Research and Development. 1957. Vol. 1. P. 130—146.
7. Dumey A. I. Indexing for rapid random-access memory // Computers and Automation. 1956. Vol. 12, N 5. P. 6—9.
8. Comer D. and Shen V. Y. Hash-Bucket Search: A Fast Technique for Searching an English Spelling Dictionary Software // Practice and Experience. 1982. Vol. 12, N 7. P. 669—682.
9. Silverstein C. Google sparsehash package. 2010.
10. Silverstein C. Google sparsehash package performance [Электронный ресурс]: http://goog-sparsehash.sourceforge.net/doc/performance.html 2010.
11. Acharya Anurag, Huican Zhu, and Kai Shen. Adaptive algorithms for cache-efficient trie search // Workshop on Algorithm Engineering and Experimentation. Lecture Notes in Computer Science. Berlin—Heidelberg: Springer, 1999. Vol. 1619. P. 300—315.
12. Thenmozhi M., Srimathi H. An Analysis on the Performance of Tree and Trie based Dictionary Implementations with Different Data Usage Models // Indian J. of Science and Technology. 2015.
13. Pryor D. V., Thistle M. R., and Shirazi N. Text searching on Splash 2 // Proc. Workshop on FPGAs for Custom Computing Machines. 1993.
14. Aho A. V., Hill M., Hopcroft J., Ulman J. D. Data structures and algorithms. 1983.
15. Андрейченко Л. Н. Русский язык. Фонетика и фонология. Орфоэпия. Графика и орфография / Под ред. Г. Г. Инфантовой и Н. А. Сениной. М.: Флинта, 2003.
16. Malyshev B., Samarin A., and Vulis D. Russian T&jX // TUGboat. 1991. Vol. 12, N 2. P. 212—214.
17. Зализняк А. А. Грамматический словарь русского языка. М.: АСТ-Пресс, 2008.
18. Грановский Д. В., Бочаров В. В., Бичинева С. В. Открытый корпус: принципы работы и перспективы // Тр. науч. семинара „Компьютерная лингвистика и развитие семантического поиска в Интернете“ XIII Всерос. объедин. конф. „Интернет и современное общество“. Санкт-Петербург, 19—22 октября 2010. 94 с.
19. Жуков М. А., Афанасьев Д. Б. Анализ и оценка минимального уровня префиксного дерева в системе бесхешевой дедупликации // Научно-технический вестник информационных технологий, механики и оптики. 2015. Т. 15, № 3. С. 470—475.
20. Cisłak A. and Grabowski S. A practical index for approximate dictionary matching with few mismatches // arXiv:1501.04948. 2015.