NGRAM
MilvusのNGRAM インデックスは、VARCHAR フィールド、またはJSON フィールド内の特定のJSONパスに対するLIKE クエリや、条件を満たす正規表現フィルターの処理を高速化します。インデックスの構築に先立ち、Milvusはテキストを、固定長nの短い重複する部分文字列（n-gram）に分割します。 たとえば、n = 3 の場合、単語「Milvus」は 3-グラム「Mil」、「ilv」、「lvu」、「vus」に分割されます。これらの n-グラムは、各グラムが出現するドキュメント ID にマッピングされる逆引きインデックスに格納されます。 クエリ実行時、このインデックスにより、Milvus は元のフィルタ条件を検証する前に、検索対象を少数の候補に素早く絞り込むことができます。
次のような、高速な接頭辞、接尾辞、中置辞、ワイルドカード、または正規表現によるフィルタリングが必要な場合に使用します。
name LIKE "data%"title LIKE "%vector%"path LIKE "%json"message =~ "error.*timeout"url =~ "/api/v[0-9]+/users"
LIKE および正規表現フィルタ式の構文の詳細については、「パターンマッチング」を参照してください。
仕組み
Milvus は、NGRAM インデックスを 2 段階のプロセスで実装します。
インデックスの構築：各ドキュメントの n-gram を生成し、取り込み中に逆引きインデックスを構築します。
クエリの高速化：インデックスを使用して候補セットを絞り込み、その後、完全一致を検証します。
フェーズ1：インデックスの構築
データの取り込み中に、Milvusは主に以下の2つのステップを実行してNGRAMインデックスを構築します：
テキストをn-gramに分解：Milvusは、対象フィールド内の各文字列に対してn長のウィンドウをスライドさせ、重複する部分文字列（n-gram）を抽出します。これらの部分文字列の長さは、設定可能な範囲内（
[min_gram, max_gram]）に収まります。min_gram: 生成する最短のn-gram。これは、インデックスの恩恵を受けられるクエリ部分文字列の最小長も定義します。max_gram: 生成するn-gramの最大長。クエリ実行時には、長いクエリ文字列を分割する際の最大ウィンドウサイズとしても使用されます。
たとえば、
min_gram=2およびmax_gram=3を設定した場合、文字列"AI database"は次のように分割されます:
N-gramインデックスの構築
- **2-grams:** `AI`, `I_`, `_d`, `da`, `at`, ...
- **3-grams:** `AI_`, `I_d`, `_da`, `dat`, `ata`, ...
<div class="alert note">
- For a range `[min_gram, max_gram]`, Milvus generates all n-grams for every length between the two values (inclusive). For example, with `[2,4]` and the word `"text"`, Milvus generates:
- **2-grams:** `te`, `ex`, `xt`
- **3-grams:** `tex`, `ext`
- **4-grams:** `text`
- N-gram decomposition is character-based and language-agnostic. For example, in Chinese, `"向量数据库"` with `min_gram = 2` is decomposed into: `"向量"`, `"量数"`, `"数据"`, `"据库"`.
- Spaces and punctuation are treated as characters during decomposition.
- Decomposition preserves original case, and matching is case-sensitive. For example, `"Database"` and `"database"` will generate different n-grams and require exact case matching during queries.
</div>
逆引きインデックスの構築：生成された各n-gramを、それを含むドキュメントIDのリストにマッピングする逆引きインデックスが作成されます。
たとえば、2-gram「
"AI"」が ID 1、5、6、8、9 のドキュメントに含まれている場合、インデックスには「{"AI": [1, 5, 6, 8, 9]}」が記録されます。このインデックスは、クエリ実行時に検索範囲を迅速に絞り込むために使用されます。
N-gramインデックスの構築 2
<div class="alert note">
A wider `[min_gram, max_gram]` range creates more grams and larger mapping lists. If memory is tight, consider mmap mode for very large posting lists. For details, refer to [Use mmap](https://zilliverse.feishu.cn/wiki/P3wrwSMNNihy8Vkf9p6cTsWYnTb).
</div>
フェーズ 2: クエリの高速化
LIKE フィルターまたは対象となる正規表現フィルターが実行されると、Milvus は NGRAM インデックスを使用して、以下の手順でクエリを高速化します：
クエリの高速化
クエリ用語の抽出：
LIKE式から、ワイルドカードを含まない連続した部分文字列が抽出されます（例："%database%"は"database"となります）。正規表現フィルターの場合、Milvusは可能な限り正規表現パターンから固定のリテラル部分文字列を抽出します。例えば、message =~ "error.*timeout"にはリテラルerrorおよびtimeoutが含まれます。クエリ用語の分解：クエリ用語は、その長さ（
L）およびmin_gramとmax_gramの設定に基づいて、n-gramに分解されます。L < min_gramの場合、インデックスは使用できず、クエリはフルスキャンに切り替わります。min_gram ≤ L ≤ max_gramの場合、クエリ用語全体が単一の n-gram として扱われ、それ以上の分解は必要ありません。L > max_gramの場合、クエリ用語は、max_gramに等しいウィンドウサイズを使用して、重複するグラムに分解されます。
たとえば、
max_gramが3に設定されており、クエリ用語が"database"（長さ8）の場合、これは"dat"、"ata"、"tab"などの 3-gram の部分文字列に分解されます。各グラムを検索し、共通部分を抽出：Milvusは、クエリの各グラムを逆引きインデックスで検索し、その結果得られたドキュメントIDリストの共通部分を抽出することで、候補となるドキュメントの小さな集合を特定します。これらの候補には、クエリに含まれるすべてのグラムが含まれています。
結果の検証と返却：その後、元の
LIKEまたは正規表現フィルターを、この少数の候補セットに対してのみ最終チェックとして適用し、完全一致を特定します。
NGRAMインデックスの作成
VARCHAR フィールド、またはJSON フィールド内の特定のパスに対して、NGRAMインデックスを作成できます。
例 1: VARCHAR フィールドに作成する
VARCHAR フィールドの場合は、field_name を指定し、min_gram およびmax_gram を設定するだけで済みます。
from pymilvus import MilvusClient
client = MilvusClient(uri="http://localhost:19530") # Replace with your server address
# Assume you have defined a VARCHAR field named "text" in your collection schema
# Prepare index parameters
index_params = client.prepare_index_params()
# Add NGRAM index on the "text" field
index_params.add_index(
field_name="text", # Target VARCHAR field
index_type="NGRAM", # Index type is NGRAM
index_name="ngram_index", # Custom name for the index
min_gram=2, # Minimum substring length (e.g., 2-gram: "st")
max_gram=3 # Maximum substring length (e.g., 3-gram: "sta")
)
# Create the index on the collection
client.create_index(
collection_name="Documents",
index_params=index_params
)
この設定により、text 内の各文字列に対して2-gramおよび3-gramが生成され、それらを逆引きインデックスに格納します。
例 2: JSON パスでの作成
JSON フィールドの場合、グラムの設定に加えて、以下も指定する必要があります：
params.json_path– インデックス登録対象の値を指す JSON パス。params.json_cast_type– NGRAM インデックス作成は文字列に対して行われるため、"varchar"（大文字小文字を区別しない）である必要があります。
# Assume you have defined a JSON field named "json_field" in your collection schema, with a JSON path named "body"
# Prepare index parameters
index_params = client.prepare_index_params()
# Add NGRAM index on a JSON field
index_params.add_index(
field_name="json_field", # Target JSON field
index_type="NGRAM", # Index type is NGRAM
index_name="json_ngram_index", # Custom index name
min_gram=2, # Minimum n-gram length
max_gram=4, # Maximum n-gram length
params={
"json_path": "json_field[\"body\"]", # Path to the value inside the JSON field
"json_cast_type": "varchar" # Required: cast the value to varchar
}
)
# Create the index on the collection
client.create_index(
collection_name="Documents",
index_params=index_params
)
この例では：
json_field["body"]にある値のみがインデックス化されます。この値は、n-gramトークン化の前に
VARCHARに変換されます。Milvusは長さ2～4の部分文字列を生成し、それらを逆引きインデックスに格納します。
JSONフィールドのインデックス作成方法の詳細については、「JSONインデックス作成」を参照してください。
NGRAM によるクエリの高速化
NGRAM インデックスを適用するには、以下の条件を満たす必要があります。
クエリは、
NGRAMインデックスが作成されているVARCHARフィールド（またはJSONパス）を対象とする必要があります。LIKEパターンのリテラル部分は、min_gram文字以上の長さでなければなりません。 （たとえば、予想される最短のクエリ用語が 2 文字の場合、インデックス作成時に min_gram=2 を設定します。
サポートされているクエリの種類：
プレフィックス一致
# Match any string that starts with the substring "database" filter = 'text LIKE "database%"'サフィックス一致
# Match any string that ends with the substring "database" filter = 'text LIKE "%database"'中置一致
# Match any string that contains the substring "database" anywhere filter = 'text LIKE "%database%"'ワイルドカード一致
Milvusは、
%（0個以上の文字）と_（正確に1つの文字）の両方をサポートしています。# Match any string where "st" appears first, and "um" appears later in the text filter = 'text LIKE "%st%um%"'JSONパスクエリ
filter = 'json_field["body"] LIKE "%database%"'正規表現フィルター
# Match log messages that contain "error" followed later by "timeout" filter = 'text =~ "error.*timeout"'JSONパスに対する正規表現フィルター
filter = 'json_field["body"] =~ "error.*timeout"'
フィルタ式の構文の詳細については、「パターンマッチング」を参照してください。
インデックスの削除
drop_index() メソッドを使用すると、コレクションから既存のインデックスを削除できます。
client.drop_index(
collection_name="Documents", # Name of the collection
index_name="ngram_index" # Name of the index to drop
)
使用上の注意
フィールドタイプ：
VARCHARおよびJSONフィールドでサポートされています。JSON の場合、params.json_pathとparams.json_cast_type="varchar"の両方を指定してください。正規表現の高速化：
NGRAMは、Milvusが正規表現パターンから固定のリテラル部分文字列を抽出できる場合にのみ、正規表現フィルターを高速化します。[a-z]+のようなパターンは、固定リテラルを含まないため、スキャン処理に切り替わる場合があります。大文字小文字を区別しない正規表現：
(?i)を使用した正規表現パターンはサポートされていますが、インデックスでは元の大文字小文字が保持されるため、NGRAMによる最適化がスキップされる場合があります。検証ステップ：正規表現フィルターの場合、
NGRAMは候補を生成し、Milvusは完全なRE2正規表現パターンでそれらを検証するため、インデックスによる高速化によって一致結果が変わることはありません。Unicode：NGRAMの分解は文字単位で行われ、言語に依存せず、空白や句読点も含まれます。
空間と時間のトレードオフ：
[min_gram, max_gram]でグラム範囲を広くすると、生成されるグラムの数が増え、インデックスも大きくなります。メモリが逼迫している場合は、大規模なポスティングリストに対してmmapモードの使用を検討してください。詳細については、「mmapの使用」を参照してください。不変性:
min_gramおよびmax_gramはその場で変更できません。これらを調整するには、インデックスを再構築してください。
ベストプラクティス
検索の挙動に合わせて `min_gram` および `max_gram` を選択してください
最初は
min_gram=2、max_gram=3から始めます。min_gramには、ユーザーが入力すると予想される最短のリテラルを設定します。max_gramは、意味のある部分文字列の一般的な長さに近い値に設定します。max_gramを大きくするとフィルタリングは向上しますが、スペースも増えます。
選択性の低いグラムは避ける
繰り返し率の高いパターン（例：
"aaaaaa"）はフィルタリング効果が弱く、得られるメリットも限定的になる可能性があります。一貫して正規化を行う
ユースケースで必要であれば、取り込まれたテキストとクエリリテラルに同じ正規化処理（例：小文字化、先頭・末尾のトリミング）を適用してください。
