Статья

Название статьи ПРОСТРАНСТВЕННО-ВРЕМЕННАЯ ОПТИМИЗАЦИЯ СТРУКТУРЫ ДАННЫХ ЕСТЕСТВЕННОГО ЯЗЫКА С ДОСТУПОМ ПО КЛЮЧАМ
Автор И.С. Злыгостев
Рубрика РАЗДЕЛ IV. МАТЕМАТИЧЕСКИЕ МЕТОДЫ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА
Месяц, год 08, 2009
Индекс УДК 681.3.07
DOI
Аннотация В работе проведена оптимизация структуры PATRICIA-дерева в контексте использования ее для хранения данных, ключами доступа к которым являются слова русского языка с целью уменьшения объема, занимаемого структурой при минимальных потерях в скорости работы с ней. Оптимизация проведена на основе данных статистически словаря русского языка. Приведены алгоритмы итераций по ключам структуры, отсортированным в лексикографическом порядке. Оптимизация структуры привела к сокращению размера дерева в 25 раз и сделала доступным использование структуры как с целью быстрого поиска, так и для управления содержащимися в ней данными.

Скачать в PDF

Ключевые слова Структура данных; PATRICIA дерево; статистика; словарь; русский язык; лексико- графический порядок; итерация; оптимизация по объему.
Библиографический список 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.