DO++

Tx

いつもプログラム作りっぱなしだったので、解説とマニュアルを書いてみました。Tx。省スペースなtrieです

とりあえず出すところまで行きたかったので最低限の実装と解説しか書いていませんが、これから少しずつ書き足していきます。

結局、これを使って今何ができるかというと、キー集合があったら、それらに（入力順ではないが）固有の番号を0から順に付けられて、Txを使って、キーの番号を引くことができる（もしないなら、NOTFOUNDが返ってくる）。
大体入力キーのトータルの長さの半分ぐらいのスペースでできます。

アプリケーションを作る場合は各キーに付随するデータをvectorとかにキーの数だけいれておいて、それらをTxを使って参照、操作することになります。その例も作らないと

loud (level-order unary tree)とよばれる木のsuccinct な表現を使ったアプリケーションを作ってみたかったことからやってみたのですが、double arrayなみに高速化できれば用途もでてくるかなぁと。今はselect操作を適当にさぼっているので遅いと思うのですが、きちんと実装すればキャッシュも効いてきて速くなるかな。

ALENEXとSODA

ALENEXでの発表も無事終わり、今は発表聞いたり、部屋で修論を書くべく悶絶していたり街をぶらぶらしたりしてます。
今、ニューオリンズでは数学の学会もあって５０００人ぐらいの数学者が街にいるらしい。

発表聞いたり予稿集をざっと読んだところで（僕が）面白そうな話
Faster Filters for Approximate String Matching [pdf]
近似マッチングにインデクスを使って候補を絞るものでsuffix filters (suffix arrays/treesを内部で使う）を提案

A Near-Optimal Algorithm for Computing the Entropy of a Stream [pdf]
ストリーム問題（データを全部同時に見れない、メモリに一部分しかのらない）でデータのエントロピーの近似を求める

Ultra-succinct Representaiton of Ordered Trees [pdf]
順序木の最新版。ほぼ全ての操作を実装。さらにtypicalな木に対してさらに小さくなる（nノードの2分木はn bitで表現可能）

Making Deterministic Signatures Quickly
S⊂Uに対して、各Sの要素から|U| >> |T| となるようなT上への単射を求めるdeterministicな方法を提案。これを再帰的に適用するとSから|T'|=O(log|S|)までの単射が求まりsignatureとかに使える。best student paper

Succinct Indexes for Strings, Binary Relations and Multi-labeled Trees [pdf]
圧縮索引は索引とデータが密に結合している場合が多いが索引だけを別に持つことを提案。データの方が自由にencodeできて、瞬時復元可能なデータ構造とかを使える

A Simple Storage Scheme for Strings Achieving Entropy Bounds
圧縮したまま好きな場所のデータをO(logn) bit 分瞬時復元可能なデータ構造をテーブルと符号化だけでする。BWTした後のデータを提案方法で符号化した場合の解析もある

疎なbit arrayに対する現実的なRank/Selectデータ構造

久しぶりに研究紹介。

最近書いた論文です。
"Practical Entropy-Compressed Rank/Select Dictionary.", Daisuke Okanohara and Kunihiko Sadakane.
In the Proc. of ALENEX 2007, to appear[paper]

この論文では、疎なbit array B[0...n-1]に対するrank/select操作を高速に実現するデータ構造を4つ提案しています。 rank(x)はB[0...x]中にある1の数を返し、select(x)はx番目の1の位置を返す関数です。
古典的な問題ですが、これを最小（entropyに近い限界）かつ高速（定数時間、もしくはそれに近い時間）で実現する現実的なデータ構造は存在しませんでした。これを4つの違ったデータ構造で実現したというものです。
このデータ構造はsuccinct data structureを構成する上で不可欠なもので、今まで各データ構造毎に、疎なbit arrayを効率よく保存する方法がデータ構造の特徴を利用することで提案されていたのが、これを使えば統一的に解決されます。

実際どう作って、どういう特徴があるかはペーパーを参照してください。

このデータ構造はそれ以外にも使える場面があって、例えば、単調増加列の整数列を保存する場合も、その整数がある場合にはその位置のbitは1、それ以外が0であるようなbit vectorで保存すれば、selectを使って整数をランダムアクセスできます。
具体的に転置ファイルの例では、0番から100万番まで文書番号があって、ある単語が出ている文書番号を小さい順に保存する場合を考えたとき、この単語が6万文書で出現しているとしたら、これを保存するのにはそのままでは60000*32bit = 240KByteかかるのですが、提案したデータ構造(この用途にはsdarrayがいいかな）を使うと60000 * (2 + 4)bit = 45K Byteぐらいで保存できます。さらに二つの整数列のintersectionをとることもできます（i番目の位置のbitを取得する操作はrankの操作と同様にしてできる）。

また、疎な行列（やグラフ）を保存するのにも使えて、今いろいろ試しているところです

御茶ノ水飲み

昼間論文書き。夜発表。深夜飲み。今学校でvista敗戦。寝る。

Kautz-Zeckendorf符号

符号化（文字列を0と1からなるビット列に変換）に求められる性質として元の文字列に正しく復元できることはもちろんですが、他に瞬時復元可能（前から順番に文字を確定できる）なども要求されます。今日紹介するKautz-Zeckendorf符号(KZ符号）は変わった性質を持っていて、符号化されたビット列を途中からみても、どこが文字の始まりかがわかるという符号です。

KZ符号の面白い点は符号化にフィボナッチ数列を利用しているということです。
フィボナッチ数列 f(0)...f(n)はf(0)=1, f(1)=1 が最初に与えられ、f(n)=f(n-1)+f(n-2)として定義される数列で1,1,2,3,5,8,13...とふえていきます。このフィボナッチ数列の性質の一つに、全ての自然数はフィボナッチ数の和で表すことができ、このとき、同じフィボナッチ数は２回使うことなく、また隣り合うフィボナッチ数は使われないことが知られています。# f(1)はじまりと考えます

さて、この性質を符号化にどのように利用するかというと、ある自然数Nをビット列に変換するとき、そのビット列のi番目は、もしf(i)がNの和を表現するときに使われるのならば1、そうでないならば0とします。

例えば、
1 = 1 　 # 1
2 = 01 # 2
3 = 001 # 3
4 = 101 # 1 + 3
5 = 0001 # 5
6 = 1001 # 1 + 5
7 = 0101 # 2 + 5
...
というかんじです。このビット列には先程の隣合うフィボナッチ数は使われないという性質から1であるbitは連続しないという性質があります。
KZ符号は先程のビット列のそれぞれの頭に110をつけたビット列をその文字の符号とします。

1 = 110 1
2 = 110 01
3 = 110 001
4 = 110 101
...
するとデータの途中で"110"を見つけた場合にはそこが文字の始まりだということが分かります。

この符号はもともと同期を取ったりするときに使われていたのですが、最近 "FM-KZ: An Even Simpler Alphabet-Independent FM-Index."[link(ps.gz)]で提案された新しい圧縮全文索引では入力文字列をKZ符号でまず符号化してビット列に変換し、得られたビット列に対してFM-indexを作るという方法を提案しています。
変換したことにより、ビット列に対する問題になっているので、FM-indexの構築や検索が簡単になります。以前提案されたHuffman符号を使ってビット列に変換する方法では変換前の文字との同期をとる必要があり余計なデータ構造を使っていましたが、KZ符号を使うと、自然と同期がとれ作業領域量が小さいという利点があります（上の例の場合、110で始まるsuffixはsuffix arrays上では一箇所に固まっている）。

他にも使えそうな符号です。

bwtの圧縮率解析

Burrows-Wheeler Transform (blocksortingと同じもの。以下bwt)はbzip2などで利用されている文字列に対する可逆変換です（詳細は勉強会資料とかググってください）。bwtを適用した後のテキストは同じ文字が連続しやすい圧縮しやすいデータとなり簡単な後処理（MTF変換+order-0圧縮）を加えることでLZ法よりも圧縮率は高く、PPM法に匹敵するぐらいに小さくなることは実験的に示されていました。
しかし、どのくらい小さくなるかの理論的解析はあまり進んでおらず、bwt後の処理に関してはもっといい方法があるはずだと研究が進んできました。

最近発表された話(compression boosting, The Engineering of a Compression Boosting Library: Theory vs Practice in BWT compression,A Simpler Analysis of Burrows-Wheeler Based Compression）はこの問題に対し大きな前進を見せており、理論解析値が（bzip2などの）実測値にかなり近づいています。詳細については見てもらうとして、興味深いのは最初にBurrowsらによって提唱された後処理（mtf + order0)が、もっと改善できるのではないかという予想に反して実はかなり優れた方法で、最近提唱されたcompression boostingやwavelet treeを利用した方法と圧縮率は似たようなものだいうことことが示されているところです。しかもそれを非常にシンプルな方法で実現しているということで再評価がされています。

個人的には解析でゼータ関数がでてきて驚いた。本質的に関係しているわけではなく、たまたま証明ででてきたものと思うけど。

Range Coder

CodeZineでRange Coder (RC)の記事を書きました。
高速な算術圧縮を実現する「Range Coder」

RCは高速な算術圧縮として知られています。
動く原理の解説や実際に動くコードもあるので興味のある方はどうぞ。

＃今までの記事、全部先頭に"高速な"ってついてる。。

勉強会 Succinct Data Structure

今日は東工大で行われた勉強会に参加してきました。
今回は私の発表もあり、Succinct Data Structureを発表してきました。
[資料 ppt, pdf]

作り始めたのが結局ぎりぎりになってしまい、後半の説明が雑になってしまったのが残念。以前作ったものをもっと詳しくしたかったのですが・・

他の方々の発表は違う分野ばかりで勉強させていただきました。同じ概念でも分野で用語が違う場合が多いので一苦労。その後の飲み会ではいろいろな話。測度論を勉強しようかなぁと少し思いました。少し。

帰り道、ぼけーっと自転車で走っていたら何がおきたか良く分からないが、タイヤ前輪が曲がり走行不能になり自転車を駐輪場に戻し歩いて帰る。

部分復元可能なデータ圧縮

通常の（可逆）データ圧縮は入力データを圧縮して保存し、それを利用する場合は、全て復元して元のデータに戻してから利用する。この場合、圧縮した後、データの一部分のみを利用したい場合においても、全てを復元してからでなければデータを利用できない。

これを解決する最も簡単な方法は、データを小さいブロックに分割してから、それぞれを独立して圧縮し、一部分だけ利用する場合は該当するブロックだけを復元することである。しかし、この方法では、ブロックが小さい場合、全体の情報が利用できず圧縮率は著しく低下する（1kBのデータを圧縮した場合と1MBのデータを圧縮した場合の圧縮率は数倍違う）。

この問題を解決するため、圧縮アルゴリズム自体に（高速な）部分復元操作を備えさせる方法ががいくつか提案されている。

Static PPM(pdf@dcc2004,pdf@comp-nhc2006)は圧縮に用いるためのモデルをPrefix Treeで表現し（Prefix Treeは各contextの次の文字の出現確率をコンパクトに表現する）圧縮したデータと一緒に保存する。入力データを小さいブロックに分けてそれぞれを独立に圧縮し、圧縮した後の位置を保存しておくところまでは最初に紹介した方法と同じだが、全体の情報を利用したモデルをどの位置でも利用できるのでブロックを小さくしても圧縮率は低下しない。例えばブロックサイズが4KB程度でも、bzip2などと同程度の圧縮率である。

Compressed Suffix ArraysやFM-indexなどの圧縮全文索引なども部分復元可能なデータ圧縮法としてみることもできる。これらは元々、任意のパターンを検索するための索引だが、元データを必要せず、また任意の位置から部分復元可能であることも知られている。この本質はBurrows Wheelers変換（bzipの復元を途中から行う）を利用していることである。詳細はfull-textのサーベイ（version 2できたて）を参照。

さらにこの考えを推し進めて連続するlog n bit（nは入力データ長）を定数時間で復元可能なデータ圧縮法が提案されている。これが意味するところはlog n bitのメモリを定数時間でアクセスできる計算モデルにおいては、アルゴリズム中のデータ参照をこのデータ圧縮を通じた参照に置き換えても計算量は変わらないということである。

"Squeezing Succinct Data Structures into Entropy Bounds", Sadakane and Grossi SODA 2006　はデータをLZ78法でパーシングしてフレーズ列に分解し、それぞれに番号をつけたものを保存する。フレーズ列はLZ-trieで保存する。このtrieは括弧列で表現された木で表現される。部分復元する場合はこのtrie上の対応するノードまでのパスを復元する。この操作はlookupテーブルを組み合わせることで定数時間で行える。これによりlog n bitの部分復元を定数時間で実現している。

一般の圧縮法を利用した方法も提案されている（"Statistical Encoding of Succinct Data Structures.", Gonzalez and Navallo, CPM 2006　ps.gz)。これはStatic PPMとよく似ているが、この方法ではモデルは明示的に持たずに全てのlogn の復元表をテーブルで保存している（ただし、これを実現するためには、かなり入力長が大きくなければならない）

ESPer2006

今日はESPer2006で発表＆デモしてきました。スタッフの皆様準備ごくろうさまでした。

この一週間はあまり寝ない状態でぶっとおしでプログラミングしてたので、結構ふらふらだったのですがプレゼン＆デモの反響があってよかったです。疲れがふっとびました。まだまだいきますよー

Canonical Huffman Code

昔書いた記事やコードを書き直して、CodeZineに投稿しました。[link]

長さ制限付きの場合もreverse package merge法[link]を使って最適な符号を求められるようになっています。ずっと以前に長さ制限付きの最適符号を求める方法はないのと聞かれ、いずれ用意しますと答えたままでした。３年目にして提供できました。しかし、長さ制限付きの場合の構築アルゴリズムはがちがちに最適化していなくて、必要な作業領域をもっと減らせるのですが、それはまたいつか・・

succinct representation

Succinct　（簡潔な） representation (SR)は、近年データ構造界隈で盛んに研究されている分野です。

SR は固有名詞となりつつあり、現在の定義では、あるデータ構造のcardinarity （場合数）がLの場合に、そのデータ構造を (1+o(1))log L bit で表し、様々な操作を定数時間で行えるようなデータ構造を指します（と思います）。 logL bitというのはそのデータ構造を表すために必要な最低限の情報量なので、それと比較しわずかな補助データ構造を使って様々な操作を定数時間で行えるもので、時間、領域ともに限界を目指しているデータ構造です。

この概念はデータ圧縮と似ています。データ圧縮は、情報をできるだけ小さく保存、伝送する目的がありますが、そのデータを使いたい場合は基本的にはデータを元に戻す復元操作が必要になります。それに対しSRは圧縮した状態のまま、その上で様々な操作を行えるところが違います。もちろん元のデータ自身を参照することはできますし、列挙やある条件を満たした要素の頻度計数などができます。

現時点では、bit array (0と1からなる配列）、tree, permutation, function, graphなどに対するSRが提案されています。Compressed Suffix ArraysやFM-indexもテキストに対する一種のSRとして考えることができます。テキストの一部分を参照（復元）することができますし、任意の部分文字列検索をできたりするからです。

一般のテキストの部分復元をしようという話自体は、私がやったStatic PPMやLZ法を使ったもの [K. Sadakane and R. Grossi: Squeezing Succinct Data Structures into Entropy Bounds]があります。

よく研究されているtreeに対するSRでは、節点と葉の合計がn個であるtreeを2n bitで表現しつつ節点の子や兄弟、親、二つの節点の共通最小祖先とかを定数時間で求められるようなものが提案されています。今年もいくつか新しい表現方法が提案されているようです。

これらの多くは最初、理論的に構成したものが多く実際に実装してみるとうまくいかなかったものも多かったですが、最近は現実に即した表現方法の研究も盛んとなり、利用しているところも多くなってきているようです。

そのうちこれらの研究成果のいくつかがさらに洗練されみんながライブラリなどで普通に使えるようになるのでしょう。

電子情報通信学会

総合大会に行ってきました。企業の人がとても多くみんなスーツでちょっと心配になりましたが、発表する場所に入るとみんなスーツじゃなくて安心しました。
発表についての資料はここにあります
"大規模データ利用のためのデータ圧縮", 岡野原　大輔 (ppt、pdf）

以前の任意の位置からの瞬時部分復元可能なStatic PPMの話や整数列の符号化を行うVertical Codeと呼ばれる符号について。やはり計算量解析などをきちんとやってほしいという話だった。

Static PPMに関しては今ある技術をきちんと使えば、性能はもっと上がるだろうなぁ。暇になったらやろうかな。たぶん忙しくなったらやってしまうんだろうなぁ。

殆ど寝ていない＆食べていないということで夕方は激しい体温低下を招きピンチになりましたがカレー食べて復活。夜は仕事の打ち合わせでした。結構飲みました。

suffix arraysやいろいろ

suffix arraysの話は半年置きぐらいに書いているのかなぁ。
(ココログ全文検索機能無くて、不便ですね・・以前どこに書いたのか分からない。）

私が以前書いたSuffix Arraysの構築方法の記事が古くなってきたので（分かりにくいし）、近いうちにライブラリと一緒に内容も更新しようかなと。今回は、忘れないうちにメモも兼ねてSuffix Arraysの高速な構築方法について。

構築で今一番速いのは、msufsortとimproved two-stage (プログラム名はdivsufsort）(its)法だと思います。これらはデータサイズに対して線形時間で構築できる方法では無いのですが、大抵のデータでは線形時間の方法より高速に構築することが可能です。

msufsortはsuffix arrays:SAを直接構築するのではなく、その逆の値であるinverted suffix arrays:ISA を構築します（SA[i] = k ⇔ ISA[k] = i 　が成り立つ)。なぜISAを作るかというと、SA構築時にすることは suffix の順位を決定することなのですが、この決定の際、ISAが（途中まででも）分かっていれば直接文字列同士を比較せずにISA同士を比較して順位が決定できるので、文字列の順位を少ない比較回数で決定することができます。あとはtwo-stage法と同様に、ある条件を満たしたsuffixの順位は他のsuffixの順位から直接求められる性質を利用し高速化をはかっています。
# qsufsortも同じようにISAを構築する方法とみることができますがqsufsortは全体のISAを更新していくのに対し、ISAは一部分のsuffixから順にISAを決定していきます（そしてソートせずに直接順位が決定できるところはソートせずにとっておく）。詳しくはmsufsort1.0の解説を読んでください。

itsはtwo-stage法の変種で最近提案された方法です（もしかしたら前に誰かやったかもしれませんが・・）。Suffix Ti = T[i...n]　集合 i=0...nが与えられた時、SuffixをAとBの二種類に分類します。AはTi > Ti+1 Bは Ti < Ti+1 であり、ここの不等号は辞書式順序です（Tの最後には$という他のどの文字より小さい文字を置いておき必ず順序が決定できるようにしてある）。AかBのSuffix Arrays中の順位が決定できれば、残り片方の順位は直接（線形時間で）求められるのですが、ITSでは更にBのSuffix Tiの中でTi+1がAであるSuffix を B*とし、B*のSuffixだけをソートします。B*がソートし終わったら残りBの順位を直接求め、そしてAの順位を求めます。B*であるsuffix の割合は全Suffixの大体1/3程度なので、大雑把にいって3倍高速に計算できます。
moriさんによる実装では更に、B*のソートを工夫しています。まずko-alulu法と同様に、まずB*のSuffixの先頭毎にTを分割し、それら各部分列の順位を決定した後に、その順位を新しい文字集合とみなして新しい文字列T'を構成し、それをlarsson - sadakane法（いわゆるqsufsort）でソートします。全体のアルゴリズムでも、テキスト長がnの時5n byteしか消費しないlight-weightな方法です。

これだけいろいろな方法がでてきても、まだまだ速度は要求されます。自分で実装したところではどちらも大体1秒あたり2MBぐらい処理できるぐらいで、これは昔から比べればはるかに速いのですが、巨大なデータを処理したい場合には結構またされます。これ以上の高速化を図ろうとしたら、データの冗長性（k次エントロピーの意味で）を利用するのが一つかなぁとぼんやり考えています。

圧縮されたCSAもしくはwavelet treeを直接構築する方法もでてきており、それらを高速に処理する方法もいろいろ提案されていますが、それはまたの機会に。

---
他に見つけたおもしろそうな論文
"Statistical Encoding of Succinct Data Structure", Rodrigo Gonzalez, Gonzalo Navarro. TR/DCC-2006-1 [ps.gz]

SODA 2006で出た"Squeezing Succinct Data Structures into Entropy Bounds", K. Sadakane and R. Grossi: が実現している任意の位置からの瞬時復元（定数時間）をLZ78を使わずに通常の算術圧縮とかで実現したよという話。私がDCC2005で発表したStatic PPMに似ている。ちゃんと書けばこう化けるのね・・むむむ

同じところでついでにみつけた
"Practical Constructuion of k Nearest Neighbor Graphs in Metric Spaces", Rodrigo Paredes, Gonzalo Navarro, TR/DCC-2005-6 [ps.gz]　も面白そう。詳しくは読んでいないが、高次元で高速なk-NNは欲しかったところ。

これらを読んでいて面白いのがtheを使うところをdeと間違っているところ。英語はどこの国でも難しいよね。

HDD

数TBのデータで実験しようとしているが、ノートPCのHDD残り容量が５０MB切って不安定。単位がよくわからなくなって、１０Gぐらいいいよなぁってデスクトップにおいてしまっているのがいけないのかもしれない

最近、DBの勉強（SQLとかではなく、ディスクアクセス回数の少ないアルゴリズムとか）をしてます。以前紹介したstxxlとか使ってみたり。DBもすごく奥が深いなぁ

実験

aoe3は危なすぎる。封印しないといけない。以前みんゴルで廃人となりかけたときの二の舞になってしまう。

圧縮索引を使って大きいデータで実験開始。いろいろ新しい結果を入れてプログラミングし直してます。

複数単語の同一文書中の共起頻度を高速に求められないかなぁと模索中。既に論文ありそう。前に先輩に共起頻度を効率良く保存、かつ高速に求められるデータ構造は無いのかと聞かれたのだが、分からなかった。

昨年末ぐらいに書いた記事がcodezineで公開されてます。
succinctなbit vectorとwavelet tree

こういうアルゴリズム系の話は、論文読むよりもソースコード読む方が分かりやすい場合もあります（今回の私のソースが分かりやすいかは別として。。）。私自身wavelet treeは論文では分からず、moriさんのソースを読んで初めて理解しました。

掃除

することが多くなって、掃除したくなってしてました。
マシン群を整理。使ってないものを押入れにまるごといれてサーバーとして使おう

使いそうなマシンは、synergyをいれて、Windows, Mac, UNIX上のディスプレイ行き来できて、単一のキーボード・マウスで操作できるようにする。とても便利

圧縮索引の資料

夏のプロシン以降、いろいろなところで発表して変わったのでアップしておきます。CSA、FM-index、括弧木について書いてあります。間違っていたりコメントがありましたらメールなどで連絡をください。

「2005-12-compInd.ppt」をダウンロード

上のpdf版
「2005-12-compInd.pdf」をダウンロード

mumumu

遅れに遅れたやつを実装している中、６時ごろ、研究室を数か月訪問していた方のお別れ会があることをすっかり忘れていた。研究室の方々と白木屋へ。後半、芋焼酎がボディブローのように効いてくる・・。

忘年会も兼ねているということで今年一年を振り返ってみた。１年はとにかく速かった。２０超えてから速くなってるよなぁ・・

そのあとカラオケ。昼飯コロッケ食べてたということもあり、コロスケを歌った。

ミスマッチの実装

Suffix Arraysを使ってミスマッチ検索を実現する論文が出ていて、これをwavelet tree + FMindexでもできるのではということで実装。

ターゲット長n、ターゲットのk次エントロピーをH_k、パターン長m、アルファベット数A、が与えられた時、ミスマッチを最大k（ここでのミスマッチはedit distanceの意味。削除、置換、追加からなる）まで許す、ターゲット中のクエリーにマッチする全てのポジションをnH_k bit 作業領域を用いて((mA)^k *m * logn + occ * logn)　もしくは　((mA)^k * log^2 n + occ * log n)時間で報告できる、ただしoccは報告個数。

やっているのは、最初にパターン中の全ての部分列に対応するsuffix arrays中の領域をwavelet treeを使って求める(O(m^2))。あとはそれらを組み合わせて、クエリーにミスマッチが加わった形の新しい候補を作って調べている。（明示的には作らずに端から順に作る。）
例えばクエリーに"missisippi"が与えられたら"m","mi","mis",...,"i","is","iss",...,"pi","i"と全ての部分列に対応するsuffix arrays中の領域[sp,ep]をそれぞれ求める。次にこれらを順に組み合わせる。例えば3文字目のsが無くなったものを探すフェーズでは"mi"に対応する[sp1,ep1]と"sisippi"に対応する[sp2,sp2]を表からとってきて"mi":"sisippi"に対応する領域[sp,ep]をlognかmの速い方で求める。

実用的には(mA)^kの部分は殆どが候補を作る途中でターゲット領域に無いことがわかって打ち切られるので、もっと小さい。

prefix-freeの正規表現もこの勢いでできないかなぁ。夏ごろやるぞと言ったまま。

圧縮全文索引

のまとめサイトみたいなものができてました。[link]
テストセットや評価方法を整備して次の研究を促すのはとても大切なことだと思います。
サーベイ論文も最近の話を網羅していてよくできると思います。

圧縮索引のまだ解決していない実用上の問題は、直接、圧縮索引を高速に構築する手法と、2次記憶領域をうまく利用する手法（一般的には、アクセスがシーケンシャル、局所的であるデータ構造）がないことでしょうか。どちらもいくつか論文が出ていますが、まだまだ改善の余地がありそうです。

CRF

Conditional Random Field (CRF)に関しての発表準備をしていて、ここ最近のCRF関連の話を集めて読んでみた。キーワードだけ集めてみてもDynamic CRF、Skip CRF、Piecewise CRF、Semi-Morkov CRF、モデルが複雑になった時の近似手法としてもvariational approach、MCMCなどなど研究はとても盛ん。自然言語処理、Computer Vision、Bio Informaticsとかでの応用も進んでいるみたい。

でも、そんなことはともかく私は最初のところ考え込んでいる。
CRFは従来の生成モデル（HMMとか）と比較し、オーバーラップしているFeatureを気にせず自由に入れられて学習出来る点が優れているといわれている。

この理由をp(X,Y)ではなくp(Y|X)でモデルを作っているから、明示的にp(X)を求めるプロセスが必要ないからできるのだと自分は思っていたのだが、いろいろ突っ込まれてみるとどうもはっきりしない。p(X,Y)を求めることもできるし。
そっちが理由ではなく、Log linearモデルだから実現できている話もあったが、それはMaximum Entropy法から導出されているものであり自由にFeatureを入れられる議論とあまり重なっていない気もする。（例えば、式だけ見ると、それぞれのFeatureが他の気にせずに独立に利いている形になっている）　パラメータが重ね合わせを考慮して学習しているといえば、正確なのかなぁ。

そうなると、MEで学習した結果は、基底が独立っぽいやつを自動的に選ぶようになっているのか。いや、そこまではしていなくて、オーバーラップがあっても、学習器は基底がそれぞれ独立しているモデルを使った上で最善を尽くして学習できるという感じでいいのかな。

MEの論文をもう一回読み直してみよう。今ならきちんとわかるかもしれない

転置ファイル

転置ファイルのプログラムをさくさくと書いてみる。そして、いろいろな整数符号化法を試してみる。
転置ファイルでは単語が出現していた場所を位置の整数列で保存するが、そのまま整数で保存せずに圧縮するとかなり小さくなる。この整数符号化法はかなり奥が深いし、まだまだ研究が続いている。Binary Interpolative Coding とか、Recursive Integer Codingとか。Wavelet Treeも実は転置ファイルに使えるということは、あまり知られていない。（Wavelet Treeがそもそもあまり知られていない）

これについても、そのうち記事で書きます。

LZMA

のアルゴリズムについてOSASKの川合さんから話を伺いました。（LZMAは7zipが使っている圧縮法です。）
LZ法ではもうやることはないと思ってましたが、こういうことがあったのかと思わされました。CABもこれを使っていたらしいうわさなので、圧縮率が高いのも納得。詳しい技術解説は現在書いてて、そのうち記事で出る予定。

そのまま

次の日突入。今日が課題締め切りなのだ。このCSAのインクリメンタル構築ができなければ・・ということで終わるまで家に帰らないことにする。昼頃ようやくできたっぽい。whiteさんのいろいろな実装を参考にさせてもらいました。そして、でかいファイルでいろいろな性能実験。1GBぐらいのデータぐらいまでは大丈夫みたい。でもそれ以上はThinkPadが悲鳴をあげているのであまりやらないことにする。昔もノートパソコンで実験しまくってHDDが壊れたし。

課題は出したが、その後もバグっぽいのを除いていく。これを使ったアプリケーションもそろそろ整備しないとなぁ。全部作りっぱなし。発表までがんばるぞ

アルゴリズム談義

バイトの人たちとアルゴリズムの話となる。

グラフマイニング。特にGastonについて。　gspanより10倍ぐらい速いらしい。このTech Reportが詳しい　
基本的な方針はグラフマイニングで候補部分グラフを少しずつ大きくしていくのだが、そこでもし候補部分グラフがパスや木ならば閉路を含むような複雑なグラフの相同性チェックとかはいらないので簡単なチェックですませてしまおうというQuick Startの方針

skiplistとその拡張について。skiplistはAVLや赤黒木などの平衡木の難しい実装を使わなくても、ランダマイズドアルゴリズムを使うと簡単な実装で平衡木と同じようなことができますよという素敵な話。この方針は木だけでなくほかのいろいろなアルゴリズムに使える。実際にグラフとかへの拡張がすでにやられている。

Cache-Oblivious Algorithmはこの場で初めて聞いた。Reading list Cacheを意識したアルゴリズム設計をする場合は普通、キャッシュの特性（ラインサイズやライン数）を意識してそれをパラメーターにいれるが（例えばラインサイズにぴったりあうようにバッファリングするとか）、このアルゴリズムを使うとそのパラメーター項がなぜか最後の計算量項から消えて、どのようなキャッシュ構成であっても（キャッシュミス回数とかの観点で）最適なアルゴリズムとなる。理論だけじゃなくて実際のアルゴリズム（例えばFunnnel sort/heap）も存在する。

そんなに眠くないよ

実装めきめき。ここしばらくずっとSuffix Arrays/Trees関連。結構いろいろなことが現実的な計算量、メモリでできるようになってきた。後は詳細実験か。勉強もかねてFM-indexを実装しておこう。メモリいくらでもほしいなぁ。明日の発表準備。ぐひぃー

コンピュータ将棋

ミーティングで研究員の方による今年のコンピュータ将棋選手権で優勝した激指の実装内容等いろいろ聞く。以前、教えてもらったとき、激指が強かったのはもちろん将棋の局面が一次元評価関数で表現されているのに衝撃をうけたが、実装内容はもっとやばかった。用いている手法もすごい上に激チューニング。

優先して探索する場所を求める方法と、それぞれの局面での評価値を求めるところとが今はわかれているが究極的には連続的につながるのだろうか。そうなると人と同じようにもっと探索する場所をはっきりと検討をつけて数十から数百局面しか求めなくてもすむようになるのかなぁ。

その後は論文直しといろいろ他の人の実装を調査中。

Compressed Suffix Tree

去年演習３で調べてから、ちょうど１年目で動くところまできました。感無量。論文調べた時は実際に動くかどうか怪しかったのですが、いろいろなアイディアを組み合わせて動きました。

今回、CSTの実現に不可欠な（厳密）単調増加列の符号化について、rangecoderのようにbit演算をほとんど無くした方法を開発しました（再発見かもしれないが）。単調増加列の符号化とは、S=(1,4,7,10...,)のような数列に対して、select:N番目の数を返せ（例select(2)=4 select(4)=10))、rank:N以下の個数を求めろ(例 rank(1)=1,rank(3)=1,rank(5)=2)という二つの操作を定数時間で行える符号化が要求されます。実際にどれくらい速いのかとか、符号化効率はどうなのとかいろいろありますが、それは今後じっくりやります。テーブルサイズを小さくしてキャッシュにのったり、アクセスを必ずシーケンシャルにするようになどと実装面でもがんばってます。

まだまだ実装しなくてはいけないものがたくさんあーる。時間との勝負

Snowbirdまとめ

ソルトレイクシティのSnowbirdで開催されたDCCに行ってきました

最近のアメリカは出入国検査が厳しくなっているときいていましたが、確かに厳しかったです。荷物に鍵をかけてはいけないし、いろいろと怪しまれて検査に時間がかかります。入国時に１時間ぐらいかかりました。ソルトレイクシティについたときは雨で、Snowbirdについたときにはものすごい雪になっていました。レセプションでは、ヨーロッパの特許屋の人達となぜか機械翻訳について話す。

泊まったのはThe Cliffというところで、結構いいところでした。おいしかったし、ネット使えたし。Snowbirdはスキーの名所ということで、学会だけ出て帰ったらもったいないということで、学会が終わって残りの半日でスキーして、コースをまわれるだけまわってきました。レンタルはスキー板と靴だけしかできないということで、普段着ですべってきた無無計画ぶり。前日まで記録的な大雪だっただけに雪もいい感じで眺めもよく、楽しめました。

日本に帰るときにソルトレイクシティからサンフランシスコへ行くところで、飛行機が遅れて、サンフランシスコで駆け込み乗機。すごい危なかった。

初アメリカで感じたのは、英語は本気を出されるとほとんど聞き取れないということと、それと同時に聞き取れなくてもそんなに問題ではないということ。変な意味、日ごろしていたガイドの成果が。ご飯はまぁまぁおいしかったですが毎日ビュッフェであきました。時差ボケは最後まで直らなかった。

DCCは、圧縮関連で大きな学会の一つであり、圧縮と名のつくものなら何でも発表されてます。イメージ、音楽、映像圧縮が多く、純粋なテキスト圧縮は少なくなってました。

--
学会で面白かった話。

A.Moffatの"Binary Codes for Non-Uniform Sources" linkでは、整数符号化における復号スピードと圧縮率を両立した新しい整数符号法を提案してました。整数を符号化する場合は、unaryでこれから符号化するbit長さ、binaryでその実際の符号語を表現し符号化するのが基本ですが、彼の提案では多くの場合連続する整数値が似ている値なので、このunaryを隣合うN個の要素ずつのmaxをとって表現しようというもの。たとえば符号しようとしている整数(>=0)が3,5,2,9のときunary(lg(n+1))は2,3,2,4となりますがN=2の時は3,4、N=4の時は4を符号化します。maxをとっているのでbinary符号化の時に少し無駄が生じますがそれでもunaryが減るメリットが大きい。しかも連続してN個の復号でunaryは復号する必要がないので速い。このN個まとめた列をさらに再帰的に同じ整数符号化を用いて符号化します。（Nは4,16,64・・と増やしていくので大きなデータでも階層は3,4ぐらい）。実装は上のリンク先から手に入ります。

E.Bergmanの"Fast decoding of prefix encoded texts"は、Huffman法などのprefix encodの復号の高速化の提案。prefix codeの復号は木をたどるのではなく実際は表を使って行い、圧縮対象アルファベットを確率が大きい順にソートできるのであればcanonical huffman法が使えて、そうでなければ、Huffman木の各節点を状態だと考えて固定bit数を読み込んだとき、次にどの状態に遷移するかのオートマトンとして復号できることは知られています。Bergmanはこのオートマトンがものすごく大きくなってしまう問題点を指摘し、この状態を深さがM以下の節点だけに定義しそれ以外に遷移するような場合は bitを巻き戻す方法を提案してました。こうすると復元はちょっと遅くなりますが、表は小さくなって、実用的という話です。

F.Heklandの"Using 2:1 Shannon Mapping for Joint Source-Channel Coding"は歪み有り圧縮（転送にノイズ有り）の符号法の話。入力が2次元、それを1次元で情報を伝送し、復元側でまた2次元のデータとして取り出す問題で、1次元のところでノイズが入りレートが決められてます。このとき、2次元から1次元へのマッピングにアルキメデスの螺旋（この左）を使うというもの。2次元中の点をこのアルキメデスの螺旋の一番近い点で近似し、Θを伝送すると、これがかなり転送限界に近いということが理論的に解析されてました。

D.Chenの"Optimized Prediction for Geometry Compression of Triangle Meshes"はポリゴンデータの圧縮の話。ポリゴンデータは各点の三次元データとどの点同士がつながっているかのトポロジー情報からなっており、前者の圧縮が難しいことが知られています。現状知られている方法では、三角形を折り返して次の三次元データを予測し符号化するもの。彼の発表ではどのような順番で予測すれば最適に符号化できる問題かをMST問題に帰着するというもの。

自分のも英語を直して近くアップします。

SA

ちょっと、目を離すと研究はあっという間に進むもので、Suffix Arraysも去年まとめて書いたころとはかなり状況が変わっているみたい。

yuuさんのページがSuffix Arraysに関して、この一年でかなり充実してきて、すばらしい。いろいろな手法の比較検討もしているし。ただ、線形時間のやつは速くないってのはもうちょっと工夫すれば使えると思う。教えてもらったことではあるが、mod3で分ける方法とかは途中で普通のSA構築アルゴリズムに切り替えれば結構速く使える。100Mとか超えてくると差がちゃんとでてきそう。

結局、二段階ソート（それをさらに儘田さんが発展させたやつ）と線形ソートはどっちが速いんだろう。アルファベットサイズによるといわれればそれまでだが、これが最強ってないのかなぁ。メモリ量も問題になるけど。

まぁ、構築するのは一回だけだから、実用的にはそんなに問題にならないんだろうけどねぇ。それよりは利用する際のメモリ、速度のほうが問題なんだろうなぁ。でも、構築は奥が深くて面白い。

エンジニア

CSA（Compressed Suffix Arrays)やらCST(Compressed Suffix Trees)は、理論はよく構成されているが、それをいざ実装しようとなると、いろいろ大変なところがある。算術圧縮の場合も理論的に最適なことが示された後に、実際に高速かつ低領域で実装も簡単にして動かすために、たくさんの改良が必要だったことを考えると、まだまだ、たくさんやることがあるんだろうなぁと。

卒論の文書分類の方は未だにテストセットと既存手法の実装で彷徨っています。圧縮と同じで数字がバンと出るのは面白いなぁ。早くEnju結果を入れて試してみたい。Rubyでがしがし書いてます

横浜

で一泊二日の未踏の昨年度の成果報告とキックオフがありました。たくさんおもしろそうなのがありました。

帰りに寝過ごして東京越えて埼玉までいってしまった。

文書クラスタリング 文書分類

調べて見たら、うわさにはきいていたけど盛んすぎ・・　何読んで、見たらいいんだー。かたっぱしからよんでいくしかないか。単語ベースのベクトル空間で分類、LSIとかはいいとして、他にもSuffix Treeをつかってクラスタリングとかもある。集めた論文がざっと３０ぐらい。関連調べたら１００こえるなぁ。このへんは今から参入するとすごい競争にまきこまれるから、もうちょっと未開拓なものも考えて見るか。
最近思いついたものが既にありそうな気がしてどきどき。今まで何度、悲しい思いをしたことか。

直前

ですが、今日学校で発表する予定のプログラムがまだ動いていません。修羅場

Skip List

カテゴリが授業名みたい

データを保持する二分木は、バランスが崩れて探索時間が悪化する場合があるので、平衡化して深さを均等にする必要があります。

例えば、AVL木は、どの節点も、その節点が持つ、二つの子の高さの差が１以下になるようにするという制限を加えることにより平衡化をはかっています。
また、赤黒木は全ての節点が赤、黒のどちらかの色を持ち、(1)もし節点が赤なら、その子は二つとも黒 (2)NIL nodeは黒 (3)根から葉へのパス上にある黒の接点の個数はどれも同じ　という制限を加えて平衡化をはかります。

どちらも、新しい要素を挿入したり、削除したりして、この制約が守られなくなったときは、平衡になるよう、回転操作などを行わなければなりません。

Skip Listの情報はここから得ました。
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dv_vstechart/html/datastructures_guide4.asp

その一方で、Skip Listは、ソート済みリストを保持しておきます。それぞれの要素は次の要素へのポインタだけを持っておきます。
ただ、このままだと、探索は順に調べていかなければならないので、平均(要素数/2)回比較を行う必要があり、全然役に立ちません。そこで、Skipの文字通り、次の要素だけではなく、更に先の要素へのポインタを持つようにします。例えば、2で割り切れるindexを持つ要素が2個先の要素へのポインタを、4で割り切れるindexを持つ要素が4個先の要素へのポインタを持つ、8で・・・としておきます。すると、ある要素xの探索を行う場合には、8個先にある要素とxが小さいかかどうかを比較し、もし大きいなら、8個先に移動して調べるということになります。
これは二分木で、もしその節点で調べて、大きいか、小さいか調べて、大きいなら右の子を調べる（つまり左の子、その子孫をskipしている）ことと同じです。この時の探索時間は要素数がN個のとき、O(lg(N))です。

ただ、挿入、削除を行うとなると、2で割りきれるindexが2で割り切れなくなったりしてしまい、バランスが崩れてしまいます。
そこで、理想的な状況では、2個先の要素へのポインタを持つ要素は全体の50%、4,2個先へのポインタを持つ要素は25%、8,4,2個先へのポインタを持つ要素は12.5%・・という観察から、新しい要素を加える場合には、0.5の確率で2個先へのポインタを持つ要素とする、0.25の確率で4,2個先へのポインタを持つようにする・・・とします。

こうすることにより、ほとんどのデータにおいて、うまく理想的な状況と同じ状況が作り出せます。削除のときは単純にとりのぞいてしまいます。（削除の時は、確率0.5で2個先の要素へのポインタを持つ要素を取り除いていることになり・・）

こうして作られる、SkipListは、AVL、二色木などの平衡二分木と同様の性能を持ちながら、実装が簡単という利点があるそうです。