6

Here's the problem -- I have a few thousand small text snippets, anywhere from a few words to a few sentences - the largest snippet is about 2k on disk. I want to be able to compare each to each, and calculate a relatedness factor so that I can show users related information.

What are some good ways to do this? Are there known algorithms for doing this that are any good, are there any GPL'd solutions, etc?

I don't need this to run in realtime, as I can precalculate everything. I'm more concerned with getting good results than runtime.

I just thought I would ask the Stack Overflow community before going and writing my own thing. There HAVE to be people out there who have found good solutions to this before.

1
  • 1
    Very underdefined question. Upon what basis do you consider two texts to be related to each other? Common topics? Repeated phrases? Length? Complexity? Letter frequency? Aug 31, 2009 at 18:17

7 Answers 7

2

These articles on semantic relatedness and semantic similarity may be helpful. And this SO question about Latent Semantic Analysis.

You could also look into Soundex for words that "sound alike" phonetically.

1
  • Thanks. Latent semantic analysis looks promising, I will have to read up and see about implementing it.
    – Matt
    Aug 31, 2009 at 19:07
2

I've never used it, but you might want to look into Levenshtein distance

0
1

Jeff talked about something like this on the pod cast to find the Related questions listed on the right side here. (in podcast 32)

One big tip was to remove all common words, like "the" "and" "this" etc. This will leave you with more meaningful words to compare.

And here is a similar question Is there an algorithm that tells the semantic similarity of two phrases

0

This is quite doable for reasonable large texts, however harder for smaller texts.

I did it once like this, and it worked pretty well:

  • Filter all "general" words (like a, an, the, in, etc...) (filters about 10-30% of the words)
  • Count the frequencies of the remaining words, store the top x of most frequent words, these are your topics.
  • As an extra step you can create groups of 2/3/4 subsequent words and compare them with the groups in other texts. I used it as a measure for plagerism.
0

See Manning and Raghavan course notes about MinHashing and searching for similar items, and a C#(?) version. I believe the techniques come from Ullman and Motwani's research.

0

This book may be relevant.

Edit: here is a related SO question

1
  • Thank you. Information Retrieval is the general topic, and this book probably has good information in it.
    – Matt
    Aug 31, 2009 at 19:08
0

Phonetic algorithms

The article, Beyond SoundEx - Functions for Fuzzy Searching in MS SQL Server, shows how to install and use the SimMetrics library into SQL Server. This library lets you find relative similarity between strings and includes numerous algorithms.

I ended up mostly using Jaro Winkler to match on names. Here's more information where I asked about matching names on SO: Matching records based on Person Name

A few algorithms based on Levenshtein Distance are also available in the SimMetric library and would probably be useful in your application.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.