Algorithms to find longest common prefix in a sliding window.

Question

Hi,

I have written a Lempel Ziv compressor and decompressor.

I am seeking to improve the time to search the dictionary for a phrase. I have considered K-M-P and Boyer-Moore, but I think an algorithm that adapts to changes in the dictionary would be faster.

I've been reading that binary search trees (AVL or with splays) improve the performance of compression time considerably. What I fail to understand is how to bootstrap the binary search tree and insert/remove data. I'm not actually quite sure the significance of each node in the binary search. I am searching for phrases so will each character be considered a node? Also how and what is inserted/removed from the search tree as new data enters the dictionary and old data is removed?

The binary search tree sounds like a good payoff since it can adapt to the dictionary, but I'm just not quite sure of how it's used.

Answer 1

Does this help?

Answer 2

Hmm. String B tree I think is what you want, but I haven't went over the LZ algorithm for ages.

http://portal.acm.org/citation.cfm?id=301973

http://portal.acm.org/citation.cfm?id=1142385