ウェーブレット行列のrankを2倍高速化する案について著者からコメントをいただいた - EchizenBlog-Zwei
一年くらい前にウェーブレット行列のrank計算を2倍高速化する方法を思いついた。 詳細はDSIRNLP発表資料(http://ja.scribd.com/doc/102636443/Wavelet-Matrix)のP.56以降。 本当にイケているのか自信がなかったのでウェーブレット行列論文のfirst authorであるF. Claude氏に"アドバイスお願いします"と送ったメールに返信があった。 "I guess that if your alphabet is not bit, this might be a very good alternative to pointer-based wavelet trees! :D"とのこと。めでたしめでたし。
ウェーブレット行列を用いたFM-Indexを大幅に高速化した - EchizenBlog-Zwei
なんかすごい高速化できた気がする。 今日は詳しく解説する気力がないので、気になる方はコードの差分をどうぞ。 簡単に言うとrankの先頭位置って実は持ってなくていいんじゃねっていうtakeda25さんがrank_less_thanの高速化で考えていたようなこと(http://d.hatena.ne.jp/takeda25/20120807/1344336237)をrankでやっただけ。FM-Indexはrank_less_thanは事前に計算しておけるので実行時はrankの速度だけが重要なので。 https://code.google.com/p/shellinford/source/diff?spec=svn22&r=22&format=side&path=/trunk/src/shellinford_wavelet_matrix.h で肝心のデータサイズと速度はこんな感じ。 ウェーブレッ
ウェーブレット行列とウェーブレット木の性能比較をしてみた - EchizenBlog-Zwei
FM-Indexで用いる簡潔データ列としてウェーブレット行列とウェーブレット木のどちらがいけてるのかを調べてみた。 データは以下の実験で用いた住所データを使った。 http://d.hatena.ne.jp/echizen_tm/20120215/1329315913 データサイズは ウェーブレット行列: 5, 693, 256 byte ウェーブレット木: 5, 709, 560 byteとなった。ビット列のセパレータ数が少ないぶんウェーブレット行列のほうがやや小さい。 速度についてはsample/search_fm_indexを用いてインデックスした住所データ(118,073件)をシャッフルしたものをクエリとして全件検索にかかる時間を測った。 $$ time sample/search_fm_index var/zenkoku.key.fm.wm m y < var/zenkoku.s
海風に揺れる一輪のTRIEライブラリ erikaを作ってみたよ - EchizenBlog-Zwei
注意：この記事の内容は古いものです。 最新版のerika-trieは erika-trie(実用版)とキーワード抽出ツールerika_extractを作ったよ - EchizenBlog-Zwei うっかり手が滑って自分で☆つけてしまいましたが自画自賛してるわけではないです・・・。 をご参照ください。 最近TRIE(トライ)に対する興味が高まってきたので勉強のためにライブラリを作っていた。一応完成したので公開しておく。普通のTRIEとLOUDSによるTRIEの二つを実装した。 名前はerika。もしくはerika-trie。以前作ったCompressed Suffix Arrayのライブラリがtsubomiだったので、今回はerikaにした。コードはGoogleCodeのtsubomiと同じところにおいてある。というかtsubomiの付属品状態。開発はlinuxで行ったが特に環境に依存した
時代は数論！今すぐ始められる、簡単☆ProjectEuler入門ガイド - EchizenBlog-Zwei
まわりのエンジニアの間でプログラミングコンテストが流行っている。実力を磨くことができるのに加えて客観的に能力を示すことができるのも大きな魅力だと思う。 しかし興味はあるけれどプログラミングコンテストに対して敷居の高さを感じている人も多いのでは。そんなあなたにProjectEuler(プロジェクト・オイラー)！参加の敷居が非常に低く、楽しみながらアルゴリズムや数論の知識も身につくので他のプログラミングコンテストに参加する足がかりとして挑戦してみるのも良いのでは。 そこで本記事ではProjectEuler(PE)入門のために、PEとは何か？何故簡単に始められるのか？どういうメリットがあるのか？おすすめのプログラミング言語は？おすすめの参考書は？という5つについて解説する。これを読んであなたもPEに参加しよう！今すぐ！ http://projecteuler.net/ PEはプログラミングと数学
Project Eulerはじめました - EchizenBlog-Zwei
このところ数論に興味が出てきたので勉強していたら@tsubosakaさんにProject Euler(プロジェクト・オイラー)を薦められたので始めてみた。 http://projecteuler.net/ Project Eulerは数学色の強いプログラミングコンテストみたいなもの。ただ送信するのは解答だけだし制限時間などもないので好きなときに気楽にチャレンジできるのが魅力。始めるまでにTopCoderみたいな面倒な手続きが不要なので気になった人は今すぐ始めるといいと思う。 また各問題に対してForumがあり他のユーザが解き方を解説してくれていたりする。解答しか送信しなくて良い、ということで各人好きな言語で書いていて面白い。 このProject Euler。解答だけの送信ということもあり、あまり実力を証明することにはならない気がする(効率悪いプログラムを書いていないという保証もない)。「競
Project Euler 3週目 - EchizenBlog-Zwei
Project Euler 3週目。後半サボったのであまり進んでいない。とはいえ一応記録は残しておく。 http://projecteuler.net http://odz.sakura.ne.jp/projecteuler/ 問題の和訳 8: Discover the largest product of five consecutive digits in the 1000-digit number.1000桁数は文字列として持っておいて計算時に数値化した。 9: Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000.aを奇数、bを偶数として大きい方から見つかるまで探した。 10: Calculate the sum of all the primes below two million.エラト
Project Euler 4週目 - EchizenBlog-Zwei
Project Euler 4週目。周りの人達の進みが早すぎてあせる。 http://projecteuler.net http://odz.sakura.ne.jp/projecteuler/ 問題の和訳 14: Find the longest sequence using a starting number under one million.Collatz数の問題。「はじめての数論」で一度出てきていたのでちょっとうれしい気分。普通にやると結構時間かかる。とりあえず500000以下の数は候補から外していいはず。 15: Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?各地点からゴールまでの分岐数をDPで計算すればOK。こうい
Project Euler 5週目 - EchizenBlog-Zwei
Project Euler 5週目。25問目クリアでようやくレベル1。遅れてます。 http://projecteuler.net http://odz.sakura.ne.jp/projecteuler/ 問題の和訳 23: Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.事前に範囲内のabundant numbersを計算しておいて、2重ループでabundant numbersの和になっている数をハッシュに。最後にハッシュにヒットしない数を足す。あまり早くない。もっといい方法があるのかなあ。 24: What is the millionth lexicographic permutation of the digits 0, 1,
Luceneの曖昧検索を100倍高速化したアルゴリズム - nokunoの日記
@nobu_k さんのつぶやきでこのエントリを知りました。Changing Bits: Lucene’s FuzzyQuery is 100 times faster in 4.0Luceneで曖昧検索を効率化した話です。 最初の実装では、転置インデックスを全探索して編集距離がN以下の単語を拾っていたレーベンシュタインオートマトンという、編集距離がN以下の単語のみをアクセプトするオートマトンを利用することにした 単語ごとに構築したレーベンシュタインオートマトンをマージするという操作が必要になるが、なかなかうまくいかなかった 難解な論文を見つけたが、実装は難しかった良いライブラリを見つけたので、PythonからJavaに移植した 最後に1つだけ残ったバグは、移植の失敗ではなく元ライブラリのバグだった。報告すると1日で直ってきた。この前のエントリでは、有限状態トランスデューサを使った辞書の圧縮
機械学習超入門II 〜Gmailの優先トレイでも使っているPA法を30分で習得しよう！〜 - EchizenBlog-Zwei
最近の論文で The Learning Behind Gmail Priority Inbox D.Aberdeen, O.Pacovsky & A.Slater というのがある。これはGmailの優先トレイで使っている機械学習のアルゴリズムについて解説したもの。というと難しそうな印象があるが、この論文で紹介されているPassive-Aggressiveという手法は実装がとても簡単。なので今回はこれについて解説するよ。 参考資料: Gmail - 優先トレイ Online Passive-Aggressive Algorithms K.Crammer et al. The Learning Behind Gmail Priority Inbox読んだメモ - 糞ネット弁慶 わかりやすい日本語解説 機械学習超入門 〜そろそろナイーブベイズについてひとこと言っておくか〜 - EchizenBl
10兆までの素数リスト - 雷雲の変奏曲
プログラミングコンテストチャレンジブックを読んでいたら、素数リストの作り方が出てきた。 そういえば、１０兆までの素数リストを作ってみる、なんて記事があったな。 これだ http://itpro.nikkeibp.co.jp/article/Watcher/20100519/348242/?ST=develop 読み返しているうちに、ついつい挑戦してみる気になってしまった。 色々試して意外だったのが、10億までの素数をリストアップした場合でも「試し割り」より「エラトステネスの篩」の方が100倍以上も高速だったことだ。リストが大きくなればその差はますます開いていく。 メモリ上の広い範囲をまんべんなくアクセスするエラトステネスの篩は、実際には効率が悪いのではないかと思ったりしたのだが、見当が外れてしまった。 考察してみるに 試し割りは意外と無駄が多い。まず素数の密度だがn/log(n)に従うらし
「第3回自然言語処理勉強会＠東京」でCSAについて発表します - EchizenBlog-Zwei
@nokunoさんの好意で「第3回自然言語処理勉強会＠東京」でCompressed Suffix Arrayについて発表させていただくことになりました。 つきましては参考のため発表資料を以下に置いておきます。参加される方はもちろん、興味のある方はご覧になっていただけるとうれしいです。 第3回自然言語処理勉強会＠東京 : ATND 第3回自然言語処理勉強会＠東京を開催します - nokunoの日記 なお本資料は以下の皆様のアドバイスを頂きました。ありがとうございました(とくに@overlastさんには4-5時間もお付き合い頂きました。おかげさまでスライドの質が大幅アップしました。感謝)。 @overlastさん @tamago_donburiさん @tsubosakaさん @machyさん
Suffix Array(接尾辞配列)を学びたい人のためのリンク集 - EchizenBlog-Zwei
私がCompressed Suffix Arrayを学ぶのに参考にした資料へのリンクをまとめてみた。 CSAだけじゃなく、これからSuffix Arrayを学ぶ人にも便利かもしれない。 解説記事 # ［を］ Perl による Suffix Array の実装] SUFARYの開発者、たつを氏による解説 perlで20行くらいでSuffix Arrayが作れる 入門用におすすめ # DO/Suffix Array 岡野原氏によるSuffix Arrayの解説記事 高速化などの高度な話題が豊富 中級者向け # white page Suffix Arrayのリンク集が充実 多くのライブラリが公開されている ツール・ライブラリ # SUFARY 臨時復旧ページ たつを氏によるSuffix Arrayライブラリ 非常に使い勝手が良い # sary: Suffix Arrayのライブラリとツール 高
Donald Knuth, Volume 4 A (Combinatorial Algorithms)
Links to .pdf files are uncorrected; published versions are up-to-date. Corresponding .ps files are on archive.org, with links below in orange. My balance at: The Bank of San Serriffe, Financial Fiasco. Somber essay: Infreq. Asked Quest., Letter to Rice, Cartoon. Interviews: 2014-05-20, 2008-04-25, 2005-09-04, 2001-10-05, 2000-01-25, 1993-12-07 Volume 4A, Combinatorial Algorithms: Part 1 Title Pre
プログラミングコンテストチャレンジブック - カメヲラボ
ついに出た！！！！！！！！ プログラミングコンテストチャレンジブック 作者: 秋葉拓哉,岩田陽一,北川宜稔出版社/メーカー: 毎日コミュニケーションズ発売日: 2010/09/11メディア: 単行本（ソフトカバー）購入: 52人 クリック: 1,538回この商品を含むブログ (83件) を見るamazonで即予約したのに13日〜15日発送などという酷いメールが届いたので、近所の書店へダッシュして参りました。 本当は全部読んでから紹介記事を書こうと思っていたのですが、CHAPTER 3の途中まで読んだ時点ですでに素晴らしかったので早々にキーボードを叩いているわけであります。これはね、プログラミングを学ぶすべての学生に読んでほしい。何が素晴らしいかって言うと、 ・データ構造やアルゴリズムの基本的なことを網羅している ・割と平易な言葉で簡潔に説明されている ・具体例が多い ・計算量を常に意識して
行列分解ライブラリredsvdを公開しました - DO++
大規模疎行列向けの行列分解ライブラリredsvdを公開しました． redsvd 大規模疎行列向けの特異値分解や主成分分析，固有値分解を行うライブラリredsvdを公開しました． 修正BSDライセンスで公開しており，コマンドラインから使える他，C++ライブラリが用意されています． 例えば，行と列数がそれぞれ10万，非零の要素が1000万からなる疎行列に対する上位20位までの特異値分解を約2秒で処理します． 特異値分解とか，使っている技術の詳細とか応用事例を以下に簡単に紹介しましたので，興味のある方は参考にしてください． 特異値分解とは まず行列を適当に復習します．行列Xの転置をX^tと表すことにします．またIを単位行列とし，Oを全ての成分が0である零行列とします．また，行列XX^t=IであるようなXを直交行列と呼びます．Xが直交行列の時，Xvはベクトルvを長さを変えずに回転させます．ここでは
Vertical Codeはunary符号の6倍すごい - EchizenBlog-Zwei
Vertical Codeを実装してみたらunary符号のときよりデータサイズが1/6になった。とても感動したので、この気持ちを伝えるため記事を書いてみるよ。 Vertical Codeを使うことになった経緯は↓を参照 Vertical Codeを調べたよ - EchizenBlog-Zwei Vertical Codeはその名の通り、データをVerticalに持っておく符号形式。デルタ符号くらいのデータサイズで収まる。だったらデルタ符号でいいじゃんと思うのだが、Vertical Codeにはselect()、rank()という操作が簡単に実装できるメリットがある。 select(pos)とはpos番目のデータ値の累計値を求める操作。rank(value)とは累計値がvalue以上になるはじめてのposを求める操作。互いに逆関数の関係にある。(unary符号を用いたときとrank()、se
5分でわかる(かもしれない)圧縮の基本 - EchizenBlog-Zwei
大規模データを日常的に扱う人にとって、データ圧縮は基本。絶対ないと困るわけではないけど、あると格段に世界が広がる。ドラクエで言うところのルカニみたいなもの。 でも圧縮というとデータをバイナリで持たないといけないとか、なんとなく面倒なので目を背けがち。そこで5分でわかるような感じで説明を書いておく。 基本的な圧縮の方法は差分圧縮というのがある。今回はこれを説明する。 char型のデータが8つ並んでいると考える。 6 3 2 1 7 5 4 8とりあえずバイナリにしてみる。便宜上、縦に書く。 6 3 2 1 7 5 4 8 =============== 1の位:0 1 0 1 1 1 0 0 2の位:1 1 1 0 1 0 0 0 4の位:1 0 0 0 1 1 1 0 8の位:0 0 0 0 0 0 0 1 16の位:0 0 0 0 0 0 0 0 32の位:0 0 0 0 0 0 0 0
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
DSIRNLP#03 ウェーブレット行列 最速攻略~予告編~ - EchizenBlog-Zwei
