用PHP Levenshtein比较5000个字符串

Question

我在阵列中有5000个,有时更多的街道地址字符串.我想将它们与levenshtein进行比较以找到类似的匹配.如何在不循环遍历所有5000并将它们直接与其他4999进行比较的情况下执行此操作？

编辑:如果有人有建议,我也对替代方法感兴趣.总体目标是根据用户提交的街道地址查找类似的条目(并消除重复项).

Answer 1

我认为将类似地址分组的更好方法是:

1. 创建一个包含两个表的数据库 - 一个用于地址(和一个id),一个用于单词的soundexes或地址中的文字数字(使用地址表的外键)

2. 大写地址,用空格替换[AZ]或[0-9]以外的任何内容

3. 按空格分割地址,计算每个'单词'的soundex,保留任何只有数字的数据,并将其存储在soundexes表中,并使用您开始的地址的外键

4. 对于每个地址(ID为$ target),找到最相似的地址:

   SELECT similar.id, similar.address, count(*) 
   FROM adress similar, word cmp, word src
   WHERE src.address_id=$target
   AND src.soundex=cmp.soundex
   AND cmp.address_id=similar.id
   ORDER BY count(*)
   LIMIT $some_value;
   

5. 计算源地址与查询返回的前几个值之间的levenstein差异.

(在大型数组上进行任何类型的操作通常在数据库中更快)