Elektroda.pl
Elektroda.pl
X
Proszę, dodaj wyjątek www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

[C] Szukanie w słowniku - jakis pomysł?

mihau87 08 Lis 2010 17:34 738 4
  • #1 08 Lis 2010 17:34
    mihau87
    Poziom 11  

    Witam
    Piszę program który będzie szukał słowa w słowniku i mowil czy takie słowo istnieje czy tez nie.

    Jak najlepiej to zrobic? Na samym poczatku wczytywać plik(30MB) do tablicy czy mozna jakos szybciej to zrobic?

    0 4
  • #3 10 Lis 2010 10:13
    redie
    Poziom 15  

    Nie wiem czy są jakieś łatwo dostępne biblioteki, ale jeśli masz ochotę samemu się za to zabrać to możesz wczytać sobie cały ten słownik do tablicy i ją posortować. Aby przyspieszyć wyszukiwanie w dużej tablicy możesz sobie skakać najpierw co 100 indeksów i jak trafisz na wyraz który "jest większy" od szukanego to wystarczy się cofać co 10 indeksów aż trafisz na słowo które jest "mniejsze" od szukanego to wtedy wystarczy szukać do przodu już po 1 indeksie aż się trafi na dane słowo. Dzięki temu jeśli masz np. 10000 wyrazów to znalezienie wyrazu na literę "z" nie będzie zajmowało tych 10000 instrukcji if lecz jakieś 100 razy mniej.

    Możesz ewentualnie stworzyć sobie dodatkową tablicę z literami które będą miały indeksy z tego słownika w których zaczyna się dana litera, np. że wyrazy na literę "w" zaczynają się od indeksu 9000.

    Wydaje mi się że mimo wszystko słownik trzeba wczytać do pamięci bo operacje dyskowe będą znacznie wolniejsze.

    Do sortowanie dużych słowników użyj QuickSort i najlepiej jakbyś podczas sortowanie nie zamieniał całych ciągów tekstu: z jednego na drugi lecz jakbyś miał wskaźniki na te ciągi i jedynie zmieniał położenie tych wskaźników w tabeli. Ale to wymaga byś miał tabelę wskaźników na ciągi tekstowe a nie tabelę ciągów tekstowych.

    0
  • #4 13 Lis 2010 21:31
    hex0
    Poziom 11  

    Cytat:
    Możesz ewentualnie stworzyć sobie dodatkową tablicę z literami które będą miały indeksy z tego słownika w których zaczyna się dana litera, np. że wyrazy na literę "w" zaczynają się od indeksu 9000.


    A może zamiast indeksować cały słownik, 'pociąć' go na osobne pliki umieszczając wyrazy zaczynające się na konkretną literę w osobnych plikach. Przy szukaniu wczytać z danego pliku do tablicy tylko wyrazy zgadzające się ilością znaków.

    To powinno być całkiem wydajne :)

    0
  • #5 16 Lis 2010 11:13
    serpent
    Poziom 11  

    Możesz z posiadanego słownika stworzyć bazę danych używając biblioteki SQLite. Biblioteka załatwi za ciebie wstawianie, sortowanie i wyszukiwanie słów.

    0