الصفحة الرئيسية>المتعلقة بالبرمجة>شفرة المصدر الأخرى
تنزيل

الأوركيد-فست

1. نظرة عامة على المشروع

ينفذ هذا المشروع Orchid-Fst بنية بيانات بحث سريعة في قاموس سلسلة نصية: محول الحالة المحدودة، وهو اختصار لـ FST في لغة C++. يتطلب Orchid-FST دعم C++ 11 (من الأفضل التحويل البرمجي باستخدام الإصدار 7 من مجلس التعاون الخليجي أو أعلى) ويدعم حاليًا التجميع والتشغيل على أنظمة تشبه UNIX.

تم استخدام بنية بيانات Fst على نطاق واسع في محرك البحث مفتوح المصدر: Elasticsearch ومصدر Lucene الأساسي. إنه سريع جدًا للبحث عن سلسلة نصية، ويمكن فهمه على أنه خريطة قيمة مفتاح أو بنية بيانات محددة. التعقيد الزمني للاستعلام في بنية بيانات FST هو O(n)، حيث n هو طول السلسلة النصية الفعلية مع الاستعلام، بغض النظر عن حجم مجموعة البيانات النصية الضخمة. وهذه ميزة مهمة وضخمة للغاية.

يتمتع مشروع Orchid-Fst مفتوح المصدر FST C++ بالمزايا المهمة التالية:

  1. يمكن لعملية إنشاء FST في هذا المشروع تحقيق التفريغ إلى دفق الإخراج (مثل الملف الخارجي) لبيانات FST التي تم إنشاؤها للتو أثناء إنشاء FST لتقليل إشغال الذاكرة. هذه النقطة مهمة بشكل خاص لبيانات القاموس ذات الانتظام الكبير. لأنه لا يمكن تحميل الإملاء في الذاكرة دفعة واحدة لإنشاء FST. يتم بعد ذلك استخدام ملف بيانات FST كخريطة ذاكرة. العديد من تطبيقات FST الحالية مفتوحة المصدر لا تحتوي على هذه الميزة. وهذا من أهم النقاط المهمة في المشروع.

  2. يتم تنفيذه بلغة C++ وقد يكون مفيدًا جدًا إذا كان مشروعك مجرد بيئة تطوير C++. هناك بعض إصدارات تطبيقات fst مفتوحة المصدر، ولكن نادرًا ما يتم تنفيذها بشكل جيد في لغة C/C++ كرمز عالي الجودة، لذلك يمكنك دمجها بسهولة في مشاريع تطوير C++ الخاصة بك. كما نعلم فقد تم تنفيذه في Rust وJava.

  3. لقد نجح في حل سلسلة نصية ذات كود UTF8، وحل المزيد من الأخطاء الخطيرة عندما لا تكون السلسلة النصية عبارة عن أحرف إنجليزية، مثل الأحرف الصينية وما إلى ذلك. لقد استخدم أسلوبًا أكثر ذكاءً لحل سلسلة نص ترميز UTF8.

  4. يقدم هذا المشروع عددًا كبيرًا من أمثلة تطبيقات التشغيل الآلي، والتي يمكنك من خلالها معرفة المزيد حول تطبيقات التشغيل الآلي للعديد من الأغراض المختلفة، سواء تم تنفيذها على هياكل بيانات FST أو تم استخدامها في سيناريوهات أخرى. تتضمن العديد من هياكل بيانات الأوتوماتا في هذا المشروع التجريبي، على سبيل المثال لا الحصر، ما يلي: GreaterThan,LessThan,Prefix,Str,StartsWith,Intersection,Union,Not,Levenshtein Automaton, Damerau Levenshtein Automation وما إلى ذلك.

  5. فهو لا يطبق واجهة تعليمات برمجية فحسب، بل ينفذ أيضًا بعناية أداة سطر أوامر سهلة الاستخدام، وهي orchid-fst: ofst ، مع تعليمات مفصلة حول كيفية استخدام المعلمات. تحتوي أداة سطر الأوامر الأولى على الوظائف التالية.

    يمكن لمجموعة/خريطة ofst إنشاء ملف fst من ملف قاموس الإدخال الخاص بك، والذي حصل على المفتاح والقيمة من كل سطر مفصول بفاصلة عند تعيين الأمر الفرعي، ويقرأ فقط العنصر الأول قبل الفاصلة الأولى كمفتاح عند تعيين الأمر الفرعي؛ يمكن لـ ofst dot إنشاء ملف نقطي من ملف fst، والذي يمكن إنشاء ملف صورة، مثل ملف png لرؤية بنية fst بواسطة أمر dot، مثل:

    'dot -Tpng < xx.dot > xx.png' .

    نقطة أخرى مهمة هي: يمكنك رؤية التفاصيل في FST لكل حرف صيني! هذا مبهج.

    تنفذ الأوامر الفرعية match/prefix/range/fuzzy بحثًا مختلفًا في fst. يمكنك الحصول على مزيد من التفاصيل حول تعليمات الاستخدام باستخدام "ofst --help" أو "ofst Map --help" أو "ofst fuzzy --help"، يمكنك تجربتها! 

     ,10000
中国,100
中国人,50
中国人民,40
中国心,10
北七,3
北七家,10
北京,5
北平,2

    تُظهر الصورة أعلاه تأثيرًا بسيطًا لصورة PNG تم إنشاؤه بواسطة الأمر الفرعي ofst dot لأداة سطر أوامر المشروع ofst باستخدام بيانات نص القاموس البسيط الموضحة أعلاه. يمكنه عرض بنية الأحرف المشفرة متعددة البايت مثل الأحرف الصينية بوضوح. أحد الأشياء المهمة التي يجب ملاحظتها هو أن العقدة 17 في الشكل تمثل أول بايت مشترك لكل من '京' و'七'. يعد هذا أحد الأخطاء الشائعة في العديد من تطبيقات FST الأخرى مفتوحة المصدر، وهذا المشروع يعالج المشكلة بشكل مثالي.

  6. يطبق مشروع fst هذا LRUcache وLFUcache، اللذين يستخدمان في إنشاء بنية بيانات fst. من أجل منع الاستخدام المفرط للذاكرة، يلعب lruCache دورًا جيدًا في عملية بناء FST.

    يمكن لـ LruCache إنشاء الحد الأدنى التقريبي لشجرة FST، لتحقيق الحد الأدنى التقريبي لتأثير المساحة. إذا كانت مساحة الذاكرة كافية، فمن المستحسن تعيين سعة ذاكرة التخزين المؤقت المتاحة لـ lruCache على أكبر حجم ممكن عند إنشاء FST. بهذه الطريقة، يتم بناء FST صغيرًا قدر الإمكان لأنه يتم توفير المساحة قدر الإمكان.

  7. مع الأخذ في الاعتبار أن بناء ملف القاموس لـ FST يتطلب دائمًا أن يتم ترتيب الإدخال معجميًا، فإن هذا المشروع يطبق وحدة جيدة لوظيفة الفرز الخارجي للملفات الكبيرة، كما ينفذ أيضًا أداة سطر أوامر سهلة الاستخدام، lfsort، لفرز الملفات الكبيرة. ملف نصي بشكل منفصل. بالطبع، تحتوي أداة سطر الأوامر FST بالفعل على ميزة فرز الملفات الكبيرة المدمجة فيها، وتقوم افتراضيًا بإدخال ملفات نصية كبيرة لم يتم فرزها. كما أن فرز الملفات الكبيرة يستغرق وقتًا طويلاً. إذا كانت ملفات قاموس الإدخال الخاصة بك مرتبة بالفعل، فيمكنك عرض الوسائط المحددة '-s' أو '--sorted' لتجنب فرز الملفات الكبيرة قبل إنشاء FST. يمكنك إدخال "lfsort --help" للاطلاع على الإرشادات التفصيلية لأداة سطر أوامر فرز الملفات الكبيرة lfsort. 

 ofst: Orchid-Fst is a smart Fst command line tool

Usage: ofst [OPTIONS] SUBCOMMAND

Options:
  -h,--help          Print this help message and exit

Subcommands:
  map                construct fst data file from a key-value(separated with comma 
                     every line) dictionary file.
                     
  set                construct fst data file from a only key(no value) dictionary 
                     file.
                     
  dot                generate dot file from fst data file, which can be converted 
                     to png file using dot command like: dot -Tpng < a.dot > a.png,
                     then you can view the picture generated.
                     
  match              execute accurate match query for a term text in the fst.
                     
  prefix             execute prefix query starts with a term text in the fst.
                     
  range              execute range query in the fst.
                     
  fuzzy              execute fuzzy query in the fst,it works by building a Levenshtein 
                     or Damerau-Levenshtein automaton within a edit distance.
                                   
Please contact [email protected] for related questions and other matters not covered. Enjoy it!


 lfsort: A smart large file sort command line tool
Usage: lfsort [OPTIONS]

Options:
  -h,--help                             Print this help message and exit
  -f,--input-file TEXT:FILE REQUIRED    input file which is often a huge large file to sort
  -o,--output-file TEXT:PATH(non-existing) REQUIRED
                                        output file which store result sorted from input file
  -w,--work-directory TEXT:DIR=/tmp     work directory specified for total processing,default /tmp if not set
  -t,--thread-count UINT:INT in [1 - 32]=4
                                        threads count used for sort large file,default 4 if not set
  -s,--split-file-count UINT:INT in [1 - 1000]=6
                                        count number of large file split,default 8 if not set
  -p,--parallel-task-count UINT:INT in [2 - 20]=3
                                        paralleled running task count for merge sorted intermediate files, default 3 if not set
  -i,--ignore-empty-line                whether ignore all empty lines to result file,default false if not set

Please contact [email protected] for related questions and other matters not covered. Enjoy it!

حول استخدام هذا المشروع لتسجيل الدخول لطباعة مكون التوليب - يمكن العثور على السجل في إصدار المؤلف مفتوح المصدر لمشروع آخر: https://github.com/apollo008/tulip-log. إحدى المبادئ الأساسية لاستخدام أدوات سطر أوامر المشروع، ofst و lfsort ، هي الحاجة إلى تكوين ملف تعريف لسجل tuliop في الدليل الحالي. يطلق عليه عادةً اسم logger.conf. يشتمل هذا المشروع أيضًا على الاستخدام الغني لـ C++ لوحدة اختبار وحدة CppUnit لضمان جودة وظيفة التعليمات البرمجية. يعد Misc/config/logger.conf مثالاً لملف التكوين لـ Tulip Log: logger.conf.

إن تفاصيل عملية تنفيذ Levenshtein automata و Damerau Levenshtein automata معقدة للغاية في الواقع، وليس هذا الموضوع هو محور هذا المشروع، على الرغم من أن الكود المصدري لهذا المشروع يحتوي بالكامل على التنفيذ الذكي والفعال للاستعلام الغامض Levenshtein و Dameau Levenshtein. أعتقد أنه سيكون من المفيد لك أن تفهم خوارزمية الاستعلام الغامضة لقياس مسافة التعديل الخاص بـ Levenshtein وDamerau Leveshtein. فيما يتعلق بموضوع استخدام Levenshtein أو Damerau Levenshtein automata للاستعلام السريع عن سلاسل مماثلة في محركات البحث، يمكن للقراء المهتمين قراءة مقال آخر للمؤلف:<搜索引擎中相似字符串查找那些事儿> https://mp.weixin.qq.com/s/0ODgrWSVdRnYZxGRGmEdsA.

أخيرًا، تعتبر كفاءة الخوارزمية لهذا التنفيذ فعالة جدًا من الناحية النظرية، بما في ذلك عملية بناء FST والاستعلام عن FST. سيتم إضافة المزيد من بيانات اختبار الأداء التفصيلية في الإصدارات التالية.

2. تجميع المشروع وتثبيته

يدعم هذا المشروع Orchid-Fst حاليًا التجميع والتثبيت في بيئة تشبه UNIX. ويعتمد على مكتبات الطرف الثالث التالية:

  • com.cppunit
  • سجل الخزامى

قبل تجميع مشروع Orchid-Fst وتثبيته، يجب عليك أولاً تثبيت المكتبتين التابعتين أعلاه، مكتبة سجل البحث الذاتي Tulip-Log، ومكتبة اختبار الوحدة الواحدة CppUnit، الموجودة في دليل المشاركة ويمكن تجميعها مسبقًا.

ملاحظة: في Ubuntu Linux، قد يتعين عليك تثبيت zlib عن طريق الأمر: 'sudo apt install zlib1g-dev' قبل تثبيت هذا المشروع. في كل من Ubuntu وCentos Linux، من الأفضل استخدام إصدار gcc7/g++7 أو أعلى. 

 git clone https://github.com/apollo008/orchid-fst.git orchid-fst.git
cd orchid-fst.git
vim src/CMakeLists.txt
#change line 11 from 'set(${TOP_PROJECT_NAME_UPPER}_DEPEND_PREFIX_DIR $ENV{HOME}/local)   #need set' to 'set(${TOP_PROJECT_NAME_UPPER}_DEPEND_PREFIX_DIR /home/xx/local)   #need set'

make build-dir
cd build-dir
cmake -DENABLE_BUILD_SHARE=ON ../src      #firstly compile share,denpdenc libs:cppunit and tulip
rm -rf *    #clear build-dir，then begin to compile orchid-fst project
cmake -DCMAKE_INSTALL_PREFIX=/path/to/install  ../src
make -j4
make install
make test    #run unittest



 xxxxxx@cent7ay:~/work/projects/orchid-fst.git/build-dir$ make test
Running tests...
Test project ~/work/projects/orchid-fst.git/build-dir
    Start 1: common_util_unittest
1/4 Test #1: common_util_unittest .............   Passed    0.01 sec
    Start 2: cache_unittest
2/4 Test #2: cache_unittest ...................   Passed  280.42 sec
    Start 3: fst_unittest
3/4 Test #3: fst_unittest .....................   Passed   21.83 sec
    Start 4: large_file_sorter_unittest
4/4 Test #4: large_file_sorter_unittest .......   Passed    0.01 sec

100% tests passed, 0 tests failed out of 4

Total Test time (real) = 302.27 sec

سيتم الآن إنشاء الملفين القابلين للتنفيذ lfsort وofst في < /path/to/install >/bin; وسيكون الملف .so المقابل ضمن دليل lib. تشغيل الأمر "ofst --help" أو "lfsort --help" سيجعلك على دراية باستخدامهما.

ملاحظة: قبل تشغيل أداة سطر الأوامر، تحتاج إلى وضع ملف تكوين سجل logger.conf في الدليل الحالي. يوجد مثال على هذا التكوين أعلاه أو يمكنك الحصول على مثال لملف logger.conf من misc/config/logger.conf الخاص بالمشروع. ولا تنس أيضًا إنشاء سجلات في المسار الحالي للبرنامج كما تم تكوينه في logger.conf. وإلا، فسيقوم البرنامج بتشغيل خطأ والخروج. وبدلاً من ذلك، فإن التحكم في السطر الثالث من INFO أو DEBUG أو ERROR أو WARN لمستوى السجل logger.conf سيمنحك معلومات مخرجات السجل لمختلف الأفعال.

يرجى الاتصال بـ [email protected] للأسئلة ذات الصلة والمسائل الأخرى التي لم تتم تغطيتها. استمتع بها.

يوسع
معلومات إضافية
تطبيقات ذات صلة
نوصي لك
أخبار ذات صلة الكل