A perfect hashing incremental scheme for unranked trees using pseudo-minimal automata - Publikacja - MOST Wiedzy

Wyszukiwarka

A perfect hashing incremental scheme for unranked trees using pseudo-minimal automata

Abstrakt

We describe a technique that maps unranked trees to arbitrary hash codes using a bottom-up deterministic tree automaton (DTA). In contrast to other hashing techniques based on automata, our procedure builds a pseudo-minimal DTA for this purpose. A pseudo-minimal automaton may be larger than the minimal one accepting the same language but, in turn, it contains proper elements (states or transitions that are unique) for every input accepted by the automaton. Therefore, pseudo-minimal DTA are a suitable structure to implement stable hashing schemes, that is, schemes where the output for every key can be determined prior to the automaton construction. We provide incremental procedures to build the pseudo-minimal DTA and the mapping that associates an integer value to every transition that will be used to compute the hash codes. This incremental construction allows for the incorporation of new trees and their hash codes without the need to rebuild the whole DTA from scratch.Opisujemy technikę, która odwzorowuje drzewa z wierzchołkami o nieustalonej krotności na dowolne wartości funkcji mieszającej z użyciem wstępującego, deterministycznego automatu drzewiastego (DTA). W odróżnieniu od innych realizacji funkcji mieszającej opartych o automaty, nasza procedura tworzy w tym celu automat pseudominimalny. Automat pseudominimalny może być większy niż automat minimalny rozpoznający ten sam język, ale zawiera elementy własne (unikatowe stany lub przejścia) dla każdego elementu weujściowego rozpoznawanego przez automat. Dlatego pseudominimalne DTA są właściwymi strukturami do realizacji stabilnych schematów mieszania, w których wyjście dla każdego klucza może być określone przed zbudowaniem automatu. Podajemy przyrostową procedurę tworzenia automatu pseudominimalnego i odwzorowania kojarzącego wartość całkowitą z każdym przejściem, które zostanie użyte do obliczenia wartości funkcji mieszającej. Przyrostowe tworzenie automatu pozwala na dodawanie nowych drzew i związanych z nimi wartości funkcji mieszającej bez potrzeby ponownej budowy automatu od początku.

Cytowania

  • 0

    CrossRef

  • 0

    Web of Science

  • 0

    Scopus

Informacje szczegółowe

Kategoria:
Publikacja w czasopiśmie
Typ:
artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:
RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS nr 43, strony 779 - 790,
ISSN: 0988-3754
Język:
angielski
Rok wydania:
2009
Opis bibliograficzny:
Carrasco R., Daciuk J.: A perfect hashing incremental scheme for unranked trees using pseudo-minimal automata// RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS. -Vol. 43, nr. iss. 4, October-December. (2009), s.779-790
DOI:
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1051/ita/2009018
Weryfikacja:
Politechnika Gdańska

wyświetlono 18 razy

Publikacje, które mogą cię zainteresować

Meta Tagi