Elektroda.pl
Elektroda.pl
X

Search our partners

Find the latest content on electronic components. Datasheets.com
Elektroda.pl
Please add exception to AdBlock for elektroda.pl.
If you watch the ads, you support portal and users.

Uniwersalna Struktura Słownikowa

29 Nov 2004 18:06 7048 27
  • Level 22  
    Czy ktoś może mi cos pomóc w tym temacie. Mam zaimplementować w C słownik polsko angielski i angielsko polski. Może linki do stronek w necie... przykładowe programy dopisywania, kasowania i wyszukiwania par słów... baza danych przechowywana w pliku.
  • Level 25  
    heh program na zaliczenie?
  • Level 22  
    Nie, to tylko projekt na informe. Nie proszę o zrobienie tego za mnie, tylko o pomoc w szukaniu materiałów.
  • Level 25  
    Nie rozumiem w czym problem ja zrobil bym tak:

    1. ustalic co program powinien robic (to juz zrobiles, [dodawanie, usuwanie, itp])
    2. zaprojektowac interfejs (graficzny jesli to ma byc robione z WinAPI, itd)
    3. ustalic podstawowa strukture danych
    4. ustalic baze danych jako np dynamiczna tablice

    jeszcze pare mniejszych rzeczy :)

    piszesz ze niechce sz zeby zrobil to ktos za ciebie ale szukasz kodow zeby je skopiowac ...no ladnie :P
  • Level 22  
    Bo są gotowe algorytmy uniwersalnej struktury słownikowej. Tylko ja ich po prostu nie rozumiem. W tym jest problem. Chodzi właśnie o strukturę danych. Szukam gotowych kodów, żeby mi ktoś je wytłumaczył, żebym mógł ich uzywać w pełni świadomy ich działania. Całą resztą zrobię potrafię zrobić sam...
  • Level 29  
    No to podrzuć coś, pogadamy sobie o tym.
  • Level 22  
    #include < string.h>
    #include < ctype.h>
    #include < fstream.h>
    #define SIZE 29

    struct slownik
    {
    struct slownik *t[SIZE];
    };


    int do_indeks(char s)
    {
    return tolower(s)-'a';
    }

    char z_indeks(int n)
    {
    return tolower(n)+'a';
    }

    void dodaj(char *s,struct slownik* q)
    {

    for (int j=0;j< strlen(s);j++)
    {
    int pos=do_indeks(s[j]);
    if (q->t[pos]==NULL)

    {
    q->t[pos]=new slownik;
    for (int i=0;i< SIZE;q->t[pos]->t[i++]=NULL);
    }
    q=q->t[pos];
    }
    q->t[SIZE-1]=q;
    }

    void wypisz(struct slownik *s)
    {
    for (int x=0;x<26;x++)
    if (s->t[x]!=NULL)
    {
    cout<< z_indeks(x);
    if ( s->t[x]->t[SIZE-1]==s->t[x]) cout<< endl;
    wypisz( s->t[x]);
    }

    }

    void wypieprz(slownik* dt)
    {
    for (int x=0;x< SIZE;x++)
    if (dt->t[x]) wypieprz(dt->t[x]);
    delete dt;
    }


    int main()
    {
    slownik *s=new slownik;
    dodaj("komputer",s);
    dodaj("kompilator",s);
    wypisz(s);
    wypieprz(s);
    return 0;
    }


    Znalazłem taki programik, tylko nie wiem jak on ma działać.
    1. nie wiem, do czego służy fstream.h, bo bloodshed nie ma tej biblioteki.
    2. Nie bardzo rozumiem działania funkcji "dodaj" i "wypisz". A zwłaszcza gdzie on dodaje i skąd odczytuje. Docelowa ma w pliku
    3. Jak uporamy się z 1 i 2. Jak zrobić takie dwie struktury dla słów w języku polskim i angielskim, żeby były ze sobą powiązane przez znaczenie tego słowa. (Bo mam zaimplementować słownik)
    4. Nie wiem skąd to się wzięło "cout<< endl" i co to jest.

    Program mam praktycznie już napisany, ale przy użyciu topornej metody trzymania całych par słów w pliku. A chciałbym się nauczyć zrobić to lepiej...
  • Level 21  
    1. fstream.h jest to podstawowa biblioteka do obsługi plików w c++. Przyjrzyj się dokładnie co mówi kompilator a'propos tego "nie ma". Najprawdopodobniej wyświetla ostrzeżenie że używasz przestarzałego nazewnictwa. Powinieneś napisać #include <fstream> (bez .h) (też używam dev c++)
    aby program się skompilował trzeba zrobić następujące deklaracje ( w miejsce
    tych, które były):
    #include <string>
    #include <ctype.h>
    #include <fstream>
    #include <stdlib.h>
    #include <iostream>
    #define SIZE 29
    using namespace std;

    jeszcze jedno:
    w przykładzie były deklaracje typu:
    #include < ctype.h >
    w nawiasie nie może być spacji

    2. Nie wiem na jakim poziomie "dydaktyczności" jest twoje zadanie i czy masz
    narzucone to, z jakich konstrukcji masz korzystać.
    Przykład w takiej formie, jaką przedstawiłeś jest trochę zagmatwany, nie działa tak jak powinien (rezultatem wykonania programu jest wypisanie parę tysięcy razy
    znaku 'a'), a na dodatek sporo w nim archaizmów.
    Mam ochotę trochę się tym pobawić, możesz się ze mną skontaktować. (używam gg,
    numer powinieneś znaleźć).

    Funkcje o które pytasz nie działają prawidłowo, zacząłem analizę funkcji dodaj, ale jest ona na tyle (...) że lepiej ją napisać od nowa.

    3. tworzysz strukturę zawierającą dwie tablice znaków jedna zawiera słowo po angielsku,
    druga po polsku, tworzysz tablicę takich struktur albo (bardziej zaawansowana
    opcja) kontener, przeszukujesz w takiej tablicy/kontenerze po kolei wyrazy i
    sprawdzasz który pasuje.
    *Po co struktura jeśli może to być klasa.
    *w bibliotece stdlib masz typ string bardzo wygodny w użyciu

    4. cout << endl; wypisuje na ekran znak końca linii;
    cout << jakas_zmienna; wypisuje jej wartość
    można też robić rzeczy typu:
    cout << "opis: " << zmienna1 << "\topis2: " << zmienna2 << endl << "opis3: " << zmienna3<<endl;

    5. nazwa funkcji p......() jest nieprawidłowa. zamień ją np na p();
  • Level 22  
    Chodziło mi bardziej o kompresję danych, która miała być podobo zaimplementowana w tym algorytmie. Wiem, że ma on błędy. Sam bróbowałem go analizować i zmieniałem trochę, żeby cokolwiek dało się zrobić, ale nie bardzo mi wychodziło. San niestety tego nie napiszę... Nawet nie wiem o co pytać. Jakbym miał jakiś gotowy szkielet to już obrabiłbym sobie go do swoich potrzeb...

    P.S. Skąd można ściągnąc bibliotekę ncurses?
  • Level 22  
    Ech... no normalnie pomagacie mi, że aż miło... Wklajałem oryginał, próbowałem zaczaić jak działa, zmieniałem, bawiłem się...

    Zadam tylko pytanie. Czy ktokolwiek wie o co mi chodzi? Czy ktoś wie jak zaimplementować algorytm tzw. UNIWERSALNEJ STRUKTURY SŁOWNIKOWEJ?

    A jak tak, to może mi opdaj jakieś linki, przykłady, troche wytłumaczyć, żebym wiedział czego się uczepić??
  • Level 21  
    Tak, pomagamy Ci aż miło.
    Nie jest to komercyjny serwis, gdzie za kasę udzielają porad i korepetycji. Musisz się z tym pogodzić, że jeśli nikt nie ma już gotowej odpowiedzi- dostaniesz co najwyżej podpowiedzi.
    Wiem jak zaimplementować uniwersalną strukturę słownikową, ale jeszcze jej nie zaimplementowałem i dzisiaj już nie zdążę. Za pół godziny wyłączam kompa i do poniedziałku nie będę się z nim widział. Znalazłem nawet stronę z której pochodzi przykład z opisem (szkoda że nie znalazłem jej wcześniej).

    Jeśli idzie o podpowiedzi:
    (niektóre mogą się nie przydać, nie wiem ile już wiesz)
    program operuje na łańcuchach znaków "w stylu c"
    Taki łańcuch to tablica typu
    char t[dlugosc_lancucha_plus_jeden_albo_wiecej];
    ostatni (wpisany) znak w tablicy ma wartość 0 inaczej NULL, według konwencji to zakończenie łańcucha;

    tolower(s)-'a';
    oznacza "zamień literę na małą i odejmij od niej wartość 'a' " w rezultacie zamieni 'a' i 'A' na 0, 'b' i 'B' na 1 itd.
    uwaga: przy tej konstrukcji będzie problem z polskimi znakami.

    do łańcucha zdefiniowanego jak poprzednio:
    char t[dlugosc_lancucha_plus_jeden_albo_wiecej];
    możesz odwoływać się za pomocą wskażnika zdefiniowanego w ten sposób:
    char *s=dane; (nazwa tabeli w c/c++ dla kompilatora jest wskaźnikiem do pierwszego jej elementu)
    do kolejnej litery odwołujesz się
    w tymn wypadku
    s[nr_litery];
    lub
    t[nr_litery];
    (pamiętając że c/c++ numeruje elementy tabeli od 0


    Ay zrobić słownik dwujęzyczny masz dwa wyjścia:
    1. w strukturze jaką masz zapisujesz w jednym łańcuchu najpierw wyraz w języku z którego tłumaczysz oddzielasz go jakimś znakiem który na pewno nie pojawi się w słowniku np | i dopisujesz wyraz w drugim języku (nie jestem pewien czy nie będzie tu problemów przy wyszukiwaniu danych)

    2. robisz strukturę (wolałbym klasę) w której masz dwa elementy zawierające wyrazy w jednym i drugim języku.
  • Level 22  
    niestety nie o to mi chodziło. Tyle to ja potrfię. No i taki projekt już napisałem. Chodziło mi o wykorzystanie struktur odwołujących sie do samych siebie. O odczyt i zapis słów w postaci rekurencyjnej... Coś co miało być celem tego kodu co przeslałem, tylko jakoś nie za bardzo chce działać i nie wiem, jak to poprawić. I żeby wszystki dane były w pliku a w pamięci komputera tylko te aktualnie potrzebne.
  • Level 29  
    Otwarłem słownik angielsko-polski na losowej stronie, musiałem to zrobić kilkukrotnie, a szukałem słowa które miało by po polsku jedno znaczenie, należy o tym pamiętać. Lista znaczeń to w zasadzie lista wskaźników do pliku ze słowami w drugim języku, powiedzmy po cztery bajty. Liter w alfabecie angielskim jest 26 (5 bitów) w polskim potrzebne będzie 6, może warto pomyśleć o choć takiej kompresji. Stawiałbym na drzewa czerwono-czarne (red-black trees) lub jeśli słownik ma być na dysku to B-Trees (nie binarne).
    Godną polecenia (choć drogą) jest „Sztuka programowania” Donalda Knutha. Jeśli serio myślisz o programowaniu – musisz to mieć.
  • VIP Meritorious for electroda.pl
    Polskich znaków diakrystycznych jest 9 : ą, ć, ę, ł, ń, ó, ś, ż, ź, w j. angielskim dojść mogą jeszcze inne znaki, np. "`".
    Pzdr, LightI
  • Helpful post
    Level 21  
    jeśli idzie o rekurencję.....
    Z tego, co zwróciłem uwagę w przykładzie, który wkleiłeś, ktoś zapomniał o wywoływaniu rekurencji. (w opisie do przykładu o tym jest).
    metodyka jest taka (opis ogólnikowy):
    wywołujesz procedurę dla całego wyrazu.
    procedura wykonuje jakąś akcję dla pierwszego znaku, obcina pierwszą literę z wyrazu (bo dla niej już została wykonana akcja).
    Jeżeli zostały jeszcze jakieś znaki - wywołuje sama siebie z wyrazem pozbawionym pierwszego znaku.
    Jeżeli to jest ostatni znak - wykonuje akcję przewidzianą dla ostatniego znaku .


    Napisałem programik (w załączniku bo zrobił się z komentarzami dość długi). (Nie zrobiłem tego w czynie społecznym, przyda mi się w pewnym projekcie)

    Kilka uwag:
    Taka struktura słownikowa nie daje kompresji danych, nie jest też łatwa do przechowywania w pliku. Daje za to bardzo szybkie wyszukiwanie pod warunkiem, że cały słownik uda się nam załadować do pamięci. (lub uda się go odpowiednio podzielić na części)

    Utworzenie każdego indeksu (dopisanie litery) wymaga utworzenia nowego obiektu klasy slownik (oszczędza się gdy jest dużo wyrazów o takich samych początkach, wtedy tworzy się tylko tyle obiektów iloma znakami się różnią)
    Jeden obiekt klasy, którą napisałem zajmuje 124 bajty (po skompilowaniu kompilatorem mingw na którym bazuje devcpp) plus ewentualnie tyle bajtów ile zajmie string ze słowem w języku na którym tłumaczymy.

    Testy praktyczne.....

    Do struktury wczytałem plik na którym bardzo często pracuję a z pewnych wzgledow nie mozna go wrzucić do systemu typu baza danych.
    Plik w pierwszym polu zawiera dziewięciocyfrowy numer. (z tego wzgledu mozna bylo ograniczyc SIZE do 10 dzieki czemu rozmiar elementu skurczył się do 44 bajtów) takich numerów jest kilkaset tysięcy, przy czym wszystkie mają jednakowe dwie pierwsze cyfry. Plik ma łącznie 6 MB, po wczytaniu go do struktury słownikowej program pochłonął w systemie 50 MB.

    Aby zaoszczędzić pamięć - sugerowałbym zastąpienie tablicy
    slownik * t;
    kontenerem (myślę że typu set byłby dobry) (wtedy pamięć przydzielana byłaby w zależności od tego ile jest elementów indeksowanych przez dany element). (nie chce mi się tłumaczyć jak to zrobić, ale nie jest to trudne a dobrze się jest tego nauczyć jeśli się chce poważniej programować)
  • Level 29  
    Miałem kłopot zrozumieć z oryginalnego postu o co chodzi ale..., ale strasznie mi się spodobała ta struktura, bawiłem się z tym trochę, zabawne że nie miałem kłopotu z „dodaj” i „wypisz” a miałem ze „znajdz”. (Ciekawe czy to jakoś nie wynika z „ducha” języka, jutro otrzeźwieję to sprawdzę ;) ).
    W sumie po dodaniu wskaźnika do słownika „nadrzędnego”, odtworzyć mogę słowo wspinając się aż do napotkania nil’a (czy null’a w C) (mogę bez tego ale koszty rosną).
    Zamiast dodawać string z tłumaczeniem dodajmy wskaźnik, bo słownik, czyli i w te i we wte, czemu nie - „dodaj (s1, s2)” zastąpić przez „p=dodaj(s1, s2); q=dodaj(s2,s1); p->znacz=q; q->znacz=p” (jeśli trzeba uzupełnione o boolowską flagę w którą stronę).
    W jednym bycie i z jedną mechaniką mamy maszynerię w obie strony. Podoba mi się, że w ten sposób, w ogóle nie ma śladu po słowach, wszystko zaklęte jest w strukturze (zrobiłem parę rzeczy w których całość zaklęta została w plikach indeksowych, tzw. „D”anych nie trzeba było).
    Index i deindex to w sumie makra w C, mój kawałek programu w Pascalu wygląda tak:
    Code:
    const
    
    maxznak=#34;
        alfabet:array[#0..maxZnak] of char='aąbcćdeęfghijklłmnńoópqrstuvwxyzźż '; {spacja na końcu}
    var   xlat:array[#0..#255] of char;

    procedure mkxlat;
    var i:char;
    begin
    . fillchar(xlat, sizeof(xlat), char(maxZnak)); {zaciera całą tablicę maxZnakiem}
    . for i:=#0 to maxZnak do
    . . xlat[alfabet[i]]:=i;
    end;

    function index(c:char):char;
    begin    index:=xlat[c]; end;

    function deindex(c:char):char;
    begin    deindex:=alfabet[c] end;

    Wygodniej „mkxlat” zawołać raz na „dzieńdobry” niż końbinować z wyliczankami.

    Tu mój kawałek słownika (zachowuje się dobrze):
    'slaughterhouse', 'rzeźnia'
    'butchery','mord'
    'abattoir','rzeźnia'
    'dupa','dupa'
    'ass','dupa'
    :) To D... to nasza tylna część ciała na "D" i 4 litery.
    Swoją drogą słowo które można znaleźć w słownikach a Elektroda udaje świętą.
    Podobało mi się, ale jako rozwiązanie słownika Lang/Jęz to tego nie widzę.
    (maxZnak=34, czyli człość (34+1)*4+2*4=148, tablica + dwa wskaźniki <nadrzędny> i <tłumaczenie>)
  • Level 21  
    >W sumie po dodaniu wskaźnika do słownika „nadrzędnego”, odtworzyć >mogę słowo wspinając się aż do napotkania nil’a"

    Albo: aż znajdziemy wszystkie litery szukanego znaku a będzie pod danym adresem zapisane tłumaczenie.
    W każdym razie zgodzę się że znacznik jest niepotrzebny.

    >Zamiast dodawać string z tłumaczeniem dodajmy wskaźnik,

    Istotnie tego nie "zoptymalizowałem".
    Przy czym (nie jestem pewien) tego typu stringi w c++ gdy są niezainicjalizowane zajmują tyle co wskaźnik. Przy podstawieniu wartości przyda się jednak wymusić na kompilatorze żeby nie rezerwował dla niego więcej bajtów niż jest potrzebne.
    bodajże:
    nazwa_stringa.reserve(ile_trzeba);


    >bo słownik, czyli i w te i we wte, czemu nie - „dodaj (s1, s2)” zastąpić >przez „p=dodaj(s1, s2); q=dodaj(s2,s1); p->znacz=q; q->znacz=p” >(jeśli trzeba uzupełnione o boolowską flagę w którą stronę).

    kwestia notacji.
    p-> odwołuje się do obiektu, który już istnieje
    p= powinno raczej podstawiać wartość zastepujac starą; powinno raczej tworzyć nowy wskaźnik lub obiekt;

    Słownik w dwie strony oparłbym raczej o dwie (bazowe) struktury slownika.
    Albo o zmodyfikowaną strukturę zawierającą wskaźnik do tłumaczenia na jeden i na drugi język.
    Trzebaby też stworzyć dwie funkcje indeksowania dla jednego i drugiego języka albo funkcję indeksującą oba języki.
    Zwłaszcza to drugie rozwiązanie dałoby sporą oszczędność pamięci (wykorzystałoby w jednym języku wszystkie zaindeksowane wyrazy o wspólnym początku z wyrazami drugiego języka; funkcja tlumaczaca musiałaby tylko wiedzieć z ktorego na ktory jezyk tłumaczy, żeby nie było problemów z wyrazami które w jednym i drugim języku pisze się tak samo a znaczą co innego (np: Pl/Eng "do" "to" "but" )


    >char='aąbcćdeęfghijklłmnńoópqrstuvwxyzźż '; {spacja na końcu}

    Jakie to proste a sam na to nie wpadłem.....
    Zamiast do wyliczenia indeksu używać dziesiątki warunków typu if
    można zrobić tablicę gdzie pod numerem elementu odpowiadającemu numerowi znaku w ascii będzie odpowiadający mu indeks;
    w c/c++ będzie to wyglądało tak:
    char tablica_indeksow[]={kolejne wartości rozdzielane przecinkami};
    indeks=tablica_indeksow[szukany_znak];



    >Podobało mi się, ale jako rozwiązanie słownika Lang/Jęz to tego nie widzę.
    >(maxZnak=34, czyli człość (34+1)*4+2*4=148, tablica + dwa wskaźniki ><nadrzędny> i <tłumaczenie>)

    Można zrobić tak:
    niech element zawiera:

    char numer_indeksu;
    wskaźnik_do_elementu_o_nastepnym_numerze_indeksu;
    wskaźnik_do_indeksowanego_elementu;
    wskaźnik_do_stringa slowo_tlumaczone_na_jeden_jezyk;
    (opcjonalnie)wskaźnik_do_stringa slowo_tlumaczone_na_drugi_jezyk;

    rozpoczynamy szukanie:
    w elemence od którego zaczynamy szukać sprawdzamy numer indeksu
    1. jeżeli jest to numer szukany idziemy pod wskaźnik_do_indeksowanego_elementu; (przesunęliśmy się na następny poziom);
    2. jeżeli wskaźnik_do_elementu_o_nastepnym_numerze_indeksu jest pusty a nie jest to ostatni szukany znak znaczy że nie znaleźliśmy słowa
    3. jeżeli wtedy jest to ostatni szukany znak: pobieramy odpowiednie tłumaczenie
    jeżeli ani 1 ani 2 ani 3: idziemy do elementu wskaźnik_do_elementu_o_nastepnym_numerze_indeksu;
    sprawdzamy numer indeksu i powtarzamy dalej od 1 aż zostanie spełniony warunek 2 lub 3

    Procedury dopisywania, wyszukiwania itd się nieco skomplikują i wydłużą czas wykonywania (to drugie praktycznie bez znaczenia jeżeli nie chcemy tłumaczyć wszystkich_książek_świata) ale za to element zmaleje do jakichś 17 bajtów.

    Jeszcze jedno....
    Z ciekawości zrobiłem badanie na żywym słowniku.
    jest taki słownik:
    http://www.kurnik.pl/slownik/growy/
    zawiera on wyrazy z języka polskiego do sprawdzania poprawności w grze typu scrabble. Polski język ma to do siebie że tworzy makabryczne ilości końcówek, odmian itd. W rezultacie slownik zawiera ponad 2 500 000 (dwa i pół miliona!!!!) linii. (i znalazłem wertując bardzo niewiele wyrazów które o ile ich nie znałem wyglądały mi na całkiem zmyślone)

    Po wczytaniu pierwszych (około) 165 tysięcy linii (okolice wyrazu "czop") program zajął w pamięci ponad 35 MB. (zamiast angielskiego tłumaczenia dawałem przypadkowe cztery litery). Rozmiar jest i tak zaniżony - zaoszczędziłem pozbawiając tekst polskich znaków;
    Przy próbie wczytania całego słownika program zdechł.
  • Level 29  
    Nie zrozumieliśmy się, „...p=dodaj(s1, s2); q=dodaj(s2,s1); p->znacz=q; q->znacz=p...” a dokładniej:
    Code:
       p:=dodaj(s1);
    
       q:=dodaj(s2);
       p^.znaczenie:=q;
       q^.znaczenie:=p;
    (* „p” i „q” są wskaźnikami na słownik *)

    to właśnie operacja dodania słowa (s1) i jego tłumaczenia (s2) do słownika, w słowniku nie przechowuję napisów. W jednym słowniku „przechowuję” słowa z obu języków i z tej przyczyny wspomniałem o ewentualnej fladze. Tłumaczenie buduję wspinając się w górę drzewa. Dodałem dla każdego wcielenia słownika literę której odpowiada. Nie konieczne, ale ...
    Razem:
    Code:
    type
    
       pSlownik = ^tSlownik;
       tSlownik = record
          t:array[#0..maxZnak] of pSlownik;
          v: char;
          up, tlumaczenie: pSlownik;
       end;



    Aż nie mogłem się powstrzymać, żeby o czymś nie powiedzieć ;-).
    Słownik – czyli szybkie wyszukiwanie, bardzo dobrze sprawuje się mieszanie z odpowiednio dobraną funkcją hash’ującą. Ale... Jeżeli na końcu poszukiwanego słowa damy „*” (bardzo czasem pożądana możliwość) mieszanie odpada, za to na drzewach rozwiązuje się to łatwo i tanio. Ale... Co ze znakiem „?” nie na końcu słowa? Drzewa więdną ;). A tu? Właśnie!
    Znacie inny sposób na pytajnik? Albo jeszcze chyba trudniejsze (kosztowniejsze) – gwiazdkę w słowie.

    P.S.
    - W moim alfabecie brakowało literki „Ś”.
    - Dodałem jeszcze drugi alfabet – z wielkimi literami, nim też napełniam „xlat” – dzięki temu „Ą” = „ą”.
    - Użycie rekurencji w „wypisz” jak najbardziej OK. ale w „znajdz” i „dodaj” jest jakieś wymuszone. Chyba, że „znajdz” uwzględnia wildcard’s.
    - Pobadam ten słownik z kurnika.
  • Level 22  
    Dziękuję, wskazówki bardzo sie przydały. Problem polega na razie na tym, że kompilator pod Unixem nie bardzo obługuje klasy i w ogóle składnię c++. Jak na razie sobie jednak radzę i jakoś coś napisałem. Używam struktur. Problem mam z tym, że nie ma tam "new" i "delete". Jakoś z "new" sobie poradziłem, ale nie mam pomysłu na "delete". A może rekurencyjne wpisywanie NULL tam, gdzie go jeszcze nie ma?

    Zastanawiam się też co się bardziej opłaca? Dwie struktury dla słów polskich i angielskich z wskaźnikami na drugą strukturę. czy może jedna struktura, która musiałaby mieć dwa wskaźniki z czego ten drugi w 95% przypadków nie byłby potrzebny...

    Mam też dwa pytania. Jak miałby wyglądać ten wskaźnik na drugie słowo. Pewnie wskazuje on na miejsce, gdzie kończy się to słowo. I wtedy wczytywać w górę... No więc: co i w jaki sposób trzeba przypisać temu wskaźnikowi żeby wskazywał na odpowienie miejscu i jak się czyta w górę?
  • Level 29  
    Kafka
    -Pisałem w Pascalu, nie obiektowo więc też struktury. Pamięć dla struktury przydzieli Ci „malloc”. Samo wstawienie NULL’a nie daje nic, nie pamiętam co w C jest odwrotnością „malloc” coś z free w nazwie, ale ze zwalnianiem tego jest kłopot, przy wielkim słowniku jest to najbardziej czasochłonna operacja, bo pamięć zwalniamy w innej kolejności niż ją rezerwowaliśmy, a przy wirtualnej pamięci oj oj oj.
    -ja zrobiłem tak że słowa jednego i drugiego języka znajdują się w jednej strukturze, ma to istotną wadę, bo występują słowa w obu językach tak samo pisane np. „do”.
    Budowanie osobnych drzew będzie strasznym marnotrawstwem pamięci, chyba (jeszcze to przemyślę) umieszczenie w strukturze dwu wskaźników (na tłumaczenia i polskie i angielskie) załatwia sprawę doskonale i wymaga tylko kosmetyki w „znajdz”. W zasadzie to powinien być wskaźniki na listę tłumaczeń, ale to będzie kosztowało furę pamięci. I tu temat do dalszych studiów (mam pewnego pomysła ale muszę go jeszcze przemyśleć).
    -każde słowo to właśnie nasza elementarna struktura + oczywiście powiązanie jej z resztą, tak jak myślisz - wskaźnik na słowo to wskaźnik na odpowiednią strukturę (ileż synonimów: słownik, struktura (w pascalu rekord), liść, litera)
    Operację „dodaj(słowo)” rozumiesz, u mnie jest ona funkcją zwracającą wskaźnik na ostatnią zaalokowaną strukturę (liść drzewa odpowiadający temu słowu, czy też ostatniej literze tego słowa). Zobacz pierwszy kawałek kodu w poprzednim poście, dwa razy wołam „dodaj” (dla słowa i jego tłumaczenia) i każdemu przekazuję wskaźnik na jego odpowiednika.
    By piąć się w górę (czyli do korzenia) musimy mieć wskaźnik na poprzednią literę słowa (u mnie „up”) „dodaj” kiedy trzeba tworzy nową strukturę i umieszcza w niej wskaźnik na siebie( if (p->t[i]==NULL) {p->t[i]=slowniknew(); p->t[i]->up=p} ) (robię błędy w C, ale chyba można to zrozumieć). Funkcja ma wskaźnik na słowo i w pętli dopóki wskaźnik <> NULL do wskaźnika wstawia wskaźnik->up. Czyli pętla przeszła przez wszystkie litery słowa, ale jakie to są litery? Ja dodałem do struktury jedną literę, (to może powiększyć strukturę o 16 bajtów lub wcale, dalej piszę dla czego). Inny sposób to przeszukanie tablicy t[] i stwierdzenie który wskaźnik odpowiada następnej literze słowa.
    Bielski
    Dziewięcio cyfrowy numer to nie 10 bajtów tylko 4 ;)
    Przy czytaniu całości piszesz „zdechł”, a przeczytał?

    Przeczytałem plik z Kurnika.
    Budowałem słownik „polsko/polski” to znaczy tłumaczenie wskazywało na siebie.
    Rozmiar struktury to 36*4+2*4+1=153, a tak naprawdę to 160 bo dystrybutor pamięci przydziela kawałkami o rozmiarze zaokrąglonym w górę do krotności 16 bajtów (przypominam używam FreePascala, ale inni zwykle robią podobnie). Warto to wiedzieć, bo dzięki temu nie szkoda miejsca na jakieś dodatkowe drobiazgi.
    Koszmarnie było kiedy próbowałem zwracać pamięć „po bożemu”, to trwało najdłużej, więc zrezygnowałem (pozostawiłem to kompilatorowi).
    W programie były włączone wszelkie możliwe kontrole (stos, indeksy itp.) wyłączenie pewnie poprawiło by osiągi.
    Mam XP, 1GHz i 256MB fizycznej pamięci.
    Podsumowanie: przeczytałem 2 547 410 słów, 28 606 294 liter, 33 701 114 bajtów, powstało 4 038 117 liści, na łączną kwotę 646 098 720 bajtów (fiu fiu gdybym ja miał kiedyś tyle RAMu ;-) kiedy mega kosztowało milion zł), a to wszystko w czasie 167,6 sekundy. Dołączyłem podsumowanie co 100 tys. słów.
    Średnio na słowo przypada 253,63 bajta, myślałem że będzie gorzej.
    100 tys. razy zawołałem „znajdz('abecedariuszowi')”, zajęło to 0,20 sekundy.
  • Level 21  
    >
    Pamięć dla struktury przydzieli Ci „malloc”. Samo wstawienie NULL’a nie daje nic, nie pamiętam co w C jest odwrotnością „malloc” coś z free w nazwie, ale ze zwalnianiem tego jest kłopot, przy wielkim słowniku jest to najbardziej czasochłonna operacja, bo pamięć zwalniamy w innej kolejności niż ją rezerwowaliśmy,

    Pisałem w C++ nie w C (pojawia się tu sporo elementów spoza "części wspólnej" języków), tutaj tworzymy obiekt wywołaniem new, kasujemy delete nie troszcząc się o przydział pamięci; dodatkowo w tym przykładzie jest wrzucona funkcja destruktora kasująca obiekty utworzone przez obiekt zanim sam obiekt pójdzie się (...) w ten sposób nie trzeba się martwić o wyczyszczenie pamięci. (w C istotnie trzeba się posługiwać malloc/free, w C++ można. Ale rzadko trzeba)

    >
    W zasadzie to powinien być wskaźniki na listę tłumaczeń, ale to będzie kosztowało furę pamięci. I tu temat do dalszych studiów (mam pewnego pomysła ale muszę go jeszcze przemyśleć).

    Niekoniecznie dużo pamięco. W sumie niegłupi pomysł. W wypadku tłumaczenia z polskiego na angielski może nawet zaoszczędzić pamięć.

    >
    Dziewięcio cyfrowy numer to nie 10 bajtów tylko 4 ;)

    Och, specyfika tego pliku jest taka, że wystarczy trzy bajty. Niestety, Tajemnicza Aparatura generuje co rano nowy w formie pliku tekstowego.

    >
    Przy czytaniu całości piszesz „zdechł”, a przeczytał?

    Przypomniało mi się, że kompletny słownik testowałem bez wycięcia polskich znaków (miałem problemy ze stroną kodową i z zaindeksowaniem polskich znaków)
    Puściłem to dzisiaj jeszcze raz, przeszło. Słownik wczytał się w ciągu 48 sekund (nie wiem jaki jest szybki procek w tym kompie), wyniki jeśli idzie o pamięć podobne (nieco poniżej 500 mb, ale bez polskich znaków i z krótszym tłumaczeniem). Kompilator poradził sobie z korzystaniem z pamięci wirtualnej - w kompie mam 256 MB fizycznej.
  • Level 29  
    Bielski
    Też miałem kłopot stronowo-kodowy.
    Myślałem że może to że listę mamy posortowaną powoduję że czytanie Kurnika jest takie prędkie, postanowiłem to sprawdzić, po zbudowaniu słownika, jeszcze raz przeczytałem listę słów (słowa mają max 15 liter) i dla każdego z tych 2G5 słów sprawdziłem czy w słowniku nie znajduje się to słowo pisane od końca, tu już skaczemy po całości w sposób przypadkowy, znalazłem 1213 takich słów (część z nich jest palindromami). Okazało się, że wystarczyło na to dwie minuty, czas podobny do czasu potrzebnego na budowę słownika. Nie spodziewałem się takiego wyniku.
    Zwróciłeś uwagę na to co pisałem wcześniej o znaku zapytania (przemalowałem to na czerwono)? Mażesz coś o tym powiedzieć?
  • Level 29  
    Kafka
    Czy masz jakiś słownik którym masz zamiar napełnić tą maszynerię? Może podeślij lub daj link, przydało by się coś z czym można by potrenować.
    Wiesz przeczytałem te słowne opisy algorytmów, mam nadzieję że szczyptę mogło to pomóc, choć brzmi trochę jak bełkot ;-)
    Popatrzyłem na „palindromy” które znalazłem w Kurniku:
    aktyw wytka
    motam matom
    łaps spał
    ułudom modułu
    uroda odoru
    metraż żartem
    żartem ukaż żaku metraż
    monotyp rad pytonom
    żółw onoż mors
  • Level 22  
    Nie nie mam przykładowego słownika. Testować chciałem na tym z kurnika, tyle, że pod Unixem nie ma polskich znaków... Sam napiszę kilka słów, pokażę jak co działa i jakos przejdzie...
  • Level 29  
    Z tym angielskim słownikiem skojarzony był indeks, dwuwymiarowa tablica, kolumny indeksuje pierwsza litera szukanego słowa, wiersze druga, a w tablicy jest pozycja w pliku od jakiej zaczynają się słowa na te dwie litery (pewne pozycje zawierają –1). W angielskim (i tak małym) działa fajnie, najliczniejsza grupa „CO*” to 997 słów i tylko 8631 liter, czyli z dwu pierwszych liter szukanego słowa, poprzez tablicę indeksu trafiamy w odpowiednie miejsce słownika, czytamy całkiem małą porcyjkę (tu np. 8631+2*997 jeżeli słowa rozdzielone są znakami CR LF) a dalej przeszukujemy „porcyjkę” i wiemy czy słowo jest w słowniku czy nie. Można by do słowa dodać wskaźnik na tłumaczenie (porcyjka lekko urośnie) ale....
    Dla polskiego „kurnikiwego” metoda jest słaba, np.
    „NI*” to 6.285.212 liter w 479.952 słowach, „PO*” to 2.206.143 w 190.447,
    nie wiele lepiej przy grupach trzyliterowych, „NIE*” 6.244.547 w 475.956, „PRZ*” 1.211.582 w 97.251 słowach.
    Czteroliterowe to 24.207 grup, „NIEP*” 969.972 w 71.661 słowach, „PRZE*” 728.026 w 58.026. Pięcioliterowe to ponad 64k grup, i dalej słabo np. „NIEPO*” 509.226 liter w 37.420 słowach.
  • Level 29  
    Ciekawym co tam nowego w strukturach słownikowych ;-)
    Sprawdziłem wariant naiwny. Czy ja wiem czy naiwny bo...
    Tablica 2.600.000 string’ów (około 40MB bo słowa mają do 15 liter, drzewo miało ponad pół giga), wczytałem do niej kurnik (3 sek.) i po kolei szukałem czy słowo występuje w tablicy.
    Przeszukiwanie liniowe z wartownikiem
    . słów. - .sekund
    10 000 – 5
    20 000 –21
    30 000 – 46
    40 000 – 82
    50 000 – 128 (mniej więcej tyle trwało znalezienie wszystkich „odwrotników” w drzewie)
    60 000 – 183
    .......
    2 547 410 - ? pi razy oko trzy dni i osiemnaście godzin ;-)
    ładnie widać jak czas kwadratowo rośnie. Ale tak było kiedy szukałem od początku tablicy, kiedy szukałem od końca 100 (sto) sprawdzeń zajmowało 25 sekund!

    Bisekcja (tablica jest posortowana) - sprawdzenie całego słownika trwało 12 sek., szukanie „odwrotników” 15 sek. Ten sposób nadaje się też do szukania po dysku (log(kurnik)=22), choć zgrabniej by było usypać ze słownika kopiec - wstawianie i usuwanie potanieje.

    3,75 dnia w porównaniu do 15 sekund - różnica między kwadratem a logarytmem ;-)

    Jeżeli mamy słownik ang=>pol to wcale nie znaczy, że mamy słownik pol=>ang, czy tezaurusy, no mamy ale straaaaasznie kulawe.