tongrams
1.0.0
Tongrams adalah perpustakaan C ++ untuk mengindeks dan meminta model bahasa besar dalam ruang terkompresi, seperti yang dijelaskan dalam makalah berikut
Oleh Giulio Ermanno Pibiri dan Rossano Venturini. Tolong, kutip kertas ini jika Anda menggunakan tongram.
Lebih khusus lagi, struktur data yang diimplementasikan dapat digunakan untuk memetakan n -gram ke jumlah frekuensi (integer) yang sesuai atau untuk probabilitas (titik mengambang) dan backoff untuk model Kneser-Ney yang diinterpolasi.
Perpustakaan fitur struktur data trie terkompresi di mana n -grams ditugaskan pengidentifikasi integer (ID) dan dikompresi dengan Elias -Fano untuk mendukung pencarian yang efisien dalam ruang terkompresi. Pengembalian pengidentifikasi yang berbasis konteks memungkinkan untuk menyandikan kata mengikuti konteks panjang tetap k , yaitu, kata-kata k sebelumnya, dengan bilangan bulat yang nilainya dibatasi oleh jumlah kata yang mengikuti konteks tersebut dan bukan dengan ukuran seluruh kosa kata (jumlah uni-gram). Selain struktur data trie, perpustakaan memungkinkan untuk membangun model berdasarkan minimal sempurna hashing (mph), untuk pengambilan waktu konstan.
Ketika digunakan untuk menyimpan jumlah frekuensi, struktur data mendukung operasi lookup() yang mengembalikan jumlah kejadian dari n -gram yang ditentukan. Secara berbeda, ketika digunakan untuk menyimpan probabilitas dan backoff, struktur data menerapkan fungsi score() yang, diberi teks sebagai input, menghitung skor kebingungan teks.
Panduan ini dimaksudkan untuk memberikan gambaran singkat tentang perpustakaan dan untuk menggambarkan fungsinya melalui beberapa contoh.
Kode telah diuji di Linux Ubuntu dengan gcc 5.4.1, 7.3.0, 8.3.0, 9.0.0; Mac OS X El Capitan dengan clang 7.3.0; Mac OS X Mojave dengan clang 10.0.0.
Ketergantungan berikut diperlukan untuk build: CMake dan Boost .
Jika Anda telah mengkloning repositori tanpa --recursive , Anda harus melakukan perintah berikut sebelum membangun:
git submodule init
git submodule update
Untuk membangun kode pada sistem UNIX (lihat file CMakeLists.txt untuk bendera kompilasi yang digunakan), cukup untuk melakukan hal berikut.
mkdir build
cd build
cmake ..
make
Anda dapat mengaktifkan kompilasi paralel dengan menentukan beberapa pekerjaan: make -j4 .
Untuk Best of Performace, kompilasi sebagai berikut.
cmake .. -DCMAKE_BUILD_TYPE=Release -DTONGRAMS_USE_SANITIZERS=OFF -DEMPHF_USE_POPCOUNT=ON -DTONGRAMS_USE_POPCNT=ON -DTONGRAMS_USE_PDEP=ON
make
Untuk lingkungan debug, kompilasi sebagai berikut.
cmake .. -DCMAKE_BUILD_TYPE=Debug -DTONGRAMS_USE_SANITIZERS=ON
make
Kecuali ditentukan lain, untuk sisa panduan ini kami berasumsi bahwa kami mengetikkan perintah terminal dari contoh -contoh berikut dari build yang dibuat.
N -gram menghitung file mengikuti format google, yaitu, satu file terpisah untuk setiap nilai berbeda dari n (pesanan) yang mencantumkan satu gram per baris. Kami memperkaya format ini dengan header file yang menunjukkan jumlah total n -gram dalam file (baris):
<total_number_of_rows>
<gram1> <TAB> <count1>
<gram2> <TAB> <count2>
<gram3> <TAB> <count3>
...
File N tersebut harus dinamai sesuai dengan Konvensi berikut: <order>-grams , di mana <order> adalah placeholder untuk nilai n . File-file tersebut dapat dibiarkan tidak disortir jika hanya model berbasis MPH yang harus dibangun, sedangkan ini harus diurutkan dalam urutan awalan untuk struktur data berbasis trie, menurut pemetaan kosa kata yang dipilih , yang harus diwakili oleh file uni-gram (lihat ayat 3.1 dari [1]). Mengompres file input dengan utilitas standar, seperti gzip , sangat disarankan. Utility sort_grams dapat digunakan untuk mengurutkan file n -gram dalam urutan awalan. Sebagai kesimpulan, jumlah data yang menyimpan jumlah frekuensi dibangun dari direktori yang berisi file
1-grams.sorted.gz2-grams.sorted.gz3-grams.sorted.gzdiformat seperti yang dijelaskan di atas.
Listing file n -gram probabilitas dan backoff sesuai dengan, sebagai gantinya, format file ARPA. N -gram dalam file ARPA harus diurutkan dalam urutan akhiran untuk membangun struktur data trie terbalik. Utility sort_arpa dapat digunakan untuk tujuan itu.
Direktori test_data berisi:
gzip ;queries.random.5K kueri kueri.arpa yang mencantumkan semua n -gram diurutkan dalam urutan akhiran untuk membangun ke belakang mencoba secara efisien;sample_text (6.075 kalimat untuk total 153.583 kata) yang digunakan untuk patokan kebingungan; File pendamping sample_text.LESSER hanya mencakup 10 kalimat pertama. Untuk contoh -contoh berikut, kami mengasumsikan untuk bekerja dengan data sampel yang terkandung dalam test_data .
Dua executable build_trie dan build_hash digunakan untuk membangun model bahasa berbasis trie dan (minimal sempurna) masing-masing. Jalankan yang dapat dieksekusi tanpa argumen untuk mengetahui tentang penggunaannya.
Kami sekarang menunjukkan beberapa contoh.
Perintah
./build_trie ef_trie 5 count --dir ../test_data --out ef_trie.count.bin
Membangun trie elias-fano
test_data ;ef_trie.count.bin . Perintah
./build_trie pef_trie 5 count --dir ../test_data --remapping 1 --ranks PSEF --out pef_trie.count.out
Membangun trie Elias-Fano yang dipartisi
test_data ;pef_trie.count.out . Perintah
./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
Membangun trie elias-fano
<unk> probabilitas -20.0 dan menggunakan 8 bit untuk mengukur probabilitas ( --p ) dan backoff ( --b );arpa ;ef_trie.prob_backoff.bin . Perintah
./build_hash 5 8 count --dir ../test_data --out hash.bin
Membangun model berbasis MPH
test_data ;hash.bin . Direktori test berisi uji unit dari beberapa blok bangunan mendasar yang digunakan oleh struktur data yang diimplementasikan. Seperti biasa, menjalankan executable tanpa argumen apa pun akan menunjukkan daftar parameter input yang diharapkan. Contoh:
./test_compact_vector 10000 13
./test_fast_ef_sequence 1000000 128
Direktori ini juga berisi uji unit untuk jumlah data yang menyimpan jumlah frekuensi, bernama check_count_model , yang memvalidasi implementasi dengan memeriksa bahwa setiap jumlah yang disimpan dalam struktur data sama dengan yang disediakan dalam file input dari mana struktur data sebelumnya dibangun. Contoh:
./test_count_model ef_trie.count.bin ../test_data
di mana ef_trie.count.bin adalah nama file biner struktur data (mungkin dibangun dengan perintah yang ditunjukkan pada contoh 1) dan test_data adalah nama folder yang berisi file input n -gram.
Untuk contoh di bagian ini, kami menggunakan mesin desktop yang menjalankan Mac OS X Mojave, dilengkapi dengan prosesor Intel Core i5 2,3 GHz (disebut sebagai desktop Mac ). Kode ini dikompilasi dengan clang Apple LLVM versi 10.0.0 dengan semua optimisasi (lihat bagian membangun kode). Kami juga mereplikasi beberapa percobaan dengan Intel (R) Core (TM) I9-9900K CPU @ 3.60 GHz, di bawah Ubuntu 19.04, 64 bit (disebut sebagai server Linux ). Dalam hal ini kode dikompilasi dengan gcc 8.3.0.
Untuk jumlah frekuensi penyimpanan struktur data, kami dapat menguji kecepatan permintaan pencarian dengan menggunakan program benchmark lookup_perf_test . Dalam contoh berikut, kami menunjukkan cara membangun dan membandingkan tiga struktur data yang berbeda: EF-TRIE tanpa memetakan ulang, EF-RTRIE dengan memetakan ulang pesanan 1 dan PEF-RTRIE dengan Pesan Pesan 2 (kami menggunakan nama yang sama untuk struktur data seperti yang disajikan dalam [1]). Setiap percobaan diulangi 1.000 kali selama queries.random.5K file kueri uji.random.5k. Program benchmark lookup_perf_test akan menunjukkan waktu rata -rata per run dan waktu rata -rata per kueri (bersama dengan jumlah total n -gram, total byte dari struktur data dan byte per 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
Hasil tolok ukur (mikro) ini dirangkum dalam tabel berikut.
| Struktur data | Memetakan pesanan | Bytes x gram | µs x kueri - desktop mac | µs x kueri - server 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 |
Untuk struktur data yang menyimpan probabilitas dan backoff, kami dapat menguji kecepatan mencetak file teks dengan menggunakan score program benchmark. Contoh lengkap berikut.
./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
Perintah pertama akan membangun struktur data, yang kedua akan mencetak file teks sample_text yang terkandung dalam test_data . File teks input harus berisi satu kalimat per baris, dengan kata -kata dipisahkan oleh spasi. Selama penilaian file, kami tidak membungkus setiap kalimat dengan spidol <s> dan </s> .
Output examplar bisa (OOV berdiri di luar kosakata ):
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 yang dapat dieksekusi dapat digunakan untuk mengumpulkan statistik yang bermanfaat mengenai penggunaan ruang dari berbagai komponen struktur data (misalnya, gram-id dan sekuens pointer untuk percobaan), serta sifat struktural dari dataset n -gram yang diindeks (misalnya, jumlah jumlah unik, panjang rentang min/maksimal, kemeriahan rata-rata gram, ekc.).
Sebagai contoh, perintah berikut:
./print_stats data_structure.bin
akan menunjukkan statistik untuk struktur data yang diserialisasi ke file data_structure.bin .
Direktori python menyertakan pembungkus ular python sederhana dengan beberapa contoh. Lihat ini!
