Javaで簡潔ビットベクトル(37)

簡潔ビットベクトルの圧縮タイプの実装を調べていて、以下の論文を読んだ。Re-Pair(さらっと文字列本に書いてあるよ)という文法圧縮を利用している。実際の実装は、4章にあります。場合によっては、RRRの実装よりも良いようだ。ただし、アクセス性能は良くな…

廃線ウォーキング

桜の名所ということだったので、3/30に旧福知山線の廃線を歩いてきました。 投稿するのにだいぶ時間がたったけどwww一応、JR的には入ってはいけないことになっているらしいので、入る場合は自己責任でお願いします。(ただ、ハイキングコースとしてかなり知ら…

Javaで簡潔ビットベクトル(36)

細かい改善ですが、シリアライズ可能にしました。 これで、簡潔ビットベクトルをファイルに保存することができます。 以下からダウンロードできます。https://code.google.com/p/sbvj/TRIEやウェーブレット木やFM-Indexで使おうと思うとファイルに保存したい…

Javaで簡潔ビットベクトル(35)

簡潔ビットベクトルの最新の論文を読んでみた。Space-Efficient, High-Performance Rank & Select Structures on Uncompressed Bit Sequences Dong Zhou, David G. Andersen, Michael Kaminsky, SEA'13, 2013.http://www.cs.cmu.edu/~dga/papers/zhou-sea201…

Javaで簡潔ビットベクトル(34)

Combined SamplingとRRRを結合してみた。以下にあります。https://code.google.com/p/sbvj/BuildTypeにCS_RRRを指定すると動きます。 t:63 s:63 × 32 = 2016 selectのサンプリング間隔:4096としました。性能は、以下ぐらいです。 CPU : Intel(R) Core(TM) i5…

Javaで簡潔ビットベクトル(33)

先日、RRRの完備辞書をリリースしましたが、ちょっと実装を間違えていたこともあり、性能がちゃんと出ていませんでした。修正したので、再度、アップロードします。https://code.google.com/p/sbvj/ざっくりとrankの性能を測定すると、以下ぐらいです。 Bitm…

Javaで簡潔ビットベクトル(32)

RRRの完備辞書を実装した。https://code.google.com/p/sbvj/境界付近は相変わらず怪しいかもしれないですが、ある程度は動くはずです。文字列本のp.52-54を参考にしつつ、以下の論文の方法で実装しました。Fast, Small, Simple Rank/Select on Bitmaps Gozal…

Javaで簡潔ビットベクトル(31)

疎なビットベクトルに対する完備辞書を利用できる場合について、さらに考えてみた。 メモしておく。こんな感じで、一文字だけUCS-2の範囲を超えた文字が存在すると、上位ビットのビットベクトルはかなり無駄なので、こういう時に疎なビットベクトルに対する…

Javaで簡潔ビットベクトル(30)

疎なビットベクトルに対する完備辞書が利用できるケースについて考えてみた。「複数の文書をまとめたFM-Index(CSAでもいいけど)からの文書IDの復元」で利用できると思う。複数の文書をまとめたFM-Indexから文書IDを復元する時は、以下のような感じになると思…

Javaで簡潔ビットベクトル(29)

疎なビットベクトルに対する完備辞書を作ってみました。以下で公開しています。https://code.google.com/p/sbvj/以下のようにして使えます。 public void test001() throws SuccinctBitVectorException { long sbvSize = 64; SuccinctBitVector sbv = new Su…

ビットシフト

個人的メモ。Javaのビットシフトで、 int i = 1 << 32として、iに0が入ると思っていましたが、1になるみたい。知らんかった。 0を取得したい場合は、 int i = (int) (1L << 32L);longでビットシフトして、intにキャストする。

Javaで簡潔ビットベクトル(28)

疎なビットベクトルのaccessとrankとselectをサポートしようとして、久しぶりに実装しようとしていたら、かなり追加しにくい感じになってたので、ソースをリファクタリングして、メソッドを整理しました。定数時間のselectですが、 0のみの定数時間(1は、log…

開発環境のバージョンアップ

会社でEclipseを久しぶりにダウンロードしようとしたらバージョンが4.2になってた。http://www.eclipse.org/downloads/だいぶ良くなってるみたいなんで、家のEclipse環境もバージョンアップしてみた。学生時代は、Emacsのみでプログミラングしてましたが、最…

FM-Indexで気になるところ

通勤の電車の中で漠然と脳内でN-gram IndexとFM-Indexを比べてて、気になるところをメモとして書いておく。 動的な更新が難しい。まぁ、これは研究が進めば解決されそうな気はするが、現在は難しそう。 基本、オンメモリで動作する。まぁ、N-gram Indexに比…

日帰り温泉

関西の日帰り温泉で定番の有馬温泉に行ってきた。http://www.arima-onsen.com/三宮駅からバスが出てるので、簡単に行ける。今回は、自分で車を運転して行きました。寒すぎたのであまり写真を撮れませんでした。あまり温泉街っぽいのが撮れてなくて残念です。…

FM-Index

BWTとウェーブレット行列を使って、FM-IndexをJavaで実装してみました。BWTのソースコードは以下にあります。ちょっとバグを見つけたので、気が向いたら直します。http://rn.hatenablog.com/entry/2013/02/16/115423ウェーブレット行列のソースコードは以下…

Wavelet Matrix

一部で大ブームのWavelet Matrix(ウェーブレット行列)をJavaで実装してみました。 以下を参考にしました。高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)作者: 岡野原大輔出版社/メーカー: 岩波書店発売日: 2012/12/27…

BWTとInduced Sorting

BWT(Burrows Wheeler Transform)を行うプログラムをJavaで書いてみた。一応、Unicodeのサロゲートペアの範囲でも問題なく動くので、あらゆる言語に適応できる。BWTは、Suffix Arrayから定義に従って構築している。なので、実質的なメモリ使用量や構築時間は…

ノートPC

学生の時に買ったレッツノート(CF-W7)の保証期間(4年)が切れたので、調子が悪くなってきたら買い替えようと思っている。5年も使ったが、まだまだバリバリ動いているので、今すぐというわけではないが(ただ、バッテリーはだいぶヤバい)。もう自分の用途的にノ…

すごい久しぶりに

USJに行きました。寒かったです。車で行ったんですが、駐車場のスペースが削減されて、立体駐車場になっていました。その代わり、昔、駐車場だったスペースにハリポタランド(仮)が建設されてました。http://www.usj.co.jp/wwohp/release/いや~、めっちゃ期…

振り返ってみて

去年の2月に着想して、提案して、1年間、C言語でN-gramベースの全文検索エンジンの実装を毎日やってた。だいぶ詳しくなりました。 なんとかできあがったので、振り返ってみる。性能って結局のところ I/Oコストの削減 CPUコストの削減 という結論に至りました…

文字列操作

NLP

こんな良書が出ていたとは知りませんでした。すぐに買いました。高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)作者: 岡野原大輔出版社/メーカー: 岩波書店発売日: 2012/12/27メディア: 単行本購入: 11人 クリック: 29…

初詣

1/5に世界遺産の下鴨神社に初詣に行きました。下鴨神社が通称だとは知らなかった。正式名称は、「賀茂御祖神社」というらしい。http://www.shimogamo-jinja.or.jp/実は去年も行ったのですが、今年も行くことにしました。なんとなく雰囲気とかが好きです。夏…

Javaで整数列圧縮(4)

前回作成したBitBufferクラスを使って、Gamma Codeを実装します。Gamma Code自体は、すでに説明したので、そのコードを以下に示します。 /** * * <p> * Gamma Codeによる整数値圧縮を実装するクラスである。 * </p> * */ public class GammaCode { /** 圧縮対象の整…

Javaで整数列圧縮(3)

さて、JavaでGamma Codeを実装していくわけですが、ビット単位でデータの入出力を行えるクラスが必要です。まずは、そのクラスを作ります。データは、ビット単位で入力され、ビット単位で出力されることになりますが、Javaではバイト単位でしか管理できませ…

Media Goに曲を追加する方法

個人的メモ。 iTunesを使っていてMedia Goに曲を追加する場合は、Media GoでiTunesフォルダを監視対象にしておく。 iTunesでCDをインポートする。 Media Goを起動する。 これで、Media Goの起動時にiTunesにインポートした曲を参照することができる。

Javaで整数列圧縮(2)

前回説明した可変バイトコード(Variable Byte Code)は、最小でも1バイトでしか圧縮できませんでした(以下では、VBCodeと表記します)。これは、1や2のような非常に小さな数値でも1バイト必要ということです。つまり、まだ無駄な部分があるのです。例えば、2進…

いろいろあって

Twitterを始めることにしました。https://mobile.twitter.com/ryokkieええ、それだけです。

Javaで整数列圧縮(1)

整数列圧縮について、Variable Byte CodeからNew PForまで実装してみて、実験してみようと思います。整数列の圧縮はいろんなところで使われていて、身近なところでは、検索エンジンの文書IDの圧縮に使われることが多い。なぜ、圧縮が必要かと言うと、通常、i…

腹八分目

12/1に嵐山の天龍寺に紅葉を見に行った。雨が降っていたこともあって、人はまだマシというぐらいの少なさだった。それでも多かったけど。たぶん、2月ぐらいに行けば空いているのでは?と思う。天龍寺は、靴を脱いで中に入れて、畳の上から庭を鑑賞できる。か…