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

发布于 2022-08-27 12:17:18 字数 43 浏览 48 评论 0

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

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(3

太阳哥哥 2022-09-03 12:17:18
  • 遍历字典,把每个关键词都拿到文本中查一下,看是否存在,可以用一些高效的文本匹配算法,如KR, KMP, BM, FastSearch

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

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

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

  • 10万个关键词,最短的2个字,最长的3个字,待检查文本是140字的微博,方案2合适
  • 1万个关键词,最短1个字,最长5个字,待检查文本是2万字的论文,方案3或者1合适
随梦而飞# 2022-09-03 12:17:18

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

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

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

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

时间海 2022-09-03 12:17:18

AC自动机比较靠谱吧……

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文