3

我正在尝试确定基本案例和提供的案例之间的差异。寻找一个图书馆来告诉我百分比或类似的相似性。

例如：

我有 10 个不同的 HTML 页面。* 都是 404 响应，只有一个 2 行随机代码（例如时间或当天的报价）。

现在，当我提供一个新的 404 页面时，我希望返回类似“%80”的结果，但是如果我提供另一个完全不同或相同网站但内容完全不同的页面，我应该得到一些“%20 相似”的结果。

基本上我想要做的是，当我得到一个新的回复时，我想确定新的回复是否与我之前提供的这 10 页相似。

我正在尝试在 .NET 中解决这个问题，库或算法推荐会很棒。

4

7 回答 7

1

您可以使用复制/粘贴检测器 (cpd)，而不是使用差异工具。然后，您可以配置您希望文件有多相似的阈值。

顺便说一句，我过去曾用这些来追踪学校里的作弊者。

山姆

于 2008-09-20T11:37:01.677 回答
1

如果您想使用基于字符串的解决方案，您可以使用 k-gram 进行尝试（您计算两个文件的所有长度为 k 的连续字符的字符串，然后对结果集执行 Jaccard 距离）。这是在数据库世界中执行近似查询的标准方法。

如果您对嵌入到 html 文件中的分层信息更感兴趣（例如，您正在谈论一个不可变的部分），您可以将其转换为 xhtml（对于 java，您有http://htmlcleaner.sourceforge.net/，我不是进入.net，但我认为该环境也有几种选择），看到生成为有序标记树的文件，您可以使用 pq-grams（http://www.inf.unibz.it/~augsten/publ/tods10 /用于纸和 java 代码）来评估结构相似性（pq-grams 是字符串 k-grams 的树泛化）。

此时，如果您愿意，您可以对包含文本的叶子执行基于哈希的比较，或者对这个叶子使用 k-gram，对其余部分使用基于结构 pq-gram 的相似性。

于 2012-04-04T15:32:17.857 回答
0

一种快速而肮脏的方法是计算标记的 Levenshtein 距离。

http://en.wikipedia.org/wiki/Levenstein_distance

于 2008-09-20T11:00:58.470 回答
0

对于您的任务，运行命令行 diff 实用程序并分析结果就足够了。

或者，您需要实现LCS算法，但对我来说这将是一个矫枉过正。

于 2008-09-20T11:05:22.250 回答
0

对于您的任务，运行命令行 diff 实用程序并分析结果就足够了。

这真的不是一次性的工作，我需要一个集成到应用程序中的解决方案。

diff 在这里有它自己的问题，因为我不能告诉 diff 处理 5 个页面并忽略那些不断变化的位。

这些部分可以很大，可以2kb的标准文本不断变化。而且我认为从差异的角度来看，这是一个很大的变化，但是从我的角度来看，这只是一个部分的更改（已知在所有其他 9 个文件中都会更改，因此应该完全忽略）。

也许差异库可以做到这一点，但我不知道这样的库。

于 2008-09-20T11:13:10.203 回答
0

我会使用的基本算法：

解析新旧两边页面的文本内容。当您解析时，请跟踪已处理的字节数，以便稍后使用以确定有多少 % 已更改。现在你在每一边都有完整的故事，建立相同的锚点。对于你所拥有的每一个相同的锚点，尝试向前和向后扩展它。将您的相同锚点之间的任何差距确定为差异。遍历您确定的每个差异差距并总结它们的字节数。通过使用总数量差异字节数和故事的总字节（您之前计算的那个）来计算您的差异百分比。

于 2008-09-20T11:53:49.980 回答
0

您可以使用 jqgram，一种 PQ-Gram 树编辑距离近似的实现来专门解决此问题，但如果您不想移植到 C#，则需要运行 Node.js。不过，端口应该很容易......算法并不是那么复杂。简约中的美。

https://github.com/hoonto/jqgram

在这个例子中是一个 DOM 与 Cheerio 的例子，它展示了如何处理子元素和标签以生成近似的树编辑距离。结果，它为您提供了一个介于 0 和 1 之间的数字，这就是您的百分比相等。但请注意，零值不一定表示相同的树，它仅表示它们非常相似。您也可以轻松地进行 DOM 与 DOM 比较或 Cheerio 与 Cheerio - 或使用 Cheerio 使用的 HTML 解析，而不用担心使用整个库（开箱即用的 Cheerio 是一个相当快的服务器端 jQuery 和类似 DOM执行）。

所以显然这个解决方案是特定于 Node.js 和浏览器 javascript 的，但我认为这些挑战可能比移植到 C#/.NET 更容易。

// 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'); 

// 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);
});
于 2013-06-15T17:33:51.080 回答