ワイルドカードは、クエリの中に含めることができる特殊な文字です。ワイルドカードを使用することで、特定のタームのバリエーションを検索できます。ワイルドカードを使えば、短い文字列で、スペルが似た語を効率よく検索して、データベース内でマッチするタームを多数見つけることができます。MarkLogicの検索では、次の2つのワイルドカード文字がサポートされています。

* 空白を除く、0個以上の文字にマッチします。例えば、car*は、carcarecaring(およびcarで始まる他のすべてのターム)にマッチします。
? 空白を除く、1つの文字のみにマッチします。例えば、car?は、careおよびcartにマッチしますが、carcaringにはマッチしません。

ワイルドカードは、検索タームの先頭、途中、または末尾で使用でき、それらを組み合わせることもできます(例:*e*?her?*)。

ワイルドカード検索に似た機能として、ステミング(語幹処理)があります。これは、MarkLogicでクエリを処理するときに、文法的に似た語を自動的に考慮する機能です。ステミングがオンのとき、MarkLogicでswimを検索すると、swamおよびswimmingも考慮されます。詳細については、『Search Developer’s Guide』の「ステミング検索の概要と使い方」のセクションを参照してください。

MarkLogicでは、次の3タイプのインデックスを使用したワイルドカード検索がサポートされています。

  1. three-character indexes(3文字以上の連続する非ワイルドカード文字を含む検索パターン)
  2. trailing wildcard indexes(末尾にワイルドカードがある検索パターン)
  3. レキシコン(語彙集)

これらのインデックスがいつどのように使用されるかは、検索するワイルドカードのパターンによって変わります。

Three-Character Indexes

インデックスは、MarkLogicの通常検索において重要であるだけでなく、ワイルドカードの処理においても重要な役割を果たします。インデックスは、データベースドキュメント内の文字シーケンスを取得して、それらをドキュメントIDにマッピングしたものです。MarkLogicによる一般的な検索では、クエリを分析して複雑なクエリを構成要素に分解してから、インデックスを参照してマッチする結果のリストを返しています。デフォルトでは、データベース内のすべての語と、要素名および属性名(XMLドキュメントの場合)やプロパティ名(JSONドキュメントの場合)などの構造情報に対してインデックスが付けられます。ワイルドカードなどの特定の機能をサポートするために、追加のシーケンスに対してMarkLogicにインデックスを付けさせることができます。

データベースでthree-character indexをオンにすると、MarkLogicによってすべての一意の3文字シーケンスが、対応するドキュメントにマッピングされます。例えば、caterというタームがドキュメント内にある場合は、catate、およびterのエントリがインデックスに追加されます。また、各シーケンスが語の最初にあったのか最後にあったのかを示すコンテキスト情報も含められます。three-character indexは、*ateate**ate*などの、3つの文字と*を含んだワイルドカード検索を処理するのに最適です。MarkLogicは、結果に必要なすべてのドキュメントIDをこのインデックスから取得できます。

また、MarkLogicでは、three-character indexを活用してより長いワイルドカードタームを処理できます。*ater*のような4文字のタームは、*ate**ter*に分割し、この2つのタームをthree-character indexで検索して、その結果の共通部分を取ることができます。ただし、これには不適切な結果が含まれている可能性があります。例えば、terminateが誤ってマッチとして判定されるので、この語を含んだドキュメントが結果に含まれる可能性があります。

このような不適切な結果は、検索のフィルタリングの段階で削除します。フィルタリングでは、結果のドキュメントを開いて、それらのドキュメントが検索クエリに実際にマッチすることを再確認します。MarkLogicで実行されるフィルタリングが増えると、結果を返すまでにかかる時間が長くなります。したがって、フィルタリングに時間がかかる可能性がある長いワイルドカードタームをthree-character indexで処理するのは、必ずしも得策ではありません。(フィルタリングはオフにできます。これによって結果をより速く取得できますが、不適切な結果が含まれている可能性があります。)

MarkLogicには、データベースの1文字インデックスおよび2文字インデックスをオンにするオプションもあります。より短いタームに対するワイルドカードの結果(例:b*ba*)を取得するのに役立つように思えるかもしれませんが、これらのインデックスをオンにすると、インデックスが非常に大きくなるので、ドキュメントの読み込み、インデックス付け、およびマージにかかる時間に悪影響を及ぼします。したがって、これらのインデックスはアクティブにしないことを推奨しており、以降の説明では、これらはオンになっていないものと仮定しています。

4文字以上のシーケンスに対するインデックスはどうなっているのでしょうか。MarkLogicでは、それらのインデックスは提供されていません。これは、多くの場合、それによって得られるメリットよりも、インデックススペースが増大するデメリットのほうが大きいからです。一般的に、労力に対する成果が最も大きいのがthree-character indexesで、これによってワイルドカードおよび検索全般を効率的にサポートできます。

Trailing Wildcard Index

4つ以上の文字と末尾の*からなるワイルドカード検索をすばやく処理できるように、trailing wildcard indexをオンにすることができます。このインデックスでは、3文字以上のそれぞれの語に対して、プレフィックスのすべての可能な組み合わせがエントリとして保存されます。例えば、caterに対して、catcate、およびcaterがインデックスに保存されます。このインデックスには、シーケンスが語の先頭に存在していたことを示すコンテキスト情報が含められます。cate*を検索すると、MarkLogicでtrailing wildcard indexが使用されます。

Trailing wildcard indexは、タームの先頭に*が付いている場合(例:*ater)には役立ちません。また、MarkLogicでは、trailing wildcard indexの逆バージョンである先頭ワイルドカードインデックスは提供されていません(つまり、MarkLogicはこの点で英語寄りの仕様になっています)。英語のタームを検索するときには、ワイルドカードを先頭に付けるよりも、末尾に付けるほうが多くなります。これは、英文法ではプレフィックスよりもポストフィックスのほうが多く使用されるからで、trailing wildcard indexを採用しているのはこのためです

shows how MarkLogic stores sequences from the word cater with a three-character index versus a trailing wildcard index

図1:インデックスによって、ドキュメントに存在する文字シーケンスが、対応するドキュメントIDにマッピングされます。この図は、MarkLogicで複数のインデックスがオンになっている場合に、caterという語からシーケンスが保存される様子を示しています。

レキシコン

MarkLogicでは、three-character文字列やtrailing wildcardよりも複雑な形のワイルドカード検索に対して、レキシコンの使用が試みられます。レキシコンは、データベース内の一意の語を列挙した順序付きリストです。インデックスとは異なり、レキシコンでは、語をその出現元のドキュメントにマッピングしていません。これは単なる大きな順序付きリストです。

MarkLogicはレキシコンを使用することで、ワイルドカードパターンにマッチする可能性があるすべてのものをすばやく取得できます。例えば、r?b*?tというワイルドカード文字列を検索するとします。MarkLogicは、この文字列を取得して、レキシコンの語のリストと比較できます。レキシコンの語は順番に保存されているので、MarkLogicはそれらを効率的にスキャンできます(これについては後で詳しく説明します)。

このr?b*?tの例では、レキシコンのスキャンによってrabbitrebuilt、およびrobotというタームが返される可能性があります。MarkLogicはこの情報に基づいて、ワイルドカードクエリを次のように書き換えることができます。

rabbit OR rebuilt OR robot

その後、インデックスでこの3つの語の出現を検索し、見つかったものを1つの結果としてまとめることができます。

また、レキシコンでは検索ボックスでの入力候補表示もサポートされます。ユーザーが検索ボックスに「vac」と入力すると、アプリケーションがレキシコンを確認して、vacationvacuumなどのマッチする語を列挙したメニューを表示できます。これはvac*を検索するのに似ていますが、インデックスを確認する必要がありません。

レキシコンの制限

レキシコンを使用して、ORで連結されたクエリに展開する方法は、いつもうまくいくとは限りません。ワイルドカード文字列に対してレキシコンから何千ものマッチするタームが返される場合は、数が多すぎて効果的なORクエリになりません。

これに対処するために、3文字のプレフィックスおよびポストフィックスからなる短いリストを作成することで、返された大量のタームのリストを切り詰めることができます。

例えば、レキシコンの結果リストが次のようになったとします。

  • staggered
  • staired
  • stammered
  • stared
  • starred

プレフィックス–とポストフィックスの方法を使用すれば、このリストを次のように書き換えて、より短く管理しやすいものにすることができます。

  • sta*
  • *red

その後、これらの3文字シーケンスを使用して、高速に処理されるthree-character indexesを利用できます。これには不適切な結果が含まれている可能性があり、フィルタリングが必要になりますが、レキシコンをスキャンして返される語が多すぎる場合は、こちらのほうがよい方法になります。

MarkLogicは、a*のような単一の文字と末尾のワイルドカードからなるクエリに対して、さらに別の方法を使用します。MarkLogicは、これを次の3つの別個の検索に分割します。

  • 通常の語インデックスを使用して、aを検索します(aのインデックスエントリは存在しても1つのみです)
  • レキシコンでa?を検索してから(返される結果は少数にとどまります)、それらをORで連結して展開したクエリを実行します
  • レキシコンで、プレフィックスとポストフィックスの方法を使用して、a??*を検索します(aで始まるマッチした語をリストに大量に列挙するのを避けています)

ワイルドカード検索のオプション

開発者は、lexicon-expandオプションを使用して、MarkLogicでのレキシコンを使用したワイルドカード検索の解決方法を制御できます。このオプションには次の値を使用できます。

heuristic MarkLogicの内部ルールのセットを使用して、ワイルドカードクエリを解決します(例えば、レキシコンのスキャンで大量のタームが返されることが予想される場合は、別の方法を使用します)。これがデフォルトです。
full ワイルドカードクエリを、ORで連結されたタームのセットに常に展開します。大量のタームが返されてクエリが遅くなる可能性があってもこの処理は行われます。
prefix-postfix レキシコンでマッチしたタームに基づいて、接頭辞と接尾辞のシーケンスを常に使用して、ワイルドカードクエリを解決します。
off レキシコン展開をワイルドカード検索で使用しません。代わりにインデックスを使用します。

レキシコンスキャンにおける工夫

レキシコン内のエントリの順序は、レキシコンのコレーションタイプによって決まります。小文字が大文字より前に配列されるコードポイントレキシコンは、検索が早く、より正確な結果が得られるので推奨されます。ただし、大文字と小文字を区別しない検索に対して難点があります。例えば、レキシコンでcat*というワイルドカードタームに対して単純なリニアスキャンを行うと、cで始まるエントリからCで始まるエントリにスキャンが行き着くまでに、マッチしない大量のエントリ(defなどで始まるエントリ)がチェックされることになります。

MarkLogicでは、この問題を解決するために、最初に一連のバイナリ検索を行って、スキャンする必要があるレキシコンのセクションを絞り込みます。バイナリ検索では、順序付きリストの中央にある項目を見つけ、検索タームがその中央の項目の前にあるのか後ろにあるのかを調べ、その後、同様の検索を該当する半分に対して実行します。このように分割して絞り込んでいくことで、最後に目的のものにたどり着きます。通常はこのほうが、リニア検索で見つけるよりも早くなります。

cat*のワイルドカード検索では、MarkLogicはバイナリ検索を行って、c*で始まりC*で終わる範囲を見つけます。次に、その範囲の中でバイナリ検索を行って、ca*からcA*のサブセクションと、Ca*からCA*のサブセクションを見つけます。最後に、文字tおよびTに対するサブセクションを見つけます(実際には、範囲が十分小さくなった段階で、検索ターム内の文字に対するバイナリ検索を打ち切ることがあります)。サブセクションが特定されたら、それらをすばやくスキャンして、マッチするエントリを見つけることができます。

shows areas of potential matches after performing a case insensitive search for the term cat*

図2:MarkLogicは、一連のバイナリ検索を使用して、レキシコン内でタームをスキャンする労力を最小化します。この例は、cat*というタームに対して大文字と小文字を区別しない検索を行う場合の処理を示しています。白いセクションが、マッチが存在する可能性がある領域を示しています。

まとめ

MarkLogicでは、非常に複雑なワイルドカードクエリにもすばやく結果を返すことができます。ワイルドカード検索の詳細、および関連設定の構成の詳細については、MarkLogicのマニュアルを参照してください。

この記事の執筆にあたって援助を提供してくれたMary HolstegeFei Xueに感謝します。

Ce site utilise des cookies.

En continuant votre navigation sur ce site, vous acceptez l'utilisation de cookies en accord avec la Déclaration de confidentialité MarkLogic.