Route 477

■ [ruby] 「超戦略的ブロガー」をリリースしました (powered by はてな)

この記事 に感銘を受けて、任意の文章を超戦略的に変換するサービスを作りました。 (本体 / ソース)

• http://route477.net/senryakuteki/

 このサービスは任意の文章を知的かつストラテジックに変換します。
   ↓
 この戦略的なサービスは任意の戦略的文章を知的かつストラテジックに変換します。

どうぞご利用ください。 (このサービスははてなオフィス の電源(power supply)と無線LAN環境を利用してリリースされました)

■ [event][perl] Kansai.pm#11の参加メモ

Kansai.pm #11 の適当なメモを取ったので適当に公開します。

あんまり人に読ませることを想定していません。他のレポート を補完する感じで読むといいと思います。

 13:30〜
 いつもと違う形式
 id:naoyaのリクエスト
 若い人に

 飲み物は冷蔵庫からご自由に(!!)

Cell Challenge 2009 参戦記 : PFI 吉田(oxy)さん

 Perlではない(特別講演ｗ)

 Cellのコンテスト
 コンピュータ全体の知識がないと勝てない

 京大情報学研究科M2->D1
 理論計算機科学
 P != NPを証明したい的な分野
 P: 計算機で解ける
 NP: 計算機で多項式時間できっとできないだろう

 エンジニア＠PFI

 Anthy
 ICPC
 「関連エントリ機能」

 === Cell Challenge

 マルチコアを効率的に利用したい

 08秋: 参加しないか
 Cell=めんどくさそう

 08 12月: 問題発表（編集距離）
 PFIの同僚(chun)に誘われたので、参加

 チーム名はPFI社長のSkype名から
 (>ω <)

 09 1月：Cell the Hack
 別のコンテスト
 MT(メルセンヌ・ツイスター)を高速化

 09 2月：予選トップ通過

 09 3月：昨日本戦終了
 勝てるといいなぁ

 === なぜここでCell Challenge

 高度なプログラム: アルゴリズムとアーキテクチャに関する深い知識が必要
 Perl知らないので
 Webフレームワークは習得しないようにしている

 === 既定課題

 編集距離
 A = weight ; B = write
 weight -> weighte -> wrighte -> wrihte -> write
 A,Bの距離は4(以下)である
 総当たりすると、3以下ではできないことがわかる

 AとBの間の編集距離を、Cellを使ってできるだけ速く求めよ
 A,Bの長さは一定以下
 A,Bの長さは128で割り切れる
 1文字は1〜255

 === Cell

 SPE
   SPU * 8
   SXU
   LS
   MFC

 PPE
   PPU

 SPEとPPE、全然違う2種類のCPU
 SPEは8個(Core2Duoどころではない)
 # PS3は8つ中7つしか使えない

 3.2GHz
 PPE: L1 32KB, L2 512KB
 SPE: LS 256KB, 128bitのレジスタが128個も(!!) SIMD(複数の演算を同時に行える, SSE/MMXみたいな) 重たい計算に

 === DPによる解法

 O(nm)で解けることが知られている(n = |A|, m = |B|)

     - w e i g h t
   - 0 1 2 3 4 5 6
   w 1 0 1 2 3 4 5
   r
   i
   t
   e

 左上から順に表を埋めると、右下が答え
 (上と左と左上の値から計算できる)

 サンプルプログラム：DPを7並列
 n,m=2^17 で43秒くらい (10万×10万) (並列なしならもっと)
 これを
 予選0.2秒、
 本戦0.14秒まで縮めました
 300倍くらい

 === 手法

 1. アルゴリズム的に
 2. SPE一個単位で
 3. SPE複数個単位で

 === 1. アルゴリズム的に

 SPEが7個でも7倍にしかならない
 アルゴリズムを改善すれば100倍くらいに
 128bitのレジスタを使えば、128要素を同時にもてる

 ビット並列化[H03]

 ベクトルの「横に1減っているか」「縦に1増えているか」みたいな情報(D0 HP HN VP VN)を考えると
 j列目のやつは、j-1列目のやつから計算できる
 これらを使うと編集距離が簡単に計算できる

 これらを128bitレジスタで計算しよう
 128並列

 DPの表は並列化しにくい
 が、依存関係が「足し算の繰り上がり」になってるのでハードウェアでできる

 残り7倍

 === 2. SPE一個単位で

 パイプライン
 1命令＝数クロック
 複数の命令が同時に走る (-> スループット、クロック数の向上 / レイテンシの悪化)

 データハザード (ストール)
 命令の利用するデータに依存関係があると、後ろの命令が前の命令を待つ(遅い)
 ループアンローリング
 forを一部展開する -> 計算順序を調整する(コンパイラ/手) -> ハザードを減らせる
 これだけで2,3倍になったりする
 デモ
 おおー
 # なんで

 ハザード対策: 投機実行
 128bitの加算がないので、32bitの加算*4(SIMD)を使う
 繰り上がりでハザードが起こる
 じゃあ繰り上がりあり/なしを同時に実行して、後から選ぶようにするとハザードが減る (依存関係の遅延評価)

 足し算の高速化
 こうすると速くなりそう(実装できず)
   xxxx
   xxxx
   xxx
   xx
   x

 スーパースカラ
 Cellにはパイプラインが2つある (Even/Odd)
 EvenとOddを効率よく使うように等価変換

 === 3. SPE複数個単位で

 SPEは7個だけど、普通にやると7倍速も出ない

 テーブルを128c*128のブロックに分割(cは適当な数)
 ブロック間は、端っこ以外依存がない
 ブロックの計算が終わったら、次の計算を担当するSPEにその情報を渡す
 PPEをマネージャとして

 cをいくつにするか？
 cが少ないと：SPE間のやりとりが増える
 cが大きいと：レジスタ不足、コンパイル時間(ループアンローリングしすぎ)
 16くらいが良さげだった
 が、常に16ではダメ
 単語の長さによって、最後の計算がSPE1つだけになったり

 最後までSPE7つ使うようにしたい
 (x+i)/nを足していくとsumになる (5,6,6,6,6とか)
 これを使ってcを決める
 |A|が128xだとすると、nは7の倍数かつceil(x/n)が16以下になってほしい

 ページング
 プログラムから見えるのは仮想アドレス
 ページング＝仮想アドレスと実際のアドレスとの対応
 SPE側でページングされてないメモリにアクセスすると、100~1000万クロックもかかってしまう
 でもPPE側なら速い
 PPEで事前にメモリ初期化→ページフォールトをわざと起こす
 デモ(1<<24バイト)

 === まとめ

 アルゴリズム的な改善が一番大事(bit並列化)
 有名問題なら、本や論文でいくらでも
 その他の最適化＝*コンピュータに合わせた計算*をする
 ので、コンピュータの知識がないとだめ(パイプライン、ページング、キャッシュ、SIMD)

 その後の最適化＝問題に依存したパズル
 ゴルフとかっぽい

 流行もいいけど、基礎知識の方にも面白いものがいっぱいあるよ

 === Q/A

 * C言語？
 C。アセンブラはつかわず

 * bit並列化の手法は？
 論文から。
 研究者は何百万

 * レジスタに割り付けるようなコードの確認は？
 printfで確かめる

 * アセンブラだとコード作るだけで大変だよね
 暇だったらやってたと思う(コンパイラの生成コードを参考にしたりとか)

HTMLからの本文抽出 : id:tarao(伊奈)さん

 院生
 専門はλ計算、型理論、証明支援・自動証明とか
 Javaに動的型を入れる研究

 C++, OCaml, Ruby, Perl(半年くらい), JavaScript, TeX
 JSで定理照明器を書いた
 Greasemonkeyで、問題ページを開くと自動的にsubmitするように

 === Perl

 01年：掲示板CGIの改造
 Perl嫌い病

 08年：はてなインターン
 オブジェクト指向
 CPAN
 完治→CPAN Authorになった

 === 背景

 RubyのExtractContent -> Perl移植(HTML::ExtractContent)
 バグを直したり、精度を向上したり
 サイボウズラボでも使われてるとか

 なぜ本文抽出？
 例えばブクマページ
 単純にHTMLからタグを省くだけだと、メニューとかまで入ってしまう
 例えば検索エンジン
 「この記事へのトラックバック」みたいな文字列まで引っかかると困るよね

 既存のアプローチ
 * HTML::ContentExtractor
   * HTML::TreeBuilderベースで遅い、ごみが残る
 * HTML::Content::ContentExtractor
   * トークンに分解、日本語には不向き
 * Webstemmer(Python)
   * 2つのページのdiffを取る感じで本文抽出
   * サンプルを与えて学習する
   * 一般のサイトで十分な性能が出ない

 今回の手法
 正規表現(高速）
 本文らしさをヒューリスティックに

 === 実演

 useしてnewしてextract(str)して、as_text(テキスト)とかas_html(HTML断片)を取るだけ
 HTMLは断片なのでvalidとは限らない(閉じタグだけがあったり)

 デモ
 lifehacker.jp
 youtubeとかは無理(文章が少なすぎて「ようこそ〜」以下が引っかかる)
 ニュースサイトには強い
 2chまとめブログは苦手(1: 以下、名無しさんが〜だけが取れたり)
   レスはブログだと「コメント欄」に構造が近い

 === アルゴリズム解説

 1. 明らかに要らないものを落とす
   - headタグ
   - display: none
   - <!-- -->
   - など
 2. HTMLを適当なブロックに分割
   - div
   - p
   - 開始タグのところで切る
 3. 各ブロックにスコアを
   - 本文っぽさ
 4. つながっているブロックをまとめる(クラスタ化)
   - クラスタのスコア＝ブロックのスコアの合計
 5. スコアの一番高いクラスタが本文

 本文っぽさ
 - 句読点がいっぱいある
 - テキストノードの文字列が長い
 - リンクばかりが並んでいるとこは本文っぽくない

 クラスタ化
 高スコアのブロックが連続しているところをつなげる
 低スコアのブロックは、クラスタの切れ目っぽい

 閾値の設定は職人技ｗ

 傾斜配点
 スコアは下にいくほど減点(コメント欄のため)

 === 発展

 駄目なサイトもある
 もっと確実にしたい

 フレームワーク化
   複数の抽出エンジンを試す
   Chain on Responsibilityパターン
   サイトに特化した抽出エンジンを用意(ニコニコ、youtube、amazon, ...)

   GoogleAdsenseのタグを使う
   RSSフィードを使う

   複数試して、一番良い結果を選択する
   取ってきた文字列が一番長いものを選ぶ

   # はてブではこれくらいやってるらしい

   日々のチューニング

 === Q/A

 * 日本語以外もいけそうだよね
 英語はOK
 文字の長さ

 * 複数の本文セクションがあったときは？(ブログのトップページとか)
 傾斜配点によって、一番最初のものが選ばれるはず
 そういう用途にチューニングされている

 * GoogleAdsenseは決めうち？
 他のものも使うようになっている。
 前のより2倍長かったら採用とか、選び方もヒューリスティック

 * HTML5対応
 まだ対応してない
 nanto_viさんパッチお願いしますｗ

はてな本棚

 異常にPerl力の高い本棚(見たことないPerlの洋書とか)

Perlで学ぶコルーチン : id:hakobe932さん

 M1
 ソフトウェア開発支援みたいな研究
 はてなアルバイト

 === Perl

 05年：スクリプト言語に出会う
 Python -> Ruby -> Perl

 08年：はてなインターン
 CPAN Authorに

 === コルーチン

 1/31 関西Ruby勉強会-11
 Ruby 1.9.1リリース -> Fiberについての発表が
 それPerlでも

 コルーチンとは
 サブルーチンはコルーチンのspecial caseだ! (Knuth)

 サブルーチンとは
   メイン                 サブ
   ---------------------------------
   foo
   bar()   --呼び出し->   sub bar {
                           ...
           <-リターン--   }
   baz

 コルーチン
 処理を中断したり再開したり
 coは協調のco
   A                      B
   ---------------------------------
   resume   --呼び出し-> ...
                         ...
   ...      <------中断  yield
   ...
   ...
   resume   -----再開->  ...
                         ...
                         ...

   処理の実行状態を簡単に扱うことが出来る

 === 使ってみよう

 Perl(5)では提供されてない
 が、それCPANで
 search.cpan.org -> coroutine-> 38件

 use Coro;
 XSで3000行
 Coro::State(継続オブジェクト)
 PerlのスレッドとCのスレッドを駆使
 スレッドをwaitさせとけば状態を扱えるよね、みたいな
 call/ccも実装できる、らしい

 Coroはコルーチンだけじゃない
 並行処理ライブラリ群
 scheduler, async, semaphore, channel, event driven ...

 Coro::Stateを使うと純粋なコルーチンが使える
 けどあまり使いやすくない
 CoroをベースにFiber.pmというのを作った(Ruby1.9のFiberみたいなインターフェイス)
 yieldで、中断時に値が返せるよ
 github

 例
   use Fiber;
   my $f = Fiber->new(
     sub{
       ..
       Fiber->yield;
       ..
     }
   );

   $f->resume; // subからyieldのところまでが実行される
   $f->resume; // yieldの次から最後までが実行される

 === 実用コルーチン

 実行状態を簡単に扱う
 宇宙船の例(上・右・下・左)
   do { $s->move_up; Fiber->yield } for (1..100);
 「いま何回目のループか」みたいな状態変数を用意する必要がない(Fiber内に内包されている)
 複数の宇宙船を平行動作させるのが簡単

 # 終わったFiberをresumeすると例外

 ジェネレータ
 値の列を生成する手続き(イテレータの兄弟)
 列を事前に全部生成できない・したくないときに有用
 Python, C#, JS1.7では言語の機能
 これコルーチンで
 無限factorial
   ..
   while(1){
     $val = $val * $n++;
     Fiber->yield($val);
   }
   ..
 resumeする度に次の値がもらえる
 無限ループだけど無限実行にならない！

 ステートマシン
    (1)  ->  (2)
     ^        v
    (4)  ->  (3) ->  (5)
 状態＝コルーチン、状態遷移＝コルーチンの切り替え
 Fiber->yield($state2)みたいに、中断するときに「次の状態」を返してやる

 # 状態どうしが相互参照しているとGCできないかも...？
 # 最後のステートで参照を切ってやればいいはず

 並行処理
 コルーチン＝「明示的な切り替えが必要なスレッド」
 # これを「ノンプリエンプティブ」という(スレッドが勝手に切り替わる方はプリエンプティブ)
 勝手に切り替わらないので、同期処理がスレッドほど複雑にならない
 Coro::Semaphore, Coro::Channel, Coro::Event

 === 利点と欠点

 Pros
 - 状態管理がシンプル(ゲーム(Luaとか))
 - 並行処理がクリーンに

 Cons
 - それほど使われてない
 - 既存のクラス・クロージャ・メソッドで同じことができてしまう

 === Q/A

 * resume(1)みたいに、再開時に値を渡すことは可能？
 できる

 * RubyのFiber.yieldは、なぜFiberがレシーバ？(インスタンスでなく)
 Coroだと メイン->yield みたいに、レシーバを指定する(これはちょっとめんどい)
 呼び出し時にスタックに積み、resume時にスタックトップを再開

 * RubyのFiberもスレッドで？
 VMレベルだと思う
 # 僕もスレッドじゃないと思うけど、確信がないなぁ

 Coroには「こうするとcall/cc」みたいなサンプルが載っている
 (call/ccができるということは、コルーチンくらいできるよね)

 # C#だとプログレスバーを出すのにジェネレータを使うらしい

スペルミス修正プログラムを作ろう : id:naoyaさん

 「もしかして：○○」
 正しい答えを推定
 いろいろな手法
 - 辞書との比較 (今回紹介する)
   - 字面が似ているものしか訂正できない
 - 検索ログなどから推測

 今回の手法
 はてなキーワードを辞書として使う
 (間違った)単語を与えると、訂正候補を表示

 考え方
 辞書に正解がある
 入力と正解を比較して、「誤り度」をスコア化

 編集距離(本日2回目)を使う
 文字の挿入・削除・置換を何回使えば正しくできるかの値
 動的計画法
 # これをビット並列化すると超高速になるｗ
 CPANではText::Levenshtein, Text::LevenshteinXS
   * Unicode非対応
   * パッチを書くか、自前で

 20万単語との編集距離を計算するわけにはいかない
 対象をNグラムで絞る
   例：bi-gram(2文字)
     bo -> aboard, about, border, ...
 入力が"bord"なら bo + or + rd -> それぞれをbi-gramインデックスで引く
 2回以上ヒットするものを対象に編集距離を計算

 編集距離が同じだった場合どうするか
 Web上でよく使われる語を採用 (DF, Document Frequency)
 はてブのデータ(これは非公開)を使った

 編集距離を改善
 Levenshtein距離は、何文字目が間違ってても同じスコア
 Jaro-Winkler距離: 前の文字ほど重要とみなす (伊藤xxを佐藤xxと間違う人は少ないだろう)
 CPANのはUnicode非対応
   http://github.com/naoya/perl-text-jarowinkler/
   Luceneからの移植、Unicode対応

 計算方法
 「雑音のある通信路モデル」
     W                    Y
   情報源->符号化->通信->復号->出力
                    ^
                    雑音
   音声認識とか、仮名漢字変換とか
 YからWを推定したい。
 argmax_W P(W|Y) Yを観測したとき、正解がWである確率(事後確率)
 ベイズ推定
 P(Y|W): 尤度、今回は編集距離
 P(W): 今回はDF

 参考文献：IIR (Introduction to Information Retreival) など

注意

このへんから集中力がなくなったので適当になります、ごめんなさい(´・ω・｀)

PerlMolの紹介 : 樋口さん

 www.perlmol.org
 化学構造情報
 フォーマット変換とかSDFのパースなど

 CPANで入る

 いろいろなフォーマット
   MOL形式
   - 原子の結合情報
   PDB形式
   - 巨大分子の各原子の立体座標
   SDF形式
   - 原子の結合情報とか
   SMILES

 例：アラニン
 MOLファイル：NとかCとかOとかHが書かれている

 use Chemistry::Mol;

 「オープンソースで始める
 ゲノム・プロテオーム・メタボローム解析」
 CPAN, BioPerl, PerlMol, DBD/DBI, Plagger(ちょｗ)

名札メーカー : 橋本さん

 名札PDFを作成する
 ユーザアイコンを自動取得

 Perl + PDFJ + CGI::Application

ベイズ理論と POPFile における実装例 : いいむらさん

 POPFile
 ベイズの定理
   P(Bi|E) = P(E|Bi) x P(Bi) / P(E)
   1         2         3       4

   1: メールの分類がバケツBiで合っている確率(これを知りたい)
   3: 分類Biのメールが届く確率
       = 受信メールのうち、分類Biのメールの割合
         学習するほど高くなる
   4: メールEが届く確率
       = ってそんなもの計算できない
         知りたいのは「どのP(Bi|E)が一番大きくなるか」なので、無視する
   2: 分類Biの中からメールEが取り出される確率
       = これも大変
         メールを単語ごとにちぎって、その分類から推定する
         各単語の分類があまり相関しないなら(?)わりとうまく行く

 実装
 Classifier::Bayesのclassify関数

2008年Kansai.pm活動報告＆Strawberry Perlの紹介 : lapis25さん

 Kansai.pm = Kansai Perl Mongers
 技術・学術・飲み会ｗのバランス

 2008年
 - フレームワーク勉強会
   Perlばっかりでした
 - Kansai.pm #9
 - OSC 2008
 - Kansai.pm #10
 - KOF 2008

 2009年(予定)
 - JPAセミナやりたい
 - ミーティング、あと1回は
 - OSC, KOF出展
 - 募集中
   - どんなイベントがしたい？

 アンケート
 普段の言語
 内容はよくわかった？

 混乱している人は:
 WindowsでPerlするならStrawberry Perlおすすめ

 WindowsでPerl
 - Active Perl
 - cygwin
 - VMWareでLinux
 - XAMPP + Perlアドオン
 - Strawberry Perl [new!]
   - WindowsだけどPerlつかってない
   - Active Perlつかってる
   - Perlつかってみたい

 おすすめポイント
 - gccやmakeが入ってる
 - CPAN Shellが普通に動く
   - Active Perlだと専用ツール経由になる
 - 最初からモジュールがいくつか追加されてる(Bundle::CPAN, Bundle::LWPとか)
 - 5.10と5.8.8が選べる
 - リリースは年4回くらい(比較的緩やか)
 - 通常版のインストールはc:\strawberry固定
   - 空白問題とかを回避
   - 上級者には指定ディレクトリに入れるためのパッケージも。
 - ポータブル版(beta)
   - USBメモリとかでPerl環境を持ち歩く

XSのはなし改めSocial SKK : antipopさん

 Perler, Emacser, アイドル
 はてなエンジニア(はてなボトル、Myはてなとか)

 前回の発表以降：
 Vimmer転向を宣言したが、断念
 Lux::IO
 Term::ANSIColor::Markup
   フォントタグみたいな形式で色指定

 軽い話
 ソーシャルが流行り
 Social IMEが話題
   - MS IMEの「単語登録」みたいなのをWeb経由で自動的に共有
   - Web APIがあるので、クライアントを自由に作れる

 が、SKK使いだし...
 AquaSKK
 これをSocical化したら？
 -> id:shunirrさんがRubyでやってた(SocicalIME特化)
 せっかくなのでPerlでもやってみた

 SKKとは
 IMEの一種
 連文節変換ではなく、送りがな単位で変換(「oku R igana」とか)
 文節の区切り間違いがない(当たり前ｗ)
 いろいろな辞書ファイル

 skkserv
 変換候補の返却サーバ、たくさん実装がある
 プロトコルさえ守れば、何を返してもいい→Social IMEで検索

 App::SocialSKK
 socialskk.plをSKKサーバとして使うと、変換時にSocialIMEを使うようになる
 プラグイン方式なので、Wikipediaとか英辞郎にも対応
 はてブにも対応(おまけ)
   - 「ほってんとり」で変換→最新のエントリを次々に表示

 実装
 POE::Component::Server::TCP

 shipit!!(この場で公開)