著者

中村博文

出版者

独立行政法人 国立高等専門学校機構 都城工業高等専門学校

雑誌

都城工業高等専門学校研究報告

巻号頁・発行日

vol.52, pp.1-10, 2018

---

Abstract For lossless data compression, an off-line encoding method which has analysis and cutting ofinput symbol string is proposed. The analysis is based on replacement of frequent symbol pairs appearingrepeatedly. By the operation, the encoder does not cut in the symbol string which emerges more frequentlyin the input symbol string. The encode does not send dictionary data to the encoder directly, but sendinformation for construction of dictionary to the encoder. Its decoding can be done fast with one-pathmethod without deep analysis of its input. A set of efficient data structures for the encoding and thedecoding such as hash table, frequency table, and bidirectional list is used. Theoritical proof that theencoding and the decoding can be executed in time O(N) is proved, where N is the size of input data andO(・) is Bachmann-Landau Big O notation. Keywords [Data compression, Most frequent symbol pair, Replacement, Concatenation, Digram ]