圧縮できる?

少々思うところありまして、
いろいろコルモゴロフ複雑性について考えていたのだけど。

こんなプログラミング言語を作る。
p=「00」を出力
q=「01」を出力
r=「10」を出力
s=「11」を出力

「0011011」を出力するには「pqrs」を実行すればいいように。
ただこのプログラムの長さを4とすると、
任意の2進列を半分の長さで記述できることになる。

これではおかしくなるので、
プログラムの長さもその2進列で計れば「pqrs」も
それぞれの記号が一度ずつ出現するので圧縮しようもなく、
2進列では各記号が2文字ずつ使うであろう、と。

なんかね、こういう話をしていると
圧縮可能な文字列というのが果たしてとらえきれる性質なのか
不安になってくる。

テレビが壊れた

いや、びっくりしたぁ。

ピシっっていう音とともに画面下のほうが黒くなって
なんですと?って思ってたら次の瞬間、
ブンって画面が真っ黒に。

電源ボタン押してもうんともすんとも言わないから
壊れたんだろうなぁ。
買ってこないとさすがにねぇ。
パソコンもそうだけどテレビも
まだまだ無いと困るよね。

おろろん。デジタル対応がちょっと早く来たと思えばいいか。
保険のお金もいっぱいおりることだし。ほっほっほ。

身障者だって

身障者だってお酒ぐらい飲みます。
少々ふらふらしててあぶなっかしいてすが

非常に楽しかったです。
また飲めるといいなぁ。

リハビリ終了

何だかんだで9ヶ月。
ようやくリハビリも今日でおしまい。
症状固定をして軽度身障者として
社会復帰することとなりました。

お世話になった病院の方々や患者さんたちに
感謝しつつ。
またい未来から遠い未来まで様々な不安に
怯えつつ。

とりあえず夕方からリハビリの先生(一つ上)
と飲みに行きます。

おぉ、日記みたいだ。

コルモゴロフ複雑性

先日ランダム性について云々したことがあって、
いや日付とかは忘れて、しかも探す気もない。

んで、どこぞの先輩が書いたようなそうでないような
ページを思い出していて
「雑な定義」をそのまま定義として理解してた。迂闊。

同値な定義がいくつかあるらしいけど
やっぱりこのコルモゴロフ複雑性の定義は計算機数学的でしっくりくるね。

ところがや、
「文字列 x がc圧縮不可能ならばその部分文字列もc圧縮不可能」っていう
簡単な事実を、まぁこれはそれほど証明は面倒臭くないと思うけど
結局はアルゴリズムの存在性とか非存在性に帰着しなきゃいけないのは
どうしても話がややこしくなる。

学問として発展するのに、P=NP?みたいに
接近不可能な問題が早い段階で現れてくるでしょ。きっと。
どうにかならんかね。

新車のお祓いいってきました

写真はこちら

いままではiPhoto⇒iWebという流れで写真ページをつくってたんだけど
iWeb自体が.Macを前提としているところが多々あって、
一般のサイトにアップするにはちょっと使い勝手が悪い。

んで、さしあたって写真ページ作成プログラムをつくってみた試作ページとなってます。
写真のサイズをいっさい手を加えずにアップしてるから
ちょっとロード時間が遅いかもしれない。
あと、後で修正しようとしてもデータが残ってないから
書き出したページを直接いじるしかないのもちょっと難点。

形になったら公開しますゆえ。

データ圧縮について、思うところ

まずは基本。可逆圧縮において全てのファイルのサイズを縮小する方法はない。
 f:N->Nを圧縮関数、log:N(>0)->N(>0)をサイズを計算する関数
 for all n log(n)>log(f(n))であるならば
 log(n),log(f(n)),log(f(f(n))),...は無限降下列となる。
 これはlogの定義に反する。

さらに、可逆圧縮においてファイルのサイズが減少しないファイルは無限個ある。
証明はこちら 

んでさ、そうするとある程度のラインで圧縮をあきらめる必要がある。
例えばテキストファイルを圧縮するなら
 バイナリファイルのサイズは圧縮できないことにして、
 そいつらが占めてた場所に順序よくテキストファイルを当てれば
 それで圧縮にはなるわけだ。

Zipなどの汎用の圧縮フォーマットでは
大雑把に言えば、そのファイルに現れる記号に
 別の記号を当てはめた上で
 近くに同じ記号列があればその記号列を書くよりは短い新たな記号で
 代用する、といった感じで圧縮をする。

これは人間が使用する記号に偏りがあることであったり、
画像などにおけるある点とその周辺の点は色が似ていたり、
また文章のなかで同じ単語をなんども使用したりすることを
うまく表していると言える。

ようは無茶を承知で言えば
圧縮とは自然を人工に落とし込む作業で
圧縮されたファイルがどれだけ「反自然」であるかが圧縮率。

「反自然」って何かな。一様な乱数とか?
違う、ランダム性だ。ランダム性と圧縮かぁ。
効率的なものではなくて理論的なものとしては
面白い研究対象かもしれないねぇ。

Java(Rhino)でサムネイルを作成する

写真ページを作るのにiPhoto->iWebという流れはまぁいいんだけど
.Macを使用していない人間にとってみると
iWebでサイト全体を作る気は毛頭ないので
ちょっとiWebのフォルダ書き出し機能はしんどいわけです。
(過去に作ったページまで書き出そうとするから)

というわけでJavaで自分好みのPhoto管理ソフトを作ろう
(とか言いながらRhinoで作ってる)

まずはサムネイルを指定したサイズでまとめて作りたい関数。


importPackage(Packages.java.awt)
importPackage(Packages.java.awt.image)
importPackage(Packages.java.io)
importPackage(Packages.javax.imageio)

var createThumb=function(srcfile,dstfile,maxSize){
// srcfileの読み込み
var fis=new FileInputStream(srcfile)
var image=ImageIO.read(fis)
fis.close()

// 縮小率を計算する
var h=image.getHeight()
var w=image.getWidth()
var s= h>w? h:w
var scale=1.0*maxSize/s

w=parseInt(w*scale)
h=parseInt(h*scale)

// dstfileの書き込み準備
var shrink=new BufferedImage(w,h,image.getType())
var g=shrink.createGraphics()
g.setRenderingHint(RenderingHints.KEY_INTERPOLATION,RenderingHints.VALUE_INTERPOLATION_BICUBIC)
g.setRenderingHint(RenderingHints.KEY_RENDERING,RenderingHints.VALUE_RENDER_QUALITY)
g.setRenderingHint(RenderingHints.KEY_DITHERING,RenderingHints.VALUE_DITHER_ENABLE)

// 書き込み
g.drawImage(image,0,0,w,h,null)
ImageIO.write(shrink,'jpg',new File(dstfile))
}

再帰定理?

>計算論の「再帰定理」では、再帰関数を使用したプログラムを
>ループと条件分岐を使ってgotoなしで書き換えられる、ということを証明している。

一部表現を変えてありますが、そんな記述を見つけて。
それは「構造化定理」なんじゃないかと。

証明は再帰的な定義を許容するプログラミング言語と
ループと条件分岐があって再帰的な定義とgoto文がないプログラミング言語が
それぞれチューリング完全であることを示せばよいと。
まぁいちいちやるきは起きないけど
それほど難しくはないだろう。


ちなみに「再帰定理」は
引数を1つ以上とる任意のプログラムAについて
あるプログラムBがあって、プログラムAの引数としてプログラムBを代入した結果と
プログラムBを実行した結果が等しくなる。
正確な表現ではないけど、翻訳するとこんなところ。

これを面白いと思える人が多いと、いいなぁ。

自動車保険の見積り

OUTLANDERを買うことにしました。
そういえば自分の車を持つなんて初めてであります。
保険にもしっかり入っとかんとね。




自己出力プログラム

ネットサーフィン(死語)してたら
「チューリング完全ならば自己出力プログラムが存在することを示せ」
という問いに答えられなかった~という話を見つけたので
さしあたって解いてみますた。→こちら

暇人、とか言わない。

関節に注射

今日は「関節内に痛み止めを打ってみますか?」ということで
ぶっとい注射を足首に。

とても見れたもんじゃないので
目を閉じて我慢すること数分。
先生の声がした。
「入らなかったのでレントゲンを撮ってそれを見ながら」

この数分の我慢はなんだったんだろうと
麻酔はかけてるけど、それなりに痛いのよっていう。
a8
最近の記事
月別アーカイブ
ブログ内検索
グリムス
フリーエリア
リンク
RSSフィード