מרוץ ויקיפדיה

מרוץ ויקיפדיה

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

אני רוצה ליישם את זה בקוד, כמובן.

אלגוריתמיקה

אפשר להסתכל על הבעיה כמו על בעיית עצים/גרפים – מציאת המסלול הכי קצר. כל דף אינטרנט (של ערך בויקיפדיה) הוא node בעץ, וה״ילדים״ שלו הם הקישורים לערכים שנמצאים בדף. כדי לעבור על עץ,  אפשר לנסות חיפוש לעומק (DFS) או חיפוש לרוחב (BFS).

wiki_tree
ערך מוביל לעוד ערך שמוביל לעוד הרבה ערכים

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

קוד

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

def getAnchors (url):
    status, response = http.request(url)
    soup = BeautifulSoup(response, 'html.parser')
    return set(soup.find_all('a', href=re.compile(r"^/wiki/.*[^.jpg]$")))

הפונקציה הזו מקבלת url, ומחזירה anchors – תגיות <a> שנמצאים באותה הכתובת – תוך כדי סינון של כתובות שלא נחוצות לנו (כמו תמונות).

הסינון הזה לא מושלם, לכן נוסיף את הפונקציה הזו:

def isValue (value):
    link = value.get('href')
    return value.parent.get('class') != 'citation web' and value.parent.get('class') != 'citation book' and value.parent.get('class') != 'reference-text' and not 'Category:' in link and not 'Special:' in link and not 'Help:' in link and link != '/wiki/Main_Page' and not link in checkedUrls

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

פתרון נאיבי

נתחיל מהפתרון הפשוט יותר:

def naiveLookForUrl (original, dest, deep, path):
    toRet = MAX_DEEP + 1
    if (deep &gt; MAX_DEEP or original in checkedUrls):
        return toRet
    print "try deep of " + str(deep) + " with path: " + urllib.unquote(str(path)).decode('utf8')
    checkedUrls.append(original)
    for link in getAnchors(original):
        if not isValue(link):
            continue
        href = link.get('href')
        newList = path[:]
        newList.append(PREFIX + href)
        if (PREFIX + href == dest):
            print "found!! deep: " + str(deep) + " path: " + str(newList)
            return deep
        d = naiveLookForUrl(PREFIX + href, dest, deep + 1, newList)
        if (d &lt; toRet):
            toRet = d
    return toRet

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

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

פתרון משופר

פתרון יעיל יותר יהיה לעבור על העץ לרוחב (BFS):

def betterLookForUrl (curList, dest, deep):
    curDeep = deep
    found = False
    while found == False:
        if (curDeep &gt; MAX_DEEP):
            print "MAX deep!!!!"
            return []
        nextList = []
        for address in curList:
            url = address[-1]
            if not url.startswith(PREFIX):
                url = PREFIX + url
            if url == dest:
                found = True
                print "FOUND!!!"
                return address + [link]
            for a in getAnchors(url):
                link = a.get('href')
                if isValue(a):
                    if PREFIX + link == dest:
                        found = True
                        print "FOUND!!!"
                        return address + [link]
                    nextList.append(address + [link])
                    #print "adding to list: " + str(address + [link])
                    checkedUrls.append(link)
        curDeep += 1
        curList = nextList
    return []

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

גם לפונקציה הזו ייקח זמן לא מבוטל למצוא תוצאה. ניסיתי למצוא את המסלול הקצר ביותר מבלייד ראנר לאוסטאופורוזיס וזה לקח למעלה מ- 7 שעות (!!).

את הקוד במלואו אפשר למצוא כאן.

Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedIn

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *