fuzzy DISTINCT Values

Question

我有一个房地产清单数据库，需要返回一个社区列表。现在我使用的是mysql DISTINCT，它返回所有不同的值。我的问题是，有很多社区有类似的名字：例如：

Park View Sub 1
Park View
Park View Sub 2
Park View Sub 3
Great Lake Sub 1
Great Lake Sub 2
Great Lake 
Great Lake Sub 3

我正在寻找一个简单的php或mysql解决方案，它可以识别"Park View"one_answers"Great Lake"已经存在，并且只返回"Park View"one_answers"大湖"。

我最初的想法是如何根据长度获得排序顺序，使短值位于顶部，然后使用strstr循环。这听起来像是一项艰巨的任务，我想知道mysql或php中是否有一个函数可以轻松完成这项任务。

Answer 1

以下是您可以尝试的一些方法；大概你在寻找完全匹配和势均力敌的匹配。

先找一个完全匹配的。然后在反转名称上查找LIKE匹配项。然后寻找额外字符最少的匹配项。

这里有一个查询可以完成所有这些操作。请注意，如果您希望高效，则需要将反转的地名存储在索引列中。

select name 
  from (
   select name, 0 ordinal
     from place 
    where name = 'Park View'
  union
  select name, 1 ordinal
    from place 
   where Reverse(Name) like concat(Reverse('Park View'),'%')
  union
  select name, 2+length(name)
    from place
   where name like concat('Park View','%')
 ) a 
order by ordinal
   limit 1

请注意这个UNION查询是如何使用ordinal来找出最佳匹配的。

点击此处查看：http://sqlfiddle.com/#！2/76a97/9/0

Answer 2

如果您总是有一个没有"Sub#"部分的条目，您可以这样做：

SELECT DISTINCT neighborhood FROM table WHERE neighborhood NOT LIKE '% Sub %';

按字符串长度排序：

SELECT DISTINCT neighborhood FROM table ORDER BY LENGTH(neighborhood);

Answer 3

您可以使用PHP的similar_text来实现一个简单的解决方案。如果你对数据进行预排序，使所需的较短地址优先，那么它应该会很好地工作。此外，如果"不同"的地址不太相似，它会更好地工作（但你总是可以提高阈值）：

// if an address is 70% (or more) similar to another, it is not unique
$threshold = 70;
// list of addresses (and sorting them); this is done through the DB in your code
$addresses = array('Park View Sub 1', 'Park View', 'Park View Sub 2', 'Park View Sub 3', 'Great Lake Sub 1', 'Great Lake Sub 2', 'Great Lake', 'Great Lake Sub 3');
sort($addresses);
$unique = array();
foreach ($addresses as $address) {
    $isUnique = true;
    foreach ($unique as $u) {
        // get the similarity between the current address and each unique address
        similar_text($address, $u, $percent);
        if ($percent > $threshold) {
            // not unique; drop it
            $isUnique = false;
            break;
        }
    }
    if ($isUnique) $unique[] = $address;
}

对于其他替代方案，您还可以查看PHP的levenshtein和soundex，以及MySQL的SOUNDEX()。

另一种伪模糊方法是按字母顺序（通过MySQL或PHP）对地址进行排序，并逐个循环；如果当前地址以已经找到的唯一地址的文本开头，则将其删除。这与使用实际的模糊方法非常相似，但更直接：

// list of addresses (and sorting them); this is done through the DB in your code
$addresses = array('Park View Sub 1', 'Park View', 'Park View Sub 2', 'Park View Sub 3', 'Great Lake Sub 1', 'Great Lake Sub 2', 'Great Lake', 'Great Lake Sub 3');
sort($addresses);
$unique = array();
foreach ($addresses as $address) {
    $isUnique = true;
    foreach ($unique as $u) {
        if (substr($address, 0, strlen($u)) == $u) {
            $isUnique = false;
            break;
        }
    }
    if ($isUnique) $unique[] = $address;
}

只有对它们进行排序时，此方法才会起作用，因为需要在Park View Sub 1之前找到较短的地址Park View。如果您的地址太过相似，并且上面的similar_text方法删除了太多地址，则可以尝试后一个函数，因为它更严格。

Answer 4

下面的示例查询将使用MySQL获得指定的结果集，但它并没有真正进行"模糊匹配"，至少我不会这样描述算法。（这实现了您描述的算法——按值排序，然后检查每个值，看看前导部分是否与之前检索到的值"匹配"。）

这会发现邻域值的前导部分与之前检索到的行中的值"完全匹配"，匹配实际上没有任何"模糊性"。

当查询遇到"不匹配"的值时，它会标记该值为"不匹配的"。对于检索到的下一个值，它检查该值是否以以前"不匹配"的值开头；如果字符串的前导部分完全匹配，则丢弃该值。否则，该值将标记为"不匹配"值，并保留。

这种方法使用内联视图（或者MySQL所指的"派生表"）。最里面的内联视图（别名为s）为我们提供了一个邻域的不同值的排序列表。"技巧"（如果你想这么称呼它的话）在下一个内联视图（别名为"t"）中，我们使用MySQL用户变量来引用以前检索到的值。

为了避免"特殊人物"出现任何问题，我们对主角进行了平等比较。

以下是整个查询：

SELECT t.neighborhood
  FROM (
         SELECT IF(IFNULL(LEFT(s.neighborhood,CHAR_LENGTH(@match)) <> @match,1),@match := s.neighborhood,NULL) AS neighborhood
           FROM (SELECT RTRIM(neighborhood) AS neighborhood
                   FROM mytable
                   JOIN (SELECT @match := NULL) r
                  GROUP BY neighborhood
                  ORDER BY neighborhood
                ) s
       ) t
 WHERE t.neighborhood IS NOT NULL  

这一切都非常简单，除了@match变量的初始化，以及执行当前值与以前值比较的表达式。

如果我们不关心值中特殊字符引入的角大小写，我们可以使用更简单的LIKE或REGEXP进行比较：

s.neighborhood NOT LIKE CONCAT(@match,'%')
s.neighborhood NOT REGEXP CONCAT('^',@match)

LIKE运算符受下划线和百分比字符的约束，REGEXP受正则表达式中使用的特殊字符的约束。为了避免这些问题，上面的查询使用了一个看起来有点笨拙的比较：

LEFT(s.neighborhood,CHAR_LENGTH(@match)) <> @match

这就是取上一个值（例如@match:="Park View"），并将其与下一个值的前导部分（直到"Park View’的长度）进行比较，确定它是否匹配。

---

此查询方法的一个好处是，保证返回的值在后续查询的谓词中"匹配"。假设您正在使用此查询来获取社区列表，并且用户已经选择了一个。这将返回一组值，这些值将"匹配"到每一行。

后续查询可以使用简单谓词（WHERE子句）中的任何返回值来返回匹配的行。例如，如果用户选择了值"大湖"：

SELECT t.*
  FROM mytable t
 WHERE LEFT(t.neighborhood,CHAR_LENGTH('Great Lake') = 'Great Lake'

在我们使用LIKE或REGEXP谓词进行匹配的情况下，我们希望在后续查询的谓词中使用相应的匹配：

SELECT t.*
  FROM mytable t
 WHERE t.neighborhood LIKE CONCAT('Great Lake','%')
SELECT t.*
  FROM mytable t
 WHERE t.neighborhood REGEXP CONCAT('^','Great Lake')