計算機科学

簡潔データ構造超入門V 〜LOUDSというメモリ効率のよい木構造の話(本編)〜

前回に引き続きLOUDSという簡潔木の話。前回準備したunaryの簡潔ビットベクトルを使って親ノード、子ノードへのアクセスが効率的に可能な木構造であるLOUDSの話をする。 前回までの記事: 簡潔データ構造超入門 〜つくって学ぶ簡潔ビットベクトル〜 - Echize…

未知の分野の論文を読むときの10のポイント

同じ分野の論文ばかり読んでいると視野が狭くなるので専門外の分野の論文も積極的に読んでいきたい。とはいえ未知の分野だとどの論文から読めばいいのかわからず困ることも。そんなときにこれまで試して役に立ったことをメモしてみた。

簡潔データ構造超入門IV 〜LOUDSというメモリ効率のよい木構造の話(準備編)〜

今回はLOUDS(Level Order Unary Degree Sequence, ラウズ)というデータ構造の話。LOUDSは木構造の簡潔データ構造版、簡潔木と呼ばれているものの一種。 簡潔木には他にBP(Balanced Parentheses)やDFUDS(Depth First Unary Degree Sequence)というものがある…

簡潔データ構造超入門III 〜簡潔ビットベクトルで転置インデックスを効率的に実装する〜

前回までで簡潔ビットベクトルというデータ構造を実装した。簡潔ビットベクトルとは普通のビット列に少しの追加データを持たせることでrank/selectという2つの操作が可能にしたもの。そしてrank/selectとはそれぞれ以下の操作のこと。 rank(x) : x番目のビッ…

簡潔データ構造超入門II 〜ちょっとだけ実用的な簡潔ビットベクトル〜

簡潔データ構造(Succinct Data Structure)の魅力を紹介する本シリーズ。前回の記事では疎ベクトルを簡潔データ構造を使って効率的に実装する方法を紹介した。 前回の実装ではビットベクトルのサイズの上限が256だった。今回はこれを拡張して任意の大きさを扱…

簡潔データ構造超入門 〜つくって学ぶ簡潔ビットベクトル〜

簡潔データ構造は各種操作を高速に保ったままでデータサイズを情報理論的な下限近くまで圧縮できる。大規模データを扱うことの多くなってきた現在、特に注目を集めている技術である(※個人的な見解です)。 しかし有用性とは裏腹にまとまった教科書等がないこ…

LCP(Longest Common Prefix)を用いたSuffix Arrayの検索

Suffix Arrayは「インデックスの構築」と「キーワードの検索」からなる。それぞれ構築には文字列のsortが、検索には文字列の二分探索が必要になる。 以前にCompressed Suffix Arrayのライブラリtsubomiを実装したときにはsortについてはマルチキー・クイック…

簡潔データ構造(Succinct Data Structure)で最初に読むと良さそうな論文

最近、簡潔データ構造(Succinct Data Structure)まわりの論文を色々読んでいる。その中で良さそうなものをいくつかピックアップしてみた。まだ調査中なので他に良いものがあったら教えてもらえると嬉しいです。

DSIRNLP#1で発表しました「TRIEにトライ!〜今日からはじめるTRIE入門〜」

昨日開催された「第1回 データ構造と情報検索と言語処理勉強会(DSIRNLP)」に発表者として参加しました。主催者の@overlastさん、発表者の皆さん、ボランティアの皆さん、会場を提供してくださったミクシィさん、そして発表を聞いてくださった皆さん。どうも…

機械学習超入門IV 〜SVM(サポートベクターマシン)だって30分で作れちゃう☆〜

ニーズがあるのかさっぱりわからない機械学習超入門だけどひっそり続けていきたい。 前回は識別関数の基礎であるパーセプトロンの簡単な説明とPerlによる実装を解説した。実はこの時点でかの有名なSVM(Support Vector Machine、サポートベクターマシン)もほ…

高村本でCRFのお勉強をしたのでメモ

「言語処理のための機械学習入門」通称高村本でCRF(Conditional Random Fields, 条件付き確率場)のお勉強をしたのでメモしておく。

ACL2011論文「Faster and Smaller N-Gram Language Models」を読んだ

ACL2011の論文で「Faster and Smaller N-Gram Language Models」というのが気になったので読んでみた。 ACL Anthology » P11 Faster and Smaller N-Gram Language Models Adam Pauls, Dan Klein; 2011 本論文はこれまで提案されている言語モデルの圧縮・高速…

SVMの定番入門書「サポートベクターマシン入門(赤本)」の読み方

SVMを学びたい人にとっては「サポートベクターマシン入門」通称「赤本」は最適な入門書であるといえる。理論から実践までバランスよく解説されており、本書を読むだけでSVMの実装が可能になる。 しかし本書はSF小説を彷彿とさせる独特な翻訳の文体のため機械…

機械学習超入門III 〜機械学習の基礎、パーセプトロンを30分で作って学ぶ〜

機械学習には大きく分けて「識別関数」「識別モデル」「生成モデル」の3つの種類がある。このなかで識別関数は確率を使わないので初心者が入門するのに最適。 識別関数で有名なのはSVM(Support Vector Machine、サポートベクターマシン)。名前を聞いたことが…

「ProjectEuler Level 3 到達記念」 PEをやってよかったこと

ようやくProjectEuler Level 3 に到達した。身近に進みの早い人がいると良い刺激になる(Lv3以上が知る範囲で4人もいる)。 Lv3到達記念ということでPEをやってよかったことなどメモしておく。

SPIRE2010の論文リンク集

SPIRE(String Processing and Information REtrieval)はその名のとおり文字列処理や情報検索を扱う国際会議で、特に圧縮データ構造について多数論文が投稿されているので個人的に注目している。 参考: SPIRE2011 開催日:October 17-21, 2011 SPIRE2010 SPIRE…

時代は数論!今すぐ始められる、簡単☆ProjectEuler入門ガイド

まわりのエンジニアの間でプログラミングコンテストが流行っている。実力を磨くことができるのに加えて客観的に能力を示すことができるのも大きな魅力だと思う。 しかし興味はあるけれどプログラミングコンテストに対して敷居の高さを感じている人も多いので…

Project Euler 5週目

Project Euler 5週目。25問目クリアでようやくレベル1。遅れてます。 http://projecteuler.net http://odz.sakura.ne.jp/projecteuler/ 問題の和訳

Project Euler 4週目

Project Euler 4週目。周りの人達の進みが早すぎてあせる。 http://projecteuler.net http://odz.sakura.ne.jp/projecteuler/ 問題の和訳

Project Euler 3週目

Project Euler 3週目。後半サボったのであまり進んでいない。とはいえ一応記録は残しておく。 http://projecteuler.net http://odz.sakura.ne.jp/projecteuler/ 問題の和訳

Project Euler 3-4日目

毎日記事にするのも面倒なので日曜日にまとめてその週の進捗を書くことにした。自分用メモなので面白くなくてすみません。 http://projecteuler.net http://odz.sakura.ne.jp/projecteuler/ 問題の和訳(@tsubosakaさん情報thanks)

Project Euler 2日目

Project Euler続けてます(username:echizen_tm)。これは楽しい。まだ最初のほうなので簡単というのもあるけど。毎日ちょっとずつやると負担が少なくて良いね。 http://projecteuler.net http://odz.sakura.ne.jp/projecteuler/ 問題の和訳(@tsubosakaさん情…

Project Eulerはじめました

このところ数論に興味が出てきたので勉強していたら@tsubosakaさんにProject Euler(プロジェクト・オイラー)を薦められたので始めてみた。 http://projecteuler.net/ Project Eulerは数学色の強いプログラミングコンテストみたいなもの。ただ送信するのは解…

CCPという新しいデータ圧縮の国際会議が開催されるそうです

CCP2011(1st International Conference on Data Compression, Communication and Processing)というデータ圧縮の国際会議が新しく開催されるとのこと。 1st International Conference on Data Compression, Communication and Processing データ圧縮は興味の…

SVMツールと関連する論文まとめ

最近SVM(Support Vector Machine)周りの復習をしているので有名どころのツールと、それに関連する論文をまとめた。完全に個人用メモなので抜けがあるかも。あくまで参考程度に。

これからはじめる人のための機械学習の教科書まとめ

最近では企業における機械学習の認知度も高まっていてエンジニアの求人募集でも「望ましいスキル:機械学習」というのをよく見かける。特にweb系の企業だと当たり前のように機械学習を活用した魅力的なサービスが生み出されているようだ。 そんなわけで先日…

機械学習超入門II 〜Gmailの優先トレイでも使っているPA法を30分で習得しよう!〜

最近の論文で The Learning Behind Gmail Priority Inbox D.Aberdeen, O.Pacovsky & A.Slater というのがある。これはGmailの優先トレイで使っている機械学習のアルゴリズムについて解説したもの。というと難しそうな印象があるが、この論文で紹介されている…

Burrows-Wheeler変換(BWT)の圧縮率が高い理由

Burrows-Wheeler変換(BWT, Burrows-Wheeler Transform)されたテキストは同じ文字が並びやすい。従ってランレングス法等と併用することで大きな圧縮効果を得ることができる。 では、なぜBurrows-Wheeler変換によって同じ文字が並びやすいのか。これについて説…

機械学習超入門 〜そろそろナイーブベイズについてひとこと言っておくか〜

最近では機械学習の認知度も上がってきていて専門家でなくてもナイーブベイズやSVMなどの名前を知っている人も増えてきたように思う。 そんなわけでちょっと機械学習をはじめてみようかな、と思っている人も多いのではないだろうか。とはいえ「数式よくわか…

wat-arrayでラクラク実装☆FM-Indexの作り方

というわけで大変便利なライブラリwat-arrayを使ってFM-Indexを簡単に実装してみるよ。本格的なライブラリは既にFM-Index++という良いものがあるので、本記事では仕組みの解説を目的とする。 参考資料: FM-index++を公開しました - tb_yasuの日記 An alphabe…