搜索词间最短长度的算法

Question

我正在尝试提出一种算法来查找单词列表之间的最短距离。我有一个列表字典，它显示在文档中找到一个词的不同位置。

匹配{“the”:[2, 24, 15]，“is”:[5, 13]，“apple”:{45} ... }

是否有确定的算法来找到所有这些重叠的最短长度？例如，在这一个中，13-45 将是答案，因为所有的单词都可以在该范围内找到。

Answer 1

我会保留两个位置，left 和 right，它们分别是包含所有单词的范围的左端和右端。我还会维护一个优先级队列，其中的每个条目都是一个单词，以及该单词出现在当前左边缘或之后的位置列表。

要初始化，创建一个新的空优先级队列，插入每个单词及其出现的完整列表，并正确排序。当您插入每个单词时，更新 right 使其成为任何单词的最大首次出现次数。对于您的数据，初始设置为

left=2,right=45,queue=[["the", [2,15,24]], ["is", [5, 13], ["apple", [45]]

我将优先级队列显示为一个数组，按其第二个组件的第一个组件排序。也就是说，顺序为 2(代表“the”)、5(代表“is”)和 45(代表“apple”)。请注意，“the”的出现必须在此初始化期间进行排序。 right结果是45，2、5、45中的最大值。

left 是隐含的。它始终是优先级队列前面的任何内容的第一次出现。此时我们发现的最短距离是 2..45。

然后重复下面的循环:

remove the first entry from the priority queue
shift its next occurrence into `left`
check if left..right is a new shortest sequence
if we've shifted off the last occurrence for this entry
    stop
otherwise, 
    update `right` to include this new next occurrence
    insert the entry back into the priority queue

对于您的数据，连续的值将是:

left=2,right=45,queue=[["the", [2,15,24]], ["is", [5, 13], ["apple", [45]]
left=5,right=45,queue=[["is", [5, 13], ["the", [15,24]], ["apple", [45]]
left=13,right=45,queue=[["is", [13], ["the", [15,24]], ["apple", [45]]

然后我们终止，因为在从队列中弹出 ["is", [13]] 并将 13 从其出现列表中移出后，没有留下。