Wyszukiwarka
Abstrakt
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.
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Opublikowano w:
-
LECTURE NOTES IN COMPUTER SCIENCE
nr 6807,
strony 118 - 129,
ISSN: 0302-9743 - Język:
- angielski
- Rok wydania:
- 2011
- Opis bibliograficzny:
- Daciuk J., Weiss D.: Smaller Representation of Finite State Automata// LECTURE NOTES IN COMPUTER SCIENCE. -Vol. 6807., (2011), s.118-129
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 137 razy
Publikacje, które mogą cię zainteresować
Incremental and Semi-Incremental Construction of Pseudo-Minimal Automata
- J. Daciuk,
- D. Maurel,
- A. Savary