Search
Abstract
This paper is a follow-up to Jan Daciuk's experiments on space-efficient finite state automata representation that can be used directly for traversals in main memory (Daciuk, 2000)[4]. We investigate several techniques for 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 size 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 (Ristov and Laporte, 1999)[15] method, but remains memory and CPU efficient during construction.Ten artykuł nawiązuje do doświadczeń Jana Daciuka dotyczących reprezentacji automatów skończonych, która może być użyta bezpośrednio w pamięci operacyjnej (Daciuk, 2000)[4]. Badamy kilka sposobów obniżenia zajętości pamięci automatów minimalnych głównie wykorzystując fakt, że etykiety przejść i przesunięcia wskaźników do stanów docelowych przejść nie są równomiernie rozłożone i poddają się kompresji. Osiągamy zmniejszenie pamięci o 20-30% w porównaniu z oryginalną reprezentacją przedstawioną w [4]. Ten wynik jest porównywalny z najlepszym obecnie sposobem kompresji słowników jak LZ-trie (Ristov i Laporte, 1999)[15], ale pozostaje oszczędny w użyciu pamięci i czasu procesora w czasie budowy słownika.
Citations
-
3
CrossRef
-
0
Web of Science
-
7
Scopus
Cite as
Full text
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.tcs.2012.04.023
- License
- Copyright (2012 Elsevier B.V)
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
THEORETICAL COMPUTER SCIENCE
no. 450,
pages 10 - 21,
ISSN: 0304-3975 - Language:
- English
- Publication year:
- 2012
- Bibliographic description:
- Daciuk J., Weiss D.: Smaller representation of finite state automata// THEORETICAL COMPUTER SCIENCE. -Vol. 450, (2012), s.10-21
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.tcs.2012.04.023
- Verified by:
- Gdańsk University of Technology
seen 122 times