Wyszukiwarka
Abstrakt
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.
Cytowania
-
3
CrossRef
-
0
Web of Science
-
7
Scopus
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.tcs.2012.04.023
- Licencja
- Copyright (2012 Elsevier B.V)
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
THEORETICAL COMPUTER SCIENCE
nr 450,
strony 10 - 21,
ISSN: 0304-3975 - Język:
- angielski
- Rok wydania:
- 2012
- Opis bibliograficzny:
- Daciuk J., Weiss D.: Smaller representation of finite state automata// THEORETICAL COMPUTER SCIENCE. -Vol. 450, (2012), s.10-21
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.tcs.2012.04.023
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 177 razy