Java

文法圧縮(4)

前回、紹介した論文で、かなりざっくりとRe-Pairを実装してみた。An Online Algorithm for Lightweight Grammar-Based Compression. Shirou Maruyama, Algorithms 2012, 2012.バグもいっぱいあると思うし、後処理もさぼってはいるが、それなりに動く。 class…

Javaでのテスト

仕事上は、Cやったり、Javaやったりな生活ですが、家での開発は、Javaを使ってます。https://code.google.com/p/sbvj/テストには、主にJUnitとEclEmmaを使っているんですが、ネット上に情報がたくさんあるってわけではないんで、我流で使ってます。ふと、も…

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

密なビットベクトル、疎なビットベクトル、偏りのあるビットベクトルのそれぞれに対して完備辞書をJavaで作って公開している。https://code.google.com/p/sbvj/今後、改良する点もあるかと思うが、現在の実装でrankとselectの性能を測定した結果を報告してお…

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

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

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…

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から定義に従って構築している。なので、実質的なメモリ使用量や構築時間は…

Javaで整数列圧縮(4)

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

Javaで整数列圧縮(3)

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

Javaで整数列圧縮(2)

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

Javaで整数列圧縮(1)

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

JavaでWavelet Tree(7)

さて、別な形のWavelet Treeに対して、rank操作とselect操作を行ってみますが、実際の実装のWavelet Treeに変換してみようと思います。まず、今まで、見てきたWavelet Treeは、以下です。ここで、各ノードに必要なのは、簡潔ビットベクトルだけなので、Sの情…

JavaでWavelet Tree(6)

懐かしいわ~。作業がかなり中断しましたが、Wavelet Treeに対するrank操作とselect操作について説明していきます。 rank操作とselect操作は、以下のような操作です。 rank(i, c) : i-1の位置までに現れるcの数を取得する。 select(i, c) : i-1番目に現れるc…

JavaでWavelet Tree(5)

さて、Wavelet Treeの解説を続けます。前回までで、文字をグループ化することで、簡潔ビットベクトルで表現できることがわかりました。 このとき、文字のグループに対するrank操作とselect操作は可能ですが、文字に対するrank操作とselect操作はできません。…

JavaでWavelet Tree(4)

仕事が忙しくてなかなか更新できなかったのですが、任意の文字列に対するrank操作とselect操作を実現するWavelet Treeについて実装を進めていきます。さて、前回までは、Wavelet Treeを利用しない強引なやり方で、任意の文字列に対するrank操作とselect操作…

JavaでWavelet Tree(3)

さて、任意の文字列に対するrank操作とselect操作を簡潔ビットベクトルで実現してみます。簡潔ビットベクトルは自作のsbvjという簡潔ビットベクトルのライブラリを利用します。http://code.google.com/p/sbvj/sbvjを利用すると以下のようなコードで実現でき…

JavaでWavelet Tree(2)

さて、任意の文字列に対するrank操作とselect操作を行えるようにしていきます。これを実現するための簡単な方法の一つとして、簡潔ビットベクトルを利用するやり方があります。 ビットベクトルは、0と1がひたすら並んでいるデータ構造です。このとき、任意の…

JavaでWavelet Tree(1)

さて、JavaでWavelet Treeを構築してみようと思います。Wavelet Treeは、任意の文字列に対してrank操作とselect操作を効率良く行えるようにしたデータ構造です。 まず、Wavelet Treeの説明は、簡潔ビットベクトルの知識を前提とします。簡潔ビットベクトルに…

コードカバレッジ

Javaでの自動テストのためにJUnit4を使ってみた。 Visual Studio 2010の自動テストは使ったことがあったので、それほど違和感なく使うことができた。一応、プロなので、コードカバレッジも知りたいと思って、やり方を調べてたら、「Eclipse + JUnit + EclEmm…

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

クラスの使い方をざっくりと書いたJavadocをアップしました。http://code.google.com/p/sbvj/現在、JUnitによるテストを進めています。 テストが完了したら、0.0.3としてアップロードしようと思います。