פרדיגמת קל כבד

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

דיווח המשולשים בגרף

האלגוריתם הנאיבי

triangle_report(G=(V,E))
	for each (u,v,w) in V
		if (u,v) and (v,w) and (u,w) are in E
			report triangle (u,v,w)

האלגוריתם הנאיבי הזה עונה על בעייה שדיברנו עליה בהקשר שלכפל מטריצות מהיר, בזמן זהה לזמן של זיהוי משולש אני יכול לדווח על המשולש עצמו. כמובן שזמן זה הוא $O(|V{|}^3)$

האלגוריתם הפחות נאיבי

ניתן לשים לב, לכך שזמן הריצה כלל לא תלוי במספר הקשתות בגרף ־ והרי ברור שאם בגרף אין בכלל קשתות למשל, אז אין סיבה שהאלגוריתם ייקח הרבה זמן. נרצה שהאלגוריתם יתחשב בקשתות הגרף. נשים לב לכך שכל משולש, אפשר להסתכל עליו כקשת "בסיס" $(u,v)$ וקודקוד שלישי $w$ במחובר בשתי קשתות אחרות לקשת הבסיס. אם כן בעזרת הבחנה זו יתקיים

triangle_report(G=(V,E))
	for each (u,v) in E
		for each w in V - {u,v}
			if (u,w) and (v,w) are in E
				report triangle (u,v,w)

זמן הריצה של אלגוריתם זה הוא $O(|V||E|)$ . נכונות האלגוריתם היא מיידית. אם הגרף צפוף אז לא שינינו את זמן הריצה ביחס לקודם. אבל בסבירות נמוכה שזמן הריצה יהיה זהה. אומנם סדר הריצה לא משנה כרגע, אבל יש לו חשיבות שנראה בהמשך.

האלגוריתם השלישי

באלגוריתם הקודם על כל קשת רצנו על כל הקודקודים האפשריים שוב ושוב בלי להתחשב בשכנים האופציונליים של $u,v$ שיכולים להרכיב איתם משולש וכך רצנו על הרבה קודקודים שלא לצורך.
נשים לב שאם הגרף מיוצג ברשימת שכנויות, וכל הרשימות ממוינות לפי סדר גלובלי של קודקודי הגרף, אזי ניתן לחשב חיתוך כזה במעבר אחד מסונכרן על שתי הרשימות שייקח $O(\mathrm{deg}(u)+\mathrm{deg}(v))$ זמן. אם הגרף מיוצג על ידי מטריצת שכנויות אז בכל מקרה ייקח $O(2|V|)=O(|V|)$ זמן. לכן נתמקד בייצוג של הרשימה.

אם כן מהבנה זו נבנה את האלגוריתם הבא

triangle_detection(G=(V,E))
	for each (u,v) in E
		for each w in (N(u) ∩ N(v))
			report triangle (u,v,w)

זמן הריצה יהיה $O(\sum _{(u,v)\in E}(\mathrm{deg}(u)+\mathrm{deg}(v)))$ .

אלגוריתם משולב

מההבחנה שהעלנו אנחנו מבינים שנרצה אלגוריתם שתלוי כמה שיותר במספר הקשתות וכמה שפחות במספר הקודקודים. זמן הריצה כתלות של במספר הקשתות במקרה הגרוע על גרף קליק הוא $\mathrm{\Omega }(|V||E|)=\mathrm{\Omega }(|E{|}^{1.5})$ .
באלגוריתם השלישי קיבלנו זמן ריצה שתלוי בדרגות הקודקודים. נשים לב שדרך אחת לחשוב על דרגות הקודקודים היא להזכר בכך שכל קשת תורמת 1 לדרגה של שני קצוותיה. לכן אפשר לחשוב שכאשר ידוע על גרף עם $|E|$ קשתות בעצם יש $2|E|$ "אסימונים" שמחלקים בין $|V|$ הקודקודים שמשפיעים על הדרגה של כל קודקוד. נחלק את קודקודי הגרף באופן הבא-

הגדרה - עבור $G$ גרף לא מכוון. לכל $v\in V$ נאמר ש

נזכר בלמת לחיצת הידיים שאומרת ש

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

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

למה בכל גרף יש לכל היותר $2\sqrt{|E|}$ קודקודים כבדים.
הוכחה-
מלמת לחיצת הידיים סכום הדרגות הוא $2|E|$ אם היה יותר קודקודים כבדים מ $2\sqrt{|E|}$ הרי שהיינו מקבלים מהגדרת קודקוד כבד ש

בסתירה ללמת לחיצת הידיים.

כעת, נפריד את המשולשים בגרף לשני סוגים גם כן:
• משולשים שמכילים קודקודים כבדים .
• משולשים שכל קודקודיהם קלים.

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

triangle_report(G=(V,E)):
	for each v in V:
		v.isHeavy = deg(v) > sqrt(|E|)
		
	for each w in V where w.isHeavy is true:
		for each (u,v) in E
			if (v,w) in E and (u,w) in E
				report triangle (u,v,w)
				
	for each (u,v) in E
		if u.isLite and v.isLite
			for each w in (N(u) ∩ N(v))
				report triangle (u,v,w)

נכונות
נכונות האלגוריתם נובעת מהעובדה שהיא משתמש באלגוריתמים שכבר הוכחנו את נכונותם. ראשית, בוודאות האלגוריתם לא מדווח על שלשה שאינה משולש בגלל הסיבה שתיארתי. כעת עבור משולש כלשהו $u,v,w$
אם אחד מהקודקודים כבד אז היינו שמים לב אליו בחלק הראשון של האלגוריתם. אחרת במעבר על הקשת $(u,v)$ למשל , נמצא את $w$ בחיתוך ונדווח על המשולש בחצי השני.

זמן ריצה
סריקת הגרף לצורך סיווג לוקח $O(|V|+|E|)$
השלב הראשון - $O(|V_{\text{heavy}}|\cdot |E|)=O(2\sqrt{E}|E|)=O(|E{|}^{1.5})$
השלב השני- $\sum _{(u,v)\in E}(\mathrm{deg}(u)+\mathrm{deg}(v))\le \sum _{(u,v)\in E}(\sqrt{|E|}+\sqrt{|E|})\le |E|\cdot 2\sqrt{|E|}=O(|E{|}^{1.5})$

סך הכל

מרחק האמינג עבור א״ב כללי

אם כן, בבעיית דיווח המשולשים התחלנו להבין מה הרעיון בפרדיגמת קל כבד.

• הגדרת ערך $c$ שקובע שכל מי שגדול ממנו יהיה קבע וכל מי שקטן ממנו יהיה קל.
• סיווג אוסף המידע לפי אותו $c$ ומציאת חסמים למספר האפשרויות שיקיימו כל אחד מהתנאים.
• אם ״כבד״ הרץ אלגוריתם א לחישוב בעייה כלשהי, אם ״קל״ הרץ אלגוריתם ב.

בהסבר על דיווח משולשים נתנו עובדה ואמרנו ש $c=\sqrt{|E|}$ וזה גם היה די אינטואיטיבי מלמת לחיצת הידיים. בבעיית מרחק האמינג נרצה כיצד מגיעים לערך של $c$ הזה וכיצד בחירתו מייעלת את האלגוריתם.
נזכיר שבפתרון לבעיות של FFT כבר הצגנו את מרחק האמינג על א״ב בינארי.
נרצה לפתור את בעיית מרחקי האמינג עבור המקרה הכללי שבו

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

אלגוריתם ראשון

ראינו כבר כיצד אפשר לפתור את בעיית FFT על א״ב גדול יותר למשל עבור $\mathrm{\Sigma }=\{0,1,2\}$ כל פעם רצנו על המחרוזת והחלפנו את כל הספרות פרט לספרה שאנחנו רוצים לבדוק ב $0$ ואת הספרה שנרצה לבדוק החלפנו ב $1$ וביצענו $FFT$ כמספר התווים במחרוזת. במקרה של הא״ב הנ״ל נקבל 3 פולינומי מכפלה שכל אחד מהם מייצג את מספר ההתאמות עבור תו כלשהו.
אם כן הרעיון על א״ב כללי הוא זהה פשוט ארוך יותר

סף הכל זמן הריצה יהיה מספר התווים במחרוזת כפול זמן הפעולה שלוקח לעשות FFT כלומר

נשים לב שנוכל לייעל את האלגוריתם הנ״ל על ידי ביצוע הבדיקה רק על ${\mathrm{\Sigma }}_P$ כלומר האותיות שנמצאות במחרוזת בלבד. אומנם במקרה הגרוע ב $P$ יש $m$ אותיות ונקבל זמן ריצה

האלגוריתם הנאיבי ביותר של השוואה פשוטה של ההיסטים מול הטקסט ייקח $O(m\cdot n)$ ולכן האלגוריתם הנ״ל לא תמיד מתאים לנו.
נשים לב אם כן, שהאלגוריתם הזה הוא טוב במקרים שבהם התבנית היא עם מספר קטן יחסית של אותיות מהא״ב וגרוע כאשר יש מספר גדול של אותיות מהא״ב. אנחנו לא יודעים בידיוק מה זה המספר הזה וכאן ייכנס לתמונה הסיווג לקל וכבד שהגדרנו מקודם.

אלגוריתם שני

נדגים על מקרה פשוט ואז נסביר.
נסתכל על מקרה שבתבנית יש בסה״כ מופע אחד של $a$ נגיד במיקום השלישי בתבנית.
נוכל לספור את ההתאמות של $a$ בין התבנית לטקסט באופן הבא: נבצע סריקה של הטקסט, כל פעם שנראה $a$ במיקום $i$ בטקסט נוסיף למערך מונים $1$ במיקום $M[i-3+1]$ .
אם למשל יש $a$ בתבנית בשתי אינדקסים במחרוזת $x,y$ ניתן לבצע סריקה דומה רק שכל פעם שרואים $a$ מוסיפים $1$ במיקומים $M[i-x+1],M[i-y+1]$ (ההוספה של $1$ היא כי נצא מהנחה שהאינדקס הראשון הוא $1$ ולא $0$, לא חייב אותו אם מתחילים מ $0$).
אם הפעולה הזאת זולגת בגבולות המערך לא מוסיפים בשום מקום כי זה יכול להעיד שבהמשך נתקל בתו הזה או שהוא לא תורם להיסט שאני נמצא בו.
נשים לב שעבור תווים נוספים למשל $b$ שנמצא באינדקס $j$ נוכל באותה סריקה לעדכן את מערך המונים עבורו.
נשים לב שמערך המונים $M$ יהיה בגודל $n-m+1$ מספר ההיסטים האפשריים, כמו באלגוריתם הקודם שכן המערך הזה יחזיק כמה התאמות היו לי לכל אחד מההיסטים האפשריים .

בעצם באופן ויזואלי זה ייראה כך

כאשר כל פעם שרואים $a$ בטקסט אנחנו מעלים ב$1$ את המונה במיקום שבו הוא יהיה בהיסט מסויים. החשיבות של ההזזה של האינדקס ב $M$ למעשה מטרתה נקשר בין המיקום שבו מצאנו את התו לבין המיקום היחסי של אותו תו ביחס להיסט למשל בתמונה ה $a$ השני שמצאנו משמעותו שבהיסט שמתחיל במיקום הזה יש התאמה.

דוגמה:
עבור $P=ab$ ו $T=abcdabe$
נאתחל מערך בגודל $7-2+1=6$ מאותחל באפסים. כעת נרוץ על $T$ באיטרצייה הראשונה והשנייה נזהה שיש לנו תווים מ $P$ ולכן לפי מה שאמרנו נעדכן את המערך $M$ ונוסיף מונה במיקומים

עדכנו את אותו האינדקס עבור שתי התווים כיוון שהם מיוצגים על ידי אותו ההיסט כלומר $M[1]$ מייצג את ההיסט שמתחיל מהתו במיקום ה $1$ ב $T$ . באופן דומה יקרה גם על האינדקסים $5,6$ ב $T$ כלומר $M[1]=M[5]=2$ וסך הכל $M$ בסוף הריצה יהיה

ומשמעות הדבר היא שבהיסט במיקום הראשון יש שתי התאמות וההיסט במיקום החמישי הוא עם שתי התאמות וכל השאר בלי התאמות בכלל.

נשאלת השאלה איך מנהלים את זה באופן כללי?
כלומר נרצה לדעת בכמה מיקומים נמצא כל תו שאנחנו רואים ב $T$ ב $P$ , להחזיק את זה במבנה נתונים כלשהו שיאפשר איטרצייה על האינדקסים הללו ולעדכן את $M$ לפיהם.

באופן פורמלי: נסמן לכל $\sigma \in \mathrm{\Sigma }$ את מספר המופעים שלו בתבנית כ $c(\sigma )$ ואת המופעים עצמם באינדקסים

בהנחה והא״ב סופי (בסבירות גבוהה שהוא יהיה) נוכל להחזיק מערך של רשימות מקושרות שהאינדקס ה $j$ במערך יחזיר את רשימת האינדקסים של התו ה$j$ בא״ב (לצורך הנוחות נסתכל על א״ב כקבוצה סדורה כמו האותיות באנגלית ועברית שאנחנו מכירים או תווי ASCII) . נשים לב שהרשימה מחזירה את האינדקסים לפי הסדר שלהן ב $P$ . בניית המבנה הזה דורשת ריצה אחת על התבנית כלומר $O(m)$ זמן ולכן לא תשפיע על יעילות האלגוריתם.

נשים לב שהאלגוריתם הזה לא יעיל במיוחד אם אנחנו יודעים שאות מסויימת בתבנית יכולה להופיע מספר רב מאוד של פעמים למשל עבור $P=aaaaaa\dots a$ האלגוריתם הראשון עדיף על השני שכן אפשר לבצע FFT על תו אחד במחרוזת בעוד שכאן נבצע את כל הבנייה של המבנה הזה ונרוץ על כל התווים בטקסט ובתבנית שלא לצורך. יתרה מכך , על כל $a$ שיימצא בטקסט אנחנו נרוץ על כל האינדקסים שוב ושוב ושוב ברשימה המקושרת של האינדקסים שלו.

באופן פורמלי, אם מספר המופעים של כל אות בתבנית חסום ב $c$ אז זמן הריצה הכולל לספירת המופעים של כל האותיות הוא $n\cdot c$ . במקרה שלא נתון שום חסם $c=O(m)$ וסה״ ניתן לחסום את זמן הריצה של האלגוריתם ב $O(nm)$ .

אלגוריתם קל כבד

קיבלנו אם כן עבור הבעייה שלנו שתי אלגוריתמים שבמקרה הגרוע שלהם רצים בזמן $O(nm)$ ו $O(nm\log m)$ אבל המקרה הטוב שלהם מאוד יעיל. נרצה אם כן להגדיר ערך סף $c$ שיאפשר לנו לסווג על איזה תווים נוכל להשתמש באלגוריתם הראשון ועל איזה בשני. אם כן נחלק את האותיות כך

• אותיות שמופיעות בתבנית יותר מ $c$ פעמים ייקראו כבדות
• אותיות שמופיעות בתבנית פחות מ $c$ פעמים ייקראו קלות.

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

הבחנה: בשלב 5 אפשר גם לרוץ על ${\mathrm{\Sigma }}_P$.

זמן הריצה של האלגוריתם יהיה אם כן, מספר התווים הכבדים כפול זמן הריצה של האלגוריתם הראשון פלוס זמן הריצה של האלגוריתם השני על התווים הקלים. נשים לב שכמו בבעיית המשולשים גם כאן ניתן להגיד שמספר התווים הכבדים הוא לכל היותר $\frac{m}{c}$ אחרת נקבל שמספר התווים בתבנית גדול מ$m$ בסתירה.

כעת נרצה לבחור $c$ שעבורו הביטוי $\frac{m}{c}\log (m)+c$ יהיה מזערי. נשים לב שככל שמגדילים את האיבר הימני בביטוי ככה השמאלי קטן. אם כן כיוון שעובדים בזמנים אסימפטוטיים כלומר כש $c$ מספר מאוד גדול,
הערך המינימלי ביותר מתקיים כאשר הביטויים הנ״ל שווים , שכן אם נגיד ש $c$ מספר מאוד קטן , שואף ל 0 אז ביטוי שמאל ישאף לאינסוף אחרת אם נגיד ש c מספר מאוד ביטוי ימין ישאף לאינסוף לכן נרצה את נקודה איזון בינהם.

כלומר נבחר $c$ שיהיה הערך הנ״ל ואיתו נסווג את התווים. סך הכל לאחר הצבה נקבל שזמן הריצה הוא $O(n\sqrt{m\log m})$.