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