30分でわかる高性能な圧縮符号vertical code - EchizenBlog-Zwei
検索エンジンの転置インデックスなどデータ列を小さいデータサイズで持たせたい、という状況がある。こういう場合圧縮符号を使うのが一般的でunary符号やgamma符号、delta符号など様々な種類がある。 圧縮符号の中でイチオシなのがvertical code(vcode)。これは岡野原(@hillbig)氏によって提案された圧縮符号で単純な仕組みでdelta符号並の性能を誇っている。 本記事ではvcodeのポイントを絞って30分でわかるように解説してみる。 vcodeは本棚に本を並べる作業を連想すると理解しやすい。本棚は予め高さが決まっているので全ての本が入るような本棚を用意する。つまり というようなものを想像する。 この本棚は8冊の本が並んでいるが左から5冊目の本が他よりも背が高い。このため5冊目の本に合わせて背の高い本棚が必要になる。だが他の本は5冊目の本ほどに背が高くないので、5冊目が
ファンタジーな挿絵イラスト集「おとぎ話の幻想挿絵」が良さげ - EchizenBlog-Zwei
ファンタジーは昔から好きで大学時代は暇なのを良い事に結構読んでいたけれど、挿絵集というものを今まで買ったことがなかった。 それどころか最近はラノベと技術書しか読んでいなかったのでファンタジーからも遠ざかっていたのだが書店でこの「おとぎ話の幻想挿絵」を見かけて、ファンタジー懐かしいなあと思いつつページをめくっていたら無性に欲しくなったので購入してしまった。 出版社のPIEBOOKSのサイトで試し読みができるので興味ある方はどうぞ。 PIEBOOKS / おとぎ話の幻想挿絵 目次は以下のとおり。 夢見る時代の画家たち 世紀末からアール・デコへ アーサー・ラッカム エドマンド・デュラック カイ・ニールセン ウォルター・クレイン ハリー・クラーク アラステア ジョン・オースティン おとぎ話の図像学7名の画家のイラストが解説付きでそれぞれ25Pくらいずつ。それから「おとぎ話の図像学」では「妖精」「騎
「珠玉のプログラミング」のチュートリアル的な読みもの - EchizenBlog-Zwei
先日｢自然言語処理を活用したwebサービスをつくるときに参考になる5冊の書籍｣というタイトルで本を紹介したら評判が良かった。本記事では最初の一冊である「珠玉のプログラミング」のコラム1を読みつつチュートリアル的な記事を書いてみる。 自然言語処理を活用したwebサービスをつくるときに参考になる5冊の書籍 - EchizenBlog-Zwei さて、早速コラム1「真珠貝を開いて」を読み始めると著者が「ディスク上でのソートをしたい」という質問を受けたという話が書いてある。ここで、開発のお仕事をしている人はなんとなく想像が付くと思うのだが実は質問者は「ディスク上でのソートをしたい」わけではない｡ フレンドリーな会話に潜むトラップ！？ 「1.1 フレンドリーな会話」を読むと書いてあるように質問者は「メモリがほとんど使えない状況で重複のない数値データをソート」したかったのだ。そして質問者は思考の末「デ
「テキストマイニングを使う技術/作る技術」を読んだ - EchizenBlog-Zwei
自然言語処理は大学時代からやっていたのだが、恥ずかしながらテキストマイニングについてはよくわかっていなかった。@shima__shima先生から「テキストマイニングを使う技術/作る技術」を紹介していただいたので読んでみた(紹介していただき、ありがとうございました)。 本書によるとテキストマイニングは厳密な定義はないものの、テキストデータから抽出されたデータを用いたデータマイニングを指すらしい。 で、従来のデータマイニングであれば数値データからそのままマイニングすればいいけれどテキストデータは自然言語で書かれていてそのままでは使えないので自然言語処理(NLP)を用いてマイニングで使うデータを抽出するよ。ということらしい。なんとなくNLPの中にテキストマイニングがあるのかと思っていたのだが、テキストデータとデータマイニングの橋渡しをする技術としてNLPを使っている、というのが正しいのかも。 本
これからはじめる人のための機械学習の教科書まとめ - EchizenBlog-Zwei
最近では企業における機械学習の認知度も高まっていてエンジニアの求人募集でも「望ましいスキル：機械学習」というのをよく見かける。特にweb系の企業だと当たり前のように機械学習を活用した魅力的なサービスが生み出されているようだ。 そんなわけで先日書いた機械学習の入門記事もそれなりに好評で末尾の教科書リストも結構参考にしていただいた様子。ということで、これから機械学習をはじめる人のためにオススメの教科書を10冊ほどピックアップしてみた。 幸いにして機械学習の分野には良書が多い。5年前はナイーブベイズすら知らなかった私も、これらの教科書のおかげでなんとか機械学習を使えるようになりました！(個人の体験談です。効果には個人差があります) 参考: 機械学習超入門 〜そろそろナイーブベイズについてひとこと言っておくか〜 - EchizenBlog-Zwei 最初に既存の機械学習の教科書まとめを挙げておくの
自然言語処理を活用したwebサービスをつくるときに参考になる5冊の書籍 - EchizenBlog-Zwei
自然言語処理を活用したwebサービス開発に関わって5年以上経った。いい機会なのでこれまでを振り返って役に立ったと思う5冊をメモしておく。 1.珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造 まずはこれ。有名な本なので知っている人も多いと思う。簡単に説明するとちょっと前に「フェルミ推定」という名前で流行ったような、データから必要な数値を概算する方法や、問題が起きたときに問題点がどこにあるのか？最小の労力で解決するにはどこをいじればよいのか？などが書いてある。「webサービスで自然言語処理だ！」というと無限に夢が広がりがちなので、どういうデータが使えるのか、それをどういう形にもっていけばイケてるサービスになるのか、それはどのくらいの期間で実現できるか、ということを考える必要がある。そういうわけで本書は真っ先に読むべき一冊なのでは(余談だけれど、以前M << Nなデータに対してO(
自然言語処理の教科書はもう全部FSNLP一冊でいいんじゃないかな - EchizenBlog-Zwei
自然言語処理の優秀なエンジニア各位にオススメ本を聞くと大抵FSNLP(Foundations of Statistical Natiral Language Processing)という答えが返ってくる。またブログ等でFSNLPを絶賛している方も多い。 私は自然言語処理は長尾本で満足してしまっていたのでFSNLPは読んでいなかったのだけれど､長尾本は現在入手困難ということもあって入手しやすい自然言語処理の教科書があるといいなと思っていたのでFSNLPを読んでみた。 その結果。自然言語処理の教科書はもう全部FSNLP一冊でいいんじゃないかな。という結論に至ったので全力でFSNLPを推薦する記事を書くことにした。 参考： ［を］FSNLP @ytoさん 自然言語処理の定番の教科書まとめ - 生駒日記 @mamorukさん Perl で自然言語処理 @overlastさん ざっと読んでみてFSN
LCP(Longest Common Prefix)を用いたSuffix Arrayの検索 - EchizenBlog-Zwei
Suffix Arrayは「インデックスの構築」と「キーワードの検索」からなる。それぞれ構築には文字列のsortが、検索には文字列の二分探索が必要になる。 以前にCompressed Suffix Arrayのライブラリtsubomiを実装したときにはsortについてはマルチキー・クイックソート(multikey-quicksort)というアルゴリズムを用いた。一方で二分探索については特に工夫をしていなかった。 さすがにこのまま放っておくのは気が引けたのでSuffix Array論文を読みなおしてみたらLCP(Longest Common Prefix)を用いた二分探索の方法が書いてあった。シンプルだが賢い方法だったのでメモしておく。これはすごい(というか今まで読み飛ばしてたことのほうが問題ですね。はい)。 さて。まずLCP(Longest Common Prefix)とは何かと言うとその
簡潔データ構造(Succinct Data Structure)で最初に読むと良さそうな論文 - EchizenBlog-Zwei
最近、簡潔データ構造(Succinct Data Structure)まわりの論文を色々読んでいる。その中で良さそうなものをいくつかピックアップしてみた。まだ調査中なので他に良いものがあったら教えてもらえると嬉しいです。 (1) Space-efficient Static Trees and Graphs(link) G. Jacobson; IEEE1989 まずはLOUDS論文。簡潔データ構造の元祖なので最初に読むと良さげ。 (2) Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees and Multisets(link) R. Raman, V. Raman, and S. S. Rao; SODA2002 簡潔ビットベクトルは通常n+o(n)なんだけど、これをnH0+o(n)にしたよ、
未知の分野の論文を読むときの10のポイント - EchizenBlog-Zwei
同じ分野の論文ばかり読んでいると視野が狭くなるので専門外の分野の論文も積極的に読んでいきたい。とはいえ未知の分野だとどの論文から読めばいいのかわからず困ることも。そんなときにこれまで試して役に立ったことをメモしてみた。 1.調べる論文は英語に絞る これは日本人の論文が良くないということではなく日本人の論文も含め優れた論文は国際会議(つまり英語)でも発表されているから。英語が苦手でも頑張って英語論文を読んだほうが質のよい論文に出会う確率が高い。 2.関連ありそうな単語を検索して意味を調べる まずはひたすら検索タイム。最初は漠然とした言葉でしか検索できなくても調べたい分野の用語は頻出するはずなので、だんだん知るべき用語がわかってくる。英語の単語がわからない場合も調べていれば日本語/英語を併記してくれているものがでてくるはず。あとは頻出語の意味を分かる範囲でざっと調べておく。余談だけれど技術系の
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
