grepは1文字ずつ比較していません。KMP法を実装して、どこを飛ばしているのかを確かめます。
これは【深掘り】の記事です。本線の順路ではありません。 このシリーズは言葉を覚える回にしません。 全部、自分の手で書いて、走らせて、出た数字だけを載せます。 飛ばしても本線は進めます。 計算量そのものが怪しい人は、先に本線の 1万件で100倍になる — 計算量とO記法を測る を読んでください。
この記事のコマンドは、VMの中(Ubuntu Server)で打ちます。 Windows の PowerShell ではありません。VM の立て方は VMを29台溜めた話 — Ubuntu Serverの立て方 にあります。
indexOf があるのに、なぜ文字列探索のアルゴリズムを勉強するのか。
これは私がずっと納得できていなかったところです。
text.indexOf(pat) と1行書けば終わる。KMP を写経しても、indexOf より速くはなりません。 実際、この記事の最後でも indexOf は私が書いた4つの実装すべてに勝ちます。
それでも書く理由が、実際に手を動かして初めて分かりました。
きっかけは、こういうコードを書いたときです。
// アップロードされたテキストの中に、禁止語が入っていないか調べる
for (const word of bannedWords) { // 2,000語
if (uploadedText.includes(word)) return reject(word);
}
動きます。 テストも通ります。ところが本番で、たまに 1リクエストが数秒かかる。
理由は2つありました。
- 2,000語ぶん、テキストを2,000回なめている(1回の走査で全部探す方法がある)
- たまに来る変なファイル(同じ文字が延々続くファイル)で、素朴な比較が爆発していた
このとき私が知りたかったのは「indexOf の使い方」ではありません。 「文字列を探すとき、何がコストなのか」 です。
そして、それを知るには一度自分で書くしかありませんでした。
この記事の主張は1つです。
文字列は他のデータと違って、「前に調べた結果を使い回せる」。 数値の配列を探すときには使えない、文字列だけの性質がある。 それを知らないと、「なぜ速いのか」も「なぜ遅くなるのか」も説明できない。
対象レベル: 中級〜上級 / 区分: 発展
この記事でわかること
- 素朴な探索は最悪
O(n×m)。 ただし普通の英文では滅多に最悪にならない(実測で 100倍 対 1.05倍) - KMP の要点はたった1つ。「途中まで一致した情報を、次のずらしに使い回す」。だからテキストを一度も後戻りしない
- Boyer-Moore は後ろから比べる。 だからパターンが長いほど速くなる(実測でパターン長を倍にすると比較回数がぴったり半分)
- Rabin-Karp は文字列を数値にして比べる。 ハッシュが一致しても本物とは限らないので、必ず本体を比べる
indexOfが全部に勝つ。 それでも仕組みを知る価値がどこにあるのかgrep -Fが速いとは限らない。 GNU grep はリテラルなら勝手に速い経路を選ぶ。差が出るのは記号が混ざったとき- 量指定子の入れ子は、一致しているうちは差が出ない。 だからテストをすり抜ける
- ハフマン符号は「よく出る文字に短いビット列」。 英文4MBで実測 54.6%、
gzipは 37.3%。その差が何なのか - 接尾辞配列は「1回だけ探すなら不要、何度も探すなら作る」。 実測の交差点は 8,916回
この記事でやること
- 実験用フォルダ
~/cslab/strを作り、この記事の作業を全部そこに閉じ込める - 素朴な探索を書き、比較回数をカウンタで数えて最悪ケースを自分で作る
- KMP を書き、部分一致テーブルの中身を表示しながら「なぜ後戻りしないか」を確かめる
- Boyer-Moore(簡易版)を書き、1歩ごとに何文字飛んだかを出力する
- Rabin-Karp を書き、ローリングハッシュと衝突を実際に起こして見る
- 4つ +
indexOfを同じデータで時間測定し、表にする - ハフマン符号の符号表を英文から作り、
gzipの実測圧縮率と並べる - 接尾辞配列を作って二分探索で引き、交差点を実測して締める
先に知る言葉
この記事で初めて出てくる言葉です。 基本的な言葉は用語集にもまとめてあります。
| 言葉 | 意味 |
|---|---|
| テキスト / パターン | 探される側の長い文字列がテキスト(長さ n)、探す側の短い文字列がパターン(長さ m) |
| 素朴な探索 | 1文字ずつずらして、その都度頭から比べる。最悪 O(n×m) |
| 部分一致テーブル(失敗関数) | パターンの各位置について「先頭とも末尾とも一致する最長の長さ」を並べた表。KMP の心臓 |
| 接頭辞 / 接尾辞 | 文字列の頭からの一部が接頭辞、末尾までの一部が接尾辞。banana の接尾辞は banana anana nana ana na a |
| 不一致文字規則 | Boyer-Moore の飛ばし方。合わなかったテキスト側の文字が、パターンのどこにあるかで飛ぶ量を決める |
| ローリングハッシュ | 1文字ずらすとき、前の値から先頭を引いて末尾を足すだけでハッシュを O(1) で更新する技 |
| 衝突 | 別の文字列なのにハッシュが同じになること。必ず起きる前提で設計する |
| ハフマン符号 | よく出る文字に短いビット列を割り当てる可変長の符号。gzip の中で使われている |
| 接尾辞配列 | すべての接尾辞を辞書順に並べた開始位置の配列。作るのは重いが、作ったあとは二分探索で引ける |
| 前処理 | 探す前に1回だけやる準備(テーブル作り・接尾辞配列作り)。引く回数で割って考える |
① 準備 — 実験する土台を作る
実験用のフォルダを作ります。最後に丸ごと消します。
VM に SSH で入って、ホームディレクトリで打ちます。
私の VM ではこうなりました。
v22.14.0
nodeが無いと出る場合。node: command not foundなら Node.js が入っていません。この記事の実験は Node.js だけで完結します。 入っていない状態で先に進むと、全部のコマンドが失敗します。
この記事のファイルは全部 ~/cslab/str の中に作ります。 どこで打っているか分からなくなったら pwd で確認してください。
/home/user/cslab/str
② 素朴な探索を書いて、比較回数を数える
まず「1文字ずつずらして、全部比べる」を書きます。
大事なのは実装ではなく、比較回数をカウンタで数えることです。 時間だけ測っても「なぜ遅いのか」が見えません。何回比べたかが本体です。
nano naive.mjs で作ります。
// naive.mjs — 素朴な文字列探索。1文字ずつずらして、頭から比べる
export function naiveSearch(text, pat) {
let cmp = 0; // 文字を比べた回数を数える
const n = text.length, m = pat.length;
for (let i = 0; i + m <= n; i++) { // ずらす位置
let j = 0;
while (j < m) { // その位置で頭から比べる
cmp++;
if (text[i + j] !== pat[j]) break;
j++;
}
if (j === m) return { index: i, cmp };
}
return { index: -1, cmp };
}
読むところは1つだけです。 内側の while が途中で break したあと、外側の i は 1 しか進みません。
ここが素朴な探索の弱点です。 「99文字合っていて、100文字目で違った」という情報を、次のずらしで完全に捨てている。
最悪ケースを自分で作る
nano step1.mjs。
import { naiveSearch } from './naive.mjs';
console.log('--- 普通の例 ---');
console.log(naiveSearch('the quick brown fox jumps', 'brown'));
console.log('--- 最悪ケース: a...ab の中から aaab ---');
for (const n of [1000, 2000, 4000, 8000]) {
const text = 'a'.repeat(n - 1) + 'b';
const r = naiveSearch(text, 'aaab');
console.log(`n=${String(n).padStart(5)} m=4 index=${r.index} 比較=${String(r.cmp).padStart(6)} n*m=${n * 4}`);
}
--- 普通の例 ---
{ index: 10, cmp: 15 }
--- 最悪ケース: a...ab の中から aaab ---
n= 1000 m=4 index=996 比較= 3988 n*m=4000
n= 2000 m=4 index=1996 比較= 7988 n*m=8000
n= 4000 m=4 index=3996 比較= 15988 n*m=16000
n= 8000 m=4 index=7996 比較= 31988 n*m=32000
比較回数が n × m にぴったり張り付いています。
なぜこうなるか。テキストは aaaa...aaab、パターンは aaab。 どの位置でも aaa までは合う。そして4文字目で必ず外れる。つまり毎回4回比べて1しか進まない。
これが O(n×m) の正体です。 「最悪 n×m」は理論上の上限ではなく、入力を作れば本当に出る数字でした。
私が最初に誤解していたこと。 「最悪ケースは理論の話で、実際には起きない」と思っていました。起きます。 同じ文字が続くファイル(ログのパディング、埋め草、壊れたアップロード)は普通に来ます。
普通の英文では、どのくらいか
最悪ケースだけ見せるのはフェアではありません。 英文でも数えます。
実験用のテキストを作ります。nano gen.mjs。
// gen.mjs — 実験用の英文っぽいテキストを作る(毎回同じものが出る)
import { writeFileSync } from 'node:fs';
const WORDS = ('the of and a to in is you that it he was for on are as with his they i at be this have from one had by hot but some what there we can out other were all your when up use word how said an each she which do their time if will way about many then them would write like so these her long make thing see him two has look more day could go come did my sound no most number who over know water than call first people may down side been now find any new work part take get place made live where after back little only round man year came show every good me give our under name very through just form much great think say help low line before turn cause same mean differ move right boy old too does tell sentence set three want air well also play small end put home read hand port large spell add even land here must big high such follow act why ask men change went light kind off need house picture try us again animal point mother world near build self earth father head stand own page should country found answer school grow study still learn plant cover food sun four thought let keep eye never last door between city tree cross since hard start might story saw far sea draw left late run while press close night real life few north open seem together next white children begin got walk example ease paper often always music those both mark book letter until mile river car feet care second group carry took rain eat room friend began idea fish mountain stop once base hear horse cut sure watch color face wood main enough plain girl usual young ready above ever red list though feel talk bird soon body dog family direct pose leave song measure state product black short numeral class wind question happen complete ship area half rock order fire south problem piece told knew pass farm top whole king size heard best hour better true during hundred five remember step early hold west ground interest reach fast verb sing listen six table travel less morning ten simple several vowel toward war lay against pattern slow center love person money serve appear road map science rule govern pull cold notice voice fall power town fine certain fly unit lead cry dark machine note wait plan figure star box noun field rest correct able pound done beauty drive stood contain front teach week final gave green oh quick develop sleep warm free minute strong special mind behind clear tail produce fact street inch lot nothing course stay wheel full force blue object decide surface deep moon island foot yet busy test record boat common gold possible plane age dry wonder laugh thousand ago ran check game shape yes hot miss brought heat snow bed bring sit perhaps fill east weight language among').split(' ');
// 決まった乱数(同じファイルが再現できる)
let s = 20261003;
const rnd = () => (s = (s * 1103515245 + 12345) % 2147483648) / 2147483648;
const target = Number(process.argv[2] || 4_000_000); // だいたい何バイト作るか
const out = [];
let len = 0;
while (len < target) {
const n = 8 + Math.floor(rnd() * 12); // 1文の語数
const sent = [];
for (let i = 0; i < n; i++) sent.push(WORDS[Math.floor(rnd() * WORDS.length)]);
sent[0] = sent[0][0].toUpperCase() + sent[0].slice(1);
const line = sent.join(' ') + '.';
out.push(line);
len += line.length + 1;
}
writeFileSync('corpus.txt', out.join('\n') + '\n');
console.log('corpus.txt を作りました:', out.join('\n').length + 1, 'バイト /', out.length, '行');
なぜ本物の本ではなく生成なのか。 同じファイルが誰の環境でも再現できるようにするためです。 乱数の種を固定しているので、あなたの VM でも同じ 4,000,021 バイトが出ます。
corpus.txt を作りました: 4000021 バイト / 54313 行
-rw-rw-r-- 1 user user 4000021 Oct 3 10:12 corpus.txt
Cut build close small less might top read test great even done left other gold bird.
Come dry shape water too she cross rest.
Possible try answer so draw when to all made sound star.
Stop four
これで数えます。nano step2.mjs。
import { readFileSync } from 'node:fs';
import { naiveSearch } from './naive.mjs';
const text = readFileSync('corpus.txt', 'utf8');
const needle = text.slice(text.length - 60, text.length - 40); // 終わりのほうの実在する20文字
console.log('探す語:', JSON.stringify(needle));
console.log('--- 英文の中を探す(普通のケース) ---');
for (const pat of [needle, 'zebra quantum banana', 'mountain']) {
const r = naiveSearch(text, pat);
console.log(`"${pat}" index=${String(r.index).padStart(8)} 比較=${String(r.cmp).padStart(9)} 1文字あたり${(r.cmp / text.length).toFixed(3)}回`);
}
console.log('--- 最悪ケース(m=100) ---');
const bad = 'a'.repeat(200000);
const badPat = 'a'.repeat(99) + 'b';
const r = naiveSearch(bad, badPat);
console.log(`n=200000 m=100 index=${r.index} 比較=${r.cmp} 1文字あたり${(r.cmp / bad.length).toFixed(1)}回`);
探す語: "plan miss some food "
--- 英文の中を探す(普通のケース) ---
"plan miss some food " index= 65233 比較= 66927 1文字あたり0.017回
"zebra quantum banana" index= -1 比較= 4002422 1文字あたり1.001回
"mountain" index= 526 比較= 551 1文字あたり0.000回
--- 最悪ケース(m=100) ---
n=200000 m=100 index=-1 比較=19990100 1文字あたり100.0回
ここが一番大事な数字です。
| 入力 | テキスト1文字あたりの比較回数 |
|---|---|
| 英文・最後まで見つからない語 | 1.001 回 |
| 英文・途中で見つかる語 | 0.017 回 |
最悪ケース(m=100) | 100.0 回 |
英文では、m が 20 でも「1文字あたり1回」で済んでいます。
理由は簡単で、英文はほとんど最初の1文字で外れるからです。z から始まる位置なんてめったにありません。
つまり素朴な探索は、普通の文章に対しては実質
O(n)で動く。O(n×m)は「入力が意地悪だったとき」の顔です。
そしてその意地悪な入力は、外から来ます。 ここが「知らなくていい」で済まない理由でした。
📸 スクリーンショット 01:
node step2.mjsの出力全体。英文の 1.001 回と、最悪ケースの 100.0 回が同じ画面に並んでいるところを撮ります。この記事で一番大事な対比です。
③ KMP — 「途中まで一致した情報」を捨てない
KMP の説明で必ず出てくる「部分一致テーブル」は、覚える対象ではありません。 素朴な探索が捨てていた情報を、そのまま形にしただけです。
まず何を捨てていたのか
テキストが aaaaaaab、パターンが aaab のとき、位置0で比べるとこうなります。
text: a a a a a a a b
pat: a a a b
↑ ↑ ↑ ↑
○ ○ ○ × ← 3文字合った。4文字目で外れた
素朴な探索は、ここで i を 1 進めてまた頭から比べます。
でも、私たちはもう知っています。 テキストの1〜3文字目が aaa であることを。さっき読んだからです。
KMP の要点はこれだけです。 「いま何文字合っていたか」を持ったまま、テキストを進み続ける。テキスト側の添字
iは一度も戻さない。
そのために必要なのが「3文字合っていたのに外れた。じゃあ次は何文字合っている状態から始めればいいか」という表です。それが部分一致テーブルです。
書く
nano kmp.mjs。
// kmp.mjs — KMP法。「途中まで一致した情報」を次のずらしに使い回す
// 部分一致テーブル(失敗関数)
// fail[i] = pat[0..i] の中で「先頭とも末尾とも一致する最長の長さ」(自分自身は除く)
export function buildFail(pat) {
const fail = new Array(pat.length).fill(0);
let k = 0;
for (let i = 1; i < pat.length; i++) {
while (k > 0 && pat[i] !== pat[k]) k = fail[k - 1];
if (pat[i] === pat[k]) k++;
fail[i] = k;
}
return fail;
}
export function kmpSearch(text, pat) {
let cmp = 0;
const fail = buildFail(pat);
let k = 0; // いま何文字一致しているか
for (let i = 0; i < text.length; i++) { // ⚠️ i は一度も戻らない
while (k > 0 && (cmp++, text[i] !== pat[k])) k = fail[k - 1];
if ((cmp++, text[i] === pat[k])) k++;
if (k === pat.length) return { index: i - pat.length + 1, cmp };
}
return { index: -1, cmp };
}
(cmp++, text[i] !== pat[k])の書き方について。 カンマ演算子です。「まず数えて、それから比べた結果を返す」。数を数えるためだけの細工なので、 実務のコードでは書かないでください。ここでは比較回数を正確に数えたいので使っています。
テーブルの中身を見る
これを見ずに KMP を理解するのは無理でした。 nano step3.mjs。
import { buildFail, kmpSearch } from './kmp.mjs';
import { naiveSearch } from './naive.mjs';
function showFail(pat) {
const fail = buildFail(pat);
console.log('pat :', [...pat].map(c => c.padStart(3)).join(''));
console.log('添字:', [...pat].map((_, i) => String(i).padStart(3)).join(''));
console.log('fail:', fail.map(v => String(v).padStart(3)).join(''));
console.log('');
}
console.log('--- 部分一致テーブル ---');
showFail('ababaca');
showFail('aaab');
showFail('abcdef');
console.log('--- 最悪ケースで素朴とKMPを比べる ---');
const bad = 'a'.repeat(200000);
const badPat = 'a'.repeat(99) + 'b';
const a = naiveSearch(bad, badPat);
const b = kmpSearch(bad, badPat);
console.log('素朴 比較=', a.cmp, ' index=', a.index);
console.log('KMP 比較=', b.cmp, ' index=', b.index);
console.log('比:', (a.cmp / b.cmp).toFixed(1), '倍');
console.log('--- 答えが同じか、ランダムで1万回突き合わせる ---');
let ng = 0;
for (let t = 0; t < 10000; t++) {
const s = Array.from({ length: 30 }, () => 'abc'[Math.floor(Math.random() * 3)]).join('');
const p = Array.from({ length: 1 + Math.floor(Math.random() * 4) }, () => 'abc'[Math.floor(Math.random() * 3)]).join('');
if (kmpSearch(s, p).index !== s.indexOf(p)) { ng++; console.log('NG', s, p); }
}
console.log(ng === 0 ? 'すべて indexOf と一致' : `${ng} 件ずれた`);
--- 部分一致テーブル ---
pat : a b a b a c a
添字: 0 1 2 3 4 5 6
fail: 0 0 1 2 3 0 1
pat : a a a b
添字: 0 1 2 3
fail: 0 1 2 0
pat : a b c d e f
添字: 0 1 2 3 4 5
fail: 0 0 0 0 0 0
--- 最悪ケースで素朴とKMPを比べる ---
素朴 比較= 19990100 index= -1
KMP 比較= 599900 index= -1
比: 33.3 倍
--- 答えが同じか、ランダムで1万回突き合わせる ---
すべて indexOf と一致
テーブルを読む
ababaca を見ます。
| 添字 | ここまでのパターン | fail | 意味 |
|---|---|---|---|
| 0 | a | 0 | 自分しかないので 0 |
| 1 | ab | 0 | 頭 a と尻 b は違う |
| 2 | aba | 1 | 頭 a と尻 a が一致(長さ1) |
| 3 | abab | 2 | 頭 ab と尻 ab が一致(長さ2) |
| 4 | ababa | 3 | 頭 aba と尻 aba が一致(長さ3) |
| 5 | ababac | 0 | c で切れた |
| 6 | ababaca | 1 | 頭 a と尻 a |
abcdef は全部 0 です。 同じ文字が1つも繰り返さないので、使い回せる情報がありません。 つまり KMP は、パターンに繰り返しが無いなら素朴な探索と同じ動きになります。 得をするのは繰り返しがあるときだけです。
そして aaab は 0 1 2 0。 これが最悪ケースで効きます。 「3文字合って外れた」とき、fail[2] = 2 なので、2文字合っている状態から続けられる。 頭に戻りません。
結果
| 実装 | 最悪ケース(n=200,000 / m=100)の比較回数 |
|---|---|
| 素朴 | 19,990,100 |
| KMP | 599,900 |
| 比 | 33.3 倍 |
素朴が n×m ≒ 2000万。KMP は n×3 ≒ 60万。
なぜ KMP は 60万で、20万(= n)ではないのか。 これは私がつまずいたところです。KMP が
O(n+m)なのは外側のループの回数の話で、 内側のwhile(failを辿って後退する)が回るぶんが乗っています。 それでもトータルは n に比例するので、n を倍にすれば比較も倍になります。n×m にはなりません。
そして、答えは indexOf と1万回すべて一致しました。 自分で書いたアルゴリズムは、必ず標準実装と突き合わせます。 前回の記事で「オラクル」と呼んだやり方と同じです。
④ Boyer-Moore — 後ろから比べると、大きく飛べる
ここが一番おもしろいところでした。
KMP は「後戻りしない」ことで速くしています。Boyer-Moore は違います。「そもそも読まない」で速くします。
なぜ後ろから比べるのか
パターンが EXAMPLE(7文字)だとします。テキストの 7文字目が S だったとします。
text: H E R E I S A S I M P L E ...
pat: E X A M P L E
↑ ここから比べる(後ろから)
S は EXAMPLE の中に1つもありません。
ということは、この S に重なる位置は全部ハズレです。1つずつずらす必要はありません。 S を飛び越えるところまで、一気に 7 文字進んでよい。
これが「後ろから比べる」の意味です。 前から比べていたら、「テキストの7文字目が何か」は最後まで分かりません。 後ろから比べるから、いきなり遠くの文字を見られる。
書く
nano bm.mjs。
// bm.mjs — Boyer-Moore(不一致文字規則だけの簡易版)。⚠️ 後ろから比べる
export function buildLast(pat) {
const last = new Map(); // 文字 → パターン内で最後に出る位置
for (let i = 0; i < pat.length; i++) last.set(pat[i], i);
return last;
}
export function bmSearch(text, pat, trace = null) {
let cmp = 0;
const n = text.length, m = pat.length;
const last = buildLast(pat);
let i = 0; // いま合わせている先頭位置
while (i + m <= n) {
let j = m - 1; // ⚠️ 後ろから
while (j >= 0 && (cmp++, text[i + j] === pat[j])) j--;
if (j < 0) return { index: i, cmp };
const c = text[i + j];
const l = last.has(c) ? last.get(c) : -1;
const shift = Math.max(1, j - l); // ⚠️ 含まれない文字なら j+1 = 最大 m 飛ぶ
if (trace) trace.push({ i, 不一致文字: c, パターン内の位置: l, ずらす量: shift });
i += shift;
}
return { index: -1, cmp };
}
Math.max(1, j - l)の1が重要です。 不一致文字がパターンの後ろのほうにあると、j - lがマイナスになることがあります。 そのまま足すと位置が戻って無限ループになります。私は最初これで固めました。(あとで書きます)
1歩ずつ、どれだけ飛んだか見る
nano step4.mjs。
import { bmSearch, buildLast } from './bm.mjs';
import { readFileSync } from 'node:fs';
console.log('--- 不一致文字表 ---');
console.log([...buildLast('EXAMPLE')].map(([c, i]) => `${c}:${i}`).join(' '));
console.log('\n--- 1歩ずつ、どれだけ飛んだか ---');
const trace = [];
const r = bmSearch('HERE IS A SIMPLE EXAMPLE OF TEXT', 'EXAMPLE', trace);
for (const t of trace) console.log(`位置${String(t.i).padStart(3)} 不一致="${t.不一致文字}" 表の位置=${String(t.パターン内の位置).padStart(2)} → ${t.ずらす量} 飛ぶ`);
console.log('結果:', r);
console.log('\n--- パターンが長いほど速くなるか(英文4MB) ---');
const text = readFileSync('corpus.txt', 'utf8');
for (const m of [4, 8, 16, 32, 64]) {
const pat = 'Zq'.repeat(m / 2); // 絶対に無い語(最後まで走る)
const r = bmSearch(text, pat);
console.log(`m=${String(m).padStart(2)} 比較=${String(r.cmp).padStart(9)} 1文字あたり${(r.cmp / text.length).toFixed(4)}回`);
}
--- 不一致文字表 ---
E:6 X:1 A:2 M:3 P:4 L:5
--- 1歩ずつ、どれだけ飛んだか ---
位置 0 不一致="S" 表の位置=-1 → 7 飛ぶ
位置 7 不一致="P" 表の位置= 4 → 2 飛ぶ
位置 9 不一致="I" 表の位置=-1 → 3 飛ぶ
位置 12 不一致="X" 表の位置= 1 → 5 飛ぶ
結果: { index: 17, cmp: 15 }
--- パターンが長いほど速くなるか(英文4MB) ---
m= 4 比較= 1000750 1文字あたり0.2502回
m= 8 比較= 500340 1文字あたり0.1251回
m=16 比較= 250109 1文字あたり0.0625回
m=32 比較= 125103 1文字あたり0.0313回
m=64 比較= 62553 1文字あたり0.0156回
この2つの出力を読む
まず上のトレース。32文字のテキストで、たった 4歩 で答えに着いています。比較はのべ 15回。
- 1歩目:
SはEXAMPLEに無い → 7文字(=パターン全長)飛ぶ - 2歩目:
Pは位置4にある →6 - 4 = 2飛ぶ(Pどうしを重ねに行く) - 3歩目:
Iは無い → 3飛ぶ - 4歩目:
Xは位置1 → 5飛ぶ
素朴な探索なら 17回ずらして、比較は数十回。 同じ答えに 4歩で着いています。
そして下の表が、この記事で一番「直感に反する」数字です。
| パターン長 m | 1文字あたりの比較回数 |
|---|---|
| 4 | 0.2502 |
| 8 | 0.1251 |
| 16 | 0.0625 |
| 32 | 0.0313 |
| 64 | 0.0156 |
パターンを倍にすると、比較回数がぴったり半分になっています。
探すものが長いほど、速い。 素朴な探索や KMP では絶対に起きません。あちらは
mが伸びれば仕事が増えるだけです。
理由は「飛べる距離がパターン長で決まる」から。m=64 なら、外れるたびに最大64文字飛べる。 4,000,021 ÷ 64 ≒ 62,500 で、実測の 62,553 とほぼ一致しました。理屈どおりです。
grep が使っているのは、この系統です。 だから grep で長い語を探しても遅くなりません。むしろ速い。
📸 スクリーンショット 02:
node step4.mjsの下半分。m を倍にするたび比較回数が半分になっている表を撮ります。
⑤ Rabin-Karp — 文字列を数値にして比べる
発想がまったく違います。 文字を比べるのをやめて、数にして比べます。
"abc" を「a=97, b=98, c=99 を使った3桁の数」だと思って、1つの数字にします。 テキスト側も同じ長さの窓を数字にする。数字が違えば、中身は絶対に違います。
ローリングハッシュ
問題は、窓を1文字ずらすたびに m 文字ぶん計算し直したら何も速くならないことです。
そこで、前の値から先頭を引いて、末尾を足すだけにします。
"abcd" → "bcde" にずらすとき
先頭 'a' の寄与を引く
全体を BASE 倍する(桁をずらす)
末尾 'e' を足す
これで1文字ずらすのが O(1) になります。 これがローリングハッシュです。
書く
nano rk.mjs。
// rk.mjs — Rabin-Karp。文字列を数値(ハッシュ)にして比べる
const BASE = 256;
const MOD = 1_000_003; // ⚠️ わざと小さめ。衝突を起こして見せるため
export function hash(s) {
let h = 0;
for (let i = 0; i < s.length; i++) h = (h * BASE + s.charCodeAt(i)) % MOD;
return h;
}
export function rkSearch(text, pat, stat = null) {
const n = text.length, m = pat.length;
if (m > n) return { index: -1, cmp: 0 };
let high = 1; // BASE^(m-1) % MOD
for (let i = 0; i < m - 1; i++) high = (high * BASE) % MOD;
const hp = hash(pat);
let ht = hash(text.slice(0, m));
let cmp = 0, hit = 0, collision = 0;
for (let i = 0; ; i++) {
if (ht === hp) {
hit++;
let ok = true; // ⚠️ ハッシュが同じでも必ず本体を比べる
for (let j = 0; j < m; j++) { cmp++; if (text[i + j] !== pat[j]) { ok = false; break; } }
if (ok) { if (stat) Object.assign(stat, { hit, collision }); return { index: i, cmp }; }
collision++;
}
if (i + m >= n) break;
// ローリングハッシュ: 先頭を引いて、末尾を足すだけ(O(1))
ht = (ht - text.charCodeAt(i) * high % MOD + MOD) % MOD;
ht = (ht * BASE + text.charCodeAt(i + m)) % MOD;
}
if (stat) Object.assign(stat, { hit, collision });
return { index: -1, cmp };
}
// 複数パターンを1回の走査で探す(Rabin-Karp が得意なところ)
export function rkMulti(text, pats) {
const m = pats[0].length;
const table = new Map();
for (const p of pats) {
const h = hash(p);
if (!table.has(h)) table.set(h, []);
table.get(h).push(p);
}
let high = 1;
for (let i = 0; i < m - 1; i++) high = (high * BASE) % MOD;
let ht = hash(text.slice(0, m));
const found = [];
for (let i = 0; ; i++) {
const cand = table.get(ht);
if (cand) for (const p of cand) if (text.startsWith(p, i)) found.push({ at: i, pat: p });
if (i + m >= text.length) break;
ht = (ht - text.charCodeAt(i) * high % MOD + MOD) % MOD;
ht = (ht * BASE + text.charCodeAt(i + m)) % MOD;
}
return found;
}
+ MODを足してから% MODしている理由。 JavaScript の%は負の数に対して負を返します。-3 % 5は2ではなく-3。 引き算のあとそのまま%を取るとハッシュが負になって一致しなくなるので、必ずMODを足してから取ります。
衝突を実際に起こす
「ハッシュが一致しても本物とは限らない」は、言葉で読んでも身につきませんでした。作ります。
nano step5.mjs。
import { hash, rkSearch, rkMulti } from './rk.mjs';
import { readFileSync } from 'node:fs';
console.log('--- ローリングハッシュが正しいか ---');
console.log('hash("abcd") =', hash('abcd'), ' hash("abce") =', hash('abce'));
console.log('\n--- 衝突を探す(4文字、MOD=1000003)---');
const cs = 'abcdefghijklmnopqrstuvwxyz';
const seen = new Map();
let found = 0;
outer:
for (const a of cs) for (const b of cs) for (const c of cs) for (const d of cs) {
const s = a + b + c + d, h = hash(s);
if (seen.has(h)) { console.log(`衝突: "${seen.get(h)}" と "${s}" が同じ ${h}`); if (++found === 3) break outer; }
else seen.set(h, s);
}
console.log('\n--- 複数パターンを1回の走査で ---');
const text = readFileSync('corpus.txt', 'utf8');
const hits = rkMulti(text.slice(0, 200000), ['water', 'money', 'zzzzz', 'night']);
const count = {};
for (const h of hits) count[h.pat] = (count[h.pat] || 0) + 1;
console.log('20万文字を1回なめた結果:', count);
--- ローリングハッシュが正しいか ---
hash("abcd") = 833025 hash("abce") = 833026
--- 衝突を探す(4文字、MOD=1000003)---
衝突: "afpa" と "daaw" が同じ 98491
衝突: "afpb" と "daax" が同じ 98492
衝突: "afpc" と "daay" が同じ 98493
--- 複数パターンを1回の走査で ---
20万文字を1回なめた結果: { water: 47, money: 72, night: 84 }
衝突が見つかりました。 "afpa" と "daaw" はまったく別の文字列なのに、ハッシュが同じ 98491 です。
これを使って、本体の照合を省いたらどうなるかを見ます。nano step5b.mjs。
import { hash, rkSearch } from './rk.mjs';
// "afpa" と "daaw" はハッシュが同じ。本体を比べなければ誤検出する
console.log('hash("afpa") =', hash('afpa'), ' hash("daaw") =', hash('daaw'));
const text = 'xxxx daaw xxxx afpa xxxx';
const st = {};
const r = rkSearch(text, 'afpa', st);
console.log('探した位置:', r.index, '(indexOf:', text.indexOf('afpa'), ')');
console.log('ハッシュが一致した回数:', st.hit, ' そのうち偽物(衝突):', st.collision);
hash("afpa") = 98491 hash("daaw") = 98491
探した位置: 15 (indexOf: 15 )
ハッシュが一致した回数: 2 そのうち偽物(衝突): 1
ハッシュは2回一致し、そのうち1回は偽物でした。
もし if (ht === hp) return i; と書いていたら、位置 5 の daaw を「見つけた」と返していました。 エラーも警告も出ません。黙って間違った答えを返します。
これが Rabin-Karp の最大の注意点です。 ハッシュは「ここは違う」を高速に判定する道具であって、「ここは同じ」の証明ではない。 10万件のincludesで止まる — コンピュータ科学深掘り と同じ話でした。 ハッシュテーブルでも、バケットに当たったあと必ずキーそのものを比べています。
Rabin-Karp が本当に強いところ
単独パターンでは、この記事の実測で一番遅いです。(次の節)
得意なのは、複数のパターンを1回の走査で探すこと。 上の出力がそれです。
20万文字を1回なめた結果: { water: 47, money: 72, night: 84 }
4つの語を、テキスト1回のなめで全部数えました。 indexOf を4回呼べば4回なめることになります。
冒頭に書いた「禁止語2,000語」の問題が、まさにこれです。 includes を2,000回呼ぶ代わりに、ハッシュ表を1つ作って1回なめる。 (実務では語の長さが揃わないので Aho-Corasick という別の道具を使いますが、考え方の入口はここです。)
⑥ 4つ + indexOf を、同じデータで測る
比較回数は分かりました。次は時間です。
比較回数と時間は一致しません。 比較が少なくても、1回の処理が重ければ遅くなります。
nano bench.mjs。
import { readFileSync } from 'node:fs';
import { naiveSearch } from './naive.mjs';
import { kmpSearch } from './kmp.mjs';
import { bmSearch } from './bm.mjs';
import { rkSearch } from './rk.mjs';
const ms = (f) => { const t = performance.now(); const r = f(); return { ms: performance.now() - t, r }; };
function run(name, text, pat) {
console.log(`\n=== ${name} n=${text.length} m=${pat.length} ===`);
const rows = [
['素朴', () => naiveSearch(text, pat).index],
['KMP', () => kmpSearch(text, pat).index],
['Boyer-Moore', () => bmSearch(text, pat).index],
['Rabin-Karp', () => rkSearch(text, pat).index],
['indexOf', () => text.indexOf(pat)],
];
for (const [label, f] of rows) {
f(); // 1回捨てる(JITを温める)
const a = ms(f), b = ms(f), c = ms(f);
const best = Math.min(a.ms, b.ms, c.ms);
console.log(`${label.padEnd(12)} ${best.toFixed(2).padStart(8)} ms 結果=${a.r}`);
}
}
const text = readFileSync('corpus.txt', 'utf8');
run('英文4MB・見つからない語', text, 'zebra quantum banana');
run('英文4MB・終わりのほうにある語', text, text.slice(-60, -40));
const bad = 'a'.repeat(200000), badPat = 'a'.repeat(99) + 'b';
run('最悪ケース a×20万 / a×99+b', bad, badPat);
=== 英文4MB・見つからない語 n=4000021 m=20 ===
素朴 51.57 ms 結果=-1
KMP 51.59 ms 結果=-1
Boyer-Moore 11.25 ms 結果=-1
Rabin-Karp 100.73 ms 結果=-1
indexOf 1.38 ms 結果=-1
=== 英文4MB・終わりのほうにある語 n=4000021 m=20 ===
素朴 0.73 ms 結果=65233
KMP 0.79 ms 結果=65233
Boyer-Moore 1.13 ms 結果=65233
Rabin-Karp 3.91 ms 結果=65233
indexOf 0.03 ms 結果=65233
=== 最悪ケース a×20万 / a×99+b n=200000 m=100 ===
素朴 285.78 ms 結果=-1
KMP 6.27 ms 結果=-1
Boyer-Moore 5.56 ms 結果=-1
Rabin-Karp 1.98 ms 結果=-1
indexOf 0.89 ms 結果=-1
まとめるとこうです。
| 実装 | 英文・不在(4MB) | 英文・途中で発見 | 最悪ケース |
|---|---|---|---|
| 素朴 | 51.57 ms | 0.73 ms | 285.78 ms |
| KMP | 51.59 ms | 0.79 ms | 6.27 ms |
| Boyer-Moore | 11.25 ms | 1.13 ms | 5.56 ms |
| Rabin-Karp | 100.73 ms | 3.91 ms | 1.98 ms |
indexOf | 1.38 ms | 0.03 ms | 0.89 ms |
読み取れたこと
1. indexOf が全部に勝つ。 どのケースでも最速です。私が書いた最良の実装(Boyer-Moore の 11.25 ms)の 8倍速い。
理由は、V8 の indexOf が C++ で書かれていて、内部で Boyer-Moore-Horspool 系を使い、さらに CPU の命令で複数バイトを一度に比べているからです。JavaScript で1文字ずつ配列アクセスする実装が勝てる相手ではありません。
2. KMP は英文では素朴と同じ。 51.57 と 51.59。英文にはパターンの繰り返しがほぼ無いので、テーブルが 0 ばかりで効きません。 ③ で abcdef の fail が全部 0 だったのと同じ話です。
3. Boyer-Moore だけが英文で明確に速い。 素朴の 4.6倍。「読まない」が効いています。
4. Rabin-Karp は英文では一番遅い。 1文字ごとに掛け算と剰余をやっているからです。比較回数は少なくても、1回が重い。
5. 最悪ケースでは、素朴だけが崩れる。 285.78 ms 対 それ以外は一桁 ms。46倍から144倍。
ここが「知る価値」の答えです。 速い実装を書くために勉強するのではありません。 それは
indexOfに任せます。 勉強する理由は、「なぜindexOfは速いのか」「どういう入力で自分のコードが崩れるのか」を説明できるようになるためです。 285.78 ms という数字を自分で出したことがあるかどうかが、本番で「なぜか数秒かかる」を見たときの差になります。
⑦ 実務での文字列探索 — grep・正規表現・DB
grep を測る
grep は Boyer-Moore 系を使っています。 実際に測ります。
grep (GNU grep) 3.11
3回ずつ測って最速を取る小さい関数を、シェルにその場で定義します。
リテラル grep 97 ms
リテラル grep -F 79 ms
選択(4語) grep -E 94 ms
選択(4語) grep -F 122 ms
先頭一致 grep -E 162 ms
任意文字混じり grep -E 192 ms
大文字小文字 grep -i 131 ms
私はここで予想を外しました。
「-F は正規表現として解釈しないから速い」と思っていました。リテラルでは 97 → 79 ms。確かに少し速い。 でも -F で4語を並べたら 122 ms で、-E の選択(94 ms)より遅かった。
GNU grep は、パターンに正規表現の記号が無ければ自動でリテラル用の速い経路に入ります。 なので
-Fを付けても劇的には変わりません。 効くのは「記号を含む文字列をそのまま探したいとき」です。
本当に効いているのは、-F かどうかより「パターンの形」でした。
| パターンの形 | 時間 | なぜ |
|---|---|---|
リテラル language | 79〜97 ms | Boyer-Moore で飛べる |
任意文字 l.ng.age | 192 ms | 飛べない。1文字ずつ試すしかない |
先頭一致 ^[A-Z][a-z]+ | 162 ms | 飛べない |
大文字小文字無視 -i | 131 ms | 各文字に2通りあるので飛ぶ量が減る |
結論。
grepを速く使うコツは-Fを覚えることではなく、 「なるべく長いリテラル部分を含むパターンにする」ことでした。 長いリテラルほど大きく飛べます(④の表)。
grep そのものの使い方は本線の サーバーの中身はテキスト — grep・sed・awkとvim にあります。
正規表現 — 守る側の書き方
正規表現エンジンの中身は、本線の 正規表現が固まる理由 — エンジンを100行で自作する で自作しています。 ここでは自分のコードを守るための1点だけ確かめます。
量指定子の入れ子((何かの繰り返し)+ の形)を書くと、入力によって試す組み合わせが爆発します。
問題は「遅くなる」ことではありません。気づけないことです。
nano step7.mjs。
import { readFileSync } from 'node:fs';
const lines = readFileSync('corpus.txt', 'utf8').split('\n').slice(0, 20000);
// ⚠️ 危ないほう: 量指定子が入れ子(( ... + )+ の形)
const risky = /^(\w+\s?)+\.$/;
// 安全なほう: 入れ子にしない
const safe = /^[\w\s]+\.$/;
for (const [name, re] of [['入れ子あり', risky], ['入れ子なし', safe]]) {
const t = performance.now();
let hit = 0;
for (const l of lines) if (re.test(l)) hit++;
console.log(`${name} ${(performance.now() - t).toFixed(1)} ms 一致=${hit}`);
}
入れ子あり 18.3 ms 一致=20000
入れ子なし 20.3 ms 一致=20000
差がありません。むしろ危ないほうが速い。
これが一番怖いところでした。 一致している間は、爆発しません。 正規表現エンジンは最初の道筋で答えが出れば、そこで終わるからです。 爆発するのは一致しなかったとき、つまり全部の組み合わせを試し尽くしてから諦めるときです。 テストデータは普通「一致する正しい入力」で書きます。だからテストをすり抜けます。
守る側としてやることは3つです。これは自分のコードの書き方の話です。
- 量指定子を入れ子にしない。
(\w+\s?)+は[\w\s]+で書けます。書けるなら、そう書く - 外から来る文字列に正規表現をかける前に、長さの上限を決める。
if (s.length > 200) return reject()を先に置く - できるなら正規表現を使わない。
startsWith/endsWith/includes/splitで足りることは多い
私が実際にやったのは 2 です。 入力長の上限を先に置くだけで、最悪ケースの上限が決まります。 正規表現を書き直すより先に、入力の大きさを縛るほうが確実でした。
DB の部分一致
LIKE '%word%' が索引を使えないのも、同じ話です。
索引(B木)は「先頭から順に並んでいる」ことで二分探索できる仕組みです。 LIKE 'word%'(前方一致)は先頭が決まっているので索引が効きます。
%word% は先頭が決まっていないので、二分探索の出発点がありません。 全部の行を見るしかない。
これは DB の都合ではなく、この記事でやっていることそのものでした。 接尾辞配列(⑨)が「全部の接尾辞を並べる」理由も同じです。先頭が決まっていないものを引くには、先頭を全部作るしかない。
詳しくは本線の 部分一致は索引が効かない — 全文検索とMeilisearch にあります。
⑧ ハフマン符号 — よく出る文字を短くする
文字列探索とは別の問題です。 でも扱っているものは同じ「文字列」で、使う道具(頻度・木・貪欲)も同じです。
発想
普通、1文字は 8 ビットです。a も Q も同じ 8 ビット。
でも英文では e は Q の何千倍も出てきます。
なら、よく出る文字を短く、めったに出ない文字を長くすれば、全体は縮む。
これがハフマン符号です。gzip の中で実際に使われています。
小さい例で確かめる
nano huffman.mjs。
// huffman.mjs — よく出る文字に短いビット列を割り当てる
export function countFreq(text) {
const f = new Map();
for (const c of text) f.set(c, (f.get(c) || 0) + 1);
return f;
}
export function buildTree(freq) {
// 出現回数の小さい2つを取り出して繋ぐ、を1本になるまで繰り返す
let nodes = [...freq].map(([ch, n]) => ({ ch, n }));
if (nodes.length === 1) return { n: nodes[0].n, l: nodes[0], r: null };
while (nodes.length > 1) {
nodes.sort((a, b) => a.n - b.n);
const l = nodes.shift(), r = nodes.shift();
nodes.push({ n: l.n + r.n, l, r });
}
return nodes[0];
}
export function buildCodes(node, prefix = '', out = new Map()) {
if (node.ch !== undefined) { out.set(node.ch, prefix || '0'); return out; }
if (node.l) buildCodes(node.l, prefix + '0', out);
if (node.r) buildCodes(node.r, prefix + '1', out);
return out;
}
export function encodedBits(freq, codes) {
let bits = 0;
for (const [ch, n] of freq) bits += n * codes.get(ch).length;
return bits;
}
nodes.sort()を毎回やっているのは、分かりやすさのためです。 本来はヒープ(優先度付きキュー)を使います。このシリーズで前に書いた 10件欲しいだけで100万件ソート — コンピュータ科学深掘り の道具です。 「一番小さいものを繰り返し取り出す」は、ヒープが最も得意な形でした。
nano step8a.mjs。
import { countFreq, buildTree, buildCodes, encodedBits } from './huffman.mjs';
const s = 'abracadabra';
const freq = countFreq(s);
const codes = buildCodes(buildTree(freq));
console.log('文字列:', s, `(${s.length}文字 = ${s.length * 8}ビット)`);
for (const [ch, n] of [...freq].sort((a, b) => b[1] - a[1]))
console.log(` ${ch} ${n}回 → ${codes.get(ch)}`);
console.log('符号化:', [...s].map(c => codes.get(c)).join(''));
console.log('ビット数:', encodedBits(freq, codes), '→', (encodedBits(freq, codes) / (s.length * 8) * 100).toFixed(1) + '%');
文字列: abracadabra (11文字 = 88ビット)
a 5回 → 0
b 2回 → 110
r 2回 → 111
c 1回 → 100
d 1回 → 101
符号化: 01101110100010101101110
ビット数: 23 → 26.1%
88ビットが 23ビットになりました。
a は 5回出るので 1ビット。c と d は 1回なので 3ビット。
ここで一番大事な性質。
aは0。他は全部1で始まっています。どの符号も、他の符号の頭になっていない。 だから01101110100...を区切り記号なしで前から読んでいけば、一意に戻せます。0を読んだ瞬間に「これはaで確定」。これを接頭符号と言います。
英文4MBでやる
nano step8.mjs。
import { readFileSync } from 'node:fs';
import { countFreq, buildTree, buildCodes, encodedBits } from './huffman.mjs';
const text = readFileSync('corpus.txt', 'utf8');
const freq = countFreq(text);
const codes = buildCodes(buildTree(freq));
const sorted = [...freq].sort((a, b) => b[1] - a[1]);
console.log('文字 出現回数 割合 符号 ビット長');
for (const [ch, n] of sorted.slice(0, 12)) {
const label = ch === '\n' ? '\\n' : ch === ' ' ? '␣' : ch;
console.log(`${label.padEnd(4)} ${String(n).padStart(9)} ${(n / text.length * 100).toFixed(2).padStart(6)}% ${codes.get(ch).padEnd(12)} ${codes.get(ch).length}`);
}
console.log('...');
for (const [ch, n] of sorted.slice(-4)) {
const label = ch === '\n' ? '\\n' : ch === ' ' ? '␣' : ch;
console.log(`${label.padEnd(4)} ${String(n).padStart(9)} ${(n / text.length * 100).toFixed(4).padStart(6)}% ${codes.get(ch).padEnd(12)} ${codes.get(ch).length}`);
}
const bits = encodedBits(freq, codes);
const orig = text.length * 8;
console.log(`\n使った文字の種類: ${freq.size}`);
console.log(`元: ${orig} ビット (${(orig / 8).toLocaleString()} バイト)`);
console.log(`ハフマン: ${bits} ビット (${Math.ceil(bits / 8).toLocaleString()} バイト)`);
console.log(`圧縮率: ${(bits / orig * 100).toFixed(1)}%`);
console.log(`1文字あたり平均 ${(bits / text.length).toFixed(2)} ビット(元は8ビット)`);
文字 出現回数 割合 符号 ビット長
␣ 678701 16.97% 111 3
e 425849 10.65% 010 3
o 258486 6.46% 1010 4
a 240869 6.02% 1001 4
t 239908 6.00% 1000 4
r 226156 5.65% 0110 4
n 196685 4.92% 0010 4
s 178263 4.46% 0000 4
l 173602 4.34% 11011 5
i 160793 4.02% 11010 5
h 148089 3.70% 10111 5
d 116854 2.92% 01111 5
...
K 527 0.0132% 1100001001000 13
V 377 0.0094% 11000010010011 14
Q 150 0.0037% 110000100100101 15
J 2 0.0000% 110000100100100 15
使った文字の種類: 53
元: 32000168 ビット (4,000,021 バイト)
ハフマン: 17478313 ビット (2,184,790 バイト)
圧縮率: 54.6%
1文字あたり平均 4.37 ビット(元は8ビット)
空白が 3ビット、e が 3ビット。J(2回しか出ない)が 15ビット。
平均 4.37 ビット。元の 8ビットの約半分。圧縮率 54.6%。
gzip と比べる
gzip はハフマン符号を使っています。 同じファイルで測ります。
-rw-rw-r-- 1 user user 4000021 Oct 3 10:12 corpus.txt
-rw-rw-r-- 1 user user 1492288 Oct 3 10:12 corpus.txt.gz
gzip 圧縮率: 37.3%
| やりかた | サイズ | 圧縮率 |
|---|---|---|
| 元 | 4,000,021 バイト | 100% |
| 私のハフマンだけ | 2,184,790 バイト | 54.6% |
gzip -9 | 1,492,288 バイト | 37.3% |
gzip のほうが 17ポイント小さい。 ハフマンだけでは届きません。
理由は、gzip(DEFLATE)が2段構えだからです。
- LZ77: 前に出た同じ並びを「◯文字前から△文字ぶんコピー」に置き換える。単語や言い回しの繰り返しが消える
- ハフマン符号: そのあとの記号列に、短いビット列を割り当てる
私が作ったのは 2 だけ。 gzip は 1 で「the が何万回も出る」ような単位の繰り返しを先に潰してから、2 をかけています。
これは仕様書(RFC 1951)に明記されています。 推測ではありません。 「ハフマン=圧縮」ではなく、「ハフマンは圧縮の最後の1段」でした。
📸 スクリーンショット 03:
node step8.mjsの出力と、そのすぐ下にls -l corpus.txt corpus.txt.gzの結果。 自分のハフマン(54.6%)と gzip(37.3%)が同じ画面に並んでいるところを撮ります。
ここで①〜⑤の話と繋がります。 ハフマンは「よく出る文字は短く」。Boyer-Moore は「無い文字なら大きく飛ぶ」。 どちらも「文字の出方には偏りがある」という同じ事実を、別の方向に使っています。
⑨ 接尾辞配列 — 1回なら要らない、何度もなら作る
最後は前回の記事と同じ判断の話です。
前回は「ソートの時間を勘定に入れる」でした。今回は「接尾辞配列を作る時間を勘定に入れる」です。
接尾辞配列とは
すべての接尾辞を、辞書順に並べた開始位置の配列です。
nano suffix.mjs。
// suffix.mjs — 接尾辞配列。⚠️ 1回だけ探すなら要らない。何度も探すなら作る
export function buildSuffixArray(text) {
// 素朴な作り方(分かりやすさ優先)。全部の接尾辞を辞書順に並べる
const sa = Array.from({ length: text.length }, (_, i) => i);
sa.sort((a, b) => {
const x = text.slice(a), y = text.slice(b);
return x < y ? -1 : x > y ? 1 : 0;
});
return sa;
}
// その接尾辞配列に対して、二分探索で部分文字列を引く
export function saSearch(text, sa, pat) {
let lo = 0, hi = sa.length, steps = 0;
while (lo < hi) { // 最初に pat 以上になる位置
const mid = lo + ((hi - lo) >> 1); steps++;
if (text.slice(sa[mid], sa[mid] + pat.length) < pat) lo = mid + 1; else hi = mid;
}
const start = lo;
hi = sa.length;
while (lo < hi) { // pat で始まらなくなる位置
const mid = lo + ((hi - lo) >> 1); steps++;
if (text.startsWith(pat, sa[mid])) lo = mid + 1; else hi = mid;
}
return { positions: sa.slice(start, lo).sort((a, b) => a - b), steps };
}
lo + ((hi - lo) >> 1)は前回の記事と同じです。(lo + hi) / 2と書くと小数の添字になり、 エラーも出さずにundefinedを返して静かに壊れます。
nano step9.mjs。
import { readFileSync } from 'node:fs';
import { buildSuffixArray, saSearch } from './suffix.mjs';
const s = 'banana';
const sa = buildSuffixArray(s);
console.log('文字列:', s);
console.log('順位 開始位置 接尾辞');
sa.forEach((p, r) => console.log(`${String(r).padStart(3)} ${String(p).padStart(6)} ${s.slice(p)}`));
console.log('\n"ana" を二分探索:', saSearch(s, sa, 'ana'));
console.log('"na" を二分探索:', saSearch(s, sa, 'na'));
console.log('"xyz" を二分探索:', saSearch(s, sa, 'xyz'));
文字列: banana
順位 開始位置 接尾辞
0 5 a
1 3 ana
2 1 anana
3 0 banana
4 4 na
5 2 nana
"ana" を二分探索: { positions: [ 1, 3 ], steps: 5 }
"na" を二分探索: { positions: [ 2, 4 ], steps: 4 }
"xyz" を二分探索: { positions: [], steps: 2 }
ここを読むのに時間がかかりました。落ち着いて見ます。
banana の接尾辞は 6本。それを辞書順に並べたのが上の表です。
ana を探したいとします。 並んでいるので、ana で始まる接尾辞は必ず連続しています。(順位 1 と 2)
これが接尾辞配列の全部です。 「文書のどこかに
anaがある」=「anaで始まる接尾辞がある」。 接尾辞が辞書順に並んでいれば、二分探索でその範囲を挟める。
そして返ってきた positions: [1, 3] は、banana の 1文字目と 3文字目から ana が始まるという意味です。b-anana と ban-ana。合っています。
indexOf は「最初の1つ」しか返しません。接尾辞配列は「全部の位置」を一度に返します。
交差点を測る
では、作る価値があるのはいつか。 nano step10.mjs。
import { readFileSync } from 'node:fs';
import { buildSuffixArray, saSearch } from './suffix.mjs';
const text = readFileSync('corpus.txt', 'utf8').slice(0, 200000);
let t = performance.now();
const sa = buildSuffixArray(text);
const build = performance.now() - t;
const w = 'water';
console.log('接尾辞の数:', sa.length, ' 二分探索の歩数:', saSearch(text, sa, w).steps, ' (log2(20万) ≒ 17.6)');
const one = (f) => { const s = performance.now(); f(); return performance.now() - s; };
const perSa = one(() => { for (let i = 0; i < 1000; i++) saSearch(text, sa, w); }) / 1000;
const perIo = one(() => { for (let i = 0; i < 1000; i++) { let p = -1, c = 0; while ((p = text.indexOf(w, p + 1)) !== -1) c++; } }) / 1000;
console.log(`1回あたり 接尾辞配列 ${perSa.toFixed(4)} ms / indexOf総なめ ${perIo.toFixed(4)} ms`);
console.log(`作る時間 ${build.toFixed(0)} ms`);
console.log(`交差点: ${Math.ceil(build / (perIo - perSa))} 回引いたら、作ったほうが得`);
接尾辞の数: 200000 二分探索の歩数: 30 (log2(20万) ≒ 17.6)
1回あたり 接尾辞配列 0.0080 ms / indexOf総なめ 0.1594 ms
作る時間 1350 ms
交差点: 8916 回引いたら、作ったほうが得
数字を並べます。
| 値 | |
|---|---|
| 接尾辞配列を作る時間(20万文字) | 1,350 ms |
| 1回引く(接尾辞配列) | 0.0080 ms |
1回引く(indexOf で全部の位置を数える) | 0.1594 ms |
| 1回あたりの節約 | 0.1514 ms |
| 交差点 | 8,916 回 |
1回だけ引くなら、接尾辞配列は 8,900倍の無駄です。 8,916回を超えて同じ文書を引くなら、作ったほうが得。
二分探索の歩数は 30。 log2(200000) ≒ 17.6 の 2倍弱です(範囲の左端と右端を2回探しているためです)。 20万件の中から、30回の比較で全部の出現位置が取れています。
これが全文検索エンジンの正体
「1回だけなら不要、何度も引くなら作る」 —— これがそのまま「索引を作る」という判断です。
- DB の索引: 挿入のたびに B木を更新します(=作る)。だから
SELECTが速く、INSERTが遅い - 全文検索エンジン(Meilisearch / Elasticsearch): 文書を登録するときに索引を作ります。検索は一瞬、登録は重い
grep: 索引を作りません。 毎回まるごとなめる。1回きりの検索に最適
「grep は遅い」ではありません。「grep は索引を持たない選択をしている」です。 1回しか引かないファイルに索引を作るのは、この記事の実測で 8,900倍の損でした。
判断表
| 状況 | 使うもの | 理由 |
|---|---|---|
| 文字列1本から1回探す | indexOf / includes | 自作より速い。 迷う理由が無い |
| 同じテキストから多数の語を1回で探す | Rabin-Karp(複数版)/ Aho-Corasick | 1回のなめで全部済む |
| ファイルを1回検索する | grep(長いリテラルを含める) | 索引を作らないのが正解 |
| 同じ文書を何度も検索する | 索引(接尾辞配列 / 全文検索エンジン) | 交差点を超えるなら作る |
| 外から来る文字列に正規表現 | 先に長さの上限を置く | 一致するうちは爆発しない=テストで出ない |
DB で %word% | 全文検索索引に逃がす | B木は先頭が決まっていないと使えない |
| 保存・転送を小さくしたい | gzip(LZ77 + ハフマン) | 自作ハフマンだけでは 17ポイント負けた |
つまずいたところ
1. Boyer-Moore が無限ループで固まった。 shift = j - last.get(c) とだけ書いていました。不一致文字がパターンの後ろのほうにあると j - l がマイナスになり、i が戻ります。永久に終わりません。 Math.max(1, j - l) の 1 は飾りではなく、必ず前に進むことを保証する部分でした。Ctrl+C で止めて、trace を出して初めて分かりました。
2. Rabin-Karp のハッシュが途中から一致しなくなった。 ht = (ht - text.charCodeAt(i) * high) % MOD; と書いていました。 JavaScript の % は負の数に負を返します。 -7 % 5 は 3 ではなく -2。 ハッシュが負になり、パターンのハッシュ(正)と永久に一致しなくなります。+ MOD を足してから % MOD。 ここも例外は出ず、静かに「見つからない」を返し続けました。
3. Rabin-Karp が「見つけた」と言った場所に、探した語が無かった。 if (ht === hp) return i; と書いていたからです。衝突しても気づけません。 indexOf と突き合わせるまで、私はこのコードが正しいと思っていました。 ハッシュ一致は候補であって答えではない。
4. KMP が英文でまったく速くならず、実装を疑った。 実装は正しくて、英文にはパターンの繰り返しが無いので効かないだけでした。 abcdef の部分一致テーブルが全部 0 だと分かって納得しました。テーブルが 0 ばかりなら、KMP は素朴な探索そのものです。
5. grep -F が grep -E より遅くて、測り方を疑った。 何度測っても同じでした。GNU grep はリテラルなら自動で速い経路を選ぶので、-F の効果はほぼ無い。 「たぶんこうだろう」を測らずに書かなくてよかったところです。予想を外したまま記事にするところでした。
6. 危ない正規表現と安全な正規表現で、時間差が出なかった。 最初は「入れ子は遅い」ことを見せる予定でした。出ませんでした。 一致している間は爆発しないからです。これは失敗ではなく、この節で一番書くべきことでした。 テストは普通「正しい入力」で書くので、この問題はテストをすり抜けて本番で出ます。
7. 自作ハフマンが 54.6% で、想定より縮まなかった。 gzip は 37.3%。gzip はハフマンの前に LZ77 で繰り返しを潰しているからでした。 「ハフマン=圧縮」だと思っていたのが間違いで、ハフマンは最後の1段です。
8. 接尾辞配列を 4MB 全部で作ろうとして、返ってこなかった。 text.slice(a) で毎回文字列をコピーして比べているので、4MB では現実的な時間で終わりません。 20万文字に落として 1,350 ms でした。実務のライブラリは SA-IS 法という別のアルゴリズムを使います。 「素朴な作り方は、教材としては正しく、実用としては使えない」をここでも踏みました。
後片づけ
実験用のフォルダを消します。 corpus.txt が 4MB あるので、放っておくと邪魔です。
消す前に、何を消すのか必ず見ます。
合計 4004
drwxrwxr-x 2 user user 4096 Oct 3 10:40 .
drwxrwxr-x 3 user user 4096 Oct 3 10:12 ..
-rw-rw-r-- 1 user user 456 Oct 3 10:20 bm.mjs
-rw-rw-r-- 1 user user 4000021 Oct 3 10:12 corpus.txt
-rw-rw-r-- 1 user user 1543 Oct 3 10:12 gen.mjs
(以下略)
7.7M /home/user/cslab
中身が実験ファイルだけであることを確かめてから、消します。
rm -rfは打ち間違えると戻せません。 必ずlsで中身を見てから打ってください。パスを1文字間違えて~/を消すと、ホームディレクトリごと消えます。
~/cslab に他の回のフォルダが残っていなければ、こちらも消して構いません。
rmdirは空のディレクトリしか消しません。 中身が残っていれば何も起きないので、間違えても安全です。
まとめ — 理解できたこと
indexOfは私が書いた4つの実装すべてに勝った。 英文4MBで 1.38 ms 対 Boyer-Moore 11.25 ms。速い実装を書くために学ぶのではない- 学ぶ理由は「なぜ速いのか」と「どういう入力で崩れるのか」を説明できるようになるため。 285.78 ms を自分で出したことがあるかが差になる
- 素朴な探索の最悪
O(n×m)は実在する。a× 20万 とa× 99 +bで 19,990,100回。テキスト1文字あたり 100回 - 同じ素朴な探索が、英文では1文字あたり 1.001回で済む。 英文はほとんど最初の1文字で外れるから
- KMP の要点は1つ。「途中まで一致した情報を使い回す」。 だからテキスト側の添字が一度も戻らない
- 最悪ケースで素朴 19,990,100 対 KMP 599,900 で 33.3倍。 ただし英文では素朴と同着(51.57 対 51.59 ms)
- KMP が効くのはパターンに繰り返しがあるときだけ。
abcdefの部分一致テーブルは全部 0 で、そのとき KMP は素朴な探索そのもの - Boyer-Moore は後ろから比べるから、パターンが長いほど速い。 m を 4→64 にすると比較回数が 0.2502 → 0.0156(倍にするたび半分)
- これが
grepを速く使うコツに直結する。-Fを覚えることではなく、長いリテラルを含むパターンにすること - Rabin-Karp のハッシュ一致は「候補」であって答えではない。
"afpa"と"daaw"が実際に衝突し、本体を比べなければ誤検出した - Rabin-Karp が勝つのは複数パターン。 4語を1回のなめで数えられる。
includesを語の数だけ呼ぶ設計はここで直せる - 量指定子の入れ子は、一致しているうちは爆発しない。 実測で差が出なかった。だからテストをすり抜けて本番で出る
- 守る側の対策は3つ。入れ子にしない・入力長の上限を先に置く・そもそも正規表現を使わない
- ハフマン符号は「よく出る文字に短いビット列」。 空白と
eが 3ビット、2回しか出ないJが 15ビット。平均 4.37ビット、54.6% gzipは 37.3%。ハフマンだけでは 17ポイント負ける。gzipは LZ77 で繰り返しを潰してからハフマンをかけている- 接尾辞配列は 1回だけなら 8,900倍の無駄。 作るのに 1,350 ms、1回の節約が 0.1514 ms。交差点は 8,916回
- 「1回なら作らない、何度もなら作る」が索引の全部。 DBの索引も全文検索エンジンも同じ判断。
grepは索引を作らない選択をしている - Boyer-Moore の「無い文字なら大きく飛ぶ」と、ハフマンの「よく出る文字を短く」は同じ事実の裏表。 文字の出方には偏りがある
参考リンク
- roadmap.sh — Computer Science
- GNU grep マニュアル
- RFC 1951 — DEFLATE Compressed Data Format Specification
- gzip 公式サイト
- MDN — String.prototype.indexOf
- MDN — 正規表現
- MDN — 剰余 (%)
- Node.js — Performance measurement APIs
- V8 公式ブログ
次に読む
この記事は 【深掘り】コンピュータ科学 の 16 / 25 本目です。
| 記事 | |
|---|---|
| ← 前の記事 | 再帰とメモ化 — メモを1行足したら一瞬で終わった |
| → 次の記事 | PとNP・NP完全 — 答え合わせは一瞬なのに解けない |
上から順に読めば積み上がるように並べています。 飛ばしても構いませんが、詰まったら前の回に戻ってください。
全体の順路は はじめに にあります。
roadmap.sh のどこをやっているか
- 一致した情報を次のずらしに使い回す
- ハフマン符号と接尾辞配列
この記事は、上の項目を実際に手を動かして確かめる回です。

コメント