Hatena::ブログ(Diary)

ROOT MX127

 | 

January 30(Sat), 2010

sak_655362010-01-30

Googleの講演会に行ってきました

Tech Talk in 関西: Google 日本語入力を支える情報処理技術 (学生向け)のお知らせ (1 月 30 日)

ちょうど前回のパターン認識の講義で統計的言語モデルを扱っていたので、これは聞きに行くしかない!と何も考えずに行ってきました。

以下、走り書きメモを若干補完したものです。
私が興味をもった質問に対する回答も該当場所に埋め込みました。
誤りがあれば指摘してくださると有り難いです。


概要紹介

内部設計

IMは複雑(Officeソフト並?)
これまでの一般的な実装 - As DLL
  • 各アプリにロード
    • アプリ毎にOfficeソフトがくっついているようなもの
  • 辞書は共有リソース
    • 排他制御が必要
  • (弱点1)クラッシュに弱い
    • IMが落ちるとアプリも落ちる。逆も然り
    • 辞書にアクセス中だった場合辞書も破壊
  • (弱点2)セキュリティ問題
    • ログオン時etcではIMはシステム権限
      • 仮に、F10を押すとブラウザが起動する機能がIMに実装されていたら?
      • これまでこの問題は放置されていた(カーネルモードで動作していた)
クラッシュもセキュリティホールも致命的、ダメゼッタイ!
  • でも100%防ぐのは現実的に無理
    • なんとか努力。しかし長年の経験がモノをいう
      • Googleには経験がない、どうすれば・・・?
発想の転換 - クラッシュ/セキュリティホールの存在を考慮した設計
  • 機能分離
    • IM DLLのサイズをできる限り小さく
      • クラッシュのリスクが低下
    • 処理毎に別プロセスに分業する
      • Converter(変換エンジン)やRenderer(候補ウィンドウ表示)
    • プロセス間通信(IPC)
      • ひとつのプロセスがクラッシュした時のリスク低減
ありがちな実装方法
  • アプリとIM DLL間でほとんどのやりとり、かなを漢字に変換する時のみ変換エンジンプロセスに送る
    • リスクは低減できていない。結局多くの処理をDLLで行っている
Google日本語入力の実装方法
  • IM DLLはほとんどの処理を変換エンジンプロセスに丸投げ
    (a→あ、i→あい、(space)→合い、(space)→愛・合い・etc)
    • Statelessになる
    • Portability - 移植が容易
      • Win版/Mac版で変換エンジンのほとんどを共有
      • 64bit版は1日でできた。テストは10日(小さいDLLのみ64bit化、残りは32bit)
    • クラッシュリスク減
変換エンジンがクラッシュしたら?
  • (仮説)ユーザ入力がリセットされる?
  • 4秒毎にkillするscriptを走らせて実験
    • 特に問題なく(?)入力ができている
      • Why?
Playback機能
  • 変換エンジンがクラッシュするとDLLが変換確定前のやりとりを全部再送
    • クラッシュ時のログを吐けばデバッグ
    • 500キーほど記憶される(それ以上打つ前にユーザは変換確定させるだろうという推測)
  • いつkillされても安全
  • 自動アップデートが簡単にできる
    • ユーザはおそらく気づかない
    • IM ONになる時(念のため安全な状態)に勝手にアップデートされる
セキュリティ問題の解決策 - Sandbox
  • 変換エンジンを別プロセスにし、Sandbox化
    • 外部プログラムを起動不可
    • 必要な特定ディレクトリ(AppData/LocalLow)以外への書き込み不可
自動テスト
  • クラッシュしないほうがいいのは言うまでもない
  • 自動ストレステスト
    • 入力をランダム生成、リソースギリギリのPCへ送信を長時間継続する
    • クラッシュ→Playback機能からログが吐かれる→デバッグ
まとめ
  • 発想の転換
    • Google Productsの共通哲学
      • Google File System
      • Google Chrome ←特に強い影響

豊富な語彙・変換の秘密

ウェブ辞書生成
  • Web Indexから持ってくる
  • 特徴的・高頻度で出現する単語・フレーズの抽出
  • 読みはどうする?
    • 単漢字辞書
      • 当て字に弱い(もず→百舌鳥)
    • ウェブ技術の応用
      • もしかして機能
      • 読みがわかっている
      • 読み間違いは少なからずある
言語モデル
  • MeCab
    • 単語・フレーズのつながりをデータベース化
      • 特殊なことはしていない。教科書的な手法
    • 辞書も言語モデルでモデル化
      • 大量の語彙を登録すると副作用(もっさり)
辞書
  • Key Value Storeにする?→たぶんムリ
    • 圧縮率が高くないので肥大化
    • 一般にexact matchしかできない
  • 日本語入力特有の検索要求
    • Common Prefix Search
      • 連文節変換
    • Predictive Search
      • サジェスト
データ構造
  • TRIE
    • 共通のPrefixをまとめて木構造
      • 前述の2つのSearchに適している
  • LOUDS
    • TRIEの中で最もスペース効率がよい
      • Read Only時。ユーザ辞書では使っていない
    • 速くない
  • 古典的圧縮手法の組み合わせ
    • ハフマンコーディングなど
      • 「タバタテクノロジー」:田畑さんが20%ルールで70MB→35MBに
辞書はどこにある?
  • バイナリ(Converter.exe)埋め込み
  • 辞書アロケーションをOSに任せる
    • メモリが十分あれば物理メモリ上に
      • WinXPはフォアグラウンドプロセス優先のため気がつくとSwap outしてるかも
      • Vista以降ならSuper Fetch(よく使うプログラムは先読み)があるから大丈夫
  • 辞書アップデートの複雑性を回避
    • 中途半端な状態(例:プログラムは古いのに辞書は新しい)がなくなる
      • アップデート時のテストが一番面倒
  • 圧縮アルゴリズムを日々改善できる
  • 辞書が破壊されない
    • バイナリはRead Only

開発経緯

  • 20%ルール
    • 20%使いなさい
  • もしかして機能のログ分析
    • 大部分がIMによる誤変換
  • 経験者多数
    • Anthy, skkime, AjaxIME, PRIME, SCIM,...
  • (関西(京大?)にゆかりのある人ばかり)
立ち上がるまで
  • 半年間:ディスカッションのみ
    • 週に数回話し合い
    • 方針
      • マルチプロセスアーキテクチャ
      • Win/Mac両対応
  • コードが一行もない!
    • 週1回(=20%)集中的に書く
  • 本プロジェクトに昇格
リリースまで
  • 社内でDogfood(まず自分たちで使う)
    • 既存IMとの互換性要望
      • 「○○のキーバインド・機能がないと使えない!」
    • 移行コストを最小限にする必要
      • サジェストと語彙で勝負することに
    • コードベースが肥大化
      • 機能を選別してカット
      • 実装の2〜3倍かけてテスト
      • さらにテスト不足でカットした機能が2,3個

その他

  • Chrome OSに載る、オープンソース化
    • Linux版は勝手に作ってね

全体が終了したのは15時頃。

そして私は16時からのバンド練習@京都のため、まわりにおられる優秀な方々とは一言も会話を交わすことなく、ダッシュで地下鉄扇町駅に飛び込んでいったのでありました・・・

 |