2011-01-01から1年間の記事一覧

第12回アルゴリズム勉強会に行ってきました

人生初勉強会。 やったのは 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)の英訳

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

アルゴリズムクイックリファレンス 7.4 A*探索の実装

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

アルゴリズムクイックリファレンス 7.4 A*探索での GoodEvaluator

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

韓国語単語メモ

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

logsumexp は人類の黒歴史

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

日本語の自然言語処理には Perl も便利

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

電車内でシャドウイングする方法

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

コーパスと実用のサイクル (2)

昨日のエントリ(コーパスと実用のサイクル - アスペ日記)の続き。 「コーパスを使って漢字かな・かな漢字変換を作り、その間違いをコーパスに反映する」というのを具体的にどうするか。自分としては、せっかく現代日本語書き言葉均衡コーパス (BCCWJ)がで…

コーパスと実用のサイクル

他人にはどうでもいいことだが、ぼくは毎日 1時間、自分のための時間(娯楽以外なので、読書と語学は除く)を設けている。数学の勉強・プログラミング・ブログエントリ作成等に主に使っている。 生きる上でワークライフバランスが重要なように、考える・やる…

良い IME に必要なもの 3つ

日本語のかな漢字変換に必要なもののうち、主要なものを 3つ挙げてみる(細かく言えば、必要なものはもっとずっといっぱいある)。 1. N-gram 言語モデル 直接つながる前後の文脈によって曖昧性を解消する。これが基本。「おもってはいる」が「思って-入る」…

ワイン問題詳しく

http://d.hatena.ne.jp/nokuno/20110802/1312236781で紹介されている@http://twitter.com/neubig さんの問題について、id:nokuno さんの解説に加え、具体的な答えを書いてみる。 問題を改めて引用。 貴重なワインの瓶27本を持っていて、その内1本は毒で汚染…

可変次数 N-gram デコードのアルゴリズム

前に書いた N-gram 漢字-かな変換 - アスペ日記 のアルゴリズムについて。 かなり縦に長いエントリになると思う。途中までは一般的な日本語自然言語処理にかかわること。 例として、「かれがくるまでまつ」というひらがなの文をデコードして、対応する漢字か…

雑感3

この数日間は、イベント等があって趣味のプログラミングはしていない。 前々回、 前回 とネガティブな日記を書いた。考えを論文にして、アルゴリズムに関するものであっても実験で性能を出して国際学会で採択されるなどしないと、アルゴリズムの内容も読んで…

雑感2

今日も引き続き、ソウルジェムの穢れをまき散らすような日記を書いてみる。 なぜ論文を書きたくないか。 それは、「そりゃこれは書かないとだめだよね」と納得できる以上のことを書かないといけないからだ。 まず、先行研究。 修士のころ、論文を書いていて…

雑感

N-gram かな漢字変換 をアップデート。 内部の Unicode 化、未知の文字への対応。 これまでは未知の文字があると結果を返さなかったので、特に漢字かな変換では致命的だったが、今回の変更で大丈夫になったかもしれない。 まだ漢字かなでは試してないけど。 …

N-gram かな漢字変換(3)

リポジトリを更新した。N-gram ID から スコアを取得するのに cdb を使っていたのをメモリマップトファイルに変えた。 さらにスコアは 1バイトで持つようにした。 400MB ぐらいだったサイズが 20MB ぐらいになって、速度もだいぶ向上した。合計すると、辞書…

N-gram かな漢字変換:続き

昨日(記事を)書いた N-gram かな漢字(&漢字かな)変換について。 プログラムを書いたのはこの一週間ぐらい。 先週は仕事が終わってからマクドナルドで書いて、連休中は家でも書いていた。N-gram の N は、最初は 3 で十分かと思って、それで試した。 "Tr…

N-gram 漢字-かな変換

@gologo13さんの言語モデル配布ページのデータを利用して簡単な漢字->かな/かな->漢字変換ができないかなーと思って作ってみた。言語モデルの作成には SRILMを使用。配布中のデータを SRILM で扱うには多少加工しないといけないので、その変換スクリプトも作…

.gdbinit を公開してみる

タイトルのまま。自分はずっと Windows で開発してきたので、C++ は Visual Studio(VS) でやっていた。 VS のいいところは、デバッグ機能。 条件付きブレークポイントやメモリ変更時のブレークといったことをしても爆速で動いてくれてきちんと止まってくれる…

Bloom filter の気持ち

Bloom filter について書いてみる。 実装例についてはBloom filterのシンプルな実装 - 西尾泰和のはてなダイアリー等があるので、ここでは「気持ち」中心に。 前提:ハッシュ関数と key-value store の知識 注意:途中、説明のために実際の Bloom filter とは…

手抜き日中判別(繁体字)

前回の続き。 繁体字の場合。 use strict; use utf8; use Encode; my $enc_cp950 = find_encoding('cp950'); my $enc_cp932 = find_encoding('cp932'); my $level2_eucjp; $level2_eucjp .= chr(0xd0 + ($_ / 94)) . chr(0xa1 + ($_ % 94)) for 0..3389; # 3…

手抜き日中判別

Twitter 上で、 id:showyou さんがログデータの日中言語判別をしたいという話をしていたので、それについて。まず前提として、文字だけ見ても日本語と簡体字中国語(繁体字はもっと面倒だけど、ここではいったん棚上げ)を 100%判別することはできない。 と…