Menemukan hasil yang paling cocok dengan penelusuran fuzzy

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

Selain melakukan penelusuran token yang tepat menggunakan SEARCH dan SEARCH_SUBSTRING Spanner juga mendukung perkiraan (atau kabur). Penelusuran fuzzy menemukan dokumen yang cocok meskipun berukuran kecil perbedaan antara kueri dan dokumen.

Spanner mendukung jenis penelusuran fuzzy berikut:

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

Penelusuran fuzzy berbasis N-gram bergantung pada tokenisasi substring yang penelusuran substring Anda butuhkan. Konfigurasi tokenizer ini penting karena memengaruhi kualitas dan performa penelusuran. Contoh berikut menunjukkan cara membuat kueri dengan kata yang salah eja atau dieja berbeda untuk menemukan kecocokan yang mendekati 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 dekat dengan "Kebencianl 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 perolehan untuk penelusuran perkiraan berbasis n-gram

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

  1. SEARCH_NGRAMS menemukan semua album kandidat yang memiliki n-gram yang dibagikan dengan kueri penelusuran. Misalnya, n-gram tiga karakter untuk "California" sertakan [cal, ali, lif, ifo, for, orn, rni, nia] dan untuk "Kaliphorn" menyertakan [kal, ali, lip, iph, pho, hor, orn]. N-gram yang dibagikan di set data ini adalah [ali, orn]. Secara default, SEARCH_NGRAMS cocok dengan semua dokumen dengan setidaknya dua n-gram bersama, oleh karena itu "Kaliphorn" kecocokan "California".
  2. SCORE_NGRAMS memberi peringkat pada kemiripan. Kesamaan dua {i>string<i} didefinisikan sebagai rasio n-gram bersama yang berbeda terhadap n-gram tidak berbagi yang berbeda:
$$ \frac{shared\_ngrams}{total\_ngrams_{index} + total\_ngrams_{query} - shared\_ngrams} $$

Spanner memiliki tiga argumen konfigurasi yang dapat digunakan SEARCH_NGRAMS:

  1. Ukuran minimum dan maksimum n-gram yang ditentukan dalam TOKENIZE_SUBSTRING atau TOKENIZE_NGRAMS. Sebaiknya jangan gunakan satu karakter n-gram karena cocok dengan jumlah dokumen. Di sisi lain, n-gram panjang menyebabkan SEARCH_NGRAMS kata-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). Angka yang lebih besar biasanya membuat kueri lebih cepat, tetapi mengurangi perolehan.

Untuk mencapai keseimbangan yang baik antara performa dan perolehan, argumen dapat dikonfigurasi agar sesuai dengan kueri dan workload tertentu.

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

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 disempurnakan

Bersamaan dengan pencarian fuzzy berbasis n-gram, mode kueri yang ditingkatkan juga menangani beberapa kata yang salah eja. Dengan demikian, ada beberapa tumpang tindih di antara keduanya baru. Tabel berikut meringkas 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 pada dokumen pendek dengan beberapa kata, seperti nama orang, nama kota, atau nama produk Berfungsi sama baiknya dengan dokumen berukuran apa pun dan kueri penelusuran berapa pun ukuran
Penelusuran kata sebagian Melakukan pencarian {i>substring<i} 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, baik di indeks atau kueri Hanya mendukung kata yang salah eja dalam kueri
Koreksi Menemukan kecocokan yang salah eja, meskipun kecocokan tersebut bukan kata asli Memperbaiki kesalahan ejaan untuk kata-kata umum dan sudah dikenal

Lakukan penelusuran fonetik dengan Soundex

Spanner menyediakan SOUNDEX untuk menemukan kata yang dieja secara berbeda, tetapi terdengar sama. Sebagai contoh, SOUNDEX("steven"), SOUNDEX("stephen"), dan SOUNDEX("stefan") adalah semua "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 sekunder seperti yang ditunjukkan pada contoh berikut:

CREATE TABLE Singers (
  SingerId INT64,
  Name STRING(MAX),
  Name_Soundex STRING(MAX) AS (LOWER(SOUNDEX(name)))
) PRIMARY KEY(SingerId);

CREATE INDEX SingersPhoneticIndex ON Singers(Name_Soundex);

Kueri berikut cocok dengan "stefan" kepada "Steven":

SELECT SingerId
FROM Singers
WHERE Name_Soundex = LOWER(SOUNDEX("stefan"))

Langkah selanjutnya