Например, Бобцов

МЕТОД БЫСТРОГО ПОИСКА УЗЛОВ СЕМАНТИЧЕСКОЙ СЕТИ ПО ТОЧНОМУ СОВПАДЕНИЮ СЛОВОФОРМЫ

Аннотация:

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

Ключевые слова:

Статьи в номере