From: Dave Bass Date: 2008-07-09T20:21:07+09:00 Subject: Re: String matching/comparing, statistical similarity This is a major problem that search engines have to solve. There are no easy answers but there are lots of possible techniques, all of which suffer from false positives and false negatives. You might like to look at the information retrieval literature to find out what's been tried. A simple metric for how alike two documents are is the Jaccard similarity measure. If you can break your formatted files into words, the Jaccard similarity between two documents is (no. of words in both docs)/(no. of words in either doc). In mathematics, if you have two sets A and B, the Jaccard similarity is the cardinality of the intersection of A and B divided by the cardinality of the union of A and B: |A n B| / |A u B|. This lies in [0, 1]. If you're using words as features, it's usual to eliminate common function words such as "the", "a", "an", etc. Of course you can use other features than words, for example phrases. Another possibility is the cosine similarity measure. You form a vector for each document by counting the number of times each feature occurs, and take the cosine of the angle between them in high-dimensional space. This lies in [-1, 1]. Levenstein distance is not used by search engines, as two documents can have very similar content but a large edit distance. Dave -- Posted via http://www.ruby-forum.com/.