アルゴリズム
id:echizen_tm さんの記事「ウェーブレット木の効率的で簡単な実装 "The Wavelet Matrix"」から始まったウェーブレット行列ブームから半年以上が過ぎ、すでに枯れた技術として確立されつつある感があります。 …嘘です。日本以外ではあんまり来ていません。理…
関西入力メソッドワークショップ、通称 IM 飲み会で発表してきました。ワークショップの様子やそれぞれの発表内容については @mamoruk さんが29日の日記に書いてくださっています（それにしても @mamorukさんの執筆能力はすごい）。 私が発表した「用言活用…
今回は、CRF の前向き・後ろ向きアルゴリズムについて。可変次数 CRF のアルゴリズムとの対比のために書いておく。 前向き・後ろ向きアルゴリズムは、1 次の CRF で使われる*1。高次に応用する方法も考えられないこともないが、計算量が次数に対して指数的に…
今回は、可変次数 CRF の計算方法についての解説。これはぼくの研究で、2年前に修論にして、国内の言語処理学会にも出したのだが、一人で国際学会に出せるような論文にするまでのモチベーションが湧かず、そのままになっている。一緒に考えてくれる人を募集…
最大エントロピーモデルの続き。今回は、CRF（Conditional Random Fields, 条件付き確率場とも） 一般*1について。前向き・後ろ向きアルゴリズムについては書かない。また、一般に関連が深いとされる MEMM というものについても、ここでは触れない。 CRF と…
table.list{ line-height:1.33em; border-collapse:collapse; table-layout:fixed; width:480pt; } table.list td{ margin:0px; padding:5px; background-color:#FFFFFF; border:1px solid #42B4ED; text-align: right; } .list td.ttl{ padding:5px; backgr…
超小ネタ。ウェーブレット行列の C++ 版を書いた時にビット逆転（上位から下位のビットの並びを逆にする）テーブルを作る必要があったので、その時にちょっと工夫したこと。どっかでとっくに既出かも。状況としては、0 から 255 まで（8ビット）とか、0 から…
ウェーブレット行列を使って、wat-array のクローン（List*Range() を除く）を作ってみました。GitHub リポジトリ: https://github.com/hiroshi-manabe/wavelet-matrix-cppテストは動かない状態です。 wat-array に含まれていた performance_test.cpp を利用…
（注：今回の内容は元論文に書いてあったわけではないので独自研究気味です）前々回と前回で、ウェーブレット行列を使ったアルゴリズムを二つ紹介しました。二つとも、ある配列に対して開始位置と終了位置を指定した範囲についての操作です。RankLessThan(),…
前回に引き続き、ウェーブレット行列を使った検索について書きます。今回も、2進数やビット操作に慣れている人には冗長に感じられるかもしれません。今回は、「配列のある範囲の中にある数字で、n番目に小さい数字を返す」という関数です。これは少しわかり…
前回、ウェーブレット木にできることはウェーブレット行列にもできると書きましたが、今回と次回に分けて、ウェーブレット行列を使って2種類の関数を実行する方法を書いてみます。細かく手順を追うため、2進数やビット操作に慣れている人には冗長に感じられ…
ウェーブレット行列のテスト実装に、rank(), select() の他、wat-array で実装されているものをだいたい追加しました。ウェーブレット木でできることは、ウェーブレット行列でも同じようにできる（元論文の最後にちゃんとそう書いてある）ということが確認で…
えちぜんさんによる Wavelet Matrixの紹介記事を読んで、これはすごいと感銘を受けたので、試しに Python で実装してみた。https://github.com/hiroshi-manabe/wavelet-matrix（追記: wat-array を元にした C++版 https://github.com/hiroshi-manabe/wavelet…
作った。リポジトリはこちら。https://github.com/hiroshi-manabe/ngram-converter-cpp 以前、N-gram 漢字-かな変換という記事で、N-gram を使ったかな漢字・漢字かな変換を公開した。内部で使用しているアルゴリズムについては、可変次数 N-gram デコードの…
今更ながら、Faster and Smaller N-Gram Language Modelsを読んでみました。この記事については、すでにACL2011論文「Faster and Smaller N-Gram Language Models」を読んだ - EchizenBlog-Zwei やN-gram 言語モデルを圧縮するには - やた＠はてな日記で紹介…
iOS の日本語フリック入力などで実装されている「修飾キー省略入力」という機能について書きます。次の記事に解説されています。 http://blog.pasonatech.co.jp/ohashi/16439.html 「しゆうてん」と入力すると、「充電」「終電」「重点」「終点」という候補…
「日本語入力を支える技術」（通称「徳永本」）や「高速文字列解析の世界」（通称「岡野原本」）で紹介されている LOUDS というデータ構造を、12回に分けて解説しました。 友達に教える時に使ったもので、練習問題付きです。実際に紙に書いてやってみるとわ…
一回でわかりやすく書くのは難しいので、簡潔データ構造 LOUDS の解説（全12回、練習問題付き）というシリーズにまとめました。(2014/01/26) 古い内容を削除しました。
最近話題の「日本語入力を支える技術」を途中まで読んだ。 3章がものすごく気合いが入っている。trie（トライ）というデータ構造の2つの実装、「ダブル配列」と「LOUDS」について詳しく説明がされている。ダブル配列については、ぼくは以前論文を読んで勉強…
昨年12/29に京都大学で行われたIM飲み会（という名前のワークショップ）で発表した資料をアップロードしました。 http://www.slideshare.net/takeda25/kanakanji-conversion-using-ngram-10817343 口頭説明用のプレゼンなので、単体で見るとわかりにくいとこ…
先週書いたアルゴリズムクイックリファレンス 7.4 のA*探索を Python で実装してみた。 8パズルの各ピースは、左上を起点とした (X座標, Y座標) のタプルで管理している。 8枚のピース全体は Board クラス。 いろいろ手抜き。 def CalcManhattanScoreCoords(…
あえて言い切る。ここでは主に計算量について言っているので、スクリプト言語でデモ的なものを作るような場合は除く。この記事では C++ を使って書く。logsumexp でどのように計算の量が増えるかはunnonouno: logsumexpとスケーリング法に詳しい。ちょっと引…
前に書いた N-gram 漢字-かな変換 - アスペ日記 のアルゴリズムについて。 かなり縦に長いエントリになると思う。途中までは一般的な日本語自然言語処理にかかわること。 例として、「かれがくるまでまつ」というひらがなの文をデコードして、対応する漢字か…
リポジトリを更新した。N-gram ID から スコアを取得するのに cdb を使っていたのをメモリマップトファイルに変えた。 さらにスコアは 1バイトで持つようにした。 400MB ぐらいだったサイズが 20MB ぐらいになって、速度もだいぶ向上した。合計すると、辞書…
昨日（記事を）書いた N-gram かな漢字（＆漢字かな）変換について。 プログラムを書いたのはこの一週間ぐらい。 先週は仕事が終わってからマクドナルドで書いて、連休中は家でも書いていた。N-gram の N は、最初は 3 で十分かと思って、それで試した。 "Tr…
@gologo13さんの言語モデル配布ページのデータを利用して簡単な漢字->かな/かな->漢字変換ができないかなーと思って作ってみた。言語モデルの作成には SRILMを使用。配布中のデータを SRILM で扱うには多少加工しないといけないので、その変換スクリプトも作…
Bloom filter について書いてみる。 実装例についてはBloom filterのシンプルな実装 - 西尾泰和のはてなダイアリー等があるので、ここでは「気持ち」中心に。 前提:ハッシュ関数と key-value store の知識 注意:途中、説明のために実際の Bloom filter とは…
Twitter で「極大部分文字列を求めるいいライブラリないかなー」とつぶやいていたら id:tkng さんに esaxx という岡野原さんのライブラリを教えてもらった。esaxx というライブラリ名なのに説明が"stxx is ..."で始まったり、説明がところどころおかしい*1の…
