2011-11-07
統計的手法で文字コード（UTF-8/EUC/JIS/SHIFT_JIS）を判別する方法の追試
どうも初めまして。最初のエントリが他人のアイデアの追試というのもあれですが、面白かったので私も自分で書いてみました。
元記事： 統計学の力を借りて、文字化け退散！ - ψ（プサイ）の興味関心空間
http://ledyba.org/2011/11/06004312.php
Permalink | コメント(0) | トラックバック(1) | 04:44 
このアルゴリズムの概要
（１）隣接する２バイト（i番目とi+1番目）の組の頻度分布（256x256のマップ）を文字コード既知のテキストデータについて計算すると、文字コードごとに明らかに大きな差が出る（元記事を参照）。これを辞書データとして保管する。
（２）この文字コードの辞書データを65536(=256^2)次元のベクトルとしてとらえ、それぞれと、文字コード未知のテキストデータを一部切り出して同様に計算した65536次元のベクトルの内積を取る。辞書データは同じノルムに規格化しておく。*1こうすることで、未知データがどれくらいそれぞれのエンコードに似ているかが計算できる。未知データとの内積が一番大きいエンコードを採用。
メリット
いったん辞書データを作ってしまえば、あとは計算コストは小さい。テキストの一部（〜100バイトの並び）に対しての内積の計算コストはほとんど無視できるレベルに小さい。アイデアはコロンブスの卵的でクール。このままで実用的かどうかはともかく、文字コードの詳細な知識を用いずに判別出来るのがコンセプト的に面白い。
改善の余地
辞書データのサイズが大きい。一つ、すぐ考えられる改良は、内積の線形性（）を用いて、一つの辞書ベクトルデータをその他から差し引いて消すことだが、サイズが3/4になるだけで劇的とは言いがたい。辞書データのマップがぱっと見からして大きく異なることを考えると、辞書データの特徴を上手く抽出してもっとサイズを小さく出来そうに思われる。
Permalink | コメント(0) | トラックバック(0) | 04:44
私の実装と、計算結果
データ取得
日本語の辞書データ作成のための素材は青空文庫からダウンロードした。
aozoraget.rb
ASCIIは、以下のサイトからrfcのデータ（RFCs 5001-5500）をダウンロードし、解凍。
http://www.rfc-editor.org/download.html
辞書データ作成
青空文庫の元データがSHIFT JISなので、そこからRubyのiconvで他のエンコード（EUC-JP, UTF-8, ISO-2022-JP (JIS)）のテキストを作成した。iバイト目と(i+1)バイト目の相関図を作り規格化して保存。
aozora.rb
ASCIIデータも解析。
rfcascii.rb
日本語の辞書データからASCIIのデータを差し引く。（ASCIIで0でない値を持つ点を、日本語データではすべて0にする）。
subtract.rb
テスト
テスト用のテキストデータはGoogleの検索結果（日本語サイト限定；ただし時々英文が混じる）からのリンク先HTMLを取得。webget.rb
例えば
ruby webget.rb AKB48でAKB48の検索結果を200件保存。
metaタグで文字コードが指定されていないHTMLは除外し、指定された文字コードを正解として、プログラムが推定した文字コードと比べる。読み込みバイト数（非ASCII）は100バイトにした。ASCIIが多い／テキストが短いという理由で１００バイト非アスキー文字を読めないケースがあるが、そういうケースは除外してから失敗率を計算した。*2
encode_test.rb
失敗率は、1.1%であった。
Permalink | コメント(0) | トラックバック(0) | 04:44
辞書データを小さく出来ないか？
１次元のみ
連続した２バイトの相関ではなく、単にバイトの値の頻度分布を見る、という考え方。頻度分布を見ると、差が結構あるように見え、このアイデアは良さそうに思える。
元記事を読んでしばらく考えていたときに思いついた。２バイト相関よりも先に思いつくべきアイデアかもしれない。結果は以下の通り。
2dto1d.rb
encode_test_1d.rb
失敗率が4.7%。ただ辞書サイズは２次元の場合の２５６分の１。それで失敗率が４倍…。良いのか悪いのかよく分からん。
平均化
次に、2バイト相関のまま、辞書データのマップの隣り合うピクセルを平均化してみて結果を比較してみた。
makecoursevectors.rb
左から順に、EUC, UTF-8, JIS, SHIFT JIS。上の4つが元のデータ、下の4つが8x8ピクセルで平均化した例。
こうやって、粗視化してもなおエンコードごとの見た目の違いがあるので期待できた。
結果は以下の通り。（encode_test_coarse.rb）
32x32pixelの粗視化のケースでは、辞書サイズが元の1000分の１で、失敗率が3%。１次元の時よりは若干良いという感じだろうか。
Permalink | コメント(0) | トラックバック(0) | 04:52
既存の方法との比較
既存のライブラリの文字コード判別成功率はどのくらいかというのを調べると、2004年と古いがこんなのがあった。
たむら::日本語文字コードの自動判定
これは短い単語で判別しているようなので単純には比較できないが、これらの方法はおそらく長い文字列でも成功率は上がらないと思われるので、テキストが長ければpsi氏の方法が有利になるだろう（追記: そもそもこれらは皆そんなに成功率が高くない。リンク先に挙げられている中で、Guess.guessというのは統計的手法を使っているそうで、成績も>96%と割と高い）。
Permalink | コメント(0) | トラックバック(0) | 04:44
まとめ
psi氏の元サイトでは20バイトでほぼ100%の成功率に飽和しているのに対して、私の実装では100バイトまで読んで99％なので、私のは辞書データもあまり良くないのかもしれない。青空文庫の文章は記号や数字はほとんど含まないし、カタカナも少ないと思われる。Wikipediaのほうが良さそう。
ちなみに、判定に失敗しているのは英文のサイトが多い。この文章を書いていて気がついたのだけど、私の実装では、判別関数の答えの選択肢の中にASCIIが入っていない。ASCIIをASCIIとして捕らえられれば成功率が一気に上がりそう。元サイトはそうしているのかな。それと、UTF-8の辞書データの見た目が結構元サイトと違う。私の辞書データが青空文庫から取ってきているので、記号やアルファベットがほとんど無く、カタカナも少ないことが影響しているかも。
異なるエンコード間での辞書の「形」の違いを保ったまま、特徴を上手く抽出してサイズを小さく出来れば良いのだけど。結局それは画像認識みたいな世界になってしまい、どんどんややこしくなってしまうのかもしれない。
追記：高次元行列の次元を、内積をあまり変えずに下げる、ランダムプロジェクションという方法があるそうだ。ただこれは判定対象の文字列にたいしても次元縮小の行列計算が必要なのでその行列を保持する必要がある。なので辞書サイズは小さくならないかな...。
Permalink | コメント(0) | トラックバック(0) | 04:44
余談： ブラウザ上にこの機能を実装？
この機能をGreasemonkeyで実装したいなと思ったのだけど、loadイベントでmetaタグを追加 or 変更しても文字コード解釈の変更は効かなかった。
Chromeでは、スクリプトの冒頭で@run-at document-startというオプションを指定すると早く実行できるとのこと（まだheadすら存在しない状態）だが、この段階で何かすれば上手くいくかも。
Permalink | コメント(0) | トラックバック(0) | 04:44
