Take the 2-minute tour ×

Is there a method to calculate something like general "similarity score" of a string? In a way that I am not comparing two strings together but rather I get some number/scores (hash) for each string that can later tell me that two strings are or are not similar. Two similar strings should have similar (close) scores/hashes.

Let's consider these strings and scores as an example:

Hello world 1000

Hello world! 1010

Hello earth 1125

Foo bar 3250

FooBarbar 3750

Foo Bar! 3300

Foo world! 2350

You can see that Hello world! and Hello world are similar and their scores are close to each other.

This way, finding the most similar strings to a given string would be done by subtracting given strings score from other scores and then sorting their absolute value.

My end aim is : there would be streaming log messages(only pure messages) and i wanna find the pattern of those messages(some sort of regular expression type).But that gets started only when i can bucket similar strings. I again focus that I should get some number/scores (hash) for each string AND THAT CAN LATER tell me that two strings are or are not similar

share|improve this question
possible duplicate of String similarity algorithims? (and many other previous questions) –  larsmans Jul 12 '11 at 14:02
@larsmans the solutions of the post are deviated towards somewhat i am not looking to(i.e they concentrates on string similarity based on comparing strings). For me, the data are huge and streaming, so comparing strings is out of question. i just find one way to solve:scoring(may be bad type of hashing) the each string and THAT can LATER tell me that two strings are or are not similar. –  Ajay Jul 12 '11 at 16:33
Hello, I am also very interested in this problem. Did you get any progress on this problem? –  Bloodmoon Jan 13 at 9:02
@Bloodmoon: couldn't compute the hash value(integer). Haven't been able to concentrate on research as I have to concentrate on job. However, I had tweaked charikar Hash algorithm to get it work to some extent. Still, there is some theoretical limitation when the string is of few words. It is hard to know whether say, Hello world is similar to Hello earth or Foo world or Foo earth? But still need to research for better optimisation for strings with good enough number of words.. –  Ajay Jan 13 at 11:35
Can similarity be defined by a distance threshold of the hash values? Say if the function is f(), and |f("hello world")-f("hello worth")| < t, where t is the threshold, then "hello world" is similar to "hello worth". Otherwise they are not similar. –  Bloodmoon Jan 14 at 8:18
show 5 more comments

7 Answers

There are several such "scores", but they all depend on how you define similarity.

share|improve this answer
soundex might not work here as my messages contains numeric value and some special characters as well. regarding Levenshtein distance, I am looking to bucket the hash value rather than comparing the string themselves which might be slow for streaming data that are huge in numbers. May be that can be used as back up idea later on... anyway thanks for your help :) –  Ajay Jul 13 '11 at 14:48
add comment

Have a look at locality-sensitive hashing.

The basic idea is to hash the input items so that similar items are mapped to the same buckets with high probability (the number of buckets being much smaller than the universe of possible input items).

There's a very good explanation available here together with some sample code.

share|improve this answer
it has been the best concept i have encountered so far. i'll soon read all relevant documents. thank you very much –  Ajay Jul 13 '11 at 12:42
add comment

TL;DR: Python BK-tree

Interesting question. I have limited experience within this field, but since the Levenshtein distance fulfills the triangle inequality, I figured that there must be a way of computing some sort of absolute distance to an origin in order to find strings in the vicinity of each other without performing direct comparisons against all entries in the entire database.

While googling on some terms related to this, I found one particularly interesting thesis: Aspects of Metric Spaces in Computation by Matthew Adam Skala.

At page 26 he discusses similarity measures based on kd-trees and others, but concludes:

However, general metric spaces do not provide the geometry required by those techniques. For a general metric space with no other assumptions, it is necessary distance-based to use a distance-based approach that indexes points solely on the basis of their distance from each other. Burkhard and Keller [35] offered one of the first such index structures, now known as a BK-tree for their initials, in 1973. In a BK-tree, the metric is assumed to have a few discrete return values, each internal node contains a vantage point, and the subtrees correspond to the different values of the metric.

A blog entry about how BK-trees work can be found here.

In the thesis, Skala goes on describing other solutions to this problem, including VP-trees and GH-trees. Chapter 6 analyses distances based on the Levenshtein edit distance. He also presents some other interesting distance metrics for strings.

I also found Foundations of Multidimensional and Metric Data Structures, which seems relevant to your question.

share|improve this answer
thank u very much i will look at all of them.. –  Ajay Jul 13 '11 at 12:33
+1 for research. –  doc_180 Jul 13 '11 at 15:50
add comment

For a fast way of determining string similarity, you might want to use fuzzy hashing.

share|improve this answer
add comment

You may be interested in Hamming Distance. The Python function hamming_distance() computes the Hamming distance between two strings.

def hamming_distance(s1, s2):
    assert len(s1) == len(s2)
share|improve this answer
The OP explicitly lists some string of unequal length in the examples, so Hamming distance won't work. More generally, it's a pretty weak metric for text strings. –  larsmans Jul 12 '11 at 14:09
The OP also said he wanted to compare the hash values instead of the strings. –  Brett Stottlemyer Jul 12 '11 at 15:50
exactly i want to bucket the strings based on the computed hashes –  Ajay Jul 13 '11 at 12:36
add comment

You can always use Levenshtein distance, also, there is a written implementation for that: http://code.google.com/p/pylevenshtein/

But, for simplicity, you can use builtin difflib module:

>>> import difflib
>>> l
{'Hello Earth', 'Hello World!', 'Foo Bar!', 'Foo world!', 'Foo bar', 'Hello World', 'FooBarbar'}
>>> difflib.get_close_matches("Foo World", l)
['Foo world!', 'Hello World', 'Hello World!']


share|improve this answer
the edit distance method is just for comparing two strings at a time.its not possible due to space complexity(huge number of data...i think i mention streaming data)... its not possible to store the data and chech one by one using Levenshtein distance –  Ajay Jul 19 '11 at 3:46
add comment

You might want to look at using a BK-Tree. Here is a discussion and python implementation.

A BK-Tree stores strings in a tree, sorted by Levenshtein distance to the parent nodes. This is normally used to prune the search space when looking for similar strings, but it seems that this tree would form a natural ordering that could be used to create clusters.

share|improve this answer
add comment

Your Answer


