יום ראשון, 26 בפברואר 2012

Search Engine Spider

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

נעים להכיר - עכביש (Spider).
Spider - זו תוכנית שרצה לה ברחבי האינטרנט וקוראת את תוכן ה HTML ומפרקת אותו לחלקי מפתח ע"י החוקים שתכננו לה מראש כשבסוף המידע שנאסף נאגר במסדי נתונים ענקיים שבהם הלקוחות עושים את החיפושים, תהליך בניית ה Spider יכול להפוך למורכב מאוד ובתוכו חוקים רבים לגבי חיתוך דפי Html, במאמר זה נעבור בקצרה כיצד לממש מנוע חיפוש בעצמנו ונכיר את המנגנונים שבו.

באיזה פלטפורמה ניתן לממש Spider?
האמת היא שרוב השפות מאפשרות לנו יצירת Spider , ניתן גם להשתמש בשפות Scripts לדוגמה Perl , החלטתי להשתמש בפלטפורה של .Net שניתן לממש בה Spider בפשטות.

יופי טופי אבל בואו נדבר תכלס, בעצם מדובר בסוג של כדור שלג, תחילה טוענים Url ראשוני ל Spider  ולאחר מכן ה Spider מתחיל לעבוד, תחילה הוא מבצע Request לדף וממתין ל Response מהשרת, כשמגיע ה Response הוא מכיל את קוד ה Html , ה Spider מתחיל לחתוך חלקים מה Html בעזרת Regular Expression (נעבור עליהם בהמשך) ובסוף הוא אוגר רשימת Links (לדוגמה תגיות href) , כשמסתיים תהליך העיבוד הוא עובר ל Link הבא וכך הלאה.



שלב א: יצירת חיבור וקבלת Html.

 public string Html(string incomingCharset,string incomingWebsite)
        {
            try
            {
                if (incomingCharset != "")
                {
                    WebClient Client = new WebClient();
                    string Temphtml = "";
                    Client.Encoding = Encoding.GetEncoding(incomingCharset);
                    Temphtml = Client.Encoding.GetString(Client.DownloadData(incomingWebsite));
                    Client.CancelAsync();
                    return Temphtml;
                }
                else
                    return "";
            }
            catch (Exception ex)
            {
                return "";
            }
         
       
        }

הפונקציה תחזיר לנו את ה Html המלא של הדף בעזרת 2 פרמטרים , הפרמטר הראשון הוא ה CharSet עבור קידוד הטקסט לדוגמה: Windows-1252 , והשני הוא הכתובת של האתר שאנחנו רוצים לסרוק לדוגמה:  http://www.google.co.il/, בסיום התהליך יהיה לנו את ה Html עליו נבצע מניפולציות בעזרת Regular Expression.

 שלב ב: ביטויים רגולרים
ביטויים רגולרים (Regular Expression) הם בעצם סוגים של Patterns שמאפשרים לבצע חיתוכים על מחרוזות בצורה מהירה ויעילה לדוגמה: בדיקת תקינות ל Email, מספר טלפון, ת"ז וכו', אני לא אפרט על צורת הכתיבה של ביטויים רגולרים כי זה עולם ומלואו (למי שלא יכול להתאפק אפשר להתחיל כאן)  אבל אני מקווה להקדיש זמן בעתיד עבור נושא מרתק זה.

ריכזתי מספר Patterns מעניינים עבור ה Spider שלנו:

 public string MetaData(string IncomingHtml)
{
return new Regex("content\\s*=\\s*(?:\"(?<1>[^\"]*)\"|(?<1>\\S+))", RegexOptions.IgnoreCase).Match(IncomingHtml).Value.Trim();
}
* מחזיר תגית Metadata.

public string Title(string IncomingHtml)
{
return new Regex("(?<=<title.*>)([\\s\\S]*)(?=</title>)", RegexOptions.IgnoreCase).Match(IncomingHtml).Value.Trim();
}
* מחזיר תגית Title.

public string H1(string IncomingHtml)
{
return Regex.Replace(new Regex("(?<=<h1.*>)([\\s\\S]*)(?=</h1>)", RegexOptions.IgnoreCase).Match(IncomingHtml).Value.Trim(), "<.*?>", string.Empty).Trim();
}
* מחזיר תגית H1.

public string H2(string IncomingHtml)
{
return Regex.Replace(new Regex("(?<=<h2.*>)([\\s\\S]*)(?=</h2>)", RegexOptions.IgnoreCase).Match(IncomingHtml).Value.Trim(), "<.*?>", string.Empty).Trim();
}
* מחזיר תגית H2.

public string P(string IncomingHtml)
{
return Regex.Replace(new Regex("(?<=<p.*>)([\\s\\S]*)(?=</p>)", RegexOptions.IgnoreCase).Match(IncomingHtml).Value.Trim(), "<.*?>", string.Empty).Trim();
}
* מחזיר תגית P.

public string TD(string IncomingHtml)
{
return Regex.Replace(new Regex("(?<=<td.*>)([\\s\\S]*)(?=</td>)", RegexOptions.IgnoreCase).Match(IncomingHtml).Value.Trim(), "<.*?>", string.Empty).Trim();
}
* מחזיר תגית TD.

הבעיה עם סוג כזה של Pattern שהוא תמיד יחזיר לנו רק ערך אחד, מה יקרה אם נרצה להחזיר מערך מלא של כל הלינקים בדף? במקרה זה נשתמש ב Patterm הבא:

public ArrayList HRefs(string incomingHtml)
    {
      ArrayList arrayList = new ArrayList();
      string pattern = "href\\s*=\\s*(?:\"(?<1>[^\"]*)\"|(?<1>\\S+))";
      for (Match match = Regex.Match(incomingHtml, pattern, RegexOptions.IgnoreCase | RegexOptions.Compiled); match.Success; match = match.NextMatch())
      {
        string str = match.Groups[1].Value;
        arrayList.Add((object) str);
      }
      return arrayList;
    }

* אפשר להשתמש ב Pattern זה גם על שאר התגיות שכבר ראינו.

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

סיכום (קצר מאוד):
אז מה ראינו? שמימוש של מנוע חיפוש הוא לא בשמיים מבחינה תכנותית אבל מאוד אדגרי בכל הקשור למסד הנתונים, שמירת מיליונים של חיתוכים ומניפולציות על עמודי Html מצריך חומרה חזקה ותחזוקה רצינית, במאמר זה עברנו על הטכניקה הבסיסית למימוש מנועי חיפוש.

בהצלחה במכה!

2 comments: