データが増えると区間集計が遅い?「wavelet-matrix」なら件数に左右されない
- 公開
- 正式公開 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-rs | API クライアント | NotebookLM Enterprise API を Rust の CLI と Python SDK から使う非公式クライアント | CLI(Rust)/ Python SDK | 無料(OSS, MIT) |
| harumi | PDF 編集ライブラリ | 既存の PDF に CJK テキストをフォントの自動サブセット化つきで追記する Pure Rust のライブラリ | Rust クレート(WASM 対応) | 無料(OSS) |