Spiderman: ein Webcrawler mit eigener Suchmaschine

Was du hier lernst

• HTML parsen mit Beautiful Soup
• SQL mit sqlite3
• Rekursion
• async und await
• Relevanz nach Häufigkeit und Position
• robots.txt

Die Erklärung stammt – leicht überarbeitet für Python 3 – aus dem Buch „Coding for Fun mit Python“ von Lars Heppert, Kapitel 9, Abschnitte 9.1 bis 9.5.

Spiderman

»Aus großer Kraft folgt große Verantwortung.« – aus dem Film »Spiderman«, gilt aber auch für Google

In diesem Kapitel entwickeln wir eine kleine Suchmaschine. Sie sucht ausgehend von einer Startadresse selbstständig weitere Seiten und indiziert sie nach den Wörtern, die darauf vorkommen. Für das Zerlegen der Seiten verwenden wir Beautiful Soup, eine frei verfügbare Bibliothek zum Parsen von HTML, und für die Daten die Datenbank SQLite, die bei Python gleich dabei ist.

Webcrawler – folge den Zeichen

HTML ist die Sprache, in der Webseiten beschrieben sind. Sie strukturiert vor allem den Inhalt; für das Layout hat sich CSS etabliert. HTML ist allerdings oft nicht wohlgeformt: Nicht jedes Tag wird geschlossen, und viele Seiten enthalten schlicht Fehler. Suchmaschinen müssen trotzdem alles lesen können.

Ein Webcrawler ist im Grunde sehr einfach aufgebaut. Er sucht auf den Seiten, die er kennt, nach Links und nach Wörtern. Den Links folgt er, sodass er auch die verlinkten Seiten indiziert. Beim Indizieren merkt er sich zu jeder Seite die vorkommenden Wörter, wie oft sie vorkommen und wo sie zum ersten Mal auftauchen. Auch die Verlinkung der Seiten untereinander landet in der Datenbank.

Im Buch startete der Crawler bei chessbase.de und suchte nach »Kasparov«. Im Browser geht das nicht: Ein Programm auf einer Webseite darf nur Seiten von derselben Adresse abrufen. Unser Spiderman crawlt deshalb diese Website hier – dazu weiter unten mehr.

Beautiful Soup – Suppe?!

Die Verwendung der Bibliothek ist denkbar einfach. Der Crawler lädt eine Seite und übergibt den HTML-Text an BeautifulSoup:

text = await c.string()
soup = BeautifulSoup(text, "html.parser")

Über das Objekt soup erreichst du alle HTML-Elemente. soup.title liefert das Title-Tag der Seite, und soup('a') gibt eine Liste aller Links zurück – Links stehen in HTML im Tag <a>. Genauso lassen sich alle anderen Tags als Liste abrufen.

Für die Wortsuche brauchen wir nur den reinen Text. Diese Aufgabe übernimmt getTextOnly(). Die Methode arbeitet rekursiv: Hat ein Element genau einen Text, gibt sie ihn zurück. Sonst ruft sie sich für alle enthaltenen Elemente selbst auf und hängt die Ergebnisse aneinander:

v = soup.string
if v == None:
    c = soup.contents
    c = filter(noscript, c)
    c = filter(nostyle, c)
    resulttext = ''
    for t in c:
        subtext = self.getTextOnly(t)
        resulttext += subtext + '\n'
    return resulttext
else:
    return v.strip()

Dabei blendet sie JavaScript und Style-Sheets aus, die nicht zum Inhalt einer Seite gehören. Das erledigt filter() mit den beiden kleinen Funktionen noscript() und nostyle(), die für <script>- und <style>-Elemente False liefern.

SQL – die Daten im Griff

Alle Daten des Crawlers landen in Tabellen der Datenbank SQLite. Der Zugriff läuft über SQL, die Structured Query Language: Man öffnet eine Verbindung, erzeugt einen Cursor und kann darüber Daten schreiben und lesen. Beim Start legt die Klasse die Tabellenstruktur an:

self.cursor.execute("""CREATE TABLE webIndex
                       (id INTEGER PRIMARY KEY,
                        website INTEGER,
                        word INTEGER, count INTEGER,
                        position INTEGER)""")

Jede Tabelle bekommt in der ersten Spalte einen Primärschlüssel id, den SQLite selbst vergibt. Er ist eindeutig und dient als zuverlässige Referenz auf eine Zeile. Die Tabelle websites enthält alle besuchten Seiten, webIndex verknüpft Wörter mit Seiten – samt Häufigkeit und Position des ersten Auftretens –, und webLinks speichert, welche Seite auf welche verweist. Die Tabelle words legt das Programm zwar an, benutzt sie aber noch nicht.

Geschrieben wird mit INSERT. Die Fragezeichen sind Platzhalter, für die execute() die Werte einsetzt. Erst commit() schreibt die Daten dann wirklich fest. So wahren Datenbanken die Transaktionssicherheit: Entweder werden alle zusammengehörigen Änderungen übernommen oder keine. Stell dir eine Überweisung vor – ohne Transaktion könnte ein Fehler zwischen Abbuchung und Gutschrift das Geld im Nirvana verschwinden lassen.

Gelesen wird mit SELECT. fetchall() liefert alle Treffer auf einmal, fetchone() einen nach dem anderen – das spart Speicher, wenn die Ergebnismenge sehr groß ist. Noch bequemer ist es, mit for row in cursor: direkt über den Cursor zu laufen.

Indizieren – das war mir jetzt zu viel Text!

Was sollte die Einordnung einer Seite beeinflussen? Üblich sind die Häufigkeit eines Suchbegriffs und seine Position im Text: Je häufiger und früher ein Begriff auftaucht, desto wichtiger ist er in der Regel. Google wertet zusätzlich aus, wie viele Seiten auf eine Seite verlinken, und gewichtet Links von oft verlinkten Seiten höher – der sogenannte Pagerank.

Die Suche selbst übernimmt find(). Weil die Daten normalisiert über mehrere Tabellen verteilt sind, führt ein JOIN sie wieder zusammen:

sql = """SELECT wi.count, wi.position, ws.url
         FROM webIndex wi
         JOIN websites ws ON ws.id = wi.website
         WHERE wi.word = ?
         ORDER BY wi.count DESC"""

Das eigentliche Indizieren erledigt crawl(). Die Methode arbeitet rekursiv und prüft deshalb zuerst ihre Abbruchbedingung – ohne sie liefe die Rekursion endlos, bis Python mit »maximum recursion depth exceeded« aufgibt. Der Parameter depth gibt die Linktiefe an: Bei 2 werden die Startseite und alle von ihr verlinkten Seiten indiziert. Das Web ist eigentlich kein Baum, sondern ein Graph mit Zyklen. Das stört aber nicht, denn isNotIndexed() verhindert, dass eine Seite zweimal indiziert wird.

Für jede neue Seite geht es dann Schlag auf Schlag: Text herauslösen, in Wörter zerlegen, zählen, speichern.

text     = self.getTextOnly(soup)
words    = self.separateWords(text)
wordList = self.countWords(words)
self.associateWordsWithLink(link, wordList)

separateWords() zerlegt den Text mit einem regulären Ausdruck an allen Zeichen, die keine Buchstaben oder Ziffern sind, und wandelt alles in Kleinbuchstaben um. Viele Sonderfälle bleiben dabei auf der Strecke: Aus »C++« wird »c«, und Worttrennungen werden nicht erkannt. Für den Anfang genügt das. countWords() zählt alle Wörter mit mehr als fünf Buchstaben und merkt sich die Position ihres ersten Auftretens. Kurze Füllwörter wie »und« oder »der« fallen so von selbst heraus.

Zum Schluss folgt der Crawler den Links. Jeder Link wird auf das Wesentliche gekürzt – ohne Anker und ohne Daten, die per GET übergeben werden. Anker sind Sprungpunkte innerhalb einer Seite und spielen keine Rolle, weil immer die ganze Seite indiziert wird. Relative Links wie /beispiele/snake/ ergänzt urljoin() zur vollständigen Adresse. Im Buch wurden relative Links noch verworfen – und ich hatte damals angeregt, sie aus den vorhandenen Informationen zu ergänzen.

Höflich crawlen

Ein Crawler ist zu Gast auf fremden Servern und sollte sich entsprechend benehmen. Drei Regeln hält Spiderman ein:

• robots.txt: Unter dieser Adresse legt jede Website fest, was Crawler besuchen dürfen. Das Modul urllib.robotparser liest die Datei, und self.robots.can_fetch() fragt vor jedem Abruf nach. Diese Website sperrt zum Beispiel den Pfad /r/.
• Pausen: Zwischen zwei Abrufen wartet der Crawler eine Zehntelsekunde, statt den Server mit Anfragen zu überschütten.
• Grenzen: Mehr als 25 Seiten ruft er nicht ab.

Dazu kommt eine Regel, die der Browser selbst durchsetzt: die Same-Origin-Policy. Ein Programm auf einer Webseite darf nur Seiten von derselben Adresse laden, außer der fremde Server erlaubt es ausdrücklich (CORS). isSameSite() sortiert fremde Adressen deshalb gleich aus – und dazu alles, was nicht auf / endet, also Bilder und andere Dateien.

Was denn noch?

Ideen gibt es genug. Du könntest das erwähnte Pageranking einführen: Die Tabelle webLinks enthält bereits alles, was du dafür brauchst. Oder du sortierst die Ergebnisse nach verschiedenen Kriterien und gewichtest sie gegeneinander – Häufigkeit, erstes Auftreten, Zahl der eingehenden Links. Bei Suchen nach mehreren Wörtern lässt sich auch der Abstand zwischen den Suchbegriffen einbeziehen; die gespeicherte Position des ersten Auftretens reicht dafür schon aus.

Bevor du Neues einbaust, lohnt sich ein wenig Aufräumen: crawl() ist eindeutig zu lang und ein guter Kandidat für Refactoring. Beim Aufräumen verstehst du den Code noch besser als beim Lesen. Teste dabei jede kleine Änderung sofort – dann merkst du gleich, was du verbessert hast.

Probier mal

Jede Variante ändert den Code oben. Ein Klick auf »Ausprobieren« übernimmt die Änderung in den Editor und startet das Programm. »Zurücksetzen« holt das Original zurück.

1. 01Nach etwas anderem suchen

   Die Suche findet nur Wörter mit mehr als fünf Buchstaben, denn nur die hat der Crawler indiziert. Probiere eigene Begriffe – Groß- und Kleinschreibung spielen keine Rolle.

   - for term in ["Minimax", "Goethe", "Schlange"]:
   + for term in ["Fraktal", "Verschlüsselung", "Pendel", "Python"]:

   Ausprobieren

2. 02Nach dem ersten Auftreten sortieren

   Das Buch schlägt vor, die Treffer nach verschiedenen Kriterien zu sortieren. Statt nach der Häufigkeit ordnet die Suche jetzt nach der Position: Seiten, auf denen der Begriff früh auftaucht, stehen oben – oft ein guter Hinweis darauf, worum es auf einer Seite geht.

   -                  ORDER BY wi.count DESC"""
   +                  ORDER BY wi.position ASC"""

   Ausprobieren

3. 03Die meistverlinkten Seiten

   Die Tabelle webLinks speichert, welche Seite auf welche verweist. Zählt man die eingehenden Links, hat man ein vereinfachtes Pageranking, wie es das Buch in Abschnitt 9.5 anregt. Damit alle Links gezählt werden, speichert der Crawler jetzt auch Links zu Seiten, die er schon kennt.

   -                         if self.isSameSite(url) and self.isNotIndexed(url):
   -                             newpages.append(url)
   -                             description = self.getTextOnly(outgoingLink)
   -                             self.saveLink(link, url, description)
   +                         if self.isSameSite(url):
   +                             description = self.getTextOnly(outgoingLink)
   +                             self.saveLink(link, url, description)
   +                             if self.isNotIndexed(url):
   +                                 newpages.append(url)
   - for term in ["Minimax", "Goethe", "Schlange"]:
   + print("Die meistverlinkten Seiten:")
   + crawler.cursor.execute("""SELECT ws.url, COUNT(*) AS links
   +                           FROM webLinks wl
   +                           JOIN websites ws ON ws.id = wl.outgoingLink
   +                           GROUP BY wl.outgoingLink
   +                           ORDER BY links DESC LIMIT 8""")
   + for url, links in crawler.cursor:
   +     print("%4d Links auf %s" % (links, urlparse(url).path))
   + print()
   + 
   + for term in ["Minimax", "Goethe", "Schlange"]:

   Ausprobieren

4. 04Die häufigsten Wörter der Website

   Mit SQL lässt sich der ganze Index auf einmal auswerten. GROUP BY fasst alle Einträge eines Worts zusammen, SUM(count) addiert die Vorkommen über alle Seiten und COUNT(*) zählt, auf wie vielen Seiten es steht. Welche Wörter hättest du oben erwartet?

   - for term in ["Minimax", "Goethe", "Schlange"]:
   + print("Die häufigsten Wörter der ganzen Website:")
   + crawler.cursor.execute("""SELECT word, SUM(count) AS total, COUNT(*) AS pages
   +                           FROM webIndex
   +                           GROUP BY word
   +                           ORDER BY total DESC LIMIT 12""")
   + for word, total, pages in crawler.cursor:
   +     print("%6d-mal auf %2d Seiten: %s" % (total, pages, word))
   + print()
   + 
   + for term in ["Minimax", "Goethe", "Schlange"]:

   Ausprobieren

'''
Created on 17.01.2010

@author: sourcer
'''
import operator
import urllib2
import re

import sqlite3
from BeautifulSoup import BeautifulSoup

class spiderman(object):
    def __init__(self, createDatabase=False):
        self.connection  = sqlite3.connect("crawler.db")
        self.cursor      = self.connection.cursor()
        
        if createDatabase:
            self.cursor.execute("""CREATE TABLE websites
                                (id INTEGER PRIMARY KEY, url TEXT)""")
            self.cursor.execute("""CREATE TABLE words
                                (id INTEGER PRIMARY KEY, word TEXT)""")            
            self.cursor.execute("""CREATE TABLE webIndex
                                (  id INTEGER PRIMARY KEY, website INTEGER,
                                 word INTEGER, count INTEGER, position INTEGER)""")
            self.cursor.execute("""CREATE TABLE webLinks
                                  ( id INTEGER PRIMARY KEY,
                                    link INTEGER,
                                    outgoingLink INTEGER,
                                    description TEXT )""")
            self.connection.commit()
    
    def __del__(self):
        self.connection.close()
        
    def find(self, text):
        text = text.lower()
        sql = """ SELECT wi.count, wi.position, ws.url
                  FROM webIndex wi
                  JOIN websites ws ON ws.id=wi.website 
                  WHERE wi.word='""" + str(text) + "'" 
        self.cursor.execute(sql)
        
        return self.cursor.fetchall()
        
    def crawl(self, links, depth=2):
        if depth == 0:
            return
        
        newpages    = []     
        for link in links:
            if self.isNotIndexed(link):
                try:
                    c = urllib2.urlopen(link)
                except:
                    print "Could not open %s" % link
                    continue
                try:
                    text = c.read()
                    soup = BeautifulSoup(text)
                except Exception, arg:
                    print "Could not parse %s" % link
                    print Exception, arg
                    continue
                
                text        = self.getTextOnly(soup)
                words       = self.seperateWords(text)
                wordList    = self.countWords(words)
                self.associateWordsWithLink(link, wordList)
                linksOnPage = soup('a')
                for outgoingLink in linksOnPage:
                    if ('href' in dict(outgoingLink.attrs)):
                        url = outgoingLink['href']
                        url = url.split('#')[0] # remove location portion (anker)
                        if url[0:4]=='http' and self.isNotIndexed(url):
                            newpages.append(url)
                            description = self.getTextOnly(outgoingLink)
                            self.saveLink(link, url, description)
                        
        self.connection.commit()
        self.crawl(newpages, depth - 1)
            
    def saveLink(self, link, outgoingLink, description):
        sql     = "INSERT INTO webLinks (link, outgoingLink, description) VALUES (?, ?, ?)"
        werte   = self.getWebsiteId(link), self.getWebsiteId(outgoingLink), description
        self.cursor.execute(sql, werte)
           
    def associateWordsWithLink(self, link, wordList):
        website = self.getWebsiteId(link)
        if website == None:
            website = self.saveWebsite(link)
        for entry in wordList:
            word, params    = entry
            count, position = params
            print "word = ", word, "count = ", count, "pos = ", position
            sql     = "INSERT INTO webIndex (website, word, count, position) VALUES (?, ?, ?, ?)"
            werte   = website, word, count, position
            self.cursor.execute(sql, werte)

    def saveWebsite(self, link):
        sql = "INSERT INTO websites (url) VALUES (?)"
        self.cursor.execute(sql, [str(link)])
        sql = "SELECT id FROM websites WHERE url='" + str(link) + "'"
        self.cursor.execute(sql)
        
        return self.cursor.fetchone()[0]

    def getWebsiteId(self, url):
        sql = "SELECT id FROM websites WHERE url='" + str(url) + "'"
        self.cursor.execute(sql)
        row = self.cursor.fetchone()
        
        if row == None:
            return self.saveWebsite(url)
        else:
            return row[0]
        
    def getWordId(self, word):
        self.cursor.execute("SELECT id FROM words WHERE word='" + str(word) + "'")
        row = self.cursor.fetchone()
        
        if row == None:
            return None
        else:
            return row[0]
        
    def isNotIndexed(self, link):
        self.cursor.execute("SELECT * FROM websites WHERE url='" + str(link) + "'")
        row = self.cursor.fetchone()
        if row:
            id  = row[0]
            self.cursor.execute("SELECT * FROM webIndex WHERE website=" + str(id))
            row = self.cursor.fetchone()
            if row:
                return False
            else:
                return True 
        else:
            return True
        
    def getTextOnly(self, soup):
        def noscript(s):
            s = str(s).lower()
            if s==None or s.startswith('<script'):
                return False
            else:
                return True
            
        def nostyle(s):
            s = str(s).lower()
            if s==None or s.startswith('<style'):
                return False
            else:
                return True
        # has to be reduced to <title> tag and <body> tag
        v=soup.string
        if v==None:
            c=soup.contents
            c=filter(noscript, c)
            c=filter(nostyle, c)
            resulttext=''
            for t in c:
                subtext=self.getTextOnly(t)
                resulttext+=subtext+'\n'
            return resulttext
        else:
            return v.strip()
    
    # Separate the words by any non-whitespace character
    def seperateWords(self, text):
        # does not work for stuff like C++, $20, Ph.D., 617-555-1212
        splitter=re.compile('\\W*')
        return [s.lower() for s in splitter.split(text) if s!='']
    
    def countWords(self, words):
        mydict  =   {} 
        
        position = 0
        for word in words:
            if len(word) > 5:
                if mydict.has_key(word) == 1:
                    mydict[word][0] = mydict.get(word)[0] + 1
                else:
                    mydict[word] = [1, position]
                
                position += 1
                        
        wordList = mydict.items()
        wordList = sorted(wordList, key=operator.itemgetter(1), reverse=True)
        
        return wordList

if __name__ == "__main__":
#    crawler = spiderman(createDatabase=True)
    crawler = spiderman()
    links   = ['http://www.chessbase.de']
    crawler.crawl(links)    
    links   = crawler.find('Kasparov')
    for link in links:
        print "Adresse:   ", link[2]
        print "Vorkommen: ", link[0]
        print "Position:  ", link[1]
        print "------------------------------"