2009-05-01から1ヶ月間の記事一覧
週末に参加した Managing Gigabytes の読書会で第2章のハフマン符号を担当しました。この中で Canonical Huffman Codes の解説がありますが、そこにハフマン符号の符号長を効率的に求める手法の説明が含まれています。輪講では時間切れのためこのアルゴリズ…
IIR の第4章 Dynamic indexing では検索用のインデックスにおいて対象とする文書に頻繁に更新が発生する場合にどうそれを扱うべきかという話題を扱っています。ここで "Logarithmic merging" という話が出てきます。以前に読んだ際に良く理解できなかったの…
1999年出版と少し古い書籍ですが Managing Gigabytes を読んでいます。理解のために 2.3 で出て来る Canonical Huffman Codes の習作を作りました。ハフマン符号は情報圧縮で利用される古典的なアルゴリズムで、圧縮対象データに出現するシンボルの出現確率…
