自然言語処理を活用したwebサービスをつくるときに参考になる5冊の書籍 - EchizenBlog-Zwei
自然言語処理を活用したwebサービス開発に関わって5年以上経った。いい機会なのでこれまでを振り返って役に立ったと思う5冊をメモしておく。 1.珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造 まずはこれ。有名な本なので知っている人も多いと思う。簡単に説明するとちょっと前に「フェルミ推定」という名前で流行ったような、データから必要な数値を概算する方法や、問題が起きたときに問題点がどこにあるのか？最小の労力で解決するにはどこをいじればよいのか？などが書いてある。「webサービスで自然言語処理だ！」というと無限に夢が広がりがちなので、どういうデータが使えるのか、それをどういう形にもっていけばイケてるサービスになるのか、それはどのくらいの期間で実現できるか、ということを考える必要がある。そういうわけで本書は真っ先に読むべき一冊なのでは(余談だけれど、以前M << Nなデータに対してO(
d.y.d. 2倍だけじゃない
10:01 10/07/20 それでも２倍だ 先日のvectorの伸長度合いの記事に関して 本当に1.5倍のほうがメモリ効率がよいのか という反応をいただきました。とても興味深い。みんな読みましょう。 自分の理解メモ： 「再利用ができるから嬉しい」等の議論をするなら、 今までに確保したメモリ (1 + r^1 + ... + r^k) のうち、 有効に使えてるメモリ r^{k-1} (バッファ拡大直後) や r^k (次のバッファ拡大直前) の割合で評価してみようじゃないかという。 まず簡単のために再利用をしない場合を考えると、この割合はそれぞれ (r-1)/r^2、 (r-1)/r になります（途中計算略）。 この利用率が最悪になる瞬間 (r-1)/r^2 を最善にしよう、 という一つの指標で考えてみると、式を微分なりなんなりしてみると r = 2 で最大(25%)となることがわかります
きまぐれ日記: 動的配列への追加コストはなぜ O(1)?
動的配列への追加コストは O(1) ってのは覚えていればそれだけの話ですが，どうしてかと言われると意外と難しいものです． というのも, このO(1)ってのは動的配列の実装方法に強く依存しているからです．実装を知っていないと答えられません． 一般論として，1つ要素を追加するとき，配列に空きがなかったら新しく配列を作り直して全要素をコピーする必要があります．コピーのコストは O(n) だから，追加コストも O(n) になるという議論が混乱の元になっています． こういうときは，要素追加を n 回繰り返したときの計算量を n で割った平均をとるという解析方法が使われるそうです．一般に, ある operation C の計算量を C を n 回行ったときの計算量 O(n) を n で割った値 O(n)/n で評価する手法をならし解析 (amortized analysis)と言うそうです． さて，s
文脈自由文法 - Wikipedia
文脈自由文法（ぶんみゃくじゆうぶんぽう、英: Context-free Grammar、CFG）は、形式言語の理論（特に、生成文法）において全生成規則が以下のようである形式文法である。 ここで は非終端記号であり、 は終端記号と非終端記号の（0個を含む）任意個の並びである。「文脈自由」という用語は前後関係に依存せずに非終端記号 を に置換できる、という所から来ている（「文脈無用」という訳の提案もある[1]）。文脈自由文法によって生成される形式言語を文脈自由言語という。 背景[編集] 文脈自由文法はノーム・チョムスキーによる句構造文法の研究の中から、形式言語の類別（形式言語の階層やチョムスキー階層の記事を参照）のひとつとして見出されたものである[2]。 文脈自由文法の形式性は、言語学が伝統的に自然言語の文法を形式的に記述してきた既存の方法（例えばパーニニ）に倣っている。たとえば、入れ子（ne
Parsing Expression Grammar - Wikipedia
Parsing Expression Grammar（PEG）は、分析的形式文法の一種であり、形式言語をその言語に含まれる文字列を認識するための一連の規則を使って表したものである。PEGは再帰下降構文解析を文法を示すためだけに純粋に図式的に表現したものと見ることもでき、具体的な構文解析器の実装やその用途とは独立している。 PEGにおける構文（文法）の定義は文脈自由文法のバッカス・ナウア記法によるそれに似ているが、文脈自由文法では一般に「｜」（縦棒、バーティカルバー）で表される「これらのうちどれか」ではなく、「最初の解析がうまくいったらそれを、失敗なら次を順に試してゆき、成功したものを採用」（「/」であらわす）という意味を使う。 このため、文脈自由文法とは異なり、PEGには曖昧さは存在しない。文字列を構文解析する場合、正しい構文木は常に1つしかない。このためPEGはコンピュータ言語の構文解析
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Amazon.co.jp: プログラミングコンテストチャレンジブック: 秋葉拓哉, 岩田陽一, 北川宜稔: 本
Amazon.co.jp: アルゴリズムデザイン: Jon Kleinberg (著), Eva Tardos (著), 浅野孝夫 (翻訳), 浅野泰仁 (翻訳), 小野孝男 (翻訳), 平田富夫 (翻訳): 本