NGRAM

L'index NGRAM de Milvus est construit pour accélérer les requêtes LIKE sur les champs VARCHAR ou les chemins JSON spécifiques dans les champs JSON. Avant de construire l'index, Milvus divise le texte en courtes sous-chaînes se chevauchant d'une longueur fixe n, connues sous le nom de n-grammes. Par exemple, avec n = 3, le mot "Milvus" est divisé en 3 grammes : "Mil", "ilv", "lvu" et "vus". Ces n-grammes sont ensuite stockés dans un index inversé qui associe chaque gramme aux identifiants des documents dans lesquels il apparaît. Au moment de la requête, cet index permet à Milvus de restreindre rapidement la recherche à un petit ensemble de candidats, ce qui accélère considérablement l'exécution de la requête.

Utilisez-le lorsque vous avez besoin d'un préfixe, d'un suffixe, d'un infixe ou d'un filtrage par caractères génériques rapide tel que :

• name LIKE "data%"

• title LIKE "%vector%"

• path LIKE "%json"

Fonctionnement

Milvus met en œuvre l'index NGRAM dans un processus en deux phases :

1. Construction de l'index: Générer des n-grammes pour chaque document et construire un index inversé pendant l'ingestion.

2. Accélération des requêtes: Utiliser l'index pour filtrer un petit ensemble de candidats, puis vérifier les correspondances exactes.

Phase 1 : Construction de l'index

Pendant l'ingestion des données, Milvus construit l'index NGRAM en effectuant deux étapes principales :

1. Décomposition du texte en n-grammes: Milvus fait glisser une fenêtre de n sur chaque chaîne du champ cible et extrait les sous-chaînes qui se chevauchent, ou n-grammes. La longueur de ces sous-chaînes se situe dans une plage configurable, [min_gram, max_gram].

   • min_gram: Le n-gramme le plus court à générer. Cela définit également la longueur minimale de la sous-chaîne de la requête qui peut bénéficier de l'index.

   • max_gram: Le n-gramme le plus long à générer. Au moment de la requête, il est également utilisé comme taille maximale de la fenêtre lors de la division de longues chaînes de requête.

   Par exemple, avec min_gram=2 et max_gram=3, la chaîne "AI database" est décomposée comme suit :

Construire un index de ngrammes

- **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>

1. Construire un index inversé: Un index inversé est créé pour faire correspondre chaque n-gramme généré à une liste d'ID de documents le contenant.

   Par exemple, si le 2-gramme "AI" apparaît dans des documents portant les ID 1, 5, 6, 8 et 9, l'index enregistre {"AI": [1, 5, 6, 8, 9]}. Cet index est ensuite utilisé au moment de la requête pour restreindre rapidement le champ de recherche.

Création de l'index de ngrammes 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>

Phase 2 : Accélérer les requêtes

Lorsqu'un filtre LIKE est exécuté, Milvus utilise l'index NGRAM pour accélérer la requête dans les étapes suivantes :

Accélérer les requêtes

1. Extraire le terme de la requête : La sous-chaîne contiguë sans caractères génériques est extraite de l'expression LIKE (par exemple, "%database%" devient "database").

2. Décomposer le terme de la requête : Le terme de la requête est décomposé en n-grammes en fonction de sa longueur (L) et des paramètres min_gram et max_gram.

   • Si L < min_gram, l'index ne peut pas être utilisé et la requête revient à un balayage complet.

   • Si min_gram ≤ L ≤ max_gram, le terme entier de la requête est traité comme un seul n-gramme et aucune décomposition supplémentaire n'est nécessaire.

   • Si L > max_gram, le terme de la requête est décomposé en grammes qui se chevauchent en utilisant une taille de fenêtre égale à max_gram.

   Par exemple, si max_gram est défini sur 3 et que le terme de la requête est "database", qui a une longueur de 8, il est décomposé en sous-grammes de 3 grammes comme "dat", "ata", "tab", et ainsi de suite.

3. Recherche de chaque gramme et intersection: Milvus recherche chacun des grammes de la requête dans l'index inversé, puis intersecte les listes d'ID de documents qui en résultent pour trouver un petit ensemble de documents candidats. Ces candidats contiennent tous les grammes de la requête.

4. Vérifier et renvoyer les résultats : Le filtre original LIKE est ensuite appliqué comme vérification finale sur le petit ensemble de candidats pour trouver les correspondances exactes.

Créer un index NGRAM

Vous pouvez créer un index NGRAM sur un champ VARCHAR ou sur un chemin spécifique à l'intérieur d'un champ JSON.

Exemple 1 : Création sur un champ VARCHAR

Pour un champ VARCHAR, il suffit de spécifier le champ field_name et de configurer min_gram et 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
)

Cette configuration génère des 2-grammes et des 3-grammes pour chaque chaîne de caractères dans text et les stocke dans l'index inversé.

Exemple 2 : Création sur un chemin JSON

Pour un champ JSON, en plus des paramètres de gramme, vous devez également spécifier :

• params.json_path - le chemin JSON qui pointe vers la valeur à indexer.

• params.json_cast_type - Le chemin JSON doit être "varchar" (insensible à la casse), car l'indexation NGRAM fonctionne sur des chaînes de caractères.

# 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
)

Dans cet exemple :

• Seule la valeur à json_field["body"] est indexée.

• La valeur est convertie en VARCHAR avant la tokenisation n-gram.

• Milvus génère des sous-chaînes de longueur 2 à 4 et les stocke dans l'index inversé.

Pour plus d'informations sur l'indexation d'un champ JSON, voir Indexation JSON.

Requêtes accélérées par NGRAM

Pour que l'index NGRAM soit appliqué :

• La requête doit cibler un champ VARCHAR (ou un chemin JSON) qui possède un index NGRAM.

• La partie littérale du motif LIKE doit comporter au moins min_gram caractères(par exemple, si le terme le plus court de votre requête est de 2 caractères, définissez min_gram=2 lors de la création de l'index).

Types de requêtes pris en charge :

• Correspondance de préfixes

  # Match any string that starts with the substring "database"
  filter = 'text LIKE "database%"'
  

• Correspondance suffixe

  # Match any string that ends with the substring "database"
  filter = 'text LIKE "%database"'
  

• Correspondance infixe

  # Match any string that contains the substring "database" anywhere
  filter = 'text LIKE "%database%"'
  

• Correspondance de caractères génériques

  Milvus prend en charge les requêtes % (zéro ou plusieurs caractères) et _ (un seul caractère).

  # Match any string where "st" appears first, and "um" appears later in the text 
  filter = 'text LIKE "%st%um%"'
  

• Requêtes de chemin JSON

  filter = 'json_field["body"] LIKE "%database%"'
  

Pour plus d'informations sur la syntaxe des expressions de filtre, voir Opérateurs de base.

Supprimer un index

Utilisez la méthode drop_index() pour supprimer un index existant d'une collection.

client.drop_index(
    collection_name="Documents",   # Name of the collection
    index_name="ngram_index" # Name of the index to drop
)

Notes d'utilisation

• Types de champs: Pris en charge pour les champs VARCHAR et JSON. Pour JSON, fournir à la fois params.json_path et params.json_cast_type="varchar".

• Unicode: La décomposition du NGRAM est basée sur les caractères et indépendante de la langue, et inclut les espaces blancs et la ponctuation.

• Compromis espace-temps: des plages de grammes plus larges [min_gram, max_gram] produisent plus de grammes et des index plus volumineux. Si la mémoire est limitée, envisagez le mode mmap pour les listes d'écritures volumineuses. Pour plus d'informations, reportez-vous à la section Utiliser mmap.

• Immuabilité: min_gram et max_gram ne peuvent pas être modifiés sur place - il faut reconstruire l'index pour les ajuster.

Meilleures pratiques

• Choisissez min_gram et max_gram en fonction du comportement de recherche.

  • Commencez par min_gram=2, max_gram=3.

  • Définissez min_gram comme le littéral le plus court que vous vous attendez à ce que les utilisateurs tapent.

  • Fixez max_gram à une longueur proche de celle des sous-chaînes significatives ; une longueur plus importante de max_gram améliore le filtrage mais augmente l'espace disponible.

• Évitez les grammes à faible sélectivité

  Les motifs très répétitifs (par exemple, "aaaaaa") n'offrent qu'un filtrage faible et peuvent donner des résultats limités.

• Normaliser de manière cohérente

  Appliquez la même normalisation au texte ingéré et aux littéraux de la requête (par exemple, mise en minuscules, découpage) si votre cas d'utilisation le nécessite.