SATソルバーを使ってBrainfuckのプログラムを実行するというネタのLTです。
詳しくはgithubのリポジトリへ。
アプリケーションが正当な目的でパスワードを読み取れるということは、攻撃者が不当にパスワードを読み取れることも意味するのです。
(SQLアンチパターン / Bill Karvin 著 児島 修 訳 2013)
ニコニコ動画の弾幕は歌詞の内容を元にした「空耳」であることが多く、歌詞には直接出てこないフレーズであるこの弾幕は面白い存在だと思います。
これは今日やったハッカソンでやったことのまとめで、使ったソースコードとデータ一式はこちらにあります。
よく見ると4日目、07/12はGoogleTrendでの最大ピークと一致している。
SNSを見て検索して大量に流入したバズ志向の新規視聴者がこの弾幕でお祭り的に盛り上がろうとしたのが 大ヒットの原因であるという憶測はできるが、これだけでは証拠が弱すぎる。単なる偶然かもしれない。
わかば*ガールの今季一番アレな弾幕「TNP鳴らして」も調べました。
巨大なグラフ1を階層的に纏め上げてくれるLouvain Method(Blondel, et al. [2008])というアルゴリズムの論文と、これをリアルタイム可視化に用いている(Praneenararat et al.[2011])論文を発見して、面白そうだなぁと思ったので(小学生並みの感想)、ニコニコデータセットに適応してやってみました。
明日、日曜日(4/26)に「ニコニコ超会議」内の「ニコつく」でサークルの一つとして展示します。I19です。
デモサイトはこちら
(2018/04/24: メモリの圧がキツいので終了しました)
ニコニコ動画へのタグって、ふつう「アニメ, 遊戯王, この虫野郎」みたいな感じで相互に関連するタグが付けられますよね。
このタグ同士の関連をネットワークとして可視化したら、ニコニコ動画の中でどんな概念同士がリンクしてるのかなー、とか、詳しくないジャンル2でどんなワードが流行っているのかなー、とかが一目で把握できそうです。
というわけで、今回はタグを頂点、辺を 「同じ動画に付けられている回数(共起回数)」としたグラフ(ネットワーク図)を作り、可視化してみました。
それだけ?って感じかもしれませんが、実はグラフをそのまま表示しただけでは頂点も辺も数が多すぎて人間には解釈不能な「Hair-ball graph(髪の毛もじゃもじゃグラフ)」になってしまいます。たとえば、ノードが1万4000のグラフを可視化した結果がこんな感じだそうです。
うーむ、とてもじゃないけど、人間には読めない図です。今回は15万タグを対象としたので、この10倍ほどの頂点とエッジがあります。
この問題に対処するために、可視化する前にタグを階層的にまとめるクラスタリングを行います。たとえば、「ぽいぽい教」や「金剛」タグをまとめて「艦隊これくしょん」クラスタを作り、さらに「艦隊これくしょん」と「ご注文はうさぎですか?」や「きんいろモザイク」とまとめて「アニメ」クラスタを作るわけです。その状態で可視化を行えば、先ほどの図のように「ゲーム」「音楽」「アニメ」みたいなざっくりとした関係の図が出来上がります。
もちろん、その纏めた「アニメ」クラスターの中身もダブルクリックすれば見ることができます。ニコニコデータセットはそこまで最近のデータはないので、例として2011年データから「IS(インフィニットストラトス)」のクラスタを持ってきました。
わたし自身はこのアニメを見てないのであまり詳しくないのですが、一時期エースコンバットとのMADが流行っていたのと、(キャラ名)党っていうタグでお気に入りのキャラクタを示す文化があるのがわかります。
今回の売りは、この集計を「その場」で行っていることです。従来でもさいころ [2013], tasukuchan [2009]など可視化は行われているのですが、基本的には「事前に」集計しておいて、それを可視化しています。しかし今回のシステムでは、表示するたびに毎回、15万ノード+200万エッジの大規模なグラフを、クラスタリングしつつその場で可視化してしまいます。かかる時間はさくらのVPS2Gのような非力なマシン1台でも2秒以下です。
今回これをやった本心としては「データの分析をして知識をマイニングしたい!」とかよりは「この超高速なクラスタリングアルゴリズムを使ってみたかった」という感じなので、実際にこのソフトウェアから有益な知識が得られるかどうかは微妙です。客観的評価とかもとくにしてないし、まぁそのへんはご愛嬌。
今回のシステムのもう一つの売りは、高速性を活かしてインタラクティブに集計期間を変更して好きな時期のデータをその場で可視化できることです。
上のバーを左右に動かすことで、時間を行き来しながらネットワークの様子を可視化できます3。
たとえば、初音ミクはニコニコ動画文化を象徴するものだと言っていいと思うのですが、できた当時の2007年すぐには初音ミクはありません。なので、2007年の最初期のデータで可視化すると初音ミクがなかったころのニコニコ動画が見えます。
最近はもう見なくなったものもちらほらありますが4、今でも人気な作品も多いですね。「涼宮ハルヒの憂鬱」はアニメなのにアニメクラスタに入っていませんが、このような人気な作品はそれ自体が大きなコミュニティを形成しているので、独立して一個のクラスタになることがよくあります。また「ヘタリア」みたいな腐女子向け作品がちょくちょく独立してますが、腐女子向け作品は「アニメ」「ゲーム」タグと同時につかない動画が多いのが原因みたいです。
時間を行き来しながら見ると、時事ニュースによるその時の流行タグも自然と浮上してきます。たとえば、2011年4月の画面を見てみましょう。
右下のほうに「東北地方太平洋沖地震」とありますね。一ヶ月弱前にあった地震を扱った動画がたくさん投稿されていたことがわかります。ちなみに中はほとんど政治的な動画で、みんな大好き「あいさつの魔法。」は「エンターテインメント」の中に入ってます。ただいマンボウ。
昔の流行の思い出に浸るもよし、新規ジャンル開拓に使うもよし、まぁなんか暇つぶしにご活用ください。
「超大規模なグラフをその場で可視化して仮説発見に役立てる」というのはPraneenararat et al.[2011]. が元ネタです。彼らはバイオインフォマティクスで日々生まれる膨大なデータを素早く可視化するために使っていますが、これをニコニコ動画に適応したらどうなるかなーと考えた所、こんな感じになりました。
ソースコードはこちらに置いてあります。
結果を再現するためのプログラムが全部置いてあるので、あなたも自分のサーバで動かすことができます。データはNIIのサイトからダウンロードしてきてください。
また、クラスタリングアルゴリズムであるLouvain Methodの実装はゼロから書き起こした物を使っています。元の実装よりも少し制限がキツい(エッジの重みがintのみ)いのですが、その分だけ頑張って高速化して、だいたい3倍ぐらい速いです。
もしも、「ニコニコデータセットじゃなくてウチのデータセットでもやってみたいんだけど…」という方が居た場合はご相談ください。本当に有益な情報をマイニングしようとするとここから更に何段階か努力しないといけないとおもいますが…。
だいぶ前にJSで実装したcrypt関数を紹介します。crypt関数はパスワードを暗号化するための関数です。
char *crypt(const char *key, const char *salt);
Perlではビルトインで使えます。実際に使ってみるとこんな感じです。keyは8文字(8 bytes)まで、saltには2文字(2 bytes)までしか使えません。
% perl -e "print(crypt('Hello', 'wl'))" wlCoUbJ6h11vY
saltとkey、どちらが変わっても出力結果が変わります。パスワード認証をするときはユーザーのパスワードをそのまま保存するのではなく、このような関数でハッシュにしてから保存しなさいというのはよく言われていますが、さらにその際にユーザーの入力をそのままハッシュに掛けるとハッシュ表が盗まれた時にレインボー攻撃と呼ばれる攻撃ができてしまうので、keyにユーザーごとに異なるsalt(塩)も加えてからハッシュにかける…というのが典型的な使い方です(受け売りです)。
2chのトリップはこのcrypt関数を使っており、この(ledyba.org)サイトに設置してあったCGI「2chトリップ生成システム」をCGIからJSへ移植するために必要になったので書いたというわけです。
Apacheから流行りのnginxに移行したのですが、nginxではCGIを動かすのがかなり面倒臭くなっており、JSで書きなおすのが一番楽そうだったのでそうしました。Public DomainのcryptのCでの実装があったので、それをほぼそのまま移植しています。
ただし、暗号は理論だけでなく実装も注意深く行う必要があり、たとえばキーによって処理時間が変わるような実装だとその差を使ったタイミング攻撃ができたりします。 この実装は私が適当に作ったものなので、2chのトリップのようなどうでもいいアプリならともかく、実際に暗号に用いる場合はもっと有名で枯れた実装を使うのをお勧めします。
大昔に作った「ソーシャル地球儀」っていうWebアプリを公開してないことに気がついたので記事を書いておきます。Twitterの位置情報付きのPublicStreamをリアルタイムでGoogleMaps上に表示するWebアプリです。
大したことはないソフトウェアですが、リアルタイムで「いま世界中で呟かれているさま」を眺めていると「おお、地球上にはたくさんのニンゲンおり、皆それぞれに生きておるのじゃなぁ」というまるで10万10歳のロリババアかなにかのような達観を得られるのでオススメです(?)
もうちょっと人間くさいことをいうと、アフリカはやっぱりあんまりツイートないんだなとか、やっぱり今昼の時間帯のところで活発にツイートされてるんだなとか、色々気づきがあります。疲れたときの暇つぶしにどうぞ。
フレームワークにはScalatraを、JSとの連携にはAtmosphereを使っています。ユーザーごとの状態とかはとくに持ってないのでそんなに複雑なソースではないです。
ソースはこちらです。
とあるイベントでのLT。
なんでFortranせなあかんねんと。その時間を使ってね、バイナリおじさんをする。そういう考え方もできると思うんですよ。だってスパコン向けでもないのにFortran書いてもこころぴょんぴょんしないでしょ。