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

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