代码之家 › 专栏 › 技术社区 › Eran Galperin

实现关键字比较方案(反向搜索)

tokenize keyword search mysql php

Eran Galperin · 技术社区 · 16 年前

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

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

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

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

另一种方法是在内存中创建一个哈希表(使用类似memcache的东西)并以相同的方式检查它。

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

6 回复 | 直到 16 年前

Norman Ramsey 16 年前

在文本流中搜索多个关键字的经典方法是 Aho-Corasick finite automaton ,它在要搜索的文本中使用时间线性。您可能希望进行一些小的调整,以便只识别单词边界上的字符串,或者检查找到的关键字并确保它们没有嵌入到较大的单词中可能会更简单。

您可以在 fgrep . 更妙的是,Preston Briggs用C编写了一个非常好的实现,它可以完成你所说的关键字搜索。(它搜索程序中出现的“有趣的”标识符。)Preston的实现作为 Noweb literate-programming tool . 你可以从PHP中找到调用这段代码的方法,也可以用PHP重写它——recognize本身是大约220行C,主程序是另外135行。

所有提议的解决方案, 包括 Aho Corasick,有这些共同点:

一种预处理步骤,所需的时间和空间与数据库中关键字的数目成正比。
一种搜索步骤,所需时间和空间与文本长度加上找到的关键字数成比例。

Aho Corasick在搜索步骤中提供了更好的比例常数,但是如果你的文本很小,这无关紧要。事实上,如果你的文本很小,你的数据库很大,你可能想要最小化预处理步骤中使用的内存量。Andrew Appel的DAWG数据结构 the world's fastest scrabble program 可能会成功。

Hugh Bothwell 16 年前

一般来说,

把课文译成文字

b.将单词转换回规范的根形式

c.删除常用连词

d.剥离副本
将单词插入临时表,然后对关键字表进行内部联接, 或者(如您所建议的)将关键字构建到复杂的查询条件中

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

ÊÉÄ±u 16 年前

我不是百分之百清楚你在问什么,但也许你在找的是 inverted index ?

更新:

可以使用反向索引一次匹配多个关键字。

将新文档拆分为标记,并将与文档标识符成对的标记插入到反向索引表中。一个(相当非规范化的)反向索引表:

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

有没有更接近你想要的?