Article

Article title SPATIO-TEMPORAL OPTIMIZATION OF DATA STRUCTURE IN NATURAL LANGUAGE WITH ACCESSING BY-KEYS
Authors I.S. Zlygostev
Section SECTION IV. MATHEMATICAL METHODS OF THE ARTIFICIAL INTELLECT
Month, Year 08, 2009 @en
Index UDC 681.3.07
DOI
Abstract In this work the PATRICIA-tree structure optimization in the context of using it for data storage was investigated. The access keys for data are the words of Russian language. Optimization made by volume contraction of structure with the minimum loss of work speed. Optimization was done on basis of statistical data of Russian language vocabulary. The algorithms of direct and reverse iterations by structure keys that sorted lexicographically were considered. Research makes it possible to decrease the structure size 25 times and makes available the usage of the structure not only for the quick search, but also for the full data control.

Download PDF

Keywords Data structure; PATRICIA-tree; statistic optimization; dictionary; Russian language; lexi- cographical grading; iteration on tree; volume optimization.
References 1. Зализняк, А.А. Грамматический словарь русского языка (словоизменение). 2-е изд. – М.: Русский язык, 1980.
2. Мельчук, И.А. Курс общей морфологии. – М.: ЯРК, 1998. – С. 175.
3. Мельчук, И.А. Русский язык в модели «Смысл-Текст»/ И.А. Мельчук. – Москва – Вена: Школа «Языки русской культуры», Венский славистический альманах, 1995. – XXVIII. – С. 682.
4. E. Ukkonen. Approximate String Matching over Suffix-Trees. In Proceedings of the Fourth Annual Symposium on Combinatorial Pattern Matching, Padova, Italy, June. 1993. – Р. 229-242,
5. D.R. Morrison. PATRICIA - practical algorithm to retrieve information coded in alphanumeric. Journal of the ACM, 15(4):514-o34 (1968).
6. Kahveci, T.М. Proceedings of the 27th International Conferenc on Very Large Databases // T. Kahveci, Ambuj K. Singh // An Efficient Index Structure for String Databases. 2001. – Р. 351-360.
7. Resnikoff, H.L. The Nature of Affixing in Written English. Part 1, in Mechanical Translation, 8, No. 3 (1965), Part 11 in Mechanical Translation 9, No. 2 (1966).
8. Shang, H.G. Tries for Approximate String Matching – H. Shang T.H. Merret – In IEEE Transactions on Knowledge and Data Engineering, volume 8(4). 1996. – Р. 540 – 547,

Comments are closed.