Search
Abstract
This paper is a follow-up to Jan Daciuk's experiments on space-effcient finite state automata representation that can be used directly for traversals in main memory. We investigate several techniques of reducing memory footprint of minimal automata, mainly exploiting the fact that transition labels and transition pointer offset values are not evenly distributed and so are suitable for compression. We achieve a gain of around 20-30% compared to the original representation given in [4]. This result is comparable to the state-of-the-art dictionary compression techniques like the LZ-trie [10] method, but remains memory and CPU efficient during construction.Ten artykuł jest uzupełnieniem doświadczeń Jana Daciuka z oszczędną pamięciowo reprezentacją automatów skończonych, która może być być bezpośrednio użyta w pamięci głównej komputera. Badamy kilka technik zmniejszania zajętości pamięci automatów minimalnych, głównie wykorzystując fakt, że etykiety przejść i wartości przesunięcia odnośników przejść nie są równomiernie rozłożone, a więc nadają się do kompresji. Otrzymaliśmy zmniejszenie rozmiaru o około 20-30% w stosunku do oryginalnej reprezentacji podanej w [4]. Ten wynik jest porównywalny z najlepszymi technikami kompresji, takimi jak metoda LZ-trie [10], ale jest wydajna pamięciowo i czasowo w trakcie tworzenia.
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Articles
- Type:
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Published in:
-
LECTURE NOTES IN COMPUTER SCIENCE
no. 6807,
pages 118 - 129,
ISSN: 0302-9743 - Language:
- English
- Publication year:
- 2011
- Bibliographic description:
- Daciuk J., Weiss D.: Smaller Representation of Finite State Automata// LECTURE NOTES IN COMPUTER SCIENCE. -Vol. 6807., (2011), s.118-129
- Verified by:
- Gdańsk University of Technology
seen 137 times
Recommended for you
Incremental and Semi-Incremental Construction of Pseudo-Minimal Automata
- J. Daciuk,
- D. Maurel,
- A. Savary