2008/06/15

Parallel Huffman Decoding

吳家麟老師上課提到有人在做 bidirectional Huffman code(即順著讀倒著讀都解得出來的 Huffman code)。我今天突然想到,解 bidirectional Huffman code 的演算法其實依照定義就是可以同時表示成 foldr 和 foldl 的 function 嘛,那根據 third homomorphism theorem,就存在某種方式可以把 bidirectionally Huffman-coded segment 亂切成小段、交給多顆處理器平行解碼,最後再組合起來呀!剛剛 Google 一下,parallel Huffman decoding 的確有人做了,但演算法的概念看起來有點 ad hoc。感覺上值得用 algebraic method 試試看!

--
看起來就是很熱的題目 XD。

Labels: