fm-index 1.0.1

High-performance FM-index powered by Rust, enabling fast substring search and count/locate queries.

FM Index

High-performance FM-index implementation powered by Rust,
designed for fast substring search on large texts and collections

• PyPI: https://pypi.org/project/fm-index
• Document: https://math-hiyoko.github.io/fm-index
• Repository: https://github.com/math-hiyoko/fm-index

Features:

• Fast count / locate substring queries
• Supports single text and multiple documents

Installation

pip install fm-index

FMIndex (Single Document)

What is FMIndex?

FMIndex builds a compressed index over a single string,
allowing fast substring search without scanning the original data.

Construction Complexity

• Time / Space: O(|data| log σ)
• σ = alphabet size (e.g. 2⁸ for UCS-1, 2¹⁶ for UCS-2).

Example

from fm_index import FMIndex

genome = "ACGTACGTTGACCTGACTGACTGACTGACGATCGATCGATCGATCGATCG"
fm = FMIndex(data=genome)

Count Substring Occurrences

Counts how many times a pattern appears.
Time complexity is independent of data size.

fm.count(pattern="GACTGACT")
# 2

Locate Substring Positions

Returns all starting offsets where the pattern occurs.

fm.locate(pattern="GACTGACT")
# [18, 14]

MultiFMIndex (Multiple Documents)

MultiFMIndex extends FMIndex to support multiple documents
while keeping query time independent of corpus size

Construction Complexity

• Time / Space: O(|''.join(data)| log σ)
• σ = alphabet size (e.g. 2⁸ for UCS-1, 2¹⁶ for UCS-2).

from fm_index import MultiFMIndex

documents = [
    "政府はAI研究の支援を強化すると発表した。",
    "政府は新たなデータ活用方針を発表した。",
    "政府はサイバーセキュリティ対策を発表した。",
    "専門家はAI検索技術の進化に注目している。",
    "研究者は高速な検索アルゴリズムに注目している。",
    "オープンソース界隈では全文検索ライブラリに注目している。"
]

mfm = MultiFMIndex(data=documents)

Count Across All Documents

mfm.count_all(pattern="検索")
# 3

Count Per Document

mfm.count(pattern="検索")
# {3: 1, 4: 1, 5: 1}

Locate Per Document

mfm.locate(pattern="検索")
# {5: [13], 4: [7], 3: [6]}

Prefix / Suffix Search

mfm.startswith(prefix="政府は")
mfm.endswith(suffix="注目している。")

Development & Testing

Run Tests

pip install -e ".[test]"
cargo test --all --release
pytest

Formating

pip install -e ".[dev]"
cargo fmt --all
cargo clippy --all-targets --all-features
ruff format

Generating Docs

pdoc fm_index \
      --output-directory docs \
      --no-search \
      --no-show-source \
      --docformat markdown \
      --footer-text "© 2026 Koki Watanabe"

References

• P. Ferragina and G. Manzini,
  Opportunistic data structures with applications,
  Proceedings 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, CA, USA, 2000, pp. 390-398, https://doi.org/10.1109/SFCS.2000.892127.