SSG向け日本語対応の全文検索エンジンを作りました(1) - 日本語で検索したい！

• 第一回 日本語で検索したい！(今回)
• 第二回 英語でももちろん検索したい！
• 第三回 打ち間違いしても検索したい！
• 第四回 WebGPUで検索したい！
• 第五回 使いやすい検索にしたい！

この文章では、どういう理由で、どうやって全文検索エンジンを作るに至ったかを適当に書き散らします。また、検索エンジンの構成のひとつについても説明します。タイトルのブツについては、ドキュメントをウェブサイトで公開しています。是非ご覧ください。なんとサイトは日本語未対応ですが...
https://staticseek.lulliecat.com/

はじめに - 全文検索エンジンが欲しい！

みなさん、ウェブサイト運営していますか？ぼくは必要にかられてはじめました。最初はWordPressでしぶしぶ始めたのですが、インターネットの悪いおたくにそそのかれ、自分でいちからウェブサイトを作り直しました。はじめてみるとこれがなかなか技術的に楽しく、完全に本末転倒になりながらもちまちま構築を続けているところです。

インターネットの悪いおたくはセキュリティ意識が高いので、WordPressでもSymply Staticというプラグインを使ってHTMLファイルに変換してからサーバーにアップロードすることで運営していました。自分でサイト構築しはじめた後もSSG(静的サイトジェネレーター)を使って、サーバー側の実装なしにサイト運営をしています。

その目的では、Cloudflare Pagesが無料のわりにめっちゃ便利で使いまくっています。GitHubのレポジトリとCloudflareを連携させておくと、レポジトリにSSGを使ったプロジェクトをpushするだけで、GitHub Actionsなどの設定なしに勝手にnpm installとnpm run buildがCloudflare側で実行され、生成されたHTMLファイル群がすべてCloudflareのエッジサーバーに公開されます。しかも、mainブランチは本番用、ほかのブランチは試験用として両方とも違うURLで公開させることができ、本番サイトの公開前に試験サイトを確認することができます。べんりすぎる...これで全世界でちょっぱやアクセスが無料で実現できる...https対応だし、もう全人類これでいいんじゃないかな...

SSGはAstroを使っています。作成対象のウェブサイトはブログのあるブランドサイトで、SPA(シングルページアプリケーション)ではないので、Markdownコンテンツ中心の爆速プラットフォームであるAstroを使いました。Astroは裏でViteが使われており、爆速更新爆速デプロイが快適すぎる最高環境です。ReactとかVueとかなんも知らないマンだったのですが、HTMLとCSSの知識があればふつうになんとなくウェブサイト構築ができます。初心者にも優しいので興味がありましたら是非使ってみてください。

Astroはアイランドアーキテクチャというものを採用しています。アイランドアーキテクチャ下では、ウェブサイト上のコンポーネントはアイランドと呼ばれ、アイランドごとにReactとかVueとかSvelteとか好きなフレームワークを使ってアイランドを実装できます。だいたいふつうのHTMLでいいんだけど、この領域だけReactコンポーネントつかいたいなー、あーでもここはVueのいいコンポーネントが使いどころだよなー、みたいなのが混在できるようで、まぁ便利な気がします。

とはいえ、ぼくはReactなどは使っていません。理由はちょっと込み入っているのですが、AstroではReactなどのコンポーネントを使うと、HTML内にsytle要素とscript要素が少しだけ挿入されます。コンテンツセキュリティポリシー(CSP)を使ってウェブサイトのセキュリティをさらに高めようとした場合、インラインスクリプトやインラインスタイルは無効化すべきのようです。Reactを使うとどうしてもインラインでスクリプトが少しだけ展開されるため、今のサイトではReactコンポーネントなどは採用しないことにしました。

ちなみに、Astroのデフォルトの設定だとMarkdown内のシンタックスハイライトにShikiが使われます。ShikiはHTMLタグのstyle属性に直接スタイルを適用します。CSPでstyle-src self指定だけしていると、このインラインスタイルが無効化されてデザインが崩れます。そのため、Shikiに代わりPrismを使い、CSSをHTMLファイルからlinkさせることでCSP対応をしました。あと、インラインスタイルシートをneverにしています。一方スクリプトは何もしなくても全部分離されるようです。詳細はまた今度...

Reactなどが使えないとすると、クライアント側だけで実現するリアクティブな要素はどう実装するんじゃ、とかなりますが、それは素のJavaScriptを使います。辛すぎる...TypeScriptは使えるし、ライブラリはインポートできるのでなんとなかりますが、JSXなどがないのでDOM操作が本当にしんどい...

そんな縛りがある中で、基本的にリアクティブな要素もほぼHTMLとCSSで実現しました。これがやってみると結構できるものです。チェックボックスやラジオボタンなどのinput要素にstateを保存する、という裏技みたいのとCSSの複雑なセレクタを活用すると、ハンバーガーボタンで開くメニューとかドロワーとかポップアップとかアニメーションとかは結構実装できてしまいます。この裏技についてもまた今度...

とはいえ、物事には限界があります。そろそろHTMLとCSSだけだと実装できることもほとんどなくなってきたなー、となり、次は流石にJavaScript利用かな、となりました。

ぼくの作るサイトは基本ブランドサイトなのですが、ブログも併設するため、見た目的に検索窓があると嬉しそうだなぁ、となりました。自分がほかの人のサイトを訪れた時にはほぼ使わない機能なので、本当に必要なのそれ？となりますが、完全に技術目的です。また、将来商品をウェブサイトに載せたら検索があると便利かもな、とは思いました。

日本語対応の全文検索エンジンがほとんどない！

前座なのに明らかに話が長くなりました。ようやく本題です。ちなみに以下の話題に関して、ラムダノートさんから検索システム ― 実務者のための開発改善ガイドブックという本が出版されており、とても役に立つので、興味のある人は読んでおくとよいと思います。

で、既存の全文検索エンジン、しかもサーバー側の実装の必要がないやつ、というのを探したのですが、これがまた苦労しました。全文検索エンジン自体はいくつもあるのですが、どれも英語など対応で、日本語に対応したものはかなり少なかったのです。

なぜ全文検索エンジンは日本語対応しているものが少ないのでしょうか？そのいちばんの理由は、日本語は分かち書きが難しいからです。英語などのよーーーーーーろぴあんな言語は空白で単語が区切られるため、文章の中に存在する単語を抜粋するのはとても簡単です。一方、日本語や中国語、韓国語、その他いくつかの言語は、句読点のようなものは存在すれど、単語同士は明白な空白で区切られていません。そのため、機械的に単語を抜粋することはできず、MeCabのような形態素解析エンジンを使わねばなりません。形態素解析エンジンにはファイルサイズの大きい辞書が必要なため、なかなかポータブルな実装をすることができません。それがいちばんのネックになるようです。

ところで、そもそもなんで検索機能に分かち書きが関係あるのでしょうか？それは、検索のためのインデックスの構造に関係します。

みなさんは、全文検索をしようと考えたときに、どんなアルゴリズムを考えるでしょうか？一番簡実装は、JavaScriptでいうString.prototype.indexOf()を使う実装です。線形探索（リニアサーチ）と呼びます。この関数は（実際の実装は物凄く最適化されているはずですが）文字列の先頭から順次文字列を比較し、マッチする文字列の位置を戻り値として返します。いわゆる素朴なアルゴリズムです。素朴ですが、存在する文字列は確実に列挙することができるため、もっとも確実なアルゴリズムでもあります。

しかし、このアルゴリズムには欠点があります。想像できる方も多いと思いますが、計算量がとても大きく、文章サイズに比例して検索時間がかかることです。文章の長さをNとすると、たぶんO(N)とかそうなると思います（エアプです、素朴すぎるアルゴリズムならキーワード長Mとの積でO(NM)かも）。短い文章の一致を検索するだけならば最適なアルゴリズムですが、たとえばブログサイトなどで文章量がとても多くなると、検索に時間がかかりすぎてしまいます。ブラウザで動くJavaScriptは基本的にシングルスレッドで動くため、検索に時間がかかるとその間ブラウザの操作ができなくなり、快適なブラウジングを妨げます。ちなみに、UI視点ですと、数十ミリ秒以上の時間操作ができなくなると、「あれ、なんか重いな」とユーザーに気づかれます。そのくらいの時間が閾値です。

この問題を解決するために導入されたのが、転置インデックスというデータ構造です。データ構造というか、辞書の索引です。このアルゴリズムのポイントは、辞書の索引を前もって時間をかけて作ることで、検索の時はすばやく索引をひくだけで検索を実行できることです。

転置インデックスは「単語、及び、その単語が含まれる文章idのリスト」の配列です。単語のことを「ターム」と呼び、文章idのリストのことを「ポスティングリスト」と呼びます。転置インデックスは以下の3ステップで作成します。

1. 1つの文章に文章idを割り当て、文章を分かち書きして、タームのリストにする
2. 文章中の全ての単語に対し、(ターム, ポスティングリスト)というタプルを作り、このタプルを転置インデックスに追加する。既に索引に単語が登録されている場合は、ポスティングリストに文章idを追加する
3. これを全文章分実行する

検索単語が与えられたときに検索を実行するには、転置インデックスを眺めて、該当するタームをみつけだし、その単語に紐づけられているポスティングリストを結果として返します。転置インデックスは、たとえばハッシュなどで作成します。そうすると、検索時間は文章のサイズに依存せずO(1)で実現できます。

このアルゴリズムで注目すべきはステップ1です。そう、分かち書きが必要なのです。英語などは空白で文字列を分割すれば分かち書きが簡単にできるため、転置インデックスは簡単に作れます。一方、日本語などは分かち書きが難しいため、なかなか簡単な分かち書きの手法がありません。ここが日本語対応の検索エンジンを作る際のネックになります。

たとえば、日本語でもインデックスを作るときに大きい分かち書き辞書を使って単語に分割し索引を作れたとします。しかし、検索を実行するためには、検索文字列も同じ分かち書きアルゴリズムを用いて分かち書きをせねばなりません。索引作成時と検索実行時にそれぞれ違うアルゴリズムの分かち書きを採用すると、単語の分かれ目が一致せず、検索ミス（false negative）につながります。そのため、日本語の検索には、大きな分かち書き辞書を持つプログラムをサーバー側で動かし、クライアント側からのリクエストに応じて分かち書きと転置インデックス引きを実行し、クライアントに返す、という実装が必要になります。クライアント側で完結させるのは難しいのです。

ちなみに、英語などでは実際はその他にも単語の正規化をしてよりヒット率を上げる工夫をします。ステミングと呼ばれています。他にも「a」や「the」などのよくある意味のない単語（ストップワード）を取り除く処理もします。

ないなら作るか！がはは！n-gram転置インデックス！

日本語に対応する全文検索エンジンが見つからなかったため、自分で作ることにしたのですが、アルゴリズムのアテはありました。単語の分かれ目を推測した分かち書きが無理ならば、機械的に2文字ずつ、3文字ずつなどと決め打ちして文字を区切ればいいのです。この手法を文字n-gramと呼びます。分かち書きができない場合の定番手法のようです。定番手法なのですが、よーーーーーーろぴあんな皆さんは空白による単語分割で満足しきっているため、n-gramを使う全文検索エンジンがほとんどないようです。かなり探したのですが...許せん...

bigram転置インデックスの作成方法

文字n-gram転置インデックスの作成及び、それを用いた検索の実際の手順を説明します。まず転置インデックスの作り方です。これは分かち書きに文字n-gramを使うだけで、先ほど説明した手順とまったく同じになります。ただ、n-gramを作る際に一つ注意点があります。例えば2-gram(bigram、2文字単位で文章を区切る)で文章を区切る場合、2文字で区切るウィンドウを1文字ずつスライドさせるようにbigramを作ります。

ちょっとわかりにくいので実例を出します。例えば、

"東京都渋谷区"

という文章があった場合、これをbigram転置インデックスにするには、

["東京", "京都", "都渋", "渋谷", "谷区"]

というように、1文字ずつ重複させながらタームのリストを作ります。

何故このようなことをするのでしょうか？それは、重複させないと、検索においてfalse negative(偽陰性、実際には検索文字列が文章中に存在するのに、検索にひっかかってくれない)が生じてしまうからです。

もし、文字を重複させずbigram転置インデックスを作ると、以下のようなタームのリストになります。

["東京", "都渋", "谷区"]

さて、元の文章の中に"渋谷"という検索文字列は存在するでしょうか？存在しますよね。でも、タームのリストには"渋谷"は存在しないため、「この文章中には"渋谷"は存在しない」という結果を出してしまいます。これがfalse negativeが生じる原因です。1文字ずつ重複させながらタームを作った場合は、"渋谷"という文字列がタームとして抽出されるため、正しく検索ができています。このような理由から、ウィンドウをスライドさせるような手法でタームのリストを文章から抽出します。これにより、false negativeを取り除くことができます。

ちょっと脇道にそれます。上の文章に「京都」は存在するでしょうか？しますね。では、それは求めた結果でしょうか？たぶん、検索文字列として「京都」を指定した人にとって、東京都の文章がひっかかるのはイマイチ目的にあってない場合が多いと思います。完全に正しい分かち書きができる場合ならば、おそらく、以下のようなタームのリストになり、「京都」がひっかかることはないでしょう。

["東京", "都", "渋谷", "区"]

これは、本来の検索目的からするとfalse positive(擬陽性、ひっかかってほしくない文章まで検索にひっかかる)になります。なるのですが、このfalse positiveは線形探索でも生じ、分かち書きができない現在の環境だと解決する手法が簡単にはありません。そのため、このfalse positiveは受け入れることにします。

bigram転置インデックスを使った検索方法

検索は、検索文字列をbigramにしてbigram転置インデックスをひくだけです。ここでは、基本的な手法に基づく場合、インデックス作成時のような文字の重複はさせなくても大丈夫です。たとえば、検索文字列も"東京都渋谷区"だったとします。このとき、検索文字列は以下のタームに分割されます。

["東京", "都渋", "谷区"]

これらは全て先ほど作ったbigram転置インデックスに含まれますね。あとは、これらのタームが全て含まれる文章idを見つけ出せば検索終了です。具体的には、各タームに紐づけられたポスティングリストの共通部分(インターセクション)をとれば検索終了です。

ちなみに、bigram転置インデックスで、検索文字列長が奇数の場合は、最後だけ1文字重複させます。"東京都"を調べるときは、["東京", "京都"]にします。他の長さのn-gramでも、検索文字列長がnの倍数ではない場合は、最後は同様に重複させます。

検索文字列長が文字n-gramのnより短い場合

細かい話をします。文字bigramインデックスのもとで、例えば"都"という1文字を検索したい場合はどうすればいいのでしょうか？文字bigramインデックスには1文字のタームは存在せず、インデックスをハッシュで実装した場合は検索することができません。このままでは、false negativeが発生します。検索できるようにするには、以下のどちらかの手法をとる必要があります。

1. m-gram(m < n)を全て転置インデックスに加える
2. インデックスのタームの先頭1文字を全検索して一致するポスティングリストを抜粋する

1を用いた場合は、インデックスの実装はハッシュのままで使えます。その代わり、インデックスサイズが相当膨れそうです。検索文字列長が1文字というコーナーケースを埋めるためだけにしてはすこし大げさな気がしています。

2は、結局全探索になるので、そのままでは処理が重そうです。が、インデックスをタームで事前にソートしておき、少し手を加えた二分探索を実装することで、比較的軽量に実装することができそうと気づきました。二分探索にどのように手を加えたかはソースコードを読み解いてください（おさぼり）

これらは、実際にサイズがどの程度ふくれて検索時間がどの程度になるか確認することでバランスをみてどちらを使うかを判断することにしました。

ちなみに、さらに細かい話をしますと、2を用いた場合でも、"区"だけは検索ができません。"区"が先頭に現れるタームが存在しないからです。そこで、文章の最後だけはnより小さいm-gramも追加で含めることにしました。

["東京", "京都", "都渋", "渋谷", "谷区", "区"]

それでも生じるfalse positive

これまでのアルゴリズムでfalse negativeはある程度取り除けました。しかし、false positiveはまだ生じます。生じる原因は、このインデックス構造によります。この構造では、ターム単体がある文章に属しているかはわかるのですが、あるターム同士が連続して文章に存在しているかはわからないのです。そのため、例えば"東京都"を検索したいときに、離れた位置に存在する"東京"と"京都"というふたつのタームが存在すれば、その文章は検索にヒットしてしまいます。たまたま、n-gramによる分割がちょうど別の意味にとれる単語になる場合によく生じます。これは現状のインデックスでは構造上致し方ないfalse positiveです。

一方で、n-gramのnが大きくなればなるほど、この問題は減るだろう、という目星はつきます。長ければ長いほど、文字間がつながっているという情報が増えるからです。実際にnをいくつまで増やせばfalse positiveが許容範囲内になるかは、実際のデータを使って確認することにしました。

さらにfalse positiveを減らす手法も追加で考えました。検索文字列も転置インデックスを作る時のように文字を重複させながら検索タームを生成します。例えば、3-gram(trigram)で"東京都渋谷区"を検索する場合、従来の方法では以下のふたつのタームがインデックスに存在するかを確かめるだけでした。

["東京都", "渋谷区"]

この場合、"東京都"、と"渋谷区"が連続しているかどうかの情報は失われており、false positiveにつながります。そこで、文字を重複させながら、以下のようなタームが全て存在することを検索条件とすることにしました。

["東京都", "京都渋", "都渋谷", "渋谷区"]

普通の文章の中では"京都渋"という単語や"都渋谷"という単語はまず出てきませんよね。それを利用し、このような一見意味が通じないタームが存在することを根拠として、"東京都"と"渋谷区"が連続して文章内に存在することを確認できるだろう、と目星をつけました。

bigram転置インデックス生成関数の作成とベンチマーク

アルゴリズムの方針は定まってきたので、具体的にnをいくつにするか、および、検索文字列がnより短い場合のふたつのアルゴリズム案で性能やインデックスサイズは満足できるか、これらを実際のデータを用いて比較することにしました。実装にとりかかります。

特に使えるライブラリはなさそうで、一からの作成になるため、慎重に足元をみながら少しずつ実装しました。まずリファレンス実装として、String.prototype.indexOf()を用いた線形探索による検索を実装し、目視で検索が正しく動くことを確認しました。次に、文字n-gramを用いた転置インデックスを実装し、その検索結果と線形探索の検索結果を比較してfalse positiveとfalse negativeを抜粋できるようにしました。また、インデックサイズと、gzipしたインデックスサイズ、およびインデックス作成時間と検索時間を計測できる関数を作りました。ベンチマーク実行スクリプトをブラウザ上で実行するようにindex.html内でコメントアウトして、npm run devしブラウザを開けば実行結果が得られます。

以下、実行結果です。手法のカッコ内の数字は、(1)がm-gram(m < n)を全て転置インデックスに加える場合で、(2)がインデックスのタームの先頭1文字を二分探索して一致するポスティングリストを抜粋する場合です。データセットは日本語のWikipediaの記事抜粋で、文章総サイズは3,020kbyte、検索実行回数は1,033回です。表の「サイズ」はインデックスサイズを指し、「検索時間」は、1,033回の検索時間の合計です。

手法	作成時間	サイズ	gzipサイズ	検索時間	一致	擬陽性	偽陰性
線形探索	18ms	2,988kbyte	1,051kbyte	224ms
2-gram(1)	600ms	6,677kbyte	1,052kbyte	7.3ms	15,435	6,396	2
3-gram(1)	1150ms	16,888kbyte	2,563kbyte	3.8ms	15,435	182	2
4-gram(1)	1400ms	30,309kbyte	4,228kbyte	3ms	15,435	9	2
2-gram(2)	370ms	6,067kbyte	900kbyte	18.3ms	15,435	6,396	2
3-gram(2)	610ms	11,875kbyte	1,997kbyte	10.5ms	15,435	182	2
4-gram(2)	930ms	16,607kbyte	3,040kbyte	9.2ms	15,435	9	3

1,033回の検索に対して一致が15,435もあるのは、1つの検索文字列に対して複数個所のマッチがあるからです。

1. 検索性能は線形探索にくらべ10-100倍程度はやい
2. 偽陰性はこのデータセットではほとんどない
3. 擬陽性は4-gram以上はサチりそう
4. (2)の二分探索でも性能は満足できそう
5. gzipすると、(1)と(2)のインデックスサイズは思ったより差がない
6. インデックスサイズはnに比例気味かそれより上振れしている

まとめるとこれくらいでしょうか。nは増やすとしたら4まで、一方でインデックスサイズはnの増加で倍増していくため、擬陽性を我慢できるのであれば2-gramにしたいですね。クライアント側での全文検索を考えているので、ネットワーク越しのデータ転送はできるだけ控えたいと考えています。そのため、(2)の方を選びたいところです。

ただ、3に関しては私のデータセットの選び方に問題がある可能性が高いとも思っています。検索キーワード長自体が長いデータが少ないからです。なので、ここは眉唾でみておいてください。

おわりに

本当は記事一本で終わらせるつもりだったのですが、長くなってしまったので分割することにしました。あいまい検索対応、WebGPUの利用など、いくつかトピックがあります。前処理やクエリのパース、検索結果のスコアリングなども重要な要素なのですが、それについては話すかまだ未定です。

そして、実はこの時点でこの表からもう一つわかることがあるのです。なかなか重要なことなのですが、ぼくはもっともっと先の本番の実装をするまで気づきませんでした。さて、なんでしょうか？正解は、次回以降の記事で発表します！（ゲス顔で）