4

次の状況があります。

String a = "Web クローラーは、World Wide Web インターネットを自動的に閲覧するコンピューター プログラムです"; String b = "Web Crawler コンピュータ プログラムが World Wide Web をブラウズ";

類似度を計算するためのアイデアや標準アルゴリズムはありますか?

たとえば、上記のケースでは、手動検索で推定された類似性は 90%++ である必要があります。

私の考えは、両方の文字列をトークン化し、一致したトークンの数を比較することです。(7 トークン / 1 0 トークン) * 100 のようなものですが、もちろん、この方法ではまったく効果がありません。一致した文字数の比較も効果がないようです....

誰でもガイドラインを教えてもらえますか???

上記は私のプロジェクト、Plagiarism Analyzer の一部です。

したがって、一致する単語は同義語なしでまったく同じになります。

この場合の唯一の問題は、類似性の非常に正確なパーセンテージを計算する方法です。

助けてくれてありがとう。

4

6 に答える 6

5

Konrad が指摘したように、あなたの質問は、「類似」の意味に大きく依存します。一般的に、次のガイドラインが役立つはずです。

  • 単語をその基本形に減らして小文字にすることにより、入力を正規化します
  • 単語の頻度リスト (Web で簡単に入手可能) を使用し、単語の「類似性関連性」を頻度リスト上の位置に反比例させる
  • 両方の文に出現する単語の類似度の合計を、文の類似度の合計で割ったものとして、文の類似度の合計を計算します。

単語の形、文の語順、同義語リストなどの違いを含めるようにテクニックを改良できます。完璧な結果が得られることはありませんが、多くの微調整の可能性があり、一般的に非常に価値のある類似性の尺度が得られると思います。 .

于 2010-03-06T16:34:17.770 に答える
4

それはあなたの類似性の考え方に依存します。正式には、統計を適用するために、「類似」文字列と見なすもののメトリックを定義する必要があります。通常、これは仮説的な質問によって行われます。「最初の文字列が、最初の文字列の修正バージョンであり、エラー (たとえば、入力による) が導入された可能性はどのくらいありますか?」</p>

このような類似性 (またはその逆) の非常に単純で効果的な尺度は、動的計画法を使用して計算できる 2 つの文字列の編集距離です。これには、一般にO ( nm ) の時間がかかります。ここで、 nmは文字列の長さです。文字列。

使用状況によっては、より複雑な測定 (またはsoundex メトリックなどのまったく無関係の測定) が必要になる場合があります。

あなたの場合、トークンの一致 (つまり、単なる単語数) を直接適用すると、90% を超える類似性が得られることはありません。意味のある方法でこのような高い類似性を取得するには、高度な意味分析が必要です。これが完了したら、論文を公開してください。これはまだほとんど解決されていない問題です。

于 2010-03-06T16:01:46.730 に答える
2

コンラッド・ルドルフがすでに言ったことに賛成です。

他の人は、異なる距離メトリックを推奨する場合があります。私が言おうとしていることはそれらに付随していますが、セマンティクスのマッチングの問題にもっと目を向けています。

あなたが探していると思われるものを考慮して、標準的なテキスト処理方法のいくつかを適用することをお勧めします. これらはすべて潜在的な失敗を伴うため、アプリケーションとうまく実行するのが難しい順にリストします。

  1. 文の分割。比較の単位を把握します。
  2. ストップワードの削除: a、an、the、of などを削除します。
  3. bag of words パーセンテージ: 順序に関係なく、単語全体の何パーセントが一致するか
  4. (はるかに攻撃的) 同義語を一致した単語としてカウントする同義語展開を試すことができます。
于 2010-03-06T16:10:29.317 に答える
1

この質問の問題は、類似性が人間化された類似性(「+- 90%の類似性」と言うように)または統計的類似性(コンドラッド・ルドルフの答え)のいずれかである可能性があることです。

人間の類似性は決して簡単に計算することはできません: たとえば、これらの 3 つの単語

cellphone car message

mobile automobile post

統計的類似性は非常に低いですが、実際にはかなり似ています。したがって、この問題を解決するのは難しいでしょう。私が指摘できるのは、ベイジアン フィルタリングまたはベイジアン ネットワークを使用した人工知能だけです。

于 2010-03-06T16:10:12.987 に答える
1

一般的な尺度の 1 つは、文字列編集距離の特殊なケースであるレーベンシュタイン距離です。apache string utilライブラリにも含まれています。

于 2010-03-06T16:12:08.143 に答える
0

Longest Common Sub-sequenceは、文字列非類似度メトリックとしてよく知られており、動的プログラミングで実装されています。

于 2010-03-06T16:07:56.580 に答える