NGRAM

Indeks NGRAM di Milvus dibuat untuk mempercepat kueri LIKE pada bidang VARCHAR atau jalur JSON tertentu di dalam bidang JSON. Sebelum membuat indeks, Milvus membagi teks menjadi substring-substring pendek yang saling tumpang tindih dengan panjang tetap n, yang dikenal sebagai n-gram. Sebagai contoh, dengan n = 3, kata "Milvus" dipecah menjadi 3-gram: "Mil", "ilv", "lvu", dan "vus". N-gram ini kemudian disimpan dalam indeks terbalik yang memetakan setiap gram ke ID dokumen tempat kata tersebut muncul. Pada saat kueri, indeks ini memungkinkan Milvus mempersempit pencarian dengan cepat menjadi sekumpulan kecil kandidat, sehingga menghasilkan eksekusi kueri yang jauh lebih cepat.

Gunakan ini ketika Anda membutuhkan pemfilteran awalan, akhiran, infiks, atau karakter pengganti yang cepat, seperti:

• name LIKE "data%"

• title LIKE "%vector%"

• path LIKE "%json"

Bagaimana cara kerjanya

Milvus mengimplementasikan indeks NGRAM dalam proses dua tahap:

1. Membangun indeks: Menghasilkan n-gram untuk setiap dokumen dan membangun indeks terbalik selama proses ingest.

2. Mempercepat kueri: Gunakan indeks untuk memfilter ke kumpulan kandidat yang kecil, lalu verifikasi kecocokan yang tepat.

Tahap 1: Membangun indeks

Selama konsumsi data, Milvus membangun indeks NGRAM dengan melakukan dua langkah utama:

1. Menguraikan teks menjadi n-gram: Milvus menggeser jendela n di setiap string di bidang target dan mengekstrak substring yang tumpang tindih, atau n-gram. Panjang substring ini berada dalam rentang yang dapat dikonfigurasi, [min_gram, max_gram].

   • min_gram: N-gram terpendek yang akan dihasilkan. Ini juga mendefinisikan panjang substring kueri minimum yang dapat memanfaatkan indeks.

   • max_gram: N-gram terpanjang yang akan dihasilkan. Pada waktu kueri, ini juga digunakan sebagai ukuran jendela maksimum ketika memisahkan string kueri yang panjang.

   Sebagai contoh, dengan min_gram=2 dan max_gram=3, string "AI database" dipecah sebagai berikut:

Membangun Indeks Ngram

- **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. Membangun indeks terbalik: Indeks terbalik dibuat yang memetakan setiap n-gram yang dihasilkan ke daftar ID dokumen yang mengandungnya.

   Misalnya, jika 2-gram "AI" muncul di dokumen dengan ID 1, 5, 6, 8, dan 9, indeks akan mencatat {"AI": [1, 5, 6, 8, 9]}. Indeks ini kemudian digunakan pada waktu kueri untuk mempersempit cakupan pencarian dengan cepat.

Membangun Indeks Ngram 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>

Tahap 2: Mempercepat kueri

Ketika filter LIKE dijalankan, Milvus menggunakan indeks NGRAM untuk mempercepat kueri dengan langkah-langkah berikut:

Mempercepat Kueri

1. Ekstrak istilah kueri: Substring yang bersebelahan tanpa karakter pengganti diekstrak dari ekspresi LIKE (misalnya, "%database%" menjadi "database").

2. Menguraikan istilah kueri: Istilah kueri diuraikan menjadi n-gram berdasarkan panjangnya (L) dan pengaturan min_gram dan max_gram.

   • Jika L < min_gram, indeks tidak dapat digunakan, dan kueri kembali ke pemindaian penuh.

   • Jika min_gram ≤ L ≤ max_gram, seluruh istilah kueri diperlakukan sebagai satu n-gram, dan tidak perlu dilakukan penguraian lebih lanjut.

   • Jika L > max_gram, istilah kueri dipecah menjadi beberapa gram yang tumpang tindih menggunakan ukuran jendela yang sama dengan max_gram.

   Sebagai contoh, jika max_gram disetel ke 3 dan istilah kueri adalah "database", yang memiliki panjang 8, istilah tersebut diuraikan menjadi substring 3 gram seperti "dat", "ata", "tab", dan seterusnya.

3. Cari setiap gram & potong: Milvus mencari setiap gram kueri dalam indeks terbalik dan kemudian memotong daftar ID dokumen yang dihasilkan untuk menemukan sekumpulan kecil dokumen kandidat. Kandidat-kandidat ini berisi semua gram dari kueri.

4. Verifikasi dan kembalikan hasilnya: Filter LIKE asli kemudian diterapkan sebagai pemeriksaan akhir hanya pada kumpulan kandidat kecil untuk menemukan kecocokan yang tepat.

Membuat indeks NGRAM

Anda dapat membuat indeks NGRAM pada bidang VARCHAR atau pada jalur tertentu di dalam bidang JSON.

Contoh 1: Membuat pada bidang VARCHAR

Untuk bidang VARCHAR, Anda cukup menentukan field_name dan mengonfigurasi min_gram dan 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
)

Konfigurasi ini menghasilkan 2-gram dan 3-gram untuk setiap string di text dan menyimpannya dalam indeks terbalik.

Contoh 2: Membuat pada jalur JSON

Untuk bidang JSON, selain pengaturan gram, Anda juga harus menentukan:

• params.json_path - jalur JSON yang mengarah ke nilai yang ingin diindeks.

• params.json_cast_type - harus "varchar" (tidak peka huruf besar-kecil), karena pengindeksan NGRAM beroperasi pada string.

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

Dalam contoh ini:

• Hanya nilai di json_field["body"] yang diindeks.

• Nilai tersebut di-cast ke VARCHAR sebelum tokenisasi n-gram.

• Milvus menghasilkan substring dengan panjang 2 hingga 4 dan menyimpannya dalam indeks terbalik.

Untuk informasi lebih lanjut tentang cara mengindeks bidang JSON, lihat Pengindeksan JSON.

Kueri yang dipercepat oleh NGRAM

Agar indeks NGRAM dapat diterapkan:

• Kueri harus menargetkan bidang VARCHAR (atau jalur JSON) yang memiliki indeks NGRAM.

• Bagian literal dari pola LIKE harus memiliki panjang setidaknya min_gram karakter.(Misalnya, jika istilah kueri terpendek yang Anda harapkan adalah 2 karakter, tetapkan min_gram = 2 saat membuat indeks).

Jenis kueri yang didukung:

• Pencocokan awalan

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

• Pencocokan akhiran

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

• Pencocokan infiks

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

• Pencocokan wildcard

  Milvus mendukung % (nol karakter atau lebih) dan _ (tepat satu karakter).

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

• Kueri jalur JSON

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

Untuk informasi lebih lanjut tentang sintaks ekspresi filter, lihat Operator Dasar.

Menghapus indeks

Gunakan metode drop_index() untuk menghapus indeks yang sudah ada dari koleksi.

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

Catatan penggunaan

• Jenis bidang: Didukung pada bidang VARCHAR dan JSON. Untuk JSON, sediakan params.json_path dan params.json_cast_type="varchar".

• Unicode: Penguraian NGRAM berbasis karakter dan bahasa-agnostik serta menyertakan spasi dan tanda baca.

• Pertukaran ruang-waktu: Rentang gram yang lebih luas [min_gram, max_gram] menghasilkan lebih banyak gram dan indeks yang lebih besar. Jika memori terbatas, pertimbangkan mode mmap untuk daftar posting yang besar. Untuk informasi lebih lanjut, lihat Menggunakan mmap.

• Kekekalan: min_gram dan max_gram tidak dapat diubah di tempatnya-bangun kembali indeks untuk menyesuaikannya.

Praktik terbaik

• Pilih min_gram dan max_gram untuk mencocokkan perilaku pencarian

  • Mulai dengan min_gram=2, max_gram=3.

  • Tetapkan min_gram ke literal terpendek yang Anda perkirakan akan diketik oleh pengguna.

  • Tetapkan max_gram di dekat panjang khas substring yang bermakna; max_gram yang lebih besar meningkatkan penyaringan tetapi menambah ruang.

• Hindari gram dengan selektivitas rendah

  Pola yang sangat berulang (misalnya, "aaaaaa") memberikan penyaringan yang lemah dan mungkin menghasilkan keuntungan yang terbatas.

• Lakukan normalisasi secara konsisten

  Terapkan normalisasi yang sama pada teks yang dicerna dan literal kueri (misalnya, huruf kecil, pemangkasan) jika kasus penggunaan Anda membutuhkannya.