Как быстро найти строки в большом файле (800 Мб) в Lazarus и определить их позиции

Delphi , Синтаксис , Текст и Строки

При работе с большими файлами (например, 800 Мб и более) в Lazarus или Delphi, эффективный поиск строк становится критически важной задачей. В этой статье мы рассмотрим несколько подходов к решению этой проблемы, сравним их производительность и предложим оптимальные решения.

Проблема поиска в больших файлах

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

1. Чтение файла блоками

procedure SearchInChunks(const FileName: string; const SearchStr: string);
var
  F: File;
  Buffer1, Buffer2: array[0..1023] of Byte;
  BytesRead, TotalRead: Integer;
  i, j: Integer;
  Found: Boolean;
begin
  AssignFile(F, FileName);
  Reset(F, 1);
  try
    TotalRead := 0;
    BlockRead(F, Buffer1, SizeOf(Buffer1), BytesRead);
    while BytesRead > 0 do
    begin
      BlockRead(F, Buffer2, SizeOf(Buffer2), BytesRead);

      // Объединяем буферы для проверки границ блоков
      for i := 0 to SizeOf(Buffer1) - Length(SearchStr) do
      begin
        Found := True;
        for j := 1 to Length(SearchStr) do
        begin
          if (i + j - 1 < SizeOf(Buffer1)) then
          begin
            if Chr(Buffer1[i + j - 1]) <> SearchStr[j] then
            begin
              Found := False;
              Break;
            end;
          end
          else
          begin
            if Chr(Buffer2[i + j - 1 - SizeOf(Buffer1)]) <> SearchStr[j] then
            begin
              Found := False;
              Break;
            end;
          end;
        end;

        if Found then
        begin
          // Найдено совпадение
          Writeln('Found at position: ', TotalRead + i);
        end;
      end;

      Move(Buffer2, Buffer1, SizeOf(Buffer1));
      Inc(TotalRead, SizeOf(Buffer1));
    end;
  finally
    CloseFile(F);
  end;
end;

Этот метод решает проблему поиска строк, которые могут находиться на границе блоков.

2. Использование TFileStream и TMemoryStream

procedure SearchWithMemoryStream(const FileName: string; const SearchStr: string);
var
  Stream: TMemoryStream;
  P, EndP: PByte;
  i, j: Integer;
  Found: Boolean;
begin
  Stream := TMemoryStream.Create;
  try
    Stream.LoadFromFile(FileName);
    P := Stream.Memory;
    EndP := P + Stream.Size;

    while P < EndP - Length(SearchStr) do
    begin
      Found := True;
      for j := 1 to Length(SearchStr) do
      begin
        if (P + j - 1)^ <> Byte(SearchStr[j]) then
        begin
          Found := False;
          Break;
        end;
      end;

      if Found then
      begin
        Writeln('Found at position: ', P - Stream.Memory);
        Inc(P, Length(SearchStr)); // Пропускаем найденную строку
      end
      else
      begin
        Inc(P);
      end;
    end;
  finally
    Stream.Free;
  end;
end;

3. Использование Memory Mapped Files (для Windows)

uses Windows;

function SearchWithMemoryMapping(const FileName: string; const SearchStr: string): Boolean;
var
  hFile: THandle;
  hMapping: THandle;
  FileSize: Int64;
  FilePtr: PByte;
  i: Integer;
begin
  Result := False;
  hFile := CreateFile(PChar(FileName), GENERIC_READ, FILE_SHARE_READ, nil,
    OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, 0);
  if hFile = INVALID_HANDLE_VALUE then Exit;

  try
    FileSize := GetFileSize(hFile, nil);
    hMapping := CreateFileMapping(hFile, nil, PAGE_READONLY, 0, 0, nil);
    if hMapping = 0 then Exit;

    try
      FilePtr := MapViewOfFile(hMapping, FILE_MAP_READ, 0, 0, 0);
      if not Assigned(FilePtr) then Exit;

      try
        for i := 0 to FileSize - Length(SearchStr) do
        begin
          if CompareMem(@FilePtr[i], @SearchStr[1], Length(SearchStr)) then
          begin
            Writeln('Found at position: ', i);
            Result := True;
          end;
        end;
      finally
        UnmapViewOfFile(FilePtr);
      end;
    finally
      CloseHandle(hMapping);
    end;
  finally
    CloseHandle(hFile);
  end;
end;

4. Оптимизированный поиск для конкретного случая ($$$$$$)

Как предложил avk, для конкретного случая поиска строки '$$$$$$' можно использовать оптимизированный алгоритм:

function FindBucks(const Data: array of Byte): TArray<Integer>;
var
  ResultArray: array of Integer;
  ResultCount: Integer;
  i: Integer;
begin
  SetLength(ResultArray, 1000); // Начальный размер
  ResultCount := 0;

  i := 0;
  while i <= High(Data) - 5 do
  begin
    if (Data[i] = Ord('$')) and 
       (Data[i+1] = Ord('$')) and 
       (Data[i+2] = Ord('$')) and 
       (Data[i+3] = Ord('$')) and 
       (Data[i+4] = Ord('$')) and 
       (Data[i+5] = Ord('$')) then
    begin
      if ResultCount = Length(ResultArray) then
        SetLength(ResultArray, Length(ResultArray) * 2);

      ResultArray[ResultCount] := i;
      Inc(ResultCount);
      Inc(i, 6); // Пропускаем найденную строку
    end
    else
    begin
      Inc(i);
    end;
  end;

  SetLength(ResultArray, ResultCount);
  Result := ResultArray;
end;

Сравнение производительности

По результатам тестирования, предложенного avk:

1. Наивный поиск (посимвольный) - очень медленный (минуты)
2. Boyer-Moore алгоритм - ~432 мс для файла 800 Мб
3. Специализированный FindBucks() - ~82 мс для файла 800 Мб

Рекомендации

1. Для общего случая поиска строк используйте:
2. Memory Mapped Files (на Windows)
3. Алгоритм Бойера-Мура для сложных строк

4. Чтение блоками с обработкой границ

5. Для конкретного случая поиска строки '$$$$$$':

6. Используйте оптимизированный алгоритм FindBucks()

7. Рассмотрите вариант загрузки всего файла в память через TMemoryStream

8. Если структура файла известна (как в случае andyf97), создайте индекс:

9. При первом чтении сохраните позиции всех заголовков
10. В дальнейшем используйте этот индекс для быстрого доступа

Заключение

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

Пример полного решения для случая andyf97:

procedure ProcessStructuredFile(const FileName: string);
var
  Stream: TMemoryStream;
  P, EndP: PByte;
  HeaderPositions: array of Integer;
  HeaderCount: Integer;
begin
  Stream := TMemoryStream.Create;
  try
    Stream.LoadFromFile(FileName);
    P := Stream.Memory;
    EndP := P + Stream.Size;
    SetLength(HeaderPositions, 17000); // Известное количество заголовков
    HeaderCount := 0;

    while (P < EndP - 6) and (HeaderCount < 17000) do
    begin
      // Ищем начало заголовка
      if (P[0] = $24) and (P[1] = $24) and (P[2] = $24) and
         (P[3] = $24) and (P[4] = $24) and (P[5] = $24) then
      begin
        HeaderPositions[HeaderCount] := P - Stream.Memory;
        Inc(HeaderCount);
        Inc(P, 46); // Пропускаем весь заголовок
      end
      else
      begin
        Inc(P);
      end;
    end;

    // Теперь HeaderPositions содержит позиции всех заголовков
    // Можно быстро переходить к любому заголовку: Stream.Position := HeaderPositions[i];
  finally
    Stream.Free;
  end;
end;

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

Создано по материалам из источника по ссылке.

Оптимизация поиска строк в больших файлах в Lazarus/Delphi с использованием различных методов и алгоритмов.

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Текст и Строки ::