Wir wollen nun eine tatsächlich nützliche Erweiterung schreiben. Dazu brauchen wir einige Präliminarien.
Ein häufig vorkommendes Problem ist die Suche in großen Datenmengen. Datenbanken (in Python kann man auf jeden Fall anydbm verwenden) sind ein Möglichkeit, es zu lösen, häufig ist es aber einfacher, die Daten in flat files zu halten, also einfachen Textdateien, in denen jede Zeile einem Eintrag entspricht. Um darin schnell Einträge zu finden, bietet sich binary search an.
Dabei müssen die Daten sortiert sein, und man geht vor wie beim Zahlenraten: Nimm den Eintrag in der Mitte, wenn der Suchschlüssel größer ist, mach in der oberen Hälfte weiter, sonst in der unteren, höre auf, wenn du den Eintrag gefunden hast oder sicher bist, dass du ihn nicht mehr findest. Das Python-Modul bisect implementiert das schon. Eine Funktion daraus:
def bisect_right(a, x, lo=0, hi=None): if hi is None: hi = len(a) while lo < hi: mid = (lo+hi)//2 if x < a[mid]: hi = mid else: lo = mid+1 return lo
Wir wollen das für Textdateien haben, die z.B. so aussehen könnten:
a AP AAA FW Aarhus NP Aaron NP aback AVP abacus NN abalone NP abandon VB
Dabei kommt als Komplikation gegenüber dem einfachen Fall oben hinzu, dass wir nicht wissen, wo die Datenfelder jeweils anfangen, denn die Textzeilen haben ja verschiedene Längen. Das Unix-Programm look kann damit aber umgehen. Wir möchten es jetzt in Python verwenden, und zwar ohne os.system oder Freunde.
Der Quelltext des BSD-Programms ist z.B. im Paket util-linux zu finden (vgl. Freshmeat) oder auch auf der Webseite zu dieser Vorlesung.