子串算法建议

Question

我有一个大字符串(100k)的短字符串(不超过100个字符),我需要快速找到所有具有某个子字符串的人.

这将用作用户开始键入的搜索框,系统立即提供"建议"(将用户键入的文本作为子字符串的字符串).与StackOverflow中的"Tag"框类似的东西.

因为这将是互动的,它应该非常快.您为此推荐了什么算法或数据结构？

顺便说一下,我将使用Delphi 2007.

提前致谢.

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.

这是浏览器和文本编辑器所做的事情,并且每次加载页面时它们都不会真正构建巨型前缀表.

Answer 2

您可能想要使用的数据结构是Trie,特别是后缀trie.阅读本文,以获得有关它们如何工作以及如何为您的问题编写一个的详细解释.

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岁 - 按现行标准来说几乎不是速度恶魔),每次搜索大约需要3 10毫秒.这对于交互式用户来说足够快速 - 并且使用10倍的字符串,它仍然会很好.