How can I efficiently identify similar, but not identical, strings in a large dataset?

Question

Assume I have thousands of strings in which I need to identify the most common group.

Here's a sample dataset: http://pastebin.com/XGijjsfE

The first 10 lines of this dataset represent the type of strings I'm after. Although in real life these would be mixed in with the rest.

One strategy is to loop through each string and compare it to each of the others using a string comparison tool and keeping track of high similarities. Here's some pseudo-php-code to illustrate this:

<?php
$arr = explode("\n",http://pastebin.com/XGijjsfE); // I know. Just pseudocode here!
$winners = array(); // store close matches here
foreach ($arr as $k1 => $line1) {
    foreach ($arr as $k2 => $line2) {
        if ($k1 != $k2) {
            $lev = levenshtein($line1, $line2);
            if ($lev < 10) { // assume 10 is a reasonable start to learn and tune later
                $winners[] = array($line1,$line2,$lev);
            }
        }
    }
}
print_r($winners);
?>

But at 100k rows times 100k rows, this can be very expensive.

What's a more efficient way to identify similar strings in a larger dataset?

I'm in a LAMP environment and the strings are currently in a MySQL table. But answers can be executed in Shell, PHP, Python, MySQL, and so on.

Here's the dataset:

Lorem ipsum dolor sit amet, consectetur adipiscing elit.
Lorem ipsum dolor sit amet consectetur adipiscing elit.
My Lorem ipsum dolor sit amet, consectetur adipiscing elit.
Lorem ipsum dolor sit amet, consectetur adipiscing elit
Lorem ipsum dolor sit amet, consectetur adipiscing elit!
Lorem ipsum dolor sit amet - consectetur adipiscing elit.
Lorem ipsum dolor sit amet. Consectetur adipiscing elit.
Lorems ipsum dolor sit amet, consectetur adipiscing elit.
Lorem & ipsum dolor sit amet, consectetur adipiscing elit.
*Lorem ipsum dolor sit amet, consectetur adipiscing elit.
Vestibulum non condimentum sapien, in rutrum nisl.
Nunc ante lorem, varius nec nunc id, porttitor malesuada odio.
Ut non nibh tortor.
Donec accumsan auctor nulla, ac tempus lectus varius vel.
In imperdiet in sapien et ultricies.
Integer ultrices neque nibh, vel varius ante ultricies non.
Etiam aliquet pretium ante, at suscipit mi placerat vitae.
Praesent lobortis commodo tincidunt.
Quisque convallis ultricies eros, vel ultricies augue lacinia eget.
Pellentesque aliquam eleifend enim, et rutrum urna vehicula a.
Nunc euismod metus felis, eget ultricies arcu lobortis at.
Quisque quis leo urna.
Fusce malesuada blandit sodales.
Fusce ut dictum lorem, eget molestie mi.
Mauris rutrum neque a nisl volutpat tristique.
Vestibulum sit amet ligula placerat, imperdiet neque at, ullamcorper purus.
Cras id rutrum orci.
Duis lacus tortor, adipiscing a cursus adipiscing, vestibulum ac dolor.
Suspendisse potenti.
Curabitur sed quam metus.
Nullam velit eros, sodales sed dapibus a, convallis et nibh.
Nunc fringilla tempor tristique.
Fusce fermentum erat ut est adipiscing, in consequat sapien ornare.
Vivamus ac magna sollicitudin purus feugiat blandit.
Vestibulum libero tellus, ullamcorper a elit ut, viverra interdum lorem.
Duis sit amet lobortis nisl, et fringilla nunc.
Vivamus nec ante et turpis pretium congue.
Vivamus nec metus ut nisi tempus vehicula.
Duis malesuada lacinia hendrerit.
In nisl ligula, vestibulum nec convallis vel, hendrerit non elit.
Ut in pretium nibh, in fermentum est.
Proin consectetur nisl et nunc ullamcorper sagittis.
Sed aliquet magna sem, quis malesuada felis semper ac.
Proin interdum volutpat sapien, vitae malesuada turpis placerat in.
Nam semper leo vitae turpis faucibus adipiscing.
Morbi odio neque, adipiscing vel nulla faucibus, mollis viverra sem.
Vestibulum ultrices magna et aliquet luctus.
Nulla id tincidunt mauris.
Sed dignissim eget diam lacinia ullamcorper.
Vivamus interdum in ligula quis tempor.
Suspendisse sed posuere ligula, ut varius sem.
Morbi sollicitudin aliquam sapien, id egestas sapien tincidunt sed.
Mauris et massa eget neque fermentum rhoncus.
Vivamus tincidunt ut mi non tincidunt.
In hac habitasse platea dictumst.
Donec non cursus diam.
Nulla ac metus sem.
Duis id nisl dictum, molestie ligula ut, congue nibh.
Nulla eget massa et elit pellentesque blandit.
Donec mauris magna, porttitor ac neque vel, convallis commodo metus.
Nam consequat, orci sed rutrum sagittis, augue sapien mattis nisi, quis fermentum tellus lorem ac magna.
Nam vehicula quam id purus condimentum, vel pharetra tellus posuere.
Quisque vitae massa viverra, bibendum sem non, tempor sapien.
Vivamus aliquam dapibus dictum.
Aliquam sapien dolor, dictum sed augue sit amet, accumsan ultrices justo.
Mauris urna augue, egestas nec nunc in, ultrices fermentum odio.
Nullam vel odio at erat semper convallis.
Curabitur vel nisi erat.
Mauris vulputate dolor quis pharetra euismod.
Pellentesque pretium aliquet quam, dignissim iaculis mi.

Answer 1

You want to use a BK-tree. The tree can be built in linear time, and then can answer questions like "which items in this set are within a levenshtein distance of N from my test string". Each query is sub-linear time. Here's some example code that builds them in python and haskell, along with a link to a more thorough article on the subject: https://github.com/ahupp/bktree