DOI: 10.17586/2226-1494-2017-17-3-490-497


ОЦЕНКА ПОДОБИЯ ДЕРЕВЬЕВ С ПОМОЩЬЮ ВЫЧИСЛЕНИЯ pq-ГРАММ РАССТОЯНИЯ

Андреева А. Г., Маркина Т. А.


Язык статьи - русский

Ссылка для цитирования: Андреева А.Г., Маркина Т.А. Оценка подобия деревьев с помощью вычисления 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 с.
Информация 2001-2017 ©
Научно-технический вестник информационных технологий, механики и оптики.
Все права защищены.

Яндекс.Метрика