Parsing with suffix and prefix dictionaries

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by M. Cohn Articles by R. Khazan

Data Compression Conference (DCC '96)

Snowbird, UT

March 31-April 03

ISBN: 0-8186-7358-3

	ASCII Text	x
	M. Cohn, R. Khazan, "Parsing with suffix and prefix dictionaries," Data Compression Conference, pp. 180, Data Compression Conference (DCC '96), 1996.

	BibTex	x
	@article{ 10.1109/DCC.1996.488323, author = {M. Cohn and R. Khazan}, title = {Parsing with suffix and prefix dictionaries}, journal ={Data Compression Conference}, volume = {0}, year = {1996}, issn = {1068-0314}, pages = {180}, doi = {http://doi.ieeecomputersociety.org/10.1109/DCC.1996.488323}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Data Compression Conference TI - Parsing with suffix and prefix dictionaries SN - 1068-0314 SP EP A1 - M. Cohn, A1 - R. Khazan, PY - 1996 KW - grammars; data compression; adaptive signal processing; prefix dictionaries; suffix dictionaries; parsing; greedy left to right parsing; greedy right to left parsing; static suffix dictionary; adaptive online method; LZW dictionary VL - 0 JA - Data Compression Conference ER -

M. Cohn, Dept. of Comput. Sci., Brandeis Univ., Waltham, MA, USA

R. Khazan, Dept. of Comput. Sci., Brandeis Univ., Waltham, MA, USA

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/DCC.1996.488323

We show that greedy left-to-right (right-to-left) parsing is optimal w.r.t. a suffix (prefix) dictionary. To exploit this observation, we show how to construct a static suffix dictionary that supports on-line, linear-time optimal parsing. From this we derive an adaptive on-line method that yields compression comparing favorably to LZW.

Index Terms:

grammars; data compression; adaptive signal processing; prefix dictionaries; suffix dictionaries; parsing; greedy left to right parsing; greedy right to left parsing; static suffix dictionary; adaptive online method; LZW dictionary

Citation:

M. Cohn, R. Khazan, "Parsing with suffix and prefix dictionaries," dcc, pp.180, Data Compression Conference (DCC '96), 1996

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.