Язык статьи - русский
Ссылка для цитирования: Андреева А.Г., Маркина Т.А. Оценка подобия деревьев с помощью вычисления pq-грамм расстояния // Научно-технический вестник информационных технологий, механики и оптики. 2017. Т. 17. № 3. С. 490–497. doi: 10.17586/2226-1494-2017-17-3-490-497
Аннотация
Представлен алгоритм оценки подобия иерархических данных на основе вычисления pq-грамм расстояния. Выполнен анализ чувствительности алгоритма от выбранных параметров p и q. Показано, насколько сильно будет изменяться результат работы алгоритма при сравнении двух деревьев, имеющих различие в одном произвольном узле, когда один из узлов исходного дерева удален, переименован, либо добавлен лишний узел. Продемонстрировано, что подобный анализ позволяет подобрать параметры pи qприменительно к решаемой задаче. Обоснована задача предварительной оценки дерева – приближенный анализ начального уровня расхождений узлов в выбранных pq-граммах сравниваемых деревьев. Обозначены основные термины и определения, относящиеся к алгоритмам обработки древовидных структур данных, а также непосредственно к самому рассматриваемому алгоритму. Приведены примеры, иллюстрирующие практическое использование алгоритма, показаны детали реализации алгоритма на реальной задаче.
Ключевые слова: pq-грамм, деревья, подобие деревьев, pq-грамм расстояние, pq-грамм шаблон, pq-грамм профиль, XML
Список литературы
1. Tai K.-C. The tree-to-tree correction problem // Journal of ACM. 1979. V. 26. N 3. P. 422–433. doi:
10.1145/322139.322143
2. Zhang K., Shasha D. Simple fast algorithms for the editing distance between trees and related problems // SIAM Journal of Computing. 1989. V. 18. N 6. P. 1245–1262.
3. Demaine E.D., Mozes S., Rossman B., Weimann O. An optimal decomposition algorithm for tree edit distance // ACM Transactions on Algorithms. 2009. V. 6. N 1. Art. 2. doi:
10.1145/1644015.1644017
4. Pawlik M., Augsten N. RTED: a robust algorithm for the tree edit distance // Proc. 38th VLDB Endowment. Istanbul, Turkey, 2012. V. 5. N 4. P. 334–345.
5. Augsten N., Boehlen M., Gamper J. Approximate matching of hierarchical data using pq-grams // Proc. 31st Int. Conf. on Very Large Data Bases. Trondheim, Norway, 2005. V. 1. P. 301–312.
6. Кубенский А.А. Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++. СПб.: БВХ-Петербург, 2004. 464 с.
7. Гасфилд Д. Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология. СПб.: Невский Диалект, БВХ-Петербург, 2003. 656 с.
8. Кнут Д.Э.Искусство программирования. Т. 2. Основные алгоритмы. 3-е изд. М.: Вильямс, 2000. 832 с.
9. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. 3-еизд. М.: Вильямс, 2013. 1328 с.
10. Богомолов А.М., Салий В.Н. Алгебраические основы теории дискретных систем. М.: Физматлит, 1997. 368 с.
11. Кремер Н.Ш. Теория вероятностей и математическая статистика. 2-е изд. М.: Юнити-Дана, 2003. 573 с.
12. Srivastava N., Mishra V., Bhattacharya A. Analyzing the sensitivity of pq-gram distance with p and q // Proc. 10th Int. Conf. on Very Large Data Bases. Singapore, 2010.
13. Wagner R.A., Fischer M.J. The string-to-string correction problem // Journal of ACM. 1974. V. 21. N1. P. 168–173.doi:
10.1145/321796.321811
14. Захаров В.Н., Хорошилов А.А. Автоматическая оценка подобия тематического содержания текстов на основе сравнения их формализованных смысловых описаний // Труды 14-й Всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции», RCDL-2012. Переславль-Залесский, Россия, 2012.
15. Хантер Д., Рафтер Д., Фаусетт Д., ван дер Влист Э. и др. XML. Работа с XML. 4-е изд. М.: Диалектика, 2009. 1344 с.
Флах П. Машинное обучение. Наука и искусство построения алгоритмов, которые извлекают знания из данных. М.: ДМК Пресс, 2015. 400 с.
