从搜索文档中查找最小片段的算法？

Question

我一直在阅读Skiena出色的"算法设计手册",并在其中一个练习中被挂了.

问题是:"给定三个单词的搜索字符串,找到包含所有三个搜索词的文档的最小片段 - 即,其中包含最少数量单词的片段.您将获得这些单词的索引位置在出现的搜索字符串中,例如word1:(1,4,5),word2:(4,9,10)和word3:(5,6,15).每个列表按排序顺序排列,如上所述. "

我想出的任何东西都是O(n ^ 2)......这个问题出现在"排序和搜索"一章中,所以我假设有一种简单而聪明的方法.我现在正在尝试使用图表,但这似乎有些过分.

想法？谢谢

Answer 1

除非我忽略了一些东西,否则这是一个简单的O(n)算法:

1. 我们将用(x,y)代表片段,其中x和y分别是片段开始和结束的位置.
2. 如果它包含所有3个搜索词,则片段是可行的.
3. 我们将从不可行的片段(0,0)开始.
4. 重复以下操作,直到y到达字符串结尾:
   5. 如果当前片段(x,y)可行,则转到片段(x + 1,y)
      Else(当前片段不可行)进入片段(x,y + 1)
5. 选择我们经历过的所有可行片段中最短的片段.

运行时间 - 在每次迭代中,x或y增加1,显然x不能超过y,y不能超过字符串长度,因此迭代总数为O(n).此外,在这种情况下可以在O(1)处检查可行性,因为我们可以跟踪每个单词在当前片段中出现的次数.我们可以将此计数维持在O(1),每次x或y增加1.

正确性 - 对于每个x,我们计算最小可行片段(x,？).因此,我们必须重温最小的片段.此外,如果y是最小的y,使得(x,y)是可行的,那么如果(x + 1,y')是可行的片段y'> = y(这个位是为什么这个算法是线性的而其他的是'n'' T).

Answer 2

我已经发布了一个相当简单的算法,可以在这个答案中解决这个问题

Google搜索结果:如何查找包含所有搜索关键字的最小窗口？

但是,在该问题中,我们假设输入由文本流表示,并且单词存储在易于搜索的集合中.

在您的情况下,输入的表示略有不同:作为一组向量,每个单词的排序位置.通过简单地将所有这些矢量合并到(position, word)按位置排序的单个矢量矢量中,该表示可以容易地变换为上述算法所需的内容.它可以按字面意思完成,或者可以通过将原始向量放入优先级队列(按照其第一个元素排序)来"虚拟地"完成.在这种情况下从队列弹出元素意味着从队列中的第一个向量弹出第一个元素,并可能根据其新的第一个元素将第一个向量下沉到队列中.

当然,由于您的问题陈述明确地将单词数量固定为三,您可以简单地检查所有三个数组的第一个元素,并在每次迭代时弹出最小的一个.这给了你一个O(N)算法,其中N是所有数组的总长度.

此外,您对问题的陈述似乎表明目标词可能在文本中重叠,这是相当奇怪的(假设您使用术语"词").这是故意的吗？在任何情况下,它对上述链接算法都没有任何问题.

Answer 3

从这个问题来看,似乎你在文档中给出了每个n个 "搜索词"(word1,word2,word3,...,word n)的索引位置.使用排序算法,与搜索词相关联的n个独立阵列可以容易地以递增的数字顺序表示为所有索引位置的单个阵列,并且与阵列中的每个索引(索引阵列)相关联的词标签.

基本算法:

(无论该问题的海报是否意图允许两个不同的搜索词在同一索引号上共存,设计工作.)

首先,我们定义一个简单的函数来测量一个片段的长度,该片段包含索引数组中给定起点的所有n个标签.(从数组的定义可以明显看出,数组上的任何起点都必然是n个搜索标签之一的索引位置.)该函数只是跟踪函数迭代元素时看到的唯一搜索标签.在数组中,直到观察到所有n个标签.片段的长度定义为找到的最后一个唯一标签的索引与索引数组中起始点的索引(找到的第一个唯一标签)之间的差异.如果全部n 在数组结束之前未观察到标签,函数返回空值.

现在,可以为数组中的每个元素运行片段长度函数,以关联包含从数组中每个元素开始的所有n个搜索词的片段大小.片段长度函数在整个索引数组上返回的最小非Null值是您要查找的文档中的片段.

必要的优化:

1. 跟踪当前最短片段长度的值,以便在通过索引数组迭代一次后立即知道该值.
2. 如果正在检查的当前片段超过之前看到的最短片段长度的长度,则在遍历数组时终止片段长度函数.
3. 当片段长度函数返回null以便不在其余索引数组元素中定位所有n个搜索词时,将空片段长度与索引数组中的所有连续元素相关联.
4. 如果片段长度函数应用于单词标签并且紧随其后的标签与起始标签相同,则为起始标签指定空值并转到下一个标签.

计算复杂性:

显然,算法的排序部分可以安排在O(n log n)中.

这是我如何计算算法第二部分的时间复杂度(任何批评和更正将非常感激).

在最佳情况下,算法仅将片段长度函数应用于索引数组中的第一个元素,并发现不存在包含所有搜索词的片段.这种情况将在n次计算中计算,其中n是索引数组的大小.稍微差一点的是,如果最小的片段等于整个数组的大小.在这种情况下,计算复杂度将略小于2 n(一次通过数组找到最小的片段长度,第二次证明没有其他片段存在).平均计算片段长度越短,需要在索引数组上应用片段长度函数的次数越多.我们可以假设我们更糟糕的情况是需要将片段长度函数应用于索引数组中的每个元素.为了开发将函数应用于索引数组中的每个元素的情况,我们需要设计一个索引数组,其中整个索引数组的平均片段长度与整个索引数组的大小相比可以忽略不计.使用这种情况,我们可以将我们的计算复杂度写出为O(C n),其中C是一个明显小于n的常数.给出最终的计算复杂度:

O(n log n + C n)

哪里:

C << n

编辑:

AndreyT正确地指出,而不是排序的字indicies ñ日志ñ时间,一个还不如合并他们(因为子阵列已经排序)ñ数米时间,其中米要合并搜索词阵列的数量.这显然会加速算法是m < n的情况.