per la somiglianza del testo

Question

Devo implementare l'algoritmo (o trovarne uno in una libreria open source) per la valutazione delle somiglianze di testo. Ho bisogno di un algoritmo efficiente per avere due serie arbitrarie di documenti (un numero relativamente piccolo di grossi pezzi di testo) per creare una coppia di corrispondenza tra loro - quale documento è più probabile che venga prodotto da quale.

Credo che dividerò questo in due - definendo il coefficiente di somiglianza di ogni coppia - e quindi applicando alcuni algoritmi di problemi di assegnazione. Mentre per gli algoritmi di assegnazione riesco a trovare un buon numero di soluzioni non riesco a trovarne una buona per il calcolo dei coefficienti di similarità.

Nota: i documenti non sono noti in anticipo: anche gli indici di calcolo del testo (se presenti) devono essere veloci.

Sono consapevole della distanza di Hamming, Levenshtein distanzia alcuni degli altri algoritmi per la differenza di stringa. Questo non è quello che sto cercando però - sto usando la parola text invece string di proposito.

Non sono interessato agli algoritmi di ricerca di frasi e alle librerie come Lucene e Xapian (almeno sembra).

Probabilmente qualcosa basato su tf-idf.

Suppongo che la domanda sia, c'è qualcosa che risolve già questo problema o è possibile che librerie come lucete siano utilizzate per farlo.

Answer 1

Ecco cosa farei come punto di partenza (solo perché è semplice e veloce):

• mappare le parole di numeri usando una mappa condivisa o hash_map
• Per ogni testo, costruire il corrispondente mappa di-livello di parola trigramma conta
• Confrontare la sovrapposizione

possiamo supporre che la dimensione del dizionario è < 1m (o 21bit), in modo che possiamo solo codificare un trigramma in un a 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++; 
     } 
    } 
    } 
} 

poi confrontare i risultati per ciascuna coppia:

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; 
} 

Può avere senso normalizzare il punteggio in qualche modo, ad esempio dividere per il numero totale di trigrammi.