从搜索文档中查找最小片段的算法？
问题描述 投票：14回答：7
我一直在阅读Skiena出色的“算法设计手册”，并在其中一个练习中被挂了。
问题是：“给定三个单词的搜索字符串，找到包含所有三个搜索词的文档的最小片段 - 即，其中包含最少数量单词的片段。您将获得这些单词的索引位置在出现的搜索字符串中，例如word1：（1,4,5），word2：（4,9,10）和word3：（5,6,15）。每个列表按排序顺序排列，如上所述。 “
我想出的任何东西都是O（n ^ 2）......这个问题出现在“排序和搜索”一章中，所以我假设有一种简单而聪明的方法。我现在正在尝试使用图表，但这似乎有些过分。
想法？谢谢
7个回答
投票
我已经发布了一个相当简单的算法，可以在这个答案中解决这个问题
Google search results: How to find the minimum window that contains all the search keywords?
但是，在该问题中，我们假设输入由文本流表示，并且单词存储在易于搜索的集合中。
在您的情况下，输入的表示略有不同：作为一组向量，每个单词的排序位置。通过简单地将所有这些矢量合并到由位置排序的(position, word)对的单个矢量中，该表示可以容易地变换为上述算法所需的内容。它可以按字面意思完成，或者可以通过将原始向量放入优先级队列（按照其第一个元素排序）来“虚拟地”完成。在这种情况下从队列弹出元素意味着从队列中的第一个向量弹出第一个元素，并可能根据其新的第一个元素将第一个向量下沉到队列中。
当然，由于您的问题陈述明确地将单词数量固定为三，您可以简单地检查所有三个数组的第一个元素，并在每次迭代时弹出最小的一个。这给你一个O(N)算法，其中N是所有数组的总长度。
此外，您对问题的陈述似乎表明目标词可能在文本中重叠，这很奇怪（假设您使用术语“词”）。这是故意的吗？在任何情况下，它都不会对上述链接算法产生任何问题。
投票
除非我忽略了一些东西，否则这是一个简单的O（n）算法：
- 我们将用（x，y）代表片段，其中x和y分别是片段开始和结束的位置。
- 如果它包含所有3个搜索词，则片段是可行的。
- 我们将从不可行的片段（0,0）开始。
- 重复以下操作，直到y到达字符串结尾： 如果当前片段（x，y）可行，请转到片段（x + 1，y） 否则（当前片段不可行）进入片段（x，y + 1）
- 选择我们经历过的所有可行片段中最短的片段。
运行时间 - 在每次迭代中，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）。
投票
从这个问题来看，似乎你在文档中给出了每个n个“搜索词”（word1，word2，word3，...，word n）的索引位置。使用排序算法，与搜索词相关联的n个独立阵列可以容易地以递增的数字顺序表示为所有索引位置的单个阵列，并且与阵列中的每个索引（索引阵列）相关联的词标签。
基本算法：
（无论该问题的海报是否意图允许两个不同的搜索词在同一索引号上共存，设计工作。）
首先，我们定义一个简单的函数来测量一个片段的长度，该片段包含索引数组中给定起点的所有n个标签。 （从数组的定义可以明显看出，数组上的任何起点都必然是n个搜索标签之一的索引位置。）该函数只是跟踪函数迭代元素时看到的唯一搜索标签。在数组中，直到观察到所有n个标签。片段的长度定义为找到的最后一个唯一标签的索引与索引数组中起始点的索引（找到的第一个唯一标签）之间的差异。如果在数组结束之前未观察到所有n个标签，则该函数返回空值。
现在，可以为数组中的每个元素运行片段长度函数，以关联包含从数组中每个元素开始的所有n个搜索词的片段大小。片段长度函数在整个索引数组上返回的最小非Null值是您要查找的文档中的片段。
必要的优化：
- 跟踪当前最短片段长度的值，以便在通过索引数组迭代一次后立即知道该值。
- 如果正在检查的当前片段超过之前看到的最短片段长度的长度，则在遍历数组时终止片段长度函数。
- 当片段长度函数返回null以便不在其余索引数组元素中定位所有n个搜索词时，将空片段长度与索引数组中的所有连续元素相关联。
- 如果片段长度函数应用于单词标签并且紧随其后的标签与起始标签相同，则为起始标签指定空值并转到下一个标签。
计算复杂性：
显然，算法的排序部分可以安排在O（n log n）中。
这是我如何计算算法第二部分的时间复杂度（任何批评和更正将非常感激）。
在最佳情况下，算法仅将片段长度函数应用于索引数组中的第一个元素，并发现不存在包含所有搜索词的片段。这种情况将在n次计算中计算，其中n是索引数组的大小。稍微差一点的是，如果最小的片段等于整个数组的大小。在这种情况下，计算复杂度将略小于2 n（一次通过数组以找到最小的片段长度，第二次证明不存在其他片段）。平均计算片段长度越短，需要在索引数组上应用片段长度函数的次数越多。我们可以假设我们更糟糕的情况是需要将片段长度函数应用于索引数组中的每个元素。为了开发将函数应用于索引数组中的每个元素的情况，我们需要设计一个索引数组，其中整个索引数组的平均片段长度与整个索引数组的大小相比可以忽略不计。使用这种情况，我们可以将我们的计算复杂度写为O（C n），其中C是一个明显小于n的常数。给出最终的计算复杂度：
O（n log n + C n）
哪里：
C << n
编辑：
AndreyT正确地指出，不是在n log n时间内对单词indicies进行排序，而是可以在n log m时间内合并它们（因为子数组已经被排序），其中m是要合并的搜索字数组的数量。这显然会加速算法是m <n的情况。
投票
O（n log k）解，其中n是索引的总数，k是单词的数量。我们的想法是使用堆来识别每次迭代中的最小索引，同时还跟踪堆中的最大索引。我还将每个值的坐标放在堆中，以便能够在恒定时间内检索下一个值。
#include <algorithm>
#include <cassert>
#include <limits>
#include <queue>
#include <vector>
using namespace std;
int snippet(const vector< vector<int> >& index) {
// (-index[i][j], (i, j))
priority_queue< pair< int, pair<size_t, size_t> > > queue;
int nmax = numeric_limits<int>::min();
for (size_t i = 0; i < index.size(); ++i) {
if (!index[i].empty()) {
int cur = index[i][0];
nmax = max(nmax, cur);
queue.push(make_pair(-cur, make_pair(i, 0)));
}
}
int result = numeric_limits<int>::max();
while (queue.size() == index.size()) {
int nmin = -queue.top().first;
size_t i = queue.top().second.first;
size_t j = queue.top().second.second;
queue.pop();
result = min(result, nmax - nmin + 1);
j++;
if (j < index[i].size()) {
int next = index[i][j];
nmax = max(nmax, next);
queue.push(make_pair(-next, make_pair(i, j)));
}
}
return result;
}
int main() {
int data[][3] = {{1, 4, 5}, {4, 9, 10}, {5, 6, 15}};
vector<vector<int> > index;
for (int i = 0; i < 3; i++) {
index.push_back(vector<int>(data[i], data[i] + 3));
}
assert(snippet(index) == 2);
}
投票
java中的示例实现（仅使用示例中的实现进行测试，可能存在错误）。实施基于上述答复。
import java.util.Arrays;
public class SmallestSnippet {
WordIndex[] words; //merged array of word occurences
public enum Word {W1, W2, W3};
public SmallestSnippet(Integer[] word1, Integer[] word2, Integer[] word3) {
this.words = new WordIndex[word1.length + word2.length + word3.length];
merge(word1, word2, word3);
System.out.println(Arrays.toString(words));
}
private void merge(Integer[] word1, Integer[] word2, Integer[] word3) {
int i1 = 0;
int i2 = 0;
int i3 = 0;
int wordIdx = 0;
while(i1 < word1.length || i2 < word2.length || i3 < word3.length) {
WordIndex wordIndex = null;
Word word = getMin(word1, i1, word2, i2, word3, i3);
if (word == Word.W1) {
wordIndex = new WordIndex(word, word1[i1++]);
}
else if (word == Word.W2) {
wordIndex = new WordIndex(word, word2[i2++]);
}
else {
wordIndex = new WordIndex(word, word3[i3++]);
}
words[wordIdx++] = wordIndex;
}
}
//determine which word has the smallest index
private Word getMin(Integer[] word1, int i1, Integer[] word2, int i2, Integer[] word3,
int i3) {
Word toReturn = Word.W1;
if (i1 == word1.length || (i2 < word2.length && word2[i2] < word1[i1])) {
toReturn = Word.W2;
}
if (toReturn == Word.W1 && i3 < word3.length && word3[i3] < word1[i1])
{
toReturn = Word.W3;
}
else if (toReturn == Word.W2){
if (i2 == word2.length || (i3 < word3.length && word3[i3] < word2[i2])) {
toReturn = Word.W3;
}
}
return toReturn;
}
private Snippet calculate() {
int start = 0;
int end = 0;
int max = words.length;
Snippet minimum = new Snippet(words[0].getIndex(), words[max-1].getIndex());
while (start < max)
{
end = start;
boolean foundAll = false;
boolean found[] = new boolean[Word.values().length];
while (end < max && !foundAll) {
found[words[end].getWord().ordinal()] = true;
boolean complete = true;
for (int i=0 ; i < found.length && complete; i++) {
complete = found[i];
}
if (complete)
{
foundAll = true;
}
else {
if (words[end].getIndex()-words[start].getIndex() == minimum.getLength())
{
// we won't find a minimum no need to search further
break;
}
end++;
}
}
if (foundAll && words[end].getIndex()-words[start].getIndex() < minimum.getLength()) {
minimum.setEnd(words[end].getIndex());
minimum.setStart(words[start].getIndex());
}
start++;
}
return minimum;
}
/**
* @param args
*/
public static void main(String[] args) {
Integer[] word1 = {1,4,5};
Integer[] word2 = {3,9,10};
Integer[] word3 = {2,6,15};
SmallestSnippet smallestSnippet = new SmallestSnippet(word1, word2, word3);
Snippet snippet = smallestSnippet.calculate();
System.out.println(snippet);
}
}
助手班：
public class Snippet {
private int start;
private int end;
//getters, setters etc
public int getLength()
{
return Math.abs(end - start);
}
}
public class WordIndex
{
private SmallestSnippet.Word word;
private int index;
public WordIndex(SmallestSnippet.Word word, int index) {
this.word = word;
this.index = index;
}
}
投票
联系（I）
Pair find(int[][] indices) {
pair.lBound = max int;
pair.rBound = 0;
index = 0;
for i from 0 to indices.lenght{
if(pair.lBound > indices[i][0]){
pair.lBound = indices[i][0]
index = i;
}
if(indices[index].lenght > 0)
pair.rBound = max(pair.rBound, indices[i][0])
}
remove indices[index][0]
return min(pair, find(indices)}
投票
其他的答案都没问题，但是和我一样，如果你在第一时间理解这个问题时遇到了麻烦，那些问题就没那么有用了。让我们重新解释一下这个问题：
给定三组整数（称为A，B和C），找到包含每个集合中一个元素的最小连续范围。
关于三组是什么有一些混淆。该书的第2版将它们称为{1, 4, 5}，{4, 9, 10}和{5, 6, 15}。但是，上面评论中陈述的另一个版本是{1, 4, 5}，{3, 9, 10}和{2, 6, 15}。如果一个单词不是另一个单词的后缀/前缀，那么版本1是不可能的，所以让我们继续使用第二个单词。
由于图片胜过千言万语，让我们绘制点数：
简单地从视觉上检查上面的内容，我们可以看到这个问题有两个答案：[1,3]和[2,4]，两者都是3号（每个范围内有3个点）。
现在，算法。我们的想法是从最小的有效范围开始，并逐步尝试通过向左移动左边界来缩小它。我们将使用从零开始的索引。
MIN-RANGE(A, B, C)
i = j = k = 0
minSize = +∞
while i, j, k is a valid index of the respective arrays, do
ans = (A[i], B[j], C[k])
size = max(ans) - min(ans) + 1
minSize = min(size, minSize)
x = argmin(ans)
increment x by 1
done
return minSize
其中argmin是ans中最小元素的索引。
+---+---+---+---+--------------------+---------+
| n | i | j | k | (A[i], B[j], C[k]) | minSize |
+---+---+---+---+--------------------+---------+
| 1 | 0 | 0 | 0 | (1, 3, 2) | 3 |
+---+---+---+---+--------------------+---------+
| 2 | 1 | 0 | 0 | (4, 3, 2) | 3 |
+---+---+---+---+--------------------+---------+
| 3 | 1 | 0 | 1 | (4, 3, 6) | 4 |
+---+---+---+---+--------------------+---------+
| 4 | 1 | 1 | 1 | (4, 9, 6) | 6 |
+---+---+---+---+--------------------+---------+
| 5 | 2 | 1 | 1 | (5, 9, 6) | 5 |
+---+---+---+---+--------------------+---------+
| 6 | 3 | 1 | 1 | | |
+---+---+---+---+--------------------+---------+
n =迭代
在每个步骤中，三个索引中的一个递增，因此保证算法最终终止。在最坏的情况下，i，j和k按此顺序递增，并且算法在O(n^2)（在这种情况下为9）时间运行。对于给定的示例，它在5次迭代后终止。
最新问题
- 使用域映射 API 映射域和自动配置 SSL 证书时，Gcloud App Engine“500 内部服务器错误”
- ActionScript 3.0编译器宏创建当前AS文件和代码行的字符串？
- @Observable 宏：不使用 @ObservationIgnored 标记属性会导致任何问题吗？
- 找到距交线给定垂直距离的两条线的交点
- 编译器差异
- django：在 pypy、psyco、unladensweat 或 cpython 上，哪一个最快？ [已关闭]
- 我收到此警告：com.sun.org.apache.xml.internal.serialize.OutputFormat 是 Sun 专有 API，可能会在未来版本中删除
- 如何将列表转换为多列和数据框？
- 如何获取包含shadowRoot元素的文档或节点中的所有HTML
- 在 Chrome 中使用 Selenium 和 Python 下载 PDF：禁用 PDF 查看器
- Perlbrew 无法安装新的 perl 版本
- 如何在64位应用程序中使用32位指针？
- 如何在AnimatedVisibility中设置弹簧类型animationSpec的持续时间？
- 更新 GLMeshItem 的颜色
- Unicode 特殊字符 U+FFFD 从我的 Nest.JS API 返回，但只是有时
- 通过 .NET 核心代码将敏感度标签应用到 Microsoft Exchange Mail
- 我的字符串不会在循环中重新声明
- SQL Server 2019 Express Setup.exe 未安装 MSSQL Server 实例
- 循环中使用前三个唯一 ID 填充数组
- Web Essentials Less 导入文件保存不会编译主文件