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包裝器，其中包含一些示例。檢查一下！
