tongrams
1.0.0
如以下论文所述
由Giulio Ermanno Pibiri和Rossano Venturini撰写。如果您使用Tongrams，请引用这些论文。
更具体地说，实现的数据结构可用于将n个格映射到其相应的（整数）频率计数或（浮点）概率和向后交换的旋转旋钮模型的退缩概率和退缩。
该库具有压缩的TRIE数据结构，其中n-克分配了整数标识符（IDS），并用Elias -Fano压缩，以支持压缩空间内的有效搜索。基于上下文的重新映射允许按照固定长度k的上下文编码一个单词，即IE，其先前的k个单词和一个整数，其价值受遵循此上下文的单词数量的界限，而不是由整个词汇的大小（uni-gram的数量）。除了TRIE数据结构外，该库还允许基于最小的完美哈希（MPH）构建模型，以进行恒定的时间检索。
当用于存储频率计数时，数据结构支持lookup()操作，该操作返回指定的n -gram的出现数量。以不同的方式，当用来存储概率和退缩时，数据结构实现了一个score()函数，鉴于文本为输入，可以计算文本的困惑得分。
本指南旨在简要概述库，并通过一些示例来说明其功能。
该代码已在Linux Ubuntu上使用gcc 5.4.1、7.3.0、8.3.0、9.0.0进行了测试； Mac OS X El Capitan具有clang 7.3.0; Mac OS X Mojave，带有clang 10.0.0。
构建需要以下依赖关系： CMake和Boost 。
如果您无需--recursive将存储库克隆，则需要在构建之前执行以下命令：
git submodule init
git submodule update
要在UNIX系统上构建代码（请参阅File CMakeLists.txt以获取使用的汇编标志），就足以进行以下操作。
mkdir build
cd build
cmake ..
make
您可以通过指定一些作业来启用并行汇编： make -j4 。
为了表现最好的表演，请按以下方式进行编译。
cmake .. -DCMAKE_BUILD_TYPE=Release -DTONGRAMS_USE_SANITIZERS=OFF -DEMPHF_USE_POPCOUNT=ON -DTONGRAMS_USE_POPCNT=ON -DTONGRAMS_USE_PDEP=ON
make
对于调试环境，相反，编译如下。
cmake .. -DCMAKE_BUILD_TYPE=Debug -DTONGRAMS_USE_SANITIZERS=ON
make
除非另有说明，否则对于本指南的其余部分，我们假设我们从创建的目录build中键入以下示例的终端命令。
n -gram计数文件遵循Google格式，即，对于n （顺序）列出每行1克的每个不同值的一个单独的文件。我们使用文件标头来丰富此格式，该文件标头指示文件中的n个格总数（行）：
<total_number_of_rows>
<gram1> <TAB> <count1>
<gram2> <TAB> <count2>
<gram3> <TAB> <count3>
...
此类n文件必须根据以下约定命名： <order>-grams ，其中<order>是n值的占位符。如果仅必须构建基于MPH的模型，则可以将这些文件放在未分类中，而根据所选的词汇映射，这些文件必须以基于TRIE的数据结构的前缀顺序进行排序，该词汇映射应由Uni-Gram文件表示（请参阅[1]的第3.1款）。强烈建议使用标准实用程序（例如gzip ）压缩输入文件。实用程序sort_grams可用于按前缀顺序排列n -gral计数文件。总之，存储频率计数的数据结构是由包含文件的目录构建的
1-grams.sorted.gz2-grams.sorted.gz3-grams.sorted.gz格式如上所述。
文件列表n -gram概率和退缩符合ARPA文件格式。 ARPA文件中的n个格必须以后缀顺序排序，以构建相反的TRIE数据结构。实用程序sort_arpa可用于此目的。
目录test_data包含：
gzip压缩；queries.random.5K包括5,000 n -grams（每个订单为1,000，并随机绘制）；arpa列出了以后缀顺序排序的所有N -gram以构建向后尝试有效的。sample_text查询文件（总共153,583个单词的6,075个句子）；它的伴随sample_text.LESSER文件仅包含前10个句子。对于以下示例，我们假设与test_data中包含的示例数据一起工作。
两个可执行文件build_trie和build_hash分别用于构建基于TRIE的和（最少）基于哈希的语言模型。在没有任何争论的情况下运行可执行文件。
我们现在显示一些例子。
命令
./build_trie ef_trie 5 count --dir ../test_data --out ef_trie.count.bin
建造一个Elias-Fano Trie
test_data中包含的文件；ef_trie.count.bin 。 命令
./build_trie pef_trie 5 count --dir ../test_data --remapping 1 --ranks PSEF --out pef_trie.count.out
建立一个分区的Elias-Fano Trie
test_data中包含的文件；pef_trie.count.out 。 命令
./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
建造一个Elias-Fano Trie
<unk>量化概率（ --p ）和退缩（ --b ）；arpa的ARPA文件；ef_trie.prob_backoff.bin 。 命令
./build_hash 5 8 count --dir ../test_data --out hash.bin
建立基于MPH的模型
test_data中包含的文件；hash.bin 。 该test目录包含实现数据结构使用的一些基本构件的单位测试。像往常一样，在没有任何参数的情况下运行可执行文件将显示其预期输入参数的列表。示例：
./test_compact_vector 10000 13
./test_fast_ef_sequence 1000000 128
该目录还包含存储频率计数的数据结构的单元测试，该计数名为check_count_model ，该计数通过检查数据结构中存储的每个计数是否与先前构建数据结构的输入文件中提供的每个计数相同，从而验证了实现。例子：
./test_count_model ef_trie.count.bin ../test_data
其中ef_trie.count.bin是数据结构二进制文件的名称（也许是使用示例1中显示的命令构建），而test_data是包含输入n -gram计数文件的文件夹的名称。
对于本节中的示例，我们使用了运行Mac OS X Mojave的台式机，该台式机配备了2.3 GHz Intel Core i5处理器（称为Desktop Mac ）。该代码与Apple LLVM版本10.0.0 clang一起编译，并具有所有优化（请参阅“构建代码”部分）。我们还使用Intel（R）Core（TM）I9-9900K CPU @ 3.60 GHz复制一些实验，在Ubuntu 19.04下，64位（称为Server Linux ）。在这种情况下，该代码是用gcc 8.3.0编译的。
对于数据结构存储频率计数，我们可以使用基准程序lookup_perf_test测试查找查询速度。在下面的示例中，我们显示了如何构建和基准测试三个不同的数据结构： ef-trie ，没有重新映射， ef-rtrie具有重新映射订单1和带有重新映射订单2的pef-rtrie （我们使用[1]中列出的数据结构使用相同的名称）。每个实验在测试查询文件queries.random.5K中重复1,000次。random.5k。基准程序lookup_perf_test将显示每次运行的平均时间和每个查询的平均时间（以及n -gram的总数，数据结构的总字节和每个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
下表总结了该（微）基准的结果。
| 数据结构 | 重新订单 | 字节X克 | µs x查询- 桌面Mac | µs x查询- 服务器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 |
对于数据结构存储概率和退缩，我们可以使用基准程序score测试得分文本文件的速度。如下一个完整的示例。
./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
第一个命令将构建数据结构，第二个命令将为test_data中包含的文本文件sample_text评分。输入文本文件必须包含每行的一个句子，其中单词被空间隔开。在文件评分期间，我们不会用标记<s>和</s>包裹每个句子。
可以是检查程序输出（OOV代表词汇量）：
perplexity including OOVs = 493720.19
perplexity excluding OOVs = 1094.2574
OOVs = 55868
corpus tokens = 153583
corpus sentences = 6075
elapsed time: 0.037301 [sec]
可执行的print_stats可用于收集有关各种数据结构组件的空间使用情况（例如，用于尝试的gram-id和指针序列）的有用统计信息，以及索引n -gram数据集的结构属性（例如，唯一计数的数量，min/max范围的数量，min/max范围的数量，min/max范围，平均差异序列的平均差距，革兰氏集序列的平均差距，cr ecc。）。
例如，以下命令：
./print_stats data_structure.bin
将显示序列化到文件data_structure.bin数据结构的统计信息。
目录python包括一个简单的Python包装器，其中包含一些示例。检查一下！
