CL-Blog

Computerlinguistik & Politik

2017 24 Jul

C++ II, 24.7. (Schluss)

Abgelegt unter: C++ in der Computerlinguistik II | RSS 2.0 | TB | Kommentare geschlossen

Thema: Inkrementelle Minimierung von Wortlisten

  • Hash-Funktion für Zustände mit boost::hash_combine
  • Funktionsobjekte mit Nicht-Defaultkonstruktoren
  • Übergabe von Funktionsobjektinstanzen an ihre Container (z.B. unordered_set) per Konstruktor-Aufruf
  • Weitergehende Optimierungen:
    • Gelöschte Zustände und Übergänge werden zunächst inaktiv gesetzt, wir sollten sie wieder verwenden => Man kann das einfach mit zwei Listen machen — eine für Zustände, eine für Übergänge — wo wir StateIDs und Übergangsindices speichern und bei Bedarf wieder benutzen können (vgl. Funktionen new_state() und new_transition() in FSAListRepr. Man verwendet hier am besten eine double ended queue (std::deque), diese hat gute Speicherlokalität.
    • Auch dann können noch Lücken in der Zustandsnummerierung bleiben. Beim Umkopieren in eine Nur-Lesen-Repräsentation kann man diese noch schließen
  • Zu klären ist noch, in welchem Verhältnis der Minimierungsalgorithmus und der fertige Automat stehen. Am besten baut man um die Repräsentation herum eine Klasse ähnlich wie Trie (im Beispielcode DFA genannt). Diese verwendet dien Minimierer dann beim Einlesen einer Wortliste.
  • Testen ist im Kurs etwas zu kurz gekommen. Heutzutage testet man automatisiert und zufallsbasiert (fuzzing). Das folgende Shell-Skript nimmt z.B. zufallsbasiert 1000 Wörter aus der Derewo-Liste und minimiert diese. Gibt es einen Absturz, so erkennt man diesen und speichert die das Problem generierende Liste. Statt einer vorhandenen Liste wie Derewo kann man das Eingabematerial auch nach einer W’keitsverteilung erzeugen, ggf. sogar durch einen Markov-Zufallsprozess. Das lässt man dann ein paar Stunden laufen und fühlt sich gleich besser.
    while :
    do 
    	shuf -n 1000 derewo.txt > wl.list
    	./build-dawg wl.list
    	if [ $? -eq 139 ]; then
    		echo "CRASH"
    		cp wl.list crash.list
    		exit 1
    	fi
    done
  • Auch Äquivalenztests kann man auf diese Weise machen: man erzeugt eine zufällige Wortliste und  einen DWAG daraus. Dann gibt man von diesem die Wörter wieder sortiert aus. Beide Listen vergleicht man per diff und beendet das Testskript wieder, wenn sie nicht gleich sind

Weitere interessante Dinge:

  • Die Boost-Bibliotheken bieten zahlreiche nützliche Klassen, z.B. Mengen etc. auf Vektor-Basis (boost::container::flat_set), dynamische Bit-Mengen (boost::dynamic_bitset), Ringpuffer (boost::circular_buffer), Prüfsummen (boost::crc), Hashing (boost::hash), Python-Wrapping von C++-Klassen (boost::python) und vieles mehr. Einfach mal reinsehen
  • Portables Befehlszeilenparsing kann man gut mit tclap machen (von Bibliotheken wie boost::program_options rate ich ab)
  • Hocheffiziente Tokenisierer, auch für natürlichsprachliche Eingaben, macht man mit re2c.

Programmcode:

 

Dieser Beitrag wurde geschrieben am Montag, 24. Juli 2017 und wurde abgelegt unter "C++ in der Computerlinguistik II". Du kannst die Kommentare verfolgen mit RSS 2.0. Kommentare und Pings sind zur Zeit geschlossen.

Kommentare sind zur Zeit geschlossen.


CL-Blog läuft unter Wordpress 3.5.1
Anpassung und Design: Gabis Wordpress-Templates
20 Verweise - 0,202 Sekunden.