tongrams
1.0.0
Tongrams es una biblioteca C ++ para indexar y consultar modelos de lenguaje grande en el espacio comprimido, como se describe en los siguientes documentos
por Giulio Ermanno Pibiri y Rossano Venturini. Por favor, cita estos documentos si usa tongrams.
Más específicamente, las estructuras de datos implementadas se pueden usar para mapear n -grams a sus recuentos de frecuencia (enteros) correspondientes o a probabilidades y probabilidades (punto flotante) y retroceso para los modelos Kneser-Rney interpolados con retroceso.
La biblioteca presenta una estructura de datos TRIE comprimida en la que los n -grams se asignan identificadores enteros (ID) y se comprimen con Elias -Fano para admitir búsquedas eficientes dentro del espacio comprimido. La reasignación basada en el contexto de tales identificadores permite codificar una palabra que sigue un contexto de longitud fija k , es decir, sus palabras k anteriores, con un entero cuyo valor está limitado por el número de palabras que siguen dicho contexto y no por el tamaño de todo el vocabulario (número de uni-gramos). Además de la estructura de datos de TRIE, la biblioteca permite construir modelos basados en un hashing mínimo perfecto (MPH), para la recuperación de tiempo constante.
Cuando se usa para almacenar recuentos de frecuencia, las estructuras de datos admiten una operación lookup() que devuelve el número de ocurrencias del N -gram especificado. De manera diferente, cuando se usa para almacenar probabilidades y retroceso, las estructuras de datos implementan una función score() que, dada un texto como entrada, calcula la puntuación de perplejidad del texto.
Esta guía está destinada a proporcionar una breve descripción de la biblioteca e ilustrar sus funcionalidades a través de algunos ejemplos.
El código se ha probado en Linux Ubuntu con gcc 5.4.1, 7.3.0, 8.3.0, 9.0.0; Mac OS X El Capitan con clang 7.3.0; Mac OS X Mojave con clang 10.0.0.
Se necesitan las siguientes dependencias para la compilación: CMake y Boost .
Si ha clonado el Repositorio sin --recursive , deberá realizar los siguientes comandos antes de construir:
git submodule init
git submodule update
Para construir el código en los sistemas UNIX (consulte el archivo CMakeLists.txt para los indicadores de compilación usados), es suficiente hacer lo siguiente.
mkdir build
cd build
cmake ..
make
Puede habilitar la compilación paralela especificando algunos trabajos: make -j4 .
Para lo mejor de Performace, compile de la siguiente manera.
cmake .. -DCMAKE_BUILD_TYPE=Release -DTONGRAMS_USE_SANITIZERS=OFF -DEMPHF_USE_POPCOUNT=ON -DTONGRAMS_USE_POPCNT=ON -DTONGRAMS_USE_PDEP=ON
make
Para un entorno de depuración, compile de la siguiente manera.
cmake .. -DCMAKE_BUILD_TYPE=Debug -DTONGRAMS_USE_SANITIZERS=ON
make
A menos que se especifique lo contrario, para el resto de esta guía suponemos que escribimos los comandos de terminales de los siguientes ejemplos de la build del directorio creado.
Los archivos de N -gram cuenta siguen el formato de Google, es decir, un archivo separado para cada valor distinto de n (orden) que enumera un gramo por fila. Enriquecemos este formato con un encabezado de archivo que indica el número total de N -grams en el archivo (filas):
<total_number_of_rows>
<gram1> <TAB> <count1>
<gram2> <TAB> <count2>
<gram3> <TAB> <count3>
...
Dichos archivos n deben nombrarse de acuerdo con la siguiente convención: <order>-grams , donde <order> es un marcador de posición para el valor de n . Los archivos se pueden dejar sin clasificar si solo se deben construir modelos basados en MPH, mientras que estos deben ordenarse en orden de prefijo para las estructuras de datos basadas en TRIE, de acuerdo con el mapeo de vocabulario elegido , que debe estar representado por el archivo uni-gram (ver la subsección 3.1 de [1]). Es muy recomendable que comprimir los archivos de entrada con utilidades estándar, como gzip . La utilidad sort_grams se puede usar para ordenar los archivos de N -gram cuenta en el orden de prefijo. En conclusión, los recuentos de frecuencia de almacenamiento de estructuras de datos se construyen a partir de un directorio que contiene los archivos
1-grams.sorted.gz2-grams.sorted.gz3-grams.sorted.gzformateado como se explicó anteriormente.
La lista de archivos N -gram Probabilidades y retacos se ajusta a, en cambio, al formato de archivo ARPA. Los N -grams en el archivo ARPA deben ordenarse en orden sufijo para construir la estructura de datos de TRIE invertida. La utilidad sort_arpa se puede usar para ese propósito.
El directorio test_data contiene:
gzip ;queries.random.5K que comprende 5,000 n -grams (1,000 para cada pedido y dibujado al azar);arpa que enumera todos los n -grams ordenados en orden de sufijo para construir los intentos hacia atrás de manera eficiente;sample_text (6.075 oración para un total de 153,583 palabras) utilizado para el punto de referencia de perplejidad; Su archivo complementario sample_text.LESSER incluye solo las primeras 10 oraciones. Para los siguientes ejemplos, suponemos que funciona con los datos de muestra contenidos en test_data .
Los dos ejecutables build_trie y build_hash se utilizan para construir modelos de idiomas hash basados en TRIE y (mínimos perfectos), respectivamente. Ejecute los ejecutables sin ningún argumento para saber sobre su uso.
Ahora mostramos algunos ejemplos.
El comando
./build_trie ef_trie 5 count --dir ../test_data --out ef_trie.count.bin
construye un trie de elias-fano
test_data ;ef_trie.count.bin . El comando
./build_trie pef_trie 5 count --dir ../test_data --remapping 1 --ranks PSEF --out pef_trie.count.out
Construye un trie de Elias-Fano dividido
test_data ;pef_trie.count.out . El comando
./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
construye un trie de elias-fano
<unk> para cuantificar probabilidades ( --p ) y backoffs ( --b );arpa ;ef_trie.prob_backoff.bin . El comando
./build_hash 5 8 count --dir ../test_data --out hash.bin
Construye un modelo basado en MPH
test_data ;hash.bin . El directorio test contiene las pruebas unitarias de algunos de los bloques de construcción fundamentales utilizados por las estructuras de datos implementadas. Como de costumbre, ejecutar los ejecutables sin ningún argumento mostrará la lista de sus parámetros de entrada esperados. Ejemplos:
./test_compact_vector 10000 13
./test_fast_ef_sequence 1000000 128
El directorio también contiene la prueba unitaria para los recuentos de frecuencia de almacenamiento de estructuras de datos, llamado check_count_model , que valida la implementación verificando que cada recuento almacenado en la estructura de datos es el mismo que el proporcionado en los archivos de entrada a partir de los cuales se construyó la estructura de datos previamente. Ejemplo:
./test_count_model ef_trie.count.bin ../test_data
Donde ef_trie.count.bin es el nombre del archivo binario de la estructura de datos (tal vez construido con el comando que se muestra en el ejemplo 1) y test_data es el nombre de la carpeta que contiene los archivos de entrada n -gram de entrada.
Para los ejemplos en esta sección, utilizamos una máquina de escritorio que ejecuta Mac OS X Mojave, equipada con un procesador Intel Core i5 de 2.3 GHz (denominado Mac de escritorio ). El código se compiló con Apple LLVM Versión 10.0.0 clang con todas las optimizaciones (consulte Sección Construir el código). Además, replicamos algunos experimentos con un núcleo Intel (R) (TM) I9-9900K CPU @ 3.60 GHz, bajo Ubuntu 19.04, 64 bits (denominado servidor Linux ). En este caso, el código se compiló con gcc 8.3.0.
Para una estructura de datos de almacenamiento de frecuencia de almacenamiento, podemos probar la velocidad de las consultas de búsqueda utilizando el programa Benchmark lookup_perf_test . En el siguiente ejemplo, mostramos cómo construir y comparar tres estructuras de datos diferentes: EF-trie sin reasignación, EF-Rtrie con orden de reasignación 1 y PEF-Rtrie con orden de reasignación 2 (usamos los mismos nombres para las estructuras de datos presentadas en [1]). Cada experimento se repite 1,000 veces sobre las queries.random.5K del archivo de consulta de prueba.random.5k. El programa Benchmark lookup_perf_test mostrará tiempo medio por ejecución y tiempo medio por consulta (junto con el número total de n -gramos, bytes totales de la estructura de datos y bytes por 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
Los resultados de este punto de referencia (micro) se resumen en la siguiente tabla.
| Estructura de datos | Orden de reasignación | Bytes x gramo | µs x consulta - Desktop Mac | µs x consulta - servidor Linux |
|---|---|---|---|---|
| Tre-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 |
Para una estructura de datos que almacena probabilidades y retrocesos, podemos probar la velocidad de calificar un archivo de texto utilizando la score del programa de referencia. Sigue un ejemplo completo.
./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
El primer comando construirá la estructura de datos, el segundo obtendrá el archivo de texto sample_text contenido en test_data . El archivo de texto de entrada debe contener una oración por línea, con palabras separadas por espacios. Durante la puntuación del archivo, no envolvemos cada oración con marcadores <s> y </s> .
Se podría ser una salida de ejemplo (OOV representa fuera del vocabulario ):
perplexity including OOVs = 493720.19
perplexity excluding OOVs = 1094.2574
OOVs = 55868
corpus tokens = 153583
corpus sentences = 6075
elapsed time: 0.037301 [sec]
El Ejecutable print_stats se puede utilizar para recopilar estadísticas útiles sobre el uso del espacio de los diversos componentes de la estructura de datos (p. Ej., ID y secuencias de puntero para intentos), así como propiedades estructurales del conjunto de datos N -gram indexado (p. Ej.
Como ejemplo, el siguiente comando:
./print_stats data_structure.bin
Mostrará las estadísticas de la estructura de datos serializada en el archivo data_structure.bin .
El Directorio python incluye una envoltura de pitón simple con algunos ejemplos. ¡Mira esto!
