4

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

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

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

下面是这个表的一个例子：

在此处输入图像描述

我的任务是在我的数据库表列 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. 等等……</li>

该算法的图形模式在这里

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

所以，我的问题是：有没有什么特殊的算法可以帮助解决这个任务？

4

2 回答 2

4

您可以采用另一张桌子，例如

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 组也有两个词（黑色、猫）但只找到一个，匹配存在但不完整。

如果您还记录关键字集大小和关键字 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”。

您通常在已有的表中插入关键字列表，然后检索新创建的行的 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%

现在可以按匹配率降序排序，然后按列表大小降序排序（因为匹配 100% 的 3 个单词优于匹配 100% 的 2，匹配 1 in 2 优于匹配 2 in 3）：

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列上索引的“辅助”中的精确匹配。

于 2012-10-26T11:54:03.033 回答
1

你可能想看看全文搜索引擎，比如狮身人面像：http ://sphinxsearch.com/

或者，另一种方式 - 制作存储过程，将搜索字符串拆分为关键字，使用指定的分隔符并在 DB 列中查找每个关键字的 charindex（取决于您的数据库管理系统）

于 2012-10-26T11:12:53.713 回答