Самый быстрый способ найти подстроки в текстовых файлах

Question

Какой самый быстрый способ найти строки в текстовых файлах? Сценарий: поиск определенного пути в текстовом файле с указанием порядка 50000 путей к файлам (каждый путь имеет свою собственную строку).

Answer 1

Вам нужно найти одну строку в файле, одну и ту же строку в нескольких файлах, несколько строк в одном файле?

В зависимости от сценария у вас есть несколько возможных ответов.

• построение структуры данных (например, набора, предложенного Алексом) полезно, если вам нужно найти несколько строк в одном файле

• с использованием алгоритма типа Бойера-Мура эффективен, если вам нужно искать одну строку

• использование механизма регулярных выражений, вероятно, будет предпочтительнее, если вам придется искать несколько строк.

Answer 2

Файл такого размера должен легко помещаться в памяти, и вы можете превратить его в std :: set (или, что еще лучше, в хэш-набор, если у вас есть библиотека с этим под рукой) с путями в качестве его элементов. Проверка точного пути будет очень быстрой.

Если вам также нужно искать подпути, единственно полезным может быть отсортированный std :: vector (если вы ищете только префиксы) - или если вы ищете полностью общие подстроки пути, тогда вам все равно придется сканировать весь вектор, но если вам не придется делать это миллион раз, даже это не будет слишком плохо.

Answer 3

Я не уверен, насколько вы хотели бы использовать поиск, но FSM - хорошие варианты для использования.

Вот обсуждение: Краткий пример преобразования регулярного выражения в конечный автомат?

Answer 4

Это поле для регулярных выражений; вы должны посмотреть в grep и awk.