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

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

בנוסף לביצוע חיפושים מדויקים של טוקנים באמצעות הפונקציות 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-גרמים ארוכים גורמים ל-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-grams מצב שאילתה משופר
עלות נדרשת טוקניזציה יקרה יותר של מחרוזת משנה שמבוססת על 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')

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