tongrams
1.0.0
Tongrams é uma biblioteca C ++ para indexar e consultar grandes modelos de linguagem no espaço comprimido, conforme descrito nos documentos a seguir
Por Giulio Ermanno Pibiri e Rossano Venturini. Por favor, cite esses papéis se você usar tongrams.
Mais especificamente, as estruturas de dados implementadas podem ser usadas para mapear n -gramas para suas contagens de frequência correspondentes (inteiras) ou para (ponto flutuante) e probabilidades e retomfos para modelos de Kneser-ney interpolados por backoff.
A biblioteca apresenta uma estrutura de dados trie compactada na qual n -gramas são atribuídos identificadores inteiros (IDs) e compactados com Elias -Fano, para suportar pesquisas eficientes no espaço comprimido. O remapeamento baseado em contexto de tais identificadores permite codificar uma palavra após um contexto de comprimento fixo K , ou seja, suas palavras precedentes , com um número inteiro cujo valor é limitado pelo número de palavras que seguem esse contexto e não pelo tamanho de todo o vocabulário (número de uni-grama). Além da estrutura de dados Trie, a biblioteca permite criar modelos com base no hash perfeito mínimo (MPH), para recuperação de tempo constante.
Quando usados para armazenar contagens de frequência, as estruturas de dados suportam uma operação lookup() que retorna o número de ocorrências do n -grama especificado. Diferentemente, quando usados para armazenar probabilidades e retomfos, as estruturas de dados implementam uma função de score() que, dado um texto como entrada, calcula a pontuação perplexidade do texto.
Este guia visa fornecer uma breve visão geral da biblioteca e ilustrar suas funcionalidades através de alguns exemplos.
O código foi testado no Linux Ubuntu com gcc 5.4.1, 7.3.0, 8.3.0, 9.0.0; Mac OS X El Capitan com clang 7.3.0; Mac OS X Mojave com clang 10.0.0.
As seguintes dependências são necessárias para a compilação: CMake e Boost .
Se você clonou o repositório sem --recursive , precisará executar os seguintes comandos antes de criar:
git submodule init
git submodule update
Para criar o código nos sistemas UNIX (consulte o arquivo CMakeLists.txt para os sinalizadores de compilação usados), é suficiente fazer o seguinte.
mkdir build
cd build
cmake ..
make
Você pode ativar a compilação paralela especificando alguns trabalhos: make -j4 .
Para o Best of Performace, compile da seguinte forma.
cmake .. -DCMAKE_BUILD_TYPE=Release -DTONGRAMS_USE_SANITIZERS=OFF -DEMPHF_USE_POPCOUNT=ON -DTONGRAMS_USE_POPCNT=ON -DTONGRAMS_USE_PDEP=ON
make
Para um ambiente de depuração, compile o seguinte.
cmake .. -DCMAKE_BUILD_TYPE=Debug -DTONGRAMS_USE_SANITIZERS=ON
make
Salvo indicação em contrário, para o restante deste guia, assumimos que digitamos os comandos do terminal dos seguintes exemplos da build do diretório criado.
Os arquivos N -Gram Counts seguem o formato do Google, ou seja, um arquivo separado para cada valor distinto de n (ordem) listando um grama por linha. Enriquecemos este formato com um cabeçalho de arquivo indicando o número total de n -gramas no arquivo (linhas):
<total_number_of_rows>
<gram1> <TAB> <count1>
<gram2> <TAB> <count2>
<gram3> <TAB> <count3>
...
Esses arquivos N devem ser nomeados de acordo com a seguinte convenção: <order>-grams , onde <order> é um espaço reservado pelo valor de n . Os arquivos podem ser deixados não classificados se apenas os modelos baseados em MPH precisarem ser construídos, enquanto estes devem ser classificados na ordem de prefixo para estruturas de dados baseadas em trie, de acordo com o mapeamento de vocabulário escolhido , que deve ser representado pelo arquivo Uni-Rram (consulte a subseção 3.1 de [1]). Compressa os arquivos de entrada com utilitários padrão, como gzip , é altamente recomendado. Os utilitários sort_grams podem ser usados para classificar os arquivos N -Grama contagem no pedido de prefixo. Em conclusão, as estruturas de dados que armazenam contagens de frequência são construídas a partir de um diretório que contém os arquivos
1-grams.sorted.gz2-grams.sorted.gz3-grams.sorted.gzformatado conforme explicado acima.
A lista de arquivos N -Gram e as probabilidades e os backoffs está em conformidade com o formato do arquivo ARPA. Os n -grama no arquivo ARPA devem ser classificados na ordem do sufixo para criar a estrutura de dados TRIE reversa. O utilitário sort_arpa pode ser usado para esse fim.
O diretório test_data contém:
gzip ;queries.random.5K compreendendo 5.000 n -gramas (1.000 para cada pedido e desenhado aleatoriamente);arpa Arpa ARPA, que lista todos os n -Grams classificados em ordem de sufixo, para construir as tentativas para trás eficientemente;sample_text (6.075 frase para um total de 153.583 palavras) usada para a referência perplexidade; Seu arquivo complementar sample_text.LESSER inclui apenas as 10 primeiras frases. Para os exemplos a seguir, assumimos trabalhar com os dados de amostra contidos em test_data .
Os dois executáveis build_trie e build_hash são usados para criar modelos de idiomas baseados em trie e (mínimo perfeito), respectivamente. Execute os executáveis sem argumentos para saber sobre seu uso.
Agora mostramos alguns exemplos.
O comando
./build_trie ef_trie 5 count --dir ../test_data --out ef_trie.count.bin
Construa um trie Elias-Fano
test_data ;ef_trie.count.bin . O comando
./build_trie pef_trie 5 count --dir ../test_data --remapping 1 --ranks PSEF --out pef_trie.count.out
constrói um trie elias-fanó particionado
test_data ;pef_trie.count.out . O 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
Construa um trie Elias-Fano
<unk> probabilidade de -20,0 e usando 8 bits para quantizar probabilidades ( --p ) e backoffs ( --b );arpa ;ef_trie.prob_backoff.bin . O comando
./build_hash 5 8 count --dir ../test_data --out hash.bin
Construa um modelo baseado em MPH
test_data ;hash.bin . O diretório test contém os testes de unidade de alguns dos blocos fundamentais de construção usados pelas estruturas de dados implementadas. Como sempre, a execução dos executáveis sem argumentos mostrará a lista de seus parâmetros de entrada esperados. Exemplos:
./test_compact_vector 10000 13
./test_fast_ef_sequence 1000000 128
O diretório também contém o teste de unidade para as estruturas de dados que armazenam contagens de frequência, chamado check_count_model , que valida a implementação, verificando que cada contagem armazenada na estrutura de dados é a mesma que a fornecida nos arquivos de entrada a partir da qual a estrutura de dados foi criada anteriormente. Exemplo:
./test_count_model ef_trie.count.bin ../test_data
Onde ef_trie.count.bin é o nome do arquivo binário da estrutura de dados (talvez criado com o comando mostrado no Exemplo 1) e test_data é o nome da pasta que contém os arquivos de entrada n -grama.
Para os exemplos nesta seção, usamos uma máquina de desktop executando o Mac OS X Mojave, equipado com um processador Intel Core i5 de 2,3 GHz (referido como MAC da área de trabalho ). O código foi compilado com o Apple LLVM versão 10.0.0 clang com todas as otimizações (consulte a seção construindo o código). Além disso, replicamos algumas experiências com um núcleo Intel (R) (TM) I9-9900K CPU @ 3,60 GHz, no Ubuntu 19.04, 64 bits (referido como servidor Linux ). Nesse caso, o código foi compilado com gcc 8.3.0.
Para uma contagem de frequência de armazenamento da estrutura de dados, podemos testar a velocidade das consultas de pesquisa usando o programa de referência lookup_perf_test . No exemplo a seguir, mostramos como construir e comparar três estruturas de dados diferentes: EF-TRIE sem remapeamento, EF-RTRIE com a ordem de remapeamento 1 e PEF-rtrie com a ordem de remapeamento 2 (usamos os mesmos nomes para as estruturas de dados apresentadas em [1]). Cada experimento é repetido 1.000 vezes nas queries.random.5K de arquivo de consulta de teste.Random.5K. O programa Benchmark lookup_perf_test mostrará tempo médio por execução e tempo médio por consulta (juntamente com o número total de n -gramas, bytes totais da estrutura de dados e bytes por n -grama).
./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
Os resultados desta referência (micro) estão resumidos na tabela a seguir.
| Estrutura de dados | Ordem de remapeamento | Bytes x grama | µs x consulta - MAC de mesa | µs x consulta - servidor 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 |
Para uma estrutura de dados que armazena probabilidades e retomfos, podemos testar a velocidade de pontuar um arquivo de texto usando a score do programa de referência. Um exemplo completo segue.
./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
O primeiro comando criará a estrutura de dados, o segundo pontuará o arquivo de texto sample_text contido em test_data . O arquivo de texto de entrada deve conter uma frase por linha, com palavras separadas por espaços. Durante a pontuação do arquivo, não envolvemos cada frase com marcadores <s> e </s> .
Uma saída de exame pode ser (Oov significa fora do vocabulário ):
perplexity including OOVs = 493720.19
perplexity excluding OOVs = 1094.2574
OOVs = 55868
corpus tokens = 153583
corpus sentences = 6075
elapsed time: 0.037301 [sec]
Os print_stats executáveis podem ser usados para reunir estatísticas úteis sobre o uso de espaço dos vários componentes da estrutura de dados (por exemplo, sequências de Gram-ID e Pointer para tentativas), bem como propriedades estruturais do conjunto de dados N -RAM indexado (por exemplo, Número de Counts, Min/Max Comprimentos, GAP de seqüências GAP-ID.
Como exemplo, o seguinte comando:
./print_stats data_structure.bin
mostrará as estatísticas da estrutura de dados serializadas para o arquivo data_structure.bin .
O diretório python inclui um invólucro simples de Python com alguns exemplos. Confira isso!
