罢谤颈别と尝翱鲍顿厂？？
- 2. 今日は自己紹介から。 ● 東海道らぐ元名古屋案内人です – 愛知県大府市に住んでました。（今は神奈川県民） ● ちびぎーこ保護者会（別名：日本openSUSEユーザ会）の中の人 – 夏コミ、また出るそうです(笑) ←NEW ● 最近はおーぷん万葉を始めてます – Cannaをフォークして新しいかな漢字変換システムを 開発しています。 …のはずが。。。
- 3. 3 さてここからはおーぷん万葉の話 ● 目的「自由な日本語入力環境を手に入れよう！」 – 現在: かな漢字変換ソフト「Izumo」を開発中。 ● 現状の問題点： – ビックデータと叫ばれる時代に、開発がアクティブで 自由にコミットメントできる日本語入力システムがない？ ● 例： mozc, Anthy... （但し、SKKを除く！） → iBusMozcが開発停止！？（openSUSEはどうする！？？） → そんな現状を打破したい！てのが目的です。
- 7. さて、今時のかな漢字変換。。。 ● なにやらいろいろな技術が出てきているらしい – Trie木 （辞書データ検索） – ダブル配列 （辞書データ保管） – LOUDS （辞書データ保管） – ビタビアルゴリズム （最短路検索） 当然Izumoにもこういったものが実装されるわけで…
- 8. 今日の話題はこれ。 ● なにやらいろいろな技術が出てきているらしい – Trie木 （辞書データ検索） – ダブル配列 （辞書データ保管） – LOUDS （辞書データ保管） – ビタビアルゴリズム （最短路検索） 当然Izumoにもこういったものが実装されるわけで…
- 9. Trie木とは？ ● 通常の木構造に対し、枝にラベルがついたもの – メリット：共通接頭辞検索が可能になる ０ １ ２ ３ ４ ５ ６ ７ ８ か み た す び わ た し これがいわゆるラベル これがついてるとTrieと呼ぶらしい ラベルをたどることで 辞書検索が可能になります →データ圧縮にもつながる
- 10. Trieの実装方法 ● ダブル配列 – base, check という２つの同じ大きさの配列に値を格納 – LOUDSに比べて高速だが、メモリを多く使用する – 形態素解析器Mecabで使用（Darts） ● LOUDS – Trieをビット配列のみで表したもの – ダブル配列に比べ遅くなるが、省メモリ – Google日本語入力/Mozcで使用（Rx）
- 11. オープンソースライブラリも結構ある！ ● Darts / Darts-clone – ダブル配列の実装。Mecabで採用。 ● Tx / Ux – LOUDSの実装。Ux は Tx の進化版？ ● Rx – LOUDSの実装。Mozcで採用。 ● marisa-trie – LOUDSの実装。とにかく高速らしい。
- 12. Izumoもこれを使えばいいんじゃね？ ● いろいろ諸事情があった… – Darts / Darts-clone : ダブル配列は不採用 – Tx / Ux / Rx / marisa-trie : →上記すべて「C++」、且つ「new-bsdライセンス」 Izumoは「C」、「MITライセンス」じゃ?！！ できれば混ぜたくないですし。。。
- 13. ところでLOUDSってなに？ ● 「らうず」と発音するらしい。（たぶん） ● 私が説明するより、ぐぐったほうがきっと正解^^; こんなビット配列です。。。 10 1110 10 110 10 0 0 0 10 0 これで先程のツリー構造を表現しています
- 14. 比べてみましょう 10 1110 10 110 10 0 0 0 10 0 ０ １ ２ ３ ４ ５ ６ ７ ８ か み た す び わ た し 仮想ノード 「0」から ３つに分岐 「１」は 分岐なし 「2」から 2つに分岐 「3」は 分岐なし 「4」「5」「6」は 末端ノード 「7」は 分岐なし 「8」は 末端ノード …とか書いてますが これを実装しようとするとどうなるか？ 何か気づくことがありませんか？？？
- 15. LOUDS実装上の最大（？）の欠点 ● LOUDSは「動的ノード追加」ができません(^^; – できるかもしれないけどえらく大変！！（とのこと） – つまりは先にTrie木を構築してね！という話 10 1110 10 110 10 0 0 0 10 0 仮想ノード 「0」から ３つに分岐 「１」は 分岐なし 「2」から 2つに分岐 「3」は 分岐なし 「4」「5」「6」は 末端ノード 「7」は 分岐なし 「8」は 末端ノード いきなりこのビット配列を作ったり 後でノードを追加したりが大変となorz
- 18. こんな具合に実装中 ● 32bitの値でノードを表現して それを比較しながらTrieを構築する方法 – Key = 「ひらがな」なので行けそう。 （Value＝仮名文字の方は後で考える…） ● １?２バイト目： ノードID ● ２バイト目： 制御bit ● ３?４バイト目： ひらがな（key）のコード 1?2 ノードID 3?4 ひらがなコード 制御コードを入れようと思ったけど これを判定対象にするといろいろめんどいかも ２バイトでは足りないのでは？ 64bitにすべきでは？