Um neue Domainnamen vorzuschlagen und zu erzeugen, müssen wir erkennen können, aus welchen Wörtern ein Domainname besteht. Wortsegmentierung ist eine Technik der Sprachverarbeitung, die meist Wörter in Zeichenfolgen von Sprachen ohne natürliche Wortgrenzen findet, etwa Chinesisch oder Japanisch. Wir finden damit die Wörter „Instant Domain Search“ in Domains wie instantdomainsearch.com. Die Python-Bibliothek wordsegment löst dieses Problem. Für Instant Domain Search mussten wir sie jedoch nach Rust portieren, damit sie schnell genug arbeitet.
Wordsegment basiert auf Peter Norvigs Beispiel zur Wortsegmentierung in Beautiful Data. Die Grundidee: Man durchläuft alle möglichen Segmentierungen einer Zeichenfolge und bewertet, wie wahrscheinlich sie in realen Texten vorkommen. Dafür brauchen wir zwei Komponenten:
- Eine Methode, die Wahrscheinlichkeit eines Satzes in realen Texten zu schätzen.
- Eine effiziente Methode, alle möglichen Segmentierungen der Eingabe zu bewerten.
Sehen wir uns beide genauer an.
Einen Satz bewerten
Die einfachste Methode bewertet einzelne Wörter nach ihrer Häufigkeit in realen englischsprachigen Daten. Norvig verwendete den Google Trillion Web Corpus (2006). Die Web-1T-Sammlung ist öffentlich ausschließlich für Forschungs- und Bildungszwecke verfügbar. Diese Daten verwendete ich anfangs auch für unsere Portierung.
Um den Wert für ein einzelnes Wort zu erhalten, teilt man die Anzahl seiner Vorkommen im Korpus durch die Gesamtzahl aller Wortvorkommen. Das Wort „instant“ erschien in der Web-1T-Sammlung beispielsweise etwa 28 Millionen Mal. Unser Korpus umfasst insgesamt rund 588 Milliarden Wörter, da seltene Wörter aus dem langen Ende der Verteilung fehlen. Die Wahrscheinlichkeit für „instant“ bewerten wir daher mit 0.000049. Auch Wörter, die nicht im Korpus vorkommen, brauchen einen Wert. Einzelheiten beschreibt Norvigs Kapitel.
Als Nächstes bewerten wir Wortfolgen. Dazu könnten wir die Wahrscheinlichkeiten aller Wörter des Eingabesatzes multiplizieren. Um Rechenfehler durch die Multiplikation vieler kleiner Zahlen zu vermeiden, verwenden wir stattdessen den Zehnerlogarithmus jedes Werts und addieren die Ergebnisse. Für „this is a test“ ergibt das -2.3 + -2.1 + -1.8 + -3.6 = -9.7. Die Formel für Wörter außerhalb des Korpus liefert dagegen -22 für „thisisatest“.
Um die Ergebnisse weiter zu verfeinern, berücksichtigen wir wie Norvig auch Bigramme: die bedingte Wahrscheinlichkeit, dass zwei Wörter nebeneinander stehen. Für jedes Wort außer dem ersten betrachten wir statt der einfachen Auftretenswahrscheinlichkeit die Wahrscheinlichkeit, dass es auf das vorherige Wort folgt. Mit dem ursprünglichen Korpus bewerten wir „is“ nach „this“ mit -3.2 statt -2.1. So fließt Kontext in die Bewertung ein.
Segmentierungen aufzählen
Bei kurzen Zeichenfolgen möchten wir alle Segmentierungen aufzählen, um die Aufteilung mit dem besten Wert zu finden. Da ihre Anzahl jedoch exponentiell mit der Eingabelänge wächst, ist das bei längeren Zeichenfolgen nicht praktikabel. Zugleich werden sehr lange Wörter zunehmend unwahrscheinlich. Deshalb legen wir zunächst eine maximale Wortlänge von 24 Zeichen fest. Dann teilen wir die Eingabe an jeder der ersten 24 Zeichengrenzen und addieren den Wert des ersten Worts zum Wert der übrigen Wörter.
Norvig verwendete Rekursion, und unsere ersten Rust-Versionen folgten diesem Ansatz. Vor Kurzem änderten wir die Implementierung auf Grundlage von Wolf Garbes Artikel Fast Word Segmentation of Noisy Text. Wir nutzen nun eine Variante des dort beschriebenen Dreiecksmatrixalgorithmus. Ein dynamisch großes Array, Rusts Vec, hält den besten Wert an jeder Segmentierungsposition fest. Bei „thisisatest“ hätte der Kandidat für Position 6, nach „is“, beispielsweise die Länge 2 und den Wert für „this is“. Dieser Ansatz begrenzt die Stackgröße. Die verschachtelten Schleifen finde ich außerdem leichter nachvollziehbar als begrenzte Rekursion. Wir haben den Dreiecksmatrixansatz für Bigrammwerte angepasst.
Performance-Optimierungen
Auf meinem Rechner segmentiert die Python-Bibliothek wordsegment „thisisatest“ einmal alle 500 µs. Die neueste Version von instant-segment erledigt dieselbe Aufgabe in 4 µs, bei gleicher Arbeit 95-mal schneller. Hier einige der eingesetzten Techniken:
- Die erste Portierung war nur 1,7-mal schneller als Python. Sie zählte Segmentierungen wie wordsegment und Norvigs Code rekursiv auf und speicherte Teilwerte in einer Hashmap. Beispielsweise lassen sich „thisis a test“ und „this is a test“ schneller bewerten, wenn der Wert für „a test“ wiederverwendet wird.
- Einige unnötige Speicherallokationen in der Kernschleife zu vermeiden und den Cache auf den ahash-Algorithmus umzustellen, erhöhte die Leistung auf das 4,9-Fache von Python.
- Die Crate smartstring vermeidet Heap-Allokationen bei kurzen Zeichenfolgen. Das passt gut, da Wörter meist kurz sind. Damit erreichten wir das 9,0-Fache.
- Das Inlining der Kernschleife, die Segmentierungspositionen liefert, brachte uns auf das 11-Fache.
- Wiederholte Allokationen für Zwischenergebnisse zu vermeiden, half uns auf das 12-Fache.
- Rust-Zeichenfolgen sind UTF-8-codiert. Beim Aufteilen müssen daher Zeichenpositionen validiert werden. instant-segment lehnt Eingaben mit Nicht-ASCII-Zeichen jedoch ab. Etwas unsicherer Code zum Umgehen der Unicode-Prüfung erhöhte die Leistung auf das 15-Fache.
- Ein Update von ahash brachte uns auf das 18-Fache.
- Der Wechsel von f64::powf() zu f64::powi() half uns auf das 19-Fache.
- Die Wiederverwendung von Zwischenallokationen bei mehreren aufeinanderfolgenden Segmentierungen brachte eine 25-mal höhere Geschwindigkeit als Python.
- Schließlich führte der Dreiecksmatrixansatz zum 95-Fachen.
instant-segment
Wir haben diese Arbeit als Open Source veröffentlicht. Die neueste Version von instant-segment ist auf crates.io verfügbar. Dieses Jahr haben wir mit dem hervorragenden PyO3 Python-Anbindungen ergänzt. Außerdem basiert der Testdatensatz unseres Repositorys nun auf aktuelleren und freier lizenzierten Daten von Google und dem SCOWL-Projekt. Der Einstieg in instant-segment ist damit einfacher denn je. Wir freuen uns auf Ihr Feedback und darauf zu hören, wie Sie das Projekt einsetzen!