Какова самая быстрая структура или структура строк для запуска и/или содержит поисковые запросы

Question

У меня есть следующая ситуация: У меня есть большая коллекция строк (скажем, 250.000+) средней длины, возможно, 30. Что мне нужно сделайте много попыток в пределах этих .. в основном это будут StartsWith и Содержит вид.

Коллекция является статической во время выполнения. Это означает, что первоначальное чтение и заполнение коллекции выбора выполняется только один раз. Поэтому выполнение построения структуры данных абсолютно не важно. Память также не является проблемой: это также означает, что я не против иметь две коллекции с одинаковыми данными в каждом случае, если это необходимо (например, один для startswith и другой для содержит). Единственное, что имеет значение, это выполнение поисков, которые должны возвращать все элементы, которые соответствуют условию поиска.

Для начала я столкнулся с деревом Trie или Radix .. но, возможно, есть еще лучшие варианты?

Для содержит. У меня пока нет хорошей идеи (помимо запуска запроса linq в списке, который не будет очень быстрым с этим объемом данных).

Заранее благодарен всем!

обновления: Я забыл важную роль: с Содержит я не имею в виду никаких точных совпадений в коллекции .. но я хочу, чтобы найти все строки в коллекции, которые содержат данное SearchString

Answer 1

, строящее suffix tree позволит вам выполните поиск подстроки по всем вашим строкам параллельно в O(1). Педантичный во мне не может не заметить, что это действительно O(n + m) где n - это количество строк, соответствующих вашей подстроке, и m - размер запрашиваемой подстроки.

Итак, что вы спрашиваете? В своей самой базовой реализации это trie с помощью метода вставки fancier: помимо добавления строки, он также добавляет все возможные суффиксы этой строки в trie. В этой структуре данных поиск подстрок становится префиксом поиска всех возможных суффиксов. Поскольку вы также хотите выполнять поиск в префиксах, вам нужно добавить специальный символ перед каждой вставленной строкой и подстроками запроса. Специальный символ позволит вам различать суффикс и полную строку.

Хотя эта реализация дерева суффикса замечательно проста, она также очень неэффективна (O(n^2) пространство и время сборки). К счастью, существуют и другие более эффективные реализации, которые могут значительно сократить пространство и временные рамки. Один из них, алгоритм Укконена, очень хорошо объяснен в this SO answer и сместил пространство до O(n). Вы также можете посмотреть в suffix arrays, которые являются эквивалентным, но более эффективным представлением суффиксов.

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