これを行うには、本当に簡単で迅速な方法があると思います。
私は最近、DOM のような構造、JSON 構造、または独自の設計のツリー構造を比較するための使いやすい API を使用してツリー編集距離の近似値を計算するための jqgram を作成してリリースしました。
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 などを介して真の編集距離を取得するよりもはるかに高速です。あなたが見ているアルゴリズム。
これは、github の README から直接取り出した、特定の課題に jqgram を使用する方法の始まりです。質問の 1 つに答えるには、jQuery などのライブラリで DOM を独自のツリー構造として使用するか (以下に示すように)、それを複製するか、Cheerio またはその基礎となる HTML 解析ライブラリの html 文字列から 1 つを生成するか、またはそれらの任意の組み合わせを使用できます。 (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 パラメーターは、各ツリーがノード ラベル名と各ツリー ルートの子配列を個別に決定する方法を指定することに注意してください。これにより、DOM を JSON オブジェクトまたは子とは何かを指定するために異なるセマンティクスを使用する何かと比較できます。ノード ラベルとは。この例では、2 つのツリーが非常に似ているか非常に異なっているかをより明確にするために、DOM エンティティ クラス属性を使用して、それを個々のクラスに分割し、DOM ノード自体の ID をノードの直接の子として使用していることにも注意してください。 . これを拡張して、独自の属性を含めることができます。または、各ツリーの lfn 関数を変更して、「tagname:id」のようにラベルに ID を含めることもできます。
要約すると、これらの lfn 関数と cfn 関数を各ルートと共に提供するだけで、残りは jqgram が実行し、lfn 関数と cfn 関数を呼び出してツリーを構築します。
jqgram によって実装された PQ-Gram アルゴリズムは、編集距離を 0 から 1 の間の数値として提供します。値 0 は必ずしも絶対的な同等性を示すわけではなく、2 つのツリーが非常に類似していることのみを示すことに注意してください。jqgram によって決定された2 つの非常に類似したツリーが実際に同一であるかどうかを判断する必要がある場合は、Zhang と Shasha を使用できますが、jqgram を使用してメトリックを取得すると、クライアント側のブラウザーで非常に重要になる大量の計算を節約できます。エンドユーザーのパフォーマンスが明らかに重要なアプリケーション。
それが役立つことを願っています!
