Предложение алгоритма подстроки

Ответ 1

Я написал длинный рекламный ролик, выполнив кучу сложных вычислений и шуток xzibit (дерево в дереве, чтобы вы могли искать при поиске), но потом поняли, что это проще, чем я думал. Браузеры делают это все время, и они никогда не прекомпитуют большие таблицы каждый раз, когда вы загружаете страницу.

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

что это означает, что вы берете свои 100k строки и объединяете их в одну длинную строку. вы затем берете свою подстроку запроса и повторяете свою большую строку, ища свои матчи. но вы не прыгаете по персонажам (это означало бы, что вы смотрите 100 и 100 итераций). вы прыгаете по длине своей подстроки, поэтому чем дольше ваша подстрока получается, тем быстрее это происходит.

вот отличный пример: http://userweb.cs.utexas.edu/users/moore/best-ideas/string-searching/fstrpos-example.html

они ищут строку ПРИМЕР.

это то, что делают браузеры и текстовые редакторы, и они никогда не создают гигантские таблицы префикса каждый раз, когда вы загружаете страницу.

Ответ 2

Структура данных, которую вы, скорее всего, захотите использовать, - это Trie, в частности, суффикс trie. Прочтите эту статью для хорошего объяснения того, как они работают, и как написать один для вашей проблемы.

Ответ 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 раз больше строк, все равно будет хорошо.

Ответ 4

Мне не нравится не соглашаться с Майком и его сторонниками, но деревья суффиксов (структура данных, описанная в его ссылке) - это большая боль для реализации. И найти надежную реализацию в Pascal/Delphi может быть сложно.

Суффикс-массивы предлагают ту же функциональность, что и намного проще. Компромисс - это O(m * logn) сложность, где m - длина токена поиска, а n - размер набора данных (в данном случае - 100 кбайт).

В случае, если кто-то не знает, оба дерева суффикса и массивы суффиксов позволяют вам найти все вхождения подстроки s в длинном тексте t.

Проблема Fernando может быть сведена к этой, путем объединения начального набора строк в одну строку с использованием некоторого символа разделителя. Например, начальный набор равен ["text1", "text2", "some text"], тогда строка результата t будет "text1|text2|some text".
Теперь вместо поиска строки "text" в каждом слове отдельно, нам просто нужно найти все его вхождения в большой строке t.

Я также рекомендую ответить Oren, где он предлагает другой реалистичный подход.

Ответ 5

Эта реализация в Delphi Boyer-Moore-Horspool может дать вам то, что вам нужно.
Отказ от ответственности: я не пробовал этот код...

Ответ 6

Что вы, вероятно, ищете, это n-gram. Он использовал для поиска наиболее вероятных слов, связанных с вашей подстрокой. Очень интересный материал, и хотя он может быть излишним для того, что вы ищете, это все еще полезно знать.