tongrams

Zungenrams - Tonnen von n -Grams

Tongrams ist eine C ++ - Bibliothek, um Großsprachenmodelle im komprimierten Raum zu indizieren und abzufragen, wie in den folgenden Arbeiten beschrieben

• Effiziente Datenstrukturen für massive N-Gramm-Datensätze [1]
• Umgang mit massiven N-Gramm-Datensätzen effizient [2]

von Giulio Ermanno Pibiri und Rossano Venturini. Bitte zitieren Sie diese Papiere, wenn Sie Tongrams verwenden.

NACHRICHT!

• Die Sprachmodellschätzungsbibliothek ist hier verfügbar.
• Eine Rost -Implementierung von Kampersanda ist hier erhältlich.

Einführung

Insbesondere können die implementierten Datenstrukturen verwendet werden, um n -Gramme ihren entsprechenden (Ganzzahl-) Frequenzzahlen oder an (Gleitkomma-) Wahrscheinlichkeiten und Backoffs für Backoff-Interpolated Kneser-NEY-Modelle zuzuordnen.

Die Bibliothek verfügt über eine komprimierte Trie -Datenstruktur, in der N -Grams Integer Identifiers (IDs) zugewiesen und mit Elias -Fano komprimiert werden, um effiziente Suchvorgänge im komprimierten Raum zu unterstützen. Die kontextbasierte Neubeschaffung solcher Kennungen ermöglicht es, ein Wort nach einem Kontext der festen Länge k zu codieren, dh seinen vorhergehenden K- Wörtern, mit einer Ganzzahl, deren Wert durch die Anzahl der Wörter begrenzt ist, die einem solchen Kontext folgen, und nicht durch die Größe des gesamten Vokabulars (Anzahl der Uni-Grams). Zusätzlich zur Trie-Datenstruktur ermöglicht die Bibliothek, Modelle basierend auf minimaler perfektem Hashing (MPH) für den Abrufen von Konstantzeiten zu erstellen.

Wenn die Datenstrukturen zum Speichern von Frequenzzählungen verwendet werden, unterstützen sie einen lookup() -Operation, der die Anzahl der Vorkommen des angegebenen n -Grams zurückgibt. Unter Verwendung zum Speichern von Wahrscheinlichkeiten und Backoffs implementieren die Datenstrukturen eine score() -Funktion, die bei einem Text als Eingabe die Verwirrungsbewertung des Textes berechnet.

Dieser Leitfaden soll einen kurzen Überblick über die Bibliothek geben und ihre Funktionen anhand einiger Beispiele veranschaulichen.

Inhaltsverzeichnis

• Den Code erstellen
• Eingabedatenformat
• Aufbau der Datenstrukturen
• Tests
• Benchmarks
• Statistiken
• Python Wrapper
• Autoren
• Bibliographie

Den Code erstellen

Der Code wurde auf Linux Ubuntu mit gcc 5.4.1, 7.3.0, 8.3.0, 9,0,0 getestet; Mac OS X El Capitan mit clang 7.3.0; Mac OS X Mojave mit clang 10.0.0.

Die folgenden Abhängigkeiten sind für den Build erforderlich: CMake und Boost .

Wenn Sie das Repository ohne --recursive geklont haben, müssen Sie vor dem Erstellen die folgenden Befehle ausführen:

 git submodule init
git submodule update

Um den Code auf UNIX -Systemen zu erstellen (siehe Datei CMakeLists.txt

 mkdir build
cd build
cmake ..
make

Sie können eine parallele Zusammenstellung aktivieren, indem Sie einige Jobs angeben: make -j4 .

Für Best of Performace wie folgt kompilieren.

 cmake .. -DCMAKE_BUILD_TYPE=Release  -DTONGRAMS_USE_SANITIZERS=OFF -DEMPHF_USE_POPCOUNT=ON -DTONGRAMS_USE_POPCNT=ON -DTONGRAMS_USE_PDEP=ON
make

Kompilieren Sie für eine Debug -Umgebung stattdessen wie folgt.

 cmake .. -DCMAKE_BUILD_TYPE=Debug -DTONGRAMS_USE_SANITIZERS=ON
make

Sofern nicht anders angegeben, gehen wir für den Rest dieses Handbuchs davon aus, dass wir die Terminalbefehle der folgenden Beispiele aus dem erstellten build eingeben.

Eingabedatenformat

Das n -Gram zählt Dateien, folgen dem Google -Format, dh einer separaten Datei für jeden einzelnen Wert von N (Order), in dem ein Gramm pro Zeile aufgelistet ist. Wir bereichern dieses Format mit einem Dateiheader, der die Gesamtzahl der n -Gramme in der Datei (Zeilen) angibt:

 <total_number_of_rows>
<gram1> <TAB> <count1>
<gram2> <TAB> <count2>
<gram3> <TAB> <count3>
...

Solche n- Dateien müssen nach der folgenden Konvention benannt werden: <order>-grams , wobei <order> ein Platzhalter für den Wert von n ist. Die Dateien können ungeortiert bleiben, wenn nur MPH-basierte Modelle erstellt werden müssen, während diese in der Präfixreihenfolge für Trie-basierte Datenstrukturen gemäß der ausgewählten Vokabellzuordnung sortiert werden müssen, die durch die Uni-Gram-Datei dargestellt werden sollte (siehe Abschnitt 3.1 von [1]). Das Komprimieren der Eingabedateien mit Standard -Dienstprogrammen wie gzip wird dringend empfohlen. Mit dem Dienstprogramm sort_grams können die n -Gram -Dateien in Präfixreihenfolge sortiert werden. Zusammenfassend sind die Datenstrukturen, die die Frequenzzahlen speichern

• 1-grams.sorted.gz
• 2-grams.sorted.gz
• 3-grams.sorted.gz
• ...

formatiert wie oben erläutert.

Die Dateilisten -N -Gram -Wahrscheinlichkeiten und -backoffs entsprechen stattdessen dem ARPA -Dateiformat. Die n -Gramme in der ARPA -Datei müssen in Suffix Reihenfolge sortiert werden, um die umgekehrte Trie -Datenstruktur zu erstellen. Der Dienstprogramm sort_arpa kann zu diesem Zweck verwendet werden.

Das Verzeichnis test_data enthält:

• Alle n -Gramm zählen Dateien (für insgesamt 252.550 n -Gramms), für N von 1 bis 5, extrahiert aus der Handbuch des Agner -Fog -Optimierungssoftware in C ++ , sortiert in Präfixreihenfolge und mit gzip komprimiert.
• die Abfragedatei queries.random.5K mit 5.000 n -Grams (1.000 für jede Bestellung und zufällig gezeichnet);
• Die ARPA -Datei arpa , in der alle N -Grams in Suffix -Reihenfolge sortiert sind, um rückwärts effiziente Versuche zu erstellen.
• Die für den Verwirrungs -Benchmark verwendete sample_text -Abfragedatei (6.075 Satz für insgesamt 153.583 Wörter); Die Datei ohne Begleiter sample_text.LESSER enthält nur die ersten 10 Sätze.

Für die folgenden Beispiele gehen wir davon aus, dass wir mit den in test_data enthaltenen Beispieldaten arbeiten.

Aufbau der Datenstrukturen

Die beiden ausführbaren build_trie und build_hash werden verwendet, um Trie-basierte bzw. (minimale perfekte) Hash-basierte Sprachmodelle zu erstellen. Führen Sie die ausführbaren Ausführungen ohne Argumente aus, um sie über ihre Verwendung zu informieren.

Wir zeigen jetzt einige Beispiele.

Beispiel 1

Der Befehl

 ./build_trie ef_trie 5 count --dir ../test_data --out ef_trie.count.bin

baut einen Elias-Fano-Trie

• der Ordnung 5;
• das speichert die Frequenzzahlen;
• Aus dem n -Gram zählt Dateien, die im Verzeichnis test_data enthalten sind;
• ohne kontextbasiertes Neuapping (Standard);
• deren Zählungen werden mit der indizierten Codeworks (IC) -Technik (Standard) codiert;
• Das ist serialisiert mit der binären Datei ef_trie.count.bin .

Beispiel 2

Der Befehl

 ./build_trie pef_trie 5 count --dir ../test_data --remapping 1 --ranks PSEF  --out pef_trie.count.out

baut einen verteilten Elias-Fano-Trie

• der Ordnung 5;
• das speichert die Frequenzzahlen;
• Aus dem n -Gram zählt Dateien, die im Verzeichnis test_data enthalten sind;
• mit kontextbasiertem Neuapparat von Order 1;
• deren Zählungen werden mit Präfixsummen (PS) + Elias-Fano (EF) codiert;
• Das wird in der binären Datei pef_trie.count.out serialisiert.

Beispiel 3

Der Befehl

 ./build_trie ef_trie 5 prob_backoff --remapping 2 --u -20.0 --p 8 --b 8 --arpa ../test_data/arpa --out ef_trie.prob_backoff.bin

baut einen Elias-Fano-Trie

• der Ordnung 5;
• das speichert Wahrscheinlichkeiten und Backoffs;
• mit kontextbasiertem Neuzuordnen von Order 2;
• mit <unk> Wahrscheinlichkeit von -20,0 und 8 Bit zur Quantisierung der Wahrscheinlichkeiten ( --p ) und Backoffs ( --b );
• aus der ARPA -Datei mit dem Namen arpa ;
• Das ist mit der binären Datei ef_trie.prob_backoff.bin serialisiert.

Beispiel 4

Der Befehl

 ./build_hash 5 8 count --dir ../test_data --out hash.bin

baut ein MPH-basierter Modell auf

• der Ordnung 5;
• Das verwendet 8 Bytes pro Hash -Schlüssel;
• das speichert die Frequenzzahlen;
• Aus dem n -Gram zählt Dateien, die im Verzeichnis test_data enthalten sind;
• Das wird mit dem Binärdatei hash.bin serialisiert.

Tests

Das test enthält die Unit -Tests einiger der grundlegenden Bausteine, die von den implementierten Datenstrukturen verwendet werden. Durch das Ausführen der ausführbaren Ausführungsfähigkeiten ohne Argumente wird die Liste ihrer erwarteten Eingabeparameter angezeigt. Beispiele:

 ./test_compact_vector 10000 13
./test_fast_ef_sequence 1000000 128

Das Verzeichnis enthält außerdem den Unit -Test für die Datenstrukturen, die die Frequenzzahlen namens check_count_model speichern, die die Implementierung validiert, indem er prüft, ob jede in der Datenstruktur gespeicherte Anzahl in den Eingabedateien, aus denen die Datenstruktur zuvor erstellt wurde, überprüft wird. Beispiel:

 ./test_count_model ef_trie.count.bin ../test_data

wobei ef_trie.count.bin der Name der Datenstruktur -Binärdatei ist (möglicherweise erstellt mit dem in Beispiel 1 angezeigten Befehl) und test_data der Name des Ordners, der die Eingabe n -Gram zählt, zählt Dateien.

Benchmarks

Für die Beispiele in diesem Abschnitt haben wir einen Desktop -Computer verwendet, der Mac OS X Mojave mit einem 2,3 -GHz -Intel Core i5 -Prozessor (als Desktop -Mac bezeichnet) ausgestattet ist. Der Code wurde mit Apple LLVM Version 10.0.0 clang mit allen Optimierungen zusammengestellt (siehe Abschnitt Erstellung des Codes). Wir replizieren zusätzlich einige Experimente mit einem Intel (R) Core (TM) i9-9900K CPU @ 3,60 GHz unter Ubuntu 19.04, 64 Bit (als Server Linux bezeichnet). In diesem Fall wurde der Code mit gcc 8.3.0 kompiliert.

Für eine Datenstruktur, die die Frequenzzahlen speichert, können wir die Geschwindigkeit der Nachschlaganfragen mit dem Benchmark -Programm lookup_perf_test testen. Im folgenden Beispiel zeigen wir, wie drei verschiedene Datenstrukturen erstellt und bewertet werden: EF-Trie ohne Neuapparp, EF-RTRIE mit Remapping Order 1 und PEF-Rtrie mit Neueinstellungsreihenfolge 2 (wir verwenden dieselben Namen für die in [1] dargestellten Datenstrukturen). Jedes Experiment wird 1.000 -mal in den queries.random.5K der Testabfragedatei.5k wiederholt. Das Benchmark -Programm lookup_perf_test zeigt die mittlere Zeit pro Lauf und die mittlere Zeit pro Abfrage an (zusammen mit der Gesamtzahl der n -Grams, der Gesamtbytes der Datenstruktur und Bytes pro n -Gram).

 ./build_trie ef_trie 5 count --dir ../test_data --out ef_trie.bin
./lookup_perf_test ef_trie.bin ../test_data/queries.random.5K 1000

./build_trie ef_trie 5 count --remapping 1 --dir ../test_data --out ef_trie.r1.bin
./lookup_perf_test ef_trie.r1.bin ../test_data/queries.random.5K 1000

./build_trie pef_trie 5 count --remapping 2 --dir ../test_data --out pef_trie.r2.bin
./lookup_perf_test pef_trie.r2.bin ../test_data/queries.random.5K 1000

Die Ergebnisse dieser (MICRO) Benchmark sind in der folgenden Tabelle zusammengefasst.

Datenstruktur	Neueinstellungsbestellung	Bytes x Gramm	µs x Query - Desktop -Mac	µs x Query - Server Linux
EF-Trie	0	2.40	0,435	0,316
Ef-rtrie	1	1,93 ( -19,7% )	0,583	0,428
Pef-rtrie	2	1,75 ( -26,9% )	0,595	0,427

Für eine Datenstruktur, die Wahrscheinlichkeiten und Backoffs speichert, können wir stattdessen die Geschwindigkeit der Bewertung einer Textdatei mithilfe der Benchmark score testen. Ein vollständiges Beispiel folgt.

 ./build_trie ef_trie 5 prob_backoff --u -10.0 --p 8 --b 8 --arpa ../test_data/arpa --out ef_trie.prob_backoff.8.8.bin
./score ef_trie.prob_backoff.8.8.bin ../test_data/sample_text

Der erste Befehl erstellt die Datenstruktur, die zweite bewertet den in test_data enthaltenen Textdatei sample_text . Die Eingabetextdatei muss einen Satz pro Zeile enthalten, wobei die durch Leerzeichen getrennten Wörter getrennt sind. Während der Bewertung der Datei wickeln wir nicht jeden Satz mit Markern <s> und </s> .

Ein Beispielerausgang könnte sein (OOV steht für Vokabular ):

 perplexity including OOVs = 493720.19
perplexity excluding OOVs = 1094.2574
OOVs = 55868
corpus tokens = 153583
corpus sentences = 6075
elapsed time: 0.037301 [sec]

Statistiken

Die ausführbaren print_stats können verwendet werden, um nützliche Statistiken bezüglich der Raumverwendung der verschiedenen Datenstrukturkomponenten (z. B. Gram-ID- und Zeigersequenzen für Versuche) sowie strukturelle Eigenschaften der indizierten n- Gram-Datensatz (z. B. Anzahl der eindeutigen Zählungen, max.

Beispielsweise der folgende Befehl:

 ./print_stats data_structure.bin

Zeigt die Statistiken für die Datenstruktur an, die in der Datei data_structure.bin serialisiert ist.

Python Wrapper

Das Verzeichnis python enthält einen einfachen Python -Wrapper mit einigen Beispielen. Schau dir das an!

Autoren

• Giulio ermanno pibiri, [email protected]
• Rossano Venturini, [email protected]

Bibliographie

• [1] Giulio Ermanno Pibiri und Rossano Venturini Effiziente Datenstrukturen für massive N-Gramm-Datensätze . In den Proceedings der 40-ten ACM-Konferenz über Forschung und Entwicklung im Informationsabruf (Sigir 2017): 615-624.
• [2] Giulio Ermanno Pibiri und Rossano Venturini. Umgang mit massiven N-Gramm-Datensätzen effizient. ACM-Transaktionen zu Informationssystemen (TOIS) 37.2 (2019): 1-41.