MG勉強会の後にid:sleepy_yoshiさんに教えてもらったWSDM 2009における講演"Challenges in Building Large-Scale Information Retrieval Systems"で述べられている符号化方式のGroup Varint Encodingを実装してみた。 資料 講演スライド スライドの日本語による解説記事 整数の符号化方式 転置インデックスなどで文章番号のリストを前の値との差分で表すなどの方法を用いると出現する、ほとんどの値は小さな値となるためこれを4バイト使って表現するのは記憶容量の無駄である。 このためVarint Encoding、ガンマ符号、デルタ符号、Rice Coding、Simple 9、pForDeltaなど様々な符号化方式が提案されている。このうちVarint Encodingは実装が手軽なことからよく用いられて
![[IR] Google WSDM'09講演で述べられている符号化方式を実装してみた - tsubosakaの日記](https://cdn-ak-scissors.b.st-hatena.com/image/square/d5a026a6225c4524c834d0237efa271b5b0d54f0/height=288;version=1;width=512/https%3A%2F%2Fsiteproxy.ruqli.workers.dev%3A443%2Fhttps%2Fogimage.blog.st-hatena.com%2F17680117127124028144%2F17680117127124030436%2F1557332443)
ちょうど二年ぐらい前，機械学習で疎ベクトルの圧縮に情報検索でよく使われる整数列の圧縮技術を使うことを検討したことがあった（オンライン学習でキャッシュを実装してみた - ny23の日記）．そのときは，オンラインで圧縮し Disk に保存，圧縮したベクトルは陽にメモリに置かず読む（OS に任せる）という実装で，（Disk IO のオーバーヘッドが大きく）圧縮さえすれば何を使っても大差なしという身も蓋もない結論になった（結局2行で書ける最も単純な Variable byte code を採用）． それ以降は整数列圧縮アルゴリズムに関する知識も NewPFD ぐらいで止まっていたのだけど，つい先日，現時点で最速の圧縮アルゴリズムの提案＋ここ数年の主な整数列圧縮アルゴリズム（Simple-8b (J. Software Pract. Exper. 2010), VSEncoding (CIKM 20
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
