如何在大型数据集中有效地识别相似但不相同的字符串？

Question

假设我有数千个字符串,我需要识别最常见的组.

这是一个示例数据集:http://pastebin.com/XGijjsfE

此数据集的前10行代表我所追求的字符串类型.虽然在现实生活中,这些会与其他人混在一起.

一种策略是循环遍历每个字符串,并使用字符串比较工具将其与其他字符串进行比较,并跟踪高度相似性.这里有一些伪php代码来说明这一点:

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

但是在100k行乘以100k行时,这可能非常昂贵.

在更大的数据集中识别类似字符串的更有效方法是什么？

我在LAMP环境中,字符串当前在MySQL表中.但答案可以在Shell,PHP,Python,MySQL等中执行.

这是数据集:

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

您想使用 BK 树。该树可以在线性时间内构建，然后可以回答诸如“该集合中的哪些项目与我的测试字符串的编辑距离在 N 之内”之类的问题。每个查询都是亚线性时间。下面是一些用 python 和 haskell 构建它们的示例代码，以及有关该主题的更全面文章的链接： https: //github.com/ahupp/bktree