なぜJavaScriptで「76287755398823936」が正しく表示できないか、あるいはなぜRubyでも表せないか。

Posted on

 「Twitter住所特定実験」を開発中に気づいた事です。取得したツイートをサーバからJSONでクライアント側のJSに送る処理があって、当初この時にTwitterのツイートのIDをJSONに数値として含めて送っていました。

 が、JavaScriptではこの値を受信してeval()した†1際、うまく変換することができず、たとえばChrome/Firefoxでは「76287755398823940」となり、微妙に異なった数値になってしまいました。

 以下をクリックすることで、実際に実行できます。

javascript:alert(76287755398823936)

 IE8/9だと「76287755398823930」となり、まだ微妙に違った値になります。

doubleの精度の問題??

 まず疑われたのはdoubleの精度の問題。一部では有名な話で、JavaScriptでは数値はすべてdoubleで持っています。doubleは64ビットの浮動小数点なので、64bit整数より若干精度が落ち(具体的には53ビットしか精度がありません)、かなり大きな(64bit整数の限界に近いような値は)うまく表現することができません。

 で、実際に実験してみると…。

$ cat test.asm
global  _main
extern  _printf
section .text
_main:
;問題の値を読み込む
push 0x010f074f
push 0x31424000
fild qword [esp]
;64ビット浮動小数点としてスタックに保存←おそらくここで下位ビットが失われる
fstp qword [esp]
;表示
push    messagef
call    _printf
add     esp, 12
ret
messagef:
db      "%f", 0x0a, 0
$ nasm -fwin32 test.asm
$ gcc -o test.exe test.obj
$ ./test.exe
76287755398823936.000000

あれれ!?せっかくアセンブラまで書いたのに

実は余裕でdoubleで表せる

 Doubleの精度は53ビットまでですが、この「76287755398823936」という値は43ビットの精度があれば表すことができます。この値を2進数で表すと、

100001111000001110100111100110001010000100100000000000000(57ビット)

 となります。これは57ビットありますが、doubleで十分表すことができます。えっdoubleって53ビットまでってさっき言ったじゃん?

 それについて詳しく納得していくために、doubleの仕組みを見ていきましょう。

 doubleはIEEE754に基づく浮動小数点で…。能書きはいいさね、実物を見ながら解説します。

 問題の値のdoubleでの表現は次の通りです。

0/10000110111/0000111100000111010011110011000101000010010000000000

 スラッシュで区切った三つの構造からできています:左から符号、指数、仮数。

 浮動小数点では、理系の本でよく見るような値の表現をします。つまり、

+4.2195 * 10³m

 みたいな感じですね。42195mじゃなくて、+4.2195 * 10³mです。

符号(0)

 先ほどの例で言うと、「+」のところを現しています。

 1ビットの値で、0ならプラス、1ならマイナスの値で有ることを示します。

指数(10000110111)

 先程の例で言えば、「³」の部分にあたります。

 11ビットの値で、仮数で表される値が2の何乗されるかを表します。ただし、この値は本当の値より1023大きく表現されています。-2(マイナス二乗)のように小さな値を示す場合に困らないようにするための表現です†2。これをバイアスする、と言います。

仮数(0000111100000111010011110011000101000010010000000000)

 残りの52ビットの値です。先程の(略)、「4.2195」に対応します。

 doubleでは10進数の小数ではなく、二進数の小数を表します。

 よって、値は必ず1.01011110… * 2xxxxのように表す、つまり小数点より大きな部分は必ず1とするように指数を調整することができます(正規化)。

 そこで、doubleでは最初の1を省略して残りの小数点以下の部分だけをここに記入しています。つまり、この仮数は、

1.0000111100000111010011110011000101000010010000000000

 という二進数の小数を表している、ということになります。

 最初の1ビットを省略してるので、実際に表現できる桁数が1ビット増えるんです。仮数部分が52ビットしかないのに、精度が52ビットでなく53ビットなのは、このためです。

基数

 先ほどだと10の何乗かをかけていましたが、doubleでは2の何乗をかけています。

まとめ

 以上をまとめると、doubleのデータは符号、仮数、指数の部分に分けられて、

 (-1)符号 * 仮数 * 2指数

 の値を示す、ということがわかりました。

問題の値をdoubleに手動で変換してみよう。

 問題の値は、

100001111000001110100111100110001010000100100000000000000

でした。これを実際に表して先ほどしめしたのと一致することを確かめましょう。まずは2進小数での表現になおします。10進数と同じ、小数点を移動させるだけですよ。

1.000011110000011101001111001100010100001001 * 256

 ほら、こうすると最後の0が消えて43桁の二進数になったでしょう!だから53ビット精度で表せるはずです。

 上の説明とにらめっこしながらパラメータを決めると…

符号:0(プラスだから)

指数:56+1023 = 1079(1023でバイアスします)

仮数:000011110000011101001111001100010100001001(二進数)

(小数点以下だけをdoubleには記入します;けち表現)

これを並べると…

0/10000110111/0000111100000111010011110011000101000010010000000000

 元に戻りました!とりあえず、doubleでもちゃんと表現できるんだってこと、理解してもらえましたか?

問題は入力側?出力側?

 となると、これはブラウザのどこかでバグが起きてるということになります。

 さて、問題の切り分けを行いましょう。この問題は、2つのうちのどちらかで起こってると思われます。

  • 入力側(ソースコードに書かれた文字列をdoubleに変換する際に起こっている)
  • 出力側(doubleを文字列に変換する際に起こっている)

 で、切り分けるために実際に試してみたのがこれ。

javascript:alert(76287755398823936/1024)

 割り算してみました。本当に内部の表現でも76287755398823940になってる(=入力側の問題)なら1024では割り切れないから何かしらの少数が出ると思われますし、もし実は内部表現は正しくなってる(=出力側の問題)なら、きっと桁数が減ってうまく表示できると思われます。

 で、結果は「74499761131664」になったと思います。これは正しい結果です

Rubyでも起きる!

 いつ書こうか悩みましたが、この問題はRubyでも発生します。

$ ruby1.9.1 -e "puts 76287755398823936.to_f"
76287755398823940.0

次回に続きます

 今から続きを書きますが、長くなりすぎたのでちょっと分割。とりあえずV8のissueに投げておきましたので、ゴミのような英語でも良いならそちらへ…。

続きかけた

 つづきです:

やっぱりdoubleでは「76287755398823936」は表現できない

  • †1: といいつつprototype.js頼りですが
  • †2: 補数表現じゃだめだったんだろうか?

SVNのデフォルト無視設定

Posted on

 引っかかってしまって悩んだので備忘録的に書いておきます。

 SVNでは、一切設定をしていなくても特定の拡張子をデフォルトで無視するようになっています。

 設定ファイル(UNIXでは~/.subversion/.config、windows版ではC:\Users\<ユーザ名>\AppData\Roaming\Subversion\config)内では、一切設定していない場合このようになっています。

# global-ignores = *.o *.lo *.la *.al .libs *.so *.so.[0-9]* *.a *.pyc *.pyo
#   *.rej *~ #*# .#* .*.swp .DS_Store

 これを読む限りだとコメントアウトされてるから無視されなさそうな感じがしますが、実は無視されます。(設定例を示すのではなく、デフォルト値を示すコメントみたいで…。)

$ touch test.a
$ svn st
$ svn st --no-ignore
I       test.a

 明示的にこれらを共有したい場合は、svn addに–no-ignoreを設定するか、上記の設定ファイルをコメントアウトして無視設定を外すなど工夫が必要です。

# こうすれば無視しなくなる
global-ignores =
$ svn add --no-ignore test.a
A         test.a

 現在ノートPCとデスクトップPCでSVNを使って開発環境を共有してるのですが、この仕様でひどく苦労しました…。Bazaarに移行しようかな、やっぱり…。

Twitterで住所がバレる!?「Twitter住所特定実験」

Posted on

なにやら物騒なタイトルで。たまにはタイトル一本釣り。

リア充の皆様。AndroidにiPhoneといったスマートフォンを活用してリアルを充実させていらっしゃることと存じます。今回、私どもは、皆様のスマートフォンからTwitterへ送信することができる位置情報から、住所を特定できるのでは無いか、というありがちだけど実際検証した人は居ない†1仮説に基づき、実際にそれを行えるのかどうかやってみました。

今回開発したアプリでは、過去のツイートのうち、位置情報を持っている物を抜き出してGoogleMaps上に配置します。このアプリでは自分の位置情報のみを取得するようにしていますが、誰でも取得できる情報です。

実例と結果

こちらからアクセスしてください。

使い方も解説します。

20110626_01.jpg

この画面で「Twitter経由でログインする!」をクリックすると、このようにOAuthの認証画面が現れます。ログインを押して続行できます。

20110626_02.jpg

ログインに成功すると、このような画面になりますので、「ロード」を押してツイートの読み込みを開始してください。

20110626_03.jpg

うまく読み込むと、こんな感じで地図上にマッピングされます。このψ(プサイ)という人は関東から…出ていないようです…w

20110626_04.jpg

ズームしていくと…つくばエクスプレスユーザーだと一目で分かってしまいますーー;;

20110626_05.jpg

自宅周辺では、たくさんのピンが立っているのが特徴なのはもちろん、こういった自宅でしてるっぽいツイートがあるのも特徴です。

住所を特定するコツ

単に位置情報だけでは通勤・通学で使う駅等で呟いてることが案外多かたりで、それだけで住所まで絞り込むのは難しいです。

ですので、発言内容も手がかりにしてみてください。住所だけじゃなくてよく使うレストランとかも特定できます←父親のアカウントで検証済み、こがねちゃん弁当乙

色々と生活パターンが分かって怖い…^^;こち亀でGPSの大きな装置を背負って生活してもらう!なんて話が100巻~120巻くらいにありましたけど、それが現実になってるんだな~、って感じです。もちろん、背負わなきゃいけないほど大きな装置ではありあませんが。

住所が第三者からでも特定できちゃいそう!どうすれば?

Twitterの設定画面から、あなたの位置情報をすべて消すことができます。

20110626_twitter-acount-settings.jpg

書かれている通り、大体30分くらい時間が必要なようです。何か怖いと感じたら消してしまって良いと思います。

そもそも

位置情報って活用されてるんでしょうか?私はなんとな~くiPhoneの時は毎回入れていましたけど、冷静に考えるとあんまりいらない機能である気がして仕方がありません…w

政情不安とか地震とかの超リアルタイム緊急時だったら案外活用されてるのかな。

その他

sessionでOAuth用のtokenの受け渡しとかが出来るのが便利~。やっぱりフレームワーク使うとサクサクできていいですね~。

  • †1: Google先生調べ

録画したアニメのファイル名を自動で書き換えて整理しよう:「ShoboCal_Renamer」

Posted on

 現在、このサーバは「foltia」という録画ソフトとPT2を組み合わせた、アニメ録画サーバを兼ねています。このfoltiaでは、ファイル名を以下のような形で格納しています:

1725-35-20100607-1730.m2t
(しょぼいカレンダの番組ID)-(話数)-(日付)-(時間).拡張子

 このファイル名の書式は機械が扱う分には簡単なのですが、人間が読むのはちょっとしんどいです(だって、番組ID1725って何なのか知らないし…)。というわけで、これをしょぼいカレンダーのDBに問い合せ、こんな感じの名前にしてくれるソフトを作ってみました:

あにゃまる探偵 キルミンずぅ 第35話 ダブルでお任せ!ハグハグリーダー!? (20100607-1730).m2t

 ファイル名の書式は入力/出力ともに自由にかつ割と簡単に設定可能ですので、foltia以外でも使えるかもしれませんね。

ダウンロード

githubからDLしてください。

オプションの指定

面倒なのでhelpをコピー!(ぉ

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
ShoboCal_Renamer 1.0 (2011/04/28)
written by PSI ( / )
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
usage: ruby shobo_cal.rb [options] files or directories
-i, --in_format FORMAT           入力ファイルのフォーマットを指定してください。
-o, --out_format FORMAT          出力ファイルのフォーマットを指定してください。
-d, --dry-run                    ファイル名を実際には書き換えません。
-r, --recursive                  再帰的に実行します。
-e, --except FILENAME            指定したファイルは除外します。
-y                               上書きが必要な際に、その旨を聞きません。
-h, --help                       このメッセージを表示します
--version                    バージョンを表示します。

 こんな感じで使えます。

カレントフォルダのファイルを全て処理
> ruby shobo_cal.rb .
mp4に変換してあるのだけ処理したい。
> ruby shobo_cal.rb *.mp4
入力ファイル名、出力ファイル名のフォーマットを指定して、カレントフォルダのファイルを処理する。
> ruby shobo_cal.rb \
-i %tid%-%stid%-%date%-%time%.%ext% \
-o %title% 第%stid%話 %subtitle% (%date%-%time%).%ext% \
.

ファイル名のフォーマットについて

 入力ファイル内の”%キーワード%”で囲んだ部分の数字を読み取り、出力ファイル名の対応する”%キーワード%”に書き出します。基本的に数字縛りです。

 ただし、以下の例外があります。

  • 入力ファイル名で%tid%で指定した番号のアニメのタイトルを、出力側で%title%として使えます。
  • 入力ファイル名で%stid%で指定した番号のアニメのサブタイトルを、出力側で%subtitle%として使えます。
  • %ext%は特殊で、数字以外でも受け付けます。拡張子用です。

文字列⇔数値文字参照相互変換ページ

Posted on

数値実態参照というのは、HTMLやXMLで直接記述できない文字を記述するための方法です。HTMLを書いた事のある方は、一度は「&amp;」とか「&lt;」とか見たことがあるんじゃないでしょうか。これらはHTMLのいわゆる”タグ”を表記したりするのに使うので、直接書くとタグの一部なのかどうか区別が付かなくなっちゃいます。だから、このように迂回して書くことで混同されるのを避けます。

HTMLやXMLには「&」を「&amp;」と表すだけでなく、「&#38;」と数字で表すこともでき、前者を文字実体参照、後者を数値文字参照と呼びます。前者の文字実体参照では表せる文字は限られますが、後者の数字文字参照ではUNICODEで表せる文字ならどんな文字でも表すことができます。

今回はこの文字と数値文字参照の相互変換、つまり「☆」を「&#9734;」に変換したり、逆に「&#9825;」を「♡」に変換したりしてくれるスクリプトです。たまに使う、かつありそうで無いスクリプトだったので昔作ったやつを公開します。

20110113.png

rails2.xの**_remoteをrails3.xに機械的に移植するには

Posted on

 「UFO大好き霊子さん」をRails2.x系から3.x系に移植するに当たってぶち当たった問題のひとつです。かなり汎用性のある内容と思われるので、今回こちらにメモしておきます。

 めんどくさい人は最後だけ見てね。

rails2系でのお手軽Ajax

 Rails2系では、こんなヘルパを書くことで簡単なAjax通信ができます。

<%= link_to_remote 'イイネ!', :url => {:controller => 'votes', :action => 'create', :moderate => 'yes', :post_id => @post.id}, :update => "post_voting_#{@post.id}" %>

 こうすることで、’イイネ!’というリンクが現れます。これをクリックすると、VotesコントローラのCreateアクションがpost_idとmoderate=yesというパラメータで呼ばれ、その結果が”post_voting_#{@post.id}”というIDを持つ要素のinnerHTMLに書きこまれます。殆どJavaScriptを意識すること無く書けるので、とても便利で楽でした。

rails3系では”:remote=>true”で出来ると言うものの…

 rails3系では「link_to_remote」が廃止され、代わりに「link_to」に:remote=>trueというオプションが加わりました。が、完全互換ではなく、:updateオプションはありません。

 rails3.x系で正攻法で今までと同じことをするには、ビューの元の部分を

<%= link_to 'イイネ!', {:controller => 'votes', :action => 'create', :moderate => 'yes', :post_id => @post.id}, :remote=>true %>

 と書き換え、さらにこの上でVotes#createがJavaScriptをrenderして返さなければなりません。たとえば、”view/votes/create.js.erb”を作って、

Element.update($("post_voting_<%= @post.id %>"),'投票ありがとう!');

 みたいな感じですね。正直めんどくさい。

移植のため、Prototype.jsだけで機械的になんとか移植するには!

 正直めんどくさいので、最小の手順でなんとかしましょう。Rails3系では、JavaScriptとHTML部分が完全に分離され、上記のlink_toで:remote=>trueをしても出力されたHTMLにはこのようにJavaScriptは一切含まれていません。こんな出力です:

<a href="/votes?moderate=true&amp;post_id=1" data-remote="true" rel="nofollow">イイネ!</a>

 ではどうやってJavaScriptで通信してるのかというと、rails.jsを見ればわかりますが、”data-remote”が指定されてる要素に対して”click”イベントハンドラを追加することで処理しています。こんな感じ:

document.on("click", "a[data-remote]", function(event, element) {
if (event.stopped) return;
handleRemote(element);
event.stop();
});

 で、Ajax通信がとりあえず終わったらajax:competeイベント、成功するとajax:successイベントが、失敗するとajax:failureイベントが投げられます。rails.jsのイカの部分でゲソ:

function handleRemote(element) {
(略)
new Ajax.Request(url, {
method: method,
parameters: params,
evalScripts: true,
onComplete:    function(request) { element.fire("ajax:complete", request); },
onSuccess:     function(request) { element.fire("ajax:success",  request); },
onFailure:     function(request) { element.fire("ajax:failure",  request); }
});
(略)
}

 じゃ、このイベントを活用すれば良いんじゃなイカ?というわけで、イベントを追加して結果を流しこめばおk。こんなのをapplication.jsにでも追加しましょう:

document.on("ajax:success", "a[data-remote]", function(event, element) {
alert(event.memo.responseText); //結果が出てくる
});

 あれ?結果を書きこむ先は?

 link_toでは任意の属性を出力される要素に追加することができるので、これを使いましょう。また、createはpostメソッドなので、それも指定します。

<%= link_to_remote 'イイネ!', {:controller => 'votes', :action => 'create', :moderate => 'yes', :post_id => @post.id}, :remote=>true, 'data-update'=>"post_voting_#{@post.id}", 'data-method'=>:post %>

 application.jsではこのようにして結果を書き込みます:

document.on("ajax:success", "a[data-update]", function(event, element) {
Element.update($(element.readAttribute('data-update')), event.memo.responseText);
});

 これで目的は達成されました。

手順まとめ

1:link_to_remoteは廃止されたので、link_toに書き換えて:remote=>trueを追加する。

 URLオプションの渡し方も微妙に変わってるので注意†1。:updateは’data-update’に変更し、アクションがpostの場合は’data-method’=>’post’も末尾に追加。

<%= link_to_remote 'イイネ!', :url => {:controller => 'votes', :action => 'create', :moderate => 'yes', :post_id => @post.id}, :update => "post_voting_#{@post.id}" %>

を、次のように変更します。

<%= link_to 'イイネ!', {:controller => 'votes', :action => 'create', :moderate => 'yes', :post_id => @post.id}, :remote=>true, 'data-update'=>"post_voting_#{@post.id}", 'data-method'=>:post %>

2:application.jsにこんな内容を追加する。

document.on("ajax:success", "a[data-update]", function(event, element) {
Element.update($(element.readAttribute('data-update')), event.memo.responseText);
});

以上です。Rails3のAjaxでHTMLを返してjQueryで処理する – とはえ領域を参考にしつつ、jQueryを使わない方法を模索しました。

  • †1: link_toが三つ引数を取るようになり、その二つ目がurlオプション

オカルト共有サイト「UFO大好き霊子さん」、完全復活のお知らせ

Posted on

運命の2012年まであと10ヶ月、霊子さんが帰ってきたぞっ!

 2009年に開始したしばらく後、アップデートがめんどくさいという諸事情により停止していた世界初?のオカルトスポット共有サイトUFO大好き霊子さん」ですが、2012年に世界が崩壊すると聞いて霊子さんも黙って居られなくなったようです。今回、URLも移転しながら完全復活と相成りました。

 立ち絵も得た霊子さんの活躍に刮目せよっ!イラストはりあたんです。

20110226.png

ついに立ち絵を得た霊子さん!

20110226reiko.png

 前述の通り霊子さんのキャラクターデザインは友人のりあたんがやってくれました、ありがとー!

 霊子さんは…えーと…なんか昔私が注文時に語った中二設定が有った気がしますが覚えてません!輪廻転生がどうとか運命がどうとかそんな感じの設定だったと思います!

 霊子さん初公開は私の大学受験の直前だったんですね。そりゃ落ちるわ。

GENETOSの音楽を聞こう!-“Oreshiki Decrypter”

Posted on

 なんか最近プログラミング・STGネタを投稿しなさすぎなので、たまにはそっち方面を投稿するテストw

 進化するシューティングゲーム”GENETOS”が最近一番の個人的ヒット作です!ゲームシステムがゲーム進行にあわせ進化してくという発想の斬新さ、STGの歴史をうまくまとめ上げた構成力、ドラマチックな演出、遊びやすい難易度…。そしてBGMです!特に最終面のBGMはステージ演出と相まって最高です!

 今回、そのGENETOSのBGMや画像ファイルに掛けられてる暗号を解除するツールを作成しました。ソースつき。

 また、このツールを利用することで、BGMを暗号化することもできます。BGMの差し替えも可能です!(※制限あり、後述)

ダウンロード

 ライセンスはGPL3です。(アーカイブ内のLICENSE.TXTを参照)

使い方

 GENETOSの、bgmフォルダ内の”○○○.mp3.ore”ファイル、または”○○○.mid.ore”を”oreshiki.exe”にドラッグアンドドロップすると同じフォルダに復号化されたファイルがでてきます。同様に、img内の.oreファイルも復号化できます。

20110123_01.png

 なお、soundフォルダ内に入っている効果音ファイルは実は暗号化されてないので、.wav.oreを.wavに変更するだけで再生することができます。

解説

 ファイルの先頭128バイトを、”oreshikioreshikioreshiki…..”という”oreshiki”がぐるぐると連続する文字列とxorを取っただけです。つまり、ファイルの大部分は平文ですw

 これを、再生直前に復号化して、再生が終わったら再び暗号化して再生できないようにする、という方法で暗号化しています。たぶんライブラリがメモリ上に展開されたmp3ファイルの再生に対応していなくて、その仕様と妥協しあった結果、でしょうか?

BGM差し替え

 .mp3ファイルや.midファイルをこのソフトにドラッグアンドドロップすることで暗号化することもできます!このソフトで暗号化したファイルを、元のBGMのファイルと入れ替えることでBGMの差し替えを行うことができます。

 ただしファイルフォーマットのチェックがシビアなのか、にこさうんど#等、ネット上から拾ってきたmp3はそのままでは再生に失敗することも多いので、一度wavに戻してからlame等で再エンコードして使うのを推奨します。

 さらに、この方法ではステージがmidiのステージはmidiのファイルで、mp3のステージはmp3ででしか差し替えることができません。プログラムを書き換えれば可能で、一応そのための改造パッチも作ってあります。もう少しテストした上で公開できそうなら公開する予定ですが、いつになるやら。

磯野ー!ワードサラダ作ってアフィリエイト付スパムブログしようぜー!

Posted on

 この記事は「[痛デバドラ] /dev/louise_love作ってみた [Linux]」の解説記事です。内部でルイズコピペを自動生成するために使った、ワードサラダの技術について解説しています。

ワードサラダ??

 みなさんはワードサラダってご存知でしょうか。サンプルとしてこのBlogを上げておきます。なんだか、日本語が変じゃありませんか?ところどころ読めるけど、なんだか変なような…。

着目すべきは、「核抑止力」を「強化」するという表現である。。

これについては核武装大腸がんの予防論を参照。。

 核武装大腸がん???なんじゃそら。

 こういった、ぱっと見日本語に見えるんだけど、ちゃんと読むと意味不明、という文章を「ワードサラダ」と呼びます。†1スパマーがプログラムで自動生成して、スパム広告用のBlogに利用しているみたいです。†2

 さて、こんな文章どうやれば作れるんでしょう?ワードサラダの作り方を書いてあるサイトは結構あるんですが、ちゃんと動くソースコードが貼ってあるサイトはなかなかないんで、実際にやってみましょう。

実際にRubyで作ってみよう

 ソースコードは「[痛デバドラ] /dev/louise_love作ってみた [Linux]」の「辞書作成ユーティリティ」の中にありますので、DLしてみてください。githubでも公開していて、Webから見るならこちらの方が便利かもしれません。

 なお、利用にはYahoo!デベロッパーネットワークのアプリケーションIDが必要です(OAuthは利用しません)。取得したIDは、parser.rb冒頭の「APP_ID」にセットしてください。

大まかな流れ

  1. 文章を形態素解析
  2. マルコフ連鎖のための辞書を作成
  3. 辞書に基づいて実際にマルコフ連鎖して文章を生成

形態素解析

 形態素解析とは、文章を解析して、単語にわけ、それぞれの品詞についても調べる事です。受験の時に古文で同じことを手動でさせられましたが(涙)、受験でも何でもありませんのでコンピュータに自動で解析させましょう。

 形態素解析のソフトにはMeCab等のローカルのライブラリを使うのが定石みたいですが、インストールがめんどくさいので、Yahoo!の構文解析WebAPIを使おうと思います。Web経由なんであまり高速に大量のデータは処理はできませんが、まあ実験には十分でしょう。

 さらに係り受け解析の結果も使うとそれっぽい日本語が作れるようですが、目的がルイズコピペの無限生成なんで、そこまでやらなくてもそれっぽい文章ができると思います。係受け解析の結果も利用するうまい文章作成ソフトができたら/あったら教えてください。

 以下、実際に行なってるコードです。「libparser.rb」内にあります。

class YahooParser < Parser
	API_SERVER = 'jlp.yahooapis.jp'
	API_URL = '/MAService/V1/parse';
	BOM_UTF8 = [0xef, 0xbb, 0xbf].pack("c3")
	def initialize(api_id = APP_ID)
		@data = "appid=#{api_id}&results=ma&sentence="
	end
	def parse(text)
		http = Net::HTTP.new(API_SERVER);
		resp = http.post(API_URL,@data+URI.encode("#{text}"));
		if resp.code != '200'
			raise "Yahoo! Japan Parser unavailable. Return Code:#{resp.code}"
		end
		body = resp.body;
		doc = REXML::Document.new(body).elements['ResultSet/ma_result/word_list/'];
		text = Text.new();
		doc.elements.each('word') {|item|
			surface = item.elements['surface'].text if item.elements['surface'] != nil
			next if surface.empty? || surface == BOM_UTF8
			reading = item.elements['reading'].text if item.elements['reading'] != nil
			pos = item.elements['pos'].text if item.elements['pos'] != nil
			baseform = item.elements['baseform'].text if item.elements['baseform'] != nil
			text << Word.new(surface,reading,pos,baseform)
		}
		return text;
	end
end

 概ね、’net/http’を使ってAPIのURLにPOSTで文章を送り、結果(XMLで帰ってきます)を’rexml/document’で読み込んで、形態素解析の結果を得るだけです。あえて上げれば、”elements[‘ResultSet/ma_result/word_list/’]”として、DOMを操作する手間を少し省くのがコツ…?

 それぞれの要素の意味は、

  • surface:字面です。「桃色」だったら「桃色」
  • reading:読み方です。「桃色」だったら「ももいろ」
  • pos:品詞です。「桃色」だったら「名詞」
  • baseform:動詞だった場合の”終止形”です。「届け」だったら「届く」。でも、今回の文章生成には使ってません。

マルコフ連鎖のための辞書を作成

 さて、以上の形態素解析は自然言語をコンピュータで扱うなら定番の処理で、ワードサラダ生成の処理はここからが本番です。”markov.rb”内にあります。

class Dic
	def initialize()
		@dic = Hash.new();
		@dic2 = Hash.new();
		@size = 0;
	end
	def add(text)
		if @first == nil
			@first = text[0]
			@second = text[1]
		end
		#二階
		for i in 0..text.size-2
			word = text[i]
			if @dic[word.reading] == nil
				@dic[word.reading] = Array.new
			end
			@dic[word.reading] << text[i+1]
			@size += 1;
		end
		#三階
		for i in 0..text.size-3
			word = text[i]
			word2 = text[i+1]
			if @dic2[word.reading] == nil
				@dic2[word.reading] = Hash.new
			end
			if @dic2[word.reading][word2.reading] == nil
				@dic2[word.reading][word2.reading] = Array.new
			end
			@dic2[word.reading][word2.reading] << text[i+2]
		end
	end
=begin
・・・
(略)
・・・
=end
end

 簡単にいえば、「ある単語の後にはどんな単語が来るか」というインデックスをつくっています。

20100907_louise01.png

 こういう感じの対応表をハッシュと配列を使って記録しています。ハッシュのキーには字面ではなくよみがなを使っていて、これはなんとなくです。なお、この図とは違って同じ単語も何度でも登録していて、一応後で文章を生成したときに、「ルイズ」の後の単語の出現頻度が元の文章と同じになるように調整しています。

 さらに、これだけだと文章があまりにも不安定になるので、「ルイズ/へ」→「届け」、という、ハッシュのキーが二段階になっている辞書もつくっています。これが「三階のマルコフ連鎖」と書かれているところです。

辞書に基づいて実際にマルコフ連鎖して文章を生成

 というわけで、作った辞書を使って実際に文章を生成してみましょう。同じくmarkov.rb内にあります。

class Dic
=begin
・・・
(略)
・・・
=end
	def next(word = nil,word2 = nil)
		if word != nil && word2 != nil
			# 三階の連鎖
			array = @dic2[word.reading][word2.reading];
			if array == nil #辞書に入っていない場合は、二階のマルコフ連鎖を行う
				array = @dic[word2.reading];
			end
			return array[rand(array.length)];
		end
		# 最初
		if word == nil && word2 == nil
			return @first
		end
		# どちらかnullでない方
		left = (word == nil ? word2 : word);
		# 次
		if left == @first
			return @second
		end
		# どっちかが足りない=二階の連鎖を行わざるをえない
		array = @dic[left.reading];
		return array[rand(array.length)];
	end
end

 このdic#next()に、ふたつ前の単語といっこ前の単語を渡すと、今度出力されるべき単語が返されます。

 上で作った辞書からランダムに選ぶだけです。三階のための辞書は場合によっては組み合わせによって該当する辞書が空の場合があるので、その場合は二階の辞書を使います。(二階の辞書は、文章の最後の単語以外は必ず対応する単語があります)

実際につくった文章

% ruby markov.rb <文章>

 とすると実際に文章が生成されます。copipe/内にいくつか文章がすでにあります。

ルイズコピペ

ルイズ!ルイズ!ルイズ・フランソワーズたんの桃色ブロンドの髪をクンカクンカしたいお!モフモフ!髪髪モフモフ!カリカリモフモフ…きゅんきゅい!!!!にゃあああああああ!かわいい!ルイズ!ルイズぅぅうううわぁああああああああああああああああああああああ!!

小説11巻のルイズちゃんは現実じゃないんだねっ!

この!ちきしょ!やめてやる!!

あっあんああっああんあアン様ぁあああ!!いやぁああああああああああああん!!!あぁあ!!俺の想いよルイズへ届け!!

あっあんああっああんあアン様ぁあ!!あ…小説もアニメもよく考えたら…

ルイズちゃんは現実じゃない?にゃああああ…あっあっー!あぁああああああ!!!

あぁ!クンカクンカ!

ルイズルイズぅううぁわぁああああああああああああ!!

スーハースーハー!

吉野家

そんな事より1よ、ボケが。

150円。

お前は本当につゆだくで、それに大盛りギョク(玉子)。これ最強。

そしたらなんか人がめちゃくちゃいっぱいで座れないんです。吉野家。

よーしパパ特盛頼んじゃうぞー、とか言ってるの。もう見てらんない。

そこでまたぶち切れですよ。ボケが。

ねぎだくってなさいってこった。

素人にはお薦め出来ない。

Uの字テーブルの向かいに座った奴といつ喧嘩が始まってもおかしくない、

刺すか刺されるか、そんな雰囲気がいいんじゃねーか。おめでてーな。

お前は本当につゆだくを食いたいのかと。

そこでまたぶち切れですよ。ボケが。

吉野家ってのはな、もっと殺伐としてるべきなんだよ。ボケが。

得意げな顔して何が、つゆだくって言いたいだけ

ステーキを食べたくなったので

ステーキを食べたくなったのでステーキの話を書きますが、とある日僕が気づいたのです!

やっぱりそうだ、確信した!僕の好きな食べ物は、ステーキより高いステーキソースさえあれば、そもそも本体は肉でステーキ。ちょっと新ワードですが。

それ以来、ステーキソースをかけて食べるのでは!?

ってことで、食べる!うわーこれもうまい!!

やっぱりそうだ、確信した!僕の好きな食べ物は、ステーキより高いステーキソースをかけて食べるのでは!?

と、盛り上がったところで本題に行きます。

結果から言えば牛となんら変わりませんでしたYO!

ということで、食べる!うわーこれもうまい!!

という点です。

それ以来、ステーキソースでステーキを食べておりました。

しかし!ようやく今日気づいたのです!

と、

 割とサクサク読めて、でも意味がさっぱり分からない感覚は再現できましたかね?そういえば、難しい本読んだ時とかもそんな気分になるよね…。

 はっ!哲学の論文をこれに掛けたら誰も分からないのでは!?

  • †1: 他の例としてこのサイトを挙げておきます。
  • †2: このBlogだと広告が貼ってませんが…一体なんのために作ったんだ、このBlog。

「一応動く」Linux用デバイスドライバをつくろう

Posted on

 これは「[痛デバドラ] /dev/louise_love作ってみた [Linux]」の解説記事です。

 今回は「Linux2.6系(今回は2.6.32)からドライバとして認識されるには最低限何をしないといけないのか」をまとめてみます。

 えらく貧相な話ですが、最初のとっかかりとしては需要のある話かなあ、と。というかですね、自分自身が欲しかったのですよ。

キャラクタ型とブロック型デバイス

 Linuxのデバイスは、おおよそ二つの種類に分けられる…らしいです。ブロック型というのは固定長の長さずつでしか入出力出来ないデバイスで、キャラクタ型はそれ以外、だそうです。とりあえず、The Linux Kernel APIを見ると別々にAPIが定義されてるので、OSからもかなり別物として定義されているようです。

 今回は、とりあえず情報も多く楽なキャラクタ型デバイスを作ります。

サンプルソースコード

[痛デバドラ] /dev/louise_love作ってみた [Linux]」のソースコードを使って解説します。githubでも公開していて、Webから見るならこちらの方が便利かもしれません。

デバイスドライバに最低限必要な関数

 カーネルモジュールとして名乗るために、名前やライセンスを名乗る必要があります。

MODULE_AUTHOR("PSI");
MODULE_DESCRIPTION("\"I love Louise tan!\" MODULE");
MODULE_LICENSE("GPL");

 なお、”MODULE_LICENSE(“GPL”);”ですが、これがオープンソース系ライセンスでないととロードした時に

Warning: loading /lib/modules/..../***.o will taint the kernel: non-GPL License - Proprietary

という感じのワーニングメッセージが出るそうですが、Linuxantという会社は

MODULE_LICENSE("GPL\0for files in the \"GPL\" directory; for others, only LICENSE file applies");

 としてその汚染メッセージの表示を回避したとか…。よう考えるわ。

 さて。まず、初期化と終了のための関数が必要です。初期化はinit_module、終了処理はcleanup_moduleという関数で行ってください。どうしても別の名前が良い時は、

module_init( 初期化する関数名 );
module_exit( 終了処理をする関数名 );

 というのを関数外に書くことで代用できます。

初期化処理

int  init_module( void ){
	if ( register_chrdev( 0x0721, "louise_love", &louise_fops ) ) {
		printk( KERN_INFO "louise_love : louise chan ha genjitsu ja nai!?\n" );
		return -EBUSY;
	}
	buildDictionary();//ルイズコピペ表示のための辞書作成処理
	printk( KERN_INFO "louise_love : kunka kunka.\n" );
	return 0;
}

 0を返すと初期化に成功したとカーネルが判断し、ロードされます。register_chrdevでデバイスとしてカーネルに登録でき、この時の0x0721はメジャー番号と言って、あとで/dev/louise_loveとドライバの紐付けを行う際に必要な番号、”louise_love”はデバイスドライバの名前(lsmodしたときに見れるやつ)、louise_fopsはfile_operations構造体で、カーネルからデバイスを操作するときに使われる関数で、あとで定義します。

 register_chrdevの詳しい説明はこちらで。

 printkというのが出てきますが、これはprintfのカーネル版で、dmesgした時等に表示されます。フォーマットストリングの前にはKERN_INFO等を付けないと表示されません。詳しくはこちら。

終了処理

void cleanup_module( void ){
	unregister_chrdev( 0x0721, "louise_love" );
	printk( KERN_INFO "louise_love : Harukeginia no louise he todoke !!\n" );
}

 unregister_chrdevでアンロードするだけです。特に説明しません。詳しくはこちら

デバイス操作関数

 カーネルはregister_chrdevに渡すfile_operations構造体に記された関数を通してデバイスを操作します。デバイスドライバを作るには、そのうち最低限以下を実装しなければなりません。

  • open
  • release
  • readかwrite

 ここを見てプロトタイプの通りに実装してください。

 open( struct inode* inode, struct file* filp )のinodeはとりあえず無視していいみたいで、filpのfilp->private_dataに自分でkmallocを使って確保したデータを渡すことで、このデータも使ってwriteやreadが制御できます。

 あとは多分ソース見れば分かるかな…?

デバイスドライバをコンパイルするための最低限のMakefile

 ”-DMODULE -D__KERNEL__”を付ければ普通にコンパイルできるよ!って話もあったんですが出来ませんでした。-Iとかも色々いじったりもしたんですが通りません。昔の話みたいです。

 というわけで、こちらのサイトのMakefileを流用しましょう。

 ファイル名はMakefile(先頭大文字)じゃないとエラーが出るみたいです。

 今回は、このMakefileにこんな行も追加してインストール・アンインストールもできるようになっています。

install: all
	sudo mknod /dev/louise_love c 0x0721 0
	sudo chmod 0666 /dev/louise_love
	sudo insmod louise_love.ko

uninstall:
	sudo rmmod louise_love
	sudo rm -f /dev/louise_love

 mknodで特殊ファイルを作成&0x0721というメジャー番号を使って作成しています。cはキャラクタデバイスで、0x0721はメジャー番号で、register_chrdevしたときの数字とあわせてください。0(マイナー番号)はちょっとよくわかりまへん…。マニュアルはこちら

 chmod 666はただたんに、誰でも読み書きできるようにしているだけです。

 特殊ファイルを作ったあとにinsmodして作ったカーネルモジュールを読み込んで、/dev/louise_loveの制御を作ったドライバに任せています。

 uninstallでrmmod <モジュール名>することでドライバをアンロード、スペシャルファイルは普通にrmdirで削除できます。

 今回分かったんですが、bashでのif文はこういう構造なんですね。

if <条件:[ -e /tmp/...]など>; ←文の句切れ
then コマンド1; ←then~コマンドまでで一文
else コマンド2; 同様 else~コマンドで一文
fi

 いやーこれに気づかずに結構時間が掛かりました…。thenとコマンド1のあいだ、elseとコマンド2のあいだに;をいれるとエラーがでちゃうんだもん。

さらなる情報を得るには(参考サイト一覧)

 デバイスドライバのインターフェーイスは割と変わるみたいなので、他の記事を参考にする場合はバージョン情報や書かれた月日は参考にしたほうがいいです。

 ちなみにこの記事はカーネル2.6.32を対象に書いています。