fm-index 1.2.0

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
• Data-parallel optimizations across index construction and 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.

To improve throughput for high-frequency patterns,
FMIndex applies parallel execution to parts of the locate pipeline.

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

Iterative Locate (Streaming)

For large result sets, iter_locate provides a memory-efficient
iterator interface that yields positions lazily.

for pos in fm.iter_locate(pattern="GACTGACT"):
    print(pos)
# 18
# 14

• Same results as locate
• Does not allocate a result list
• Suitable for streaming and early termination

MultiFMIndex (Multiple Documents)

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

Query processing is internally parallelized where possible,
making multi-document search efficient in practice.

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]}

Iterative Locate (Streaming)

for doc_id, pos in mfm.iter_locate(pattern="検索"):
    print(doc_id, pos)
# 4 7
# 5 13
# 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.