orchid fst
To make ofst command line tool can print more petty help messages.
Proyek Orchid-Fst ini mengimplementasikan struktur data pencarian kamus string teks cepat: Finite state transducer , yang merupakan kependekan dari FST dalam bahasa C++. Orchid-FST memerlukan dukungan C++11 (Yang terbaik adalah mengkompilasi dengan GCC 7 atau lebih tinggi) dan saat ini mendukung kompilasi dan berjalan pada sistem mirip UNIX.
Struktur data pertama telah banyak digunakan di mesin pencari sumber terbuka: Elasticsearch dan sumber inti Lucene. Ini sangat cepat untuk mencari string teks, dapat dipahami sebagai peta nilai kunci atau struktur data kumpulan. Kompleksitas waktu kueri pada struktur data FST adalah O(n), dengan n adalah panjang string teks aktual dengan kueri, tidak bergantung pada ukuran kumpulan data teks yang sangat besar. Ini adalah keuntungan yang sangat penting dan besar.
Proyek sumber terbuka FST C++ Orchid-Fst ini memiliki keuntungan signifikan sebagai berikut:
Proses konstruksi FST dalam proyek ini dapat mewujudkan aliran dump ke output (seperti file eksternal) untuk data FST yang baru saja dibuat sambil membangun FST untuk mengurangi penggunaan memori. Poin ini sangat penting untuk data kamus dengan keteraturan yang besar. Karena dict tidak dapat dimuat ke dalam memori sekaligus untuk membangun FST. File data FST kemudian digunakan sebagai peta memori. Banyak implementasi FST open source saat ini tidak memiliki fitur ini. Ini adalah salah satu hal penting dari proyek ini.
Ini diimplementasikan dalam bahasa C++ dan mungkin sangat berguna jika proyek Anda hanyalah lingkungan pengembangan C++. Ada beberapa versi implementasi open source pertama, tetapi jarang diimplementasikan dengan baik dalam bahasa C/C++ sebagai kode berkualitas tinggi, sehingga Anda dapat dengan mudah mengintegrasikannya ke dalam proyek pengembangan C++ Anda. Seperti yang kita ketahui, ini telah diterapkan di Rust dan Java.
Ini telah berhasil menyelesaikan string teks kode UTF8, dan menyelesaikan lebih banyak bug server ketika string teks bukan karakter bahasa Inggris, seperti karakter Cina dan sebagainya. Ini menggunakan pendekatan yang jauh lebih cerdas untuk menyelesaikan string teks pengkodean UTF8.
Proyek ini menyajikan sejumlah besar contoh implementasi automata, yang darinya Anda dapat mempelajari lebih lanjut tentang implementasi automata untuk berbagai tujuan, baik dilakukan pada struktur data FST atau digunakan dalam skenario lain. Banyak struktur data automata dalam Demo proyek ini termasuk, namun tidak terbatas pada: GreaterThan, LessThan, Prefix, Str, StartsWith, Intersection, Union, Not, Levenshtein Automaton, Damerau Levenshtein Automation dan seterusnya.
Tidak hanya mengimplementasikan antarmuka kode, namun juga secara hati-hati mengimplementasikan alat baris perintah yang mudah digunakan, yaitu anggrek-fst: ofst , dengan petunjuk rinci tentang cara menggunakan parameter. Alat baris perintah pertama memiliki fungsi berikut ini.
ofst map/set dapat membuat file fst dari file kamus masukan Anda, yang memperoleh kunci dan nilai dari setiap baris yang dipisahkan dengan koma saat sub-perintah map, dan hanya membaca item pertama sebelum koma pertama sebagai kunci saat menyetel sub-perintah; ofst dot dapat menghasilkan file dot dari file fst, yang dapat menghasilkan file gambar, seperti file png untuk melihat struktur fst dengan perintah dot, seperti:
'titik -Tpng < xx.dot > xx.png' .
Poin penting lainnya adalah: Anda dapat melihat detail di fst untuk setiap karakter Cina! Ini menggembirakan.
sub-perintah match/prefix/range/fuzzy menjalankan pencarian berbeda di fst. Anda dapat memperoleh petunjuk penggunaan lebih detail dengan menggunakan 'ofst --help' atau 'ofst map --help' atau 'ofst fuzzy --help', Anda dapat mencobanya!
,10000
中国,100
中国人,50
中国人民,40
中国心,10
北七,3
北七家,10
北京,5
北平,2
Gambar di atas menunjukkan efek gambar PNG sederhana yang dihasilkan oleh subperintah titik pertama dari alat baris perintah proyek dengan data teks kamus sederhana yang ditunjukkan di atas. Ini dapat dengan jelas menampilkan struktur karakter yang disandikan multi-byte seperti karakter Cina. Satu hal penting untuk dicatat adalah bahwa node 17 pada gambar mewakili byte umum pertama dari '京' dan '七'. Ini adalah salah satu bug umum di banyak implementasi FST open source lainnya, dan proyek ini mengatasi masalah tersebut dengan sempurna.
Proyek pertama ini mengimplementasikan LRUcache dan LFUcache, yang digunakan dalam membangun struktur data pertama. Untuk mencegah penggunaan memori yang berlebihan, lruCache memainkan peran trade-off yang baik dalam proses pembuatan FST.
LruCache dapat membuat perkiraan pohon FST minimum untuk Anda, untuk mencapai perkiraan efek ruang minimum. Jika ruang memori mencukupi, disarankan agar kapasitas cache lruCache yang tersedia diatur sebesar mungkin saat membangun FST. Dengan cara ini, FST dibangun sekecil mungkin karena ruang dapat dihemat semaksimal mungkin.
Mengingat konstruksi file kamus FST selalu memerlukan input yang diurutkan secara leksikografis, proyek ini mengimplementasikan modul fungsi penyortiran eksternal file besar yang baik, dan juga mengimplementasikan alat baris perintah yang mudah digunakan, lfsort, untuk mengurutkan file besar file teks secara terpisah. Tentu saja, alat baris perintah FST sudah memiliki penyortiran file besar yang terintegrasi ke dalamnya, dan secara default alat ini memasukkan file teks besar yang tidak disortir. Penyortiran file berukuran besar juga memakan waktu. Jika file kamus masukan Anda sudah diurutkan, Anda dapat menampilkan argumen '-s' atau '--sorted' yang ditentukan untuk menghindari pengurutan file besar sebelum membuat FST. Anda dapat memasukkan 'lfsort --help' untuk melihat instruksi rinci untuk alat baris perintah pengurutan file besar 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!
Tentang proyek ini gunakan untuk masuk ke komponen cetak tulip - log dapat ditemukan di rilis sumber terbuka penulis dari proyek lain: https://github.com/apollo008/tulip-log. Salah satu premis dasar yang terlibat dalam penggunaan alat baris perintah proyek, ofst dan lfsort , adalah kebutuhan untuk mengkonfigurasi file definisi untuk log tuliop di direktori saat ini. Biasanya bernama logger.conf. Juga termasuk dalam proyek ini adalah penggunaan C++ yang kaya dari modul pengujian unit CppUnit untuk memastikan kualitas fungsi kode. misc/config/logger.conf adalah contoh file konfigurasi untuk Tulip Log: logger.conf.
Detail proses implementasi Levenshtein automata dan Damerau Levenshtein automata sebenarnya cukup rumit, topik ini bukan fokus proyek ini, meskipun kode sumber proyek ini sepenuhnya berisi implementasi kueri fuzzy Levenshtein dan Dameau Levenshtein yang cerdas dan efisien. Saya yakin akan sangat membantu bagi Anda untuk memahami algoritma kueri fuzzy dari pengukuran jarak edit Levenshtein dan Damerau Leveshtein. Mengenai topik penggunaan automata Levenshtein atau Damerau Levenshtein untuk menanyakan string serupa dengan cepat di mesin pencari, pembaca yang tertarik dapat membaca artikel lain dari penulis:<搜索引擎中相似字符串查找那些事儿> https://mp.weixin.qq.com/s/0ODgrWSVdRnYZxGRGmEdsA.
Terakhir, efisiensi algoritma implementasi ini secara teoritis sangat efisien, termasuk proses pembuatan FST dan query FST. Data uji kinerja yang lebih rinci akan ditambahkan di versi berikutnya.
Proyek Orchid-Fst ini saat ini mendukung kompilasi dan instalasi di lingkungan mirip UNIX. Itu bergantung pada perpustakaan pihak ketiga berikut:
Sebelum mengkompilasi dan menginstal proyek Orchid-Fst, Anda harus terlebih dahulu menginstal dua perpustakaan dependen di atas, satu perpustakaan log penelitian mandiri Tulip-Log, satu perpustakaan pengujian unit CppUnit, yang ada di direktori berbagi dan dapat dikompilasi terlebih dahulu.
Catatan: Di Ubuntu Linux, Anda mungkin harus menginstal zlib dengan perintah: 'sudo apt install zlib1g-dev' sebelum menginstal proyek ini. Baik di Ubuntu dan Centos Linux, Anda sebaiknya menggunakan versi gcc7/g++7 atau lebih tinggi.
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
Sekarang lfsort dan executable pertama akan dihasilkan di < /path/to/install >/bin; dan file .so yang sesuai akan berada di bawah direktori lib. jalankan perintah 'ofst --help' atau 'lfsort --help' akan membuat Anda terbiasa dengan penggunaannya.
Catatan: Sebelum menjalankan alat baris perintah, Anda perlu menempatkan file konfigurasi log logger.conf di direktori saat ini. Contoh konfigurasi ini ada di atas atau Anda dapat memperoleh contoh file logger.conf dari misc/config/logger.conf proyek. Selain itu, jangan lupa untuk membuat log pada jalur program saat ini seperti yang dikonfigurasi di logger.conf. Jika tidak, program akan mengalami kesalahan dan keluar. Alternatifnya, mengendalikan baris ketiga INFO tingkat log logger.conf atau DEBUG, ERROR, atau WARN akan memberi Anda informasi keluaran log untuk kata kerja yang berbeda.
Silakan hubungi [email protected] untuk pertanyaan terkait dan hal-hal lain yang tidak tercakup. Nikmatilah.
