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

Autorzy (2)