子字符串算法建议

Question

我有一个包含大量短字符串（不超过100个字符）的数据集（100k），我需要快速查找其中包含某个子字符串的所有字符串。

这将用作搜索框，用户开始输入文本后，系统会立即提供“建议”（即包含用户键入的文本作为子字符串的字符串）。类似于StackOverflow中的“标签”框。

由于这将是交互式的，所以速度应该相当快。你推荐使用什么算法或数据结构来完成这项任务？

顺便说一下，我将使用Delphi 2007。

谢谢！

- cfischer

---

感谢所有回复的人。我查看了Mike建议的后缀树。然而，考虑到我的时间限制和缺乏现有实现，我将首先采用Oren建议的更简单的方法：Boyer-moore算法。 - cfischer

我刚刚尝试了Boyer-Moore-Horspool算法（感谢Oren和François），速度比我预期的要快得多。对于我的目的来说，已经足够了。 - cfischer

Answer 1

我写了一个长篇介绍，进行了大量的复杂度计算和Xzibit笑话（树中的树，因此您可以在查找时查找），但后来意识到这比我想象的要容易。浏览器经常这样做，而且每次加载页面时都不会预先计算大表。

http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

它的意思是将你的100k字符串合并成一个长字符串。然后取出你的查询子串，并迭代你的大字符串，寻找匹配项。但你不是按字符跳转（这意味着你要查看100k*100次），而是按子串长度跳转，所以你的子串越长，速度越快。

下面是一个很好的例子：http://userweb.cs.utexas.edu/users/moore/best-ideas/string-searching/fstrpos-example.html

他们正在搜索字符串EXAMPLE。

这就是浏览器和文本编辑器所做的事情，它们实际上并不会为每个加载的页面构建巨大的前缀表。

- Oren Mazor

---

我一直在想，学习和理解后缀树的痛苦是否值得，因为它们似乎被提及为解决所有字符串问题的万能工具。 - Rohan Monga

@bronzebeard 完全同意你的观点，对 Oren 提供现实解决方案表示赞同。 - Nikita Rybak

后缀树非常强大，但不易理解和构建。当你有大量数据时，它们会发挥作用。对于简单的建议，它们可能过于复杂。+1 给 Oren。 - Runner

Boyer-Moore 是首选。我编写了一个 Boyer-Moore 算法，用于查找音频库中数千个短字符串（基本上是所有的 ID3 标签以及一些额外的数据）。它非常快，你可以实时输入并显示更新结果。 - Gregor Brandt

你有没有任何证据来支持你的说法，即浏览器中没有进行任何预处理？这让我感到相当惊讶。另一方面，这可以解释为什么“超级地址栏”如此糟糕...。只是为了明确：虽然这种方法可以，但使用 trie 对于 OP 处理的数据量更加高效。而且，实现 trie 并不难。 - Konrad Rudolph

Answer 2

你可能想要使用的数据结构是Trie，特别是后缀Trie。阅读这篇文章，了解它们是如何工作的以及如何为您的问题编写一个。

- Mike Axiak

---

赶我一步。如果文章没有明确说明，你可以为整个语料库构建一个后缀树，并注释说明该后缀属于哪个字符串。 - Steve Jessop

一个好的建议，但可能对他想要的东西来说有些过度。+1 建议使用不多人知道的数据结构。 - Runner

@Runner 不是很多人知道吗？“Trie”就像新的JQuery :) 现在很难找到没有“用户尝试”答案的算法问题。 - Nikita Rybak

@Rybak - 这一定是我错过了。有趣，我以为这不是很出名。一年半前我实现了一个，当时我确实没有找到太多关于它们的信息。必须再去看看 :) - Runner

Answer 3

虽然使用更好的数据结构可以加快速度，但在某些情况下暴力搜索可能已经足够。我们来做一个快速测试：

[编辑：修改代码以搜索子字符串，并再次编辑以缩短要搜索的子字符串与要搜索的字符串之间的比较长度。]

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <time.h>

std::string rand_string(int min=20, int max=100) { 
    size_t length = rand()% (max-min) + min;
    std::string ret;

    for (size_t i=0; i<length; i++)
        ret.push_back(rand() % ('z' - 'a') + 'a');
    return ret; 
}

class substr {
    std::string seek;
public:
    substr(std::string x) : seek(x) {}

    bool operator()(std::string const &y) { return y.find(seek) != std::string::npos; }
};

int main() { 
    std::vector<std::string> values;

    for (int i=0; i<100000; i++)
        values.push_back(rand_string());

    std::string seek = rand_string(5, 10);

    const int reps = 10;

    clock_t start = clock();
    std::vector<std::string>::iterator pos;
    for (int i=0; i<reps; i++)
         pos = std::find_if(values.begin(), values.end(), substr(seek));
    clock_t stop = clock();

    std::cout << "Search took: " << double(stop-start)/CLOCKS_PER_SEC/reps << " seconds\n";
    if (pos == values.end())
        std::cout << "Value wasn't found\n";
    else
        std::cout << "Value was found\n";
    return 0;
}

在我的机器上（约4年前的机器——按现有标准几乎不算快），每次搜索运行大约10毫秒左右。这足够快，对于交互用户来说几乎是瞬间出现的——即使有10倍的字符串，也仍然很好。

- Jerry Coffin

---

我不精通STL，但如果我没记错的话，std::find 在容器中搜索元素的确切出现。而Fernando对子字符串感兴趣。 - Nikita Rybak

@Nikita：非常正确。这并没有太大的区别，但我已经编辑了代码来测试正确的事情。即使如此，我们仍然在谈论单位毫秒的搜索时间。虽然我用C++编写了测试代码，但我预计Delphi的结果会差不多。速度可能会有几个百分点的差异，但我们必须看到10倍的差异才能接近显著，而我会非常惊讶看到那种情况。 - Jerry Coffin

在复杂化问题之前，应该先尝试暴力解决方案。+1 - GrandmasterB

即使字符串的数量和大小相当大，我认为使用多个线程可能会更快。 - luiscubal

@Jerry，你的时间估计不准确，因为“seek”字符串的平均长度与“values”字符串相同。尝试搜索类似“abcde”的内容（更真实的用户输入示例）。虽然结果仍然相当不错（对于我来说，在随机输入上大约需要20毫秒），虽然不是0.1毫秒，但通常也足够好了。 - Nikita Rybak

顺便说一句，你可以在你的帖子中更新时间估计（3毫秒是在“substr”之前的，会让人困惑）。 - Nikita Rybak

Answer 4

我不愿意反驳Mike和他的支持者，但后缀树（在他提供的链接中描述的数据结构）实现起来很麻烦。而且在Pascal/Delphi中找到可靠的实现也许很困难。 后缀数组提供相同的功能，同时更加简单。权衡之下，其复杂度为O(m * logn)，其中m是搜索词的长度，n是数据集的大小（在这种情况下为100kb）。

如果有人不知道，后缀树和后缀数组都允许您在长文本t中查找所有子字符串s的出现。 Fernando的问题可以通过将初始字符串集合使用某个分隔符连接成一个字符串来简化。例如，如果初始集合是["text1", "text2", "some text"]，则结果字符串t将为"text1|text2|some text"。
现在，我们不再需要在每个单词中分别搜索字符串"text"，而只需在大字符串t中查找所有出现次数即可。

我还建议参考Oren的答案，他提出了另一种现实可行的方法。

- Nikita Rybak

---

一棵Trie树和一个后缀数组有很大的区别。虽然后缀数组可以建立在字符串集上，但是Trie树更自然、更高效——搜索时间复杂度为O(m)，而不是O(log n + m)，对于长度为100的10万个字符串，这可能会产生巨大的差异。最后，高效地构建Trie树比构建后缀数组要容易得多——即使是暴力快速排序方法在实践中也能获得可接受的性能。但除此之外，后缀数组也是不错的选择！ - Konrad Rudolph

Answer 5

这个Delphi实现的Boyer-Moore-Horspool算法可能会给你所需的东西。
免责声明：我没有尝试过这段代码...

- Francesca

Answer 6

你可能正在寻找的是n-gram。它用于查找与您子字符串相关的最有可能的单词。非常有趣的东西，虽然它可能对您所寻找的功能过于复杂，但还是值得了解的。

- ReaperUnreal