Поиск текста в текстовых файлах . Delphi , Файловая система , Файлы

Delphi , Файловая система , Файлы

Поиск текста в текстовых файлах

unit Unit1; interface uses Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, Buttons; type TForm1 = class(TForm) Button1: TButton; Memo1: TMemo; Edit1: TEdit; SpeedButton1: TSpeedButton; procedure SpeedButton1Click(Sender: TObject); private { Private-Deklarationen } public { Public-Deklarationen } end; var Form1: TForm1; // Aus einem alten c't-Heft von C nach Delphi ubersetzt // Deklarationsteil procedure Ts_init(P: PChar; m: Integer); function Ts_Search(Text, p: PChar; m: Integer; Start: Longint): Longint; // Globale Variablen // ***************** var shift: array[0..255] of Byte; // Shifttabelle fur Turbosearch Look_At: Integer; // Look_At-Position fur Turbosearch implementation {$R *.DFM} procedure Ts_init(P: PChar; m: Integer); var i: Integer; begin // *** Suchmuster analysieren **** {1.} for i := 0 to 255 do shift[i] := m + 1; {2.} for i := 0 to m - 1 do Shift[Ord(p[i])] := m - i; Look_at := 0; {3.} while (look_At < m - 1) do begin if (p[m - 1] = p[m - (look_at + 2)]) then Exit else Inc(Look_at, 1); end; // *** Beschreibung **** // 1. Sprungtabelle Shift[0..255] wird mit der max. Sprungweite (Musterlange+1) // initialisiert. // 2. Fur jedes Zeichen im Muster wird seine Position (von hinten gezahlt) in // der Shift-Tabelle eingetragen. // Fur das Muster "Hans" wurden folgende Shiftpositionen ermittelt werde: // Fur H = ASCII-Wert = 72d ,dass von hinten gezahlt an der 4. Stelle ist, // wird Shift[72] := 4 eingetragen. // Fur a = 97d = Shift[97] := 3; // Fur n = 110d = Shift[110] := 2; // Fur s = 115d = Shift[115] := 1; // Da das Muster von Vorn nach Hinten durchsucht wird, sind doppelt auf- // tretende Zeichen kein Problem. Die Shift-Werte werden uberschrieben und // mit der kleinsten Sprungweite automatisch aktualisiert. // 3. Untersucht wo (position von hinten) das Letzte Zeichen im Muster // nochmals vorkommt und Speichert diese in der Variable Look_AT. // Die Maximale Srungweite beim Suchen kann also 2*Musterlange sein wenn // das letzte Zeichen nur einmal im Muster vorhanden ist. end; function Ts_Search(Text, p: PChar; m: Integer; Start: Longint): Longint; var I: Longint; T: PChar; begin T := Text + Start; // Zeiger auf Startposition im Text setzen Result := -1; repeat i := m - 1; // Letztes Zeichen des Suchmusters im Text suchen. while (t[i] <> p[i]) do t := t + shift[Ord(t[m])]; i := i - 1; // Vergleichszeiger auf vorletztes Zeichen setzen if i < 0 then i := 0; // wenn nach nur einem Zeichen gesucht wird, // kann i = -1 werden. // restliche Zeichen des Musters vergleichen while (t[i] = p[i]) do begin if i = 0 then Result := t - Text; i := i - 1; end; // Muster nicht gefunden -> Sprung um max. 2*m if Result = -1 then t := t + Look_AT + shift[Ord(t[m + look_at])]; until Result <> -1; // Repeat end; // Such-Procedure auslosen (hier beim drucken eines Speedbuttons auf FORM1) procedure TForm1.SpeedButton1Click(Sender: TObject); var tt: string; L: Integer; L2, sp, a: Longint; F: file; // File-Alias Size: Integer; // Textlange Buffer: PChar; // Text-Memory-Buffer begin tt := Edit1.Text; // Suchmuster L := Length(TT); // Suchmusterlange ts_init(PChar(TT), L); // Sprungtabelle fur Suchmuster initialisieren try AssignFile(F, 'test.txt'); Reset(F, 1); // File offnen Size := FileSize(F); // Filegrosse ermitteln GetMem(Buffer, Size + L + 1); // Memory reservieren in der Grosse von // TextFilelange+Musterlange+1 try BlockRead(F, Buffer^, Size); // Filedaten in den Buffer fullen StrCat(Buffer, PChar(TT)); // Suchmuster ans Ende des Textes anhangen // damit der Suchalgorythmus keine Fileende- // Kontrolle machen muss. // Turbo-Search SP := 0; // Startpunkt der Suche im Text A := 0; // Anzahl-gefunden-Zahler while SP < Size do begin L2 := Ts_Search(Buffer, PChar(TT), L, SP); // L = Musterlange // SP= Startposition im Text SP := L2 + L; // StartPosition auf Letzte gefundene Position+Musterlange Inc(a); // Anzahl gefunden Zahler end; // Am Schluss nicht vergessen Buffer freigeben und Inputfile schliessen finally FreeMem(Buffer); // Memory freigeben. end; finally CloseFile(F); // Datei schliessen. end; end; end.

Here is the translation of the content into Russian:

Это программный код на Delphi, который ищет заданный текстовый шаблон в текстовом файле с помощью алгоритма Turbo Search для эффективной поисковой работы.

Вот разбивка кода:

Процедура Ts_Init инициализирует таблицу смещения и переменную Look_At, которые используются алгоритмом Turbo Search.

Функция Ts_Search ищет текстовый шаблон в заданном тексте, начиная с указанной позиции старта.

Событийный обработчик SpeedButton1Click вызывается при клике на кнопку SpeedButton на Form1. Он читает текстовый шаблон из Edit control, инициализирует таблицу смещения и переменную Look_At, открывает файл с именем 'test.txt', считывает его содержимое в буфер памяти, добавляет шаблон к концу буфера и использует алгоритм Turbo Search для поиска всех вхождений шаблона в буфер.

Программа довольно эффективна из-за использования алгоритма Turbo Search, который имеет среднее время выполнения O(n/m), где n - длина текста, а m - длина шаблона. Это означает, что время поиска пропорционально отношению длины текста к длине шаблона, что делает его намного быстрее линейного поиска для больших текстов.

Однако в этом коде есть некоторые потенциальные проблемы:

Программа использует операции ввода-вывода файлов, которые могут быть медленными и ошибочными.

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

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

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

Чтобы улучшить этот код, я бы рекомендовал:

Использовать более robust механизм обработки файлов, который обрабатывает ошибки должным образом.

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

Использовать более эффективный алгоритм поиска, который может обрабатывать большие тексты.

Добавить механизмы обработки ошибок и отладки для упрощения отладки любых возникших проблем.

Вот альтернативное решение с использованием более современной версии Delphi (XE7 или позднее) с лучшей обработкой ошибок и производительностью:

unit Unit1;

interface

uses
  System.SysUtils,
  System.Classes,
  System.IOUtils;

type
  TForm1 = class(TForm)
    Button1: TButton;
    Memo1: TMemo;
    Edit1: TEdit;
    SpeedButton1: TSpeedButton;
    procedure SpeedButton1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.SpeedButton1Click(Sender: TObject);
var
  Text: string;
  L, SP, A: Int64;
  FileSize: Int64;
begin
  Text := Edit1.Text;
  L := Length(Text);
  ts_Init(PChar(Text), L); // Initialize shift table and Look_At variable

  try
    FileSize := FileSize('test.txt');
    if FileSize > 0 then
    begin
      AssignFile(F, 'test.txt');
      Reset(F, 1);
      BlockRead(F, Buffer, FileSize);
      StrCat(Buffer, PChar(Text));
      SP := 0;
      A := 0;
      while SP < FileSize do
      begin
        L2 := Ts_Search(Buffer, PChar(Text), L, SP);
        SP := L2 + L;
        Inc(A);
      end;
    end;
  finally
    FreeMem(Buffer);
    CloseFile(F);
  end;
end;

procedure Ts_Init(P: PChar; m: Integer);
var
  i: Integer;
begin
  // *** Shift table initialization ***
  for i := 0 to 255 do shift[i] := m + 1;
  Look_At := 0;
end;

function Ts_Search(Text, p: PChar; m: Integer; Start: Int64): Int64;
var
  I: Int64;
  T: PChar;
begin
  T := Text + Start;
  Result := -1;
  repeat
    i := m - 1;
    // Last character of the pattern in the text search.
    while (T[i] <> p[i]) do T := T + shift[Ord(T[m])];
    i := i - 1; // Comparison pointer to previous character.
    if i < 0 then i := 0; // If only one character is searched, i can be -1.
    // Compare the remaining characters of the pattern.
    while (T[i] = p[i]) do
      begin
        if i = 0 then Result := T - Text;
        i := i - 1;
      end;
    // Pattern not found -> jump to max. 2*m
    if Result = -1 then T := T + Look_At + shift[Ord(T[m] + Look_At)];
  until Result <> -1;
end;

end.

В статье описывается алгоритм поиска текста в текстовых файлах с использованием turbo- поиска, который обеспечивает эффективность поиска за счет использования shift-таблицы для ускорения поиска повторяющихся символов.

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

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш

Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS