Simple linear-time off-line text compression by longest-first substitution

Eyosuke Nakamura, Hideo Bannai, Shunsuke Ineriaga, Masayuki Takeda

研究成果: 書籍/レポート タイプへの寄稿会議への寄与

8 被引用数 (Scopus)

抄録

We consider grammar based text compression with longest first substitution where non-overlapping occurrences of a longest repeating substring of the input text are replaced by a new non-terminal symbol. We present a new text compression algorithm by simplifying the algorithm presented in [4]. We give a new formulation of the correctness proof introducing the sparse lazy suffix tree data structure. We also present another type of longest first substitution strategy that allows better compression. We show results of preliminary experiments comparing grammar sizes of the two versions of the longest first strategy and the most frequent strategy.

本文言語英語
ホスト出版物のタイトルProceedings - DCC 2007
ホスト出版物のサブタイトル2007 Data Compression Conference
ページ123-132
ページ数10
DOI
出版ステータス出版済み - 2007
イベントDCC 2007: 2007 Data Compression Conference - Snowbird, UT, 米国
継続期間: 3月 27 20073月 29 2007

出版物シリーズ

名前Data Compression Conference Proceedings
ISSN(印刷版)1068-0314

その他

その他DCC 2007: 2007 Data Compression Conference
国/地域米国
CitySnowbird, UT
Period3/27/073/29/07

!!!All Science Journal Classification (ASJC) codes

  • コンピュータ ネットワークおよび通信

フィンガープリント

「Simple linear-time off-line text compression by longest-first substitution」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル