Programowanie w języku Delphi » Gotowce

Wyszukiwanie binarne w pliku tekstowym

  • 2011-10-03 17:13
  • 2 komentarze
  • 1839 odsłon
  • Oceń ten tekst jako pierwszy
art zainspirowany wątkiem http://forum.4programmers.net/viewtopic.php?id=76743

chcemy sprawdzić, czy dane słowo znajduje się w pliku tekstowym zawierającym posortowane alfabetyczne słowa. założenie jest takie, że zależy nam na oszczędności pamięci, więc nie ładujemy całego pliku do pamięci (może mieć on kilkadziesiąt MB). aż się prosi o to, żeby wyszukiwać binarnie, ale jak tu zapewnić sobie swobodny dostęp do pliku? pliki tekstowe mają przecież dostęp sekwencyjny.
ale kto powiedział, że plik z tekstem trzeba otwierać jako plik tekstowy?  

traktujemy taki plik jako plik amorficzny, celując poprzez seek() w jego dowolne miejsce, a linijkę z jakimś słowem odczytujemy jako pierwszy tekst w odczytanych danych znajdujący się pomiędzy znakami końca linii. w praktyce wymaga to odczytania trochę nadmiarowych danych (co najmniej 2*najdłuższe znajdujące się w pliku słowo + 4B na znaki końca linii).

funkcja zwracająca pierwsze słowo pod danym offsetem w pliku wygląda tak:

function getword : shortstring;
var
  buf         : array[1..512] of char;
  i,j,numread : integer;
begin
  blockread(f,buf,sizeof(buf),numread);
 
  for i := 1 to numread do
  if buf[i] = #10 then
  begin
    if sizeof(buf) - i < 250 then j := sizeof(buf) - i else j := 250;
 
    move(buf[i+1],result[1],j);
    result[0] := #255;
    result[0] := char(system.pos(#10,result)-1);
    break;
  end;
end;

przy czym f jest zdefiniowane wcześniej jako f : file; ponadto funkcja ta działa na danych oddzielonych znaczkami LF (format uniksowy), do CR LF (format windows) trzeba by ją nieznacznie poprawić. funkcja "przegapia" pierwsze i ostatnie słowo ze słownika - tu też trzeba by ją poprawić, ale już mi się nie chce.

i to w zasadzie wszystko - mając tą funkcję można zaimplementować binarne wyszukiwanie w pliku tekstowym.
funkcja findword sprawdza, czy w pliku ze słownikiem znajduje się podane słowo (małymi literami, bo funkcja jest case-sensitive).

function findword(n : shortstring) : boolean;
var
  f       : file;
  a,b,c,i : integer;
  s       : shortstring;
 
function getword : shortstring;
// tu wkleić wyżej podany kod
 
function ConvertISO1250(ch : char) : char;  { z iso-8859-2 na Windows Latin-2 1250 }
begin
  case ch of
  #177 : ConvertISO1250 := 'ą';
  #182 : ConvertISO1250 := 'ś';
  #188 : ConvertISO1250 := 'ź';
  else ConvertISO1250 := ch;
  end;
end;
 
 
function compare(const s,n : shortstring) : integer;
var
  conv : string[255];
  i : integer;
begin
  for i := 1 to length(s) do
  if s[i] < #128 then conv[i] := s[i] else conv[i] := ConvertISO1250(s[i]);
  conv[0] := s[0];
  result := AnsiCompareText(conv,n);
end;
 
 
begin
  assignfile(f,'slownik2.txt');
  reset(f,1);
 
  a := 0;
  b := filesize(f);
 
 
  while a <> b-1 do
  begin
    c := (a + b) shr 1;
 
    seek(f,c);
    s := getword;
    i := compare(s,n);
 
    if i > 0 then b := c else
    if i < 0 then a := c else
    break;
  end;
 
  closefile(f);
  result := i = 0;
end;

funkcja ConvertISO1250 dokonuje konwersji strony kodowej danych - po prostu w pliku, który miałem, dane miały kodowanie iso-8859-2. w sumie można wywalić całą funkcję compare zastępując ją AnsiCompareText.

2 komentarze

ŁF 2005-09-16 23:22

słownik, na któryj ćwiczyłem, miał akurat same małe litery. poza tym nie to jest sednem kodu.

migajek 2005-08-18 17:14

sry, a co z duzymi literami w funkcji ConvertISO1250.. ?:>