我基本上有一个两列的表,其中包含一个主键和大约20,000行的公司名称。
我的任务是找到所有重复的条目。
我最初尝试使用soundex,但它会匹配完全不同的公司,只是因为它们的首字母相似。因此,这使我着手了levenshtein距离算法。
问题是查询需要不确定的时间。我已经离开它约10个小时了,它仍然没有回应。
这是查询:
SELECT *
FROM `Companies` a, `Companies` b
WHERE levenshtein(a.name, b.name)<5
AND a.id<>b.id
这是我正在使用的levenshtein函数(从这篇文章中得到了)
DELIMITER $$
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$$
DELIMITER ;
我该怎么做才能加快查询速度?
因此,我在此线程中实施了很多建议以减少查询时间。
我索引了名称collumn,将a.id <> b.id更改为a.id <b.id以减少重新比较已比较的行,并向其中添加LEFT(a.name,3)= LEFT(b.name,3)防止在前三个字符容易排除的行上执行沉重的levenshtein函数。
这是我使用的查询:
SELECT *
FROM `Companies` a, `Companies` b
WHERE LEFT(a.name, 3) = LEFT(b.name, 3)
AND a.id < b.id
AND levenshtein(a.name, b.name)<3
这花费了大约2个小时才能完成,并给了我964个结果。之后,我将结果导出为.csv并将其导入到另一个表TABLE 2中。表2的结构如下:
COL 1, COL 2, COL 3, COL 4
a.id, a.name, b.id, b.name
我注意到,表2中有很多结果实际上是不同的公司,但是相距仅几个字符,从而使levinshtein距离无法有效地对它们进行排序。例如:“ Body FX”,“ Body Fit”或“ Baxco”,“ Baxyl”。
我试图通过比较字符串的最后两个字符的RIGHT()来过滤出更多名称,但是由于某些名称是复数形式而遇到了问题,例如“ Aroostock Medical Center”和“ Aroostock Medical Centers”。因此,我编写了自己的RIGHT_PLURAL()函数,该函数忽略了复数字符。
DROP FUNCTION IF EXISTS RIGHT_PLURAL;
DELIMITER $$
CREATE FUNCTION RIGHT_PLURAL(input VARCHAR(50), right_input INT)
RETURNS VARCHAR(50)
BEGIN
DECLARE length INT;
SET length = LENGTH(input);
IF RIGHT(input, 2)="'s" THEN
RETURN SUBSTR(input, length-right_input-1, right_input);
ELSEIF RIGHT(input, 1)="s" THEN
RETURN SUBSTR(input, length-right_input, right_input);
ELSE
RETURN RIGHT(input, right_input);
END IF;
END;
$$
DELIMITER ;
我跑了
SELECT *
FROM `TABLE 2`
WHERE RIGHT_PLURAL(
`COL 2` , 2
) = RIGHT_PLURAL(
`COL 4` , 2
)
并且减少到893个重复项。我很满意 我将结果集复制到了表3,然后运行以下命令。
DELETE
FROM `Companies`
WHERE `id` IN ( SELECT `COL 1` FROM `TABLE 3` )
我的数据库现在基本上是免费的!剩下的仅有的几只流浪者是由于姓名的严重拼写错误。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句