LASSIC Media らしくメディア

Webサイトやシステムに載せる検索機能は、登録件数が増えるほど応答が重くなり、担当者を悩ませることがあります。データベースのLIKE検索や、文書を都度すべて読み込んで照合する素朴な仕組みのままでは、対象件数の増加にほぼ比例して処理時間が伸びていくためです。

この重さを解消する土台になっているのが、転置インデックスと呼ばれる索引の仕組みです。この記事では、システム開発の発注担当者やプロジェクトマネージャーに向けて、転置インデックスが検索を速くできる理由、日本語処理ならではの注意点、発注やレビューの場面で確認しておきたいポイントを整理します。実装の細部に立ち入るというより、開発会社との打ち合わせで会話できる粒度を意識してまとめました。

転置インデックスとは、単語から文書を逆引きする索引

転置インデックスとは、文書に含まれる単語ごとに「その単語がどの文書のどこに出現するか」の一覧を先に作っておき、検索語からすばやく該当文書を引ける索引（インデックス）です。

「インデックス」は、書籍の巻末に載っている索引のように、探したい語から該当ページを一気に絞り込む仕組みを指します。転置インデックスは、この索引の考え方を全文検索向けに広げたものと捉えると理解しやすいでしょう。書籍の索引が語ごとにページ番号を並べるのと同じように、転置インデックスは単語ごとに文書番号を並べる、と考えると対応関係がつかみやすくなります。

通常の索引が「文書には、どんな単語が含まれるか」という向きの対応を持つのに対し、転置インデックスは向きを逆にして「単語は、どの文書に含まれるか」という対応を持ちます。この向きの反転こそが、Wikipedia日本語版でも触れられている「転置（inverted）」という名前の由来です^*1。

こうした「先に整理しておき、あとから引く」という発想自体は、コンピュータが登場する以前から使われてきたものです。書籍の索引や電話帳がその代表例でしょう。転置インデックスは、この発想を大量の文書データに対してコンピュータ上で実現したもの、と捉えると位置づけが分かりやすくなります。

なお、「文書には、どんな単語が含まれるか」という向きの対応を持つ従来型の索引は、正引き索引と呼ばれることもあります。検索エンジン製品では、検索語から文書を絞り込む処理を転置インデックスが担い、絞り込んだ文書の内容を取り出す処理を別の仕組みが担う、という形で役割を分けて設計されているのが一般的です。

なぜ転置インデックスが必要か

検索のもっとも素朴なやり方は、問い合わせのたびに全文書を先頭から読み、目的の語が含まれているかを一件ずつ確かめる方法です。いわゆる総なめ検索（逐次走査）で、grepコマンドのように文書を順に照合していくイメージに近いものになります。

この方式は、文書数が少ないうちは大きな問題になりにくいものです。ところが対象が数万件・数十万件と積み上がるにつれて、1回の検索で読み込む量が件数に比例して膨らんでいきます。都度すべての文書へ目を通す発想のままでは、応答時間の伸びを避けにくいのです。

そこで採られるのが、検索が発生する前に「単語は、どの文書に出現するか」という対応表をあらかじめ作っておく発想です。Apache Luceneの公式ドキュメントでも、用語と文書の対応をあらかじめ持たせることで、問い合わせの処理を速くできると説明されています^*3。検索のたびに文書を読みに行くのではなく、事前に用意した対応表を引くだけで済むようにする——これが転置インデックスの基本的な発想です。

総なめ検索の負荷は、検索が実行される頻度が増えるほど重くのしかかります。1回あたりの走査時間がわずかでも、複数の利用者が同時に検索を実行する状況では負荷が積み重なり、他の処理の応答にも影響が及びかねません。あらかじめ対応表を用意しておく転置インデックスは、この積み重なりを避けるための工夫だといえるでしょう。

発注担当者にとってなじみのある例で言えば、データベースに張るインデックス（索引）と役割の発想は近いものです。会員IDのような特定の列にインデックスを張っておくと、その列を条件にした検索が速くなるのと同じように、転置インデックスは文章中の単語を対象にした検索を速くする仕組みだと考えると位置づけやすくなります。違いは、対象が単一の列の値ではなく、文章に含まれる無数の単語である点です。

検索が遅いと感じられると、利用者はページ内検索を使わずに離脱してしまうことがあります。ECサイトであれば目的の商品にたどり着けないまま離脱につながり、社内システムであれば必要な資料が見つからず、業務の手戻りが生まれかねません。検索の応答速度は、利用者の体験に直結する要素だといえるでしょう。

転置インデックスの仕組み

転置インデックスを作る手順は、大きく2段階に分かれます。文書群を単語（トークン）に分割する段階と、分割した単語ごとに、それを含む文書の一覧をまとめる段階です。下の図は、この変換の流れを示したものになります。

たとえば、次のような3件の文書があるとします。

• 文書1：在庫管理システムの開発
• 文書2：在庫管理と受発注システム
• 文書3：受発注システムの保守

これらを単語に分割すると、転置インデックスは次のような対応関係になるでしょう。

• 在庫管理 → 文書1・文書2
• 受発注 → 文書2・文書3
• システム → 文書1・文書2・文書3

「在庫管理」という語で検索すれば、文書を一件ずつ確かめずとも、この対応表から文書1と文書2だけをすぐに取り出せます。Elasticsearchの公式ドキュメントでも、転置インデックスは「文書に出現する一意な単語の一覧を持ち、単語ごとにそれを含む文書の一覧を対応させる構造」と説明されており^*2、この対応表を引くという発想こそが仕組みの核なのです。

転置インデックスが持つ情報は、単語と文書の対応だけではありません。Apache Luceneの公式ドキュメントでは、各単語について、それを含む文書の一覧とあわせて、文書内での出現回数も記録すると説明されています^*3。この出現回数は、検索結果をどの文書から先に並べるかという関連度の判断材料になるのです。

加えて、単語が文書内のどの位置に出現するかという情報まで保持しておけば、複数の単語が連続して出現する文書だけに絞り込む、フレーズ単位の検索にも対応できるようになります。単語と文書の対応だけでなく、頻度や位置まで踏み込んで設計されている点が、転置インデックスの奥行きといえるでしょう。実務では、これらの索引を作る処理を検索エンジン製品が自動で担い、文書が追加・更新されるたびに、索引全体ではなく差分だけを反映する仕組みを備えているものがほとんどです。

検索が実行されるときの内部の流れも、押さえておくと理解が深まるでしょう。まず、入力された検索語を文書と同じ方法で単語に分割します。次に、分割した単語ごとに転置インデックスを引き、それぞれの出現文書リストを取り出します。複数の単語をすべて含む文書を探す場合は、取り出した文書リストどうしの共通部分を求めることで、条件に合う文書だけへ絞り込むのです。この一連の処理が、文書を一件も読まずに完了する点こそ、総なめ検索との大きな違いになります。

具体例で確認してみましょう。先ほどの3件の文書に対して、「在庫管理」と「システム」の両方を含む文書を探すケースです。まず「在庫管理」の出現文書リスト（文書1・文書2）を取り出し、次に「システム」の出現文書リスト（文書1・文書2・文書3）を取り出します。この二つのリストの共通部分を求めると、両方の単語を含む文書1と文書2だけが残るのです。文書3が除外される理由も、対応表を突き合わせるだけで説明がつくでしょう。

この表からも分かるとおり、転置インデックスは検索を速くする一方で、事前の索引構築と更新の手間という代償を伴います。どちらを選ぶかは、検索対象の件数や更新頻度に応じて判断すべき事柄でしょう。

日本語処理ならではの難所

英語は単語の間に空白があるため、文をそのまま区切るだけで単語の境目を取り出せます。一方で日本語の文には単語間の空白がなく、どこで区切るかを機械的に判断する前処理が要ります。

この前処理でよく使われるのが、形態素解析（文を文法規則や辞書に基づいて単語単位に分ける処理）です。「在庫管理システム」という文字列を「在庫」「管理」「システム」のように分割し、それぞれを転置インデックスの見出し語として登録します。

形態素解析のほかに、文字列を決まった長さで機械的に区切るN-gram（文字列をN文字ずつの断片に分割する方式）という手法もあります。意味のまとまりを気にせず均一に区切るため、辞書に載っていない新語や固有名詞も拾いやすい一方、区切り方によっては検索結果に無関係な文書が混じりやすくなる面もあるのです。

どちらの方式にも一長一短があるため、対象データの性質や求める検索精度に応じて選ぶことになります。両方式を組み合わせて使う製品もあり、選定は開発会社との相談事項のひとつでしょう。

加えて、「サーバー」と「サーバー」、「WEB」と「Web」のような表記ゆれ、「PC」と「パソコン」のような同義語をどこまで同一の語として扱うかも、日本語処理では詰めておきたい論点です。ここを詰め切らないまま索引を作ると、検索語を少し変えただけで見つかるはずの文書が抜け落ちてしまう恐れがあります。

もう一つ押さえておきたいのが、「の」「は」「です」のように、ほぼすべての文書に出現し検索の絞り込みに役立たない語（除外語）の扱いです。こうした語をそのまま索引に含めると、対応する文書の一覧がふくらみ、索引の容量や検索の効率に影響します。除外する語の範囲は、対象データの性質に合わせて調整する必要があるでしょう。

運用が始まった後も、新しい商品名やサービス名などの固有名詞は次々に生まれます。形態素解析の辞書に登録されていない語は、分割のされ方が意図どおりにならないことがあるため、辞書を定期的に見直す運用体制も、日本語処理を採用する際にあわせて検討しておきたい点です。

どこで使われているか

転置インデックスは、特定の一社が抱え込む技術ではなく、全文検索の分野で広く採用されてきた基礎技術です。代表的な採用例を挙げます。

• Elasticsearch・OpenSearchなどの検索エンジン製品 — 内部でApache Luceneを用い、転置インデックスによって文書を管理します^*3。
• ECサイトやコーポレートサイトのサイト内検索 — 商品名やページ内の語句から該当ページを絞り込む処理に使われる仕組みです。
• アプリケーションやサーバーのログ検索 — 大量のログ行から特定のキーワードを含む行を短時間で見つけ出す目的で使われているのです。

これらの検索エンジン製品をどう選び、どう設計するかという話題は論点が広く、この記事の範囲を超えるため、別の機会に扱う領域とします。ここでは、転置インデックスという仕組みが土台にあるという位置づけを押さえておけば十分でしょう。

検索エンジン製品には、オープンソースとして公開されているものや、商用サポートが付いたものがあり、料金体系や運用サポートの範囲は製品によって異なります。導入検討では、検索の性能だけでなく、サポート体制やライセンス条件も含めて比較する視点が求められるでしょう。

発注担当者にとって重要なのは、これらの基盤を導入する際、転置インデックスという仕組みが前提になっているという理解です。検索エンジン製品の提案書やカタログに「転置インデックスを採用」と書かれていれば、それは総なめ検索ではなく、事前に対応表を作る方式を指していると読み替えられます。

身近な例では、社内のドキュメント管理システムやFAQサイトの検索窓、問い合わせ履歴を横断して探すサポートツールなども、内部では同じ仕組みを採用している場合があります。登録件数が増えても検索が遅くならないシステムを見かけたときは、その裏側に転置インデックスが働いている、と考えてよいでしょう。

発注・レビューでおさえる点

転置インデックスの仕組みそのものは、Elasticsearchなどの製品が内部で担ってくれます。発注担当者やプロジェクトマネージャーが押さえておきたいのは、実装の細部よりも、要件と設計判断の勘所です。

契約や仕様書のなかで「転置インデックス」という言葉が明示されていなくても、全文検索や高度な検索機能という要件があれば、実質的に同じ論点が持ち上がります。次に挙げる観点は、そうした場面で開発会社と認識を合わせるための切り口になるでしょう。

対象データ量と更新頻度

検索対象のデータが数千件規模なのか、日々大量に追加される規模なのかによって、必要な構成やインデックスの再構築にかかる負荷は変わってきます。更新が頻繁なデータほど、索引への反映タイミングと反映までの遅延を確認しておくことが欠かせません。将来的なデータ増加も見込んで、余裕を持った構成を検討しておくとよいでしょう。

日本語処理の方式

形態素解析かN-gramか、どちらの方式を採るかによって検索の精度や検索できる語の範囲が変わります。表記ゆれや同義語をどこまで吸収するかも、要件定義の段階で開発会社とすり合わせておきたい点でしょう。対象データに専門用語や社内特有の呼び方が多い場合は、辞書への語句追加が可能かどうかも確認材料になります。

あいまい検索の要否

誤字や部分一致まで許容する検索を求めるのか、正確な一致に近い検索で足りるのかによって、必要な機能や設計の複雑さは変わります。要件を絞り込まないまま進めると、公開後の作り直しを招きかねないのです。利用者がどのような語で検索しそうかを、業務の現場に近い担当者へヒアリングしておくと、要件の精度を高めやすくなります。

既存データベースとの連携

転置インデックスは、既存のデータベースとは別に用意される検索専用の仕組みになる場合がほとんどです。データベース側でレコードが更新されたとき、その変更を検索側の索引へどう反映させるかという連携方法も、設計段階で決めておく事柄になります。反映の間隔が長すぎると、更新したはずの情報が検索結果に出てこない、という食い違いが生じるのです。バッチ処理でまとめて反映する方式と、更新のたびに逐次反映する方式とでは、システム構成の複雑さも変わってきます。どちらを採るかは、検索結果への反映が遅れてもよい範囲を、業務上どこまで許容できるかで判断する事柄でしょう。

契約・体制で確認する点

検索基盤の設計や日本語処理の調整には、専門的な知識を持つ技術者が要ります。要件定義から設計、実装、公開後の調整までをどの体制で担うのかを契約前に確認しておくと、公開後に生じる細かな調整依頼にも対応しやすくなるでしょう。とくに公開後の辞書調整や索引の見直しは、開発フェーズが終わった後にも発生しやすい作業です。保守契約の範囲にこれらの調整が含まれているかどうかも、契約時に確認しておきたい点になります。

日本語処理の方式を決めないまま開発を進めると、公開後に「検索語を少し変えると結果が出ない」といった問い合わせが増え、索引設計の見直しに追加の工数がかかることがあります。形態素解析の辞書調整や索引構築の設計には専門的な知識が求められるため、要件段階から検索基盤に詳しい担当者を交えて検討する進め方が、後々の手戻りを抑えることにつながるでしょう。

受け入れテストで確認する点

公開前のレビューでは、実際に使われそうな検索語を複数用意し、想定どおりの文書が返るかを確認しておくことが大切です。表記ゆれを含む語、部分的にしか一致しない語、専門用語や固有名詞など、性質の異なる検索語を組み合わせてテストすると、日本語処理の設定が要件どおりかを見極めやすくなります。あわせて、データを追加してから検索結果に反映されるまでの時間も、実際の運用を想定して確かめておきたい項目です。辞書を調整したときや索引の設定を見直したときは、同じ検索語の一覧であらためて確認し、以前は返っていた文書が抜け落ちていないかを見るとよいでしょう。

まとめ

• 転置インデックスとは、単語ごとに出現文書の一覧をあらかじめ作っておき、検索語から該当文書を引ける索引である。
• 全文書を都度読み込む総なめ検索と違い、対応表を引くだけで済むため、文書数が増えても応答が伸びにくい。
• 文書を単語に分割し、単語ごとの出現文書リストをまとめる、という2段階で索引が作られる。
• 日本語は単語間の空白がないため、形態素解析やN-gramによる前処理と、表記ゆれ・同義語の扱いが論点になる。
• 発注時は対象データ量・更新頻度・日本語処理の方式・あいまい検索の要否を確認しておくことが大切だ。
• 検索エンジン製品の選定や日本語処理方式の判断は、実装の細部よりも要件整理の質が結果を左右する。

よくある質問

テレリモ総研編集部　鈴木 亮佑

著者：テレリモ総研編集部　鈴木 亮佑

ご不明な点はお問い合わせフォームからもご連絡いただけます。

出典

• Wikipedia日本語版「転置インデックス」
• Elastic「Inverted index」（Elasticsearch: The Definitive Guide）
• Apache Lucene公式ドキュメント「Index File Formats」

Tweet