Lip Reading How-To: Alle Level des CCC fertigstellen

Wie meistert man alle 7 Level eines für 4 Stunden ausgelegten Catalysts Coding Contests in knapp unter zwei Stunden? Schreibt man dazu schönen Code? Der uns von vielen Teilnehmern zur Verfügung gestellte Sourcecode kann über diese Fragen Auskunft geben. Zunächst wollen wir uns ansehen, wie die fünf schnellsten Teilnehmer einen Programmierwettbewerb angehen. Bis auf den Gewinner Patrik Fimml, welcher in Ruby programmierte, hat die “Spitze” beim CCC 2012 in Wien durchwegs in C++ gearbeitet.

Achtung Spoiler: Dieser Blogeintrag enthält die Analyse von Lösungen für das CatCoder-Game “Lip Reading“. Wer sich zuerst selber am Game versuchen möchte, bitte nicht weiterlesen!

Level 1

Auffällig ist, dass vier der fünf Schnellsten bereits vorprogrammierten Code mitgebracht haben. Obwohl die Aufgabenstellung im Vorhinein nicht bekannt ist, vergeht im Vergleich zur Implementierung der einfachen Aufgabenstellung von Level 1 wertvolle Zeit damit, “Boilerplate Code” zu programmieren – beispielsweise Bibliotheken einzubinden oder Ein-/Ausgabe zu schreiben, die beim CCC bekanntermaßen immer ähnlich aufgebaut ist. Zu sehen sind u.a. Datentypen für geometrische Objekte (die Marsrover lassen grüßen!), I/O, Includes aller erdenklichen C++-Header sowie C-Makros für Schleifen.

Mitgebrachter Boilerplate-Code für den CCC 2012 Wien

C++ Boilerplate Code

Die Lösung auf Level 1 war pro Mundstellung eine Suche dieser in den Trainingdaten (aus dem File trainingdata.txt, dieses war bereits vorsortiert).

Level 2

Auf Level 2 unterscheiden sich die Programme der fünf Schnellsten bereits stark von der Effizienz her. Die für mich als Aufgabensteller naheliegendste Lösung war, pro gesprochenem Wort die Aussprache der Wörterbuchwörter zu durchsuchen, um Wörter mit gleicher Aussprache zu finden. Es gibt auch eine abgewandelte Form dieser Idee, die buchstabenweise die möglichen Wörterbuchwörter eingrenzt. Nicht alle Lösungen waren jedoch so schnell.

Wer stur auf die Lösung von Level 1 aufbaute, konstruierte alle möglichen Buchstaben zu einem gesprochenen Wort, um diese dann nach Wörterbuchwörtern zu durchforsten. Praktikabel war diese Möglichkeit nur wegen der Leichtigkeit der Eingabedaten. Zum Beispiel kam das Wörterbuchwort “honorificabilitudinitatibus” nicht vor – mit beachtlichen 1.253.826.625.536 möglichen Buchstabenkombinationen (die Anzahl der Möglichkeiten aus Level 1 für jede Mundstellung dieses Wortes multipliziert) hätte die Rechenzeit für diesen Lösungsweg bis zum Ende des Contests wohl nicht gereicht…

Eine weitere praktische Datenstruktur für die Aufgabenstellung, der Trie, kam schon auf Level 2 zur Anwendung. Diese buchstabenweise Speicherung des Wörterbuches in einen Baum hatte auch für die Implementierung von Level 3 erhebliche Vorteile.

Wer sich übrigens fragt, woher die Wörter für den Contest kommen, der sei auf William Shakespeares Werke hingewiesen.

Level 3

In Gedanken befinden wir uns zeitlich durchschnittlich 40 Minuten nach dem Start des Wettbewerbs, als die Sieger beginnen, an Level 3 zu arbeiten. Diese Angabe sollte bei den meisten Teilnehmerinnen und Teilnehmern erst später für Verwirrung sorgen; die Anführer der Hall of Fame bekümmert der Level hingegen schon jetzt – wie ist das Gleichheitszeichen in der Angabe zu verstehen? Stehen die Silben auf beiden, oder nur auf der linken Seite? Kann man Silben rekursiv auflösen? Führt es dann nicht zu einer endlosen Reihe von Auflösungen, wenn “k” wie “ck” klingt und diese Silbe wiederum rekursiv aufgelöst wird?

Wer die eigentliche Aufgabenstellung (Lippenlesen) im Hinterkopf hatte, dachte hier vielleicht eher an das Richtige, der Rest dachte teilweise zu kompliziert – hier gab es viele Fragen.

Die vielleicht einfachste Lösung von Level 3 bestand darin, aus Wörtern des Wörterbuches ein eigenes “Aussprache-Wörterbuch” zu erstellen, in dem die Wörter in ausgesprochener Form gesucht werden können. Die Aussprache eines Wortes wird erzeugt, indem mit einer Art Tokenizer von links nach rechts zuerst nach Silben und erst dann nach Buchstaben aufgelöst wird. Der Rest der Lösung besteht dann aus der in Level 2 programmierten Suche.

Eine andere Variante, die im vorliegenden Quellcode nur dank der Reihenfolge der Ersetzungen auch für Spezialfälle wie das Wort “bacchus” funktioniert hat, ist ebenfalls ein Aussprache-Wörterbuch, das sich jedoch aus dem sturen Ersetzen von Silben durch ihre Aussprache ergibt. Ein nicht befolgenswertes Beispiel für eine Implementierung dieser Variante sieht man im Bild…

Copy & Paste vom Feinsten!

Don't Repeat Yourself

Wer einen Trie benutzt hat, hätte die Funktionalität für Silben eigentlich ebenfalls in den Trie packen können, indem Buchstaben (außer Teile von Silben!) und ausgesprochene Silben (und zusätzlich die Schreibweise) in den Trie gespeichert werden. Stattdessen wurde auch hier lieber der Weg über die Textersetzung von Silben vor dem Befüllen des Trie gewählt. Nach dem Auflösen von möglichen Wörtern mittels Trie musste dabei noch ein Mapping von der Form mit umgeschriebenen Silben zur originalen Wörterbuchform gemacht werden.

Level 4

Nachdem das Konzept der Silben auf Level 3 gut verstanden wurde, sollte dieses Wissen später eingesetzt werden, um das wahrscheinlichste Wort auszuwählen. Um die Richtigkeit dieser Auswahl sicherzustellen, wurde dabei in Level 4 die Berechnung der benutzten Wahrscheinlichkeiten kontrolliert.

Wer in Level 3 Textersetzung für die Silben benutzt hatte, benutzte die gleiche Methode, um dieses Level zu lösen (Silben durch Einzelbuchstaben ersetzen, dann ist die Anzahl der Silben-/Buchstabenpaare in einem Wort gleich der Anzahl Buchstaben im ersetzten Wort minus eins). Auch hier wurde öfters per Copy & Paste mehr Code erzeugt, als eigentlich notwendig gewesen wäre… Vielleicht hätten wir die Definition der Silbenaussprache lieber ebenfalls als File bereitstellen sollen?

Level 5

In Level 5 waren für die Wahrscheinlichkeit eines Wörterbuchwortes die Wahrscheinlichkeiten aller Silben-/Buchstabenpaare zu multiplizieren – für das Wort “cloth” wären das z.B. die Wahrscheinlichkeiten der Paare aus Level 4 für (c,l), (l,o), (o,th). Gefragt war dann nach dem Wort mit der größten Wahrscheinlichkeit. Warum eigentlich den selben Code von Funtion zu Funktion kopieren, hier von solveInput3() nach solveInput5(), um dann unten noch etwas dranzuhängen? Grundsätzlich hätte man Level 5 vollständig auf die Ergebnisse von Level 3 aufbauen können.

Copy & Paste von solveInput3() nach solveInput5()

Copy & Paste von Funktion zu Funtion - beide Seiten aus einer Lösung für Level 5

Level 6

Auf Level 6 wurde eine andere Art der Wahrscheinlichkeit von Wörtern eingeführt, weil diese für uns in der Praxis besser funktioniert hat. Die Häufigkeit der Wörter in einem für die englische Sprache repräsentativen Beispieltext lieferte die Grundlage für die Berechnung. Die Frage nach dem Wert der Wahrscheinlichkeit sollte wieder sicherstellen, dass diese Berechnung für später, also Level 7, richtig ist. Drei der fünf besten Teilnehmer benötigten dafür keine zehn Minuten.

Wie, das letzte Wort des Beispieltextes wird nicht korrekt gelesen? Nicht lange den Fehler suchen, einfach das letzte Wort (“jungle”) hardcoden!

Hardcoded input data

Hardcoded input data

Level 7

Die Schwierigkeit in Level 7 bestand darin, dass man keine Zwischenräume zwischen Wörtern hat (man spricht keine Leerzeichen). Damit ist ein Satz eine Folge von Mundstellungen der einzelnen Wörter. Die Hauptaufgabe bestand nun darin, die Zwischenräume zu finden. Um die Lösung eindeutig zu machen, fragten wir nach dem wahrscheinlichsten Satz, und definierten diese Wahrscheinlichkeit als Produkt der Wahrscheinlichkeiten der einzelnen Wörter.

Level 7 wurde so ausgelegt, dass eine Suche von allen möglichen Aufspaltungen des Satzes und aller möglichen Wörter ohne Optimierung nicht in vernünftiger Zeit zu einem Ende kommt. Hier war etwas Kreativität beim Optimieren gefragt.

Zwei der fünf betrachteten Lösungen benutzen dynamische Programmierung – im Allgemeinen werden dabei Zwischenergebnisse gespeichert, die dann nicht immer wieder berechnet werden müssen. Konkret wird zeichenweise nach der (aktuell) besten Lösung gesucht. Wenn ein Wort durch das buchstabenweise Vorgehen erst später berücksichtigt werden kann, kann natürlich später eventuell eine bessere Lösung gefunden werden.

Es geht aber auch einfacher: Man merkt sich dazu bei jeder möglichen Aufteilung des Satzes in Wörter immer nur das wahrscheinlichste Wort. Mit den anderen Wörtern zu denselben Mundstellungen braucht nicht mehr gerechnet zu werden, weil diese eine geringere Satzwahrscheinlichkeit bedeuten würden. Teilweise musste noch die Suche des wahrscheinlichsten Wortes optimiert werden, damit zu den größten Testcases mit 47 Mundstellungen rechtzeitig die Lösung berechnet werden konnte.

Die nicht nur am schnellsten programmierte, sondern auch am schnellsten rechnende Lösung ist übrigens in Ruby geschrieben, benutzt einen Trie und merkt sich immer nur das wahrscheinlichste Wort.

Trie sentence-splitting

Kern der Lösung von Patrik Fimml

Interessant an der Aussprache finde ich, dass man sie als eine Art nicht eindeutig umkehrbare Verschlüsselung betrachten kann. Damit der erkannte Satz einen Sinn ergibt, müsste der Computer die Sprache verstehen; weil das noch nicht möglich ist, ist man als Programmierer auf die Statistik angewiesen, und für die Mundstellungen des Satzes “what is in a name that which we call a rose” ist die nach Level 7 wahrscheinlichste Interpretation “what i this i name that what we call in one” für Menschen völlig sinnfrei. Ich finde die Erkennungsrate für diese einfache Implementierung trotzdem beeindruckend.

Fazit

Wir haben nicht nach poliertem Sourcecode gefragt, sondern nach Ergebnissen. Die am schnellsten fertiggestellten Programme erfüllen dieses Ziel punktgenau: Teilweise wurde keine Sekunde darüber nachgedacht, ob man den Code auch schöner schreiben kann (das wird am deutlichsten durch das ausufernde Copy & Pasting gezeigt). Ich glaube, dass man trotz Zeitdruck etwas darauf achten sollte, dass der Code wartbar bleibt. Wenn sich etwas an der Behandlung der Silben geändert hätte, hätten einige Teilnehmer an 11 verschiedenen Stellen etwas ändern müssen – hier zahlt sich doch ein Array aus, oder?!

Vorheriger Beitrag
Die BBS Rohrbach ist der Sieger der CCC Schul-Wettbewerb-Wertung
Nächster Beitrag
Christopher Avery Workshop – The Responsibility Process

Related Posts

No results found

1 Kommentar. Hinterlasse eine Antwort

Ich finde es in erster Linie beachtenswert, dass die Zeit investiert wird, die Lösungen der Teilnehmer so genau zu betrachten – und damit auch andere Metriken als nur die brutale Effizienz in die Bewertung der Lösungen einfließen zu lassen.

Auf solche Analysen freue ich mich nach dem nächsten CCC wieder.

Antworten

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Bitte füllen Sie dieses Feld aus
Bitte füllen Sie dieses Feld aus
Bitte gib eine gültige E-Mail-Adresse ein.
Sie müssen den Bedingungen zustimmen, um fortzufahren

Menü