Dnia 19.08.2009 Marcin Połeć <u...@g...pl> napisał/a:

> tak to jest bardzo dobry trop!!! Problemem jest znalezienie gotowego
> algorytmu na DAWG (tzn. są dostępne ale nie na polskie litery).

E tam, wydaje mi się, że powinny działać z dowolnymi znakami. Poza tym
idea jest na tyle prosta, że łatwo machnąć implementację w jeden
wieczór. Moja implementacja deserializatora i trawersera DAWG-ów w
Clojure zajmuje jakieś trzydzieści linii kodu.

> 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 :)

Zależy do czego. Jeśli potrzebujesz tylko sprawdzać, czy napis jest w
słowniku, to DAWG-i wystarczają w zupełności (oczywiście, najlepiej
optymalne w sensie liczby węzłów -- patrz wspominany przeze mnie
artykuł). GADDAG przydaje się, gdy chcesz pracować z podnapisami
niekoniecznie zaczynającymi się na początku napisu ze słownika.

--
Daniel 'Nathell' Janus, m...@n...korpus.pl, http://danieljanus.pl
- Proč má člověk mlčet?
- Aby slyšel melodie lidí kolem sebe.
[Rok diabła]