postgresql - 具有编辑距离的组

Question

我有 postgreSQL 9.2

我的任务是在表中找到相似的名字(受一些 levenshtain 距离的限制)。

比如距离为3，表有数据:

|           name            |
|***************************|
|       Marcus Miller       |
|       Marcos Miller       |
|       Macus Miler         |
|       David Bowie         |
|       Dave Grohl          |
|       Dav Grol            |
|           ...             |

我想要得到的结果是这样的:

|       Marcus Miller, Marcos Miller, Macus Miler       |
|       Dave Grohl, Dav Grol                            |
|           ...                                         |

或者

|       Marcus Miller, Marcos Miller                    | 
|       Marcus Miller, Macus Miler                      |
|       Dave Grohl, Dav Grol                            |
|           ...                                         |

我试过这个:

SELECT a.name, b.name
FROM my_table a
JOIN my_table b ON b.id < a.id AND levenshtein(b.name, a.name) < 3;

但是我的数据太慢了。

Answer 1

您的问题存在严重的概念错误； GROUP BY 取某些 equivalence relations (在数学意义上)作为参数并将其用于 partition到 equivalence classes 的 SQL 关系.

问题是你描述的关系，即“是彼此在一定编辑距离内的两个字符串”，不是等价关系。它是对称的和自反的，但不是传递的。为了说明这一点，如果我在您的数据集中添加了一系列将“Marcus Miller”变成“Dave Grohl”的名字，并且该系列中的每个名字都在与前一个名字的编辑距离之内，那么答案应该是什么？

但是，有些算法使用非等价关系(例如几何距离)来划分数据集。 K-means clustering是最著名的例子之一。也许有一种方法可以适应 k-means 或类似的问题，我不知道。