如何查找mySQL行之间的相似性？

Question

我正在尝试创建一个脚本，以找到我的表格行之间的匹配百分比。例如，我的MySQL数据库中的表格products包含字段name（索引、全文本）的值如下：

LG 50PK350 PLASMA TV 50" Plasma TV Full HD 600Hz 
LG TV 50PK350 PLASMA 50"
LG S24AW 24000 BTU
Aircondition LG S24AW 24000 BTU Inverter

你可能会发现它们都有一些相同的关键字。但是第一个名字和第二个名字更相似。此外，第三个和第四个之间的关键字比第一和第二个之间的更相似。

我的MySQL数据库中有数千个产品名称。我想要找到那些具有超过一定相似度百分比（比如60%）的名称。

例如，如我所说，第一个、第二个（以及任何其他匹配项）彼此之间匹配超过60%的名称将以分组格式回显，让我知道这些产品是相似的。第三个和第四个以及任何其他匹配超过60%的名称将在另一组后面回显，告诉我这些产品是匹配的。

如果可能的话，最好回显满足所有分组匹配名称的关键字。例如，LG S24AW 24000 BTU 是包含在第三和第四个名称中的关键字。

最终，我将创建所有这些关键字的列表。

我现在拥有以下查询（正如Jitamaro建议的那样）：

Select t1.name, t2.name From products t1, products t2

创建一个新的名称字段，放在所有其他名称旁边。抱歉我不知道如何正确解释，但这就是它所做的事情：（实际值类似于产品名称）

查询之前

-name-
A
B
C
D
E

查询后

-name- -name-
A        A
B        A
C        A
D        A
E        A
A        B
B        B
C        B
D        B
E        B
.
.
.

是否有使用mySQL或PHP的方法可以找到匹配的名称并提取上述关键词？请分享代码示例。

谢谢社区。

- EnexoOnoma

---

我认为你在这里得不到代码，但可以得到算法。我们不会帮你完成作业。 - Micromega

你销售同一产品的不同商店数量有多少个？所有（或大部分）产品名称是否都包含型号号码，例如“50PK350”？ - Imre L

同一产品可以在多家商店销售，没有数量限制。不同商店销售的同一产品之间有99%的可能包含相同的条款。 - EnexoOnoma

也许可以使用二元组或三元组？... http://bit.ly/o5Iw8o 以及在维基百科上... http://bit.ly/ptpUJ4 - dgnorton

Answer 1

使用LIKE或REGEXP查询数据库：

SELECT * FROM product WHERE product_name LIKE '%LG%';
SELECT * FROM product WHERE product_name REGEXP "LG";

循环结果并使用similar_text()函数：

$a = "LG 50PK350 PLASMA TV 50\" Plasma TV Full HD 600Hz"; // DB value
$b = "LG TV 50PK350 PLASMA 50\"" ; // USER QUERY

$i = similar_text($a, $b, $p);
echo("Matched: $i  Percentage: $p%");

//outputs: Matched: 21 Percentage: 58.3333333333%

您的第二个例子匹配了62.0689655172％：

$a = "LG S24AW 24000 BTU"; // DB value
$b = "Aircondition LG S24AW 24000 BTU Inverter" ; // USER QUERY

$i = similar_text($a, $b, $p);
echo("Matched: $i  Percentage: $p%");

您可以定义一个比40%更高的百分比来匹配产品。
请注意，similar_text()是区分大小写的，因此您应该将字符串转换为小写。

- Pedro Lobito

---

嗨，使用类似的文本函数没问题，但主要问题是如何自动检查所有名称，例如每个名称与另一个名称进行比较。由于数据库将非常庞大，因此不应有手动输入。 - EnexoOnoma

嗨，尼古拉，我不确定我是否理解了“自动检查所有名称，例如每个名称与另一个名称相比”，你能让它更清晰吗？ - Pedro Lobito

请您看一下我更新的问题，里面包含了所有需要的细节。 - EnexoOnoma

每次查看产品都需要昂贵的表扫描吗？ - Jeff Ferland

Answer 2

关于你的第二个问题，levenshtein() 函数 (在 MySQL 中) 是一个不错的选择。

- Alix Axel

Answer 3

当我看到你的例子时，我会考虑如何根据标题寻找类似的产品。从你的两个例子中，我可以看出每行有一件事情比其他所有东西都突出：型号。50PK350可能只出现在与这个型号相关的地方。

现在，MySQL本身并不是为处理这类问题而设计的，但是它上面的一些附加工具可以处理。问题的一部分是在所有这些字段和位置上查询是昂贵的。你真的想以某种方式分割它并对其进行索引。Lucene的相似性类将给那些在所有数据中很少出现但在你的数据中占高比例的单词一个高分。参见 Lucene相似性类的高级解释？ 你还应该查看全文搜索引擎的比较-Lucene、Sphinx、Postgresql、MySQL？ 将每个单词与Lucene相似性类进行评分应该更快，更可靠。您的得分总和应该给出最相关的产品。对于电视，我希望首先看到完全匹配，然后是一些相同尺寸的其他电视，然后是品牌，然后是普通电视等。

无论您做什么，请意识到除非您使用SQL系统之上的另一个工具来创建更好的数据结构来改变数据结构，否则您的查询将太慢且昂贵。我认为Lucene可能是最好的选择。Sphinx或其他未提及的选项也可以考虑。

- Jeff Ferland

---

我认为Lucene的方法（或类似的方法）会非常有效。我已经为一般产品搜索功能实现了几乎相同的方法，尽管它不支持自动建议，但很容易实现，因为Lucene已经返回给定搜索查询的“不同”产品。因此，您只需要设置一个定期脚本，使用新的/更改的/删除的产品更新您的Lucene索引（我必须保留Oracle数据库，因为它不在我的控制范围内...）。 - Simon Lehmann

Answer 4

这比看起来更棘手，您的帖子中有缺失的信息：

• 人们将如何使用此自动完成功能？
• 能否找到产品所有名称很重要吗？因为显然并非所有商店都以相似的方式命名其产品，所以职员可能无法找到他/她找到的产品。
• 您是否有关于哪些产品名称是属于同一产品的信息？
• 从哪个商店搜索是相关的？这个自动完成在哪里使用？
• 自动完成是否真的只建议与您键入的所有单词匹配的产品？（技术上纠正拼写错误并不难）

我认为您需要更清晰地了解您（或更好的是：用户）希望此自动完成功能执行的任务。

自动完成功能非常适合用户友好型特性。它可以模糊地帮助用户，因此没有一个正确答案。您必须找出什么最好用，而不是技术上最容易做到的。

首先确定您想要什么，然后再考虑技术。

- Halcyon

---

你好，感谢你的回复。然而，我认为我的问题已经足够清晰表达我需要什么。应用程序按照我所描述的方式对我最为适用。任何自动完成的问题都已得到解决，并且不同商店的产品名称相似，这是我经过核实的。（我不是那个投反对票的人）。 - EnexoOnoma

我同意Frits的第三点，尤其是那一点。我不知道Nikolai为什么要维护相同产品的不同行，并且他没有提到它们之间的逻辑数据库关系。我认为这就是为什么数据库变得如此庞大的原因。 - kiranking

Answer 5

一个可能的解决方案是使用 Damerau-Levenstein距离。可以像这样使用它。

select *
from products p
where DamerauLevenstein(p.name, '*user input here*')<=*X*

你需要找到最适合你需求的X值。它应该是大于零的整数。你可以将其硬编码、参数化或根据需要计算。

最棘手的问题在于 DamerauLevenstein。它必须是存储过程，实现Damerau-Levenstein算法。我这里没有MySQL，所以我可能会在今天晚些时候为你编写它。

更新：MySQL不支持存储过程中的数组，因此除了为每个函数调用使用临时表之外，没有办法在MySQL中实现Damerau-Levenstein。而这将导致可怕的性能问题。因此，你有两个选择：像Alix Axel建议的那样，在PHP中使用levenstein循环遍历结果，或将数据库迁移到支持数组的PostgreSQL中。

还有一种选项是创建用户定义函数，但这需要用C语言编写此函数，将其链接到MySQL并可能重建MySQL，因此这样做只会增加更多的麻烦。

- J0HN

---

谢谢您，我必须说这个“列表创建”将在每次更新产品时都会被创建，这意味着不是很频繁，所以我想性能不是问题。但我需要继续使用mySQL或/和PHP。 - EnexoOnoma

嗯，我必须承认MySQL不是我最喜欢的数据库，所以使用varbinary作为数组的方式对我来说是新的。 - J0HN

Answer 6

这个问题与这个类似：)

在SQL中实现子字符串搜索的最佳方法是什么？

Trigram可以轻松找到相似的行，在那个问题中我发布了一个php+mysql+trigram解决方案。

- steve

Answer 7

如果您的数据库只是将UPC码作为其中一个字段，并且该字段得到了良好的维护，即您可以相信数据库维护者正确输入并正确反映了物品信息，那么您就不需要做所有您建议的工作。

更好的想法可能是在您的下一个数据库中添加一个UPC字段，并将其限制为唯一。

当数据库用户尝试将已存在的UPC放入数据库时，他们会收到错误提示。

数据库保持完整性。

如果这样的数据库保持其完整性，则永远不需要执行您所建议的操作。

这可能对您当前的任务没有太大帮助（抱歉）-但对于类似的未来数据库，您可能希望考虑一下...

- Peter Sherman

Answer 8

这是一个聚类问题，可以通过数据挖掘方法来解决。 (http://en.wikipedia.org/wiki/Cluster_analysis) 它需要大量的内存和计算密集型操作，不适合数据库引擎。否则，单独的数据挖掘、文本挖掘或业务分析软件就不会存在。

- Tae-Sung Shin

Answer 9

我建议您使用一些全文搜索引擎，例如 sphinx。它具有实现任何算法的可能性。例如，您可以使用“全票”或“任意”搜索。

- Timur

Answer 10

你的方法看起来很可行。对于匹配相似产品，我建议使用三元搜索。这里有一个相当不错的解释，附带 String::Trigram Perl 模块。

我建议使用三元搜索来获取匹配列表，取决于你要处理多少数据以及需要多频繁添加新产品，可以结合一些人工审核。在实践中，我发现这种方法非常有效。

- Michael Mior