Suchen mit Strategie

In den vergangenen Wochen habe ich mich viel mit XML befasst. Für die Verarbeitung eines XML-Dokuments habe ich mir ein Python-Programm geschrieben, das die XML-Darstellung direkt in einen Objektbaum abbildet -- alle weiteren Bearbeitungsschritte führe ich dann in dem Objektmodell aus. Jedes Objekt in diesem Baum hat einen Vorgänger (parent) und keinen oder mehr Nachfolger (childs). Das ist sehr ähnlich zu DOM.

Bei der Verarbeitung einer solchen Baustruktur tritt ein Problem immer wieder auf: Sie suchen Knoten (= Objekte) in dem Baum, die einem oder mehreren Kriterien genügen. Für diese Aufgabe kann man eine sehr flexible query-Funktion programmieren:

def query(criteria):
    assert callable(criteria)
    result = []
    for element in allElements():
        try:
            if criteria(element) == True:
                result.append(element)
        except: pass
    return result

Dieser query-Funktion übergibt man ein Kriterium in Form eines Lambda-Ausdrucks (das ist eine anonyme, sprich namenlose Funktion; so etwas gibt es jetzt auch in C# 3.0). Zum Beispiel:

query(lambda e: e.tag == "page")

Dieser Aufruf sucht aus dem Objektmodell alle Objekte raus, die in der XML-Darstellung das Tag "page" tragen.

Ein Nachteil dieser Suchabfrage ist, dass alle Elemente (allElements()) durchgegangen werden. Optimiert werden könnte das durch eine Suchstrategie, die nur relevante Elemente nach einem bestimmten Verfahren der Suche zum Test vorlegen würde. Hier die optimierte Version:

def query(criteria,strategy=yieldElements):
    assert callable(criteria) and callable(strategy)
    result = []
    for element in strategy():
        try:
            if criteria(element) == True:
                result.append(element)
        except: pass
    return result

Dazu zwei Strategien. Die erste Strategie (yieldElements) generiert wie gehabt alle Elemente. Die zweite Strategie (yieldInnerElements) generiert alle Elemente, die im Sinne einer XML-Darstellung "innerhalb" eines gegebenen Elements liegen. Die Strategie ist also parametrisiert.

def yieldElements():
    for klass in elementClasses:
        for element in klass.instances:
            yield element

def yieldInnerElements(element):
    def _yieldInnerElements():
        def yieldInnerNodes(node):
            for n in node.childs:
                yield n
                for child in yieldInnerNodes(n):
                    yield child
        return yieldInnerNodes(element)
    return _yieldInnerElements

Wieder ein Beispiel für eine Abfrage:

query(lambda e: e.tag == "page",yieldInnerElements(chapterOne))

Jetzt werden lediglich die Objekte mit dem Tag "page" herausgesucht, die als Kinder bzw. Kindskinder etc. innerhalb eines chapterOne-Objekts des Objektmodells zu finden sind.

Eine interessante Einsicht ist, dass jede Strategie auch als Teil eines Kriteriums in criteria verstanden werden kann. Die explizite Formulierung einer Strategie optimiert lediglich die Vorlage von Elementen zum Kriteriumstest und beschleunigt das Suchverfahren. Strukturwissen um die Organisation der Daten kann so effizient ausgenutzt werden. Die Parallelen zum Constraint Programming sind kein Zufall!