Dynamic Perfect Hashing with Finite-State Automata
| Autor: | Agata Savary, Jan Daciuk, Denis Maurel |
|---|---|
| Rok vydání: | 2006 |
| Předmět: |
Nested word
Deterministic finite automaton Theoretical computer science Computer science Dynamic perfect hashing Automata theory Quantum finite automata Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) Nondeterministic finite automaton ω-automaton Perfect hash function Computer Science::Formal Languages and Automata Theory |
| Zdroj: | Advances in Soft Computing ISBN: 3540250565 Intelligent Information Systems |
| DOI: | 10.1007/3-540-32392-9_18 |
| Popis: | Minimal perfect hashing provides a mapping between a set of n unique words and n consecutive numbers. When implemented with minimal finite-state automata, the mapping is determined only by the (usually alphabetical) order of words in the set. Addition of new words would change the order of words already in the language of the automaton, changing the whole mapping, and making it useless in many domains. Therefore, we call it static. Dynamic minimal perfect hashing assigns consecutive numbers to consecutive words as they are added to the language of the automaton. Dynamic perfect hashing is important in many domains, including text retrieval and databases. We investigate three methods for its implementation. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|