שאזאם - חלק ב׳
27/02/2018
בפוסט הקודם למדנו איך שומרים מוזיקה בפורמט דיגיטלי. היום נלמד איך שאזאם משתמש בייצוג הזה כדי לזהות שירים מהר.
בגישה של שאזאם יש שני רכיבים עיקריים, השרת והלקוח. השרת הוא קטלוג ענק שמכיל את כל האינפורמציה הדרושה לנו כדי לזהות שיר. הלקוח הוא הטלפון שמקשיב לשיר, ומחלץ ממנו אינפורמציה שאיתה אפשר לבצע את הזיהוי. השאלות הגדולות הן - איך נשמור את המידע על השרת, איך נחשב את האינפורמציה מתוך ההקלטה של השיר, ואיך נבצע את החיפוש בקטלוג באופן יעיל?
כאשר הטלפון שלנו מקליט חתיכה מהשיר, הוא שומר אותה בצורת ספקטרוגרמה [ראו פוסט קודם]. הדבר הראשון שצריך להבין הוא שהספקטרוגרמה מכילה מספיק מידע כדי לשחזר את השיר באופן כמעט מדוייק. שאזאם לא צריך את כל האינפורמציה הזו, רק מספיק כדי לזהות את השיר. זה כמו ההבדל בין לזהות אדם מוכר לפי כמה פרטים מזהים לבין לצייר דיוקן מושלם שלו. אם אני אגיד משהו על החבר הזה שלכם שהוא קצת נמוך, ג'ינג'י ועם עיניים כחולות זה עשוי להספיק לכם בשביל לדעת על מי אני מדבר, אבל אף אחד (אחר) לא יוכל להרכיב מהתמונה הזאת קלסתרון של אותו החבר. באותו אופן, שאזאם לא צריך לדעת הכל על השיר כדי לדעת להבדיל בינו לבין שאר השירים שהוא מכיר.
אז איך נמצה מתוך הספקטרוגרמה מספיק מידע כדי לזהות את השיר? הדבר הראשון ששאזאם עושה הוא לזהות את הנקודות הכי בולטות בספקטרוגרמה ולזכור רק אותן. לכל נקודה כזו אנו זוכרים רק את הזמן ואת התדר, אפילו לא עד כמה התדר חזק. הציור שמתקבל נקרא "הקונסטלציה" של השיר, בגלל הדמיון שלו לשרטוט של קבוצות כוכבים (קונסטלציות, בלעז).
אחת התכונות היפות של קונסטלציה כזו היא שהיא די עמידה לרעשים. תנאי סאונד נחותים עשויים להבליט תדרים מסויימים על פני אחרים, אבל הם לרוב לא יעלימו את התדרים הכי דומיננטיים בשיר. זה מוביל באופן טבעי לפתרון הבא: בהנתן הקלטה, נשמור את הקונסטלציה שלה ונשלח אותה לשרת. השרת יחפש שיר עם חתימה כזו וסיימנו. כמות המידע שאנחנו שולחים קטנה, והשרת אפילו לא צריך לעבור על כל החתימות. טכניקה בשם גיבוב [1] מאפשרת לנו לאחסן את המידע בצורה כזו שהתרגום של החתימה בחזרה לשיר יהיה מאוד מהיר, גם אם יש לנו המון שירים.
אבל זה עדיין משאיר שאלה אחת פתוחה - איך שאזאם יודע לזהות את השיר בעזרת חתיכה קטנה ממנו? היות ועכשיו אין לנו את כל הקונסטלציה, אלא רק חלק ממנה, הטכניקות של הגיבוב לא יעזרו לנו יותר. נראה שהפתרון הוא שוב לעבור אחת אחת על החתימות, ואם זה לא מספיק גרוע, אז לרוץ על כל חתימה ולחפש בתוכה חתיכה שנראית כמו המידע החלקי שלנו.
כאן מגיע הפתרון הפשוט אך מבריק של שאזאם: במקום להסתכל על כל נקודה בקונסטלציה נסתכל על זוגות של נקודות קרובות. הדרך בה נעשה זאת היא לבחור כמה "נקודות עוגן". אחרי זה, נקח כל נקודת עוגן ולכל אחת מהנקודות לפני נקודת העוגן הבאה נשמור את הפרש הזמנים והפרש התדירויות בין שני הנקודות האלו. כל אוסף כזה, של נקודת עוגן ביחד עם ההפרשים מכל הנקודות שאחריה, נקרא "טביעת אצבע" של השיר. השרת שומר לכל שיר רשימה של טביעות אצבע כאלו. בשיר יש טביעות אצבע רבות, שכל אחת מהן מחושבת מחתיכה אחרת של השיר. לכן מספיק להאזין רק לחתיכה קטנה מהשיר כדי למצות ממנו טביעת אצבע שאפשר לשלוח לשרת ולבקש ממנו להזות באמצעותה את השיר.
זה משאיר רק שאלה אחת - איך נבחר את נקודת העוגן שלפיה נחשב את טביעת האצבע הזו? זה לא ממש חשוב מי נקודת העוגן, אבל כן חשוב שהמכשיר הסלולרי יבחר נקודה מנקודות העוגן שהשרת השתמש בהן בשביל לחשב את תביעת האצבע. לצערנו, זה סוד מסחרי של חברת שאזאם, ורק הם יודעים איך זה נעשה בדיוק.
קריאה נוספת:
מקורות:
דוקטורנט בחוג למדעי המחשב באוניברסיטה העברית. מתעניין במחשוב קוואנטי. במהלך התואר השני שלו, עסק שי בחקר לוגיקה מתמטית, בפרט, תורת המודלים.
