Быстрый поиск, чтобы увидеть, существует ли строка в больших файлах с Delphi

Question

В моей программе есть подпрограмма FindFile, в которой будут перечислены файлы, но если заполнено поле «Содержащий текст», то в нем должны отображаться только файлы, содержащие этот текст.

Если введено поле «Содержащий текст», я ищу в каждом файле найденный текст. Мой текущий метод это:

  var
    FileContents: TStringlist;

  begin
    FileContents.LoadFromFile(Filepath);
    if Pos(TextToFind, FileContents.Text) = 0 then
      Found := false
    else 
      Found := true;

Приведенный выше код прост и обычно работает нормально. Но у него есть две проблемы:

1. Сбой для очень больших файлов (например, 300 МБ)

2. Я чувствую, что это может быть быстрее. Это неплохо, но зачем ждать 10 минут поиска по 1000 файлам, если есть простой способ немного ускорить его?

Мне нужно, чтобы это работало для Delphi 2009 и для поиска текстовых файлов, которые могут быть или не быть Unicode. Это нужно только для работы с текстовыми файлами.

Так как я могу ускорить этот поиск, а также заставить его работать с очень большими файлами?

---

Бонус: я также хотел бы разрешить опцию "игнорировать регистр". Это сложнее сделать эффективным. Есть идеи?

---

Решение:

Хорошо, mghie указал на мой предыдущий вопрос Как я могу эффективно прочитать первые несколько строк из многих файлов в Delphi , и, как я ответил, он был другим и не дал решения.

Но он заставил меня подумать, что я делал это раньше, и у меня было. Я создал процедуру чтения блоков для больших файлов, которая разбивает его на блоки по 32 МБ. Я использую это, чтобы прочитать входной файл моей программы, который может быть огромным. Рутина работает хорошо и быстро. Поэтому первый шаг - сделать то же самое для этих файлов, которые я просматриваю.

Итак, теперь вопрос заключался в том, как эффективно осуществлять поиск в этих блоках. Ну, у меня был предыдущий вопрос на эту тему: Существует ли эффективная функция поиска по всему слову в Delphi? , и RRUZ указал мне на процедуру SearchBuf.

Это также решает "бонус", потому что SearchBuf имеет опции, которые включают Поиск по всему слову (ответ на этот вопрос) и MatchCase / noMatchCase (ответ на бонус).

Так что я ухожу и бегу. Еще раз спасибо ТАК сообщество.

Answer 1

Лучшим подходом здесь, вероятно, является использование файлов с отображенной памятью.

Сначала вам понадобится дескриптор файла, для этого используйте функцию CreateFile windows API.

Затем передайте это CreateFileMapping, чтобы получить дескриптор сопоставления файлов. Наконец, используйте MapViewOfFile, чтобы отобразить файл в память.

Для обработки больших файлов MapViewOfFile может отображать в память только определенный диапазон, так что вы можете, например, сопоставьте первые 32 МБ, затем используйте UnmapViewOfFile, чтобы удалить его, затем MapViewOfFile для следующих 32 МБ и так далее. (РЕДАКТИРОВАТЬ: как было указано ниже, убедитесь, что блоки, которые вы отображаете таким образом, перекрываются кратным 4 КБ, и, по крайней мере, на длину текста, который вы ищете, чтобы вы не пропускали текст, который может быть разделен на границе блока)

Чтобы выполнить фактический поиск, как только (часть) файла отображается в памяти, вы можете сделать копию источника для StrPosLen из SysUtils.pas (к сожалению, он определен только в разделе реализации и не отображается в интерфейс). Оставьте одну копию как есть и сделайте другую, заменяя Wide на Ansi каждый раз. Кроме того, если вы хотите иметь возможность поиска в двоичных файлах, которые могут содержать встроенные #0 файлы, вы можете удалить часть (Str1[I] <> #0) and.

Либо найдите способ определить, является ли файл ANSI или Unicode, либо просто вызвать версию Ansi и Unicode для каждой сопоставленной части файла.

Как только вы закончили с каждым файлом, обязательно вызовите CloseHandle сначала для дескриптора сопоставления файлов, а затем для обработки файлов. (И не забудьте сначала позвонить UnmapViewOfFile).

РЕДАКТИРОВАТЬ:

Большое преимущество использования файлов с отображенной памятью вместо использования, например, TFileStream для чтения файла в память в блоках заключается в том, что байты останутся в памяти только один раз.

Обычно при доступе к файлам сначала Windows считывает байты в файловый кеш ОС. Затем копирует их оттуда в память приложения.

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

Бонусный ответ: вызывая StrLIComp вместо StrLComp, вы можете выполнять поиск без учета регистра.

Answer 2

Если вы ищете поиск по текстовой строке, поищите алгоритм поиска Бойера-Мура.Он использует отображенные в память файлы и действительно быстрый поисковик.Вокруг есть несколько модулей delphi, которые содержат реализации этого алгоритма.

Чтобы дать вам представление о скорости - я в настоящее время ищу файлы размером 10-20 МБ, и это занимает порядка миллисекунд.

О, просто прочитайте, что это может быть Unicode - не уверен, поддерживает ли он это - но определенно посмотрите на этот путь.

Answer 3

Могу ли я предложить компонент?Если да, я бы порекомендовал ATStreamSearch .Он обрабатывает ANSI и UNICODE (и даже EBCDIC, а также корейский и другие).

Или класс TUTBMSearch из JclUnicode (Jedi-jcl).Он был в основном написан Майком Лишке (VirtualTreeview).Он использует настроенный алгоритм Бойера-Мура, который обеспечивает скорость.Плохой момент в вашем случае, это то, что он полностью работает в Юникоде (широкие строки), поэтому перевод с String на Widestring может привести к штрафным санкциям.

Answer 4

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

Answer 5

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

Это называется «Полнотекстовый поиск».

Это будет медленнеев первый раз (текст должен быть проанализирован и индексы должны быть созданы), но любой будущий поиск будет немедленным: вкратце, он будет использовать только индексы и не будет читать весь текст снова.

У вас есть точныйанализатор, который вам нужен в Delphi Magazine Issue 78, февраль 2002 : «Алгоритмы Alfresco: задавайте тысячи раз» Джулиан Бакнолл обсуждает индексирование слов и поиск документов: если вы хотите узнать, как Google работает, его магия - это страницаобратиться к. "

Существует несколько реализаций FTS для Delphi:

• Рубикон
• Mutis
• ColiGet
• Google - ваш друг ..

Я хотел бы добавить, что большинство БД имеют встроенный движок FTS.SQLite3 даже имеет очень маленькую, но эффективную реализацию, с рейтингом страниц и тому подобным.Мы предоставляем прямой доступ из Delphi с классами ORM к этой системе полнотекстового поиска с именем FTS3 / FTS4.

Answer 6

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

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

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

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