java - 根据一组常量搜索词解析大量文本

Question

我有一组搜索词，例如 [+dog -"jack russels"+"fox terrier"]、[+cat +persian -tabby ]。这些可能很长，每个术语可能有 30 个子术语。

我现在有一些在线新闻文章摘录，例如[“我的狐狸梗是世界上最可爱的狗......”]和[”有人看到我丢失的波斯猫了吗？他失踪了……”]。它们不太长，每个最多 500 个字符。

在传统的搜索引擎中，人们期望大量的文章被预处理成索引，在搜索给定的“搜索词”时允许加速，使用集合论/boolean 逻辑将文章减少到仅匹配的文章短语。然而，在这种情况下，我的搜索词的顺序是 ~10^5，我希望能够一次处理一篇文章，以查看该文章将与之匹配的所有搜索词集(即所有 + 术语都在文本中，而 - 术语都没有)。

我有一个可能的解决方案，使用两个映射(一个用于积极的子短语，一个用于消极的子短语)，但我认为它不会非常有效。

一等奖是解决这个问题的图书馆，二等奖是朝着正确的方向解决这个问题。

亲切的问候，

Answer 1

假设匹配需要所有正子项:

将搜索词中的所有子词放入哈希表中。子项是键，值是指向完整搜索项数据结构的指针(应包括唯一 ID 和子项到 boolean 值的映射)。

此外，在处理新闻项时，创建一个“候选”映射，由术语 id 索引。每个候选结构都有一个指向术语定义的指针，一个包含所见子术语的集合和一个“拒绝”标志。

遍历新闻文章中的单词。

对于每个命中，查找候选条目。如果不存在，请创建并添加一个空的。

如果设置了候选拒绝标志，你就完成了。

否则，从术语数据结构中查找子术语。如果为负，则设置拒绝标志。如果为正，则将该子项添加到已见子项集合中。

最后，遍历候选人。所有未被拒绝且已见集合的大小等于该术语的正子术语数的候选者都是您的命中。

实现:https://docs.google.com/document/d/1boieLJboLTy7X2NH1Grybik4ERTpDtFVggjZeEDQH74/edit

运行时为 O(n * m)，其中 n 是文章中的单词数，m 是共享相同子术语的最大术语数(预计会相对较小)。