模糊匹配地址

Question

我正在忙着写一个简单的算法来模糊匹配来自两个数据集的地址。我正在计算两个地址之间的levenshtein距离，然后将精确匹配或最短匹配添加到匹配数组。

然而，这是非常缓慢的，因为在最坏的情况下，它必须将每个旧地址与每个新地址进行比较。

我目前的解决方案如下：

matches = []; 
foreach ($classifications as $classification) 
{ 
    $classification = $stringMatchingService->standardize($classification, $stringMatchingService->isClassification()); 
    $shortest = -1; 
    $closest = ''; 
    $cnt = 0; 
    foreach ($lines as $line) 
    { 
     $line = $stringMatchingService->standardize($line, $stringMatchingService->isRTT()); 
     if ($classification[CLASSIFICATION_POSTCODE] != $line[RTT_POSTCODE]) { 
      continue; 
     } 

     $lev = levenshtein($classification[CLASSIFICATION_SUBURB], $line[RTT_SUBURB]); 
    if ($lev == 0) { 
     $matches[$classification[CLASSIFICATION_SUBURB]] = $line[RTT_SUBURB]; 
     $cnt++; 
     break; 
    } 

    if ($lev <= $shortest || $shortest < 0) { 
     //set the closest match and distance 
     $closest = $line[RTT_SUBURB]; 
     $shortest = $lev; 
    } 

    if ($cnt == count($lines)) { 
     $matches[$classification[CLASSIFICATION_SUBURB]] = $closest; 
    } 
    $cnt++; 
} 

} 
print_r(count($matches)); 

注意，标准化功能只是试图通过去除不相关的信息和填补邮政编码规范的地址。

但是，我想知道如何加快这一进程，因为目前它非常昂贵，或者如果有更好的方法可以采取？

任何帮助表示赞赏，

谢谢！

编辑： 的$大小分类为12000行和$行大小17000行。该标准化功能如下：

public function standardize($line, $dataSet) 
{ 
    switch ($dataSet) { 
     case self::CLASSIFICATIONS: 
      if (!isset($line[9], $line[10]) || empty($line[9]) || empty($line[10])) { 
       continue; 
      } 
      $suburb = $line[9]; 
      $suburb = strtoupper($suburb); 
      $suburb = str_replace('EXT', '', $suburb); 
      $suburb = str_replace('UIT', '', $suburb); 
      $suburb = preg_replace('/[0-9]+/', '', $suburb); 

      $postCode = $line[10]; 
      $postCode = str_pad($postCode, 4,'0', STR_PAD_LEFT); 
      $line[9] = $suburb; 
      $line[10] = $postCode; 
      return $line; 
     case self::RTT: 
      if (!isset($line[1], $line[0]) || empty($line[1]) || empty($line[0])) { 
       continue; 
      } 
      $suburb = $line[1]; 
      $suburb = strtoupper($suburb); 
      $suburb = str_replace('EXT', '', $suburb); 
      $suburb = str_replace('UIT', '', $suburb); 
      $suburb = preg_replace('/[0-9]+/', '', $suburb); 
      $postCode = $line[0]; 
      $postCode = str_pad($postCode, 4,'0', STR_PAD_LEFT); 
      $line[1] = $suburb; 
      $line[0] = $postCode; 
      return $line; 
    } 

它只是旨在适当地访问数据，并删除某些关键字，垫后的代码，如果它不是在格式XXXX。

Answer 1

这里的问题是每个$classifications行，你检查一行匹配$line。 = 12000 * 17000 ...

所以，我不知道你的数组的结构，但你可以想象使用array_filter。

$matches = array_filter($classifications, function ($entry) use ($lines) { 

    foreach ($lines as $line) 
    { 
     $lev = levenshtein($entry[CLASSIFICATION_SUBURB], $line[RTT_SUBURB]); 

     // if match, return true 
    } 

}); 

$matches将是一个匹配行数组。

这取决于你的数据结构，但更好的方法是使用加上array_unique

Answer 2

你用什么宽容的Levenshtein距离算法array_merge？根据我的经验，低于0.8会导致太多的错误匹配。我最终使用了诸如raod = road之类的短语的手动更正，否则得分将是1个字符错误，使其成为75％的匹配。我找到了一篇12 tests to find addresses using fuzzy matching的文章，可以用来改进你的算法。例子包括：

1. 拼写错误
2. 缺墨空间
3. 错误类型（街VS路）
4. 边区/近郊
5. 缩写
6. 别名：地板VS级
7. 单位，单位或公寓与信
8. 数字与字母
9. 额外的单词（例如前门，部门名称）
10. 已交换信函
11. 听起来像
12. 断词（不同的输入顺序