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-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.

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:
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 6 razy

Publikacje, które mogą cię zainteresować

Meta Tagi