M.Hiroi's Home Page
Guest Book Log
2005年8月14日 (日) 19時15分22秒
[お名前] : Sam
[メールアドレス] :
[題名] : ブロックソート向けレンジコーダの改良法
[本文] : こんにちは、Sam です。主にブロックソートによるファイル圧縮を参考にさせて頂いております。
今回はブロックソート向けの適応型レンジコーダについて、圧縮率を改善できそうな方法を調べてみたので、それを紹介したいと思います。レンジコーダというのは多値レンジコーダの方です。
ブロックソート・MTFを行ったデータの特徴は、記号 0 の度数が一番多く、記号 1,2,3... と値が増えるに従い度数が少なくなっていることですが、このような度数分布に合った出現頻度表の更新の方法にすれば、圧縮率が改善すると思われます。その方法の一つは、単純なアイデアですが、例えば出現した記号を c として、出現頻度表の c の度数を加算していますが、それ以外に記号 c-1(c==0 の時は 0) の度数なども加算するというものです。実際のところ、ほんの少しですが圧縮率がよくなりました。それぞれの度数の増分値などを調整すれば、他の様々なモデルについても圧縮率を改善できるかもしれません。興味があればお試しください。
それでは。
2005年5月11日 (水) 19時29分25秒
[お名前] : M.Hiroi
[メールアドレス] :
[題名] : Re:ありがとうございました。
[本文] : まさよしさん、はじめまして。
M.Hiroi's Home Page へようこそ。
＞インターネットで検索しましたらこのサイトが見つかり
＞説明を読ませていただきました。とても分かりやすく
＞大変勉強になりました。
拙作のページが少しでもお役に立てれば幸いです。
最近、Perl 関連のページは更新が止まっていますが、
これらもがんばりますので、よろしくお願いいたします。
2005年5月11日 (水) 02時25分09秒
[お名前] : まさよし
[メールアドレス] :
[題名] : ありがとうございました。
[本文] : いま実用perlプログラミング（2回目）を読んでいますが、tie関数の説明についていけず途方にくれていました。インターネットで検索しましたらこのサイトが見つかり説明を読ませていただきました。とても分かりやすく大変勉強になりました。（参考文献に実用perlプログラミングがあがっているときは笑いました。）本当にどうもありがとうございました。m(__)m
2005年4月17日 (日) 10時33分03秒
[お名前] : M.Hiroi
[メールアドレス] :
[題名] : Re:ZLEの改良 補足など
[本文] : Sam さん、こんにちは。
＞Memorandom 4月6日分拝見しました。試してくれてありがとうございます。
どういたしまして。
＞0-1-2 coding 等で圧縮する前段階に行う RLE でも、記号 2 以上で
＞この方法を適用すれば、同じような効果があると思われます
そうですね。kennedy.xls の圧縮率は向上するかもしれません。
そのうちに試してみたいと思います。
＞画像・音声データに特化した(可逆の)圧縮アルゴリズムについても
＞興味があり、本講座で採り上げてもらいたいと願っているのですが、
＞もしもよろしければお願いします。
画像や音声の可逆圧縮はとても興味深い分野なのですが、勉強不足で
よくわかりません。どちらかというと、汎用的なデータ圧縮アルゴリ
ズムに興味があるので、その方向で進めていきたいと思っております。
あしからずご了承くださいませ。
それでは。
2005年4月17日 (日) 01時41分46秒
[お名前] : Sam
[メールアドレス] :
[題名] : ZLEの改良 補足など
[本文] : どうも Sam です。Memorandom 4月6日分拝見しました。試してくれてありがとうございます。
お気付きかと思いますが、Canterbury Corpus のテストデータについて、RLE3などを用いた場合 kennedy.xls が、ZLEの場合にはそれ以外のファイルが高い圧縮率になっています。ZLEの改良型は、この2つのいいとこ取りを狙ったものであり、その目的はある程度は達成できたとみれるでしょう(これがベストの方法とは言い切れませんが)。また、0-1-2 coding 等で圧縮する前段階に行う RLE でも、記号 2 以上でこの方法を適用すれば、同じような効果があると思われます(ちなみに私はレンジコーダのほうは勉強不足で、まだ少ししか理解できていません)。
あと、別に無理じいはしませんが、画像・音声データに特化した(可逆の)圧縮アルゴリズムについても興味があり、本講座で採り上げてもらいたいと願っているのですが、もしもよろしければお願いします。
それでは。
2005年4月4日 (月) 18時59分36秒
[お名前] : M.Hiroi
[メールアドレス] :
[題名] : Re:ZLEの改良
[本文] : Sam さん、はじめまして。
M.Hiroi's Home Page へようこそ。
＞ポイントは、なるべく大きい記号の出現頻度を減らすように、
＞ランレングスを開始する連長nの値を記号によって変えることです。
なるほど、面白い方法ですね。「ブロックソート + MTF」のあとでも、
大きな記号が多く残っているような場合には効果がありそうです。
そのうちに試してみたいと思います。
それでは、これからもよろしくお願いいたします。
2005年4月3日 (日) 18時29分15秒
[お名前] : Sam
[メールアドレス] :
[題名] : ZLEの改良(その2)
[本文] : 私の思いついたZLE&RLEの方法は、記号によって次のように変換します。
記号
0 :ZLE (オリジナルと同じ)
1 :RLE10
2 , 3 :RLE9
4 - 7 :RLE8
8 - 15 :RLE7
16 - 31 :RLE6
32 - 64 :RLE5
64 - 128 :RLE4
128 - 253 :RLE3
254 , 255 :0xff を出力後、[(ラン長-1)*2 + (記号254:0, 記号255:1)]を出力
ポイントは、なるべく大きい記号の出現頻度を減らすように、ランレングスを開始する連長nの値を記号によって変えることです。これを可変長RLEとでも名付けておきましょう。また、記号254,255についても前述の方法でランレングスを適用してみたところ(この場合、ラン長128が限度ですが)、一部のバイナリファイルで圧縮率が多少改善されるようです。興味のある方は、ランレングス開始の連長をいろいろ変えたりして試してみて下さい。感想などを頂けたら幸いです。
2005年4月3日 (日) 18時25分20秒
[お名前] : Sam
[メールアドレス] :
[題名] : ZLEの改良(その1)
[本文] : はじめまして。Sam と申します。学生で、ちょっとしたプログラミングが趣味といった感じです。このページを見つけてからファイル圧縮に興味を持つようになり、主にブロックソートによるファイルの圧縮を参考にさせて頂いております。それに関することですが、ZLE&RLE(http://www.geocities.jp/m_hiroi/zsaru/zsarub08.html参照)の改良型を思いついたので、ちょっと紹介したいと思います。長くなりそうなので、ここで一旦切ります。
2005年2月23日 (水) 18時41分47秒
[お名前] : M.Hiroi
[メールアドレス] :
[題名] : Re^2:レンジコーダの改良について
[本文] : M.Hiroi です。
ZLE (Zero Length Encoding) と 0-1-2 coding (混合法）の
組み合わせを試してみました。結果は次のページをお読みく
ださいませ。
http://www.geocities.jp/m_hiroi/memo0502.html#23
2005年2月21日 (月) 19時59分44秒
[お名前] : M.Hiroi
[メールアドレス] :
[題名] : Re:レンジコーダの改良について
[本文] : jil さん、こんばんは。
ZLE (Zero Lengh Encoding) と 0-1-2 coding を組み合わ
せる場合、jil さんの方法は確かに効果があると思います。
しかしながら、拙作のページ「0-1-2 coding」で説明しまし
たが、0-1-2 coding と ZLE の相性はあまりよくありません。
ランレングスの場合は、2 以上の記号に対して適用すると、
圧縮率が向上する場合があります。「混合法による binary
model の改良」の RLE はこの方法を使っています。
混合法を適用すると ZLE の方が高い圧縮率になる、という
ことでしたら、とても興味深いことです。私も試してみよう
と思います。
ではでは。
2005年2月21日 (月) 11時49分27秒
[お名前] : jil
[メールアドレス] :
[題名] : レンジコーダの改良について
[本文] : お久しぶりです。jil です。
早速ですが、私が考えた圧縮方法(の改良)についてですが、
「混合法による binary model の改良」において、0-1-2Codingを行うときに、
0-1-2：出力コード
0：1
1：01
2：00
という風に出力されていると思います。
ただ、レンジコーダ直前に、RLEではなくZLEを使用していた場合、0-1-2Codingでは、'0','1'の数よりも、'2'の数が増えます。
よって、出力コードを以下のように変更します。
0-1-2：出力コード
0：01
1：00
2：1
処理は煩雑になりますし、小手先の技術だとは思いますが、多少圧縮率が向上します。
ZLEを利用している人は試してみてはいかがでしょうか。
2005年2月17日 (木) 01時38分25秒
[お名前] : 畑健一郎
[メールアドレス] : xc9k-ht@asahi-net.or.jp
[題名] : バージョンアップ
[本文] : ふくろうリスプ Ver. 0.4 をリリースしました。
型指定子、パッケージ、関数型（クロ－ジャー）が
追加されました。
ホームページ：http://www.asahi-net.or.jp/~xc9k-ht/
2005年2月13日 (日) 21時32分22秒
[お名前] : M.Hiroi
[メールアドレス] :
[題名] : Re:無事・・・
[本文] : jil さん、こんばんは。
「すたんだ～ど」の完成、おめでとうございます。
VECTOR からダウンロードして試してみたいと思います。
バージョンアップ、がんばってください。
ではでは。
2005年2月13日 (日) 16時23分40秒
[お名前] : jil
[メールアドレス] :
[題名] : 無事・・・
[本文] : １２月にここに書き込みをした jil です。
無事卒業研究としてソフトが出来上がり、VECTORにフリーソフトとして登録されたので報告します。
「すたんだ～ど」という名称でVECTORに登録しています。(２月下旬までにはさらにバージョンアップする予定です)
私個人でなく、複数人数での共同開発です。
ちなみに、私は DLL 部分の開発を行いました。
すばらしいソースコードを公開されているM.Hiroi様に感謝したいと思います。
2005年2月11日 (金) 09時26分18秒
[お名前] : M.Hiroi
[メールアドレス] :
[題名] : Re:prolog01.html 正誤
[本文] : F.Saito さん、はじめまして。
M.Hiroi's Home Page へようこそ。
拙作のページが少しでもお役に立てれば幸いです。
ご指摘ありがとうございます。
さっそく修正したいと思います。
それでは、これからもよろしくお願いいたします。
2005年2月10日 (木) 21時43分49秒
[お名前] : F.Saito
[メールアドレス] :
[題名] : prolog01.html 正誤
[本文] : おかげさまで Prolog の勉強をさせて頂いております。
prolog/prolog01.html 内、「簡単な例題：家系図」のプログラムで、mather_of 及び grandmather_of のスペリングが気になりました。それと、『ここで、male( X ) を female( X ) に変更すると、「娘 (daughter_of) 」の関係を表すことができます。』と述べておられるのに、「娘 (daughter_of) の定義」内で、
daughter_of( X, Y ) :- parents_of( Y, X ), male( X ).
と、なっています。
2004年12月25日 (土) 10時48分16秒
[お名前] : M.Hiroi
[メールアドレス] :
[題名] : Re:静的ハフマンの符号表の保持方法について
[本文] : MALU さん、はじめまして。
M.Hiroi's Home Page へようこそ。
拙作のページが少しでもお役に立てれば幸いです。
＞ハフマン木は符号長のみから作成でき、・・・
＞(N=256の場合、8bit*256=256Bytes)で静的ハフマンの符号表を保持できると
＞ありましたが、
「256 byte でハフマン木を表現する方法」は参考文献を示しただけで、
拙作のページでは説明しておりません。
参考文献 [3]
村田敏幸,『X68000マシン語プログラミング Chapter_2C ハフマン符号化』,
Oh!X 1993 年 12 月号, ソフトバンク
昔の雑誌ですが、符号語長だけでハフマン木を再現する方法が説明されています。
＞先頭1Byteに表現に必要なbit数を書き、
＞・・・
＞符号表のサイズが約半分にもなります。
なるほど、面白い方法だと思います。参考文献 [3] のプログラムでは、
最長符号語長を制限することで符号長を 5 bit で表し、符号表のサイズ
を小さくしていますが、MALU さんの方法だと制限が無いので柔軟に対応
できますね。ハフマン符号を使うときに試してみたいと思います。
MALU さん、ありがとうございました。
これからもよろしくお願いいたします。
2004年12月24日 (金) 22時22分16秒
[お名前] : MALU
[メールアドレス] :
[題名] : 静的ハフマンの符号表の保持方法について
[本文] : はじめまして。MALUと申します。
最近圧縮アルゴリズムに興味を持ち、勉強している中でここのページを知り、大変参考にさせていただいております。
さて、本題です。ハフマン木は符号長のみから作成でき、そして符号長は最長で(符号の種類N-1)となるため、(最短符号長(1)～最長符号長(N-1)を表現するのに必要なbit数)*N (N=256の場合、8bit*256=256Bytes)で静的ハフマンの符号表を保持できるとありましたが、
実際のデータにおいては最長符号長は例えばN=256の時はせいぜい20(表現に必要なbit=5)くらいにしかならなく、頻度の偏りが少なければ16(同4)に収まる事も多かったので、先頭1Byteに表現に必要なbit数を書き、以降そのbit数で各符号長を書いていけば、N=256,bit=5の場合は1Byte+5bit*256=161Bytes、bit=4の場合に至っては1Byte+4bit*256=129Bytesと、符号表のサイズが約半分にもなります。
非常に単純な方法ですが、どこにも文献が見当たらなかったので失礼ながらここに書かせていただきました。(もしも既出でしたらすみません。)
2004年12月13日 (月) 19時49分38秒
[お名前] : M.Hiroi
[メールアドレス] :
[題名] : Re:はじめまして
[本文] : jil さん、はじめまして。
M.Hiroi's Home Page へようこそ。
拙作のページが少しでもお役に立てれば幸いです。
＞ここのページに掲載してあるソースコードを利用して、卒業研究
＞でプログラムを組もうと思います。圧縮部分を VC++ でDLLとし
＞て作成し、ユーザインタフェースを VB で作成しようと思ってい
＞ます。いずれは VECTOR にフリーソフトとして公開したいのです
＞が、その許可をいただきたいと思います。
Ｃ言語講座の「権利・免責事項など」に書いてありますように、Ｃ
言語講座で作成したプログラムはフリーソフトウェアとしておりま
す。ご自由にお使いください。
卒業研究の場合、jil さんの学校の規則や先生の指導方針に従って
研究されていると思います。これらに反することがないよう、先生
に相談してからお使いください。
なお、これらのプログラムは無保証であり、使用したことにより生
じた損害について、作者 (M.Hiroi) は一切の責任を負いません。
このことはご了承くださいませ。
それでは、卒業研究がんばってください。
2004年12月12日 (日) 22時57分40秒
[お名前] : jil
[メールアドレス] :
[題名] : はじめまして
[本文] : はじめまして。
私は福岡の専門学校に通う jil と申します。
１年ほど前より圧縮に興味を持ち始めまして、今年５月に家にネット回線を引いてからすぐにこのページを見つけ、以来よく来ております。
さて、早速なのですが、ここのページに掲載してあるソースコードを利用して、卒業研究でプログラムを組もうと思います。圧縮部分を VC++ でDLLとして作成し、ユーザインタフェースを VB で作成しようと思っています。いずれは VECTOR にフリーソフトとして公開したいのですが、その許可をいただきたいと思います。
具体的に利用する(予定の)ソースは「ブロックソートの高速化(6)」「レンジコーダによるファイルの圧縮(3)(4)(5)」「ブロックソートによるファイルの圧縮(11)」「ブロックソートによるファイルの圧縮(3)」内の各ソースです。
2004年11月13日 (土) 11時00分36秒
[お名前] : M.Hiroi
[メールアドレス] : m_hiroi@yahoo.co.jp
[題名] : Re:高速化アルゴリズム
[本文] : 大地さん、こんにちは。
＞私は最近バイナリサーチよりも条件次第で高速なサーチを考案しました。
それは凄いですね。とても興味があります。
プログラムが最後まで書き込まれていませんが、
これはゲストブック側に問題があるようです。
どうやらこのゲストブックは、プログラムの書き込みに
適していないようです。
大地さんのプログラムですが、私のページでよろしければ
喜んで掲載いたします。お手数ですが、メールでお送りくださいませ。
それではよろしくお願いいたします。
2004年11月12日 (金) 20時06分06秒
[お名前] : 大地
[メールアドレス] : kool@mocha.freemail.ne.jp
[題名] : 続きです
[本文] : [Hybrid Search]
int c = 0, j;
for (j=64; j; j =2) {
if (sum[c+j]
2004年11月12日 (金) 20時05分37秒
[お名前] : 大地
[メールアドレス] : kool@mocha.freemail.ne.jp
[題名] : 高速化アルゴリズム
[本文] : こんにちは、久しぶりに書き込みです。
最近、レンジコーダの高速化に取り組んでいまして、
効果のあったアルゴリズムを紹介します。
M.Hiroiさんのレンジコーダのデコード部でシンボルの検索では、
今のところリニアサーチを使っているようで、
いずれはバイナリサーチにするのだと思いますが、
私は最近バイナリサーチよりも条件次第で高速なサーチを考案しました。
まずバイナリサーチからいきますと以下のようになります。
int c = 0, j;
for (j=128; j; j =1) c += (sum[c+j]
2004年10月24日 (日) 18時15分26秒
[お名前] : M.Hiroi
[メールアドレス] :
[題名] : Re:地震！？
[本文] : 鎌田さん、こんにちは。
＞大丈夫とのことで安心しました。
＞余震で崩壊するところもあるかも知れないので気をつけてくださいね。
お気づかい、ありがとうございます。
今でもときどき大きな余震があるので、
油断しないで気をつけたいと思います。
ではでは。
2004年10月24日 (日) 17時01分01秒
[お名前] : M.Kamada
[メールアドレス] : m_kamada@nifty.com
[題名] : Re:地震！？
[本文] : 広井さん、こんにちは。
大丈夫とのことで安心しました。
余震で崩壊するところもあるかも知れないので気をつけてくださいね。
では。
2004年10月24日 (日) 15時35分28秒
[お名前] : M.Hiroi
[メールアドレス] :
[題名] : Re:地震！？
[本文] : 卓さん、こんにちは。
＞Penguin'sBARの卓です。新潟、大変なことになりましたね。
＞私の実家（上越）は大丈夫でしたが、M.Hiroiさんは大丈夫でしたか？
＞何事も無いことをお祈りしています。
ご心配をおかけしましたが、おかげさまで
私の方はほとんど被害もなく大丈夫です。
ライフラインも復旧したので一安心ですが、
まだ余震が続いているので注意したいと思います。
ではでは。
2004年10月23日 (土) 22時37分46秒
[お名前] : 卓
[メールアドレス] : hql11254@nifty.com
[題名] : 地震！？
[本文] : Penguin'sBARの卓です。新潟、大変なことになりましたね。私の実家（上越）は大丈夫でしたが、M.Hiroiさんは大丈夫でしたか？何事も無いことをお祈りしています。
2004年10月23日 (土) 10時17分40秒
[お名前] : M.Hiroi
[メールアドレス] :
[題名] : Re:centerとtableの入れ子が逆
[本文] : nari さん、はじめまして。
M.Hiroi's Home Page へようこそ。
＞ページソースを見るとcenterとtableの入れ子が逆に
＞なっているところが結構あってブラウザ(firefox)で
＞上手く表示されていません。。。
ご指摘、ありがとうございます。
さっそく修正したいと思います。
それでは、これからもよろしくお願いいたします。
2004年10月23日 (土) 05時20分25秒
[お名前] : nari
[メールアドレス] : maaanaari@hotomail.com
[題名] : centerとtableの入れ子が逆
[本文] : CommonLispでwebを検索して辿りつきました。
で、xyzzy lispのページを見ていたのですが、
ページソースを見るとcenterとtableの入れ子が逆に
なっているところが結構あってブラウザ(firefox)で
上手く表示されていません。。。
ちょっと見なおしてみてもらえませんか？
2004年10月8日 (金) 21時35分34秒
[お名前] : M.Hiroi
[メールアドレス] :
[題名] : 新しいゲストブック
[本文] : M.Hiroi です。
ジオシティーズが統合されて、M.Hiroi's Home Page も新ジオシティーズに移りました。
今までのゲストブックは廃止されたので、とりあえず新ジオシティーズで用意されているゲストブックを使うことにしました。
ご意見やご感想など、お気軽にお書き込みくださいませ。