FM Indexは、文字列を圧縮したまま検索できるデータ構造です。
転置インデックスとは異なり、分かち書きを前提としないため、巨大なテキストをそのまま扱う用途と相性があります。

FM IndexをPythonから使えるライブラリとしてfm-indexを実装し、PyPIで公開しています。¹
この記事では、そのfm-indexを使って、Wikipedia検索のようなことがどこまで可能かを実際に試してみます。

※ FM Index の理論や数式の詳細には踏み込まず、「実際に使うと何ができるか」を中心に紹介します。ライブラリの詳しい利用方法はPyPIページや、ドキュメントを参照してください。

FM Indexとは

FM Indexは、文字列を圧縮した形で保持しながら、部分文字列検索（「含まれるか」「何回出るか」「どこに出るか」）を効率よく行うためのデータ構造です。
転置インデックスのように「単語に分割して表を作る」方式とは異なり、テキストを文字列として扱うのが特徴です。

コード例：Wikipedia（ja）をサンプリングして検索してみる

実行環境

import sys, platform

print("Python:", sys.version.replace("\n"," "))
print("Platform:", platform.platform())
print("Implementation:", platform.python_implementation())

Python: 3.13.5 (v3.13.5:6cb20a219a8, Jun 11 2025, 12:23:45) [Clang 16.0.0 (clang-1600.0.26.6)]
Platform: macOS-15.7.3-arm64-arm-64bit-Mach-O
Implementation: CPython

1. セットアップ & データロード

今回はHugging Faceで公開されているWikipediaデータセット（日本語）²を使います。

依存ライブラリのインストール

!pip install datasets fm-index

...
Installing collected packages: fm-index, datasets
Successfully installed datasets-4.5.0 fm-index-1.2.0

データセットダウンロード

from datasets import load_dataset

wikipedia = load_dataset(
    path="wikimedia/wikipedia",
    name="20231101.ja",
    split="train",
)

print(wikipedia)
print(f"num articles: {len(wikipedia):,}")
print(f"total chars: {sum(len(text) for text in wikipedia['text']):,}")

Dataset({
    features: ['id', 'url', 'title', 'text'],
    num_rows: 1389467
})
num articles: 1,389,467
total chars: 2,658,082,408

このWikipediaデータセットには約140万件項目分のテキストが収録されており、その総文字数は26.6億文字にも上ることがわかります。

ちなみに収録されている各項目のデータは以下のようになっています。

wikipedia[0]

{'id': '5',
 'url': 'https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%B3%E3%83%91%E3%82%B5%E3%83%B3%E3%83%89',
 'title': 'アンパサンド',
 'text': 'アンパサンド（&, ）は、並立助詞「…と…」を意味する記号である。ラテン語で「…と…」を表す接続詞 "et" の合字を起源とする。現代のフォントでも、Trebuchet MS など一部のフォントでは、"et" の合字であることが容易にわかる字形を使用している。\n\n語源 \n\n英語で教育を行う学校でアルファベットを復唱する場合、その文字自体が単語となる文字（"A", "I", かつては "O" も）については、伝統的にラテン語の per se（それ自体）を用いて "A per se A" のように唱えられていた。また、アルファベットの最後に、27番目の文字のように "&" を加えることも広く行われていた。"&" はラテン語で et と読まれていたが、のちに英語で and と読まれるようになった。結果として、アルファベットの復唱の最後は "X, Y, Z, and per se and" という形になった。この最後のフレーズが繰り返されるうちに "ampersand" となまっていき、この言葉は1837年までには英語の一般的な語法となった。\n\nアンドレ＝マリ・アンペールがこの記号を自身の著作で使い、これが広く読まれたため、この記号が "Ampère\'s and" と呼ばれるようになったという誤った語源俗説がある。\n\n歴史 \n\nアンパサンドの起源は1世紀の古ローマ筆記体にまでさかのぼることができる。古ローマ筆記体では、E と T はしばしば合字として繋げて書かれていた（左図「アンパサンドの変遷」の字形1）。それに続く、流麗さを増した新ローマ筆記体では、さまざまな合字が極めて頻繁に使われるようになった。字形2と3は4世紀中頃における et の合字の例である。その後、9世紀のカロリング小文字体に至るラテン文字の変遷の過程で、合字の使用は一般には廃れていった。しかし、et の合字は使われ続け、次第に元の文字がわかりにくい字形に変化していった（字形4から6）。\n\n現代のイタリック体のアンパサンドは、ルネサンス期に発展した筆記体での et の合字にさかのぼる。1455年のヨーロッパにおける印刷技術の発明以降、印刷業者はイタリック体とローマ筆記体のアンパサンドの両方を多用するようになった。アンパサンドのルーツはローマ時代にさかのぼるため、ラテンアルファベットを使用する多くの言語でアンパサンドが使用されるようになった。\n\nアンパサンドはしばしばラテンアルファベットの最後の文字とされることがあった。たとえば1011年のByrhtferthの文字表がその例である。同様に、"&" は英語アルファベットの27番目の文字とされ、アメリカ合衆国やその他の地域でも、子供達はアンパサンドはアルファベットの最後の文字だと教えられていた。1863年の M. B. Moore の著書 The Dixie Primer, for the Little Folks にその一例を見ることができる。ジョージ・エリオットは、1859年に発表した小説「」の中で、Jacob Storey に次のセリフを語らせている。"He thought it [Z] had only been put to finish off th\' alphabet like; though ampusand would ha\' done as well, for what he could see." よく知られた童謡の Apple Pie ABC は  "X, Y, Z, and ampersand, All wished for a piece in hand" という歌詞で締めくくられる。\n\nアンパサンドは、ティロ式記号の et ("⁊", Unicode U+204A) とは別のものである。ティロ式記号の et は、アンパサンドと意味は同じだが数字の「7」に似た形の記号である。両者はともに古代から使用され、中世を通してラテン語の et を表すために使用された。しかし、アンパサンドとティロ式記号の et はそれぞれ独立に発明されたものである。ラテン文字から発展した古アイルランド語の文字では、アイルランド語の agus（「…と…」）を表すためにティロ式記号の et が使用されていた。今日はゲール文字の一部として主に装飾的な目的で使用されている。この文字はアイルランドにおけるキリスト教時代初期に修道院の影響によって書き文字に加わった可能性がある。\n\n手書き\n日常的な手書きの場合、欧米では小文字の （エプシロン）を大きくしたもの（あるいは数字の "3" の鏡文字）に縦線を加えた形の単純化されたアンパサンドがしばしば使われる。また、エプシロンの上下に縦線または点を付けたものもしばしば使われる。\n\nくだけた用法として、プラス記号（"+", この記号もまた et の合字である）がアンパサンドの代わりに使われることがある。また、プラス記号に輪を重ねたような、無声歯茎側面摩擦音を示す発音記号「」のようなものが使われることもある。\n\n同様の記号 \nティロの速記には「et」を表すための「」(U+204A Tironian sign et)がある。この文字はドイツのフラクトゥールで使われたほか、ゲール文字でも使用される。\n\nギリシア文字では「……と」を意味するを表すための合字として「」(U+03D7 Greek kai symbol)が使われることがある。\n\nプログラミング言語 \nプログラミング言語では、C など多数の言語で AND 演算子として用いられる。以下は C の例。\n X = A && B のように2個重ねたものは論理 AND を表す。この場合 A, B がともに真ならば X も真、それ以外は偽である。\n 0x12345678 & 0x0f0f0f0f のように1個であればビット AND を表す。この場合の結果は 0x02040608 である。\nPHPでは、変数宣言記号（$）の直前に記述することで、参照渡しを行うことができる。\n\nBASIC 系列の言語では文字列の連結演算子として使用される。"foo" & "bar" は "foobar" を返す。また、主にマイクロソフト系では整数の十六進表記に &h を用い、&h0F （十進で15）のように表現する。\n\nSGML、XML、HTMLでは、アンパサンドを使ってSGML実体を参照する。\n\n符号位置\n\n脚注\n\n外部リンク \n\n約物\nラテン語の語句\n論理記号'
}

2. データサンプリング

今回検証したローカルPCではこの文字量をそのまま扱いきれないため³、検証ではこの中からランダムに選び出した 20 万項目を使用します。

import random

random.seed(42)
sample_size = 200_000

sample_indices = random.sample(range(len(wikipedia)), sample_size)
sample_wikipedia = wikipedia.select(sample_indices)

print(f"sample num articles:　{len(sample_wikipedia):,}")
print(f"sample total chars:　{sum(len(t) for t in sample_wikipedia['text']):,}")

sample num articles:　200,000
sample total chars:　380,080,616

20万項目に絞り込んだことで、総文字数は3.8億近くになりました。

3. FM Indexの構築

いよいよライブラリを使ったFM Indexの構築します。
今回は、複数文字列に対応したMultiFMIndexクラスを用います。
例えば一冊の書籍のような単一の長文に対してはFMIndexクラスを用います。

import time
from fm_index import MultiFMIndex

start = time.perf_counter()
fm = MultiFMIndex(sample_wikipedia["text"])
elapsed = time.perf_counter() - start
print(f"elapsed: {elapsed:.3f} sec")

elapsed: 76.211 sec

今回検証した環境では76秒で構築が完了しました。理論上は構築時間とメモリ使用量は共に総文字数に比例します。⁴
構築元の文字列はおよそ1.4GBの容量の文字列で、構築されたfmインスタンスはおよそ2.2GBのメモリを占有しています。
元の文字列とメモリ占有量がさして変わらないのがFM Indexの大きな特徴の一つです。

4. FM Indexを用いた全文検索(登場回数検索)

FM Indexを用いた登場回数検索を行います。
各項目ごとのキーワードの登場回数はcountメソッドを使って求めることができます。
以下では、"Python"という文字列の登場回数が多い項目上位10件を取り出しています。

keyword = "Python"

start = time.perf_counter()
count = fm.count(keyword)  # {doc_index: occurrences, ...}
elapsed = time.perf_counter() - start
print(f"elapsed: {elapsed:.3f} sec")

# キーワードの総登場回数と登場項目数
print(f"total count: {sum(count.values())}")
print(f"total title: {len(count)}")
print()

# 出現回数の多い順に doc_index をソート
indices = sorted(count, key=count.get, reverse=True)

# 上位10件を表示
for i in indices[:10]:
    print(f"count: {count[i]}, title: {sample_wikipedia[i]['title']}")

elapsed: 0.003 sec
total count: 352
total title: 169

count: 20, title: Project Jupyter
count: 18, title: IPython
count: 12, title: ニシキヘビ科
count: 11, title: 基本情報技術者試験
count: 9, title: Pip
count: 8, title: アフリカニシキヘビ
count: 7, title: タプル
count: 7, title: マイケル・ペイリン
count: 7, title: MayaVi
count: 6, title: 文字列補間

ここで、countメソッドの実行は0.003秒で完了しています。
FM Indexを使うことで、20万項目・3.8億文字に対する検索を、これだけ短時間で実行できています。
理論上、検索時間は構築元の文字列の長さには依存せず、検索キーワードの長さと総登場回数に依存します。⁵⁶

5. FM Indexを用いた全文検索(登場位置検索)

登場回数検索で最も多くの回数ヒットした"Project Jupyter"について、この項目内でのキーワードの登場位置を調べます。
locateメソッドを用いることで、項目ごとのキーワードの登場位置を文字列中のオフセットの形で求めることができます。

start = time.perf_counter()
locate = fm.locate(keyword)
elapsed = time.perf_counter() - start
print(f"elapsed: {elapsed:.3f} sec")

top_index = indices[0]
top_text = sample_wikipedia[top_index]["text"]
top_offsets = locate[top_index]

window = 15

print("TOP:", sample_wikipedia[top_index]["title"])
print("hits:", len(top_offsets))
print()

for offset in top_offsets[:20]:  # 多すぎるので最大20個だけ表示
    start = max(0, offset - window)
    end = min(len(top_text), offset + window)
    snippet = top_text[start:end].replace("\n", " ")
    print("...", snippet, "...")

elapsed: 0.003 sec
TOP: Project Jupyter
hits: 20

...  GNU Octave   IPython   RStudi ...
... REPLを提供する。    IPython   ØMQ    ...
... bookに名前が変更された（IPython 4.0 – Ju ...
... er Notebook （旧IPython Notebook ...
... 2014年10月）の時点で、 Python 、 R 、 Ju ...
... ング言語であるJulia 、 Python 、 Rへの言及で ...
... t 、 Markdown 、 Python ）に変換できる。 ...
... 、 フェルナンドペレスは、 IPythonからProject ...
... nandoPérezによってIPythonから分離された、数 ...
... IPythonカーネルを介したPythonなど、数十の言語の ...
... ース （2011年12月）にIPythonに追加され、201 ...
...  Jupyterの前身であるIPythonに関する研究で、F ...
... やその他の言語に依存しない IPythonの部分は、Jupy ...
... プロジェクトを発表した。  IPythonは、Jupyter ...
... れにより、インストラクターは、Pythonまたはその他のサポ ...
... ter NotebookにはIPythonカーネルが付属して ...
...  Ruby 、そしてもちろんIPythonカーネルを介したP ...
... 発見論文の数値を再現するためのPythonコードを含むJup ...
... ythonは、JupyterのPythonシェルおよびカーネ ...
... 賞した 。   2013年、IPythonチームは、 Alf ...

"Python"というキーワードがどのような文脈で出てきているのかを詳しく可視化できています。

転置インデックスによる検索システムとの違い

全文検索では、転置インデックスも一般によく用いられます。
FM Indexによる全文検索と転置インデックスによる全文検索では、できることや得意なことに違いがあります。

形態素解析が前提になる転置インデックス

転置インデックスを使った全文検索では、通常「単語」をキーにするため、事前に形態素解析やトークン化が必要になります。
英語であれば比較的単純ですが、日本語ではこれが意外と難しく、検索したい語が「1単語として切れない」ケースも多くあります。
例えば、IPythonやCPythonなどの言葉はこれらをそれぞれ1つの単語として扱っていた場合、"Python"で検索してもヒットしないことになります。

そのため、「この文字列がそのまま含まれているか」を調べる用途では、FM Indexは非常に素直で、前処理に悩まされにくいアプローチです。

意味を捉えることができないFM Index

一方で、FM Index は意味検索や単語検索が得意というわけではありません。
例えば、"京都"で検索したい場合でも、FM Indexによる全文検索は"東京都"を含む文字列を大量に結果として挙げることになります。
これはアルゴリズムとして正しく、FM Indexは意味ではなく文字列を見ているだけです。
意味に沿った内容を検索したいという要素では転置インデックスによる全文検索が適しています。

https://pypi.org/project/fm-index ↩
本記事で使用しているデータセットは Wikimedia Dumps のデータです。
https://dumps.wikimedia.org/legal.html ↩
構築時に一時的に多くのメモリを占有するためです。メモリが十分に確保された環境であればサンプリングを行わずに構築が可能です。 ↩
実際には環境で利用できるRAM次第にはなります。大規模な文字列になるほどキャッシュメモリに乗らなくなってくるので構築が遅くなる傾向になります。 ↩
検索キーワードの長さのみに依存した時間で全項目でのキーワードの総登場回数のみを求めるメソッドcount_allもあります。 ↩
総登場回数に依存する処理を行う部分では並列処理を適用しているため、かなりの回数(100万回単位)登場するキーワードでもそれなりの速さで検索ができます。 ↩