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.
Authors
- dr hab. inż. Jan Daciuk link open in new tab ,
- Dawid Weiss
Additional information
- Category
- Publikacja w czasopiśmie
- Type
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Language
- angielski
- Publication year
- 2011
Source: MOSTWiedzy.pl - publication "Smaller Representation of Finite State Automata" link open in new tab
