tongrams
1.0.0
Tongramsは、次の論文で説明されているように、圧縮空間で大規模な言語モデルをインデックス化およびクエリするためのC ++ライブラリです
Giulio Ermanno PibiriとRossano Venturini。 Tongramsを使用する場合は、これらの論文を引用してください。
より具体的には、実装されたデータ構造を使用して、 n -gramsを対応する（整数）周波数カウントにマッピングするか、バックオフインタル型Kneser-Neyモデルの（浮動小数点）確率とバックオフにマッピングできます。
ライブラリは、圧縮された空間内での効率的な検索をサポートするために、 n -gramsが整数識別子（ID）を割り当てられ、 Elias -Fanoで圧縮される圧縮されたTrieデータ構造を備えています。このような識別子のコンテキストベースの再マッピングにより、固定長k 、すなわち前のk単語のコンテキストに従って単語をエンコードすることができます。その値は、語彙全体のサイズ（ユニグラム数）ではなく、そのようなコンテキストに続く単語の数に境界を絞る整数を使用します。 TRIEデータ構造に加えて、ライブラリは、最小限の完全なハッシュ（MPH）に基づいてモデルを構築できます。
周波数カウントを保存するために使用すると、データ構造は、指定されたn -gramの発生数を返すlookup()操作をサポートします。違う場合、確率とバックオフを保存するために使用すると、データ構造は、テキストを入力として与えられたscore()関数を実装し、テキストの困惑スコアを計算します。
このガイドは、ライブラリの簡単な概要を提供し、いくつかの例を通じてその機能を説明することを目的としています。
このコードは、 gcc 5.4.1、7.3.0、8.3.0、9.0.0でLinux Ubuntuでテストされています。 Mac OS X El Capitan with clang 7.3.0; Mac OS X Mojave with clang 10.0.0。
ビルドには、次の依存関係が必要です： CMake and Boost 。
--recursiveなしでリポジトリをクローニングした場合、構築する前に次のコマンドを実行する必要があります。
git submodule init
git submodule update
UNIXシステムにコードを構築するには（使用されているコンピレーションフラグについては、ファイルCMakeLists.txt参照）、以下を実行するのに十分です。
mkdir build
cd build
cmake ..
make
いくつかのジョブを指定することにより、並列コンピレーションを有効にすることができます： make -j4 。
Best of Performaceについては、次のようにコンパイルします。
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カウントファイルは、 n （順序）の個別の値ごとに1つの個別のファイルに従って、1行ごとに1グラムをリストします。ファイル（行）内のn -gramsの総数を示すファイルヘッダーでこの形式を濃縮します。
<total_number_of_rows>
<gram1> <TAB> <count1>
<gram2> <TAB> <count2>
<gram3> <TAB> <count3>
...
このようなnファイルは、次の規則に従って命名する必要があります。 <order>-grams 。 <order>はnの値のプレースホルダーです。 MPHベースのモデルのみをビルドする必要がある場合は、ファイルを未解決のままにすることができますが、選択した語彙マッピングに従って、これらはUni-Gramファイルで表現する必要がある（[1]のサブセクション3.1を参照）、Trieベースのデータ構造のプレフィックス順序でソートする必要があります。 gzipなどの標準ユーティリティを使用して入力ファイルを圧縮することを強くお勧めします。ユーティリティsort_gramsを使用して、 N -Gramカウントファイルをプレフィックス順にソートできます。結論として、周波数カウントを保存するデータ構造は、ファイルを含むディレクトリから構築されます
1-grams.sorted.gz2-grams.sorted.gz3-grams.sorted.gz上記のようにフォーマットされています。
n -gramの確率とバックオフをリストするファイルは、代わりにARPAファイル形式に準拠しています。 ARPAファイルのn -gramsは、逆のTrieデータ構造を構築するために、接尾辞の順序でソートする必要があります。ユーティリティsort_arpaは、その目的に使用できます。
ディレクトリtest_dataには以下が含まれます。
gzipで圧縮します。queries.random.5K 5,000 n -grams（各注文に1,000、ランダムに描画）。arpa 。sample_textクエリファイル（合計153,583語の6,075文）は、困惑ベンチマークに使用されます。そのコンパニオンサンプルsample_text.LESSERファイルには、最初の10文のみが含まれています。次の例では、 test_dataに含まれるサンプルデータを使用して作業すると想定しています。
2つの実行可能ファイルbuild_trieとbuild_hash 、それぞれTrieベースと（最小限の）ハッシュベースの言語モデルを構築するために使用されます。法律の使用について知るために、議論なしで実行可能ファイルを実行します。
今、いくつかの例を示します。
コマンド
./build_trie ef_trie 5 count --dir ../test_data --out ef_trie.count.bin
エリアスファノトリーを構築します
test_dataに含まれるファイルをカウントします。ef_trie.count.binにシリアルされています。 コマンド
./build_trie pef_trie 5 count --dir ../test_data --remapping 1 --ranks PSEF --out pef_trie.count.out
分割されたエリアスファノトリーを構築します
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
エリアスファノトリーを構築します
<unk> 、および確率を量子化するために8ビットを使用して（ --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カウントファイルを含むフォルダーの名前です。
このセクションの例では、2.3 GHz Intel Core I5プロセッサ（デスクトップMACと呼ばれる）を備えたMac OS X Mojaveを実行するデスクトップマシンを使用しました。このコードは、すべての最適化を備えたApple LLVMバージョン10.0.0 clangでコンパイルされました（コードの構築セクションを参照）。さらに、Intel（R）コア（TM）I9-9900K CPU @ 3.60 GHz、Ubuntu 19.04、64ビット（サーバーLinuxと呼ばれる）でいくつかの実験を再現します。この場合、コードはgcc 8.3.0でコンパイルされました。
周波数カウントを保存するデータ構造の場合、ベンチマークプログラムlookup_perf_testを使用して、ルックアップクエリの速度をテストできます。次の例では、3つの異なるデータ構造を構築およびベンチマークする方法を示します：再マッピングなしのEFトリー、再マッピングオーダー1のEF-RTRIE 、およびRemapping Order 2のPEF-RTRIE （[1]で提示されたデータ構造に同じ名前を使用します）。各実験は、テストクエリファイルqueries.random.5K 。ベンチマークプログラムlookup_perf_test 、実行あたりの平均時間とクエリごとの平均時間を示します（ n -gramsの総数、データ構造の合計バイト、 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クエリ-DesktopMac | µ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
最初のコマンドはデータ構造を構築し、2番目のコマンドはtest_dataに含まれるテキストファイルのsample_textをスコアリングします。入力テキストファイルには、単語がスペースで区切られた1行ごとに1つの文を含める必要があります。ファイルのスコアリング中、各文をマーカー<s>および</s>で包みません。
Examplarの出力は（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使用して、さまざまなデータ構造コンポーネント（たとえば、トライのためのグラムIDおよびポインターシーケンスなど）のスペース使用に関する有用な統計、およびインデックス付きn -gramデータセットの構造的特性（例えば、一意のカウント数、min/max範囲長、平均Gram-idシーケンス、ecc。）の構造的特性を収集できます。
例として、次のコマンド：
./print_stats data_structure.bin
ファイルdata_structure.binにシリアル化されたデータ構造の統計が表示されます。
ディレクトリpythonには、いくつかの例があるシンプルなPythonラッパーが含まれています。これをチェックしてください！
