חיפוש התאמות משוערות באמצעות חיפוש משוער

בדף הזה מוסבר איך להשתמש בחיפוש משוער כחלק מחיפוש טקסט מלא.

בנוסף לביצוע חיפושים מדויקים של טוקנים באמצעות הפונקציות SEARCH ו-SEARCH_SUBSTRING, ‏ Spanner תומך גם בחיפושים משוערים (או לא מדויקים). חיפושים משוערים מוצאים מסמכים תואמים למרות הבדלים קטנים בין השאילתה לבין המסמך.

‫Spanner תומך בסוגים הבאים של חיפוש משוער:

  • חיפוש משוער מבוסס N-grams
  • חיפוש פונטי באמצעות Soundex

חיפוש משוער שמבוסס על N-גרמים מסתמך על אותו תהליך של טוקניזציה של מחרוזות משנה שנדרש בחיפוש מחרוזות משנה. ההגדרה של הטוקנייזר חשובה כי היא משפיעה על איכות החיפוש ועל הביצועים. בדוגמה הבאה מוצג איך ליצור שאילתה עם מילים שמאויתות בצורה שונה או עם שגיאות איות, כדי למצוא התאמות משוערות באינדקס החיפוש.

סכימה

GoogleSQL 

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

PostgreSQL

בדוגמה הזו נעשה שימוש ב-spanner.tokenize_substring.

CREATE TABLE albums (
  albumid character varying NOT NULL,
  albumtitle character varying,
  albumtitle_tokens spanner.tokenlist GENERATED ALWAYS AS (
    spanner.tokenize_substring(albumtitle, ngram_size_min=>2, ngram_size_max=>3,
                      relative_search_types=>'{word_prefix, word_suffix}'::text[])) VIRTUAL HIDDEN,
PRIMARY KEY(albumid));

CREATE SEARCH INDEX albumsindex
ON albums(albumtitle_tokens)
INCLUDE (albumtitle);

שאילתה

השאילתה הבאה מוצאת את האלבומים שהשמות שלהם הכי קרובים ל-"Hatel Kaliphorn", כמו "Hotel California".

GoogleSQL 

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

PostgreSQL

בדוגמה הזו נעשה שימוש ב-spanner.score_ngrams וב-spanner.search_ngrams.

SELECT albumid
FROM albums
WHERE spanner.search_ngrams(albumtitle_tokens, 'Hatel Kaliphorn')
ORDER BY spanner.score_ngrams(albumtitle_tokens, 'Hatel Kaliphorn') DESC
LIMIT 10

אופטימיזציה של הביצועים וההחזרה של חיפוש משוער שמבוסס על n-גרמים

השאילתה לדוגמה בקטע הקודם מחפשת בשני שלבים, באמצעות שתי פונקציות שונות:

  1. ‫SEARCH_NGRAMS מציאת כל האלבומים הפוטנציאליים שכוללים n-גרמים משותפים עם שאילתת החיפוש. לדוגמה, n-גרמות של שלושה תווים עבור המילה California כוללות את [cal, ali, lif, ifo, for, orn, rni, nia] ועבור המילה Kaliphorn כוללות את [kal, ali, lip, iph, pho, hor, orn]. ה-n-grams המשותפים במערכי הנתונים האלה הם [ali, orn]. כברירת מחדל, SEARCH_NGRAMS מתאים לכל המסמכים עם לפחות שני n-גרמים משותפים, ולכן 'Kaliphorn' מתאים ל-'California'.
  2. ‫SCORE_NGRAMS מדרג את ההתאמות לפי מידת הדמיון. הדמיון בין שתי מחרוזות מוגדר כיחס בין n-גרמים משותפים ייחודיים לבין n-גרמים לא משותפים ייחודיים:
$$ \frac{shared\_ngrams}{total\_ngrams_{index} + total\_ngrams_{query} - shared\_ngrams} $$

בדרך כלל שאילתת החיפוש זהה בפונקציות SEARCH_NGRAMS ו-SCORE_NGRAMS. הדרך המומלצת לעשות זאת היא להשתמש בארגומנט עם פרמטרים של שאילתה ולא עם מחרוזות מילוליות, ולציין את אותו פרמטר של שאילתה בפונקציות SEARCH_NGRAMS ו-SCORE_NGRAMS.

ל-Spanner יש שלושה ארגומנטים להגדרה שאפשר להשתמש בהם עם SEARCH_NGRAMS:

  • הגודל המינימלי והמקסימלי של n-גרם מצוין באמצעות הפונקציות TOKENIZE_SUBSTRING או TOKENIZE_NGRAMS. אנחנו לא ממליצים על n-גרמים של תו אחד כי הם יכולים להתאים למספר גדול מאוד של מסמכים. מצד שני, n-grams ארוכים גורמים ל-SEARCH_NGRAMS לפספס מילים קצרות עם איות שגוי.
  • מספר ה-n-grams המינימלי שצריך להיות זהה (מוגדר באמצעות הארגומנטים min_ngrams ו-min_ngrams_percent בפונקציה SEARCH_NGRAMS). בדרך כלל, מספרים גבוהים יותר מזרזים את השאילתה, אבל מקטינים את ההחזרה.SEARCH_NGRAMS

כדי להשיג איזון טוב בין ביצועים לבין היכולת לאחזר מידע, אפשר להגדיר את הארגומנטים האלה כך שיתאימו לשאילתה ולעומס העבודה הספציפיים.

מומלץ גם להוסיף LIMIT פנימי כדי להימנע מיצירת שאילתות יקרות מאוד כשנתקלים בשילוב של n-גרמות פופולריות.

GoogleSQL 

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

PostgreSQL

בדוגמה הזו נעשה שימוש ב-spanner.score_ngrams וב-spanner.search_ngrams. פרמטר השאילתה $1 קשור ל-'Hatel Kaliphorn'.

SELECT albumid
FROM
  (
    SELECT albumid, spanner.score_ngrams(albumtitle_tokens, $1) AS score
    FROM albums
    WHERE spanner.search_ngrams(albumtitle_tokens, $1)
    LIMIT 10000
  ) AS inner_query
ORDER BY inner_query.score DESC
LIMIT 10

חיפוש משוער מבוסס N-grams לעומת מצב שאילתה משופר

בנוסף לחיפוש משוער שמבוסס על n-grams, מצב השאילתה המשופר מטפל גם במילים מסוימות עם שגיאות איות. לכן יש חפיפה מסוימת בין שתי התכונות. בטבלה הבאה מפורטים ההבדלים:

חיפוש משוער שמבוסס על n-גרמים מצב שאילתה משופר
עלות נדרשת טוקניזציה יקרה יותר של מחרוזת משנה שמבוססת על n-גרמים נדרשת טוקניזציה מלאה של הטקסט בעלות נמוכה יותר
סוגי שאילתות חיפוש היא מתאימה במיוחד למסמכים קצרים עם כמה מילים, למשל שם של אדם, שם של עיר או שם של מוצר הוא פועל בצורה טובה באותה מידה עם מסמכים בכל הגדלים ועם שאילתות חיפוש בכל הגדלים
חיפוש מילים חלקיות מבצע חיפוש של מחרוזת משנה שמאפשרת שגיאות איות תומך רק בחיפוש של מילים שלמות (SEARCH_SUBSTRING לא תומך בארגומנט enhance_query)
מילים עם שגיאות איות תמיכה במילים עם שגיאות איות באינדקס או בשאילתה התכונה תומכת רק במילים עם שגיאות איות בשאילתה
תיקונים חיפוש של התאמות עם שגיאות כתיב, גם אם ההתאמה היא לא מילה אמיתית תיקון שגיאות איות במילים נפוצות ומוכרות

ביצוע חיפוש פונטי באמצעות Soundex

ב-Spanner יש פונקציה SOUNDEX שמאפשרת למצוא מילים שמאויתות בצורה שונה אבל נשמעות אותו דבר. לדוגמה, SOUNDEX("steven"), ‏ SOUNDEX("stephen") ו-SOUNDEX("stefan") הם כולם s315, ואילו SOUNDEX("stella") הוא s340. הפונקציה SOUNDEX היא תלוית אותיות רישיות, והיא פועלת רק באלפבית שמבוסס על לטינית.

אפשר להטמיע חיפוש פונטי עם SOUNDEX באמצעות עמודה שנוצרה ואינדקס חיפוש, כמו בדוגמה הבאה:

GoogleSQL 

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

PostgreSQL

בדוגמה הזו נעשה שימוש ב-spanner.soundex.

CREATE TABLE singers (
  singerid bigint,
  albumtitle character varying,
  albumtitle_tokens spanner.tokenlist GENERATED ALWAYS AS (spanner.tokenize_fulltext(albumtitle)) VIRTUAL HIDDEN,
  name character varying,
  namesoundex character varying GENERATED ALWAYS AS (lower(spanner.soundex(name))) VIRTUAL,
  namesoundex_tokens spanner.tokenlist GENERATED ALWAYS AS (spanner.token(lower(spanner.soundex(name))) VIRTUAL HIDDEN,
PRIMARY KEY(singerid));

CREATE SEARCH INDEX singersphoneticindex ON singers(albumtitle_tokens, namesoundex_tokens);

השאילתה הבאה מתאימה ל-"stefan" ל-"Steven" ב-SOUNDEX, יחד עם AlbumTitle שמכיל "cat":

GoogleSQL 

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

PostgreSQL 

SELECT singerid
FROM singers
WHERE namesoundex = lower(spanner.soundex('stefan')) AND spanner.search(albumtitle_tokens, 'cat')

המאמרים הבאים