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としてアップロードしようと思います。

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

さて、sbvjで実装している定数時間のselect操作について説明してみたいと思います。まず、rank操作とselect操作の定義を示します。 rank操作とは、ビットベクトルBとして、b=(0 or 1)がiまでに出現する数を求める操作です。 また、b=1の場合のrank操作をrank…

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

FF6のボス戦の曲は最高です。作業をかなり妨害されたわけですが、前回の記事で性能測定した定数時間のselectをsbvjに実装したので、以下で公開します。http://code.google.com/p/sbvj/sbvj-0.0.2.jarをダウンロードして、インポートするだけで使えます。以下…

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

定数時間のselectを実装してみようと思い、以下の論文の手法を実装してみた。Fast Computation of Rank and Select Functions for Succinct Representation. Joong Chae NA, et al., IEICE, 2009.前回の性能測定と同様の条件で、性能測定を行ってみた。 「si…

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

sbvjを作りながらふと今時は、64bitアーキテクチャに最適化しないといけないなぁと思って、64bitアーキテクチャに最適化した簡潔ビットベクトルがあるのかなぁと思って調べてみたら以下のような論文があった。Broadword Implementation of Rank/Select Queri…

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

GW中に長崎〜熊本を旅行しながら新幹線での移動時間と寝る前などの空き時間に少しずつ作って、一通り動くようになったので、公開してみた。http://code.google.com/p/sbvj/jarファイルをインポートするだけで使えます。 現状の課題としては、機能落ちしてい…

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

さて、今年は、オープンソースとして、プロダクトを公開していくことに決めていたので、簡潔ビットベクトルのソースの整理を始めた。 そのために、SVNでバージョン管理ができる環境も整えた。ついでに、公開するための環境も必要だろうということで、Google …

Javaで簡潔TRIE(4)

さて、トライのイメージが掴めたところで、より実装に近いところを考えてみます。まず、前回までに作成したトライを示しておきます。キー集合Kは、以下のようなものでした。 K = { internet#, interest#, japan#, jar#, kyoto# }また、このキー集合Kから作成…

Javaで簡潔TRIE(3)

さて、トライの説明を進めていきます。前回の記事で作成したトライは以下のようなものです。ここでは、トライを使った検索について説明します。 ここで、以下のような関数を導入します。 g(n, a) = mこの関数は、ノードnにいる時に、文字aが入力された場合の…

Javaで簡潔TRIE(2)

さて、トライ(TRIE)について、もう少し説明したいと思います。まず、3つの文字列を持つキー集合Kを考えます。 K = { internet, interest, japan, jar, kyoto }まず、この5つの文字列をトライではなく、ソートした状態で保持し、2分探索で求める場合を考えま…

Javaで簡潔TRIE(1)

さて、今回からは、気分を変えて、簡潔なTRIEをJavaで作ってみたいと思います。この「簡潔な」というのがポイントで、じゃあ、ただのTRIEって何なの?という疑問になるわけです。TRIEというのは、木構造の一種で、正確には、トライ木と呼ばれるものです。 な…

Javaで簡潔ビットベクトル(まとめ)

長かった簡潔ビットベクトルシリーズも、一応、終わりにしたので、今までの記事のリンクをまとめておきます。ビットベクトルJavaでビットベクトル(1)Javaでビットベクトル(2)Javaでビットベクトル(3)Javaでビットベクトル(4)Javaでビットベクトル(5)Javaでビ…

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

さて、前回の記事で設定した実験条件で、rank操作とselect操作の性能を測定してみました。まず、rank操作の結果をグラフにしたものを以下に示します。1%となっているのは、ビットベクトルの密度です。 この結果から、rank操作の性能が2^25あたりからビットベ…

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

今週は、出張も多く、なかなかまとまった時間も取れず、実装が遅れてしまいました。 一応、出張先でコーディングぐらいは終わらせようとEclipseの環境をコピーしてノートパソコンに入れてみたけど、自宅が64bitのWindowsを使っていて、ノートパソコンが32bit…

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

さて、今回は、前回の記事で説明していないgetWordSelectメソッドについて、説明してます。getWordSelectメソッドは、32bitのビットベクトルから指定した数の1が出現する位置を返します。 32bitのビットベクトルにselectが実行できると考えてもらえれば良い…

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

今回も引き続きselectの実装を進めていきます。前回までで、8bitのselectの値を高速に取得できる表を作成しました。今回は、高速なselect操作(2分探索版)を実現できるメソッドを作ってみます。まず、BitVectorクラスに以下のメソッドを定義します。 public l…

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

今週は、仕事が忙しく、週末まで更新できませんでした。まぁ、それはさておき、今回は、表引きを利用したselectを実際に実装してみます。まず、rankの時と同じように、selectの表引き用の表を作るところから行います。 BitVectorUtilityクラス(ユーティリテ…

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

さて、今回は、selectの表引きについて、検討します。まず、rankの表引きについて復習します。 rankの表引きは、以下のような1の数を取り出すためのテーブルを用意するのでした。 RANK_TABLE[ 0 ] = 00000000 = 0 RANK_TABLE[ 1 ] = 00000001 = 1 RANK_TABLE…

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

さて、前回に引き続き、selectの実装をしていきます。 もう定義は書かないですが、わからなくなったら前回の記事を見てください。前回の記事で、高速なrank操作用のブロックを使って、2分探索でselectを計算するという戦略にしました。 ただ、rankの場合は、…

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

さて、selectを実装する戦略を考えます。まずは、復習としてselectの定義から始めます。 selectの定義は以下でした。 select(B, count, b)また、select操作とは、以下のような内容でした。 ビットベクトルBとして、b=(0 or 1)がcount + 1回出てくる位置の中…

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

さて、今回からselectの実装に取り組んでいきます。selectの実装はrankに比べると多少厄介です。 ただし、rankの時と基本方針は同じです。 ナイーブに実装すると性能が悪くて使いものになりません。 なので、rankと同じように補助的なデータ構造を利用するこ…