ごみ - 衒思力発電所

ごみ

TWOR 解析 (2)

2009/10/11 | ごみ | コメント (6)

前回の続き．

http://dvorak.jp/archive/twor_subekey_sample.zip (9.5 MiB)

今回は，前回得た上記の一次元のサンプリングデータから何がわかるか^*1調べてみよう，というようなことをやってみる．

いきなりものものしいアルゴリズムで始めるのもなんなので，手始めに各 1 文字の出現頻度を調べてみる．「特に頻出の文字」「頻度が少ない文字」などが存在するかしないかが調べられることになる．

twor1.py とかこういうのを書いて実行：

直感的に以下のふたつのことが推測できる^*2．

ほとんどの文字の出現頻度は同じ
スペースの出現頻度は，他の文字の 6 倍

文字単位で見るとスペース除けば全て同じ頻度っていうのは，意外性がないというか，完全ランダムならそうだろうし常識的にそうだろうなっていう気がしますが，もうちょっと後の考察を踏まえると再び意味を持つかなと思うので，一応押さえておきたいポイント．

スペースの頻度が他の文字の 6 倍（きれいな倍数）というのは素直に面白い結果．これだけ見ても，出題文字列は単なるランダムではなくある程度考えられたロジックに基づくものなんじゃないかなぁという香りはしてくる．

今度は文字単位ではなくて，隣り合った 2 文字をセットにして，2 文字セットの出現頻度を見てみよう^*3．たとえば「ab」と「ac」では頻度が異なるだろうか？とかいう話ね．

先ほどのスクリプトを手直しして，n 文字セットでカウントできるようにする（twor2.py）．出力を使いやすいように，区切り文字はタブ文字に変えた．

n = 2 とした結果の抜粋（全体は若干サイズあるのでリンク）：

aa  2389
ab  2990
ac  663
ad  3432
ae  844
af  2257
ag  3465
ah  663
ai  4425
aj  1388
ak  2179
al  4743
am  389
an  5731
ao  2296
ap  2034
aq  6466
ar  429
as  6337
at  3326
au  2318
av  7572
aw  811
ax  6494
ay  4588
az  2299
a{  209
a|  51
a}  183
a~  27

ということで，2 文字にしてめでたく偏った．先に文字単位の頻度は等しいことを確認しているので，「av」は 7572 回あって，「a~」は 27 回しかないという 100 倍オーバーの差は，有意とかそういうレベルではない^*4明々白々たる偏りである．

この時点で

一文字単位で都度ランダムに取ってきた文字を並べているわけではない
頻出の文字列パターンがどうやら存在する

ことが言える．第一目標は達成した^*5．

次に気になるのは当然パターンそのものがどうなっているのか．

といってもいきなりその詳細は調べようがないので，各文字列長 n についてもっとも頻度が高い一団を抽出し，そこから法則が推測できないかとやってみる．

すなわち頻度を調べる文字列長を n = 3, 4, 5, 6 と大きくしていく．ただ，さっきまで使ってた馬鹿アルゴリズムでカウントするのは効率的にアレなので，ここらでインデクスを作っておくような賢いアルゴリズムを使うことにする．

自分で実装は面倒なので SUFARY を使った．先に mkary でインデクスを作っておけば，

sang -n 6 -t 1000 out2.txt

とすることで長さ 6 文字の部分文字列のうち 1000 回以上出現したものがそれなりに高速に出力される，とかそんな感じ（-t 指定しなければ全部出る）．

これを利用して調査したところ，

3 文字では閾値 3000 くらいで最頻出の一団が取り出せる^*6 （twor3_out.txt）
4 文字では 2000 くらい（twor4_out.txt）
5 文字では 1300 くらい（twor5_out.txt）
6 文字では 1000 くらい（twor6_out.txt）
7 文字では 500 くらい（twor7_out.txt）

となった．

これはまた色々なヒントが隠された結果に思える．

まず，6 文字とかいう割と長い設定でも， 10 万回に 1000 回以上出現しているパターンが 100 オーバー見つかったということ．これは練習したりする上で実用に耐えるレベルのパターンだ．

そして，n 文字から n+1 文字へと一文字増える毎に約 2/3 とかそれくらいに最頻出の一団の頻度が減っているわけだけど，n+1 文字目には均等に文字が出てくると仮定した場合にはこれは 1/95 になるはず^*7なので， 2/3 という減り方は超ゆるやか．ちなみに，ここには載せなかったが n = 8 とか n = 9 でもいきなり 1/95 になることはなかった．それ以上になるとサンプル数が十分でなく，S/N 比が小さくなってくるので参考にならないが．

感覚的には明らかだけど一応ついでに書くと，n+1 文字のパターンは n 文字のパターンに新たな 1 文字を付け加えたものになっている．ただし，n 文字のパターン全てに，対応する n+1 文字のパターンが存在するわけではない．

このことから，以下のことが推測できる：

長さの決まったパターンの基本単位のようなものは無い
　（少なくとも長さ 9 以下ではありえない）
パターンの元（ソース文字列）があるとすればそれは十分に長く，その部分が実際の頻出パターンとして表れている

さらにこれは根拠のない話だけど，一文字ごとに約 1/3 の確率でソース文字列からの転写の継続をやめ，別のパターン（ソースの別の位置？）に飛ぶというような処理を考えれば，上記のように最頻出のパターンの出現数が減ることに説明がつくかも．

この辺りになるとまだ俺もあんまり確信していることは多くなくて^*8，推測とかばかりになってきて申し訳ないが，ここで特筆に値するポイントがある．

twor6_out.txt を見て，眺めてみて何か感じないだろうか．

わかりやすそうなところを貼ると

1091 AQt%Aa
1058 BRu&Bb
1107 CSv'Cc
1023 DTw(Dd
1069 EUx)Ee
1088 FVy*Ff
1029 GWz+Gg
1091 HX0,Hh
1011 IY1-Ii

もう分かったと思うのでもったいぶらずにいけば，文字列の各文字をアルファベット順に「ずらす」^*9と次のパターンの文字列になっている．

文字を「ずらす」操作がなんらかの法則に従って行われている

ことが推測される．そして，そうして「ずらす」ことによって作れるパターン群をまとめて（オリジナルパターンとでも呼ぶか） 1 つとして数えると，

6 文字の最頻出オリジナルパターンは 2 種類
5 文字では 3 種類
4 文字でも 3 種類
3 文字では 4-5 種類

等と，その数が激減する．このことを踏まえて，「ずらして作れる文字列」を同一視して改めて初めから調べてみると何かわかるかもしれない^*10．

要素の列挙になっていて本質的な解析が全然進んでいないという話はあって，これらの情報を統合できるのかどうか甚だ怪しいんですが，まあヒントは少ないより多い方がいいに決まっている．

さらにもう一点（One more thing…）．

今まで部分文字列に注目してきたけど，ちょっと視点を変えて，out2.txt をそのままソートしてみたらどうなるだろうか，とやってみた．
（twor_subekey_sample_sorted.zip）

適当に切り出してきた一部分はこんな感じ：

]a0{=f&.Pjp7Ko4[Ft*( yt  38;d7.DY#{_S(#NN#)_n(¥Ni-A c<-XXr`HSwEg10;Rv5~qq!Ial&XL++ k&/MU9>bt4]Cey|Q3] fn=Au#.FVx)Kk-#Pz7 TZ[ Yo'`d3~@i);Tns!Nr7^Iw-+C1w  6">g";Gb&~|W+&QQ:?A0? Zu]MKp|^jj3BUe8Qt$$|d8)G2
]a0{=f&.PjpAKo4[Ft*J y] j38;d7.DY#{_S(#NN-< w< Wr@JHm_@gg~ Q' Nq!Cca5HDzz*Rku/g9>>Ht/]W)*|l3$ 0nAAa# Fpx{K4-[Oe6<Tt@OY8'Jd.~Dix: m#D~r<^cw1MX1' R6@WM hp?CHZ/GWy*Llj$QL88Vas ap({e42¥je<<ot"Ot8_Jx.,E2x 
]a0{=f&.Pkp7Ko4[Ft*( yt  38;d7.DY#{_T(#NN-< w< Wr@JHm_@gg0 Qb5Nq!!_a5&Dzz*Rku/gU>>Ht/]We*|l3$ Ln8Aa# Fpx{K4-[FVy*Ff)8Lw4 LR/^Rh!@Rr?+X8'JXdv dt- d31[jf=>jp7Lq5]Hp&$ wr}~v1*X2) T1<:J83EFT$[ Z?KfZz{Vf&Q
]a0{=f&.PkpAKo4[Ft*J y] j38;d7.DY#{_T(#NN-< w< Wr@JHm_@gg~ Q' Nq!Dca5HDzz*Rku/g9>>Ht/]W)*|l3$ 0nAAa# Fpx{K4-[Pe6<Tt@OY8'J<Zr1[ bw_O1r~dl; D!,DSv&Ih+!Mw4 RXp}Wm%]b0y>gb./kq8Lp5¥Gu+(Azu  39<e8/EZ$|`T)$O
]a0{=f&.Qkp7Ko4[Ft*( yt  38;d8.DY#{_T(#NN-< w< Wr@JHm_@gg0 Qb5Nq!!_a5&Dzz+Sku/gU>>Ht/]We*|l3$ Ln8Aa# Fpx{K4-[Pe6<Tt@-Y8'Jdi~Eix; n#D~r<^c/?Az> Zt]LJo|]ij BT)AQs$Ffc7KF12OUm`Tj"[Yyw;dY,,~n5' 2?DDc& Hr}
]a0{=f&.Qkp7Ko4[Ft*( yt  38;d8.DY#{_T(#NN-< x< Xr@JHm_[gg0 Rb5Nq!!_a5&Dz0+Sku/hU>>Ht/]We*|l3$ Ln8Aa# Fpx{K4-[$=Id( iY-KS7<[r2[ cw`O1r~dl; EW,DSv&Ihf!MI45RXp}Wm%]b1y>gb./kq8Lp5¥Gu+(Azu  P9<{U/EZYy`Td$O
]a0{=f&.QkpAKo4[Ft*J y] j38;d7.DY#{_T(#NN-< w< Wr@JHm_@gg~ Q' Nq!Dca5HDzz*Sku/g9>>Ht/]W)*|l3$ 0nAAa# Fpx{K4-[Pe6<Tt@OY8'Jd.~Eix; m#D~r<^cw1MX1' R6@WM! Gv&,|q+_Qk:CAf?:Za]}K9|Hj4 WTyB tt39<e8/EZ$|`T)$O
]a0{=f&.QkpAKo4[Ft*J y] j38;d8.DY#{_T(#NN-< x< Xr@JHm_[gg~ R' Nq!Dca5HDz0+Sku/h9>>Ht/]W)*|l3$ 0nBAa# Fpx{K4-[Pe6<Tt[OY8'Jd.~Eix; n#D~r<^cw2MX1' R6@WM! Gv&,|q+_Qk:DAf?:Za]}K9|Hj4 WTyB ttGLd=Ka2.Ppn(UP#
]a0{>f&.Qkp7Kp4[Ft*(Ayt  38;e8.EY${_T($NNYdw ds,~i75_mi?@Dx&:H#}MMm/HR1BCW'] b@)gf5 ak+=Vp^FPu9`Ky/Pt3| o8GYj$=Jd) iY-KS7<¥r2[Acw`O1r dl; EW,DTv'Iif!NI45RXp}Wm%^b1z>gb//lq8Lp5¥Gu+)Azu  P9<{U/EZZy`Ud$O
]a0{>f&.Qkp7Lp4¥Fu*(Ayu  38<e8.EY${_T($NO-= x< Xr[KHm`[gh1 Rb6Oq"!_a5&D00+Sku:hU?>Hu/]We*|l3% Lo8Ba$ Fpx{K4-¥Pe7<Ut[-Z8'Jdj~Eiy; n$D~s=^cw2+X1( S6[>M"6HH',|q+_Ql:DBf?:aa^}K9}Hj4 WUzB tt$Ldo)a2..Bn)=P#
]a0{>f&.Qkp7Lp4¥Fu*(Ayu  38<e8.EY${_T($NO-= x< Xr[KHm`[gh1 Rb6Oq"!_a5&D00+Sku:hU?>Hu/]We*|l3% Lo8Ba$ Fpx{K4-¥Pe7<Ut[-Z8'Jdj~Eiy; n$D~s=^cw2+X1( S6[>M"6HH',|q+_Ql:DBf?:aa^}K9}Hj4 WUzB tt$Ldo)a2..Bn)e$O

こんな大きなヒントを今まで見逃していたとは．これは決して OCR で読み込むときに同じ回を二度記録してしまったとかいうものではない^*11．また文字列長は 200 だから，たった 10 万回の試行でたまたま同じようなものが出ましたとかいう偶然でもありえない．すなわち，全体としてこれだけ似ているワードが出題されることがあるのだ．

何より注目するべきは，途中はもちろん最後の方に至るまで（数パターンはあるけども）類似性が見られること．ここから，文字列を生成している途中に乱数に応じてまったく違うパターンに遷移して戻ってこないということはあまりなさそうで，初期値がまずあって，その初期値が何らかの形で後々にも再利用されるようなロジックであることが推測される．

これまでのヒントと合わせてまた根拠無く考えれば，長大なソース文字列のどの地点から読み始めるかを乱数で決定し（初期値），順次そこから読んで出題文字列として採用していくが，その都度ある確率で文字をずらしたり，別の場所から x 文字読み出して代用するような処理が挟まることがある……というような処理を書けばこのような結果が得られる気がする．十分条件のひとつに過ぎないけど．

まあとにかく

出題文字列の生成においては，初期値依存性がとても高い

ことは確か．

というわけで，調べたり無いところもあるが，基本的性質いくつかが示され，頻出パターンといってもいいものの存在が確信でき，さらに，役立ちそうなヒントがたくさん見つかった．まだこれらをつなぎあわせるには至っていないが，何歩かは進めた気がする．

# それにしても，今回出てきたことのほとんど全てを経験的に見抜いていたとりのさんがすごすぎる

次回予告

TWOR を取り巻くオカルトじみた噂．「時間帯によってワードの傾向が変わる」．

多くのタイパーがそのことを示唆し，表舞台を去っていった．

時を刻まない時計，二次元サンプリングデータは，その詳細を解き明かすことができるのか．

次回「静止した時の中で」

この次も，サービスしちゃうわよ！

わざわざこのように断る理由は，エントリ末尾次回予告にあるように時間を考慮にいれる必要性を感じるから． [↩]
暇なら標本分散計算するなどして検証するべき． [↩]
要するに N-gram 分解の頻度チェックをやっている． [↩]
本当は検定ｒｙ [↩]
なんも証明してないけど． [↩]
4000 とか 5000 とかある子は，スペースを含んでいる．スペースは先に調べたとおり頻度が 6 倍であるのでその影響と考えられる．一旦無視． [↩]
すべキーの文字種は 95． [↩]
試行錯誤しながらエントリ書いてる段階だ． [↩]
ちゃんと言えば ascii code を +1 する． [↩]
まだやってない．方法としてはある文字と次の文字の文字コードの差を取ったデータを解析すればいいと思う．興味湧いた方はチャレンジして情報公開してくれると俺が楽できて助かりますので遠慮なくどうぞ． [↩]
元々のサンプルデータでは隣り合ってないし． [↩]

信じられないことに第 8 学期

2009/10/10 | ごみ | コメント (3)

ブログのペース落ち気味ですがお察し下さい．再びリアルがアレでね．懲りないもので．

雰囲気を見る限りしばらく平日にまとまったエントリを投下できることが少なくなる（かも）．

そして無駄口は他所で叩くことにしたので，このブログにはまとまったエントリしか投下されない（かも）．

やめますとか言うことは間違ってもないけどね．色々と．宣言してもしなくてもどうせやめないんだし，何ごともなかったかのように続きます．

ご心配なく．週に三日はいつも通り．多分．

バトルスピリッツゲーム版

2009/09/28 | ごみ | コメント (2)

第一弾，第二弾とか二つも出ると発表されていて，第一弾がアクションゲーム風のエセ TCG だから第二弾はガチの TCG なんだろうなと思っていたら第二弾はモンハン風のさらにカードゲームからかけ離れたそれだった模様．

たかが数千円のゲームであれやこれやの強いカード何でもばりばり使えちゃったら肝心の TCG に子供が貢いでくれなくなっちゃうし，ゲームは販促に徹してカードを売ろうって戦略なんだろうな．まあそうだよね．

対戦エンジン書く意欲++

群生するひねくれ者

2009/09/15 | ごみ | コメント (2)

ラブプラスというものを今し方知って，例によって例の如く天の邪鬼な発想をしていい感じに付き合ってるかと思いきや実は貢がされているだけだったり股をかけられていたりするラブブラフというゲームを考え悦に浸っていたがラブブラフでぐぐったところ既に何名も同じような発想に至っていることがわかって自分の発想の安直さを恥じた．

望むようなものがないときには「こういうのが理想だろｗｗｗｗ作れよｗｗｗｗｗなんで出てこないのかわからないｗｗｗｗ」等と調子に乗っておいて，実際にそういうものが出てくると「へぇ．でもまだまだなんじゃない，知らないけど」とよく調べもせずに否定してかかるという自己中．このままだとリアル月子ちゃんが実現しても無感動なんだろうなぁ．

斜に構えているのがかっこいいと思っているお年頃が終了する気配がない．

乗り切った感

2009/09/13 | ごみ | コメント (0)

夏は暑かったですが最近は若干涼しくなってまいりました．もう 9 月も中旬ですからこのまま涼しくなっていってくれるんだろうと期待．

今のメイン機を組んだのは 3 年前でして，掃除やメンテをまめにするほうでは全然ないので，そろそろ随所にガタがきていたのね．だから正直この夏に暑さでくたばるだろうなと思っていた．

グラボのファンが逝ってて目玉焼きができそうなチリチリのグラボからディスプレイに映像送ってるっつーのは序の口で，恐らくは CPU ファンのグリスが死んでるからだと思うんだけど CPU 温度も 77 度とかで焼鳥じゃないんだからあなたは Core2Duo だからきゃー死なないで，みたいなそれはもうひどい感じだったんですが，最近の PC パーツは俺の記憶にあるそれより丈夫にできてるのかなんなのか，執念で暑さを乗り切った様子．

当時としてはそれなりにハイエンドな構成にしていてブルジョワノリだったんだけど，まあこれくらい使ってやればいいよなと思える．あと 1-2 年もってくれたら完璧．

ひとつだけダメージがあるのが HDD で，ふと思い立って検査してみると不良セクタが沸いていた．そういう子は窓から投げ捨てようと思って WD の 1TB を 2 台注文． 1TB で 6800 円？どんだけ激安なんだよ．

2-3 年という期間をあけてどれどれ何がどう変わって何が安くなったのかな？と自作の世界を覗き直すととても幸せな気分になれるって話なんだけど，それにしてもすごい時代だね．

SSD？　まあまた 2-3 年後にはベンチでシーケンシャル Read/Write 1GBps 出せる 1TB が 1 万円くらいになってるんだろうから特にヲチするでもなく待ってるよ．

Twitter やらなくないかも

2009/09/05 | ごみ | コメント (0)

他人とねちょねちょすることが極めて苦手なので敬遠してきたんだけど，iPhone のおかげで便利に利用できるらしいことと，ブログからぐだぐだを一掃したいって事情が噛み合ったのでそのうちに．

このブログの左に実は 2 カラム用意してあって，ひとつ空なのでこんなふうに記事とメニューの間が不恰好に開いたまま放置されてるんですけど，当初そこには Twitter 発言埋める予定だったんだよね．なんでそこまで思い至ってやめたのかは忘れたけど．なんかめんどいことっていうか辛いことがあったんだろうね．

{ 「A けど B」とか，「B っていうか A だろう」とかって定型文がお気に入りで，多用してきた } けど，{ ここまで徹底すると何事も言い訳と前フリをしないとしゃべれない { 心の弱い子みたいに見えるよね } っていうか { 多分事実そうなんだろう }}．

A のみと A+B を抽出して文章を読み直すと俺の二面性が浮き彫りになる，という一粒で二度おいしいエンターテイメントを埋め込みだして早半年なんですけど，というのは嘘でそういう意識は全然なかったけど，結果的にそうやって読めるエントリが多いから面白い．

関係ないな閑話休題，まあやるといってもエントリ頭に書いたとおり，特定個人とねちょねちょする気はないのであしからず．

アカウント名は Twitter アカウント名に許される文字で俺のハンドルを表そうとしたときに恐らく最適であるようなもの^*1．

でもやるやる詐欺なのできっとまだやりません．

このヒントもやりますという発言も何もなしに以前から発見してた人が少なくとも 4 名いるんだけど，さすがだよね，なんというか． [↩]

変化についていけない

2009/09/03 | ごみ | コメント (2)

気づくと世間では以下のようなことが起こっていて，そのいずれも俺は察知していなかったことが明らかになった．

おおかみかくしが発売されていた
Adobe プロダクトの CS4 が出ていた
Mac OS X Snow Leopard が出ていた
総選挙が行われ，政権交代が実現していた

趣味の領域のことはさておき，最後はシリアスになるべき問題だと思う．なんかやかましく騒いでるなあとは思っていたんだけど，ちょっと前の都議会選挙のイメージが残ってて，まだやってんのかボケがとかなんかそんな感じで，それと意識されることなくスルーされた．

どうでもいいことって本当にどうでもいいと思ってるので，そんなアンテナ低いと損をするよと頭ではわかっていても社会についていく気が起きない．器の小さな人間としては自分の目の前の，目下の関心領域だけを見つめるので精一杯である．

そんな人間でもある程度食えて楽しめているような気分になれてまあなんとかなるんじゃねって錯覚できる程度に，この社会がうまく構成されてるってことで，俺みたいな人はある意味恵まれていて，ある意味機会を腐らせているんだよな．

選挙くらい行きましょう選挙くらい．行っても白紙投票して義務を果たした気分になって帰宅するだけではあるんだけどさ．

続・右カーソルキー

2009/08/19 | ごみ | コメント (0)

冷静に考えると Num1, Num2, Num3, Num5 をカーソルキーにすればいいだけだった．

テンキー付きモデルでよかった，と珍しく思った．

他にはマウス操作しながら右手親指でテンキーのエンターを叩いたときとかに思うよね．

それくらいだけど．

夏バテではない．いや，そうなのか？

2009/08/17 | ごみ | コメント (0)

仕事はかどらないわブログ改装も終わらないわ他の所用も放置だわで絶賛死亡中．でも next week って前エントリに書いたから正しいのか，これで．

そもそも PC の前に座る時間が以前よりずっと短くなっている．外出する用なんてのがたくさんあるわけがないのだし，PC の前に長時間いると目が疲れるんだよーとかいう人でもないのだけど．

なんでだろうね．やはりというかメンタルな気はする．

まっさらなデスクトップやテキストエディタやコンソールや about:blank を見るとうわあああああと気が遠くなって肩の力が抜けて何もする気が起きなくなる．呆けたような表情で秒針を眺めるのが精一杯．ぶっちゃけ早く向精神薬を飲めよという感じ．飲まないけど．

数日で元に戻るのなら普通のあれだけど戻らないからね．きっかけが必要だね．何がベターだろうね．あ，向精神薬は除いてね．

そういえばコミケは最後まで悩んだ末，行かなかった．いつもの地引き網活動をするに足る資金が無いことによる．完璧に集められないならもう行く必要ないや，といういつもの極端思考．損こそあれ得はない考え方だと頭ではわかってるんだけど直らないねぇ．

而して君子再び沈黙せり

2009/08/10 | ごみ | コメント (0)

改装のこと考えてたら全然エントリ書かなくなっちゃったので無駄に長文で誤魔化したよ．

んでちょっと帰省してくるのでまたしばらくいないかも．

see u next week!

サイト内検索

携帯版

PC と共通の URL で OK．

衒思力発電所

個人ブログなんて結局のところカオスにならざるをえないよねという諦念による闇鍋

ごみ