転置インデックスの圧縮技法
転置インデックスは、検索エンジンの実装において、中心的な役割を果たすデータ構造である。 転置インデックスのデータ構造とアルゴリズムは、クエリ処理アルゴリズムとともに、検索エンジンの性能に直結する。とくに大規模な検索エンジンにおいては、キャッシュ効率を高めてクエリ処理を高速化するために、転置インデックスの圧縮は必要不可欠となっている。 この記事では、転置インデックス、とくにポスティングリストの圧縮について、近年の手法を簡単にまとめる。 目次 転置インデックスの基本 転置インデックスのデータ構造と特性 転置インデックスのアクセスパターン 近年のインデックス圧縮技法 Variable-Byte Family VByte Varint-GB Varint-G8IU Masked-VByte Stream-VByte Opt-VByte Simple Family Simple9 Simple16
英語論文執筆のために arXiv からの例文検索サービスを作った話
arXiv の論文から例文を検索する Hyper Collocation というサービスを公開しました． 以下はあまり整理されていない製作の記録です． 英語論文執筆用の例文検索サービス 英語での論文執筆の際に，専門用語を含む例文や言い回しのパターンを知りたいことが多々あります．有用なサービスとしては ライフサイエンス辞書のコーパス検索 Springer Exemplar (2018/2/1頃に終了) がありますが， データがライフサイエンス系の論文に限られている（ライフサイエンス辞書） ソートの基準が頻度順ではないため典型的な例文が上位にこない ストップワードに近い頻出語を検索した際の 検索が重い（Springer Exemplar） 表示可能な検索結果が偏る（ライフサイエンス辞書） という不満点があったので，並行して個人的な資料から検索を行うプログラムを作って使っていました． しかし，個
GitHub - powturbo/TurboPFor-Integer-Compression: Fastest Integer Compression
TurboPFor: The synonym for "integer compression" ALL functions available for AMD/Intel, 64 bits ARMv8 NEON Linux+MacOS/M1 & Power9 Altivec 100% C (C++ headers), as simple as memcpy. OS:Linux amd64, arm64, Power9, MacOs (Amd/intel + Apple M1), 🆕(2023.04) Rust Bindings. Access TurboPFor incl. SSE/AVX2/Neon! from Rust 👍 Java Critical Natives/JNI. Access TurboPFor incl. SSE/AVX2/Neon! from Java as f
Vertical Codeはunary符号の6倍すごい - EchizenBlog-Zwei
Vertical Codeを実装してみたらunary符号のときよりデータサイズが1/6になった。とても感動したので、この気持ちを伝えるため記事を書いてみるよ。 Vertical Codeを使うことになった経緯は↓を参照 Vertical Codeを調べたよ - EchizenBlog-Zwei Vertical Codeはその名の通り、データをVerticalに持っておく符号形式。デルタ符号くらいのデータサイズで収まる。だったらデルタ符号でいいじゃんと思うのだが、Vertical Codeにはselect()、rank()という操作が簡単に実装できるメリットがある。 select(pos)とはpos番目のデータ値の累計値を求める操作。rank(value)とは累計値がvalue以上になるはじめてのposを求める操作。互いに逆関数の関係にある。(unary符号を用いたときとrank()、se
5分でわかる(かもしれない)圧縮の基本 - EchizenBlog-Zwei
大規模データを日常的に扱う人にとって、データ圧縮は基本。絶対ないと困るわけではないけど、あると格段に世界が広がる。ドラクエで言うところのルカニみたいなもの。 でも圧縮というとデータをバイナリで持たないといけないとか、なんとなく面倒なので目を背けがち。そこで5分でわかるような感じで説明を書いておく。 基本的な圧縮の方法は差分圧縮というのがある。今回はこれを説明する。 char型のデータが8つ並んでいると考える。 6 3 2 1 7 5 4 8とりあえずバイナリにしてみる。便宜上、縦に書く。 6 3 2 1 7 5 4 8 =============== 1の位:0 1 0 1 1 1 0 0 2の位:1 1 1 0 1 0 0 0 4の位:1 0 0 0 1 1 1 0 8の位:0 0 0 0 0 0 0 1 16の位:0 0 0 0 0 0 0 0 32の位:0 0 0 0 0 0 0 0
Run-Length Compressed Suffix Array
This web page will no longer be updated. See the author's web pages for further releases. RLCSA [4, 3, 7] is a compressed suffix array implementation that has been optimized for highly repetitive text collections. Examples of such collections include version control data and individual genomes. This implementation also serves as a testbed for many techniques used with compressed suffix arrays. The
転置インデックスの圧縮 - tsubosakaの日記
Managing Gigabytes勉強会で転置インデックスの圧縮の話が出たので実際に圧縮を行った場合にどれくらいのサイズになるかを計測してみた。 利用したデータは英語版Wikidiaの全記事で 文書数 2,872,589 単語数 2,735,620 転置インデックスのポインタの数 397,603,176 ぐらいのサイズのデータです。 無圧縮の転置インデックスのフォーマットは 単語ID,文書数,文書1,....文書N, 単語ID,...で各項目4byteとなっており、1.5Gぐらいのサイズになっています。 これに対して各圧縮アルゴリズムを適用した結果は アルゴリズム 無圧縮 Variable Byte Code unary符号 γ符号 δ符号 Rice Coding pforDelta(仮) サイズ 1537MB 497MB 239475MB 474MB 407MB 367MB 455MB
画像圧縮アルゴリズム (10) 算術符号化
Range Coder復号化処理による数直線の変化は、以下のようになります。 復号化の場合、数直線は常に0からRangeまでの範囲になります。符号が数直線上のどこに位置しているのかをチェックして、Rangeを復号化されたデータが持つ範囲に変換するところは、やはり算術符号化での処理と本質的に変わりありません。 処理方法は以上になりますが、ここでいくつかの問題を解決する必要があります。まず一つは、符号化と復号化での計算で使用している変数Range / Sizeが0になる可能性があるということで、このときはRangeを計算した結果が0になってしまうため、処理を続けることができなくなります。よってRangeの取り得る最小値は、データのサイズより大きくなければなりません。Range / Sizeが0になった場合、サンプル・プログラムでは単純にエラー終了しています。Rangeの最小値はサンプル・プログ
Canonical Huffman Code
Daisuke Okanohara (VZV05226@nifty.com) 2003/12/9 公開 2003/12/11 誤植、chc.zipのmain.cppを修正 2003/12/13 multidecodeを実装 main.cppもそれに伴い変更 Canonical Huffman Code (以下CHC）は、Huffman法と同様に、最小冗長符号をHuffman木を作成、保持することなく、表引きで、符号化、復号化できる符号法です。 CHCは突然現れたアルゴリズムではなく、1950年代にHuffman法が登場して以来（Huffman法は、Fano符号で有名なFanoが出した最終試験免除の課題を学生だったHuffmanが試験直前に解決して発明された）、表向きにしろ、そうでないにしろさまざまな改良が、実装面、理論面でも行われてきました。その変種はいろいろありますが、その中で最も
white page / 全文検索や圧縮に関するlinks集
Copyright © 2004-2008, Yuta Mori, All Rights Reserved. yiv01157 at nifty dot com http://homepage3.nifty.com/wpage/
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
snippets/vc.cc at master · shnya/snippets · GitHub
Introduction to Arithmetic Coding Theory and Practice
データ圧縮の基礎
Compress-LZMA-Simple-0.2