如何找到mySQL行之间的相似性 - How to find similarity between mySQL rows?

我试图创建一个脚本，找到我的表行之间的匹配百分比。例如，我的mySQL数据库在表products中包含字段name(索引，FULLTEXT)，值如

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%，将以组样式的格式回显，让我知道这些产品是相似的。第3、第4和任何其他匹配度超过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，将找到我匹配的名称和提取关键字，我上面描述的?请分享代码示例。

感谢社区。

使用LIKE OR 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()是区分大小写的，所以你应该将字符串小写。

关于你的第二个问题，levenshtein()函数(在MySQL中)将是一个很好的候选。

当我看你的例子时，我考虑如何根据标题找到类似的产品。从你的两个例子中，我可以看到每一行中最突出的一点:型号。50PK350可能不会出现在其他地方，除了与这个模型有关。

现在，MySQL本身并不是为处理这样的问题而设计的，但是上面的一些附加工具可以。部分问题在于，在所有位置上查询所有这些字段的成本很高。你需要以某种方式拆分它并索引它。Lucene的相似性类会给那些很少在所有数据中出现，但在你的数据中出现的百分比很高的词打高分。参见Lucene相似类的高级解释?

你还应该看看全文搜索引擎的比较- Lucene, Sphinx, Postgresql, MySQL?

根据Lucene相似度类对每个单词进行评分应该更快更可靠。你的分数的总和应该给你最相关的产品。对于电视，我希望首先看到完全匹配的，然后是一些相同尺寸的其他产品，然后是品牌，然后是一般的电视，等等。

无论您做什么，都要意识到，除非您通过在SQL系统之上使用另一个工具来更改数据结构以创建更好的数据结构，否则您的查询将太慢且代价高昂。我认为Lucene可能是可行的。狮身人面像或其他未提及的选择也可能在考虑之中。

这比看起来更棘手，你的帖子中缺少信息:

人们将如何使用这个自动完成功能?
你能找到一个产品的所有名称是否相关?因为显然不是所有商店的产品名称都相似，所以店员可能无法找到他找到的产品。
您是否有相同产品的产品名称的信息?
是否与您正在搜索的商店相关?这个自动补全功能在哪里使用?
自动补全功能真的应该只推荐与所有您输入的单词匹配的产品吗?(从技术上讲，纠正错字并不难)

我认为你需要更清楚地了解你(或者更好的是:用户)希望这个自动完成功能做什么。

自动完成功能是一个非常友好的类型功能。它可能以一种模糊的方式帮助用户，所以没有单一的正确答案。你必须找出最有效的方法，而不是技术上最简单的方法。

先弄清楚你想要什么，然后再担心技术。

一个可能的解决方案是使用达默劳-列文斯坦距离。可以这样使用

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

你必须找出最适合你需要的X。它应该是大于0的整数。您可以根据需要对其进行硬编码、参数化或计算。

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

Update: MySQL在存储过程中不支持数组，所以没有办法在MySQL中实现Damerau-Levenstein，除了为每个函数调用使用临时表。这将导致糟糕的表现。所以你有两个选择:循环通过结果在PHP与levenstein像Alix Axel建议，或迁移你的数据库到PostgreSQL，数组的支持。还有一个创建用户定义函数的选项，但这需要用C编写这个函数，将其链接到MySQL，并可能重新构建MySQL，所以这样只会增加更多的麻烦。

你的方法似乎很合理。为了匹配类似的产品，我建议使用三元组搜索。这里有一个很好的解释，它是如何与String::Trigram Perl模块一起工作的。

我建议使用三元组搜索来获得匹配列表，也许还可以根据需要处理的数据量和添加新产品的频率进行一些手动检查。我发现这种方法在实践中非常有效。

也许你想从2个字符串中找到最长的公共子字符串?然后你需要为你的每个字符串计算一个后缀树，见这里http://en.wikipedia.org/wiki/Longest_common_substring_problem.

如果你想检查所有的名字对其他你需要在mysql交叉连接。有很多方法可以做到这一点:

1. Select a, b From t1, t2
2. Select a, b From t1 Join t2
3. Select a, b From t1 Cross Join t2

然后可以遍历结果。当我说创建一个包含n^2-(n-1)个元素的2d数组并且每个元素彼此连接时，这是相同的。

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

听起来你费了这么大的功夫来解释一个复杂的场景，然后说你想忽略最优答案，只让我们给你一个"握手"协议(所有东西都要和所有还没有被比较过的东西进行比较)。所以…伪代码:

select * from table order by id
while (result) {
    select * from table where id > result_id
}

那就行了。

如果你的数据库只是有一个UPC代码作为它的字段之一，并且这个字段被很好地维护，也就是说，你可以相信它是由数据库维护者正确输入的，并且正确地反映了项目是什么——那么你就不需要做你建议的所有工作。

一个更好的主意可能是在你的下一个数据库中有一个UPC字段——并将其约束为唯一的。

数据库用户尝试将一个已经存在的UPC放入数据库——他们得到一个错误。

数据库保持完整。

如果这样一个数据库保持了它的完整性，那么就没有必要按照你的建议去做了。

这可能对你当前的任务没有多大帮助(抱歉)——但对于未来类似的数据库，你可能希望考虑一下……

我建议你使用一些全文搜索引擎，比如sphinx。它有可能实现任何你想要的算法。例如，您可以使用"quorum"或"any"搜索。

似乎您可能总是想返回最短的字符串??这更像是一个问题。但是你可能会有一些像…

SELECT * FROM products LIMIT 1
WHERE product_name like '%LG%'
ORDER BY LENGTH(product_name) ASC

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

这个问题与这个问题相似:

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

Trigram可以很容易地找到类似的行，在这个问题上，我发布了一个php+mysql+ Trigram解决方案。

可以使用LIKE在表中查找类似的产品名称。例如:

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

这是另一个想法(但我投票给levenshtein()):

创建一个临时表，包含名称中使用的所有单词及其频率。

选择结果范围(最流行的词可能是LCD或LED等词，最独特的词可能是好的，它们可能是产品的实际名称)

建议每个结果词:

结果与
结果包含这些单词的最长子字符串(如:http://forums.mysql.com/read.php?10,277997,278020#msg-278020)。

好的，我想我是在尝试实现非常相似的东西。它可以工作相同的谷歌chrome地址栏。当你输入地址时，它会给你建议。在我看来，这就是你想要达到的目标。

对于那件事，我不能给你确切的解决办法，只能给你一些建议。

你需要实现下拉框，人们开始输入他们正在寻找的产品
然后你需要得到下拉框的当前值，然后像上面发布的家伙一样运行查询。可以是"SELECT * FROM product WHERE product_name LIKE 'LG%';"
保存查询结果
刷新页面
将查询结果添加到下拉菜单

注意:

您需要将查询结果保存在某个地方，如HTML代码的文本文件，即。"option" LG TS 600"/option"(在"option"后面加上<>括号)。这些值将用于在页面刷新后填充选项框。您需要为用户设置用户会话，以便为同一用户获得相同的结果，否则如果更多用户同时使用搜索，则可能会发生冲突。有了搜索id和会话id，你就可以匹配它们。您可以将其保存在文件或表中。桌子会更方便。实际上在我看来，整个子系统就是你要找的。

我希望它有帮助。