Алгоритм поиска всех уникальных слов в файле
Материал из DRKB
////////////////////////////////////////////////////////////////////////////////
//
// ****************************************************************************
// * Unit Name : Dictionary
// * Purpose : Набор классов для работы с индексированным списком поиска
// * Author : Александр Багель
// * Version : 1.00
// ****************************************************************************
//
unit Dictionary;
interface
uses
Windows, Classes, SysUtils{, FullTextGetter};
type
// Класс отвечающий за создание словаря уникальных слов
TDictionaryFounder = class
private
FDict: TList;
FDictMem: array of String;
FDictMemCount: Integer;
protected
function GetPos(const Value: String): Integer; virtual;
procedure Insert(Value: String; Position: Integer); virtual;
function Prepare(const Value: String): String; virtual;
public
constructor Create;
destructor Destroy; override;
procedure AddData(Value: String); //overload;
// procedure AddData(ObjText: IFullTextGetter); overload;
procedure SaveToStream(var AStream: TMemoryStream);
end;
// Класс осуществляющий поиск в словаре
// полученном от TDictionaryFounder
TDictionaryFinder = class
private
FDict: array of ShortString;
FDictLength: Cardinal;
protected
function GetPos(const Value: ShortString;
const SubStr: Boolean = False): Boolean; virtual;
public
destructor Destroy; override;
procedure LoadFromStream(const AStream: TMemoryStream);
function Find(const Value: String;
const SubStr: Boolean = False): Boolean;
end;
implementation
{ TDictionaryFounder }
//
// Добавление информации для построения массива индексов
// =============================================================================
procedure TDictionaryFounder.AddData(Value: String);
var
Tmp: String;
Position, I: Integer;
S: TStringList;
begin
Value := Prepare(Value);
S := TStringList.Create;
try
S.Text := Value;
for I := 0 to S.Count - 1 do
begin
Tmp := S[I];
if Tmp = '' then Continue;
if FDict.Count = 0 then
Insert(Tmp, 0)
else
begin
Position := GetPos(Tmp);
if (Position >= 0) then
if FDict.Count > Position then
begin
if String(FDict.Items[Position]) <> Tmp then
Insert(Tmp, Position);
end
else
Insert(Tmp, Position);
end;
end;
finally
S.Free;
end;
end;
//
// Добавление информации для построения массива индексов
// Информация приходит из интерфейса
// =============================================================================
{procedure TDictionaryFounder.AddData(ObjText: IFullTextGetter);
var
S: String;
begin
if ObjText = nil then
raise Exception.Create('IFullTextGetter is empty.');
S := ObjText.GetText;
AddData(S);
end; }
constructor TDictionaryFounder.Create;
begin
FDict := TList.Create;
end;
destructor TDictionaryFounder.Destroy;
begin
FDict.Free;
FDictMemCount := 0;
SetLength(FDictMem, FDictMemCount);
inherited;
end;
//
// Возвращает номер позиции где находится слово, или должно находится...
// Поиск методом половинного деления...
// =============================================================================
function TDictionaryFounder.GetPos(const Value: String): Integer;
var
FLeft, FRight, FCurrent: Cardinal;
begin
if FDict.Count = 0 then
begin
Result := 0;
Exit;
end;
FLeft := 0;
FRight := FDict.Count - 1;
FCurrent := (FRight + FLeft) div 2;
if String(FDict.Items[FLeft]) > Value then
begin
Result := 0;
Exit;
end;
if String(FDict.Items[FRight]) < Value then
begin
Result := FRight + 1;
Exit;
end;
repeat
if String(FDict.Items[FCurrent]) = Value then
begin
Result := FCurrent;
Exit;
end;
if String(FDict.Items[FCurrent]) < Value then
FLeft := FCurrent
else
FRight := FCurrent;
FCurrent := (FRight + FLeft) div 2;
until FLeft = FCurrent;
if String(FDict.Items[FCurrent]) < Value then Inc(FCurrent);
Result := FCurrent;
end;
//
// Добавление нового индекса в массив индексов
// =============================================================================
procedure TDictionaryFounder.Insert(Value: String; Position: Integer);
begin
if FDictMemCount < FDict.Count + 1 then
begin
Inc(FDictMemCount, FDict.Count + 1);
SetLength(FDictMem, FDictMemCount);
end;
FDictMem[FDict.Count] := Value;
FDict.Insert(Position, @FDictMem[FDict.Count][1]);
end;
//
// Сохранение массива индексов в поток
// =============================================================================
procedure TDictionaryFounder.SaveToStream(var AStream: TMemoryStream);
var
I: Integer;
S: PChar;
TmpS: TStringList;
begin
if AStream = nil then Exit;
TmpS := TStringList.Create;
try
for I := 0 to FDict.Count - 1 do
begin
S := FDict.Items[I];
TmpS.Add(S);
end;
AStream.Position := 0;
AStream.Size := Length(TmpS.Text);
AStream.Write(TmpS.Text[1], Length(TmpS.Text));
AStream.Position := 0;
finally
TmpS.Free;
end;
end;
//
// Подготовка данных к обработке...
// Удаляются все не буквенные символы, каждое слово начинется с новой строки...
// =============================================================================
function TDictionaryFounder.Prepare(const Value: String): String;
var
I: Integer;
Len: Cardinal;
C: PAnsiChar;
LastEnter: Boolean;
begin
SetLength(Result, Length(Value) * 2);
Len := 0;
LastEnter := False;
for I := 1 to Length(Value) do
begin
C := CharLower(@Value[I]);
if C^ in ['a'..'z', 'а'..'я'] then
begin
Inc(Len);
Result[Len] := C^;
LastEnter := False;
end
else
if not LastEnter then
begin
Inc(Len);
Result[Len] := #13;
Inc(Len);
Result[Len] := #10;
LastEnter := True;
end;
end;
SetLength(Result, Len);
end;
{ TDictionaryFinder }
destructor TDictionaryFinder.Destroy;
begin
FDictLength := 0;
SetLength(FDict, FDictLength);
inherited;
end;
//
// Поиск введенных слов...
// =============================================================================
function TDictionaryFinder.Find(const Value: String;
const SubStr: Boolean = False): Boolean;
var
S: TStringList;
I: Integer;
begin
Result := False;
if Value = '' then Exit;
S := TStringList.Create;
try
S.Text := StringReplace(Value, ' ', #13#10, [rfReplaceAll]);
S.Text := AnsiLowerCase(S.Text);
if S.Count = 0 then Exit;
for I := 0 to S.Count - 1 do
begin
Result := GetPos(S.Strings[I], SubStr);
if not Result then Exit;
end;
finally
S.Free;
end;
end;
//
// Поиск каждого слова в массиве индексов
// =============================================================================
function TDictionaryFinder.GetPos(const Value: ShortString;
const SubStr: Boolean = False): Boolean;
var
FLeft, FRight, FCurrent, I: Cardinal;
begin
Result := False;
if SubStr then
begin
for I := 0 to FDictLength - 1 do
if Pos(Value, FDict[I]) > 0 then
begin
Result := True;
Exit;
end;
end
else
begin
if FDictLength = 0 then Exit;
FLeft := 0;
FRight := FDictLength - 1;
FCurrent := (FRight + FLeft) div 2;
if FDict[FLeft] > Value then Exit;
if FDict[FRight] < Value then Exit;
if FDict[FLeft] = Value then
begin
Result := True;
Exit;
end;
if FDict[FRight] = Value then
begin
Result := True;
Exit;
end;
repeat
if FDict[FCurrent] = Value then
begin
Result := True;
Exit;
end;
if FDict[FCurrent] < Value then
FLeft := FCurrent
else
FRight := FCurrent;
FCurrent := (FRight + FLeft) div 2;
until FLeft = FCurrent;
end;
end;
//
// Загрузка массива индексов из потока
// =============================================================================
procedure TDictionaryFinder.LoadFromStream(const AStream: TMemoryStream);
var
S: TStringList;
I: Integer;
begin
S := TStringList.Create;
try
AStream.Position := 0;
S.LoadFromStream(AStream);
FDictLength := S.Count;
if FDictLength = 0 then Exit;
SetLength(FDict, FDictLength);
for I := 0 to FDictLength - 1 do
FDict[I] := S.Strings[I];
finally
S.Free;
end;
end;
end.
пример использования:
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, ComCtrls, Dictionary;
type
TForm1 = class(TForm)
Button1: TButton;
ProgressBar1: TProgressBar;
Button2: TButton;
Edit1: TEdit;
Label1: TLabel;
CheckBox1: TCheckBox;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
end;
var
Form1: TForm1;
implementation
uses ComObj;
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
var
SH: TDictionaryFounder;
S: TStringList;
M: TMemoryStream;
I: Integer;
Start: Cardinal;
begin
S := TStringList.Create;
try
S.LoadFromFile('c:\1.txt');
ProgressBar1.Position := 0;
ProgressBar1.Max := S.Count;
SH := TDictionaryFounder.Create;
try
Start := GetTickCount;
for I := 0 to S.Count - 1 do
begin
SH.AddData(S.Strings[I]);
ProgressBar1.Position := I;
end;
ShowMessage('Время составления словаря: ' + IntToStr(GetTickCount - Start));
M := TMemoryStream.Create;
try
SH.SaveToStream(M);
M.SaveToFile('c:\2.txt');
ProgressBar1.Position := 0;
Button2.Enabled := True;
finally
M.Free;
end;
finally
SH.Free;
end;
finally
S.Free;
end;
end;
procedure TForm1.Button2Click(Sender: TObject);
var
S: TDictionaryFinder;
M: TMemoryStream;
begin
S := TDictionaryFinder.Create;
try
M := TMemoryStream.Create;
try
M.LoadFromFile('c:\2.txt');
S.LoadFromStream(M);
if S.Find(Edit1.Text, CheckBox1.Checked) then
ShowMessage('Элемент найден')
else
ShowMessage('Элемент не найден');
finally
M.Free;
end;
finally
S.Free;
end;
end;
end.
Author: Автор: Александр (Rouse_) Багель
Source: Взято из http://forum.sources.ru
ID: 04206