Confusing about LZSS algorithm...

This is a discussion on Confusing about LZSS algorithm... within the C Programming forums, part of the General Programming Boards category; I'm reading Haruhiko Okumura's LZSS implementation and I cannot understand how the tree is working. It looks like neither a ...

  1. #1
    Registered User
    Join Date
    Mar 2010
    Location
    China
    Posts
    74

    Question Confusing about LZSS algorithm...

    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)

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,687
    You mean the comment "/* left & right children & parents -- These constitute binary search trees. */" isn't a big enough clue?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Mar 2010
    Location
    China
    Posts
    74
    But how can those integer variants and arrays construct a tree?

  4. #4
    Registered User
    Join Date
    Mar 2010
    Location
    China
    Posts
    74
    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.

  5. #5
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,687
    Read the code and find out ?

    Rather than pointers, he uses subscripts.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  6. #6
    Registered User
    Join Date
    Mar 2010
    Location
    China
    Posts
    74
    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.

  7. #7
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,687
    COMPRESS.TXT 12570 4/8/1989 1:00:00 AM
    Did you read that file as well?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  8. #8
    Registered User
    Join Date
    Mar 2010
    Location
    China
    Posts
    74
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 02-18-2010, 10:17 AM
  2. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 01:30 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21