Menemukan kecocokan perkiraan dengan penelusuran fuzzy

Halaman ini menjelaskan cara menggunakan penelusuran fuzzy sebagai bagian dari penelusuran teks lengkap.

Selain melakukan penelusuran token persis menggunakan fungsi SEARCH dan SEARCH_SUBSTRING, Spanner juga mendukung penelusuran perkiraan (atau fuzzy). Penelusuran fuzzy menemukan dokumen yang cocok meskipun ada perbedaan kecil antara kueri dan dokumen.

Spanner mendukung jenis penelusuran fuzzy berikut:

  • Penelusuran perkiraan berbasis n-gram
  • Penelusuran fonetik menggunakan Soundex

Penelusuran fuzzy berbasis n-gram mengandalkan tokenisasi substring yang sama dengan yang diperlukan oleh penelusuran substring. Konfigurasi tokenizer penting karena memengaruhi kualitas dan performa penelusuran. Contoh berikut menunjukkan cara membuat kueri dengan kata yang salah eja atau dieja secara berbeda untuk menemukan perkiraan pencocokan dalam indeks penelusuran.

Skema

CREATE TABLE Albums (
  AlbumId STRING(MAX) NOT NULL,
  AlbumTitle STRING(MAX),
  AlbumTitle_Tokens TOKENLIST AS (
    TOKENIZE_SUBSTRING(AlbumTitle, ngram_size_min=>2, ngram_size_max=>3,
                       relative_search_types=>["word_prefix", "word_suffix"])) HIDDEN
) PRIMARY KEY(AlbumId);

CREATE SEARCH INDEX AlbumsIndex
ON Albums(AlbumTitle_Tokens)
STORING (AlbumTitle);

Kueri

Kueri berikut menemukan album dengan judul yang paling mirip dengan "Hatel Kaliphorn", seperti "Hotel California".

SELECT AlbumId
FROM Albums
WHERE SEARCH_NGRAMS(AlbumTitle_Tokens, "Hatel Kaliphorn")
ORDER BY SCORE_NGRAMS(AlbumTitle_Tokens, "Hatel Kaliphorn") DESC
LIMIT 10

Mengoptimalkan performa dan recall untuk penelusuran perkiraan berbasis n-gram

Contoh kueri di bagian sebelumnya melakukan penelusuran dalam dua fase, menggunakan dua fungsi yang berbeda:

  1. SEARCH_NGRAMS menemukan semua album kandidat yang telah berbagi n-gram dengan kueri penelusuran. Misalnya, n-gram tiga karakter untuk "California" mencakup [cal, ali, lif, ifo, for, orn, rni, nia] dan untuk "Kaliphorn" mencakup [kal, ali, lip, iph, pho, hor, orn]. N-gram bersama dalam set data ini adalah [ali, orn]. Secara default, SEARCH_NGRAMS mencocokkan semua dokumen dengan minimal dua n-gram yang sama, sehingga "Kaliphorn" cocok dengan "California".
  2. SCORE_NGRAMS menempatkan peringkat kecocokan berdasarkan kemiripan. Kemiripan dua string ditentukan sebagai rasio n-gram bersama yang berbeda dengan n-gram yang tidak sama:
$$ \frac{shared\_ngrams}{total\_ngrams_{index} + total\_ngrams_{query} - shared\_ngrams} $$

Biasanya, search_query sama di seluruh fungsi SEARCH_NGRAMS dan SCORE_NGRAMS. Cara yang direkomendasikan untuk melakukannya adalah menggunakan argumen dengan parameter kueri, bukan literal string, dan menentukan parameter kueri yang sama dalam fungsi SEARCH_NGRAMS dan SCORE_NGRAMS.

Spanner memiliki tiga argumen konfigurasi yang dapat digunakan dengan SEARCH_NGRAMS:

  1. Ukuran minimum dan maksimum n-gram yang ditentukan dalam TOKENIZE_SUBSTRING atau TOKENIZE_NGRAMS. Sebaiknya jangan gunakan n-gram satu karakter karena n-gram tersebut cocok dengan dokumen dalam jumlah yang sangat besar. Di sisi lain, n-gram yang panjang menyebabkan SEARCH_NGRAMS melewatkan kata pendek yang salah eja.
  2. Jumlah minimum n-gram yang harus cocok dengan SEARCH_NGRAMS (ditetapkan dengan argumen min_ngrams dan min_ngrams_percent di SEARCH_NGRAMS). Jumlah yang lebih tinggi biasanya membuat kueri lebih cepat, tetapi mengurangi recall.

Untuk mencapai keseimbangan yang baik antara performa dan recall, argumen ini dapat dikonfigurasi agar sesuai dengan kueri dan beban kerja tertentu.

Sebaiknya sertakan juga LIMIT bagian dalam untuk menghindari pembuatan kueri yang sangat mahal saat kombinasi n-gram populer ditemukan:

SELECT AlbumId
FROM (
  SELECT AlbumId,
         SCORE_NGRAMS(AlbumTitle_Tokens, @p) AS score
  FROM Albums
  WHERE SEARCH_NGRAMS(AlbumTitle_Tokens, @p)
  LIMIT 10000  # inner limit
)
ORDER BY score DESC
LIMIT 10  # outer limit

Penelusuran fuzzy berbasis n-gram versus mode kueri yang ditingkatkan

Selain penelusuran fuzzy berbasis n-gram, mode kueri yang ditingkatkan juga menangani beberapa kata yang salah eja. Dengan demikian, ada beberapa tumpang-tindih antara kedua fitur tersebut. Tabel berikut merangkum perbedaannya:

Penelusuran fuzzy berbasis n-gram Mode kueri yang ditingkatkan
Biaya Memerlukan tokenisasi substring yang lebih mahal berdasarkan n-gram Memerlukan tokenisasi teks lengkap yang lebih murah
Jenis kueri penelusuran Berfungsi baik dengan dokumen singkat yang berisi beberapa kata, seperti nama orang, nama kota, atau nama produk Berfungsi sama baiknya dengan dokumen berukuran apa pun dan kueri penelusuran berukuran apa pun
Penelusuran kata parsial Melakukan penelusuran substring yang memungkinkan kesalahan ejaan Hanya mendukung penelusuran untuk seluruh kata (SEARCH_SUBSTRING tidak mendukung argumen enhance_query)
Kata yang salah eja Mendukung kata yang salah eja dalam indeks atau kueri Hanya mendukung kata yang salah eja dalam kueri
Koreksi Menemukan kecocokan yang salah eja, meskipun kecocokan tersebut bukan kata yang sebenarnya Memperbaiki kesalahan ejaan untuk kata umum yang terkenal

Melakukan penelusuran fonetik dengan Soundex

Spanner menyediakan fungsi SOUNDEX untuk menemukan kata yang dieja secara berbeda, tetapi terdengar sama. Misalnya, SOUNDEX("steven"), SOUNDEX("stephen"), danSOUNDEX("stefan") semuanya adalah "s315", sedangkan SOUNDEX("stella") adalah "s340". SOUNDEX peka huruf besar/kecil dan hanya berfungsi untuk alfabet berbasis Latin.

Penelusuran fonetik dengan SOUNDEX dapat diterapkan dengan kolom yang dihasilkan dan indeks penelusuran seperti yang ditunjukkan dalam contoh berikut:

CREATE TABLE Singers (
  SingerId INT64,
  AlbumTitle STRING(MAX),
  AlbumTitle_Tokens TOKENLIST AS (TOKENIZE_FULLTEXT(AlbumTitle)) HIDDEN,
  Name STRING(MAX),
  NameSoundex STRING(MAX) AS (LOWER(SOUNDEX(Name))),
  NameSoundex_Tokens TOKENLIST AS (TOKEN(NameSoundex)) HIDDEN
) PRIMARY KEY(SingerId);

CREATE SEARCH INDEX SingersPhoneticIndex ON Singers(AlbumTitle_Tokens, NameSoundex_Tokens);

Kueri berikut mencocokkan "stefan" dengan "Steven" di SOUNDEX, beserta AlbumTitle yang berisi "cat":

SELECT SingerId
FROM Singers
WHERE NameSoundex = LOWER(SOUNDEX("stefan")) AND SEARCH(AlbumTitle_Tokens, "cat")

Langkah selanjutnya