We present an algorithm that computes a function that assigns consecutive integers to trees recognized by a deterministic, acyclic, finite-state, bottom-up tree automaton. Such function is called minimal perfect hashing. It can be used to identify trees recognized by the automaton. Its value may be seen as an index in some other data structures. We also present an algorithm for inverted hashing.Przedstawiamy algorytm, który oblicza funkcję przypisującą kolejne liczby całkowite do drzew rozpoznawanych przez deterministyczny, acykliczny, skończony, wstępujący automat drzewiasty. Taka funkcja nazywana jest minimalną doskonałą funkcją mieszającą. Może być użyta do identyfikacji drzew rozpoznawanych przez automat. Jej wartość może być postrzegana jako indeks w innych strukturach danych. Przedstawiamy także algorytm obliczania odwrotnej funkcji mieszającej.
Autorzy
Informacje dodatkowe
- Kategoria
- Publikacja monograficzna
- Typ
- rozdział, artykuł w książce - dziele zbiorowym /podręczniku w języku o zasięgu międzynarodowym
- Język
- angielski
- Rok wydania
- 2008
Źródło danych: MOSTWiedzy.pl - publikacja "Perfect hashing tree automata" link otwiera się w nowej karcie
