查询数据库的记录以获得几乎相似的匹配字符串值

Question

场景是我有一个包含地址和城市字段的大约500,000条记录的庞大数据库,其中没有这样的标准方式来插入值,因此多个用户,例如一些已将城市值插入班加罗尔而另一个已插入其城市价值为begaluru或benglore(拼写错误)

同样在地址 字段的情况下,具有多个记录的相同用户已插入其地址值但是值不是特别相同的例如Mountville park Thomas gate和Montlee park thonas gte.

我需要获取所有那些具有相同和几乎相似的值(不知何故)的地址和城市的记录.

有没有办法让这些记录具有几乎相似但无法比拟的值？

谢谢.

Answer 1

这将是一个昂贵的查询，但由于这有望成为一次性操作，因此您可能会考虑查看编辑距离公式。

为了避免需要计算表的笛卡尔积的距离，您可以首先缩小要与更快的健全性检查进行比较的城市和地址集的范围......例如它们以相同的字母开头，并且具有相似的长度。

然后，您可以首先仅返回Levenshtein distance非常小的记录，然后逐渐增加距离，直到开始出现太多误报。

这是直接在 MySql 中的实现：

CREATE FUNCTION levenshtein( s1 VARCHAR(255), s2 VARCHAR(255) ) 
  RETURNS INT 
  DETERMINISTIC 
  BEGIN 
    DECLARE s1_len, s2_len, i, j, c, c_temp, cost INT; 
    DECLARE s1_char CHAR; 
    -- max strlen=255 
    DECLARE cv0, cv1 VARBINARY(256); 
    SET s1_len = CHAR_LENGTH(s1), s2_len = CHAR_LENGTH(s2), cv1 = 0x00, j = 1, i = 1, c = 0; 
    IF s1 = s2 THEN 
      RETURN 0; 
    ELSEIF s1_len = 0 THEN 
      RETURN s2_len; 
    ELSEIF s2_len = 0 THEN 
      RETURN s1_len; 
    ELSE 
      WHILE j <= s2_len DO 
        SET cv1 = CONCAT(cv1, UNHEX(HEX(j))), j = j + 1; 
      END WHILE; 
      WHILE i <= s1_len DO 
        SET s1_char = SUBSTRING(s1, i, 1), c = i, cv0 = UNHEX(HEX(i)), j = 1; 
        WHILE j <= s2_len DO 
          SET c = c + 1; 
          IF s1_char = SUBSTRING(s2, j, 1) THEN  
            SET cost = 0; ELSE SET cost = 1; 
          END IF; 
          SET c_temp = CONV(HEX(SUBSTRING(cv1, j, 1)), 16, 10) + cost; 
          IF c > c_temp THEN SET c = c_temp; END IF; 
            SET c_temp = CONV(HEX(SUBSTRING(cv1, j+1, 1)), 16, 10) + 1; 
            IF c > c_temp THEN  
              SET c = c_temp;  
            END IF; 
            SET cv0 = CONCAT(cv0, UNHEX(HEX(c))), j = j + 1; 
        END WHILE; 
        SET cv1 = cv0, i = i + 1; 
      END WHILE; 
    END IF; 
    RETURN c; 
  END;

然后可以在辅助函数中使用该函数，如下所示：

CREATE FUNCTION levenshtein_ratio( s1 VARCHAR(255), s2 VARCHAR(255) ) 
  RETURNS INT 
  DETERMINISTIC 
  BEGIN 
    DECLARE s1_len, s2_len, max_len INT; 
    SET s1_len = LENGTH(s1), s2_len = LENGTH(s2); 
    IF s1_len > s2_len THEN  
      SET max_len = s1_len;  
    ELSE  
      SET max_len = s2_len;  
    END IF; 
    RETURN ROUND((1 - LEVENSHTEIN(s1, s2) / max_len) * 100); 
  END; 

您还可以levenshtein通过传入当前的最大距离来优化该函数...如果该函数通过该距离，则退出而不计算确切的距离。