DSIRNLP#2で発表しました「作ろう！簡潔ビットベクトル」
DSIRNLP#1に続いて今回の#2も発表の場をいただきました。今回は簡潔データ構造、とくに最も基本的なデータ構造である簡潔ビットベクトルについて発表しました。@overlastさん、@kimurasさん、@rindai87さんをはじめ関係者、参加者の皆様どうもありがとうございました。
twitterでも紹介しましたが発表資料リンクを置いておきます。
第2回 データ構造と情報検索と言語処理勉強会 #DSIRNLP - ［PARTAKE］
DSIRNLP#1で発表しました「TRIEにトライ！〜今日からはじめるTRIE入門〜」 - EchizenBlog-Zwei
なお質疑では以下のようなものがありました。
・popcountを使った二分探索をするときのpopcount値はいつ持っておくの？
=>直前の64bit毎の線形探索時に使ったものを残しておいて使いまわすよ。
・スライド20のV[i]はV[i / B]なのでは？
=>間違ってました。すみません。。(2011/12/12: スライド修正しました)
・marisa-trieのビットベクトルが速度重視なのは、トライではビットベクトルのサイズは決定的な要素ではないからです。
=> その通りですね。説明不足ですみません。。
・rank(O(1))とselect(O(logN))の速度が同じなのはおかしいのでは？
=>うっ。後ほど見直します。。
(2011/12/12: 密ベクトルの再実験しました。最初の実験では一定範囲の数値を順番に引数としてrank/selectしていたのですが引数をランダムな数値に変更して実行したら割としっくり来る結果になりました。)
ux: rank(21.3sec), select(23.5sec) rx: rank(19.4sec), select(26.2sec) marisa: rank(19.9sec), select(21.7sec)
・ビットベクトルの値に変更があるとRank辞書の更新が大変では？
=>基本的に簡潔ビットベクトルはstaticなものとして扱うよ。
もし本発表を聴いて(読んで？)簡潔データ構造に興味を持たれましたら、さらなる勉強のために以下のリンク集をご利用ください。
