Более быстрый способ поиска строки в текстовых файлах

Ответ 1

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

При использовании поисковой системы: похоже, что вы ищете подстроки, а это значит, что вы должны индексировать свои файлы как таковые, используя свою любимую поисковую систему, предпочтительно такую, которую вы можете настроить (lucene, terrier и т.д.). Техника, в которой вы нуждаетесь, - это индексирование триграмм, то есть: все 3-значные комбинации должны быть проиндексированы. F.ex.: "foobar" будет генерировать "foo", "oob", "oba" и "bar". При поиске вы хотите сделать то же самое с вашим запросом и выдать запрос поисковой системы с И всех этих триграмм. (Это запустит объединение слияния в списках проводки из документов, которое вернет их идентификатор или все, что вы разместите в списках проводки).

В качестве альтернативы вы можете реализовать массивы суффиксов и индексировать свои файлы один раз. Это даст немного большую гибкость, если вы захотите найти короткие (1-2 char) подстроки, но с точки зрения индексов сложнее поддерживать. (Есть несколько исследований в CWI/Amsterdam для быстрого индексирования суффикса)

Если вы хотите искать только несколько раз, алгоритм для использования - либо Бойер-Мур (я обычно использую Бойер-Мур-воскресенье, как описано в [Graham A. Stephen, String Search]) или скомпилированный DFA (вы может построить их из NFA, что легче сделать). Тем не менее, это только даст вам небольшое увеличение скорости по той простой причине, что диск IO, вероятно, является вашим узким местом и сравнивает кучу байтов, которые нужно декодировать в любом случае, довольно быстро.

Самое большое улучшение, которое вы можете сделать, это не чтение вашего файла по строкам, а в блоках. Вы должны настроить NTFS на использование размера блока в 64 КБ, если сможете, и читать файлы в размножении 64 КБ - считайте 4 МБ или более в одном чтении. Я бы даже предложил использовать асинхронный ввод-вывод, чтобы вы могли одновременно читать и обрабатывать (ранее прочитанные данные). Если вы сделаете это правильно, это уже должно дать вам двухсекундную реализацию на 10 МБ на большинстве современных аппаратных средств.

И последнее, но не менее важное: аккуратный трюк, используемый во время поиска информации, также позволяет сжать ваши данные с использованием алгоритма быстрого сжатия. Поскольку диск IO медленнее операций с памятью/процессором, это, вероятно, также поможет. Компилятор Google Snappy - хороший пример быстрого алгоритма сжатия.

Ответ 2

Вам следует рассмотреть возможность использования поиска в операционной системе с содержимым. Взгляните на Microsoft Windows Search 3.x SDK

Или вы можете использовать PLINQ для поиска в массиве файлов. См. Эту ссылку:

Содержимое файла и поиск по каталогу с использованием Directory.GetFiles и PLINQ

Ответ 3

Приходят на ум два варианта:

Чтение текстового файла в памяти и просто поиск всей строки сразу.

Если это окажется слишком медленным или слишком голодным, используйте индексатор типа Apache Lucene. Существует хороший и простой SDK для того, что доступно для .NET, Lucene.net

Вот небольшое введение для него: http://www.codeproject.com/Articles/29755/Introducing-Lucene-Net

Ответ 4

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

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

Ответ 5

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