algorytm/biblioteka podobieństwa tekstu

Question

Potrzebuję wdrożyć algorytm (lub znaleźć w bibliotece open source) do oceny podobieństw tekstu. Potrzebuję skutecznego algorytmu dla dwóch dowolnych zestawów dokumentów (względnie niewielkiej liczby dużych fragmentów tekstu), aby utworzyć między nimi pary pasujące - z którego dokumentu najprawdopodobniej powstanie.

Sądzę, że podzielę to na dwie części - określając współczynnik podobieństwa dla każdej pary - a następnie stosując niektóre z algorytmów problemu przypisania. Podczas gdy dla algorytmów przydziału mogę znaleźć sporo rozwiązań, nie mogę znaleźć dobrego dla obliczenia współczynników podobieństwa.

Uwaga: dokumenty nie są znane z góry - obliczanie indeksów tekstu (jeśli jest) musi być również szybkie.

Znam odległość Hamminga, odległość Levenshteina od innych algorytmów różnicy łańcuchów. Nie tego jednak szukam - celowo używam tekstu zamiast napisu.

Nie szukam algorytmów wyszukiwania fraz ani bibliotek, takich jak Lucene i Xapian (przynajmniej wydaje się być).

Prawdopodobnie coś oparte na tf-idf.

Chyba pytanie brzmi: czy jest coś, co rozwiązuje już ten problem, czy możliwe jest, że biblioteki takie jak lucete są używane do tego.

Answer 1

Oto co bym zrobił jako punkt wyjścia (tylko dlatego, że jest prosty i szybki):

• mapie słowa z numerami za pomocą udostępnionego mapę lub hash_map
• dla każdego tekstu, budować odpowiadająca mapa słowo poziomu trygram liczy
• Porównaj nakładania

możemy przypuszczać, że rozmiar słownika jest < 1m (lub 21bit), więc możemy tylko kodować trygram w in 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++; 
     } 
    } 
    } 
} 

następnie porównać wyniki dla każdej pary:

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

To może mieć sens, aby znormalizować wynik jakoś, na przykład podzielić przez całkowitą liczbę trygramów.