データが増えると区間集計が遅い?「wavelet-matrix」なら件数に左右されない

wavelet-matrix
整数の列に索引を作り、出現回数や範囲の集計に答える Rust 製の Python ライブラリ
GitHub公式サイト
公開
正式公開 2025-12-06(Show HN は 2025-12-17)
作り手
math-hiyoko(個人)
対応
Python ライブラリ(PyPI)
言語
Python・Rust
価格
無料(MIT ライセンス)
評価
GitHub のスター 39(2026-10-13)

どんなアプリか

High-performance Wavelet Matrix implementation powered by Rust, supporting fast rank / select / range queries over indexed sequences

math-hiyoko さん、GitHub の README

wavelet-matrix は、ウェーブレット行列というデータ構造を Rust で実装し、Python から使えるようにしたライブラリです。pip でインストールでき、整数の列を渡すと索引が作られます。README によると、問い合わせにかかる時間はデータの大きさではなく、値のビット幅で決まります。

ある値が何回出てくるか(rank)、k 番目の出現がどこにあるか(select)、区間で k 番目に小さい値(quantile)を調べられます。区間の合計、指定した範囲に入る値の個数、よく出てくる値の上位 k 件、値の大きい順・小さい順の k 件といった範囲の問い合わせにも対応しています。

書き換えない列には WaveletMatrix を、挿入・削除・更新をしたい列には DynamicWaveletMatrix を使います。後者について README は、処理の負担が大きくなること、値が max_bit で指定したビット数に収まる必要があることを、引き換えになる点として挙げています。

料金とデータの置き場所

MIT ライセンスで公開されています。書き換えない大きな列では、on_disk=True を指定すると、内部のデータをすべてメモリに置かずにディスクに置けます。

同じ分野のアプリ

名前型仕掛け対応料金
wavelet-matrixデータ構造ライブラリ整数の列に索引を作り、rank / select / 範囲の集計に答えるPython ライブラリ(Rust 実装)無料(OSS, MIT)
filesqlデータ問い合わせライブラリCSV や JSON などのファイルをメモリ上の SQLite に読み込み、SQL で問い合わせるGo ライブラリ(SQL ドライバ)無料(OSS, MIT)
nblm-rsAPI クライアントNotebookLM Enterprise API を Rust の CLI と Python SDK から使う非公式クライアントCLI(Rust)/ Python SDK無料(OSS, MIT)
harumiPDF 編集ライブラリ既存の PDF に CJK テキストをフォントの自動サブセット化つきで追記する Pure Rust のライブラリRust クレート(WASM 対応)無料(OSS)