[def]

Hallo,

ich bin dabei, ein Python-Programm zu schreiben, das die Programmseiten diverser Fernsehsender automatisch durchsucht, um anhand von Stichwörtern die für mich interessanten Sendungen aufzuspüren. Das ist alles auch gar nicht so schwer und funktioniert für einen Sender bereits. Wobei das Programm ein bisschen nach Haudrauf-Methode geschrieben ist, aber es funktioniert.
Dabei ist meine Devise: Lieber ein paar Falschmeldungen, denen ich nachgehen muss, als eine interessante Sendung verpassen.
Nun möchte ich denkbare Rechtschreibfehler auf den Programmseiten in der Suche berücksichtigen. Nehmen wir an, ich wäre ein Fan der Band Tocotronic, und suche nun nach Sendungen, in denen es um diese Band geht. Nehmen wir an, das gesamte Programm des Senders sei in dem String prog, dann könnte ich mit if 'Tocotronic' in prog danach suchen. Ich könnte auch Groß- und Kleinschreibung ignorieren:

pattern = re.compile('Tocotronic', re.IGNORECASE)
match = pattern.search(prog, 0)
if match != None:
	print 'Gefunden!'
else:
	print 'Nicht gefunden!'

Aber, was mach ich, wenn dem Mitarbeiter des jeweiligen Senders, der die Sendung eintippen musste, ein Tippfehler unterlaufen ist? Wie kann ich also gleichzeitig 'Toctronic', 'Tocotronik', 'Tocotonic' usw. in die Suche einbeziehen? Sagen wir mal, bis zu ein falscher Buchstabe soll noch einen Treffer ergeben. Gibt es dafür fertige Module, womöglich sogar für Python? Die Performance wäre mir dabei ziemlich egal. Oder müsste ich so etwas per Hand schreiben?

Vielen Dank und schöne Grüße
Def

Dieser Beitrag wurde von def bearbeitet: 06. September 2008 - 17:35

[Matze]

Stichwort: Levenshtein-Distanz. Die Distanz zählt, wie viele Ersetzungen von Wort 1 zu Wort 2 nötig sind, um das Wort 2 zu bilden. Ist natürlich nicht sehr perfomant für deine Zwecke. Du könntest aber Wörter, die beim ersten Mal als "ähnlich" erkannt worden sind zwischenspeichern und dann direkt nach diesen Wörtern suchen. Das erspart dir manuelles Aufbauen von Wörterbüchern.

[def]

Zitat (Matze: 06.09.2008, 14:31)

Stichwort: Levenshtein-Distanz. Die Distanz zählt, wie viele Ersetzungen von Wort 1 zu Wort 2 nötig sind, um das Wort 2 zu bilden. Ist natürlich nicht sehr perfomant für deine Zwecke. Du könntest aber Wörter, die beim ersten Mal als "ähnlich" erkannt worden sind zwischenspeichern und dann direkt nach diesen Wörtern suchen. Das erspart dir manuelles Aufbauen von Wörterbüchern.

Danke für das Stichwort Levenshtein. Es gibt für zahllose Programmiersprachen Implementierungen im Web, wie ich jetzt festgestellt habe. Die Python-Version aus den Wikibooks kann ich allerdings nicht empfehlen. Rekursiv implementiert, braucht diese 4 bis 5 Sekunden, um die Levenshtein-Distanz von 'Apfelbaum' und 'Appelboom' festzustellen (diese beträgt 3, nebenbei vermerkt). Ganz zu schweigen von längeren Zeichenketten.
Diese Implementierung hingegen liefert das Ergebnis auch von längeren Zeichenketten praktisch ohne Verzögerung.
Es ist schon interessant, dass eine solche "unscharfe" Suche insgesamt trotzdem wesentlich länger braucht. Ich muss gestehen, ich war beim Schreiben des Skripts ein bisschen faul - ich hatte einfach den gesamten HTML-Quellcode (also einschließlich HTML-Tags) nach den Stichwörtern durchsucht - und nur kurz überprüft, ob es sich wirklich um eine Programmseite und das passende Datum handelt (nicht dass irgendwer die Seiten umstrukturiert hat). Ansonsten habe ich einfach alles, HTML-Tags, Menüs, Header, Footer, usw. in die Suche einbezogen, ohne dass die Suche eine nennenswerte Zeit eingenommen hätte. Insofern war mir Optimierung schlicht egal. Zumal das Programm, sobald es fertig ist, ja sowieso im Hintergrund laufen kann.
Wenn ich jetzt aber sehe, wie lange dieser Algorithmus braucht, muss ich mir über Optimierungen wohl doch Gedanken machen. Und sehen, dass ich das HTML nicht als ganzes durchsuche, sondern halt nur die Programminhalte.
Deine Idee klingt auch sehr gut - ich würde es halt nur umgekehrt machen, also ein Verzeichnis von regelmäßigen Sendungen, die nicht überprüft werden müssen, sondern einfach übersprungen werden können. So muss beispielsweise nicht für jeden Tag überprüft werden, wie groß die Levenshtein-Distanz zwischen "Tocotronic" (um mal beim Beispiel zu bleiben) und "Tagesschau" ist - die Sendung kann einfach übersprungen werden.
Vielen Dank nochmal.

Schöne Grüße
Def

[m4rkus]

@def: Danke für den Thread! Bringst mich auf viele tolle Ideen...

Gruß,
m4rkus

[Ludacris]

Zitat (m4rkus: 08.09.2008, 22:37)

@def: Danke für den Thread! Bringst mich auf viele tolle Ideen...

Gruß,
m4rkus

[offtopic] Codest du etwa? das wusste ich garnicht [/offtopic]

[m4rkus]

ähm, ja? zwar keine großen sachen, aber ich code, ja.