string - 似た文章の記事を探すアルゴリズム

Question

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

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

どのように？

score 34 · Accepted Answer

編集距離は、スペル/語順に依存する可能性があり、実際に検索するドキュメントのサイズと数を考慮すると、ウィルが信じさせるよりもはるかに計算コストがかかるため、候補にはなりません。

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

score 14 · Accepted Answer

それはあなたの類似の定義に依存します。

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

1) 「これは素晴らしい本です」

2) 「これらは素晴らしい本ではない」

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

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

別のアプローチは、(ラテン) 言語の構造の一部を理解することです。短い (大文字または引用されていない) 単語を取り除き、一般的または固有の単語 (または接頭辞) に重みを割り当てると、ベイズ風比較を行うことができます。次の 2 つの書評は、単純化して類似している可能性があります。

3) 「フランス革命は何とか戦争と平和だった。何とかフランスだ。」-> France/French(2) Revolution(1) War(1) Peace(1) (フランスとフランス語を組み合わせるために辞書が使用されていることに注意してください)

4) 「この本はフランス料理の革命です。」-> フランス(1) 革命(1)

これを実装するには、レビューが作成/更新されたときにレビューの「キーワード」を特定し、同様のレビューを見つけるためにクエリの where 節でこれらのキーワードを使用します (データベースがサポートしている場合は理想的には「全文検索」 )、おそらく、見つかった候補をスコアリングするための結果セットの後処理を行います。

本にもカテゴリがあります。フランスを舞台にしたスリラーは、フランスの歴史研究に似ていますか。タイトルやテキスト以外のメタデータは、結果の関連性を維持するために役立つ場合があります。

score 10 · Accepted Answer

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

彼のアルゴリズムは、共通の部分文字列とそれらの部分文字列の共通の順序の両方に報酬を与えるため、類似したタイトルをうまく選択するはずです。

score 3 · Accepted Answer

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

score 3 · Accepted Answer

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

score 2 · Accepted Answer

フルテキストの Lucene の提案を支持しますが、java は必須ではないことに注意してください。.NET ポートが利用可能です。C ポートである Lucyを含む他のプロジェクトへのリンクについては、メインの Lucene ページも参照してください。

score 2 · Accepted Answer

たぶん、あなたが探しているのは、言い換えを行うものです。私はこれについて大雑把な知識しか持っていませんが、言い換えは、テキストの 2 つのパッセージが実際に同じことを意味するかどうかを判断するための自然言語処理の概念です。

残念ながら、これを可能にするツールを私は知りません (見つけたいとは思いますが)。

score 2 · Accepted Answer

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

記事のタイトルとキーワードにアルゴリズムを使用できます (それがどのように見えるかはわかりません)。燃焼するCPU時間がもっとある場合は、記事の要約にも。

score 1 · Accepted Answer

以下を使用できます

ミンハッシュ/LSH https://en.wikipedia.org/wiki/MinHash

( http://infolab.stanford.edu/~ullman/mmds/book.pdf Minhash の章も参照)、最新技術についてはhttp://ann-benchmarks.com/も参照

ユーザーが記事とやり取りした情報 (クリック/いいね/ビュー) がある場合の協調フィルタリング: https://en.wikipedia.org/wiki/Collaborative_filtering
「セマンティック」ベクトル空間で記事を比較するための word2vec または同様の埋め込み: https://en.wikipedia.org/wiki/Word2vec
潜在意味分析: https://en.wikipedia.org/wiki/Latent_semantic_analysis
Bag-of-words を使用し、Jaccard 係数などの距離尺度を適用してセットの類似度を計算します https://en.wikipedia.org/wiki/Jaccard_index、https://en.wikipedia.org/wiki/Bag-of-words_model

score 1 · Accepted Answer

同様に巻かれた単語を探している場合は、soundex に変換し、soundex の単語を一致させることができます...私にとってはうまくいきました

score 1 · Accepted Answer

いくつかの方法を試しましたが、どれもうまくいきませんでした。次のような比較的満足のいく結果が得られるかもしれません。2 番目: SimHash コードのインデックス。3 番目: 上記のようにテキストを処理して比較し、SimHash コードを取得して、5-10 のようなハミング距離を形成する SimHash インデックスですべてのテキストを検索します。次に、項ベクトルと類似性を比較します。これはビッグデータに有効かもしれません。

score 0 · Accepted Answer

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

score 0 · Accepted Answer

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

どのような技術を使用していますか?

string - 似た文章の記事を探すアルゴリズム

15 に答える 15

Related

Reference