「モンティ・ホール問題」を実際に実験して確かめよう

Posted on 2012/02/25 by Kaede Fujisaki

　モンティ・ホール問題というのをご存知でしょうか？

モンティ・ホール問題 – Wikipedia

　大学受験生をやっていた時に、確か東工大の問題か何かで題材となっていて、それで知ったお話です。今日は国公立大学の入試日ですし、ついでなので公開しちゃいます！…懐かしいですね、去年はエア東大合格（？）して胴上げされてました。あれから１年かー。

■モンティ・ホール問題

　モンティ・ホール問題は、こんな問題です。

　とある視聴者参加ゲームショー番組のハイライト。

　あなたは３つのドアの中から、一つを選び、開けることができます。３つのうち、一つのドアの先にだけ景品がありますが、残りの２つの先には…残念、ヤギが居ます。

　さて、まずあなたはこの３つの中から一つを選びました。次に、どのドアが正解かを知っている番組の司会者が、残った２つのドアのうち、「正解でない方」を一つ開けました。

　残るドアは一つ。あなたは、今のドアから、この残ったドアに変える自由があります。

　この場合、変える方がトク（当たりやすい）でしょうか？それとも、最初の選択を貫いたほうが得でしょうか？

　「結局２つのうちから一つ選ぶんだから、どっちも一緒でしょ？」と当時の私は思ってしまったのですが…実は変えたほうがトクです！

■なっとくいかない！！

　よろしい、ならば実験だ！JavaScriptだっ！

　JavaScript版のメルセンヌ・ツイスタのライブラリがあったので、これを使ってみました。乱数は完璧です。

「モンティホール問題」実験プログラム

　ご納得頂けたと思います（ドヤ

■な、なんで？

　冷静に考えれば、わかります。

　最初にハズレを選んでいた場合、最後に残るドアは正解のドアですから、「変えた」場合に景品がもらえます。

　逆に、最初アタリを選んでいたら、「変えない」場合だけ景品がもらえます。

　よって、「変える」場合にもらえる確率は最初ハズレる確率で2/3。「変えた」場合にもらえるのは最初アタる確率で1/3。

　実験通りですね！

■えーやっぱり納得いかない

　「100個のドアのうち、最初に1つのドアを選びます。残った99個のドアのうち、一つを残して他98個のハズレのドアを司会者が開けてくれます。あなたは変えますか？」と、数を増やしてみるという説明で私は理解しました。いかがでしょう？

■

　こういった話に興味がある場合は、「ベイズ推定」について調べてみてくださいね。

派生クラスへの「変身タイミング」のC++とJavaの違い

Posted on 2012/02/21 by Kaede Fujisaki

恥ずかしながら、知らなかったので投稿です。めちゃ細かい話です。ソースはこちら。ZIPはこちら。

まとめると

派生クラスの初期化の際には、原則的に基底クラス部分を初期化した後に、派生クラスに「変身」して、派生クラス部分が初期化されるのですが、

C++は、基底クラスのコンストラクタが終わるまで派生クラスに「変身」しない。
Javaは、基底クラスのコンストラクタの実行開始時からいきなり派生クラスに「変身」済み（ただしフィールドを除く）

オブジェクト指向といえばクラス、クラスといえばオブジェクト

オブジェクトといえば初期化、初期化といえばコンストラクタ！

というわけで、こんなオブジェクト継承関係を考えてみましょう。(Sample1.java)

public class Parent{
	public Parent(){
		System.out.println("親コンストラクタだよー。");
	}
	public void method(){
		System.out.println("親のメソッドだよー。");
	}
}
public class Child extends Parent {
	public Child(){
		super();
		System.out.println("子コンストラクタだよー。");
	}
	public void method(){
		System.out.println("子供のメソッドだよー。");
	}
}

ええと、特に意味のある例が思い浮かばなかったので、安直にParentとChildです。すいません。

この状態で

public class Launch{
	public static void main(String args){
		Child child = new Child();
		child.method();
	}
}

とすると、

% java Sample1 
親コンストラクタだよー。
子コンストラクタだよー。
子供のメソッドだよー。

と表示されます。これは予想通りですよね。親クラスのコンストラクタで、親クラスのフィールドが初期化されたあとに、その派生クラスの子クラスのコンストラクタが呼ばれて、子クラスが初期化されます。入門書通りです。

コンストラクタ中に子クラスのメソッドを呼ぶ…？

さて。親クラスを元にした派生クラスを色々と作って、それらの種類で処理を分ける…というのが、一般的なケースです。

とするなら。もしかすると、基底クラスの初期化の最中に子クラスの初期化をして、その結果を使いたいと思うかもしれません。

そう思ったら、こんなコードを書くかも。(Sample2.java)

abstract class Parent{ //抽象クラスになりました。
	public Parent(){
		System.out.println("親コンストラクタだよー。");
		/* 全派生クラス共通の初期化処理がこの間に入ってる（という気持ち） */
		final int result = doInit(); //派生クラスごとで違う初期化処理
		/* ここも全派生クラス共通の初期化処理が入ってる（という気持ち） */
		System.out.println("親コンストラクタ終わりだよー。結果は"+result+"だったよー。");
	}
	public void method(){
		System.out.println("親のメソッドだよー。");
	}
	protected abstract int doInit();
}
class Child extends Parent {
	public Child(){
		super();
		System.out.println("子コンストラクタだよー。");
	}
	public void method(){
		System.out.println("子供のメソッドだよー。");
	}
	protected int doInit(){
		System.out.println("子供が初期化してるよー。");
		return 184; //特に意味はない
	}
}

実行すると、

% java Sample2
親コンストラクタだよー。
子供が初期化してるよー。
親コンストラクタ終わりだよー。結果は184だったよー。
子コンストラクタだよー。
子供のメソッドだよー。

というわけで、Javaでは、親クラスのコンストラクタを実行中でもすでに「this」は子クラスに「変身」しており、親クラスのコンストラクタから、子クラスのメソッドを呼ぶことができます。

インスタンス変数は二回初期化される

ただし。インスタンス変数は違います。先程のソース、親子両方にfieldというフィールドを入れて、親クラスを0、子クラスを1と宣言時に初期化すると…。(Sample3.java)

% java Sample3 
親コンストラクタだよー。fieldは0だったよー。
子供が初期化してるよー。
親コンストラクタ終わりだよー。結果は184だったよー。
子コンストラクタだよー。fieldは1だったよー。
子供のコンストラクタだよー。

親クラスの値0で初期化されたあと、子クラスのコンストラクタ実行前に再度初期化されます。

親クラスのコンストラクタを呼ぶ前は「何者でもない」

また、親クラスのコンストラクタ実行前は「何者にもなっていない透明な存在」です。え？どういう事かって？

こういうことはできません。

abstract class Parent{ //抽象クラスになりました。
	public Parent(int param){
		/* なにか処理 */
	}
}
class Child extends Parent {
	public Child(){
		super(getParam()); // <= 残念、コンパイルできない！
	}
	protected int getParam(){ /* 基底クラスの初期化に使う値を、事前に計算したいなあ、と */
		return 184; //特に意味はない
	}
}

「スーパータイプのコンストラクタの呼び出し前は this を参照できません。」と言われてエラーでした。

結局、それぞれの実行タイミングはどうなってるの？

クラスのフィールドの初期化は、コンストラクタ内だけでなく、フィールドの宣言時にも行うことができます。大方予想はついていると思いますが、一応調べておきましょう。(Sample4.java)

abstract class Parent{
	protected static final int log(String msg){
		System.out.println(msg);
		return 0;
	}
	protected int field = log("親クラス・フィールド宣言時");
	public Parent(){
		log("親クラス・コンストラクタ");
	}
}
class Child extends Parent {
	protected int field = log("子クラス・フィールド宣言時");
	public Child(){
		super();
		log("子クラス・コンストラクタ");
	}
}

とすると、

% java Sample4
親クラス・フィールド宣言時
親クラス・コンストラクタ
子クラス・フィールド宣言時
子クラス・コンストラクタ

というわけで、原則的に「フィールド宣言→コンストラクタ」が親から子にわたって続く感じです。コンストラクタ内からフィールドにはアクセスできますから、まあ想像通りですね。

ただし、Javaの場合、親クラスのフィールド宣言開始時ですでに子クラスに「変身」していて、メソッドがオーバーライドされていた場合、子供クラスのコンストラクタが呼ばれる前でも、そちらが呼ばれてしまいます。複数人で開発していた場合、この仕様が思いがけないバグになるかもしれません。

明確に子クラスの責任としたいメソッドじゃない場合は、コンストラクタから呼ばれるメソッドはfinal宣言したほうがいいかもですね。

ソビエトロシアC++では親クラスが子クラスに変身する！

最後のJavaと似たようなコードを書きました。(Sample.cpp)

#include <iostream>
#include <string>

using namespace std;

int log(const string& msg){
	cout << msg << endl;
	return 0;
}

class Parent{
	protected:
		int attr;// = log("親クラスフィールド初期化"); //これはできないんでした。
	public:
		Parent():
		attr(log("親クラスフィールド初期化"))
		{
			log("親クラスコンストラクタ開始");
			doInit();
			log("親クラスコンストラクタ終了");
		}
		virtual ~Parent(){
		}
		virtual void doInit(){
			log("親クラスの初期化処理");
		};
		virtual void method(){
			log("*親メソッド*");
		}
};

class Child : public Parent{
	protected:
		int attr;
	public:
		Child():
		Parent(),
		attr(log("子クラスフィールド初期化"))
		{
			log("子クラスコンストラクタ");
		};
		virtual ~Child(){
		};
		virtual void doInit(){
			log("子クラスの初期化処理");
		};
		virtual void method(){
			log("*子メソッド*");
		}
};

int main(){
	Child child;
	child.method();
	return 0;
}

そもそもフィールド宣言時に初期化できなくて、コンストラクタの初期化子に書くんでしたね。さてコンパイルです。

% ./test 
親クラスフィールド初期化
親クラスコンストラクタ開始
親クラスの初期化処理　←　子供のdoInit()じゃなくて、親のdoInit()が呼ばれてる！
親クラスコンストラクタ終了
子クラスフィールド初期化
子クラスコンストラクタ
*子メソッド*

コードの位置からすぐわかるように、Javaと同じように「フィールド初期化→コンストラクタ」の流れなのは同じです。

が、C++は親クラスの初期化が終わるまでは「厳密に親クラス」で、子クラスではないので、子クラスのメソッドを呼ぶことはできません。

子クラスに勝手にメソッドがオーバーライドされて…という事はなくなるため、この仕様はこの仕様で合理的な気がします。

まとめ

えっと、まあ、その、普通に使ってても結構気づかないことって多いんだなあ…って感じです…。

GENETOSのBGMを差し替えられるパッチ作ってみた

Posted on 2012/02/11 by Kaede Fujisaki

　以前、フリーのSTGゲーム“GENETOS”の音楽を復号化する“Oreshiki Decrypter”を公開する時に書いた、GENETOSのBGMを差し替えるための改造パッチを公開する…と言いながら忘れていましたが、最近ソースコードのフォルダを眺めていたら発見されたので配布します。

■ダウンロード

for ver 1.00(2010/11/07)

　け、結構前…。

■使い方

　ダウンロードして出てくる「_patch_genetos.EXE」を実行するとパッチが適用されます。

　次に、BGMのファイルを次のように書き換えてください。

最終面の「origin.mp3.ore」と「answer.mp3.ore」、エンディングの「rebirth.mp3.ore」はそのまま置き換えられます。“Oreshiki Decrypter”で差し替えたいmp3を暗号化し、そのまま置き換えてください。
それ以外は拡張子が変わった上で、拡張子以外のファイル名が４文字減ります。こんな感じ：
- 「little_invader.mid.ore」を差し替えたい場合は「little_inv.mp3.ore」という名前のファイルを用意してください。
- Oreshiki Decrypterを利用して差し替えたいmp3を暗号化した後、上記のようなファイル名に変更してBGMフォルダにコピーしてください。
自機が進化した後のBGMに関して、最初の数秒間が再生されません†1。予め自分で数秒間分のブランクを挿入しておく必要があります、

■パッチについて簡単な解説。

　内部では音楽を再生する関数はmidiを再生するものとMP3を再生する関数に別れています。どちらもファイル名と追加のいくつかの引数を取るもので、これを利用して、midiを再生する関数を書き換えてmp3を再生する関数にバイパスしています。

　ただしひとつ問題があって、midiを再生する関数は、ステージ開始時に一気にmidiをロードしてしかるタイミングで再生するBGMを変更する、という事ができるのですが、mp3の関数ではそれはできませんでした。この問題を解決すべくいろいろ試行錯誤した結果、自機が進化する瞬間の処理をフックしてMP3再生関数を呼んでBGMを切り替えています。

■パッチ適用時の注意。

　メニューから普通にゲームを開始する時以外の動作に関してはうまく動かないと思われます。フリープレイでちゃんと動く事とかは考えてません。

†1: 原因はよくわかりません

インターネットのカタチ：いんたーねっとがこわれた！

Posted on 2012/02/04 by Kaede Fujisaki

「Geekなぺーじ」の中の人による、「インターネットそのもの」を、”インターネットが壊れる”を切り口に、その壊れ方と直し方を通して解説した、ちょっと変わった本です。図書館をぶらぶらしてたら目についたので、読んでみました。

インターネットのカタチ―もろさが織り成す粘り強い世界―

posted with amazlet at 12.02.04

あきみち空閑洋平
オーム社
売り上げランキング: 47632

Amazon.co.jp で詳細を見る

いわゆる「インターネットの仕組み」の本とは、一味違います。もちろん、ルーティングとかDNSとか海底ケーブル網とか、そういうテクノロジーの話は沢山出てきます。

が、インターネットは、ケーブルと機械の集まりというだけではありません。人間が作って維持しているネットワークです。

機械の故障によって「壊れる(繋がらなくなる)」だけでなく、機械は問題なくても設定ミスでネットワークが「壊れる」ことも有るでしょうし、政治的な理由†1で「壊されてしまう」ことも、あるいは悪意を持った人がDDoSを仕掛けて「破壊する」こともあります。でも、そうやって壊れてしまったら、物理的に、あるいは論理的・政治的に、さらには仕様の見直しによる破壊工作の防止まで含めて、「インターネットを治す」ような仕組みも、あるのです。

この本は、そういったインターネットを取り巻き、壊れたら治して維持する、ありとあらゆる営みの視点から、インターネットを概観できる、肩肘張らずに読めるゆる～い読み物です。

いくつか本の中で私がこれは！と思ったものをご紹介。

ルーターのその先のプロバイダのその先ってどうなってるの？

私は自宅内のネットワークに関してはある程度知ってるつもりです†2。が、その先に関しては、教養番組でよくあるような「雲」以上のイメージが正直無かったですorz

私の加入しているプロバイダは、So-netです†3。So-netのようなプロバイダは、私の家のような家庭内LANをたくさん束ねて、インターネット外部への接続サービスを行っています。そのつながり方は、どのようなもので、どのようにデータのやり取りを行っているのでしょう？

Wikipediaとか読んでてもいまいちイメージがつかめなかったのですが、今回この本で可視化ツールが有ると知ったので、試してみました。

■自宅周辺のネットワークがどうなってるか調べてみる！

「自宅周辺」とか言ってますが、今大学なので大学周辺を調べます（ぁ

まずは、インターネットの住所の基本、IPアドレスを調べます。いつもの通り、診断くんで調べます。133.11.70.109だそうです。

次に、RADbのサイトにアドレスを入れて検索すると、AS番号とIPアドレスの割当範囲が分かります。（AS番号だけでしたら、Team CYMRUからも調べられます。）

このAS番号というのは、プロバイダや大学、あるいはGoogleのような大規模なネットワークを持っている団体がDNSのドメイン名のように、RIRというしかるべき団体から一意で貰ってる番号で、よく聞く「IPアドレスの割当て」は、このAS番号を持っている団体に対して行われています。恥ずかしながら、ネットワークの上位でもDHCPみたいにダイナミックに割り振ったりしてるのかなあ、とか思ってました。最終的に「IPアドレスは誰のものか？」は、ちゃんとテーブルで決まってる！のです。

さて、先ほどのRADbに入力することで、AS番号はAS2501だと分かりました（か、かなり若いのでは…）。また、133.11.70.109という番号は、133.11.0.0/16の割当のうちの一つ、だそうです。

さてさて。これから、ネットワークの可視化がやっと行えます。BGPlayというネットワーク可視化ツールを使って、調べてみましょう。

おおお、なかなかそれっぽいですね。ASの間ではBGPと呼ばれるプロトコルで通信していて、「AS2501の隣にはAS2907がいるよ！」といったメッセージを流し合っていて、その情報を使ってルーティングをしているのだそうです。恥ずかしながら知りませんでしたorz

先ほどのRADbにAS2501と入れる事で、その生のデータが取得できます。

import:     from AS2500
	           action pref=100;
	           accept ANY
import:     from AS2907
	           action pref=100;
	           accept ANY
import:     from AS7531
	           action pref=100;
	           accept AS7531
export:     to AS2500
	           announce AS2501 AS7531
export:     to AS2907
	           announce AS2501 AS7531
export:     to AS7531
	           announce ANY

さてこのルーティング情報、実はちょくちょく変わります。この可視化ツールでは下の▶ボタンを押すと、このつながりが変わっていく様を見る事ができる…はずなのですが、今私がやったところでは、あまり変わりません。どうやら、”大学だから”のようです。

お使いのプロバイダですと、結構アニメーションがくるくると動いて、同じASにつなぐにしても、色々なルートを通ってるって、分かりはずです。

基本的には、BGPにおいてAS同士は対等（なはず；自信ない）。でも、平等なこの現実社会にもリア充と非リア充がいるように、他のたくさんのネットワーク同士をつなげている「Tier1」と呼ばれる大きなASと、そのおこぼれに預かっている下々の「Tier2」のようなASが居て、大体のプロバイダはTier2以下です。下々のプロバイダは、リア充たる上位のネットワーク様に、まるで私がプロバイダと契約しているように、お金を払って繋がせていただいています（敬語）。

というわけで、ほかのネットワークにパケットを流すときには、プロバイダは流す先のASにお金を払っています（同規模程度のAS同士ではPeerといって、無料でパケットを流し合ってる所もあるようです）。またもちろん、人間のやってる組織同士ですから、その他もろもろの政治問題があって流しやすかったりそうでも無かったりするようです…。

ということで、同じASに送り届けるにしても、どのASを経由させるかは重大な問題だ、という事になります。

だからAS同士のつながりは、ちょくちょく切り替わっているって事なのかな…？…この辺は自信ないですごめんなさいorz

誰か教えて〜！！

RFCとかって、どうやって決まるの？

上が長くなったので、軽く。IETFっていうRFCを出してる所のメーリングリストとか、リアルで集まる会合で決めてるんだそうです。基本的には参加資格なしで、誰でも参加できます！

とはいえ、人間が集まっている以上、誰が言ったかで賛否が分かれたり、リアル会合に何度も出れる（ほどのお金や時間がある）人が有利になったり、はするそうで、よほどの事でもない限りいきなりちょろっとMLに顔を出しても相手にはされなさそうです。

電車内でサクッと読める

軽めのBlog記事を沢山繋げたような構成で、かなり読みやかったです。私は本を読むのはかなり遅い方で、一冊のライトノベルに三ヶ月掛けるのもままあることなのですが、2日ほどで読み終わってしまいました。ライトノベルよりも軽く読めるので、暇つぶしにいかが。

†1: 日本だと児童ポルノとか青少年健全育成条例とか
†2: 自宅サーバも含めて、自宅のネットワークはすべて私が管理しているので…一応…
†3: Gyaoだったんですが、買収されてしまいました…

ニコ動のCaptchaをやぶる

Posted on 2011/12/17 by Kaede Fujisaki

「AfterCampMeeting 2011」というイベントでのLT。

[全画面/表示されない場合]

プログラマのための文字コード技術入門；あなたなら、どう設計して拡張する？

Posted on 2011/12/04 by Kaede Fujisaki

　文字コード関連の記事で書いていた「プログラマのための文字コード技術入門」ですが、先日読み終わりました。

プログラマのための文字コード技術入門 (WEB+DB PRESS plus) (WEB+DB PRESS plusシリーズ)

posted with amazlet at 11.12.04

矢野啓介
技術評論社
売り上げランキング: 36014

Amazon.co.jp で詳細を見る

　はっきり言って凄まじくマニアックな本です。

　日本語の文字について、どのような文字が入るかと、文字を区別するための番号を決めてあるJIS X 0208と、それの拡張であるJIS X 0212、JIS X 0213といった符号化文字集合について、どの漢字がどう入っていて、のちの規格でどう拡張して…みたいな話が延々書いてあります。

　この符号化文字集合というのは、前回推定していた文字コードとはまた別の概念で、「符号化文字集合で定められた値を、実際のバイト列にどう落としこむか」を決める規格がShift_JIS、EUC-JP、ISO-2022-JP(JIS)といった「符号化方式」です。

　これについてももちろん詳しく書かれています。これらの「符号化方式」は、同じ番号（JIS区点番号）を違うバイト列に変換しているだけなので、これらの間では（ほぼ）機械的に変換を行うことができるわけですね（jcode.pl、めっちゃ懐かしいです）。

　ちなみにUnicodeはこれらの規格とはあんまり関係なく、それぞれの文字について、別の番号（Unicodeコードポイント）が決められているため、Shift_JISなどの方式と相互変換しようとすると、絶対に文字と文字の対応テーブルが必要になってきます。これに関してももちろん、結構細かく書いてあります。

　そんな感じで詳しく文字コードについて書いてるのですけど、はっきりいって、もー複雑なんですよ！これが！！

　結構集中して読んでたのですが、それでももう全然覚えてないです…。Shift_JISにしても、後々追加した漢字が使えるようになったShift_JIS-2004っていう別規格があって、どうたらこうたら…なんかもう訳わからないです＾ρ＾

　JIS X 0208やJIS X 0213も、こっちの規格とこっちの規格で文字がかぶってるだの、新しい規格で追加したせいでShift_JISにMicrosoftが独自に追加した機種依存と被ってしまっただの…。

　UnicodeとJIS X系で変換するときに、JIS X->Unicode->JIS Xってやったら元に戻るようにトリッキーな救済措置をしたら、今度はそれが仇になって、他の国の漢字と整合性が保てなくて、違う言語で同じUnicodeでの漢字がスワップしてしまったり…（”器“と”器“問題）

　もう文字コードを自力で扱ったりしないよ(世界丸見え風)と固く決心させてくれるだけでも、十二分に良書なのではないか！と思います！（割りと真剣な目で

■別の視点から読んでみる：自分が拡張しなきゃいけなくなったら、どうする？

　さて、この本で文字コードの複雑さに頭を悩ませるのも一興ですが、また違った楽しみ方があります。それは、自分が文字コードの開発者になったら、どう拡張したかな？というのを、色々考えてみるという楽しさです。それこそプログラマなら、一度は考えてみるべき！です！

　最初期の文字コ－ドは、もちろん、ASCIIに代表される英語だけの文字コ－ド。符号化文字集合と符号化方式のようなレイヤーに別れていない、素朴な仕様です。1960年代に生まれました。

　しかし、英語のアルファベットだけですから、ヨ－ロッパの国々のàみたいな別種の文字を扱うことができませんし、＄記号はあるのに、自分の国の通貨記号がないのも不便です。そして、考えなければならないのは、この時代のコンピュ－タは本当にスペックが今に比べると低かった、ということ。できる限り、ASCIIで使っている7bitの範囲内で文字を表現したかったようです（その後出てくる文字コ－ドは8bitが主流だし、どうしてなのかいまいち分からないです…7bitしか扱えないことで有名なSMTPは80年代ですし…この辺の事情詳しい人居たら教えてね！）。

　さて…どう拡張するべきでしょう…。ASCIIは、128種類の殆どを使いきってしまっています。制御文字も、きっと当時はみんな必要なものだったのでしょうから、自分たちの言語の文字に使うこともできそうにありません。

　そのとき、標準として選ばれたのが、ISO/IEC 646です。結局、ASCIIを基本としつつ、各国ごとに文字コ－ドの規格を分離し、特殊記号に関しては自分たちで決めてね…といった感じの規格です。文字コ－ドの規格自体には、「どの文字コ－ドなのか」を区別する規格はないため、別にどの文字コ－ドなのかの情報を持っていなければなりません。そう、もうこの時点で「文字化け」という概念が発生しているのです。

■超有名な円マークとバックスラッシュ問題

　たとえば、日本では、ISO 646の一種としてJIS X 0201が制定され、この規格では、ASCIIのうちの∖の代わりに¥が、˜の代わりに‾が宛がわれました。円マ－クと＼…そう、この文字化け、今でも非常によく見かけますよね！私のBlogでも、たまに円マ－クがバックスラッシュになってて、「ワンコインは∖500」みたいな文章になったりしてて、なんだかよく分からない事になってます。

　表示が化けるだけなら、まだ良い方です。そう思って、円マークとバックスラッシュに関しては、区別を適当にする…という感じで今まで対策がされてきました。が、この円マ－クとバックスラッシュの区別が適当な事を利用すると、クロスサイトスクリプティングできちゃったりします。これらの面倒な問題は、すべてこのISO 646の規格にまで遡っているのです…。。。

■三者三様の「半角カナ」「全角カナ」問題

　さらに、このJIS X 0201では、部分的に、日本語にも対応しました。でも、当時のコンピュ－タの性能は、グラフィックもCPUもあまり高く無いため、カタカナだけです（ドット数が低いと、まるっこい文字より直線的な文字のほうが表現しやすかったんですかネ）。これも、現在でも「半角カナ」として、残っています。

　この規格だけなら何の問題もありませんが、後々JIS X 0203などで拡張された際に付け加えられた「全角カナ」もあり、こちらもShift_JISやEUC-JPで使うことができます。同じ文字を二通りで表せるのは、違う文字を一通りで表してしまった円・バックスラッシュと同じく、色々と問題が発生します…。

　たとえば、「半角カナ」で「アイウエオ」と書かれた文章を検索するときに、「全角カナ」で「アイウエオ」で検索してもヒットしない、ということです。これは不便ですし、掲示板のNGワ－ドを実装するときにすり抜けられてしまったり、SPAMフィルタのために文章を単語ごとに分離させるときも、同じワ－ドが違うものになってしまったり、妙な事になってしまいます。

　そもそも、感覚的に、同じ文字が違うバイト列で表現されてるのは絶対変です。よくサービスの登録画面とかで「住所（全角で入力）」みたいなのがありますが、なんでそんな事しなきゃいけないんでしょう。カタカナはカタカナ。そうでしょう？

　う～ん、この「半角カナ」、どうするべきだったのでしょう…。EUC-JPでは、この「半角カナ」を使うには、あるエスケープシーケンスをおいた後に続けないと、使えなくなりました。これはどういう事かというと、JIS X 0201そのままのデータを、EUC-JPとして直接読むことはできません。一旦コード変換が必要になります。今では何でもありませんが、JIS X 0201のような1バイト文字コードしか扱えない環境が多く、相互でやり取りすることが多かった時代では、結構不便だったようです。

　逆に、Shift_JISはJIS X 0201をそのままにしつつ、JIS X 0201で使っていない部分に、半ば無理矢理（本来は文字が入らない、制御コードの領域も使ってしまいました）、JIS X 0213の漢字を格納しています。互換性やJIS X 0201しか扱えない環境とのデータのやり取りは簡単だったようです。が、無理やり押し込んでしまったため、例の「表示」が「侮ｦ」になる、5C問題が発生してしまいました。

　電子メールで使われるISO-2022-JPは、バッサリと切り捨ててしまいました。もし半角カナの含まれたJIS X 0201や、Shift_JIS、ISO-2022-JPから変換したい場合は、すべて「全角カナ」に統一され、全角と半角の区別が失われる事になりました。

　このように、三者三様の半角カナの扱い。どれが一番だと思います？現状ならISO-2022-JPのように廃止で良いと思うのですが、当時の状況を考えると、そうでもなかったようです。

　ちなみに、UTF-8全盛の現在でも半角カナは生き残っていますが、Unicodeの方針としてShift_JIS->Unicode->Shift_JIS、のように変換したら、元のShift_JISと同じバイト列が得られる、ということを基本としているようで、これを満たすために「半角カナ」はまだ生き残っています。Unicodeに採用されてしまった以上、半角カナはこれからもしぶとく生き残っていくでしょう。

　なお、「半角カナ」は１バイトのイメージが強いと思いますが、UnicodeやEUC-JPでは、もはやそうではありません。表示する上で半分の太さの文字にしているというだけです。

■

　似たような問題が、この本にはいくつもいくつも出てきます。これらの問題も含めて、どうするべきだったのか、当時の技術の都合も想像しながら読んで「おれのかんがえたさいきょうのしよう」を考えてみると、一興かもしれません。

この週末、東大の学園祭で同人誌を出します

Posted on 2011/11/25 by Kaede Fujisaki

　こんにちは！東大は今、年二回ある学園祭の一つ、駒場祭の真っ最中です。

　私は東大ニコ研というサークルで生放送したり、女装をしたりしている他、土日の26/27両日に開催される東大生オンリー同人誌即売会「コミックアカデミー03」において、同人誌「エミュレータはソフトなマホウ　～ハード解析”なし”で作るファミコンエミュレータ～　前編」を頒布いたします。ソースコードCD付属♪

　プログラマなら誰でも憧れる（？）ファミコンエミュレータを、ハードウェアの直接的な解析なしに、インターネット上の情報だけで実装しよう！という本です。ハードウェアの解析をしなくても、こんなエミュレータを開発できてしまいます！ただし今回は前編までで、カートリッジ・RAM・CPUの実装だけとなっています…。ごめんなさい。

　ページ数の制限もある中で、できるだけわかりやすく解説したつもり…です。解説は途中までですが、ソースコードは完全版が付属CDに収録されています。カッテネ。

　渋谷の近くにお住まいの方は、ぜひ！

■場所

　東京渋谷の近くにある、東京大学駒場キャンパスで駒場祭は開催されています。

大きな地図で見る

　この駒場キャンパスの12号館3階1233教室というところで頒布しております。

　サークルとして出ているわけではなく、本部での委託販売となっています。ご注意ください。

■

　当日は、私自身はこのコミックアカデミー会場か、５号館二階523教室で跳梁跋扈している予定です。よろしくお願いします。

■

　なお、日曜日は東大ニコ研コミュニティで「まるきゅう」のダンスのネット中継も行います。そちらもよろしくお願いします。

統計学の力を借りて、文字化け退散！　省メモリ＆実用化編

Posted on 2011/11/19 by Kaede Fujisaki

　以下の記事の続きです。最終編～♪

■abstract

　@nebutalabさんの追試結果を踏まえて、私もベクトルデータの解像度を下げる効果について検討しました。その上で、既存のライブラリ（Webkit/Chromeに組み込まれているライブラリ）と比較を行いました。

　さらにベクトルデータをlogを用いて圧縮する方法を検討したところ、既存のライブラリと同程度にまでメモリ消費を下げることができました。

　最後の仕上げとして、autotoolsを用いたライブラリとしてまとめて公開しました。

■解像度を下げてもなお特徴的なベクトルデータ

　@nebutalabさんのエントリでは、二次元でなく一次元での推定テストを行った他、二次元の場合に、ベクトルデータの解像度を下げてどれくらい推定成功率が下がってしまうかのテストを行っていらっしゃいます。

　なぜ、解像度をさげて正確性を犠牲にしてまで、ベクトルデータのサイズを小さくしなくてはいけないのでしょう？元のままだと、ベクトルデータが各エンコードごとに256×256=65536要素必要で、uint32(4バイト）で持っていると256KBも必要になってしまいます。Shift_JIS、EUC-JP、ISO-2022-JP、UTF8と4種類用意するとトータルで1MBです。実際に使おうとするとこのメモリ消費量の大きさがネックになってしまい、ソフトウェアの一部として組み込むには使いづらいからです。

　とりあえず、私の側でも解像度を下げたデータを作って見ました。

　うーん、16×16までは確実に差が分かるけど、8×8くらいから怪しいかなあ、といった感じでしょうか。

■解像度を下げて実験！

　今回は、@nebutalabさんの方法を参考に、ページ内でcharsetを指定してあるページのみをテスト用デ－タに使うことで、ノイズを排除しました。あと、方式は前回検討し疑似コードでの方式をベースに、charCntはどれかの文字コードのスコアが0より大きい物（判定として使える物）にしました。解像度を下げていくと、これは最初の擬似コードの方式と殆ど同じになります†1。

　意外にも8×8では十分判定（100バイト時点で99.907％）でき、4×4で怪しくなってきて、2×2では全然だめ、という感じのようです。それでも、Random guess（25％）よりは高く、7割程度分かってしまうようです。…確率って凄いですね。

　@nebutalabさんのものよりも成績が良いのは、おそらくやっぱり辞書データのサイズの差だと思われます。Wikipedia全文データはやはり広大みたいです…。

　99％以上の部分についてのみのグラフがこちらです。

　128×128で何故か収束が悪いですが、おおむね100バイト収集すれば収束するようです。ちょっと面白いのが、1バイトだけ使った方が、その後の50バイト分よりも判定率が良いこと！99.8%の精度が出ているので、案外これで十分！？かもしれません＾＾；

■webkitのコードと比較してみる

　Chrome/Webkitで、HTTPのレスポンスヘッダやmeta要素でのcharsetと、テキストの実際のエンコードが食い違った時に推定するために使われる†2、TextResourceDecoder::detectJapaneseEncoding(const char* data, size_t len)と、性能を比較しました。コメントから、このコードは、JVIM由来だそうです。具体的に実装を見るとわかりますが、このコードもヒューリスティック†3なアルゴリズムですが、それぞれの文字コードへの深い知識を使って実装されており、今回のアルゴリズムとは対照的といえます。

　どちらのコードも、最初の1バイトで高い性能を示し、いったんガクっと落ちる点など、非常によく似た性質を示しています。8×8の辞書サイズでは最初の方のデータのグラフが安定しませんが、おおむね同じような収束曲線を示しているように見えます（私の贔屓かな…）。なお、JVIMの実装はShift_JIS/EUC-JP/ISO-2022-JPの三種類しか判定できないので、そういう意味では私の勝ちです（ぇ

　こちらも99%以上の部分を拡大したものがこちらです。

　100バイト使うことが出来れば、わずかにですが、このwebkitのコードより良い性能を示しています。（合計で22876件のテストデ－タを使いました。誰か検定してください（えー））

　実行時間の殆どはIOなので実行速度は問題にならないと思いますが、webkitのコードよりも確実にコード量は少なく（＝省メモリ）て済んでいます。

■さらに、Logを使って圧縮しよう。

　8×8にまでベクトルサイズを下げることで、ベクトルの要素を32bitのfloatで持つと、8x8x4(bytes)*4(種類のエンコード)=1024バイトにまでベクトルデータを削減することが可能ですが、これでもwebkitの実装の256バイトよりはだいぶ大きくなってしまいます。できれば、同等のメモリ消費量程度にしたいですよね。

　もし、各ベクトルの要素を1バイトで表現するようにデ－タを圧縮する事ができれば、webkitの実装と同じ、256byte前後でベクトルデ－タが収まります。圧縮すると、展開のために少し速度が遅くなると思われますが、処理速度の大半はIOな上に、アルゴリズムは現状非常にシンプルなので、多少遅くなっても問題無いでしょう。

　まず、データの分布を見て、特性を観察しましょう。ベクトルの要素のうち、最大のものを100%として、0～1%の間の大きさの要素が何要素あるか、1～2%の間の大きさの要素が何要素があるか…という、ヒストグラムを作ってみました。

　！？…どうやら、殆どのベクトル要素は、非常に小さい部分に集中しているようです。

　となると、もし、ベクトルの要素の最大値を255とした場合に、各要素がどれくらいの割合か†4、でデ－タを表すことで圧縮してしまうと、圧縮後の要素が0～2の要素ばっかりのベクトルになってしまい、なんだかもったいないデ－タの使い方になってしまいます。また、解凍†5して元の要素を復元したときに、元々色々な値を持っていたはずの、値が小さい範囲の要素が、みんな同じ値に復元されてしまうことになります。

　デ－タの使い方がもったいない上に、精度も悪い圧縮になってしまうので、これでは圧縮としては使えません。

　では、どういう風に圧縮しましょう？小さい要素の差がつぶれて、みんな同じ値になってしまうと、もしテストデ－タを比較するときに、小さいベクトル要素ばかりが出現した場合に、みんな同じ値になってしまうので比較できなくなってしまうだろう、と思われます。逆に、非常に大きい値は、他を圧倒しているため、多少ズレてしまっても文字コ－ド別に順位を取った際の順番はあまり変わらないだろう、と考えられます。もしも圧縮するなら、小さい値をできるだけ正確に保存して、大きい値は割と目をつぶる…そんな感じが良いでしょう。

　小さい要素の値をできるだけ正確に表しつつ、大きい要素はあまり正確でなくてもいい…そこで使うのが、Logです！

　Wolfram Alpha先生に書いてもらった図です。便利ですね～。Log(x)は、xが小さい範囲では急激に増加しますが、大きくなってくると増加が緩やかになります。この関数を通すことで、値の小さい範囲の差を拡大し、大きい範囲では逆に縮小する事ができるのです。

　さてさて。というわけで、ベクトルの各要素にLogを取った後に同じようにプロットした結果がこちら。

　どうでしょう？だいぶ、グラフ上の色々なところに値が出現するようになりましたよね†6。Logを取った結果に、さらにLogを取るという二重対数というのもやってみましたが、これもそれなりに良い感じです。これを、最大値を255、最小値を0として表して†7、ベクトルデ－タを圧縮しました。

　圧縮したデ－タを、再度元に戻した場合に、元のデ－タからどれくらい”ズレ”てしまってるかを計りました。具体的には、復元後のベクトルデ－タの各要素の合計を、元デ－タの各要素の合計で割りました。

何もしない（ただ最大値＝255として1バイトで表す）
- Shift_JIS: 99.1276634489251%
- EUC: 98.3539033976696%
- ISO-2022-JP: 99.2222804703025%
- UTF-8: 98.8167690319413%
対数
- Shift_JIS: 0.392150481159483%
- EUC: 0.823989278166709%
- ISO-2022-JP: 0.419194323315878%
- UTF-8: 0.541541587104492%
二回対数
- Shift_JIS: 0.415910841860486%
- EUC: 0.77325609663897%
- ISO-2022-JP: 0.249110000167609%
- UTF-8: 0.574984371330254%

　やっぱり何もしないのでは全然駄目でしたが、対数を使うととても正確で、二回対数にするとさらに少し改善するみたいです。どちらにしてもでも1%以下しか変わらないため、きっと良い結果が得られると考えられます。

■webkitと同程度のメモリ消費に抑えても、同じ程度の性能が出る

　その結果がこちら。

　どうでしょう？一回対数の場合、1バイトだけ使ったときの推定成功率は大きく下がりましたが、元のグラフから殆ど外れないグラフが書けました。100バイト使った時の成功率は、元の結果と全く同じ。デ－タを1/4に圧縮しましたが、副作用はありませんでした。

　二回対数は正直かなり重いので、実装するには一回対数を使って圧縮すると良さそうです。

■Ｃ言語のライブラリとして実装しよう！＆autotoolsの使い方

　githubで公開中！

　さてさてさてて。すべての条件がそろいました。十分な判定率と十分なメモリ消費量、それでもシンプルなアルゴリズムを用意できました。ならば、これをライブラリにしない手は、ありませんよね！？

　とてもシンプルなライブラリですから、せっかくなので、autotoolsの使い方も調べてみましょう†8。一度は自分で./configure & make & make installなパッケ－ジ作ってみたいですよね！ね！！（

　とりあえず、こんな構成でコードを書きました。（完成品のソース見ながらの方が分かりやすいと思います）

include
- csetguess.h
src
- data.h
- data.c
- csetguess.c

　include以下が/usr/includeとかに入れるためのヘッダで、


enum CSET_GUESS_CHARSETS {
        UNKNWON=-1,
        SJIS=0,
        Shift_JIS=0,
        EUC=1,
        EUC_JP=1,
        JIS=2,
        ISO_2022_JP=2,
        UTF8=3,
};

enum CSET_GUESS_CHARSETS cset_guess(const unsigned char* data, unsigned int len);

　こんな感じのシグネチャが入っています。src以下はその具体的な実装です。cset_guessはcsetguess.cに入っています。

　さて。これからautotoolsを使って、ビルド環境を作りましょう。autotoolsは、仕様が頻繁に変わってしまうのか、公式のドキュメントを見ても、なんかよく分かりません…。一応、作業の流れはWikipediaの図が参考になりました。Googleで検索するときも、できるだけ最新の情報を見るのをお勧めします…。

　まず、トップディレクトリにMakefile.amを、こんな感じで作ります。


lib_LTLIBRARIES = libcsetguess.la
libcsetguess_la_SOURCES= \
	src/data.h \
	src/data.c \
	src/csetguess.c \
	include/csetguess.h

includedir=$(prefix)/include
include_HEADERS=include/csetguess.h

　次に、autoscanをして、configure.scanをつくり、これをconfigure.acにリネームします。


$ autoscan
$ mv configure.scan configure.ac

　configure.acのうち、


AC_INIT([FULL-PACKAGE-NAME], [VERSION], [BUG-REPORT-ADDRESS])

　となってるところを、とりあえず自分のものに併せて変更しました。


AC_INIT([libcsetguess], [1.0], [nasda60@hotmail.com])

　Wikipedaの図にそって、aclocal、autoheader、automakeします。このとき、READMEやNEWS、CHANGELOGといったファイルが無いので、automakeするときに作って貰えるように、-a -cというオプションを付けます。


$ aclocal
$ autoheader
$ automake -a -c
configure.ac: no proper invocation of AM_INIT_AUTOMAKE was found.
configure.ac: You should verify that configure.ac invokes AM_INIT_AUTOMAKE,
configure.ac: that aclocal.m4 is present in the top-level directory,
configure.ac: and that aclocal.m4 was recently regenerated (using aclocal).
Makefile.am: installing `./INSTALL'
Makefile.am: required file `./NEWS' not found
Makefile.am: required file `./README' not found
Makefile.am: required file `./AUTHORS' not found
Makefile.am: required file `./ChangeLog' not found
Makefile.am: installing `./COPYING' using GNU General Public License v3 file
Makefile.am:     Consider adding the COPYING file to the version control system
Makefile.am:     for your code, to avoid questions about which license your project uses.
configure.ac:7: required file `config.h.in' not found
Makefile.am:3: Libtool library used but `LIBTOOL' is undefined
Makefile.am:3:   The usual way to define `LIBTOOL' is to add `AC_PROG_LIBTOOL'
Makefile.am:3:   to `configure.ac' and run `aclocal' and `autoconf' again.
Makefile.am:3:   If `AC_PROG_LIBTOOL' is in `configure.ac', make sure
Makefile.am:3:   its definition is in aclocal's search path.
Makefile.am: installing `./depcomp'
/usr/share/automake-1.11/am/depend2.am: am__fastdepCC does not appear in AM_CONDITIONAL
/usr/share/automake-1.11/am/depend2.am:   The usual way to define `am__fastdepCC' is to add `AC_PROG_CC'
/usr/share/automake-1.11/am/depend2.am:   to `configure.ac' and run `aclocal' and `autoconf' again.
/usr/share/automake-1.11/am/depend2.am: AMDEP does not appear in AM_CONDITIONAL
/usr/share/automake-1.11/am/depend2.am:   The usual way to define `AMDEP' is to add one of the compiler tests
/usr/share/automake-1.11/am/depend2.am:     AC_PROG_CC, AC_PROG_CXX, AC_PROG_CXX, AC_PROG_OBJC,
/usr/share/automake-1.11/am/depend2.am:     AM_PROG_AS, AM_PROG_GCJ, AM_PROG_UPC
/usr/share/automake-1.11/am/depend2.am:   to `configure.ac' and run `aclocal' and `autoconf' again.

　た、たくさんエラーメッセージが出てしまいましたが、これらを地道に修正します。


@@ -2,12 +2,15 @@
 # Process this file with autoconf to produce a configure script.

 AC_PREREQ([2.67])
 AC_INIT([libcsetguess], [1.0], [nasda60@hotmail.com])
+AM_INIT_AUTOMAKE([foreign])
 AC_CONFIG_SRCDIR([include/csetguess.h])
 AC_CONFIG_HEADERS([config.h])
+AC_CONFIG_MACRO_DIR([m4])
 
 # Checks for programs.
 AC_PROG_CC
+AC_PROG_LIBTOOL
 
 # Checks for libraries.

　AM_INIT_AUTOMAKEの引数がよく分からないのですが、とりあえずこれで良いみたいです（そもそもこのAM_INIT_AUTOMAKEの解説、古いのでは…？よくわかりません…）。

　さて、修正したところで、再度aclocalから行って行きます。


$ aclocal
$ autoheader
$ automake -a -c
configure.ac:13: installing `./config.guess'
configure.ac:13: installing `./config.sub'
configure.ac:6: installing `./install-sh'
configure.ac:13: required file `./ltmain.sh' not found
configure.ac:6: installing `./missing'

　”configure.ac:13: required file `./ltmain.sh’ not found”するには…最初libtoolizeというのをしなければならなかったようです（Wikipediaに書いてないぞ～）


$ libtoolize
libtoolize: putting auxiliary files in `.'.
libtoolize: linking file `./ltmain.sh'
libtoolize: putting macros in AC_CONFIG_MACRO_DIR, `m4'.
libtoolize: linking file `m4/libtool.m4'
libtoolize: linking file `m4/ltoptions.m4'
libtoolize: linking file `m4/ltsugar.m4'
libtoolize: linking file `m4/ltversion.m4'
libtoolize: linking file `m4/lt~obsolete.m4'

$ automake -a -c

　うまく行きました。さて最後にautoconfすることで、ついにあのconfigureスクリプトが生成されます。


$ autoconf

　さて、これでconfigureしましょう。


$ ./configure
....
configure: creating ./config.status
config.status: creating Makefile
config.status: creating config.h
config.status: executing depfiles commands
config.status: executing libtool commands

　おおお！！これで、make & make installができるようになります。

　以上をまとめると、

Makefile.amを書く
autoscanして、configure.scanを生成し、configure.acにリネームして、編集する。
以下のコマンドを実行していく。
- libtoolize
- aclocal
- autoheader
- automake -a -c
- autoconf
./configureスクリプトができて、晴れて完成。

　こんな感じです。はしょりまくりですが、とりあえずの雰囲気掴みには…なってると良いな…。とりあえず、Makefile.amとconfigure.acさえあれば全部自動生成されるので、この二つ以外はリポジトリに入れなくても大丈夫です。

■ブラウザに実装しないの？

　技術的障壁が二つほど横たわっております。

Chrome/Firefoxともに、拡張機能からページのエンコ－ド設定を変更する方法が見当たらない
ペ－ジのテキストを、拡張機能からバイナリとして取得する方法が見つからない

　後者は、Ajax的にリクエストを投げて、その結果をバイナリとして受け取る事でできそうなのですが、わざわざ再度リクエストを投げるのは計算機資源の無駄だと思います…。前者はセキュリティ的問題でしょうか…？

　さらに、ブラウザ本体に組み込むというのも考えたのですが、このパソコンではどうやらメモリ不足みたいで、コンパイルに時間がかかりすぎて、デバッグや開発がどうにも不可能そうです…orz

　解決方法をご存知の方がいらしたら、教えてください！　

■まだちょっとやり残した気がすること

　今回のJVIM由来のwebkit内のライブラリは、実はいつも使われるわけでなく、HTTPヘッダやmetaタグで指定したエンコードと実際のエンコードが食い違っている場合にのみ使われます。

　そして、一切無指定だった場合はICUというUnicodeのライブラリを使ってエンコードの推定を行っています。

　このICUもずいぶん高性能なライブラリのようなのですが、どうしてChrome/Webkit/Safariは文字化けが起きがちなのか、デバッグして調べたかったのです…が…。PCのメモリがどうも足りないみたいで、出来ませんでした。悲しい。

■資料

実験に用いたソースコードをgithubで公開します。あまり読む価値はないと思いますが、一応証拠です。
使ったスプレッドシート：記事では使わなかった数字とかも、とりあえず全部入ってます。これも一応証拠として。

†1: どこの要素も0でなくなっていくので
†2: だから、エンコードが無指定な時には使われません。
†3: 確率的に当たる、ということ
†4: つまり、圧縮後の要素＝（元の要素／要素の最大値）＊255
†5: 元の要素＝圧縮後の要素 * （要素の最大値／255）
†6: 情報科学っぽく言えば、エントロピ－が高くなりました。
†7: 実際には、最大値の255乗根を底としたlogを取りました
†8: むしろ、こっちメインです＾＾；

ledyba.orgへ移転、メールアドレス変更のお知らせ

Posted on 2011/11/18 by Kaede Fujisaki

　先週土曜日より、独自ドメインledyba.orgへの移転を行いました。人生初ドメインです！

　ledyba.ddo.jpも、ホスティング元のDynamic DNS Doがサービスを停止するまでは、リダイレクトを提供します。（こうして”歴史的経緯”が増えていく…ｗ）

■RSSの移行をお願いします！

　RSSのアドレスも、Blog移転に伴い変更になりました。以前のアドレスからもアクセスできるようにはしていますが、できれば移行をよろしくお願いします。以下のリンクをクリックする事で、新しいフィ－ドをあなたのRSSリ－ダに登録できます。

　こちらのサイトを参考にボタンを作ってみました。

■メールアドレスも変更になりました

　メールアドレスも、今までpsi@science.mi.to†1を使っておりましたが、今回変更になりました。以下が新しいアドレスになります！

■経緯

　今までメールアドレスpsi@science.mi.toをホストしていたサービス、”CLUB BBQ“が終了になってしまいました。そのためどこかへの移行が迫られるわけですが…正直、もうメールアドレスを変えたくありません！

　そして、「そういえばledyba.ddo.jp/も無料サービスだったなあ…」と思い出しました。ddo.jpがサービスを終了すると、メ－ルアドレスと同じように使えなくなってしまうという可能性に、…やっとこさ気づいたのです！orz

　メ－ルアドレスの乗り換え先に新たなサ－ビスを探すよりも、ドメイン名を取ってしまった方が良いだろうという結論に至り、ドメインを移行しました。

　今後ともψ（プサイ）の興味関心空間をよろしくお願いします♪

†1: もう使えなくなるから、SPAM対策とか一切考えずに書いちゃえ！ｗ

統計学の力を借りて、文字化け退散！　解決＆高速化編

Posted on 2011/11/06 by Kaede Fujisaki

　前回までのあらすじ。

文字化けをどうにかしたい。
それぞれのエンコードは、バイトとバイトのつながりに特徴がある。（数バイトで一文字表すから）
これを、ベクトルに見立てて、それぞれの「角度」を調べて、一番近いので分類してみた。
ある場合†1について、エンコードに含まれるASCII部分が邪魔をして推定成功率がいまいち←イマココ！

■単純に除いてみる　だけ！

　前回、RFCの全データを使って作ったASCIIのデータがありました。これがASCIIの使われている領域ですから、これを判断に使わなきゃ良いんじゃないの？

　…というわけで、ASCII部分を除外して作ってみた各エンコードの画像がこちら。（クリックすると拡大します、ぜひクリックしてみてください）

　ASCIIと使用領域がかぶっているISO-2022-JP(JIS)でもちゃんと要素が残っているので、使えそうです。

　かなり安直な方法†2ですが、とりあえず実験です。

■それで実験してみる

　どうです！どの素材データを使っても、安定して分類出来るようになりました！ASCIIの場合、全部のエンコードに対する角度(cosθ）が0になるので、これで判断が出来ます。ただ、バックスラッシュ”∖”とチルダ”˜”の純粋ASCIIか、それぞれ円マーク”¥”とオーバーライン”‾”のJIS X 0201†3なのかは判断できません。

　かなり安直な方法でしたが、効果はあるようです。

■さらにパフォーマンスを高めたい？

　現状の方法では、特徴ベクトルの作成と、ベクトルの距離の比較の二つのパートから成り立っており、それぞれの計算量は

特徴ベクトル作成：文章の長さnに対してO(n)
ベクトルの比較：文章にかかわらずO(1)

　であり、計算量は比較的少なくて済みます（ただし計算量理論的な意味で）。

　というのも、ベクトルの比較はO(1)ですが定数項が大きい（65536回のかけ算計算）です。ASCIIを除外し、更にすべてのエンコードで0になっているところを除外したところ、43394つの座標軸†4（約66％）に減らせましたが、それでも多いと言わざるを得ません。

■ファイルの長さはどれくらい必要なの？

　ベクトル比較のO(1)は難しそうなのでとりあえず放置して、まず特徴ベクトルの作成をどれくらいケチれるか実験してみましょう。直感的に考えて、特徴ベクトル作成に使う文字数を増やしていっても、どこかで成功率が飽和していく事が予想されます。

　Wikipediaの全文のソースを素材データ†5とし、青空文庫のうち、十分に長い小説2500本を使って実験を行いました。青空文庫は全文Shift_JISですが、それをiconvを使ってそれぞれのエンコードバージョンを作りました†6。

　文章の1000バイト目†7から1バイト、2バイト、3バイト…100バイトと切っていって、それぞれで推定を行わせ、成功率を測定しました。

　20バイト前後（つまり、日本語で言うと10文字程度）で飽和し、それ以降は十分な精度が得られるようです。青空文庫は非常に綺麗な日本語であることを考えても、100バイト（日本語で50文字前後）もサンプルを集めれば十二分でしょう。

　余談として、ISO-2022-JPとUTF-8は若干グラフの立ち上がりが悪いですが、これはUTF-8が他のエンコ－ドと違い、日本語１文字を表すのに3～4バイト必要なこと、そしてISO-2022-JPはASCIIとかなり近い領域を使っていることが関係しているのかもしれません。

■日本語が50文字もあれば十二分な精度が出る→計算量を減らす工夫が可能に！

　さて、この結果から、50文字程度の日本語を集めてくれば、十分推定可能だろうという事が判明しました。この結果を生かすと、65536回もかけ算をしなくてもコサイン類似度の比較が可能だと考えられます。

　具体的には、コサイン類似度を次のようなフローで求める事で、O(1)かつ十分に小さい定数項の計算量でにエンコードの推定ができ、以上の実験結果と同じ結果が得られ、十分な推定精度が得られるのではないでしょうか？

■ほぼO(1)に高速化した推定フロー

　まず、それぞれのエンコードのベクトル、V[SJIS]、V[EUC]、V[JIS]、V[UTF8]を用意しておきます。さらに、ベクトルの各要素を長さで割って、長さ１の単位ベクトル†8にしておいてください。

　この時、Shift_JISのベクトルの、１バイト目がAで、2バイト目がBの要素にはV[SJIS][A][B]のようにアクセス出来るとします。

　さらに、スコア決定のために使う変数、score[SJIS]、score[EUC]、score[JIS]、score[UTF8]、そしてサンプルを集めた数を記録する変数charCntを用意しておき、すべて0で初期化します。

文章を先頭から1バイトずつ見ていきます。
文章中に非ASCIIな文字が現れたら、ループに入ります。
1. 現在のバイトと、一つ前のバイトを記録し、一つ前をX,現在をYとします。
2. score[SJIS] += V[SJIS][X][Y]のように、それぞれのエンコードのscoreに、対応するベクトルの値を加えます。
3. charCntに1を加えます。
4. charCntが（例えば）100†9を超えたら、ループを終了します。
5. 現在のバイトがASCIIなら、ループを終了します。
charCntが100を超えていなければ、2へ戻り、再びその位置からバイトを見ていき、次の非ASCII文字に備えます。
それぞれのscoreのうち、一番大きい値だったものが、この文章のエンコードと推定されます。

　ミソは、まず素材データのベクトルの長さを1に揃える†10こと、さらに、比較データのベクトルは作らず、直接内積を求めること、比較データのベクトルの長さで割らなくても、最終的な値の大小関係には影響を及ぼさない事†11です。

■擬似コード

　わ、わかりづらいですね。Cっぽい疑似言語でかきます。


//例えばvector[SJIS][0x30][0x21]とすると、
//SJISのベクトルで、1バイト目が0x30で、2バイト目が0x21であるときの、ベクトルの要素が取れる
//...というようなデータを事前に作成しておき、さらにベクトルの長さは各エンコードで揃えてください。
float vector[][][];

void compare(const char* text)
{
    float score[];//SJIS,EUC-JP,ISO-2022-JP,UTF8の4つの要素を用意して0で初期化。
    int charCnt = 0;
    for(int i=1;i<strlen(text);i++)
    {
    
        if(!isAscii(text[i])){
            /* サンプルを集めるためのループ */
            for(;i<strlen(text);i++,chrCnt++){
                //それぞれのベクトルを足す
                score[SJIS] += vector[SJIS][text[i-1]][text[i]];
                score[EUC-JP] += vector[EUC-JP][text[i-1]][text[i]];
                score[ISO-2022-JP] += vector[ISO-2022-JP][text[i-1]][text[i]];
                score[UTF8] += vector[UTF8][text[i-1]][text[i]];
                if(isAscii(text[i]){ //再びasciiが現れたら、再び非ASCII文字を探す
                    break;
                }
                if(charCnt >= 100){ //十分なサンプルを採取したら
                    goto judge; //推定に移る（二段ループから抜けるので、break）
                }
            }
        }
    }

    judge: /* スコアからエンコードを決定する */

    float maxScore = 0;
    encoding trueEncoding = null;
    /* 一番スコアが高いエンコードを選んでるだけ */
    foreach(それぞれのエンコードEについて)
    {
        if(score[E] > maxScore){
            trueEncoding = E;
            maxScore = score[E];
        }
    }
    
    print("このテキストのエンコードは"+trueEncode+"です。");
}

　説明用に書いただけなので、効率はあまりよろしくありません。

■さらに精度を高めたい？

　また、今回はあえて文字コードに関する知識を殆ど使っていない†12ので、これを使うことで精度が多少は上げられると考えられます。むしろ、その知識をわからなかったらこういう統計的な手法に頼るべきではないかという気もします。。

■他に使えそうな分類手法は？

■ベイズフィルタ

　まず、SPAMでも使われてる、ベイズフィルタ（PDF)なんてどうでしょう？このPDFにも書いてある通り、文章から「トークン」を作り出す際に、二文字ずつに区切って使うという、まさに今回使ったのと非常に似た手法「bigram」も存在するし、スパムと違って「未知の単語」は存在しないので†13、使えるかもしれません。しかし、計算量はこちらの方が大きそうです。

■回帰分析

　回帰分析なんてどうでしょうか？分類するための方法ではないので少し違いますけど、正しいエンコードの時は１、間違ったエンコードの時は0を返すような係数（このページの例だとβ）を決定して、それを使ってみると良いかもしれませんね。

　この分野はあまり詳しくないので、もしも他の色々な手法とか、ページとかあったら、ぜひ教えてくださいね！

■最後に

　あまりにもうまく推定できすぎてて怖いので誰か追試希望

■追記

　実際に追試していただけました！@nebutalabさんありがとうございます！辞書デ－タの解像度を下げる方法は、今度の休日に試してみる予定です。

■実験資料

データが記録された、odfファイルです。グラフの元データなどがあります。
実験に使用したソースコード。実験しながら突貫工事で作ったので、非常に遅いです。一応証拠。今回初めてC#使いましたが、なかなか良い感じ。Mono使えばLinuxでも安心。

■

　さらに実用化を目指した最終編がこちら！

†1: 基準データに、Webサイト上からクロールしてきたHTMLファイルを用いた場合
†2: だって、ASCIIでの出現頻度の情報を一切使わないという事ですから…
†3: つまり、Shift_JISやEUC-JPで英語しか書いていないのか
†4: 「ベクトル」に見立てたんでした。ですから、座標軸ということになります。格好つけて基底ベクトルでも良いけど。
†5: 比較する時に、前提知識として使う側のデータ
†6: 変換できなかった文字は無視しました。仕方ないです。。。
†7: 最初の方には、純粋な日本語以外が混じっているので
†8: １でなくても同じ長さなら良いです。
†9: 大体日本語50文字分
†10: 1でなくても、もちろん構いません。
†11: だからベクトルを作る必要はないのです
†12: 折角本まで買って読んでるのに…
†13: 原理的に65536種類しか存在しません