# What is the best algorithm to find similar text documents?

I have many text documents and I would like to find similar documents to each document within my data set. Is Latent Dirichlet Allocation (LDA) the best way to do that, or are there other algorithms taht might work better? Any ideas?

As my data set in big, I would rather use Apache Mahout to find similar documents.

• How do you define "similar" here? – Speldosa May 8 '15 at 0:04
• LDA is certainly a viable option. LSA is too. – Ami Tavory May 8 '15 at 0:17
• Semantically similar. – H.Z. May 8 '15 at 0:57
• How about techniques like vector factorization with ALS? – H.Z. May 8 '15 at 0:59
• The definition of similar is very important here. If you mean semantically similar, text similarity search might not solve you problem. But it should be the first thing to try. – Bar May 15 '15 at 13:33

To find similar documents in very large document sets is locality sensitive hashing (LSH). An indication of the gist is: "One general approach to LSH is to “hash” items several times, in such a way that similar items are more likely to be hashed to the same bucket than dissimilar items are."

For in-depth information see: http://infolab.stanford.edu/~ullman/mmds/ch3a.pdf

Why cluster? Why LDA?Much too expensive, complicated, and unreliable. Let me present you an incredible novel technique to find similar documents:

## text search

There is a wonderful tool called Apache Lucene, that makes text search fast and easy to integrate, too.

• Searching for terms is not is not the same as finding similar documents. A typical case for the latter is finding plagiary; this is not resolved by a search engine. – spdrnl Jun 2 '15 at 18:04
• Actually plagiarism detection does use these techniques, too. – Anony-Mousse Jun 2 '15 at 19:21

One good technique that I've seen used in the past for information retrieval applications is to shingle your target documents and query document, and then take the Jaccard similarity over sets of shingles.

Shingling is a procedure that takes a sliding window over characters in your document, representing a string as the set of character $k$-grams that occur in the strong. Now that we have a set representation of documents, we can compare them using their Jaccard similarity.

As an example, the 2-shingles of the string "racecar" would be the set {ra, ac, ce, ec, ca, ar}.

Below is some simple Python code that would do this to illustrate the point:

def shingle(doc, k=3):
return { doc[i:i+k] for i in range(0, len(doc) - k + 1) }

def jaccard(a, b):
return 1.0 * len(a.intersection(b)) / len(a.union(b))

documents = [...] # List of strings
query = "this week on twitter..."
query_shingles = shingle(query)

best_doc = -1
best_score = float("-inf")
for i, doc in enumerate(documents):
doc_shingles = shingle(doc)
similarity = jaccard(doc_shingles, query_shingles)
if similarity > best_score:
best_score = similarity
best_doc = i


The idea is that documents with similar $k$-shingles have similar contents for a well-chosen value of $k$. For most applications $k$ is almost always between 2 and 4 (3 is the most popular choice that I've seen).

There are alternative formulations such as $w$-shingling which use word $n$-grams instead of character $n$-grams, but the idea is still the same.

This program uses word frequency analysis ("bag of words") and sorts the repository texts by Euclidian distance to the vector of frequencies of the sample text.

Given a sample text, this program lists the repository texts sorted by similarity: simple implementation of bag of words in C++. The algorithm is linear in the total length of the sample text and the repository texts. Plus the program is multi-threaded to process repository texts in parallel.

Here is the core algorithm:

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


It's tested on Project Gutenberg books, as you can see in the example on GitHub.