3

基本ケースと付属ケースの違いを特定しようとしています。パーセンテージなどで類似性を教えてくれるライブラリを探しています。

例えば:

私は10個の異なるHTMLページを持っています。※いずれも404応答でランダムコード2行のみ(時刻や今日の名言など)。

ここで、新しい 404 ページを提供すると、「%80」と同様の結果が返されますが、別のページを提供すると、まったく異なる、または同じ Web サイトであるが、コンテンツがまったく異なる場合、「%20 類似」のようなものを取得する必要があります。

基本的に私がやりたいことは、新しい応答を受け取ったときに、新しい応答が以前に提供したこれらの 10 ページに似ているかどうかを識別したいということです。

私はこれを .NET で解決しようとしています。ライブラリまたはアルゴリズムの推奨事項は素晴らしいでしょう。

4

7 に答える 7

1

差分ツールを使用する代わりに、コピー/貼り付け検出器 (cpd) を使用できます。次に、ファイルの類似度のしきい値を構成できます。

余談ですが、私は過去にこれらを使って学校の不正行為者を追跡しました.

サム

于 2008-09-20T11:37:01.677 に答える
1

文字列ベースのソリューションを使用する場合は、k グラムを使用してショットを与えることができます (両方のファイルの連続した文字の長さ k のすべての文字列を計算し、結果のセットに対して Jaccard 距離を実行します)。これは、DB の世界で近似クエリを実行する標準的な方法です。

HTMLファイルに埋め込まれた階層情報にもっと興味がある場合(たとえば、変更不可能なセクションについて話していた場合)、それをxhtmlに変換できます(Javaの場合、http://htmlcleaner.sourceforge.net/がありますが、私はそうではありません.netに入れますが、そのenvにもいくつかの選択肢があると思います)、順序付けされたラベル付きツリーとして生成されたファイルを見て、pq-gramsを使用できます( http://www.inf.unibz.it/~augsten/publ/tods10 /紙とJavaコードの場合)構造の類似性を評価します(pq-gramは文字列k-gramのツリー一般化です)。

この時点で、必要に応じて、テキストを含む葉でハッシュベースの比較を実行するか、この葉に k-gram を使用し、残りに構造 pq-gram ベースの類似性を使用できます。

于 2012-04-04T15:32:17.857 に答える
0

手っ取り早い方法は、マークアップのレーベンシュタイン距離を計算することです。

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

于 2008-09-20T11:00:58.470 に答える
0

あなたのタスクでは、コマンド ライン diff ユーティリティを実行して結果を分析するだけで十分です。

あるいは、 LCSアルゴリズムを実装する必要がありますが、私にとってはやり過ぎです。

于 2008-09-20T11:05:22.250 に答える
0

あなたのタスクでは、コマンド ライン diff ユーティリティを実行して結果を分析するだけで十分です。

これは 1 回限りの作業ではありません。アプリケーションに統合されたソリューションが必要です。

そして、diff には独自の問題があります。なぜなら、5 ページを処理し、常に変化するビットを無視するように diff に指示することができないからです。

これらの部分は大きくなる可能性があり、2kb の標準テキストが変化し続ける可能性があります。そして、差分の観点からは大きな変更だと思いますが、私の観点からは、1つのセクションの変更にすぎません(他の9つのファイルすべてで変更されることがわかっているため、完全に無視する必要があります)。

差分ライブラリでそれができるかもしれませんが、私はそのようなライブラリを知りません。

于 2008-09-20T11:13:10.203 に答える
0

この問題を具体的に解決するために、PQ-Gram ツリー編集距離近似の実装である jqgram を使用できますが、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 に答える
0

私が使用する基本的なアルゴリズム:

古いページと新しいページの両方のページのテキスト コンテンツを解析します。解析するときに、後で使用するために処理されたバイト数を追跡​​して、変更された % の数を特定します。両側に完全なストーリーがあるので、同一性のアンカーポイントを構築します. あなたが持っているすべての同一点について、それを前後に拡張してみてください。相違点として、同一性アンカー ポイント間のギャップを特定します。特定したすべての差分ギャップをループし、それらのバイト数を合計します。総量差分バイト数とストーリーの総バイト数 (前に計算したもの) を使用して、差分の割合を計算します。

于 2008-09-20T11:53:49.980 に答える