[B! Algorithm][algorithm][n-gram] manabouのブックマーク

manabou id:manabou

Algorithmとalgorithmとn-gramに関するmanabouのブックマーク (2)

大規模テキストにおけるN-gram統計 - Negative/Positive Thinking
はじめに大規模なテキストデータでのN-gram統計を取る場合、特にNが大きい場合(N>=3)は、組み合わせの数が多くなり出てくるN-gramをすべてメモリに保持しながら個数をカウントするのが難しい。効率的な方法があるのを知ったのでちょっと試してみた。大規模テキストにおけるN-gram統計の取り方岩波講座ソフトウェア科学15「自然言語処理」論文: http://ci.nii.ac.jp/naid/110002934647 手順 ngramを取りたい文章を1つの文として扱うこの文をメモリに読み込み、各文字の先頭アドレスを保持する配列を作成その先頭アドレスの場所の文字から文最後までの部分文字列を1つの単語とみるこの単語を辞書順に並び替える(アドレス配列だけ) ソートした単語の順番で、次の単語と「先頭から共通している文字数」を保持する配列を作成 Ngramをカウントするときは、単語の
manabou 2011/10/13
n-gram

nlp

algorithm
リンク
可変次数 N-gram デコードのアルゴリズム - アスペ日記
前に書いた N-gram 漢字-かな変換 - アスペ日記のアルゴリズムについて。かなり縦に長いエントリになると思う。途中までは一般的な日本語自然言語処理にかかわること。例として、「かれがくるまでまつ」というひらがなの文をデコードして、対応する漢字かな混じり文にすることを考える。こういう時に使われるのが「ラティス構造」。こういうやつ↓ （この図は一回しか出てきません。ちなみにこのために Keynote 買ったようなもの）それぞれのノードで、そこに入ってくるエッジの中で一番確率が高いものとその確率を覚えていくことで、動的計画法によって最適なパスを導くことができる。これをプログラム上でどう実現するか。まず、共通接頭辞検索というものを使う。これは、あるキーを渡すと、そのキーに前から一致するようなキーを持つ候補を列挙してくれるというもの。例えば、「くるまで」をキーとして使うと、「く
manabou 2011/08/08
n-gram

algorithm
リンク
1