Publications Repository - Gdańsk University of Technology

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.

Authors

• dr hab. inż. Jan Daciuk link open in new tab ,
• Dawid Weiss