Printable View
I'm reading Haruhiko Okumura's LZSS implementation and I cannot understand how the tree is working. It looks like neither a trie nor other search trees. Do anyone know what the tree is?
I've implement my version using a hash map as the dictionary. But it's much slower than Haruhiko Okumura's.
Haruhiko Okumura's implementation is here: LZ_C.ZIP - \LZSS.C - Data compressing algorithms LZARI/LZSS/LZHUF - H.Okumura (asm)
You mean the comment "/* left & right children & parents -- These constitute binary search trees. */" isn't a big enough clue?
But how can those integer variants and arrays construct a tree?
I know there are many types of binary search trees such as Avl or Red-black tree. But as far as I know, none of them can be used to search a substring.
Read the code and find out ?
Rather than pointers, he uses subscripts.
The algorithm needs to match a string in (4096*16=65536) strings, but it seems it uses only 4096 nodes for the tree. I just cannot understand how he can do that.
COMPRESS.TXT 12570 4/8/1989 1:00:00 AM
Did you read that file as well?
COMPRESS.C says "This implementation uses multiple binary trees to speed up the search for the
longest match", but it didn't describe how to construct those trees and how they work.