如何高效的判断一段文本中是否包含一个字典中的某个词?
已经有一个关键词的字典(很大),找出任意一段文本中存在的字典中的关键词
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
已经有一个关键词的字典(很大),找出任意一段文本中存在的字典中的关键词
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
接受
或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
发布评论
评论(3)
遍历字典,把每个关键词都拿到文本中查一下,看是否存在,可以用一些高效的文本匹配算法,如KR, KMP, BM, FastSearch
字典用HashSet存储,对要检查的文本切词,比如已知关键词字典最短的是两个中文字,最长的是四个字,那就按2字、3字、4字各做一遍切词得到三套切词结果(为降低复杂度,不必考虑语义和词性)。然后遍历切词结果,把每个切出来的词拿到HashSet里查找一下在不在
上述两种方案的合体:按方案2的描述,对待检查文本切词,切词结果做成HashSet(就是三套切词结果的HashSet再求个并集,是不是有点像倒排索引),然后遍历关键词字典,对每个关键词,在HashSet中查找是否存在
根据字典和文本的数据规模确定采用哪种方案,比方说:
如果字典非常大,遍历字典匹配是不行的,hashset花费的空间也非常大。
字典保存上,lz可以选择用trie树。这是建立在分词的基础上的,分完词之后,看词是否在trie树中即可(和hashset类似的方法)。
直接用AC自动机之类的算法做多串匹配。这样的缺陷是某些不是词的相邻字会被匹配上呢。
trie一般只是对前缀作了压缩。如果lz要求高的话,可以尝试最小化该自动机(trie是一个无环自动机)。
AC自动机比较靠谱吧……