Я думаю, что у меня действительно простой и быстрый способ сделать это.
Я недавно написал и выпустил jqgram для вычисления расстояния редактирования дерева аппроксимация с простым в использовании API длясравнение DOM-подобных структур, JSON-структур или древовидных структур вашего собственного дизайна:
https://github.com/hoonto/jqgram
На основе оригинальной статьи: http://www.vldb2005.org/program/paper/wed/p301-augsten.pdf Изначально портировано из реализации Python: https://github.com/Sycondaman/PyGram
Модуль аппроксимации расстояния редактирования дерева jqgram реализует алгоритм PQ-Gram для приложений как на стороне сервера, так и на стороне браузера;O (n log n) время и O (n) пространство, где n - количество узлов.Аппроксимация PQ-Gram намного быстрее, чем получение истинного расстояния редактирования с помощью Zhang & Shasha, Klein, Guha или других, которые предоставляют алгоритмы истинного расстояния редактирования, которые работают в лучшем случае O (n ^ 2) или O (n ^ 3) в зависимости отпо какому алгоритму вы смотрите.
Вот начало того, как я буду использовать jqgram для вашей конкретной задачи, которую я взял прямо из README на github.Чтобы ответить на один из ваших вопросов, вы можете использовать DOM в качестве своей собственной древовидной структуры в библиотеке, такой как jQuery (как показано ниже), или реплицировать ее или сгенерировать ее из строки html в Cheerio или из его базовой библиотеки синтаксического анализа HTML или любой их комбинации.(jqgram предоставляет вам эту гибкость).В этом примере сравнивается DOM на текущей странице с представлением Cheerio, сгенерированным из строки - вашей известной ссылки.
// This could probably be optimized significantly, but is a real-world
// example of how to use tree edit distance in the browser.
// For cheerio, you'll have to browserify,
// which requires some fiddling around
// due to cheerio's dynamically generated
// require's (good grief) that browserify
// does not see due to the static nature
// of its code analysis (dynamic off-line
// analysis is hard, but doable).
//
// Ultimately, the goal is to end up with
// something like this in the browser:
var cheerio = require('./lib/cheerio');
// But you could use jQuery for both sides of this comparison in which case your
// lfn and cfn callback functions become the same for both roots.
// The easy part, jqgram:
var jq = require("../jqgram").jqgram;
// Make a cheerio DOM:
var html = '<body><div id="a"><div class="c d"><span>Irrelevent text</span></div></div></body>';
var cheeriodom = cheerio.load(html, {
ignoreWhitespace: false,
lowerCaseTags: true
});
// For ease, lets assume you have jQuery laoded:
var realdom = $('body');
// The lfn and cfn functions allow you to specify
// how labels and children should be defined:
jq.distance({
root: cheeriodom,
lfn: function(node){
// We don't have to lowercase this because we already
// asked cheerio to do that for us above (lowerCaseTags).
return node.name;
},
cfn: function(node){
// Cheerio maintains attributes in the attribs array:
// We're going to put id's and classes in as children
// of nodes in our cheerio tree
var retarr = [];
if(!! node.attribs && !! node.attribs.class){
retarr = retarr.concat(node.attribs.class.split(' '));
}
if(!! node.attribs && !! node.attribs.id){
retarr.push(node.attribs.id);
}
retarr = retarr.concat(node.children);
return retarr;
}
},{
root: realdom,
lfn: function(node){
return node.nodeName.toLowerCase();
},
cfn: function(node){
var retarr = [];
if(!! node.attributes && !! node.attributes.class && !! node.attributes.class.nodeValue){
retarr = retarr.concat(node.attributes.class.nodeValue.split(' '));
}
if(!! node.attributes && !! node.attributes.id && !! node.attributes.id.nodeValue) {
retarr.push(node.attributes.id.nodeValue);
}
for(var i=0; i<node.children.length; ++i){
retarr.push(node.children[i]);
}
return retarr;
}
},{ p:2, q:3, depth:10 },
function(result) {
console.log(result.distance);
});
Обратите внимание, что параметры lfn и cfn указывают, как каждое дерево должно определять имена меток узлов имассив children для каждого корня дерева независимо, так что вы можете сравнить DOM с объектом JSON или чем-то еще, что использует другую семантику для определения дочерних и меток узлов.Также обратите внимание, что в этом примере я использую атрибут класса сущности DOM, разделяя его на отдельные классы и идентификатор самого узла DOM как непосредственных дочерних элементов узла, чтобы прояснить, являются ли два дерева очень похожими или очень разными,Вы можете расширить это, чтобы включить ваши собственные атрибуты.Или вы можете также изменить функции lfn для каждого дерева, чтобы включить идентификатор в метку, например «tagname: id» - это зависит от вас и изменит работу алгоритма - возможно, что-то интересное для исследования в вашем исследовании.
Таким образом, чтобы подвести итог, все, что вам нужно сделать, это предоставить эти функции lfn и cfn вместе с каждым корнем, а jqgram сделает все остальное, вызывая функции lfn и cfn для построения деревьев.
Алгоритм PQ-Gram, реализованный jqgram, предоставит расстояние редактирования в виде числа от нуля до единицы, и следует отметить, что значение нуля не обязательно указывает на абсолютное равенство, только то, что два дерева оченьаналогичный.Если вам нужно определить, действительно ли два очень дерева, как определено с помощью jqgram, действительно идентичны, вы можете использовать Чжан и Шашу, но использование jqgram для получения метрики сэкономит вам массу вычислений, которые становятся чрезвычайно сложными.критически важен в клиентских браузерных приложениях, где производительность конечного пользователя явно важна.
Надеюсь, это поможет!