第3回目 MG勉強会
Managing Gigabytesの3回目です。本日の内容は算術符号とブロックソーティングです。ここは結構目から鱗的な、おもしろいアルゴリズム連発です。
算術符号
まずは算術符号です。前回出てきたハフマンコーディングは、1パス目で各語の出現頻度を求めて、2パス目で符号化するという方法でしたが、これは1パスで出現頻度を求めつつ、同時に符号化を行っていく方法になります。それでいて、ハフマンコーディングより圧縮率が高いという方法になります。
算術符号では、実数の「範囲」をうまく使って、出現頻度の高い語には広い範囲、出現頻度の低い語には狭い範囲を割り当てることで、圧縮を効率よく行う方法です。ちゃんと説明すると長そうなので、いずれまたちゃんとした説明を試みます。
第2回目 MG勉強会
本日はManaging Gigabytes勉強会の第2回目でした。本日の内容はText CompressionのさわりとHuffman Coding。Canonical Huffman Codingスゲーという感じのお話。
Text Compression
まずはText Compressionとはなんぞや、という話。テキストを普通に保存する場合、単純に保存する1文字8bitとか使うことになってしまうのですが、普通の言語の場合、すべての文字が同じ出現頻度で出現することはありません。たとえば、英語の場合"e"という文字の出現頻度は高くて、"z"みたいな文字の出現頻度は低くなります。その出現頻度を考慮して、出現頻度の高い文字には短いビット長、出現頻度の低い文字列には長いビット長を割り当てることで、全体としてのビット長を短くしましょう、というのが基本になります。この方法がCompressionということになります。このときの割り当て単位として、各文字ごとに決めていく方法をSymbolwise法で、単語やあるまとまりごとに行う方法をdictionary法といいます。
単にCompressionとはいっても、これには2つの段階、ModelingとCodingというものがあります。Modelingというのは、各語の生起確率を求めることで、その生起確率から各語にビットを割り当てる部分がCodingになります。このとき、まずModelを求めてから、それに応じてCodingを行う方法をStatic Compression(またはSemi-static Compression)、Modelを求めつつCodingをして、次々とModelを更新していく方法をAdaptive Compressionなどと言ったりします。
Models
モデリングとは、各語の生起確率を求める方法になります。ここで出てくるシャノンの情報量定理の式( I(s) = - log Pr[s] )という式はよく使われるのでチェックです。
実際にはModelというと、必ずしも各語の生起確率だけではなく、前後の関係によって生起確率が変わることなどを考慮したfinate state machineを利用した方法もあります。
また、実装のことなども考えた場合、出現頻度が0となってしまう語が出現する場合(zero frequency problem)なども問題になります。モデル作成時には出現頻度0としたが、Codingの時にその後が出現してしまった場合、その後は符号化できなくなってしまいます。これを避ける方法なども実際にはモデル化に取り込んでいかないといけないことになります。
Huffman coding
コーディングの最初の手法は、比較的よく知られたHuffman Codingです。これは各語の生起確率からトーナメント表のようなものを作って、それぞれに0,1を割り当てることによって接頭符号を作る方法です。トーナメント表を作るときに、生起確率の小さいものから組み合わせていくことで、出現頻度が高いものは短い符号、出現頻度が低いものは長い符号となるようにします。
このHuffman codingの特性を利用し、さらにいくつか制約を科すことによって、より効率的に符号化・復号化できるようにした手法がCanonical Huffuman Codingです。この部分はまだ理解が追いついてないので、理解できたらまた別エントリで。
Vimで自動的にテンプレートを挿入する
よく忘れるのでメモ。Vimで新しいファイルを作ったときに、拡張子に応じて自動的にテンプレートを適用する方法です。
まずは準備として、VIMHOMEを設定。.bashrcとか.zshrcに以下の設定。
export VIMHOME=$HOME/.vim
次に.vimrcの設定。autocmdを使って、テンプレートを読み込むようにします。
autocmd BufNewFile * silent! 0r $VIMHOME/templates/%:e.tpl
これでvimで新規ファイルを作成すると、その拡張子に応じて$HOME/.vim/templates以下の<拡張子>.tplファイルをテンプレートとして読み込む設定ができました。
あとはテンプレートファイルの作成。例えばhtmlファイルならこんな感じ。
$ vim $HOME/.vim/templstes/html.tpl <html> <head> <title></title> </head> <body> </body> </html>
拡張子に応じたテンプレートを作ったら、後はその拡張子のファイルを作成したら、自動でテンプレートが適用されます。
Hacking Vim: A Cookbook to Get the Most Out of the Latest Vim Editor
Kim Schulz (著)
￥ 5,436 （税込）
FirefoxでSCIMが効かない
Firefoxなのですが、どうも日本語入力がうまくいかなくなってました。
SCIMが起動しない。
ちょっと調べたところ、Ubuntuに限らず、どの環境でもFirefox + SCIMはうまく言ってないみたいです。
取り合えず動くっぽい方法。
$ sudo vi /usr/bin/firefox export GTK_IM_MODULE=scim-bridge (<=追加)
まあ、ちゃんと動いてるし、これでいいかな。
[追記]
全然直ってなかった。。。
どうもタイミングによってはうまくいくってだけだったみたい。
実際普通にターミナルからfirefoxを起動すると何かエラーが出る。
An IOException occurred at scim_bridge_client_imcontext_set_cursor_location ()
どうもこれはscimのデーモンにうまくつなげていないせいらしい。
ググると結構このエラー関連のページは引っかかるのですが、今のところ解決方法はなさそう。
しょうがないので、scim-bridgeを外してximを使用することにします。
今渡こそちゃんと動いてる気がする。
Ubuntu9.04でThinkpadのトラックポインタを有効にする
Ubuntuを9.04にアップグレードしたら、Thinkpadのトラックポインタが効かなくなっていたので、解決方法を調査。
どうやら普通に設定を書けばいけそう
$ sudo vi /etc/hal/fdi/policy/mouse-wheel.fdi <match key="info.product" string="TPPS/2 IBM TrackPoint"> <merge key="input.x11_options.EmulateWheel" type="string">true</merge> <merge key="input.x11_options.EmulateWheelButton" type="string">2</merge> <merge key="input.x11_options.XAxisMapping" type="string">6 7</merge> <merge key="input.x11_options.YAxisMapping" type="string">4 5</merge> <merge key="input.x11_options.ZAxsisMapping" type="string">4 5</merge> <merge key="input.x11_options.Emulate3Buttons" type="string">true</merge> </match>
これで再起動したら、ちゃんとトラックポインタが使えるようになってました。
Ubuntuをアップグレード 8.04 -> 8.10 -> 9.04
先日Ubuntuの9.04が出たので、ThinkpadのUbuntuをアップグレードしました。
かなり簡単なのですが、簡単なりにメモ。
まず9.04へのアップデートですが、8.10からしかできません。
しかし、僕のThinkpadに入っているUbuntuは8.04なので、まず一度8.10にあげる必要があります。
8.04 -> 8.10 の方法は、
- 「システム管理」の「ソフトウェア・ソース」の設定画面を開く
- 「アップデート」タブの「アップグレードリリース」を”通常リリース版でも通知”にします。
- その後、「システム管理」の「アップデート・マネージャ」で”再チェック”を実行
- ”アップグレード”ボタンが出てくるので、そのボタンを押す
だけでOK。
後はアップグレードが終わるのをひたすら待ちます。
途中で設定系の部分でいくつか聞かれるので、お好みではい・いいえを選択します。
特にいじってない人ははいにしておけばいいと思います。
よくわからない場合はいいえで。
かなーり時間がかかるので、まったりテレビでも見ながら実行しましょう。
8.10になったらやっと9.04へのアップグレードです。
とはいってもやることは基本的に同じで、
- 「システム管理」の「アップデート・マネージャ」で”アップグレード”を実行
するだけです。
また設定系でいくつか聞かれます。
相変わらずアップグレードには時間がかかるので、まったり待ちましょう。
累計で5時間以上かかってますが、何とかアップデート完了しました。
何か不具合とかないかは、これからおいおい調べてみます。
第1回目 MG勉強会
Managing Gigabytes勉強会に行ってきました。
Nothing found for 2009-03-15-1で募集していたやつです。
今回が第１回目。
メンツ的には半分くらいはIIR勉強会とかぶってます。
この「Managing Gigabytes」という本なのですが、圧縮技術全般、テキスト圧縮から、画像圧縮、検索インデックスの圧縮まで書いた結構マニアックな本です。
IIR本にさらに輪をかけて硬派な本です。
異常に重くてかさばります。。。
全体をぱらぱら見た感じだと、いくつか知った言葉も散見されたので、面白そうな感じです。
第１回の今回は第１章です。
内容的にはこの本のポジションの説明、なぜ圧縮技術が必要なのか、どんな圧縮技術が必要なのか、この本でそれをどう説明していくのか、という部分の解説です。
以下簡単に怪しげな要約。
100年以上前から、本の完全な索引(concordance)を作る試みというのが行われています。
この作業というのは、いろいろ工夫はされているのですが、どうしてもやはり単調な仕事をひたすらやらなくてはできない作業になってしまいます。
しかし、最近はコンピュータの出現により、この単調な仕事をコンピュータに肩代わりさせることができるようになったため、たくさんの文書(document database)がコンピュータ上に保存されています。
この大量の文書は、何も文字だけではなく、画像や画像化された文書(document image)も入っています。
そのため、この大量のデータを保存するための圧縮技術や、単に保存するだけでなく、取り出して使うための索引技術が必要になってきます。
このそれぞれの技術について、本章以降でその実現方法をみていくことになります。
今回は第1回目なので、懇親会です。
やっぱりこういうコアなメンバーが集まるとおもしろいですね。
端から見ると意味不明な会話だと思いますが。
