javascript - 如何从关键字搜索中返回最短的片段？

Question

我有以下任务要解决:

Given a page of content with alphanumeric words, and a search phrase of N words, write an algorithm that will return the shortest snippet of content that contains all N words in any order.

这就是我目前所拥有的。我把页面上的文字放到一个没有标点符号的数组中:

var allText = $('#all-text').text();
var punctuationless = allText.replace(/[^A-Za-z0-9_]/g," ").toLowerCase();
var lessSpaces = punctuationless.replace(/\s{2,}/g," ");
var allTextArray = lessSpaces.split(" ");
var keywords = [];

我想我或许可以使用 .filter 方法，但我不确定如何比较两个数组。

allTextArray.filter(keywords)
//find the indexes of the matches to the keywords
//compare how far apart the indexes are to each other and return the shortest length

Answer 1

因此，根据我对 OP 的理解列出一些示例，如果页面文本是:

One for the money,
two for the show.

• 搜索词 “One”、“money” 应该生成 “One for the money”。
• 搜索词 "One","two","for" 应该生成 "One for the money, two"

• 搜索词 "for","show" 应该生成 "for the show"

  • ... 但不是 为了钱，两个为了表演

我添加最后一点是因为这就是这样一个函数变得非常复杂的地方，因为它现在必须找到所有组合中尺寸最小的搜索词组合。

我解决了 a jsfiddle solution 对此，但我不会声称这是最有效的答案(因为已经很晚了，我的部分思想可能已经休眠)。

基本上，这是一个迭代和提前扫描的解决方案，这可能是人们用眼球做的方式:

1. 传递搜索文本并构建每个关键字及其索引的每次出现的数组。
2. 确保数组的顺序基于关键字在文本中出现的顺序。
3. 从(几乎)有序数组中的每个条目开始，向右扫描，直到找到每个关键字至少出现一次——此时我们看看它是否是我们迄今为止获得的最小片段。<

总而言之，检查所有可能的片段，包括所有关键字。

重要的是要注意，我创建的解决方案不区分大小写，它匹配单词的一部分，而不是整个单词，并且 OP 暗示不区分大小写和整个单词匹配。

不区分大小写(将所有输入文本转换为小写)和全词匹配(去除标点符号和多余空格的文本，然后拆分为数组)的策略应该很容易适用于该解决方案，特别是因为 indexOf 对字符串和数组的作用相同。

getSnippet = function(keywords, fullText) {
  var keywordCount = keywords.length,
      keywordIndexes = [];

  // Find each occurrence of every word
  for(var i=0; i < keywordCount; i++) {
    var searchPos = 0;
    var word = keywords[i];
    var index = -1;
    do {
      index = fullText.indexOf(keywords[i],searchPos);
      if (index >= 0) {
        keywordIndexes.push({i:index, word:word});
      }
      searchPos = index + 1;
    } while (index >= 0);
  }

  keywordIndexes.sort(function(a, b) { return a.i == b.i ? 0 : a.i < b.i ? -1 : 1; });

  // Find the shortest run by starting at each array index and scanning to the
  // right until we have encountered each word in the list.
  for (i=0, n=keywordIndexes.length-keywordCount; i<=n; i++) {
    // NOTE: We actually can actually stop once there are fewer keyword
    // indexes than keywords, since we know we won't find all the keywords (hence the subtraction of keywordCount)
    var foundWords = {},
        foundCount = 0;
    snippetStart = keywordIndexes[i].i;

    for (j=i; j < keywordIndexes.length; j++) {
      var word = keywordIndexes[j].word;
      if (!foundWords[word]) {
        foundWords[word] = true;
        foundCount++;
      }
      if (foundCount == keywordCount) {
        // We've found all the words
        snippetEnd = keywordIndexes[j].i + word.length;
        if (minSnippet.end - minSnippet.start > snippetEnd - snippetStart) {
          minSnippet.end = snippetEnd;
          minSnippet.start = snippetStart;
        }
        break;
      }
    }
  }
  return fullText.substring(minSnippet.start, minSnippet.end);
}

参见 jsfiddle 了解更多信息。