3

我有一个不断增长的关键字数据库。我需要解析传入的文本输入（文章、提要等）并查找数据库中的哪些关键字出现在文本中。关键字的数据库比文本大得多。

由于数据库不断增长（用户添加了越来越多的关键字来关注），我认为最好的选择是将文本输入分解为单词并将其与数据库进行比较。我的主要困境是实现这个比较方案（这个项目将使用 PHP 和 MySQL）。

最简单的实现是针对关键字表创建一个简单的 SELECT 查询，其中有一个巨大的 IN 子句列出所有找到的关键字。

SELECT user_id,keyword FROM keywords WHERE keyword IN ('keyword1','keyword2',...,'keywordN');

另一种方法是在内存中创建一个哈希表（使用 memcache 之类的东西）并以相同的方式对其进行检查。

有没有人对这种搜索有任何经验，并对如何更好地实现这一点有任何建议？我还没有尝试过任何这些方法，我现在只是在收集想法。

4

6 回答 6

3

在文本流中搜索多个关键字的经典方法是Aho-Corasick 有限自动机，它使用要搜索的文本中的时间线性。您需要进行小的修改以仅在单词边界上识别字符串，或者检查找到的关键字并确保它们没有嵌入更大的单词中可能会更简单。

您可以在fgrep. 更好的是，Preston Briggs 用 C 语言编写了一个非常不错的实现，它完全可以进行您所说的关键字搜索。（它在程序中搜索“有趣的”标识符的出现。） Preston 的实现作为Noweb literate-programming tool的一部分分发。你可以找到一种方法从 PHP 调用这段代码，或者你可以用 PHP 重写它——识别本身大约是 220 行 C，而主程序是另外 135 行。

所有提议的解决方案，包括Aho-Corasick，都具有以下共同特性：

  • 一个预处理步骤，花费的时间和空间与数据库中的关键字数量成正比。

  • 一个搜索步骤，所花费的时间和空间与文本长度加上找到的关键字数量成正比。

Aho-Corasick 在搜索步骤中提供了相当好的比例常数，但如果您的文本很小，这无关紧要。事实上，如果您的文本很小而数据库很大，您可能希望尽量减少预处理步骤中使用的内存量。来自世界上最快的拼字游戏程序的Andrew Appel 的 DAWG 数据结构可能会成功。

于 2009-01-02T23:00:06.117 回答
1

一般来说，

  1. 将文本分解成单词

    湾。将单词转换回规范根形式

    C。删除常用连词

    d。剥离重复项

  2. 将单词插入临时表，然后对关键字表进行内部连接，或者（如您所建议）将关键字构建到复杂的查询条件中

缓存一个 3 或 4 个字母的哈希数组可能是值得的，用它来预过滤潜在的关键字；您将不得不进行试验以找到内存大小和有效性之间的最佳折衷。

于 2009-01-02T21:04:39.797 回答
0

I hacked up some code for scanning for multiple keywords using a dawg (as suggested above referencing the Scrabble paper) although I wrote it from first principles and I don't know whether it is anything like the AHO algorithm or not.

http://www.gtoal.com/wordgames/spell/multiscan.c.html

A friend made some hacks to my code after I first posted it on the wordgame programmers mailing list, and his version is probably more efficient:

http://www.gtoal.com/wordgames/spell/multidawg.c.html

Scales fairly well...

G

于 2009-02-11T22:44:47.070 回答
0

我不是 100% 清楚你在问什么，但也许你正在寻找的是倒排索引？

更新：

您可以使用倒排索引一次匹配多个关键字。

将新文档拆分为标记，并将与文档标识符配对的标记插入倒排索引表中。一个（相当非规范化的）倒排索引表：

inverted_index
-----
document_id keyword

如果您手动搜索 3 个关键字：

select document_id, count(*) from inverted_index
  where keyword in (keyword1, keyword2, keyword3)
  group by document_id 
  having count(*) = 3

如果您有一个您关心的关键字表，只需使用内部联接而不是 in() 操作：

keyword_table
----
keyword othercols

select keyword_table.keyword, keyword_table.othercols from inverted_index 
   inner join keyword_table on keyword_table.keyword=inverted_index.keyword
   where inverted_index.document_id=id_of_some_new_document

这是否更接近你想要的？

于 2009-01-02T20:47:42.513 回答
0

我会在这里做两件事。

首先（这与问题没有直接关系）我会按用户分解和划分用户关键字。拥有更少数据的更多表，理想情况下在不同的服务器上进行分布式查找，其中切片或用户范围存在于不同的切片上。Aka，所有 usera 的数据都存在于切片 1 上，userb 存在于切片 2 上，等等。

其次，我有某种内存哈希表来确定关键字的存在。这也可能被联合起来分发查找。对于 n 个存在关键字的服务器，对关键字进行哈希处理并将其修改为 n，然后将这些关键字的范围分布在所有 memcached 服务器上。这种快速方法可以让您说正在监视关键字 x，对其进行哈希处理并确定它将在哪个服务器上运行。然后进行查找并收集/聚合被跟踪的关键字。

到那时，您至少会知道哪些关键字正在被跟踪，并且您可以获取用户切片并执行后续查找以确定哪些用户正在跟踪哪些关键字。

简而言之：SQL 在这里不是一个理想的解决方案。

于 2009-01-02T21:01:53.733 回答
0

您是否考虑过使用像 Sphinx这样的全文解决方案？

我在这里说的是我的帽子，因为我自己没有使用它。但它作为一种高速全文搜索解决方案受到了广泛关注。它可能比您使用的任何关系解决方案都具有更好的扩展性。

这是一篇关于在 MySQL 中使用 Sphinx 作为全文搜索解决方案的博客。

于 2009-01-02T22:41:23.643 回答