3

剽窃について次の生成モデルを仮定します。

剽窃者: 1. テキストの一部を削除します。 2. テキストの一部を再配置します。 3. 新しいテキストを追加します。

元。ABCD が元のテキストである場合 (A、B、C、および D は段落または文の束である可能性があります)、出力は DEAFCG であり、E、F、および G は追加のテキストです。

また、剽窃者は小さなエラー (小さな割合での挿入、置換、および削除) を追加しようとしています。

この剽窃のインスタンスを検出するにはどうすればよいでしょうか?

これまでに行ったこと: 最長共通部分列法を使用してみました。一致したテキストの 1 つの線形セットを検出します。上記の例では、D または AC のいずれかを検出します (長さによって異なります)。

必要なもの: この問題に対処する原則的な方法。既存の文献への引用は非常に役に立ちます。アイデアの擬似コードも良いです。コードはありません。

これは宿題でも、面接の質問でもありません。私は実際の問題をこのおもちゃっぽい問題に単純化しました。

4

1 に答える 1

0

多数のアプリケーションでこれを行うためのアルゴリズムが多数あります。私が知る限り、彼らが主に行っていること (そしてあなたがやりたいこと) は編集距離を計算することです: http://en.wikipedia.org/wiki/Edit_distance

http://en.wikipedia.org/wiki/Levenshtein_distance#Relationship_with_other_edit_distance_metricsによると、わずかに異なるさまざまなアルゴリズムがいくつかあります 。

たとえば、最長共通サブシーケンスは追加と削除を処理しますが、置換は処理しません。Damerau-Levenshtein 距離では、隣接する文字の置換だけでなく、置換も考慮されます。

于 2013-04-10T22:04:33.967 に答える