Linear Algorithm for Data Compression via String Matching
Michael Rodeh, Vaughan Pratt, Shimon Even · Journal of the ACM · 1981
A linear implementation of the optimal universal data compression methods of Lempel and Ziv is described.The main tool is McCreight's algorithm for constructing suffix trees.Both bounded and unbounded memory are considered.