模糊匹配地址

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

请注意，标准化函数只是尝试通过删除不相关的信息和填充邮政编码来标准化地址。

然而，我想知道如何加快这一进程，因为目前的费用非常昂贵，或者是否有更好的办法可供选择？

任何帮助都是感激的，

谢谢!

编辑： $classifications的大小为12000行，$lines的大小为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格式的话，填充post代码。

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_merge与array_unique耦合。

Answer 2

你对levenshtein距离算法使用了什么容忍度？根据我的经验，少于0.8会带来太多的假比赛。最后，我用手工更正了一些简短的单词，比如raod = road，否则分数会是1个字符错误，使它成为75%的匹配。我找到了一篇关于12次使用模糊匹配查找地址的测试的文章，它可能对改进算法很有用。这些例子包括：

1. 拼写错误
2. 缺失空间
3. 不正确类型(街道与道路)
4. 毗邻/近郊
5. 缩写
6. 同义词:楼层与楼层
7. 单位，公寓或公寓对字母
8. 数字与字母
9. 额外词汇(如前门，部门名称)
10. 交换信
11. 听起来像是
12. 令牌化(不同的输入顺序)