如何高效的判断一段文本中是否包含一个字典中的某个词？

Question

已经有一个关键词的字典（很大），找出任意一段文本中存在的字典中的关键词

Answer 1

• 遍历字典，把每个关键词都拿到文本中查一下，看是否存在，可以用一些高效的文本匹配算法，如KR, KMP, BM, FastSearch

• 字典用HashSet存储，对要检查的文本切词，比如已知关键词字典最短的是两个中文字，最长的是四个字，那就按2字、3字、4字各做一遍切词得到三套切词结果（为降低复杂度，不必考虑语义和词性）。然后遍历切词结果，把每个切出来的词拿到HashSet里查找一下在不在

• 上述两种方案的合体：按方案2的描述，对待检查文本切词，切词结果做成HashSet（就是三套切词结果的HashSet再求个并集，是不是有点像倒排索引），然后遍历关键词字典，对每个关键词，在HashSet中查找是否存在

根据字典和文本的数据规模确定采用哪种方案，比方说：

• 10万个关键词，最短的2个字，最长的3个字，待检查文本是140字的微博，方案2合适
• 1万个关键词，最短1个字，最长5个字，待检查文本是2万字的论文，方案3或者1合适

Answer 2

如果字典非常大，遍历字典匹配是不行的，hashset花费的空间也非常大。

1. 字典保存上，lz可以选择用trie树。这是建立在分词的基础上的，分完词之后，看词是否在trie树中即可（和hashset类似的方法）。

2. 直接用AC自动机之类的算法做多串匹配。这样的缺陷是某些不是词的相邻字会被匹配上呢。

trie一般只是对前缀作了压缩。如果lz要求高的话，可以尝试最小化该自动机（trie是一个无环自动机）。

Answer 3

AC自动机比较靠谱吧……