Wyszukiwarka
Abstrakt
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.
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja monograficzna
- Typ:
- rozdział, artykuł w książce - dziele zbiorowym /podręczniku w języku o zasięgu międzynarodowym
- Tytuł wydania:
- Finite-State Methods and Natural Language Processing strony 97 - 106
- Język:
- angielski
- Rok wydania:
- 2008
- Opis bibliograficzny:
- Daciuk J.: Perfect hashing tree automata// Finite-State Methods and Natural Language Processing/ ed. eds: T. Hanneforth, K.-M. Würzner. Potsdam: Potsdam University Press, 2008, s.97-106
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 124 razy
Publikacje, które mogą cię zainteresować
An implementation of deterministic tree automata minimization
- R. Carrasco,
- J. Daciuk,
- M. Forcada