Automata and graph compression

Mehryar Mohri; Michael Riley; Ananda Theertha Suresh

doi:10.1109/ISIT.2015.7283005

Automata and graph compression

Mehryar Mohri, Michael Riley, Ananda Theertha Suresh

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We present a theoretical framework for the compression of automata, which are widely used representations in speech processing, natural language processing and many other tasks. As a corollary, our framework further covers graph compression. We introduce a probabilistic process of graph and automata generation that is similar to stationary ergodic processes and that covers real-world phenomena. We also introduce a universal compression scheme LZA for this probabilistic model and show that LZA significantly outperforms other compression techniques such as gzip and the UNIX compress command for several synthetic and real data sets.

Original language	English (US)
Title of host publication	Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	2989-2993
Number of pages	5
ISBN (Electronic)	9781467377041
DOIs	https://doi.org/10.1109/ISIT.2015.7283005
State	Published - Sep 28 2015
Event	IEEE International Symposium on Information Theory, ISIT 2015 - Hong Kong, Hong Kong Duration: Jun 14 2015 → Jun 19 2015

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
Volume	2015-June
ISSN (Print)	2157-8095

Other

Other	IEEE International Symposium on Information Theory, ISIT 2015
Country/Territory	Hong Kong
City	Hong Kong
Period	6/14/15 → 6/19/15

Keywords

Lempel-Ziv
graphs
universal compression

ASJC Scopus subject areas

Theoretical Computer Science
Information Systems
Modeling and Simulation
Applied Mathematics

Access to Document

10.1109/ISIT.2015.7283005

Cite this

Mohri, M., Riley, M., & Suresh, A. T. (2015). Automata and graph compression. In Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015 (pp. 2989-2993). Article 7283005 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2015-June). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2015.7283005

Automata and graph compression. / Mohri, Mehryar; Riley, Michael; Suresh, Ananda Theertha.
Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015. Institute of Electrical and Electronics Engineers Inc., 2015. p. 2989-2993 7283005 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2015-June).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Mohri, M, Riley, M & Suresh, AT 2015, Automata and graph compression. in Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015., 7283005, IEEE International Symposium on Information Theory - Proceedings, vol. 2015-June, Institute of Electrical and Electronics Engineers Inc., pp. 2989-2993, IEEE International Symposium on Information Theory, ISIT 2015, Hong Kong, Hong Kong, 6/14/15. https://doi.org/10.1109/ISIT.2015.7283005

@inproceedings{b808a4d596c94c0bbd975e46f88413ac,

title = "Automata and graph compression",

abstract = "We present a theoretical framework for the compression of automata, which are widely used representations in speech processing, natural language processing and many other tasks. As a corollary, our framework further covers graph compression. We introduce a probabilistic process of graph and automata generation that is similar to stationary ergodic processes and that covers real-world phenomena. We also introduce a universal compression scheme LZA for this probabilistic model and show that LZA significantly outperforms other compression techniques such as gzip and the UNIX compress command for several synthetic and real data sets.",

keywords = "Lempel-Ziv, graphs, universal compression",

author = "Mehryar Mohri and Michael Riley and Suresh, {Ananda Theertha}",

note = "Publisher Copyright: {\textcopyright} 2015 IEEE.; IEEE International Symposium on Information Theory, ISIT 2015 ; Conference date: 14-06-2015 Through 19-06-2015",

year = "2015",

month = sep,

day = "28",

doi = "10.1109/ISIT.2015.7283005",

language = "English (US)",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "2989--2993",

booktitle = "Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015",

}

TY - GEN

T1 - Automata and graph compression

AU - Mohri, Mehryar

AU - Riley, Michael

AU - Suresh, Ananda Theertha

PY - 2015/9/28

Y1 - 2015/9/28

N2 - We present a theoretical framework for the compression of automata, which are widely used representations in speech processing, natural language processing and many other tasks. As a corollary, our framework further covers graph compression. We introduce a probabilistic process of graph and automata generation that is similar to stationary ergodic processes and that covers real-world phenomena. We also introduce a universal compression scheme LZA for this probabilistic model and show that LZA significantly outperforms other compression techniques such as gzip and the UNIX compress command for several synthetic and real data sets.

AB - We present a theoretical framework for the compression of automata, which are widely used representations in speech processing, natural language processing and many other tasks. As a corollary, our framework further covers graph compression. We introduce a probabilistic process of graph and automata generation that is similar to stationary ergodic processes and that covers real-world phenomena. We also introduce a universal compression scheme LZA for this probabilistic model and show that LZA significantly outperforms other compression techniques such as gzip and the UNIX compress command for several synthetic and real data sets.

KW - Lempel-Ziv

KW - graphs

KW - universal compression

UR - http://www.scopus.com/inward/record.url?scp=84969795612&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84969795612&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2015.7283005

DO - 10.1109/ISIT.2015.7283005

M3 - Conference contribution

AN - SCOPUS:84969795612

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2989

EP - 2993

BT - Proceedings - 2015 IEEE International Symposium on Information Theory, ISIT 2015

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - IEEE International Symposium on Information Theory, ISIT 2015

Y2 - 14 June 2015 through 19 June 2015

ER -

Automata and graph compression

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this