หน้าแรก>การเขียนโปรแกรมที่เกี่ยวข้อง>ซอร์สโค้ดอื่น ๆ
ดาวน์โหลด

ออร์คิด-Fst

1. ภาพรวมโครงการ

โปรเจ็กต์นี้ Orchid-Fst ใช้โครงสร้างข้อมูลการค้นหาพจนานุกรมสตริงข้อความแบบรวดเร็ว: Finite state transducer ซึ่งย่อมาจาก FST ในภาษา C++ Orchid-FST ต้องการการสนับสนุน C++ 11 (วิธีที่ดีที่สุดคือคอมไพล์ด้วย GCC 7 หรือสูงกว่า) และปัจจุบันรองรับการคอมไพล์และทำงานบนระบบที่คล้ายกับ UNIX

โครงสร้างข้อมูล Fst ถูกนำมาใช้กันอย่างแพร่หลายในเครื่องมือค้นหาโอเพ่นซอร์ส: Elasticsearch และ Lucene core source การค้นหาสตริงข้อความทำได้รวดเร็วมาก สามารถเข้าใจได้ว่าเป็นแผนผังคีย์-ค่าหรือกำหนดโครงสร้างข้อมูล ความซับซ้อนของเวลาสืบค้นในโครงสร้างข้อมูล FST คือ O(n) โดยที่ n คือความยาวของสตริงข้อความจริงกับการสืบค้น โดยไม่ขึ้นกับขนาดของชุดข้อมูลข้อความขนาดใหญ่ นี่เป็นข้อได้เปรียบที่สำคัญและยิ่งใหญ่มาก

โปรเจ็กต์โอเพ่นซอร์ส FST C++ Orchid-Fst มีข้อดีที่สำคัญดังต่อไปนี้:

  1. กระบวนการสร้าง FST ในโปรเจ็กต์นี้สามารถรับรู้ดัมพ์ไปยังเอาท์พุตสตรีม (เช่น ไฟล์ภายนอก) สำหรับข้อมูล FST ที่เพิ่งสร้างขึ้นในขณะที่สร้าง FST เพื่อลดการใช้หน่วยความจำ จุดนี้มีความสำคัญอย่างยิ่งสำหรับข้อมูลพจนานุกรมที่มีความสม่ำเสมอมาก เนื่องจากไม่สามารถโหลด dict ลงในหน่วยความจำทั้งหมดในครั้งเดียวเพื่อสร้าง FST ไฟล์ข้อมูล FST จะถูกนำมาใช้เป็นแผนที่หน่วยความจำ การใช้งาน FST แบบโอเพ่นซอร์สในปัจจุบันจำนวนมากไม่มีคุณสมบัตินี้ นี่เป็นหนึ่งในไฮไลท์สำคัญของโครงการ

  2. มันใช้งานในภาษา C++ และอาจมีประโยชน์มากหากโปรเจ็กต์ของคุณเป็นเพียงสภาพแวดล้อมการพัฒนา C++ มีการใช้งาน fst open source บางเวอร์ชัน แต่ไม่ค่อยมีการใช้งานอย่างดีในภาษา 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 มีฟังก์ชันต่อไปนี้

    ofst map/set สามารถสร้างไฟล์ fst จากไฟล์พจนานุกรมอินพุตของคุณ ซึ่งได้รับคีย์และค่าจากทุกบรรทัดคั่นด้วยเครื่องหมายจุลภาคเมื่อคำสั่งย่อย map และจะอ่านเฉพาะรายการแรกก่อนเครื่องหมายจุลภาคแรกเป็นคีย์เมื่อตั้งค่าคำสั่งย่อย ofst dot สามารถสร้างไฟล์ 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 ของเครื่องมือบรรทัดคำสั่งของโปรเจ็ก ต์ ด้วยข้อมูลข้อความพจนานุกรมอย่างง่ายที่แสดงด้านบน สามารถแสดงโครงสร้างของอักขระที่เข้ารหัสหลายไบต์ เช่น อักขระจีนได้อย่างชัดเจน สิ่งสำคัญประการหนึ่งที่ควรทราบคือโหนด 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 เป็นตัวอย่างไฟล์การกำหนดค่าสำหรับบันทึกทิวลิป: 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 มันอาศัยไลบรารีของบุคคลที่สามดังต่อไปนี้:

  • 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 executable จะถูกสร้างขึ้นใน < /path/to/install >/bin; และไฟล์ .so ที่เกี่ยวข้องจะอยู่ภายใต้ไดเร็กทอรี lib run command 'ofst --help' หรือ 'lfsort --help' จะทำให้คุณคุ้นเคยกับการใช้งาน

หมายเหตุ: ก่อนที่จะรันเครื่องมือบรรทัดคำสั่ง คุณต้องวางไฟล์การกำหนดค่าบันทึก logger.conf ไว้ในไดเร็กทอรีปัจจุบัน ตัวอย่างของการกำหนดค่านี้อยู่ด้านบน หรือคุณสามารถรับตัวอย่างไฟล์ logger.conf ได้จาก misc/config/logger.conf ของโปรเจ็กต์ นอกจากนี้อย่าลืมสร้างบันทึกที่เส้นทางปัจจุบันของโปรแกรมตามที่กำหนดไว้ใน logger.conf มิฉะนั้นโปรแกรมจะรันข้อผิดพลาดและออก อีกทางหนึ่ง การควบคุมบรรทัดที่สามของ INFO หรือ DEBUG, ERROR หรือ WARN ระดับบันทึก logger.conf จะให้ข้อมูลเอาต์พุตบันทึกสำหรับคำกริยาต่างๆ

โปรดติดต่อ [email protected] สำหรับคำถามที่เกี่ยวข้องและเรื่องอื่นๆ ที่ยังไม่ครอบคลุม สนุกกับมัน

ขยาย
ข้อมูลเพิ่มเติม
แอปที่เกี่ยวข้อง
แนะนำสำหรับคุณ
ข้อมูลที่เกี่ยวข้อง ทั้งหมด