類似したテキストの記事を検索するアルゴリズム

https://stackoverflow.com/questions/246961

05-07-2019
|

質問

データベース内に多数の記事 (タイトル、テキスト付き) があり、質問したときにスタックオーバーフローの「関連質問」のような、最も類似した X 件の記事を見つけるアルゴリズムを探しています。

これについてグーグルで検索してみましたが、他の「類似テキスト」の問題に関するページしか見つかりませんでした。たとえば、すべての記事を他のすべての記事と比較し、類似点をどこかに保存するなどです。SOは、入力したばかりのテキストに対してこれを「リアルタイム」で実行します。

どうやって？

解決

距離の編集は、スペル/単語順であるため、候補とはなりません。検索に実際に関心があるドキュメントのサイズと数を考慮すると、Willよりもはるかに計算コストが高くなります。

Luceneのようなものが道のりです。すべてのドキュメントのインデックスを作成し、特定のドキュメントに類似するドキュメントを検索する場合、特定のドキュメントをクエリに変換し、インデックスを検索します。内部的にLuceneは tf-idf と転置インデックスを使用すると、プロセス全体に、一致する可能性のあるドキュメントの数ではなく、ドキュメントの総数に比例した時間がかかりますコレクション。

他のヒント

類似の定義に依存します。

edit-distance アルゴリズムは（ラテン語）辞書の提案の標準アルゴリズムであり、テキスト全体で機能します。基本的に同じ単語（eh文字）が同じ順序である場合、2つのテキストは似ています。したがって、次の2つの書評はかなり似ています。

1）＆quot;これは素晴らしい本です。 ''

2）＆quot;これらは素晴らしい本ではありません＆quot;

（（2）を（1）にするために削除、挿入、削除、または変更する文字の数を「編集距離」と呼びます。）

これを実装するには、すべてのレビューにプログラムでアクセスします。これはおそらく思ったほどコストがかかりません。コストが高すぎる場合は、比較をバックグラウンドタスクとして実行し、最も類似度の高いものをデータベースフィールド自体に保存できます。

別のアプローチは、（ラテン）言語の構造を理解することです。短い（大文字ではない、または引用された）単語を削除し、一般的または一意の単語（または接頭辞）に重みを割り当てると、ベイジアン様式の比較を行うことができます。次の2つの書評は類似しており、類似していることがわかります。

3）＆quot;フランス革命は何とか戦争と平和と何とかフランスでした。 -＆gt;フランス/フランス語（2）革命（1）戦争（1）平和（1）（フランス語とフランス語を組み合わせるために辞書が使用されていることに注意してください）

4）＆quot;この本は、なんといってもフランス料理の革命です。 -＆gt;フランス（1）革命（1）

これを実装するには、レビューの作成/更新時に「キーワード」を識別し、類似のレビューを見つけるには、クエリのwhere句でこれらのキーワードを使用します（理想的には「フルテキスト」検索データベースはそれをサポートしています）、おそらく、見つかった候補を採点するために結果セットの後処理を行います。

書籍にもカテゴリがあります-フランスで設定されたスリラーは、フランスの歴史研究などに似ていますか？タイトルとテキストを超えたメタデータは、結果の関連性を保つのに役立つかもしれません。

このリンクのチュートリアルは、必要なもののようです。フォローするのは簡単で、非常にうまく機能します。

彼のアルゴリズムは、共通の部分文字列とそれらの部分文字列の共通の順序の両方に報酬を与えるため、同様のタイトルを非常にうまく選択する必要があります。

Apache Lucene 、パフォーマンス、完全にJavaで記述されたフル機能のテキスト検索エンジンライブラリ。これは、フルテキスト検索を必要とするほぼすべてのアプリケーション、特にクロスプラットフォームに適した技術です。インデックスを作成すると、関連する記事を簡単に見つけることができます。

使用される一般的なアルゴリズムの1つは、自己組織化マップです。これは、記事を自動的に分類するニューラルネットワークの一種です。次に、現在の記事がマップ内にあり、その記事に近いすべての記事が関連している場所を簡単に見つけることができます。アルゴリズムの重要な部分は、入力をベクトル量子化する方法です。テキストを扱う方法はいくつかあります。文書/タイトルをハッシュ化し、単語を数え、それをn次元のベクトルなどとして使用できます。AIの無限の旅のPandoraの箱を開いたかもしれませんが、それが役に立てば幸いです。

SOは、質問の本文ではなくタイトルでのみ比較を行うため、短い文字列でのみ比較します。

記事のタイトルとキーワードでアルゴリズムを使用できます（見た目はわかりません）。記事の抄録についても、書き込みのCPU時間を増やすことができます。

Luceneの全文提案の次に、Javaは必須ではないことに注意してください。 .NETポートが利用可能。メインLuceneページも参照してください。 .apache.org / lucy / "rel =" nofollow noreferrer "> Cポートのルーシー。

おそらくあなたが探しているのは、言い換えを行うものです。私はこれについて大まかな知識しか持っていませんが、言い換えることは、自然言語処理の概念であり、テキストのパッセージは実際には同じものを意味しますが、まったく異なる単語を使用する場合があります。

残念ながら、これを可能にするツールは知りません（探してみたいと思いますが）

SQL Serverのフルテキストインデックスを使用してスマートな比較を行うことができます。SOはajax呼び出しを使用し、クエリを実行して同様の質問を返すと思います。

どのテクノロジーを使用していますか

同様に傷ついている単語を探している場合、soundexに変換して、soundexの単語を一致させることができます...私のために働いた

いくつかの方法を試しましたが、どれもうまくいきませんでした。まず、すべてのテキストのすべての段落に対してGoogle SimHashコードを取得し、データベースに保存します。 2番目：SimHashコードのインデックス。 3番目：上記のように比較するテキストを処理し、SimHashコードを取得し、SimHashインデックスですべてのテキストを検索します。これらのテキストは、5〜10のようなハミング距離を形成します。次に、単純性と項ベクトルを比較します。これはビッグデータに対して機能する可能性があります。

次のいずれかを使用できます 1）Minhash / LSH https://en.wikipedia.org/wiki/MinHash

（ http://infolab.stanford.edu/~ullman/も参照してくださいmmds / book.pdf ）

または

2）共同フィルタリング： https://en.wikipedia.org/wiki/Collaborative_filtering

@ alex77 の回答のリンクは、ソーレンセンダイス係数これはその記事の著者が独自に発見したもので、この記事は非常によく書かれており、読む価値があります。

私はこの係数を自分自身のニーズに合わせて使用することになりました。ただし、元の係数では、次の処理を行うときに誤った結果が生じる可能性があります。

1 つのスペルミスを含む 3 文字の単語のペア。例: [and,amd] そして
アナグラムである 3 文字の単語のペア。 [and,dan]

最初のケースでは、Dice は誤って係数 0 を報告しますが、2 番目のケースでは、係数は誤解を招くほど高い 0.5 として表示されます。

改善提案されましたこれは本質的に、単語の最初と最後の文字を取得し、追加のバイグラムを作成することで構成されます。

私の見解では、実際に改善が必要なのは 3 文字の単語についてのみです。長い単語では、他のバイグラムには問題をカバーする緩衝効果があります。この改善を実装したコードを以下に示します。

function wordPairCount(word)
{
 var i,rslt = [],len = word.length - 1;
 for(i=0;i < len;i++) rslt.push(word.substr(i,2));
 if (2 == len) rslt.push(word[0] + word[len]);
 return rslt;
}

function pairCount(arr)
{
 var i,rslt = [];
 arr = arr.toLowerCase().split(' ');
 for(i=0;i < arr.length;i++) rslt = rslt.concat(wordPairCount(arr[i]));
 return rslt;
}

function commonCount(a,b)
{
 var t;
 if (b.length > a.length) t = b, b = a, a = t; 
 t = a.filter(function (e){return b.indexOf(e) > -1;});
 return t.length;
}

function myDice(a,b)
{
 var bigrams = [],
 aPairs = pairCount(a),
 bPairs = pairCount(b);
 debugger;
 var isct = commonCount(aPairs,bPairs);
 return 2*commonCount(aPairs,bPairs)/(aPairs.length + bPairs.length); 
}

$('#rslt1').text(myDice('WEB Applications','PHP Web Application'));
$('#rslt2').text(myDice('And','Dan'));
$('#rslt3').text(myDice('and','aMd'));
$('#rslt4').text(myDice('abracadabra','abracabadra'));

*{font-family:arial;}
table
{
 width:80%;
 margin:auto;
 border:1px solid silver;
}

thead > tr > td
{
 font-weight:bold;
 text-align:center;
 background-color:aqua;
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.0.0/jquery.min.js"></script>
<table>
<thead>
<tr>
<td>Phrase 1</td>
<td>Phrase 2</td>
<td>Dice</td>
</tr>
<thead>
<tbody>
<tr>
<td>WEB Applications</td>
<td>PHP Web Application</td>
<td id='rslt1'></td>
</tr>
<tr>
<td>And</td>
<td>Dan</td>
<td id='rslt2'></td>
</tr>
<tr>
<td>and</td>
<td>aMd</td>
<td id='rslt3'></td>
</tr>
<tr>
<td>abracadabra</td>
<td>abracabadra</td>
<td id='rslt4'></td>
</tr>
</tbody>
</table>

最後の例の意図的なスペルミスに注意してください。アブラカダーブラ vsアブラカバドラ. 。追加のバイグラム補正が適用されていないにもかかわらず、報告される係数は 0.9 です。修正すると 0.91 になります。

これがこのスレッドに遭遇した他の人を助けることを願っています。

サンプルテキストを指定すると、このプログラムは、類似性でソートされたリポジトリテキストを一覧表示します。。このアルゴリズムは、サンプルテキストとリポジトリテキストの合計の長さが線形です。さらに、プログラムはマルチスレッド化されており、リポジトリテキストを並列処理します。

コアアルゴリズムは次のとおりです。

class Statistics {
  std::unordered_map<std::string, int64_t> _counts;
  int64_t _totWords;

  void process(std::string& token);
public:
  explicit Statistics(const std::string& text);

  double Dist(const Statistics& fellow) const;

  bool IsEmpty() const { return _totWords == 0; }
};

namespace {
  const std::string gPunctStr = ".,;:!?";
  const std::unordered_set<char> gPunctSet(gPunctStr.begin(), gPunctStr.end());
}

Statistics::Statistics(const std::string& text) {
  std::string lastToken;
  for (size_t i = 0; i < text.size(); i++) {
    int ch = static_cast<uint8_t>(text[i]);
    if (!isspace(ch)) {
      lastToken.push_back(tolower(ch));
      continue;
    }
    process(lastToken);
  }
  process(lastToken);
}

void Statistics::process(std::string& token) {
  do {
    if (token.size() == 0) {
      break;
    }
    if (gPunctSet.find(token.back()) != gPunctSet.end()) {
      token.pop_back();
    }
  } while (false);
  if (token.size() != 0) {
    auto it = _counts.find(token);
    if (it == _counts.end()) {
      _counts.emplace(token, 1);
    }
    else {
      it->second++;
    }
    _totWords++;
    token.clear();
  }
}

double Statistics::Dist(const Statistics& fellow) const {
  double sum = 0;
  for (const auto& wordInfo : _counts) {
    const std::string wordText = wordInfo.first;
    const double freq = double(wordInfo.second) / _totWords;
    auto it = fellow._counts.find(wordText);
    double fellowFreq;
    if (it == fellow._counts.end()) {
      fellowFreq = 0;
    }
    else {
      fellowFreq = double(it->second) / fellow._totWords;
    }
    const double d = freq - fellowFreq;
    sum += d * d;
  }
  return std::sqrt(sum);
}

抄録間の類似性を比較する最も簡単で最速の方法は、おそらく集合概念を利用することです。まず、抽象的なテキストを単語のセットに変換します。次に、各セットがどの程度重複しているかを確認します。 Pythonのセット機能は、このタスクを非常に手作業で実行します。この方法がこれらの「類似/関連論文」と比較してどれだけ優れているかを見て驚くでしょう。 GScholar、ADS、WOS、またはScopusが提供するオプション。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow