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

Question

У меня есть большой набор (100 КБ) коротких строк (не более 100 символов), и мне нужно быстро найти всех, у кого есть определенная подстрока.пользователь начинает печатать, и система немедленно дает «предложения» (строки, которые имеют в качестве подстроки текст, набранный пользователем).Что-то похожее на поле «Tag» в StackOverflow.

Поскольку это будет интерактивно, оно должно быть довольно быстрым.Какой алгоритм или структуру данных вы порекомендуете для этого?

Кстати, я буду использовать Delphi 2007.

Заранее спасибо.

Answer 1

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

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

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

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

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-кратным числом строк это все равно будет хорошо.

Answer 4

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

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

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

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

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

Answer 5

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

Answer 6

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