الصفحة الرئيسية>المتعلقة بالبرمجة>كود الذكاء الاصطناعي
تنزيل

Tongrams - طن من n -grams

Tongrams هي مكتبة C ++ لفهرسة والاستعلام عن نماذج لغة كبيرة في مساحة مضغوطة ، كما هو موضح في الأوراق التالية

  • هياكل بيانات فعالة لمجموعات بيانات N-Gram ضخمة [1]
  • التعامل مع مجموعات بيانات n-gram الضخمة بكفاءة [2]

بقلم جوليو إيرمانو بيبيري وروسانو فينتوريني. من فضلك ، استشهد بهذه الأوراق إذا كنت تستخدم Tongrams.

أخبار!

  • مكتبة تقدير نموذج اللغة متاحة هنا.
  • يتوفر تنفيذ الصدأ من قبل Kampersanda هنا.

مقدمة

وبشكل أكثر تحديداً ، يمكن استخدام هياكل البيانات التي تم تنفيذها لرسم خريطة n -grams إلى عدد الترددات المقابلة (عدد صحيح) أو إلى (النقطة العائمة) الاحتمالات والتراجع في نماذج Kneser-kneser-interpolated.

تتميز المكتبة ببنية بيانات Trie مضغوطة يتم فيها تعيين معرفات عدد صحيح ( IDS ) وضغطها مع ELIAS -FANO لدعم عمليات البحث الفعالة داخل مساحة مضغوطة. تسمح إعادة التعيين المستندة إلى السياق لمثل هذه المعرفات بتشفير كلمة تتبع سياق الطول الثابت K ، أي كلمات K السابقة ، مع عدد صحيح يحد قيمته بعدد الكلمات التي تتبع هذا السياق وليس بحجم المفردات بأكملها (عدد الأحاديات). بالإضافة إلى بنية بيانات 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 (انظر ملف 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 Counts تنسيق Google ، أي ملف منفصل واحد لكل قيمة مميزة لـ N (Order) يسرد غرامًا واحدًا لكل صف. نحن نثري هذا التنسيق برأس ملف يشير إلى إجمالي عدد n -grams في الملف (الصفوف): 

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

يجب تسمية هذه الملفات N وفقًا للاتفاقية التالية: <order>-grams ، حيث يكون <order> عنصرًا نائبًا لقيمة n . يمكن ترك الملفات غير مصنفة إذا كان لا بد من بناء النماذج المستندة إلى MPH فقط ، في حين يجب فرزها بترتيب بادئة لهياكل البيانات المستندة إلى Trie ، وفقًا لرسم الخرائط المفردات المختارة ، والتي يجب أن يمثلها ملف Uni-Gram (انظر القسم الفرعي 3.1 من [1]). ينصح بشدة ضغط ملفات الإدخال مع الأدوات المساعدة القياسية ، مثل gzip . يمكن استخدام الأداة المساعدة sort_grams لفرز ملفات N -gram Countts بترتيب بادئة. في الختام ، تم تصميم تعدادات التردد التي تخزنها بهياكل البيانات من دليل يحتوي على الملفات

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

تنسيق كما هو موضح أعلاه.

تتوافق الاحتمالات والاحتفالات والاحتفالات التراجع عن ملفات n -gram ، بدلاً من ذلك ، بتنسيق ملف ARPA. يجب فرز n -grams في ملف ARPA بترتيب لاحقة من أجل إنشاء بنية بيانات TRIE المعكوسة. يمكن استخدام الأداة المساعدة sort_arpa لهذا الغرض.

يحتوي الدليل test_data على:

  • جميع ملفات N -gram Counts (لما مجموعه 252،550 n -grams) ، من أجل N الانتقال من 1 إلى 5 ، مستخرجة من برنامج تحسين دليل Agner Fog في C ++ ، مرتبة بترتيب بادئة وضغطها مع gzip ؛
  • Queries queries.random.5K الذي يضم 5000 N -grams (1000 لكل طلب ومرسم بشكل عشوائي) ؛
  • ملف ARPA arpa الذي يسرد جميع n -grams مرتبة بترتيب اللاحقة فيما يتعلق ببناء محاولات للخلف بكفاءة ؛
  • ملف sample_text Query (6،075 جملة ليصبح المجموع 153،583 كلمة) يستخدم في المعيار الحيوي ؛ يتضمن ملف sample_text.LESSER المصاحب الخاص به فقط الجمل العشرة الأولى.

بالنسبة للأمثلة التالية ، نفترض العمل مع بيانات العينة الواردة في test_data .

بناء هياكل البيانات

يتم استخدام اثنين من التنفيذيين build_trie و build_hash لبناء نماذج لغوية قائمة على trie و (الحد الأدنى المثالي) ، على التوالي. قم بتشغيل المنافسين دون أي حجج لمعرفة استخدامها.

نعرض الآن بعض الأمثلة.

مثال 1

الأمر 

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

يبني Elias-Fano Trie

  • من الطلب 5 ؛
  • التي تخزن التكرار.
  • من ملفات N -gram Counts الموجودة في الدليل test_data ؛
  • مع عدم وجود إعادة تنظيم قائمة على السياق (افتراضي) ؛
  • يتم تشفير صفوفهم من خلال تقنية Codwords (IC) المفهرسة (الافتراضي) ؛
  • تم تسلسله إلى الملف الثنائي ef_trie.count.bin .
مثال 2

الأمر 

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

يبني مقسمة إلياس فانو تري

  • من الطلب 5 ؛
  • التي تخزن التكرار.
  • من ملفات N -gram Counts الموجودة في الدليل 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 ؛
  • التي تخزن الاحتمالات والتراجع ؛
  • مع إعادة تنظيم السياق للطلب 2 ؛
  • مع <unk> احتمال -20.0 واستخدام 8 بتات لتحديد الاحتمالات ( --p ) والتراجع ( --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 Counts الموجودة في الدليل 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 ، مزود بمعالج Intel Core I5 ​​2.3 جيجا هرتز (يشار إليه باسم MAC على سطح المكتب ). تم تجميع الكود باستخدام Apple LLVM الإصدار 10.0.0 clang مع جميع التحسينات (انظر القسم بناء الكود). بالإضافة إلى ذلك ، نكرر بعض التجارب مع CORE (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-RTRE مع الترتيب 2 (نستخدم نفس الأسماء لهياكل البيانات كما هو موضح في [1]). يتم تكرار كل تجربة 1000 مرة على 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 استعلام - سطح المكتب 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

للحصول على بنية البيانات تخزين الاحتمالات والتراجع ، يمكننا بدلاً من ذلك اختبار سرعة تسجيل ملف نصي باستخدام 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 القابلة للتنفيذ لجمع إحصائيات مفيدة فيما يتعلق باستخدام المساحة لمكونات بنية البيانات المختلفة (على سبيل المثال ، معرم الجرام ومتواليات المؤشر للمحاولات) ، وكذلك الخصائص الهيكلية لمجموعة بيانات GRAM المفهرسة (على سبيل المثال ، عدد التهم الفريدة ، أطوال النطاق MIN/MAX ، متوسط ​​فجوة GRAM-ID ، ECC.).

على سبيل المثال ، الأمر التالي: 

 ./print_stats data_structure.bin

سيعرض إحصائيات بنية البيانات المسلسل إلى ملف data_structure.bin .

غلاف بيثون

يتضمن python الدليل غلاف Python بسيط مع بعض الأمثلة. تحقق من هذا!

المؤلفون

فهرس

  • [1] Giulio Ermanno Pibiri و Rossano Venturini هياكل بيانات فعالة لمجموعات بيانات N-Gram ضخمة . في وقائع مؤتمر 40-TH ACM للبحث والتطوير في استرجاع المعلومات (Sigir 2017): 615-624.
  • [2] جوليو إيرمانو بيبيري وروسانو فينتوريني. التعامل مع مجموعات بيانات n-gram الضخمة بكفاءة. معاملات ACM على أنظمة المعلومات (TOIS) 37.2 (2019): 1-41.
يوسع
معلومات إضافية
تطبيقات ذات صلة
نوصي لك
أخبار ذات صلة الكل