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

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

已经有一个关键词的字典(很大),找出任意一段文本中存在的字典中的关键词


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

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

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

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


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


AC自动机比较靠谱吧……

【热门文章】
【热门文章】