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

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

Аннотация:

Представлен алгоритм оценки подобия иерархических данных на основе вычисления pq-грамм расстояния. Выполнен анализ чувствительности алгоритма от выбранных параметров p и q. Показано, насколько сильно будет изменяться результат работы алгоритма при сравнении двух деревьев, имеющих различие в одном произвольном узле, когда один из узлов исходного дерева удален, переименован, либо добавлен лишний узел. Продемонстрировано, что подобный анализ позволяет подобрать параметры pи qприменительно к решаемой задаче. Обоснована задача предварительной оценки дерева – приближенный анализ начального уровня расхождений узлов в выбранных pq-граммах сравниваемых деревьев. Обозначены основные термины и определения, относящиеся к алгоритмам обработки древовидных структур данных, а также непосредственно к самому рассматриваемому алгоритму. Приведены примеры, иллюстрирующие практическое использование алгоритма, показаны детали реализации алгоритма на реальной задаче.

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

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