Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compression > #2023

Re: Skybuck's Parallel Static Huffman Decoding Algorithm

Cross-posted to 3 groups.

Show all headers | View raw

Dombo wrote:
) Op 12-Sep-13 7:54, glen herrmannsfeldt schreef:
)> In comp.compression Skybuck Flying <Windows7IsOK@dreampc2006.com> wrote:
)>
)> (snip)
)>> Today/Tonight I had an idea how to fund my Algorithm skills ;) :)
)>
)>> It's always funny to see how some programmers believe that
)>> Huffman cannot be decoded in parallel.
)>
)> No, not impossible, but not so easy, either.
)
) It is possible and not that hard either, and in fact has been done many 
) times before by many people (myself included). I'm inclined to believe 
) that you'll only see pure serial Huffman decoding in classrooms.

That depends on if you get to control the encoding side.

A small bit of extra work on the encoding side makes it easy to decode
chunks in parallel, otherwise you have several problems, such as the
impossibility to decide the position in the decoded stream without
decoding the previous stream, and the existence of encoded streams
where each position leads to a valid (but different) decoded stream,
only one of which is the correct one.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

Back to comp.compression | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Skybuck's Parallel Static Huffman Decoding Algorithm "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2013-09-12 06:37 +0200
  Re: Skybuck's Parallel Static Huffman Decoding Algorithm glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2013-09-12 05:54 +0000
    Re: Skybuck's Parallel Static Huffman Decoding Algorithm "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2013-09-12 16:28 +0200
    Re: Skybuck's Parallel Static Huffman Decoding Algorithm Dombo <dombo@disposable.invalid> - 2013-09-14 14:57 +0200
      Re: Skybuck's Parallel Static Huffman Decoding Algorithm Willem <willem@turtle.stack.nl> - 2013-09-14 19:12 +0000
  Re: Skybuck's Parallel Static Huffman Decoding Algorithm Jasen Betts <jasen@xnet.co.nz> - 2013-09-12 13:31 +0000
    Re: Skybuck's Parallel Static Huffman Decoding Algorithm "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2013-09-12 16:30 +0200
    Re: Skybuck's Parallel Static Huffman Decoding Algorithm BGB <cr88192@hotmail.com> - 2013-09-12 19:39 -0500
      Re: Skybuck's Parallel Static Huffman Decoding Algorithm "Shaun" <stereobuff07@gmail.com> - 2013-09-19 04:26 -0500
        Re: Skybuck's Parallel Static Huffman Decoding Algorithm "Skybuck Flying" <Windows7IsOK@DreamPC2006.com> - 2013-09-22 03:25 +0200
  Re: Skybuck's Parallel Static Huffman Decoding Algorithm Thomas Richter <thor@math.tu-berlin.de> - 2013-09-21 10:09 +0200

csiph-web