2012-04-01から1ヶ月間の記事一覧

@AntiBayes さんとのやりとりについて

先週、私と @AntiBayes さんとの間にかなり激しい応酬があった。NLP 業界で 私と @AntiBayes さんの二人をフォローしている人たちにはそれが見えたと思う。また、その影響は今後も残るかもしれない(残らなければそれに越したことはないが、私はあまり楽観し…

道徳について

人間の行動規範は、次の2つに分けることができる。1. それを解釈・運用する主体が決まっている行動規範=法律 2. それ以外のもの1 の「法律」が存在することは明らか。2 が存在するかどうかは自明ではない。「法律」のみを行動規範とする、つまり法律に違反…

簡潔データ構造 LOUDS の解説(全12回、練習問題付き)

「日本語入力を支える技術」(通称「徳永本」)や「高速文字列解析の世界」(通称「岡野原本」)で紹介されている LOUDS というデータ構造を、12回に分けて解説しました。 友達に教える時に使ったもので、練習問題付きです。実際に紙に書いてやってみるとわ…

詳解 LOUDS (12) trie として使う

.small { font-size: 80%; } .node { color: red; } .index { color: blue; } ここまで、LOUDS のビット列を使って木構造をたどる方法を見てきました。今回は、LOUDS のデータを使って trie を実現する方法を考えます。(trie を知らない方は、情報系修士に…

詳解 LOUDS (11) 木の検索

.small { font-size: 80%; } .node { color: red; } .index { color: blue; } 今回は、これまでのまとめとして、子ノードを連続してたどっていく手続きについて見てみます。例として、「根(1番ノード)から、左から 3つ目の子ノードを探す。さらにそのノー…

詳解 LOUDS (10) 親ノードから子ノード

.small { font-size: 80%; } .node { color: red; } .index { color: blue; } さて、今回は逆に「親ノードの番号から、子ノードのインデックスを列挙する」方法を解説します。例えば、LOUDS の表を使って、4番ノードの子ノードのインデックスを列挙したいと…

詳解 LOUDS (9) 子ノードから親ノード

.small { font-size: 80%; } .node { color: red; } .index { color: blue; } これまで何回かにわたって、「ノード番号」と「インデックス」の関係を解説してきました。次の 2点について、だいたいわかっていただけたことと思います。 木のノードは、「ノー…

詳解 LOUDS (8) インデックスからノード番号を得る

.small { font-size: 80%; } .node { color: red; } .index { color: blue; } 前回は、「ノード番号からインデックスを取得する」方法について解説しましたが、今回は、逆に「インデックスからノード番号を取得する」方法について見ていきます。前回と似てい…

詳解 LOUDS (7) ノード番号からインデックスを得る

.small { font-size: 80%; } .node { color: red; } .index { color: blue; } 今回から、「ノード番号」と、それに対応するビットの「インデックス」との関係について解説します。まずは、ノード番号からインデックスへの変換方法について解説します。これま…

詳解 LOUDS (6) インデックスでノードを表す

.small { font-size: 80%; } .node { color: red; } .index { color: blue; } 今回から数回にわたって、LOUDS のデータそのままで木構造の操作に扱う方法を解説します。難しくなりますので、文の記述と表と対応させながら読んでください。元の大きな木に戻り…

詳解 LOUDS (5) 木構造の復元

.small { font-size: 80%; } .node { color: red; } .index { color: blue; } 今回は、LOUDS のデータから木構造が復元できることを示します。次のような手順により実現できます。 まず、木構造の深さ 0 に、根(0番ノード)がひとつある状態から始め、0番ノ…

詳解 LOUDS (4) ビットの意味

.small { font-size: 80%; } .node { color: red; } .index { color: blue; } 今回は、LOUDS のそれぞれのビットが意味するところについて書きます。最初の大きな木に、仮想的な 0番ノードを加えたものを再掲します。 これに対して LOUDS のデータを作る途中…

詳解 LOUDS (3) 0番ノード

.small { font-size: 80%; } .node { color: red; } .index { color: blue; } 今回は、LOUDS のビット列が意味するところについて解説します。最初の大きな木を再掲します。 まず、木構造の特徴として、すべてのノード(根を除く)は、自分の親をひとつだけ…

詳解 LOUDS (2) ビット列を作ってみる

.small { font-size: 80%; } .node { color: red; } .index { color: blue; } 今回は、前回紹介した LOUDS のデータをどのように作るかについて説明します。 まず、対象とする木構造を再掲します。 この木構造に対応するデータが、次のようなビット列になる…

詳解 LOUDS (1) LOUDS とは

.small { font-size: 80%; } .node { color: red; } .index { color: blue; } 以前、「情報系修士にもわかるダブル配列」が好評だったので、続けて「情報系修士にもわかるLOUDS」を書きました。しかし、残念なことにあまり多くの人にわかってもらえてはいな…