Smaller representation of finite state automata - Publikacja - MOST Wiedzy

Wyszukiwarka

Smaller representation of finite state automata

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

  • 2

    CrossRef

  • 3

    Web of Science

  • 5

    Scopus

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 19 razy

Publikacje, które mogą cię zainteresować

Meta Tagi