はじめに 現在よく使われていると思われる確率的言語モデルについて簡単に調べてみたのでメモ。 Ngram言語モデルとは 例えば、「お酒が飲みたい」と「バリウムが飲みたい」という文章があった時に、前者の方がよく聞く文章で、後者はほとんど聞かない文章 上…

はじめに 先日作ったDouble ArrayにPredictive Searchを追加してみた。 Predictive Searchとは Common Prefix Searchは、入力文の長さまでで共通の接頭辞を持つ部分文字列を列挙した 入力文が「今日は晴れ」なら「今」「今日」「今日は」...が登録されている…

はじめに 雑誌に簡単なラティス構築とビタビアルゴリズムについて書かれていたので、参考にしてc++で書いてみた。 実際のコスト値などはいれてない。。。 説明 入力文に対し、部分文字列に対し辞書引きをして、ノードとする エッジは文字列上で隣接している…

はじめに 系列ラベリング問題についてちょっと調べてみたのでメモ。 系列ラベリング(系列分類)問題とは ある系列xの各要素に適切なラベル列yを付与する問題 例えば「This is a pen」という文書の各単語に「This(代名詞) is(動詞) a(冠詞) pen(名詞)」のよう…

はじめに 先日作成したDoubleArrayに共通接頭辞検索機能を追加してみた。 共通接頭辞検索とは ある文字列の接頭辞(「今日のご飯」という文字列なら「今」「今日」「今日の」...)について、それが辞書に含まれるかどうかを検索すること Trie(DoubleArray)やAC…

はじめに 形態素解析器などで利用されている「ダブル配列(double array)」の勉強するため、実装をしてみた。 動作を確認するために書いただけなので重い。。。 ダブル配列とは 文字列の検索をO(1)で行えるTrie(トライ木)の効率的なデータ構造 2つの配列BASE…

はじめに 探索空間から大域的最適解を求めることができる汎用的なアルゴリズムの「焼き鈍し法」についてちょっと調べてみたのでメモ。latticelmでも用いられているみたい。 SAアルゴリズム 温度Tによって、動作が変わる メインは「メトロポリスの手続き」で…

はじめに MeCabを使うと言っても、辞書には気をつけてなくて、実際MeCabページにおいてある辞書しか使ったことがなかった。しかし、この辞書は更新履歴(2007年！！)が古かったりして保守されているわけではない。MeCabで使えるほかの辞書はないかと思って調…

はじめに 超大規模なテキストデータでのN-gram統計を取る場合、そもそもデータがメモリにのらなくてSuffixArrayを使ったカウントも無理だったりする。近似値でよい場合、効率的な方法があると知ったのでちょっとメモ＆試してみた。 与えられるデータ 大量の…

はじめに 大規模なテキストデータでのN-gram統計を取る場合、特にNが大きい場合(N>=3)は、組み合わせの数が多くなり出てくるN-gramをすべてメモリに保持しながら個数をカウントするのが難しい。効率的な方法があるのを知ったのでちょっと試してみた。 大規模…

はじめに Trieとその周辺を調べたのでまとめた。 Trie(トライ木)とは 文字列探索のための順序付木構造 Prefix Treeとも呼ばれる 由来は「reTRIEval」らしい 共通のPrefixをまとめたデータ構造で、文字列が辞書(Trie)に登録されているかを高速に検索すること…

ポアソン分布とは http://ja.wikipedia.org/wiki/%E3%83%9D%E3%82%A2%E3%82%BD%E3%83%B3%E5%88%86%E5%B8%83 単位時間に平均で回発生する事象が、k回発生する確率 パラメータによって確率Pが決まる 最尤推定 あるポアソン分布から生成されたデータD={0,0,1,3,…

はじめに ハッシュのkeyにID、valueにソート済み整数列を持つようなデータに対して、valueの整数列を圧縮したい。 perlで簡単なUnary符号化を書いてみた。転置インデックス圧縮などに。 コードについて Unary符号とは、1を区切りとして連続する0の個数で数字…

スプレイ木とは SleatorとTarjanによって紹介 自己調整を行う平衡二分探索木 アクセスした頂点がルートにくるように「スプレイ操作」を繰り返し行う 頂点へのアクセスに偏りがある場合に有効(ある頂点によくアクセスするなど) 逆に一様にアクセスする場合は…