Quote: compared longest match search for Ziv-Lempel compression; lists for each character, best overall

Quotation Skeleton

[For Ziv-Lempel coding,] Decoding a compressed file is very fast, … few characters. This paper presents eight data structures … [p. 766] In general the data structures that require … [of positions for each character] was up to 10 times faster than linear search … The list2 method [positions for each character pair] is particularly effective [but it used the most space]. [list1 is next best up to window=2000, then binary tree and hash table are next best (hashing using 5 times more space). Splay trees, tries, linear search, and Boyer-Moore search are clearly worse. For a bit-mapped image file and window=512, list1/2 best then Boyer-Moore, with the rest clearly worse].   Google-1   Google-2

Copyright clearance needed for quotation.

Related Topics

Topic: search algorithms (40 items)
Topic: data compression algorithms (53 items)