FM Index

CI codecov PyPI - Version PyPI - License PyPI - PythonVersion PyPI - Implementation PyPI - Types PyPI Downloads PyPI - Format Rust GitHub Repo stars

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

Features:

  • Fast count / locate substring queries
  • Data-parallel optimizations across index construction and queries
  • Supports single text and multiple documents
  • Pickle serialization support for efficient index persistence
  • Optional disk-backed storage (on_disk=True)

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|)

Example

from fm_index import FMIndex

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

FMIndex also supports disk-backed storage for a large document.
Set on_disk=True to keep its internal data on disk instead of holding it all in memory.

fm = FMIndex(data=genome, on_disk=True)

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)| + len(data) log (len(data)))
from fm_index import MultiFMIndex

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

mfm = MultiFMIndex(data=documents)

MultiFMIndex also supports disk-backed storage for large documents.
Set on_disk=True to keep its internal data on disk instead of holding it all in memory.

mfm = MultiFMIndex(data=documents, on_disk=True)

Count Across All Documents

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

Count Per Document

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

# Count within a specific document
mfm.count(pattern="検索", doc_id=3)
# 1

Locate Per Document

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

# Locate within a specific document
mfm.locate(pattern="検索", doc_id=3)
# [6]

Iterative Locate (Streaming)

# Iterate across all documents
for doc_id, pos in mfm.iter_locate(pattern="検索"):
    print(doc_id, pos)
# 4 7
# 5 13
# 3 6

# Iterate within a specific document
for pos in mfm.iter_locate(pattern="検索", doc_id=3):
    print(pos)
# 6

Prefix / Suffix Search

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

Serialization (Pickle Support)

Both FMIndex and MultiFMIndex support Python's pickle protocol, allowing you to save and load pre-built indices efficiently.

The internal data structures are serialized directly in binary format, making deserialization much faster than rebuilding the index from scratch.

Save Index to File

import pickle
from fm_index import FMIndex, MultiFMIndex

# Build and save FMIndex
fm = FMIndex("large genome sequence..." * 10000)
with open("genome.fmindex", "wb") as f:
    pickle.dump(fm, f)

# Build and save MultiFMIndex
mfm = MultiFMIndex(["document1", "document2", ...])
with open("documents.mfmindex", "wb") as f:
    pickle.dump(mfm, f)

Load Index from File

# Load FMIndex
with open("genome.fmindex", "rb") as f:
    fm = pickle.load(f)

# Load MultiFMIndex
with open("documents.mfmindex", "rb") as f:
    mfm = pickle.load(f)

# Use immediately without reconstruction
result = fm.locate("ACGT")

This is particularly useful when:

  • Working with large datasets where index construction is expensive
  • Deploying pre-built indices in production environments
  • Sharing indices across different processes or machines

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 \
      --docformat markdown \
      --template-directory pdoc_templates

References

Project links

Data verified by PyPI on Aug 15, 2026
Data provided by the project maintainers, verified at the time the release was uploaded to PyPI.

Key dates

PyPI data
Data sourced directly from PyPI's database.
  • Released:
Latest release

1 maintainer

PyPI data
Data sourced directly from PyPI's database.
Avatar for math-hiyoko from gravatar.com math-hiyoko

Credits

Author: Koki Watanabe

GitHub Statistics

Data verified by PyPI on Aug 15, 2026
The GitHub source repository was provided by the project maintainers and verified by PyPI at the time of upload. Stars, forks, and open issues/PRs are derived from that repository and have not been independently verified.

License

MIT License

Requires

Python >=3.9

Provides Extra

dev test

Tags

fm-index full-text index compressed index substring search pattern matching succinct information retrieval

Classifiers

Report project as malware

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

fm_index-3.0.2.tar.gz (74.5 kB view details)

Uploaded Source

Built Distributions

If you're not sure about the file name format, learn more about wheel file names.

fm_index-3.0.2-cp39-abi3-win_amd64.whl (426.0 kB view details)

Uploaded CPython 3.9+Windows x86-64

fm_index-3.0.2-cp39-abi3-win32.whl (384.7 kB view details)

Uploaded CPython 3.9+Windows x86

fm_index-3.0.2-cp39-abi3-musllinux_1_2_x86_64.whl (830.3 kB view details)

Uploaded CPython 3.9+musllinux: musl 1.2+ x86-64

fm_index-3.0.2-cp39-abi3-musllinux_1_2_i686.whl (883.2 kB view details)

Uploaded CPython 3.9+musllinux: musl 1.2+ i686

fm_index-3.0.2-cp39-abi3-musllinux_1_2_armv7l.whl (898.8 kB view details)

Uploaded CPython 3.9+musllinux: musl 1.2+ ARMv7l

fm_index-3.0.2-cp39-abi3-musllinux_1_2_aarch64.whl (787.6 kB view details)

Uploaded CPython 3.9+musllinux: musl 1.2+ ARM64

fm_index-3.0.2-cp39-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl (602.3 kB view details)

Uploaded CPython 3.9+manylinux: glibc 2.17+ x86-64

fm_index-3.0.2-cp39-abi3-manylinux_2_17_s390x.manylinux2014_s390x.whl (644.8 kB view details)

Uploaded CPython 3.9+manylinux: glibc 2.17+ s390x

fm_index-3.0.2-cp39-abi3-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl (755.1 kB view details)

Uploaded CPython 3.9+manylinux: glibc 2.17+ ppc64le

fm_index-3.0.2-cp39-abi3-manylinux_2_17_i686.manylinux2014_i686.whl (680.1 kB view details)

Uploaded CPython 3.9+manylinux: glibc 2.17+ i686

fm_index-3.0.2-cp39-abi3-manylinux_2_17_armv7l.manylinux2014_armv7l.whl (624.1 kB view details)

Uploaded CPython 3.9+manylinux: glibc 2.17+ ARMv7l

fm_index-3.0.2-cp39-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (611.1 kB view details)

Uploaded CPython 3.9+manylinux: glibc 2.17+ ARM64

fm_index-3.0.2-cp39-abi3-macosx_11_0_arm64.whl (538.8 kB view details)

Uploaded CPython 3.9+macOS 11.0+ ARM64

fm_index-3.0.2-cp39-abi3-macosx_10_12_x86_64.whl (550.1 kB view details)

Uploaded CPython 3.9+macOS 10.12+ x86-64

File details

Details for the file fm_index-3.0.2.tar.gz.

File metadata

  • Download URL: fm_index-3.0.2.tar.gz
  • Upload date:
  • Size: 74.5 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? Yes
  • Uploaded via: twine/7.0.0 CPython/3.13.14

File hashes

Hashes for fm_index-3.0.2.tar.gz
Algorithm Hash digest
SHA256 805d0b553b95e2967b59d283e436e4e4043679354c90c564da99064c1a6fa1bf
MD5 0c62675500e54b6d9376142558d00b7f
BLAKE2b-256 cff036e36a0e0e65c96cdd7ef56f3595633cd80eee8280b789e8bd6fbf657294

See more details on using hashes here.

Provenance

The following attestation bundles were made for fm_index-3.0.2.tar.gz:

Publisher: CI.yml on math-hiyoko/fm-index

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file fm_index-3.0.2-cp39-abi3-win_amd64.whl.

File metadata

  • Download URL: fm_index-3.0.2-cp39-abi3-win_amd64.whl
  • Upload date:
  • Size: 426.0 kB
  • Tags: CPython 3.9+, Windows x86-64
  • Uploaded using Trusted Publishing? Yes
  • Uploaded via: twine/7.0.0 CPython/3.13.14

File hashes

Hashes for fm_index-3.0.2-cp39-abi3-win_amd64.whl
Algorithm Hash digest
SHA256 e061998d8d391b593b44b074896833fc06df79e4b4842d957ab492ed5cdd2cd8
MD5 afd99d904d921e7d180d36f242a07edb
BLAKE2b-256 5413d81f33597135a67b0f1b19eb6747e86777f13445b138f58333d58aefae8c

See more details on using hashes here.

Provenance

The following attestation bundles were made for fm_index-3.0.2-cp39-abi3-win_amd64.whl:

Publisher: CI.yml on math-hiyoko/fm-index

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file fm_index-3.0.2-cp39-abi3-win32.whl.

File metadata

  • Download URL: fm_index-3.0.2-cp39-abi3-win32.whl
  • Upload date:
  • Size: 384.7 kB
  • Tags: CPython 3.9+, Windows x86
  • Uploaded using Trusted Publishing? Yes
  • Uploaded via: twine/7.0.0 CPython/3.13.14

File hashes

Hashes for fm_index-3.0.2-cp39-abi3-win32.whl
Algorithm Hash digest
SHA256 622bedf8d0cfaa5b22c185b1ecd3249425a02a9a66c970df309e71a19cf55ca7
MD5 aa5aae687c2d5f9b5bf29325fe89a7e9
BLAKE2b-256 370fd0e4ad00cb79ae88ff9b58f04cb7962339cb6210c572aeb43c1977c97455

See more details on using hashes here.

Provenance

The following attestation bundles were made for fm_index-3.0.2-cp39-abi3-win32.whl:

Publisher: CI.yml on math-hiyoko/fm-index

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file fm_index-3.0.2-cp39-abi3-musllinux_1_2_x86_64.whl.

File metadata

File hashes

Hashes for fm_index-3.0.2-cp39-abi3-musllinux_1_2_x86_64.whl
Algorithm Hash digest
SHA256 0d3f2c46783d9a472fe8a60effb2cb0ac4710ecf2e1df508b9167f32c84fc0db
MD5 29ba6924c2b3a34a521e4e4822af7f93
BLAKE2b-256 f9f7770403ae0284cc4c01e2e25e127814344ddfb1db80ac105e06bd6113ada5

See more details on using hashes here.

Provenance

The following attestation bundles were made for fm_index-3.0.2-cp39-abi3-musllinux_1_2_x86_64.whl:

Publisher: CI.yml on math-hiyoko/fm-index

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file fm_index-3.0.2-cp39-abi3-musllinux_1_2_i686.whl.

File metadata

File hashes

Hashes for fm_index-3.0.2-cp39-abi3-musllinux_1_2_i686.whl
Algorithm Hash digest
SHA256 74f6b08ed775819da1972696ee4f0ea3925cd62f7d927cffcd682b2a0c7e41b2
MD5 d31e06034607b336430fab6c7d630dbe
BLAKE2b-256 9b83d1ba9178d8400f10fd7b8ade157251335c41364dfa9098117307f9b5b859

See more details on using hashes here.

Provenance

The following attestation bundles were made for fm_index-3.0.2-cp39-abi3-musllinux_1_2_i686.whl:

Publisher: CI.yml on math-hiyoko/fm-index

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file fm_index-3.0.2-cp39-abi3-musllinux_1_2_armv7l.whl.

File metadata

File hashes

Hashes for fm_index-3.0.2-cp39-abi3-musllinux_1_2_armv7l.whl
Algorithm Hash digest
SHA256 929fb87384fbc1c79aab642ef1cea5c5e82bd17811d9444225c8503a97c79f5e
MD5 9c886ae60ac2c5193a014bde592549ec
BLAKE2b-256 adafdb3460cac3c32b4b78db0148ec89fd60f1d00cb535b3620e5910c69d1f8c

See more details on using hashes here.

Provenance

The following attestation bundles were made for fm_index-3.0.2-cp39-abi3-musllinux_1_2_armv7l.whl:

Publisher: CI.yml on math-hiyoko/fm-index

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file fm_index-3.0.2-cp39-abi3-musllinux_1_2_aarch64.whl.

File metadata

File hashes

Hashes for fm_index-3.0.2-cp39-abi3-musllinux_1_2_aarch64.whl
Algorithm Hash digest
SHA256 2da4dacf7ebbfb53543bd64047e6cfea679c9036786a58b65a505a83c04810bc
MD5 aa4c40afaafbabec5fa415d24b02c958
BLAKE2b-256 96a24f0c68fe394e7798a9f9c5350df981b9d7c54899dcafb2250d57f40efad1

See more details on using hashes here.

Provenance

The following attestation bundles were made for fm_index-3.0.2-cp39-abi3-musllinux_1_2_aarch64.whl:

Publisher: CI.yml on math-hiyoko/fm-index

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file fm_index-3.0.2-cp39-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for fm_index-3.0.2-cp39-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 99b39d9d379a62ade529ce252eb7fd8f7731e21e54f4e58dd536413690c65f82
MD5 0675a22e4743ae53806dfbf1ea851eac
BLAKE2b-256 0865c5a6412c6651763491629caf771fb44384f4924529a3e626b3d3b4938617

See more details on using hashes here.

Provenance

The following attestation bundles were made for fm_index-3.0.2-cp39-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl:

Publisher: CI.yml on math-hiyoko/fm-index

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file fm_index-3.0.2-cp39-abi3-manylinux_2_17_s390x.manylinux2014_s390x.whl.

File metadata

File hashes

Hashes for fm_index-3.0.2-cp39-abi3-manylinux_2_17_s390x.manylinux2014_s390x.whl
Algorithm Hash digest
SHA256 6172ea8fa87fbbc0829ff2fcecb1aa16d2e7c95393397abbbc0b683e6a4a124c
MD5 7ca19d2deb746cd4eebc6fd707590c12
BLAKE2b-256 f35f04fea885b547a0b035b9f7e79917c567767599b724b818e253c8681669c9

See more details on using hashes here.

Provenance

The following attestation bundles were made for fm_index-3.0.2-cp39-abi3-manylinux_2_17_s390x.manylinux2014_s390x.whl:

Publisher: CI.yml on math-hiyoko/fm-index

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file fm_index-3.0.2-cp39-abi3-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl.

File metadata

File hashes

Hashes for fm_index-3.0.2-cp39-abi3-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl
Algorithm Hash digest
SHA256 6e9f1e34522ce386b5f964373fb578c06ae7d979533b6cf38f80dc3c0b8d9bad
MD5 50c53305d86708658f384725b33f861c
BLAKE2b-256 ab56da9c4d7fef2e22cccafd9131be162b09c1668c3262161d71147dcacfe096

See more details on using hashes here.

Provenance

The following attestation bundles were made for fm_index-3.0.2-cp39-abi3-manylinux_2_17_ppc64le.manylinux2014_ppc64le.whl:

Publisher: CI.yml on math-hiyoko/fm-index

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file fm_index-3.0.2-cp39-abi3-manylinux_2_17_i686.manylinux2014_i686.whl.

File metadata

File hashes

Hashes for fm_index-3.0.2-cp39-abi3-manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm Hash digest
SHA256 79b327e3868cccd193ed204a63997590a8c68754695dce85beda1e1adc181957
MD5 34b5c7c79c2f542f41089313345db659
BLAKE2b-256 c126a30ad3e12a2754c2fb839d2131ea100c005bc27dd617053f3af69d989c9b

See more details on using hashes here.

Provenance

The following attestation bundles were made for fm_index-3.0.2-cp39-abi3-manylinux_2_17_i686.manylinux2014_i686.whl:

Publisher: CI.yml on math-hiyoko/fm-index

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file fm_index-3.0.2-cp39-abi3-manylinux_2_17_armv7l.manylinux2014_armv7l.whl.

File metadata

File hashes

Hashes for fm_index-3.0.2-cp39-abi3-manylinux_2_17_armv7l.manylinux2014_armv7l.whl
Algorithm Hash digest
SHA256 397ef80b0a099c4ef240fdc2913ce3d14614c1d2f4be2cfcbe92c8ac2982c7f7
MD5 e2c752242f46b18296dd798b806fbef1
BLAKE2b-256 71b4a94ab6829cbeb96868fdc4d2faa1b27e485f38549ab79c6eb87748d65a39

See more details on using hashes here.

Provenance

The following attestation bundles were made for fm_index-3.0.2-cp39-abi3-manylinux_2_17_armv7l.manylinux2014_armv7l.whl:

Publisher: CI.yml on math-hiyoko/fm-index

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file fm_index-3.0.2-cp39-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl.

File metadata

File hashes

Hashes for fm_index-3.0.2-cp39-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm Hash digest
SHA256 2e9795f32ac39f5707fe1a3a59b561f0655c8272967551db0cda2ce34e9bcc65
MD5 d38d1fdea3da9519277e41ec2e6b193f
BLAKE2b-256 2e91c88feda0aadcf5cfef5899db13dfaf4149bb877a528e142d5357cc62060f

See more details on using hashes here.

Provenance

The following attestation bundles were made for fm_index-3.0.2-cp39-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl:

Publisher: CI.yml on math-hiyoko/fm-index

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file fm_index-3.0.2-cp39-abi3-macosx_11_0_arm64.whl.

File metadata

File hashes

Hashes for fm_index-3.0.2-cp39-abi3-macosx_11_0_arm64.whl
Algorithm Hash digest
SHA256 a5c897bb052e6edc1620d48e181dadd58cf702844c800cd70f2f23c339a4b1f1
MD5 e7d3ade7b6d5f497d37088cf8645c425
BLAKE2b-256 3313e38356ddbac9f86729c39bcdcb61cedb49f603fc15dc948f5d229c313978

See more details on using hashes here.

Provenance

The following attestation bundles were made for fm_index-3.0.2-cp39-abi3-macosx_11_0_arm64.whl:

Publisher: CI.yml on math-hiyoko/fm-index

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

File details

Details for the file fm_index-3.0.2-cp39-abi3-macosx_10_12_x86_64.whl.

File metadata

File hashes

Hashes for fm_index-3.0.2-cp39-abi3-macosx_10_12_x86_64.whl
Algorithm Hash digest
SHA256 cd93e84d1d482f7bfb66eebc90c7456b63c1c16b4ae8928289740d08240b77b0
MD5 97088bd91497843d884d1863242061f9
BLAKE2b-256 1c0865a8c43004853f20c2a68867e7f74f8e302cf49499bfe09541025ffa6cd4

See more details on using hashes here.

Provenance

The following attestation bundles were made for fm_index-3.0.2-cp39-abi3-macosx_10_12_x86_64.whl:

Publisher: CI.yml on math-hiyoko/fm-index

Attestations: Values shown here reflect the state when the release was signed and may no longer be current.

Supported by

AWS Cloud computing and Security Sponsor Datadog Monitoring Depot Continuous Integration Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page