0

目前我正在为最后一个学期做我的项目/论文，我想在“检测网络中的网页变化”上做这件事。我已经阅读了两篇关于这个主题的论文，但我有一些困惑

1.在一篇题为

一种增强的网页变化检测算法及应用加速移动网页转码1

这个已经写完了

首先从 HTML 文档生成子树，其中每个子树根据其标记内容被赋予一个标记。

我的问题是如何从 HTML 文档生成子树？这样做的技术是什么。下一个问题是“根据标签内容打分”是什么意思。

2.请看这里的图片！！拟议方法的总图

在“计算最相似的子树”框中，匹配是如何完成的？在另一篇题为

基于优化匈牙利算法的高效网页变化检测系统[2]

匹配使用匈牙利算法，引用论文中的一句话，题为

一种基于散列和减少相似度计算次数的快速 HTML 网页变化检测方法 [3]

[2] 中的方法使用 O(N 3 ) 匈牙利算法来计算加权二分图上的最大加权匹配，并且运行时间为 O(N 2 x N 1 3 ) ，其中 N 1和 N 2是，分别是旧页面和新（更改）页面中的节点数。” 我的问题是，由于子树正在形成为什么要添加权重，以及如何添加它们？

感谢您阅读我的问题/困惑，我真的需要帮助，很快，请任何人帮助我解决这个问题，我将永远感激不尽。

4

2 回答 2

0

首先可以使用Java 的文档对象模型(DOM) API 来实现。然而，DOM 模型的速度和内存效率都不是很高，但它几乎可以完美地满足您的需求。

已经有 HTML-to-DOM 解析器，我个人向您推荐Cobra HTML 渲染器和解析器。您不需要它的呈现功能，但它有一个单独且非常易于使用的解析机制 - 只需创建一个新的DocumentBuilderImpl并将页面内容输入流或页面的 URL 传递给它的parse()方法。

在第二个问题上，看看所谓的“树相似性算法”，例如在这个

于 2011-04-23T06:33:43.957 回答
0

我认为我有一个非常简单快捷的方法来做到这一点。

我最近编写并发布了用于计算树编辑距离近似值的 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 来应对您的特定挑战的开始，我直接从 github 上的 README 中取出。要回答您的问题之一，您可以在 jQuery 等库（如下所示）中使用 DOM 作为其自己的树结构，或者复制它或从 Cheerio 或其底层 HTML 解析库或其任何组合中的 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 参数指定每棵树应如何独立确定每个树根的节点标签名称和子数组，以便您可以将 DOM 与 JSON 对象或其他使用不同语义来指定子节点和什么是节点标签。另请注意，在此示例中，我利用了 DOM 实体类属性，将其拆分为各个类，并将 DOM 节点本身的 id 作为节点的直接子节点，以便更清楚地了解两棵树是非常相似还是非常不同. 您可以扩展它以包含您自己的属性。或者，您也可以修改每棵树的 lfn 函数以在标签中包含 id，例如“tagname:id”

所以总结一下，你需要做的就是提供这些 lfn 和 cfn 函数以及每个根，jqgram 将完成其余的工作，调用 lfn 和 cfn 函数来构建树。

jqgram 实现的 PQ-Gram 算法将编辑距离作为一个介于 0 和 1 之间的数字提供，并且应该注意，零值并不一定表示绝对相等，只是两棵树非常相似。如果您需要继续确定 jqgram 确定的两个非常相似的树是否确实相同，您可以使用 Zhang 和 Shasha，但是使用 jqgram 获取指标将为您节省大量计算，这在客户端浏览器中变得非常重要终端用户性能显然很重要的应用程序。

希望有帮助！

于 2013-06-15T18:01:48.427 回答