באחד הפרוייקטים שהיו לי במהלך התואר, הייתי צריך לבנות סוג של Crawler שיוריד כתבות (במקרה שלי כלכליות) מכל מיני אתרים שGoogle Finance מקשר אליהם. בהנתן כתובת האתר, להוריד את קוד המקור שלו זאת עבודה טכנית. אבל מה נעשה כשנרצה לבודד רק את הכתבה מתוך העמוד הנ"ל ? הרי הכתבה מצוייה בין עשרות\מאות טאגים שכוללים סקריפטים למיניהם, תפריטים של האתר וכו'.. איך נבודד את התוכן נטו מתוך כל הרעש מסביב ?
לי אישית היה קשה למצוא שיטה שתעבוד ברוב המקרים ורוב האתרים שנתקלתי בהם הביאו אותי לשיטות לא כ"כ טובות שעבדו בפחות מ50% מהמקרים (אפשרי שלא חיפשתי מספיק, אבל באותה תקופה חיפשתי די הרבה).
בסופו של דבר, הגעתי למאמר משנת 2009 על השיטה שאני אפרט למטה

המטרה

בידוד תוכן הכתבה מעמוד HTML אקראי

שיטות אפשריות

אם אנחנו מכירים את האתר, אז עם קצת פעולות טכניות אפשר להגיע בקלות לבידוד של כל כתבה מהאתר משום שנוכל לדעת איך האתר מייצג את הכתבות שלו (משתמש ב<div> או ב<p> ואיפה נמצאת הכותרת וכו'. יש אלגוריתמים שהם Supervised, כלומר לומדים, שבהנתן קלט מתוייג יכולים להגיע לדיוק מאוד גבוה.
המטרה שלנו היא למצוא שיטה שתעבוד באחוזים טובים על כל אתר.
יוריסטיקה אפשרית היא להסתכל על הטאגים שהתוכן שלהם הכי גדול.. מהצורה נניח <p> * </p> כשהאורך של * מקסמימלי. הבעיה היא שאין שום הבטחה שלא ישתרבבו לתוך התוכן טאגים שמכילים זכויות יוצרים וכו'.

השיטה שלנו

בידוד התוכן ע"י אלגוריתם Maximum Subsequence Segmentation.
רובינו שלמדו אלגוריתמים בסיסים\מבני נתונים באיזשהי מסגרת, נתקלו באותו אלגוריתם שמטרו בהנתן סדרת מספרים לבודד את התת סדרה (רצף מספרים) המקסימלית מתוך הסדרה הזאת. האלגוריתם די בסיסי והוא פשוט כולל ריצה על הסדרה ושמירת מונה של סכום נוכחי ומונה של הסכום המקסימלי שנתקלנו בו. ברגע שהמונה של הסכום הנוכחי עובר את המונה של הסכום המקסימלי, אנחנו שומרים את האינדקסים של הסדרה שהמונה הנ"ל סכם. ברגע שהמונה הנוכחי ירד מ0, מתחילים לספור מחדש ומעדכנים את אינדקס ההתחלה של הספירה הנוכחית.

פסאודוקד:

איך השיטה מיושמת על עמודי HTML?

נתחיל מזה שנמחק מהקוד מקור את כל הקטעים שהם מהצורה
<script> * </script> וכן מהצורה <style> * </style> שכן הקטעים האלה אף פעם לא יכילו תוכן רלוונטי לכתבה.
לאחר מכן, נכניס למערך את כל הטוקנים בקוד המקור (טוקן מבחינתנו הוא או טאג או מה שנמצא בין 2 טאגים). נייצר לכל טוקן ערך נומרי כשבמאמר בחרו לעשות את זה בצורה הבאה: טאג יקבל ערך נומרי 3.25- ואילו תוכן שבין טאגים יקבל 1 עבור עבור כל מילה או סימן בתוכו (ובסה"כ את מס' המילים + הסימנים), מהניסיון שלי אפשר לשחק עם הערכים האלה. עבור המערך הנ"ל של הערכים הנומריים נחשב MSS והקטע שנקבל יהיה הקטע של הכתבה + טאגים שנמצאים בין המשפטים (שאותם אפשר לנקות בקלות אח"כ)

מה האינטואיציה מאחורי זה ?

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

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


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

המאמר שלקחתי את השיטה ממנה (מדובר בBASELINE II ולא באלגוריתמים הלומדים):

Extracting Article Text from the Web with Maximum
Subsequence Segmentation
http://www2009.org/proceedings/pdf/p971.pdf

לפי איך שאני רואה את זה, השימוש שלך בשיטה היה כדי להוציא את הבשר של הכתבה מופרדת עם טוקנים בסיסיים (<p>, <div> וכו') במקום לרוץ על כל הטקסט ולהתעסק בזוטות. אני חושב שזה נחמד.