算法 – Google搜索结果:如何找到包含所有搜索关键字的最小窗口?

算法的复杂度是用来查找包含所有搜索关键词的最小片段?
如上所述,问题是通过一个相当简单的算法来解决的:

从一开始就按顺序浏览输入文本,并检查每个单词:是否在搜索键中.如果单词在关键字中,将其添加到结构的末尾,我们称之为“当前块”.当前块只是一个线性序列的单词,每个单词伴随着在文本中找到的位置.当前块必须保持以下属性:当前块中的第一个字必须存在于当前块中,而且只能存在一次.如果将新单词添加到当前块的末尾,并且上述属性被违反,则必须从块中删除第一个单词.这个过程称为当前块的归一化.归一化是一个潜在的迭代过程,因为一旦你从块中删除了第一个单词,新的第一个单词也可能违反了“属性”,所以你也必须删除它.等等.

所以,基本上是当前块是一个FIFO序列:新的字到达右端,并从左端通过归一化处理去除.

所有你需要解决的问题就是查看文本,维护当前块,在必要时进行规范化,使其满足该属性.您所建立的所有关键字的最短块是问题的答案.

例如,考虑文本

CxxxAxxxBxxAxxCxBAxxxC

使用关键字A,B和C.查看文本,您将构建以下序列块

C
CA
CAB - all words, length 9 (CxxxAxxxB...)
CABA - all words, length 12 (CxxxAxxxBxxA...)
CABAC - violates The Property, remove first C
ABAC - violates The Property, remove first A
BAC - all words, length 7 (...BxxAxxC...)
BACB - violates The Property, remove first B
ACB - all words, length 6 (...AxxCxB...)
ACBA - violates The Property, remove first A
CBA - all words, length 4 (...CxBA...)
CBAC - violates The Property, remove first C
BAC - all words, length 6 (...BAxxxC)

我们建造的最好的块长度为4,这是这种情况下的答案

CxxxAxxxBxxAxx CxBA xxxC

该算法的确切复杂度取决于输入,因为它规定了归一化过程将产生多少次迭代,但忽略归一化,复杂度将平均为O(N * log M),其中N是文本中的单词数M是关键字的数量,O(log M)是检查当前单词是否属于关键字集合的复杂度.

现在说过,我不得不承认,我怀疑这可能不是你需要的.由于您在说明中提及Google,所以您发表的问题陈述可能并不完整.也许在你的情况下文本是索引的? (通过索引上述算法仍然适用,只是变得更有效率).也许有一些棘手的数据库描述文本,并允许一个更有效的解决方案(如不查看整个文本)?我只能猜到你不是在说…

相关文章
相关标签/搜索