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

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

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

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

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

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

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

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

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

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

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

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

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

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

ちょっと必要になったので書きました。 perl -CSD -Mutf8 -F/\\t/ -nle 'sub apply_rule{ my ($before, $func, @arr)=@_; my @result=(); for my $str(@arr) { my @temp=(""); my $pos=0; while ($str=~/($before)/g) { my $old_pos=$pos; $pos=pos($str); m…

グーグルを辞めて古巣のマイクロソフトに戻った James Whittaker さんのブログを翻訳してみました。最後の一言が気に入ったので。 グーグルからマイクロソフトに転職することはそんなに珍しいことじゃない、と指摘するだけでは説明として十分じゃないんだろ…

一回でわかりやすく書くのは難しいので、簡潔データ構造 LOUDS の解説（全12回、練習問題付き）というシリーズにまとめました。(2014/01/26) 古い内容を削除しました。

最近話題の「日本語入力を支える技術」を途中まで読んだ。 3章がものすごく気合いが入っている。trie（トライ）というデータ構造の2つの実装、「ダブル配列」と「LOUDS」について詳しく説明がされている。ダブル配列については、ぼくは以前論文を読んで勉強…

Social Media Explained a la @ThreeShipsMedia http://instagr.am/p/nm695/ Google+ ってコンテンツ力高いよね。 自分の人生がうまくいっていないように感じる時、世の中にはもっとうまくいっていないものがあると思わせてくれる秀逸なコンテンツ。 Google …

タイトルのような状況を、主に音声関係の人のツイートで見かける。 読みがな・音声表記の変換は、"ou"->"o:"のような単純な処理をすると、「子牛」が「コーシ」になってしまったりして悲しいことになる。 そこで、自分は音声関係ではないのだが、Perl と MeC…

昨年12/29に京都大学で行われたIM飲み会（という名前のワークショップ）で発表した資料をアップロードしました。 http://www.slideshare.net/takeda25/kanakanji-conversion-using-ngram-10817343 口頭説明用のプレゼンなので、単体で見るとわかりにくいとこ…

人生初勉強会。 やったのは counting sort と radix sort。 この二つは書いたことがなかったので、Python で超手抜きに書いてみた。https://gist.github.com/1395308 base = 10 def radix_sort(x, max): radix = 1 while radix < max: x = counting_sort(x, …

先週の木・金あたりは少し凹んでいた。前回書いたように、やっと可変次数CRF論文の英訳が半分終わったので、先行研究（http://books.nips.cc/papers/files/nips22/NIPS2009_0300.pdf）の人にメールを送ってみた。しかし、ろくに読んでいないようなそっけない…

ここのところ一ヶ月ぐらい、修士論文（可変次数 CRF）の英訳に取り組んでいた（うまくいったら国際学会とやらに出してみようかなと。ちなみに出したことはない）。ただの翻訳のつもりが、始めてみるといろいろとまずいところや足りないところが見つかったの…

先週書いたアルゴリズムクイックリファレンス 7.4 のA*探索を Python で実装してみた。 8パズルの各ピースは、左上を起点とした (X座標, Y座標) のタプルで管理している。 8枚のピース全体は Board クラス。 いろいろ手抜き。 def CalcManhattanScoreCoords(…

8パズルの評価関数の例として挙げられている GoodEvaluator。 P(n)+3*S(n)、P(n)は、各駒の「ホーム」からのマンハッタン距離の和。 S(n)は、升目を順に調べて付けた点数。正しい次の駒が後に続いていなかったら2、その他の駒は、0。ただし、中央に位置する…

韓国に行って漫画等を買ってきた。今読んでいる。 知らなかった単語や表現をメモしておく。 찌질하다 情けない 콩나물 시루처럼 もやしの生えた壺のように 안 봐도 비디오 見ないでもわかる 풍경 風鈴 뜰채 すくい網 염장을 지르다 何かがうまくいっていない…

あえて言い切る。ここでは主に計算量について言っているので、スクリプト言語でデモ的なものを作るような場合は除く。この記事では C++ を使って書く。logsumexp でどのように計算の量が増えるかはunnonouno: logsumexpとスケーリング法に詳しい。ちょっと引…

小ネタ。Perl で日本語の簡単な処理をするやり方（こういうことが簡単にできるという例で、具体的なオプションの意味等は解説していない）。コマンドラインでちゃちゃっと日本語の処理をしたい時、Perl はけっこう役に立つ。日本語の一文字を一文字として扱…

語学を勉強する時、シャドウイング（音声を聞きながら、それに合わせてしゃべること）という方法がある。リピーティング（音声を聞いて、終わってから内容を繰り返す）、朗読といったものもあるが、いずれにせよ自分で発声することが欠かせない。電車での通…