tongrams
1.0.0
Tongrams est une bibliothèque C ++ pour indexer et interroger les modèles de grands langues dans l'espace comprimé, comme décrit dans les articles suivants
par Giulio Ermanno Pibiri et Rossano Venturini. S'il vous plaît, citez ces papiers si vous utilisez des tongrams.
Plus précisément, les structures de données implémentées peuvent être utilisées pour mapper des n -grammes à leurs dénombrements de fréquences correspondants (entiers) ou aux probabilités (point flottantes) et backoffs pour les modèles Kneser-NEY interpolés à interpolation.
La bibliothèque dispose d'une structure de données TRIE compressée dans laquelle les n -grammes se voient attribuer des identifiants entiers (IDS) et compressés avec Elias-Fano pour prendre en charge les recherches efficaces dans l'espace comprimé. Le remappage basé sur le contexte de ces identifiants permet de coder un mot suivant un contexte de longueur fixe k , c'est-à-dire ses k mots précédents, avec un entier dont la valeur est délimitée par le nombre de mots qui suivent un tel contexte et non par la taille de l'ensemble du vocabulaire (nombre de grammes d'union). De plus, à la structure des données TRIE, la bibliothèque permet de créer des modèles en fonction du hachage parfait minimal (MPH), pour une récupération à temps constant.
Lorsqu'ils sont utilisés pour stocker les dénombrements de fréquences, les structures de données prennent en charge une opération lookup() qui renvoie le nombre d'occurrences du n -gram spécifié. Différemment, lorsqu'ils sont utilisés pour stocker les probabilités et les backoffs, les structures de données implémentent une fonction score() qui, étant donné un texte en entrée, calcule le score de perplexité du texte.
Ce guide vise à fournir un bref aperçu de la bibliothèque et à illustrer ses fonctionnalités à travers quelques exemples.
Le code a été testé sur Linux Ubuntu avec gcc 5.4.1, 7.3.0, 8.3.0, 9.0.0; Mac OS X El Capitan avec clang 7.3.0; Mac OS X Mojave avec clang 10.0.0.
Les dépendances suivantes sont nécessaires pour la construction: CMake et Boost .
Si vous avez cloné le référentiel sans --recursive , vous devrez effectuer les commandes suivantes avant la construction:
git submodule init
git submodule update
Pour construire le code sur les systèmes UNIX (voir le fichier CMakeLists.txt pour les drapeaux de compilation utilisés), il suffit de faire ce qui suit.
mkdir build
cd build
cmake ..
make
Vous pouvez activer la compilation parallèle en spécifiant certains travaux: make -j4 .
Pour le meilleur de la performance, compilez comme suit.
cmake .. -DCMAKE_BUILD_TYPE=Release -DTONGRAMS_USE_SANITIZERS=OFF -DEMPHF_USE_POPCOUNT=ON -DTONGRAMS_USE_POPCNT=ON -DTONGRAMS_USE_PDEP=ON
make
Pour un environnement de débogage, compilez comme suit à la place.
cmake .. -DCMAKE_BUILD_TYPE=Debug -DTONGRAMS_USE_SANITIZERS=ON
make
Sauf indication contraire, pour le reste de ce guide, nous supposons que nous tapons les commandes de terminal des exemples suivants de la build du répertoire créé.
Les fichiers N -gram Counts suivent le format Google, c'est-à-dire un fichier distinct pour chaque valeur distincte de N (Ordre) répertoriant une gramme par ligne. Nous enrichissons ce format avec un en-tête de fichier indiquant le nombre total de n -grammes dans le fichier (lignes):
<total_number_of_rows>
<gram1> <TAB> <count1>
<gram2> <TAB> <count2>
<gram3> <TAB> <count3>
...
Ces fichiers N doivent être nommés conformément à la convention suivante: <order>-grams , où <order> est un espace réservé pour la valeur de n . Les fichiers peuvent être laissés non triés si seuls les modèles basés sur MPH doivent être construits, tandis que ceux-ci doivent être triés dans l'ordre des préfixes pour les structures de données basées sur le trie, selon le mappage de vocabulaire choisi , qui doit être représenté par le fichier Uni-Gram (voir la sous-section 3.1 de [1]). La compression des fichiers d'entrée avec des services publics standard, tels que gzip , est fortement recommandé. L'utilitaire sort_grams peut être utilisé pour trier les fichiers N -Gram Nombre dans l'ordre du préfixe. En conclusion, les structures de données stockant les dénombrements de fréquences sont construites à partir d'un répertoire contenant les fichiers
1-grams.sorted.gz2-grams.sorted.gz3-grams.sorted.gzformaté comme expliqué ci-dessus.
Les fichiers répertoriant les probabilités et les backoffs n -gram sont conformes au format de fichier ARPA. Les N -Grams dans le fichier ARPA doivent être triés dans l'ordre du suffixe afin de créer la structure de données TRIE inversée. L'utilitaire sort_arpa peut être utilisé à cette fin.
Le répertoire test_data contient:
gzip ;queries.random.5K comprenant 5 000 n -grammes (1 000 pour chaque commande et dessinés au hasard);arpa qui répertorie tous les n- grammes triés dans un ordre de suffixe pour construire des essais en arrière efficacement;sample_text (6 075 phrase pour un total de 153 583 mots) utilisé pour le référence Perplexity; Son fichier compagnon sample_text.LESSER ne comprend que les 10 premières phrases. Pour les exemples suivants, nous supposons que nous fonctionnons avec les exemples de données contenues dans test_data .
Les deux exécutables build_trie et build_hash sont utilisés pour construire des modèles de langage basés sur des tricolores et (minimaux parfaits), respectivement. Exécutez les exécutables sans aucun argument à connaître leur utilisation.
Nous montrons maintenant quelques exemples.
La commande
./build_trie ef_trie 5 count --dir ../test_data --out ef_trie.count.bin
construit un trie elias-fano
test_data ;ef_trie.count.bin . La commande
./build_trie pef_trie 5 count --dir ../test_data --remapping 1 --ranks PSEF --out pef_trie.count.out
construit un trie d'Elias-Fano partitionné
test_data ;pef_trie.count.out . La commande
./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
construit un trie elias-fano
<unk> Probabilité de -20,0 et en utilisant 8 bits pour la quantification des probabilités ( --p ) et des backoffs ( --b );arpa ;ef_trie.prob_backoff.bin . La commande
./build_hash 5 8 count --dir ../test_data --out hash.bin
construit un modèle basé sur MPH
test_data ;hash.bin . Le répertoire test contient les tests unitaires de certains des éléments constitutifs fondamentaux utilisés par les structures de données implémentées. Comme d'habitude, l'exécution des exécutables sans aucun argument affichera la liste de leurs paramètres d'entrée attendus. Exemples:
./test_compact_vector 10000 13
./test_fast_ef_sequence 1000000 128
Le répertoire contient également le test unitaire pour les structures de données stockant le nombre de fréquences, nommé check_count_model , qui valide l'implémentation en vérifiant que chaque nombre stocké dans la structure de données est le même que celui fourni dans les fichiers d'entrée à partir desquels la structure de données a précédemment été construite. Exemple:
./test_count_model ef_trie.count.bin ../test_data
où ef_trie.count.bin est le nom du fichier binaire de structure de données (peut-être construit avec la commande illustrée dans l'exemple 1) et test_data est le nom du dossier contenant les fichiers d'entrée n -gram comptes.
Pour les exemples de cette section, nous avons utilisé une machine de bureau exécutant Mac OS X Mojave, équipé d'un processeur Intel Core i5 2,3 GHz (appelé Desktop Mac ). Le code a été compilé avec Apple LLVM version 10.0.0 clang avec toutes les optimisations (voir la section Créant le code). Nous reproduisons également certaines expériences avec un CPU Intel (R) Core (TM) I9-9900K @ 3,60 GHz, sous Ubuntu 19.04, 64 bits (appelé serveur Linux ). Dans ce cas, le code a été compilé avec gcc 8.3.0.
Pour une structure de données stockant le nombre de fréquences, nous pouvons tester la vitesse des requêtes de recherche en utilisant le programme de référence lookup_perf_test . Dans l'exemple suivant, nous montrons comment construire et comparer trois structures de données différentes: EF-Trie sans remappage, EF-RTrie avec ordre de remappage 1 et PEF-rtrie avec ordre de remappage 2 (nous utilisons les mêmes noms pour les structures de données que présentées dans [1]). Chaque expérience est répétée 1 000 fois sur les queries.random.5K de fichier de requête de test. Le programme de référence lookup_perf_test affichera le temps moyen par exécution et le temps moyen par requête (ainsi que le nombre total de n -grammes, les octets totaux de la structure de données et les octets par 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
Les résultats de ce (micro) référence sont résumés dans le tableau suivant.
| Structure de données | Commande de remappage | Octets x gramme | µs x requête - Mac de bureau | µs x requête - serveur 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 |
Pour une structure de données stockant les probabilités et les backoffs, nous pouvons plutôt tester la vitesse de notation d'un fichier texte en utilisant le score du programme de référence. Un exemple complet suit.
./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
La première commande créera la structure de données, la seconde marquera le fichier texte sample_text contenu dans test_data . Le fichier texte d'entrée doit contenir une phrase par ligne, avec des mots séparés par des espaces. Pendant la notation du fichier, nous n'enroulons pas chaque phrase avec des marqueurs <s> et </s> .
Une sortie examplaire pourrait être (OOV signifie hors du vocabulaire ):
perplexity including OOVs = 493720.19
perplexity excluding OOVs = 1094.2574
OOVs = 55868
corpus tokens = 153583
corpus sentences = 6075
elapsed time: 0.037301 [sec]
L'exécutable print_stats peut être utilisé pour recueillir des statistiques utiles concernant l'utilisation de l'espace des différents composants de la structure de données (par exemple, Gram-ID et séquences de pointeurs pour les essais), ainsi que les propriétés structurelles de l'ensemble de données N -Gram indexé (par exemple, le nombre de comptes uniques, les longueurs de plage Min / Max, l'espace moyen des séquences Gram-ID, Ecc.).
À titre d'exemple, la commande suivante:
./print_stats data_structure.bin
affichera les statistiques de la structure de données sérialisées dans le fichier data_structure.bin .
Le répertoire python comprend un simple wrapper python avec quelques exemples. Vérifiez ceci!
