Daniel Janus <p...@n...korpus.pl> napisał(a):

> Dnia 16.08.2009 Marcin Połeć <u...@g...pl> napisał/a:
>
> > Witam,
> >
> > mam problem z wyszukiwaniem w słowniku. Gdy wyszukuję jednego klucza
> > wszystko jest ok, tzn. bardzo szybko. Problem pojawia się w momencie gdy
> > chcę sprawdzić powiedzmy milion kluczy. Mój program generuje najpierw
listę
> > kombinacji liter a następnie sprawdza w słowniku które z tych kombinacji
się
> > tam znajdują. Samo generowanie listy zabiera góra do 2-3 sekund,
natomiast
> > sprawdzanie które z tych kombinacji są w słowniku - od 20s do kilku
minut.
>
> Nie znam .Net, ale to wygląda na przypadek, w którym warto użyć
> specjalizowanej struktury danych. Google: "directed acyclic word
> graphs"; patrz też: Marcin G. Ciura, Sebastian Deorowicz, "How to
> squeeze a lexicon", Software--Practice and Experience 2001;
> 31(11):1077-1090.
>

tak to jest bardzo dobry trop!!! Problemem jest znalezienie gotowego
algorytmu na DAWG (tzn. są dostępne ale nie na polskie litery). Jest też
jeszcze szybsza wersja niż DAWG zwana GADDAC, no i wyczytałem że został
opracowany jeszcze szybszy algorytm od GADDACa oparty na DAWGU który nazywa
się optimal DAWG czy jakoś tak :)

--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/