Czy istnieje jakis system baz danych ktory nie wymaga instalowania dodatkowych serwerow, prograow czy innych elementow utrudniajacych zycie - powiedzmy ze chce miec dostep do bazy danych znajdujacej sie w katalogu z programem, chce ja szybko i sprawnie przeszukiwac w niezbyt zaawansowany sposob ale nie chce korzystac do tego z jakis serwerow bo poziom skomplikowania tego zagadanienia nijak ma sie do instalowania tego typu rzeczy :) Zalezy mi na tym zeby baza danych znajdowala sie w pliku i zeby NIE INSTALOWAC zadnych dodatkowych aplikacji - istnieje taka mozliwosc? Mozecie mi na jej temat cos powiedziec? Chodzi o proste wyrazenie SQL w ktorym moge sprawdzic czy dany rekord istnieje ale podkreslam ze plik mialby miec 2,5mln (posortowanych) rekordow (slownik).
Skoro to słownik, to może zamiast bazy danych wykorzystać zwykły plik i USS (uniwersalną strukturę słownikową)?
Moze to zabrzmi wrecz glupio ale nie moge znalezc nigdzie opisu USS pod delphi i uzyc jej zastosowania. Na zwyklym pliku rowniez probowalem operowac dziesiatkami sposobow ale albo wychodza przeklamania (typu wyraz 'rko' potrafi istniec ze wzgledu na wystepowanie tego ciagu w wyrazie 'biurko') albo trwa to niemislosiernie dlugo (w zaleznosci od parametru komputera do minuty :|) a mi zalezy na tym zeby trwalo to nie wiecej niz 2 sek - masz jaki pomysl albo namiary na opis rozwiazania? Bo wiele osob mowi o USS a ja nie moge jakos na to trafic :(
Było kiedyś o tym na forum, poszukaj.
Owszem - jest o tym na forum ale jedynie wzmianka i nie ma nic wiecej poza zaznaczeniem na czym sie to OGOLNIE opiera i ze takie cos istnieje :/ Szukalem - tego na forum nie ma (w necie tez ciezko znalezc - w zasadzie nie moge)
Dryobates napisał kiedyś kawałek gotowego kodu : http://4programmers.net/Forum/95572?h=TNode#95572
Wiem, widzialem ale nie wiem jak zapisywac/odczytowac to do/z pliku :(
Postanowilem zwrocic sie z problemem do Dryobatesa ktory staral sie cos zaradzic. Spedzil nad tym sporo czasu za co jestem mu bardzo wdzieczny ale pojawil sie problem... Slownik ma 2,5mln linii (slownik z kurnika) i kiedy dzialam na tym co zaproponowal Dryobates (kod ponizej) pojawia sie problem ktorego nie moglismy (w zasadzie on nie mogl bo ja sie w tym gubie) rozwiazac. Otoz po zastosowaniu ponizszych procedur kiedy dodaje linie do slownika to juz na literze A i nawet nie calej wywala ze zabraklo pamieci. I cos w tym jest bo w tym momencie program zajmuje az 183mb ramu :) Wczytanie SAMEJ litery 'a' dziala ale powoduje zajecie rowniez sporej pamieci ramu (niestety) - wiec moje pytanie brzmi tak: czy ktos wie co zmienic aby wszystko dzialalo? Aby USS nie zajmowal tak duzych zasobow pamieci?
Kod USS:
unit uss;
interface
uses Classes;
type PNode = ^TNode;
TNode = record
Last: Boolean;
Letters: array [Char] of PNode;
end;
type
(* Klasa slownika wykorzystujacego USS *)
TDict = class(TObject)
private
(* Element USS zawierajacy pierwsze litery slow *)
FRoot: PNode;
public
constructor Create;
destructor Destroy;override;
(* Dodaje slowo AWord do slownika *)
procedure Add(AWord: string);
(* Zwraca True, jezeli slowo AWord wystepuje w slowniku *)
function Find(AWord: string): Boolean;
(* Zwraca TStringList zawierajacy wszystkie slowa ze slownika *)
function Print: TStringList;
(* Zapisuje slownik do strumienia *)
procedure SaveToStream(AStream: TStream);
(* Wczytuje slownik ze strumienia *)
procedure LoadFromStream(AStream: TStream);
(* Czysci zawartosc slownika *)
procedure Clear;
protected
(* Pomocnicza funkcja zwracajaca nowy element drzewa *)
function NewNode: PNode;
end;
implementation
constructor TDict.Create;
begin
FRoot := nil;
end;
procedure TDict.Add(AWord: string);
(* Pomocnicza funkcja rekurencyjna dodajaca poszczegolne litery slowa *)
procedure AddRec(ANode: PNode; APos: Integer);
var
Node: PNode;
begin
if APos > Length(AWord) then
begin
ANode.Last := True;
Exit;
end;
Node := ANode.Letters[AWord[APos]];
if Node = nil then
begin
Node := newNode;
ANode.Letters[AWord[APos]] := Node;
end;
AddRec(Node, APos + 1);
end;
begin
if FRoot = nil then
FRoot := NewNode;
AddRec(FRoot, 1);
end;
function TDict.Find(AWord: string): Boolean;
(* Pomocnicza funkcja rekurencyjna wyszukujaca slowa *)
function FindRec(ANode: PNode; APos: Integer): Boolean;
var
Node: PNode;
begin
if APos > Length(AWord) then
begin
Result := ANode.Last;
Exit;
end;
Node := ANode.Letters[AWord[APos]];
if Node <> nil then
begin
Result := FindRec(Node, APos + 1);
Exit;
end;
Result := False;
end;
begin
Result := FindRec(FRoot, 1);
end;
function TDict.Print: TStringList;
var
List: TStringList;
i: Char;
procedure PrintRec(ANode: PNode; AWord: string);
var
i: Char;
begin
if ANode = nil then
Exit;
if ANode.Last then
List.Add(AWord);
for i := Chr(0) to Chr(255) do
PrintRec(ANode.Letters[i], AWord + i);
end;
begin
List := TStringList.Create;
for i := Chr(0) to Chr(255) do
PrintRec(FRoot.Letters[i], i);
Result := List;
end;
procedure TDict.SaveToStream(AStream: TStream);
procedure Save(ANode: PNode);
var
i: Char;
Buf: Byte;
begin
if ANode = nil then
Exit;
Buf := Byte(ANode.Last);
AStream.Write(Buf, SizeOf(Byte));
for i := Chr(0) to Chr(255) do
begin
Buf := Buf shr 1;
if ANode.Letters[i] <> nil then
Buf := Buf or 128;
if Byte(i) mod 8 = 7 then
AStream.Write(Buf, SizeOf(Byte));
end;
for i := Chr(0) to Chr(255) do
if ANode.Letters[i] <> nil then
Save(ANode.Letters[i]);
end;
begin
Save(FRoot);
end;
procedure TDict.LoadFromStream(AStream: TStream);
procedure Load(ANode: PNode);
var
i: Char;
Node: PNode;
Buf: Byte;
begin
AStream.Read(Buf, SizeOf(Byte));
ANode.Last := Boolean(Buf);
for i := Chr(0) to Chr(255) do
begin
if Byte(i) mod 8 = 0 then
AStream.Read(Buf, SizeOf(Byte));
if Buf and 1 = 1 then
begin
Node := newNode;
ANode.Letters[i] := Node;
end;
Buf := Buf shr 1;
end;
for i := Chr(0) to Chr(255) do
if ANode.Letters[i] <> nil then
Load(ANode.Letters[i]);
end;
begin
Clear;
FRoot := NewNode;
Load(FRoot);
end;
function TDict.NewNode: PNode;
var
Node: PNode;
begin
New(Node);
FillChar(Node.Letters, SizeOf(Node.Letters), 0);
Node.Last := False;
Result := Node;
end;
procedure TDict.Clear;
procedure ClearRec(ANode: PNode);
var
i: Char;
begin
if ANode = nil then
Exit;
for i := Chr(0) to Chr(255) do
ClearRec(ANode.Letters[i]);
Dispose(ANode);
end;
begin
ClearRec(FRoot);
Dispose(FRoot);
FRoot := nil;
end;
destructor TDict.Destroy;
begin
Clear;
end;
end.
PS. Swoja droga ktos napisal wreszcie cos na ten temat bo naprawde ciezko o tego typu zrodla w necie.
A nie bylo by dobrze aby podzielic ten slownik z kurnika na pliki tak aby w kazdym byly slowa tylko zaczynajace sie na jedna literke? No wiesz w jednym same slowa na A w drugim na B itd. Wtedy mozna by bylo wczytywac po pliku wykonac na nim operacje i wywalic z pamieci wczytac nastepny ktory bedzie potrzebny ;)
Pedros napisał(a)
A nie bylo by dobrze aby podzielic ten slownik z kurnika na pliki tak aby w kazdym byly slowa tylko zaczynajace sie na jedna literke? No wiesz w jednym same slowa na A w drugim na B itd. Wtedy mozna by bylo wczytywac po pliku wykonac na nim operacje i wywalic z pamieci wczytac nastepny ktory bedzie potrzebny ;)
Już mu radziłem coś takiego, z tym, że wg pierwszych 2 literek (przy podziale wg jednej wciąż za duże są pliki).
Tylko on chce mieć wszystko w jednym pliku.
Ograniczenie tylko do małych liter i polskich znaków diakrytycznych co prawda zmniejsza zajętość pamięci ponad dwukrotnie, ale to wciąż za mało.
A zamiast ładowania do pamięci wyszukiwanie potrzebnego słowa w pliku? Nie bardzo wiem, jak to jest zapisywane, ale chyba można dojść do konkretnego słowa nie ładując całego pliku, ale tylko konieczne gałęzie drzewa?
ja bym to zrobił tak:
dwa pliki tekstowe - w jednym stała, duża baza danych słów, w drugim malutka ze słowami dodanymi przez użytkownika.
potem wyszukiwanie binarne po kolei w obu plikach bez ładowania ich do pamięci. co prawda ciężko jest skakać po pliku tekstowym, ale jest to jak najbardziej możliwe i zaraz spróbuję to zaimplementować. Czak - jeśli Cię to interesuje, to -> gg.
[dopisane]
konkretnie wygląda to tak: mamy plik tekstowy z posortowanymi alfabetycznie słowami. niby wszystko fajnie, ż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? [diabel]
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 (conajmniej 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 - trzeba by ją nieznacznie 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.
ŁF - to ja już wolałbym wykorzystać B-drzewa. Chyba lepsza byłaby wydajność.
// drzewo binarne w pliku tekstowym? jak chcesz to zaimplementować? a wydajność... sprawdź - Ł
/* gdzie było o tym, że to ma być tekstowe? A wydajność? Zerknij jak działa index w systemie portów w FreeBSD. Oparty jest o Berkley DB, które wykorzystuje B-drzewa. Albo Subversion. Też działa w oparciu o Berkley DB (teraz może też o natywny system plików). */
A czemu nie użyjesz drzewa slownikowego:
W przykładzie poniżej zapisane są wyrazy: ala, aleja, alejka, cal, całka, z, za :]
<begin>
<a>
<l>
<a>
<end/>
</a>
<e>
<j>
<a>
<end/>
</a>
<k>
<a>
<end/>
</a>
</k>
</j>
</e>
</l>
</a>
<c>
<a>
<l>
<end/>
</l>
<ł>
<k>
<a>
<end/>
</a>
</k>
</ł>
</a>
</c>
<z>
<end/>
<a>
<end/>
</a>
</z>
</begin>
Oczywiście wpisałem to w stylu XML'owym po to by było czytelne, ale taką strukturę można znacznie lepiej upakować w pliku :]
Drzewo wygląda tak, że ort! oznacza początek wyrazu, a liść jego koniec, pomiędzy ort!, a liściem na poszczególnych węzłach zapisane są ort! litery wyrazu. Każda gałąź drzewa reprezentuje jakiś wyraz.
// prosimy nie odświeżać starych tematów - Ktos
//do Kogoś: <ort>A nipy czemó mam nie podafac rozfionzania problemó</ort> ktury <ort>hyba jesce</ort> nie jest <ort>rozfiązany tam, gdzie ten proplem zaiztniał (tzn w poscie</ort> NIE MA <ort>nidz o tym, rze jusz fszystko działa)</ort> [???] >> <ort>Morze pofinienem otwożyć nofy themat tego typó i zoztać zpesztanym, za to rze nie wyszókałem najpierf czy nic fcześniej o tym niebyło</ort> :] <ort>Jeśli niemorzna odpofiadać na ztare thematy to nipy czemó one siem same niezamykajom po jakimź czaśe</ort> :>
to ja tylko odpowiem na pytanie postawione w poście - tak są takie bazy - wszystkie, które posiadają wersję EMBADED - prócz pliku exe masz w katalogu plik bazy i 1, 2 dllki (w zależności od silnika BD)
Seba, na tym forum taka zasada jest. Kilka osób mi już zaraca uwagę, że jest dziwna.
A już naprawdę nie mogłeś tego komentarza swojego napisać w sposób komunikatowny? Dłuższą chwilę się męczyłęm ze zrozumieniem o co Ci chodzi. Wiem, że to tak specjalnie było, ale to denerwuje.
Z drugiej strony Twój post był sensowny itd. - może napiszesz artykuł o drzewach słownikowych?
Ktos napisał(a)
Może napiszesz artykuł o drzewach słownikowych?
Chyba mam lepszy pomysł ;P
Jak znajdę chwilkę to napiszę szablon klasy takiego drzewa i programik, który za jej pomocą będzie kontrolował poprawność i ewentualnie proponował najlepiej pasujace wyrazy z takiego drzewa :]
Jak go zrobię to dam wam do to do zaimplementowania w systemie coyote i więcej nie będzie takich problemów, że mi Oyon <ort>żóca bana(na) f tfasz tylco sa tho, rze parem bledzikuw zropiłem</ort> :]
A i jeszcze obliczyłem, że takie drzewo dla dowolnego języka od-łacińskiego (no może poza niemieckim ze względu na te ich strasznie długie wyrazy) będzie miało około 1k węzłów :] (tzn tyle zajełoby pełne drzewo zawierające wszystkie możliwe ciągi 7 literowe z alfabetu zawierającego 35 znaków - a w języku polskim średnia długość wyrazu wynosi nieco ponad 6 znaków i nie wszystkie kombinacje liter uznawane są za zrozumiałe ;) )
A to możnaby zapisać w pliku wielkości około 2kB (wcześniej napisałem Tobie, że 1MB ;P ale niedawno wymyśliłem jeszcze ciaśniejszą strukturę zapisu :) ) ...no min 1kB - ale to wymagałoby zapisywania po bitcie, a nie wiem czy mi się aż tak będzie chciało bawić :-/
Mam problem może głupi ale... Mam program który sprawdza bierzącą date, wyświetla ją a także przypisuje do tej daty imionona zawarte w pliku tekstowym. wszystko jest ok tylko musze dodać do programu funkcje, która po wpisaniu imienia znajdzie w pliku linie w której zanjduje sie szukane słowo. Dane w pliku zapisane są w takiej postaci: "01-01==Maria, Mieczysław, Mieszko". prosze o pomoc i wytłumaczenie "jak krowie na rowie" jak to napisać. Chce żeby to wydlądało tak: Sprawdz kiedy są twoje imieniny(podaj imie); gdy wpisze np. Maria wyskoczy linia podana wyżej. wiem że to głupie ale muszę to zrobić na zaliczenie a z fachowej literatury nic nie rozumiem.
A może zamiast tak kombinować podpiąć do tego Accessa, nie jest to server, anie nic takiego, wystaczy ustawić połączenie, a jakieś tam podstawowe funkcje bazy sa już zamiplementowane, potem go zahasłować i M$ załatwił wszystko za nas. Nie wiem jak z licencjami jest u Ciebie, ale najprościej jest dość dobrze.
Albo zrobic bazę XMLową, zajmuje nieco więcej miejsca na HDD niz te same dane z relacyjnej, ale podobno jest szybsza do tego na czasie, no też jest to plik a nie serwerek :)))
Ludzie co wy tworzycie?
Komputer z 500MB ramu nie może wczytać bazy 30MB w czasie kilku sekund z dysku o szybkości transferu kilkadziesiąt MB/s!? :D
Te obiekciki z VCL są tu przyczyną wszystkich problemów.
Tego nie można ładować do jakiegoś TStrings - użyj debagera, a zobaczysz co tam się wyprawia (współczuję dziecinom z Borland)... zwykłe dodanie linii to miliony idiotycznych operacji: realokacje, kopiowania, testowanie, sprawdzanie i kontrola sprawdzania z testowaniem kontroli, itp. [???]
To jest dobre dla kilkuset linii, góra tysiąc.
To trzeba zrobić metodami optymalnymi, a nie takim tam... zlituj się Boże, stringami paskalowymi. :D
Zwykła lista wskaźników + wyszukiwanie binarne, jeszcze kilka drobnych zabiegów z alokowaniem pamięci... wszystko śmiga, i dymu nie widać! [!!!]