我有一组搜索术语,如[ + dog - "jack russels"+"fox terrier" ],[ + cat + persian -tabby ].这些可能很长,每个学期可能有30个子术语.
我现在有一些在线新闻文章摘录,如[ "我的狐狸梗是世界上最可爱的狗......" ]和[ "有人见过我丢失的波斯猫吗？他失踪了......" ].它们不会太长,每个最多可能有500个字符.
在传统的搜索引擎中,人们期望大量的文章被预处理成索引,允许在搜索给定的"搜索术语"时加速,使用集合论/布尔逻辑将文章减少到仅与短语匹配的文章.但是,在这种情况下,我的搜索词的顺序是~10 ^ 5,我希望能够一次处理一篇文章,以查看该文章将匹配的所有搜索词集(即所有+条款都在文本中,而没有-条款.
我有一个可能的解决方案,使用两个地图(一个用于正面的子短语,一个用于负面的子短语),但我不认为它会非常有效.
一等奖将是一个解决这个问题的图书馆,二等奖是推动解决这个问题的正确方向.
亲切的问候,
假设一场比赛需要所有正子项：
将搜索词中的所有子词放入哈希表中。子项是键，值是指向完整搜索项数据结构的指针（应包括唯一的 id 和子项到布尔值的映射）。
此外，在处理新闻项时，创建一个“候选”映射，并按术语 id 进行索引。每个候选结构都有一个指向术语定义的指针、一个包含所见子术语的集合和一个“拒绝”标志。
重复新闻文章中的文字。
对于每个命中，查找候选条目。如果不存在，请创建并添加一个空的。
如果设置了候选拒绝标志，则您已完成。
否则，从术语数据结构中查找子术语。如果为负，则设置拒绝标志。如果为正，则将该子项添加到已看到的子项集中。
最后，迭代候选者。所有未被拒绝且可见集合的大小等于该术语的正子术语数量的候选者都是您的命中。
实施：https://docs.google.com/document/d/1boieLJboLTy7X2NH1Grybik4ERTpDtFVggjZeEDQH74/edit
运行时间为 O(n * m)，其中 n 是文章中的单词数，m 是共享相同子项的最大术语数（预计相对较小）。