8

我在一个数组中有 5000 个，有时甚至更多的街道地址字符串。我想将它们与 levenshtein 进行比较以找到相似的匹配项。如果不遍历所有 5000 并将它们与其他所有 4999 直接比较，我怎么能做到这一点？

编辑：如果有人有建议，我也对替代方法感兴趣。总体目标是根据用户提交的街道地址找到相似的条目（并消除重复项）。

4

8 回答 8

7

我认为对类似地址进行分组的更好方法是：

  1. 创建一个包含两个表的数据库 - 一个用于地址（和一个 id），一个用于地址中单词或文字数字的音译（使用地址表的外键）

  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 差异。

（在数据库中对大型数组进行任何类型的操作通常更快）

于 2009-12-24T12:04:10.097 回答
3

我认为你不能避免遍历数组，因为 levenstein() 函数只接受字符串而不是数组作为输入。

您可以执行以下操作：

for($i=0;$i<count($array)-1;$i++)
{
    for($j=$i+1;$j<count($array);$j++)
    {
        $lev = levenshtein($array[$i],$array[$j]);
        if($lev == 0)
        {
            // exact match
        }
        else if($lev <= THRESHOLD)
        {
            // similar
        }
    }
}
于 2009-12-24T11:41:56.007 回答
3

您可以使用bk-tree来加速搜索/比较。

http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees说：

现在我们可以对 Levenshtein 距离进行一个特别有用的观察：它形成了一个度量空间。
[...]
假设我们有两个参数，查询，我们在搜索中使用的字符串，以及字符串可以与查询的最大距离并且仍然被返回。假设我们采用任意字符串，对其进行测试并将其与查询进行比较。调用合成距离 d。因为我们知道三角不等式成立，所以我们所有的结果必须最多有 d+n 距离，至少距离 test 有 dn。
[...]
测试表明，搜索距离为 1 的查询不超过树的 5-8%，搜索两个错误的查询不超过树的 17-25% - 与检查每个节点相比有了很大的改进！

编辑：但这对您的（“12 Bird Road，Apt 6”和“12 Bird Rd.#6”）问题没有帮助。仅通过您的蛮力 m*n 比较。

于 2009-12-24T11:51:31.300 回答
2

由于 Levenshtein 算法的性质（特别是它是两个字符串之间的比较这一事实），我看不出这是怎么可能的。

您当然可以通过首先执行一些基本匹配要求来减少比较次数，但这超出了您所要求的范围。

作为一个（很可能不相关的）选项，您总是可以使用类似的东西soundex，它可以让您预先计算字符串值。（我相信你也可以直接在 MySQL 中使用它。）

于 2009-12-24T11:42:19.313 回答
2

您可以根据 soundexes 对它们进行分组，然后将比较限制为最接近的 N 个案例...

 $mashed=array();
 foreach ($address as $key=>$val) {
      $mashed[$key]=soundex($val);
 }
 sort($mashed);

然后遍历 $mashed 的键。

C。

于 2009-12-24T11:42:25.493 回答
1

鉴于您的问题，如果您想使用Lehvenstein distance ，除了将每个地址与每个其他地址进行比较之外，我别无他法。

首先，您应该规范化地址，摆脱缩写等。

  • 大道 -> 大道
  • 路。-> 道路

对于类似的地址，您可以有一些固定的最大 Lehvenstein 距离 ( N )。

如果是这样，当您确定当前地址对的编辑距离大于 N 时，您可以中止 Lehvenstein 算法。为此，您需要编写 Lehvenstein 算法的自定义版本。这将使算法更快一点。

还有一些相关的琐碎优化。例如：如果地址 A 的长度为 10 个字符，地址 B 的长度为 20 个字符，并且您认为 Lehvenstein 距离小于 8 的地址是相似的。您可以查看地址的长度并立即确定它们不相似。

于 2009-12-24T11:43:21.840 回答
1

如果要查找所有相似的值，则必须将所有项目与所有其他项目进行比较。但是选择正确的数组函数会显着加快速度。这是一个简单的示例（结果数组可能会更好）：

$results = array();
$count = count($entries);
while ($count != 0) {
    # The entry to process
    $entry = array_shift($entries);
    # Get levenshtein distances to all others
    $result = array_map(
        'levenshtein',
        # array_map() needs two arrays, this one is an array consisting of
        # multiple entries of the value that we are processing
        array_fill($entry, 0, $count),
        $toCompare
    );
    $results[] = array($entry => $result);
    $count--;
}
于 2009-12-24T11:48:09.417 回答
1 
$stringA = "this is php programming language";
$stringB = "this is complete programming script in which java php and  all other minor languages include";

echo "string 1---->".$stringA."<br />";
echo "string 2---->".$stringB."<br />";
// changing string to arrays
$array1 = explode(' ', $stringA);
$array2 = explode(' ', $stringB);

// getting same element from two strings
$c = array_intersect($array1, $array2);
// changing array to the string
$d=implode(' ',$c);

echo "string same elements---> ".$d."<br />";


// getting difrent  element from two arrays
$result = array_diff($array2, $array1);
// changing array to the string
$zem = implode(' ',$result);

if (!empty($zem)) {
  echo "string diffrence---> ".$zem."<br />";
} else {
  echo "string diffrence--->both strings are same <br />";
}

similar_text($stringA, $d, $p);
echo " similarity between the string is ".$p."% <br />";
于 2011-06-18T07:26:17.357 回答