database - 需要一些帮助(搜索算法)

Question

我需要一些帮助来解决这个问题:

作为输入，我有一个字符串，看起来像 Blue cat green eyes 2342342 , 或者它可以是 Cat blue eyes green 23242或任何其他单词排列。

在我的数据库表中有一些数据。例如，其中一列称为 keyWords。

这是该表的示例:

我的任务是在我的数据库表列 KEYWORDS 中查找记录，它与输入字符串中的一些词相匹配。

例如:对于字符串"Blue cat green eyes 2342342" "Cat blue eyes green 23242"和“Cat 23242 eyes blue green”结果必须是“blue cat”(我表格的第一行)。我能想象如何解决这个任务的唯一方法是这样的:

1. 始终从字符串中取出每个单词。
2. 用 %like% 搜索每一个词在表格列中。
3. 如果未找到，则表示该词不是关键字，我们对它不感兴趣。
4. 如果找到一次 - 太好了!毫无疑问，这就是我们要寻找的。
5. 如果有多个结果:
6. 从字符串中的所有单词中提取所有单词，这些单词未经测试但始终如一地提取每个单词。
7. 用%like%搜索这个词在第 2 步的结果中。
8. 等等……

这个算法的图形模式是here

但是如果表中有很多记录并且我的输入字符串包含大量单词，那么这个算法看起来会运行得很慢。

那么，我的问题是:是否有任何特殊的算法可以帮助解决这个问题？

Answer 1

你可以采用另一个表如

ID    KeywordID     Word
1     1             blue
2     2             blue
3     1             cat

并转换字符串

"Blue cat green eyes 2342342"

在一系列索引和计数中:

SELECT KeywordID, COUNT(*) FROM ancillary WHERE Word IN ('blue','cat','green','eyes'...)

这将执行一系列精确匹配并返回，比方说，

KeywordID   Count
1           2
2           1

然后你知道id为1的关键字组有两个词，这意味着计数为2匹配所有。所以keywordid 1就满足了。第 2 组也有两个词 (black, cat)，但只找到一个，匹配存在但不完整。

如果你同时记录了关键字集合大小和关键字ID，那么来自同一个ID的所有关键字将具有相同的KeywordSize，你也可以对其进行GROUP BY:

KeywordID   KeywordSize    Count
1           2              2
2           2              1

甚至可以SELECT COUNT(*)/KeywordSize AS match ... ORDER BY match 并按相关性对关键字匹配进行排序。

当然，一旦你有了KeywordID，你就可以在关键字表中找到它。

实现

您想将关键字列表“black angry cat”添加到现有表中。

因此，您将此关键字列表分解为单词:并得到“black”、“angry”和“cat”。

您通常在已有的表中插入关键字列表，并检索新创建的行的 ID，假设它是 1701。

现在您将单词插入我们称为“辅助”的新表中。此表仅包含主表的关键字行 ID、单个词以及该词来自的词表的大小。

我们知道我们总共要插入 3 个单词，对于表第 1701 行，所以 size=3 并且我们插入这些元组:

(1701, 3, 'black')
(1701, 3, 'cat')
(1701, 3, 'angry')

(这些将收到自己的唯一 ID，但这与我们无关)。

一段时间后我们收到一句话，

'Schroedinger cat is black and angry'

我们可以首先针对要删除的空词列表运行查询，例如“is”和“and”。但这不是必需的。

然后我们可以运行与单词一样多的查询，从而发现任何地方都没有包含“Schroedinger”的行，我们可以将其删除。但这也不是必需的。

最后，我们针对辅助构建真实查询:

SELECT KeywordID, COUNT(*) AS total, ListSize*100/COUNT(*) AS match
    FROM ancillary WHERE Word IN ('Schroedinger','cat','is','black','and','angry')
    GROUP BY KeywordID;

WHERE 将返回这些行:

(1234, 'black') -- from 'black cat'
(1234, 'cat')   -- from 'black cat'
(1423, 'angry') -- from 'angry birds'
(1701, 'cat')   -- from 'black angry cat'
(1701, 'angry') -- from 'black angry cat'
(1701, 'black') -- from 'black angry cat'
(1999, 'cat')   -- from 'nice white cat'

因此 GROUP 将返回这些行的 KeywordID 及其基数:

1423   1   50%
1701   3  100%
1234   2  100%
1999   1   33%

现在您可以按匹配率降序排序，然后按列表大小降序排序(因为匹配 3 个单词的 100% 比匹配 2 个单词的 100% 好，匹配 2 中的 1 比匹配 3 中的 2 好):

1701   3  100% -- our best match
1234   2  100% -- second runner
1423   1   50%
1999   1   33%

您还可以在一个查询中检索您的第一个表，增加匹配率:

SELECT mytable.*, total, match FROM
mytable JOIN (
SELECT KeywordID, COUNT(*) AS total, ListSize*100/COUNT(*) AS match
    FROM ancillary WHERE Word IN ('Schroedinger','cat','is','black','and','angry')
    GROUP BY KeywordID
) AS ancil ON (mytable.KeywordID = ancil.KeywordID)
ORDER BY match DESC, total DESC;

最大的成本是“辅助”中的精确匹配，它必须在 Word 列上建立索引。