テキストの類似性のためのアルゴリズム/ライブラリ

Question

テキストの類似性の評価のためにアルゴリズムを実装する必要があります（またはオープンソースライブラリで1つを見つける必要があります）。私はそれらの間で一致するペアを作成するために、2つの任意のドキュメントセット（比較的小さなテキストの大きなチャンク）に対して効率的なアルゴリズムが必要です。どちらのドキュメントがどのドキュメントから生成される可能性が最も高いですか。

私はこれを2つに分割すると思います - 各ペアの類似性係数を定義し、次に割り当て問題アルゴリズムのいくつかを適用します。私は割り当てアルゴリズムのために私は良い数の解決策を見つけることができますが、類似度係数を計算するための良いものは見つけられません。

文書が事前にわかっていないことに注意してください。テキストの計算インデックス（存在する場合）は高速でなければなりません。

私はハミング距離、Levenshtein距離の文字列の違いのための他のアルゴリズムのいくつかを認識しています。これは私が探しているものではありません - 私は目的の文字列の代わりにテキストという単語を使用しています。

私はフレーズ検索アルゴリズムと、LuceneやXapianのようなライブラリが作られているのを探していません（少なくともそうであるようです）。

おそらくtf-idfに基づくものです。

私は疑問に思うのですが、すでにこの問題を解決しているのでしょうか、それを行うためにluceteのようなライブラリを使用することが可能でしょうか。ここで

Answer 1

は（それは、シンプルで早いのが特長ですという理由だけで）私は出発点としてどうなるのかです：

• 構築、各テキストについて共有マップやhash_map
• を使用して数値への言葉の地図単語レベルのトライグラムの対応するマップは
• は重複を比較カウント

私たちは、辞書サイズが< 1メートル（または21bit）であると仮定することができますので、我々はただでにトライグラムをエンコードすることができますt64。

void CountTrigrams(const vector<string>& words, 
        map<string, int> * dict, 
        map<int64, int> * result) { 
    int64 trigram = 0; 
    for (int i = 0; i < words.size(); i++) { 
    const& word = words[i]; 
    int id; 
    auto di = dict->find(word); 
    if (di == dict->end()) { 
     id = dict.size(); 
     dict[word] = id; 
    } else { 
     id = di->second; 
    } 
    trigram = ((trigram << 21) | id) & 0x7fffffffffffffff; 
    if (i > 2) { 
     auto ti = result->find(trigram); 
     if (ti == result->end()) { 
     result[trigram] = 1; 
     } else { 
     ti->second++; 
     } 
    } 
    } 
} 

次に、各ペアの結果を比較する：

int Compare(const map<int64, int> & t1, const map<int64, int> & t2) { 
    int score = 0; 
    for (auto i = t1.first(); i != t1.end(); i++) { 
    auto j = t2.find(t1->first); 
    if (j != t2.end()) { 
     score += MAX(i->second, j->second); 
    } 
    } 
    return score; 
} 

それは例えば、何とかスコアを正規化するために意味をなすことができますトライグラムの総数で割ります。