tongrams

Tongrams - ตันของ n -grams

Tongrams เป็นไลบรารี C ++ ในการจัดทำดัชนีและสอบถามโมเดลภาษาขนาดใหญ่ในพื้นที่บีบอัดตามที่อธิบายไว้ในเอกสารต่อไปนี้

• โครงสร้างข้อมูลที่มีประสิทธิภาพสำหรับชุดข้อมูล N-Gram ขนาดใหญ่ [1]
• การจัดการชุดข้อมูล N-Gram ขนาดใหญ่อย่างมีประสิทธิภาพ [2]

โดย Giulio Ermanno Pibiri และ Rossano Venturini กรุณาอ้างอิงเอกสารเหล่านี้หากคุณใช้ Tongrams

ข่าว!

• ห้องสมุด การประมาณรูปแบบภาษา มีอยู่ที่นี่
• การดำเนินการตามสนิม โดย Kampersanda มีให้ที่นี่

การแนะนำ

โดยเฉพาะอย่างยิ่งโครงสร้างข้อมูลที่นำไปใช้สามารถใช้ในการแมป N -grams กับความถี่ (จำนวนเต็ม) ที่สอดคล้องกันหรือความน่าจะเป็น (จุดลอยตัว) และ backoffs สำหรับโมเดล Kneser-Ney-Interporated

ห้องสมุดมีโครงสร้างข้อมูล Trie ที่บีบอัดซึ่ง N -Grams ได้รับการกำหนดตัวระบุจำนวนเต็ม (ID) และบีบอัดด้วย Elias -Fano เพื่อรองรับการค้นหาที่มีประสิทธิภาพภายในพื้นที่บีบอัด การแมปตามบริบท ของตัวระบุดังกล่าวอนุญาตให้เข้ารหัสคำตามบริบทของความยาวคงที่ K , IE, คำ k ก่อนหน้านี้โดยมีจำนวนเต็มซึ่งค่าถูก จำกัด ด้วยจำนวนคำที่ตามบริบทดังกล่าวและ ไม่ใช่ ขนาดของคำศัพท์ทั้งหมด (จำนวนของ Uni-grams) นอกจากนี้ยังมีโครงสร้างข้อมูล Trie ไลบรารีอนุญาตให้สร้างโมเดลตาม การแฮชที่สมบูรณ์แบบน้อยที่สุด (MPH) สำหรับการดึงเวลาคงที่

เมื่อใช้ในการจัดเก็บจำนวนความถี่โครงสร้างข้อมูลสนับสนุนการดำเนินการ lookup() ที่ส่งคืนจำนวนการเกิดขึ้นของ N -Gram ที่ระบุ แตกต่างกันเมื่อใช้ในการจัดเก็บความน่าจะเป็นและ backoffs โครงสร้างข้อมูลจะใช้ฟังก์ชัน score() ที่ให้ข้อความเป็นอินพุตคำนวณคะแนนความงุนงงของข้อความ

คู่มือนี้มีไว้เพื่อให้ภาพรวมโดยย่อของห้องสมุดและเพื่อแสดงให้เห็นถึงฟังก์ชันการทำงานผ่านตัวอย่างบางส่วน

สารบัญ

• การสร้างรหัส
• รูปแบบข้อมูลอินพุต
• การสร้างโครงสร้างข้อมูล
• การทดสอบ
• เกณฑ์มาตรฐาน
• สถิติ
• เสื้อคลุม Python
• ผู้เขียน
• บรรณานุกรม

การสร้างรหัส

รหัสได้รับการทดสอบบน 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 (ดูไฟล์ 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 (คำสั่งซื้อ) ที่แสดงรายการหนึ่งกรัมต่อแถว เราเพิ่มรูปแบบนี้ด้วยส่วนหัวไฟล์ที่ระบุจำนวนรวมของ n -grams ในไฟล์ (แถว):

 <total_number_of_rows>
<gram1> <TAB> <count1>
<gram2> <TAB> <count2>
<gram3> <TAB> <count3>
...

ไฟล์ n ดังกล่าวจะต้องตั้งชื่อตามอนุสัญญาต่อไปนี้: <order>-grams โดยที่ <order> เป็นตัวยึดตำแหน่งสำหรับค่า n ไฟล์สามารถถูกทิ้งไว้ได้หากต้องสร้างแบบจำลอง MPH ที่ใช้ MPH เท่านั้นในขณะที่สิ่งเหล่านี้จะต้องเรียงลำดับตาม คำสั่งนำหน้า สำหรับโครงสร้างข้อมูลที่ใช้ Trie ตามการแมปคำศัพท์ที่เลือก ซึ่งควรแสดงโดยไฟล์ Uni-Gram (ดูส่วนย่อย 3.1 ของ [1]) ขอแนะนำให้ทำการบีบอัดไฟล์อินพุตด้วยยูทิลิตี้มาตรฐานเช่น gzip ยูทิลิตี้ sort_grams สามารถใช้ในการเรียงลำดับไฟล์ n -gram นับในลำดับคำนำหน้า โดยสรุปโครงสร้างข้อมูลที่เก็บจำนวนความถี่ถูกสร้างขึ้นจากไดเรกทอรีที่มีไฟล์

• 1-grams.sorted.gz
• 2-grams.sorted.gz
• 3-grams.sorted.gz
• -

จัดรูปแบบตามที่อธิบายไว้ข้างต้น

ไฟล์ที่แสดงรายการ N -GRAM ความน่าจะเป็นและ backoffs นั้นสอดคล้องกับรูปแบบไฟล์ ARPA แทน n -grams ในไฟล์ ARPA จะต้องเรียงลำดับตาม ลำดับคำต่อท้าย เพื่อสร้างโครงสร้างข้อมูล Trie ที่กลับด้าน ยูทิลิตี้ sort_arpa สามารถใช้เพื่อจุดประสงค์นั้น

ไดเรกทอรี test_data มี:

• ไฟล์ n -gram ทั้งหมด (รวมทั้งหมด 252,550 n -grams) สำหรับ n จาก 1 ถึง 5, สกัดจาก ซอฟต์แวร์การเพิ่มประสิทธิภาพด้วยตนเองของ Agner Fog ใน C ++ เรียงลำดับตามลำดับคำนำหน้าและบีบอัดด้วย gzip ;
• queries.random.5K ประกอบด้วย 5,000 N -grams (1,000 สำหรับแต่ละคำสั่งซื้อและสุ่ม);
• ไฟล์ ARPA arpa ซึ่งแสดงรายการ n -grams ทั้งหมดที่เรียงลำดับในคำสั่งต่อท้ายเพื่อสร้างการพยายามย้อนกลับอย่างมีประสิทธิภาพ
• ไฟล์ Query sample_text (6,075 ประโยครวมทั้งหมด 153,583 คำ) ที่ใช้สำหรับเกณฑ์มาตรฐานที่น่าพิศวง ไฟล์ sample_text.LESSER ของ Companion ของมันมีเพียง 10 ประโยคแรก

สำหรับตัวอย่างต่อไปนี้เราคิดว่าจะทำงานกับข้อมูลตัวอย่างที่มีอยู่ใน test_data

การสร้างโครงสร้างข้อมูล

ทั้งสอง executables build_trie และ build_hash ใช้เพื่อสร้างแบบจำลองภาษาที่ใช้ทรีและ (สมบูรณ์แบบที่สุด) ตามลำดับ เรียกใช้หน้าที่โดยไม่มีข้อโต้แย้งใด ๆ ที่จะรู้เกี่ยวกับการใช้งานของพวกเขา

ตอนนี้เราแสดงตัวอย่าง

ตัวอย่างที่ 1

คำสั่ง

 ./build_trie ef_trie 5 count --dir ../test_data --out ef_trie.count.bin

สร้าง Elias-Fano Trie

• ของคำสั่ง 5;
• ที่เก็บความถี่นับ;
• จากไฟล์จำนวน n -gram ที่มีอยู่ในไดเรกทอรี test_data ;
• โดยไม่มีการรีมอนแบบอิงตามบริบท (ค่าเริ่มต้น);
• ซึ่งมีการเข้ารหัสอันดับของการนับด้วยเทคนิค codewords (IC) ที่จัดทำดัชนี (ค่าเริ่มต้น);
• นั่นคืออนุกรมกับไฟล์ไบนารี ef_trie.count.bin

ตัวอย่างที่ 2

คำสั่ง

 ./build_trie pef_trie 5 count --dir ../test_data --remapping 1 --ranks PSEF  --out pef_trie.count.out

สร้าง Elias-Fano Trie ที่แบ่งพาร์ติชัน

• ของคำสั่ง 5;
• ที่เก็บความถี่นับ;
• จากไฟล์จำนวน n -gram ที่มีอยู่ในไดเรกทอรี test_data ;
• ด้วยการรีการรีดแบบอิงบริบทของคำสั่ง 1;
• ซึ่งมีการนับจำนวนที่ถูกเข้ารหัสด้วยคำนำหน้ารวม (PS) + ELIAS-FANO (EF);
• นั่นคืออนุกรมกับไฟล์ไบนารี pef_trie.count.out

ตัวอย่างที่ 3

คำสั่ง

 ./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

• ของคำสั่ง 5;
• ที่เก็บความน่าจะเป็นและ backoffs;
• ด้วยการรีการรีมาแอปตามบริบทของคำสั่ง 2;
• ด้วย <unk> ความน่าจะเป็นที่ -20.0 และการใช้ 8 บิตสำหรับความน่าจะเป็นเชิงปริมาณ ( --p ) และ backoffs ( --b );
• จากไฟล์ ARPA ชื่อ arpa ;
• นั่นคืออนุกรมกับไฟล์ไบนารี ef_trie.prob_backoff.bin

ตัวอย่างที่ 4

คำสั่ง

 ./build_hash 5 8 count --dir ../test_data --out hash.bin

สร้างโมเดลที่ใช้ MPH

• ของคำสั่ง 5;
• ที่ใช้ 8 ไบต์ต่อแฮชคีย์;
• ที่เก็บความถี่นับ;
• จากไฟล์จำนวน n -gram ที่มีอยู่ในไดเรกทอรี test_data ;
• นั่นคืออนุกรมกับไฟล์ไบนารี hash.bin

การทดสอบ

ไดเรกทอรี test ประกอบด้วยการทดสอบหน่วยของหน่วยการสร้างพื้นฐานบางส่วนที่ใช้โดยโครงสร้างข้อมูลที่นำไปใช้ ตามปกติการเรียกใช้ Executables โดยไม่มีข้อโต้แย้งใด ๆ จะแสดงรายการพารามิเตอร์อินพุตที่คาดหวัง ตัวอย่าง:

 ./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 ซึ่งติดตั้งโปรเซสเซอร์ Intel Core i5 2.3 GHz (เรียกว่า Desktop Mac ) รหัสถูกรวบรวมด้วยแอปเปิ้ล LLVM เวอร์ชัน 10.0.0 clang พร้อม การปรับให้เหมาะสมทั้งหมด (ดูส่วนการสร้างรหัส) นอกจากนี้เรายังทำซ้ำการทดลองบางอย่างด้วย Intel (R) Core (TM) I9-9900K CPU @ 3.60 GHz ภายใต้ Ubuntu 19.04, 64 บิต (เรียกว่า เซิร์ฟเวอร์ Linux ) ในกรณีนี้รหัสถูกรวบรวมด้วย gcc 8.3.0

สำหรับโครงสร้างข้อมูลที่จัดเก็บจำนวนความถี่เราสามารถทดสอบความเร็วของการค้นหาการค้นหาโดยใช้โปรแกรมเบนช์มาร์ก lookup_perf_test ในตัวอย่างต่อไปนี้เราจะแสดงวิธีการสร้างและเปรียบเทียบโครงสร้างข้อมูลที่แตกต่างกันสามโครงสร้าง: EF-TRIE ที่ไม่มีการรีมอน EF-RTRIE พร้อมคำสั่งซื้อใหม่ 1 และ PEF-RTRIE พร้อมคำสั่งซื้อใหม่ 2 (เราใช้ชื่อเดียวกันสำหรับโครงสร้างข้อมูลตามที่แสดงใน [1]) การทดลองแต่ละครั้งจะทำซ้ำ 1,000 ครั้งผ่านแบบสอบถามไฟล์สอบถามข้อมูลการทดสอบ 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 Query - Desktop Mac	µs X Query - 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

สำหรับโครงสร้างข้อมูลที่จัดเก็บความน่าจะเป็นและ backoffs เราสามารถทดสอบความเร็วในการให้คะแนนไฟล์ข้อความโดยใช้ 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

คำสั่งแรกจะสร้างโครงสร้างข้อมูลอันที่สองจะให้คะแนนไฟล์ข้อความ sample_text ที่มีอยู่ใน test_data ไฟล์ข้อความอินพุตจะต้องมีหนึ่งประโยคต่อบรรทัดโดยมีคำคั่นด้วยช่องว่าง ในระหว่างการให้คะแนนของไฟล์เราไม่ได้ห่อแต่ละประโยคด้วยเครื่องหมาย <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 ที่ปฏิบัติการได้สามารถใช้เพื่อรวบรวมสถิติที่มีประโยชน์เกี่ยวกับการใช้พื้นที่ของส่วนประกอบโครงสร้างข้อมูลต่าง ๆ (เช่นลำดับแกรม-ไอดีและตัวชี้สำหรับการพยายาม) เช่นเดียวกับคุณสมบัติเชิงโครงสร้างของชุดข้อมูล N -Gram ที่จัดทำดัชนี (เช่นจำนวนที่ไม่ซ้ำกัน

เป็นตัวอย่างคำสั่งต่อไปนี้:

 ./print_stats data_structure.bin

จะแสดงสถิติสำหรับโครงสร้างข้อมูลที่เป็นอนุกรมไปยังไฟล์ data_structure.bin

เสื้อคลุม Python

python ไดเรกทอรีมีเสื้อคลุมงูหลามอย่างง่ายพร้อมตัวอย่างบางส่วน ลองดูสิ!

ผู้เขียน

• giulio ermanno pibiri, [email protected]
• Rossano Venturini, [email protected]

บรรณานุกรม

• [1] Giulio Ermanno Pibiri และ Rossano Venturini โครงสร้างข้อมูลที่มีประสิทธิภาพสำหรับชุดข้อมูล N-Gram ขนาดใหญ่ ในการดำเนินการของการประชุม ACM 40 ถึงการวิจัยและพัฒนาในการดึงข้อมูล (Sigir 2017): 615-624
• [2] Giulio Ermanno Pibiri และ Rossano Venturini การจัดการชุดข้อมูล N-Gram ขนาดใหญ่อย่างมีประสิทธิภาพ การทำธุรกรรม ACM ในระบบข้อมูล (TOIs) 37.2 (2019): 1-41