orchid fst

蘭花-Fst

一、專案概況

Orchid-Fst這個專案實作了一種快速文字字串字典搜尋資料結構：有限狀態轉換器，它是C++語言中FST的縮寫。 Orchid-FST需要C++11支援（最好使用GCC 7或更高版本編譯），目前支援在類別UNIX系統上編譯和運行。

Fst資料結構已廣泛應用於開源搜尋引擎：Elasticsearch和Lucene核心源碼中。它對於搜尋文字字串的速度非常快，可以將其理解為鍵值映射或集合資料結構。 FST資料結構的查詢時間複雜度為O(n)，其中n是查詢的實際文字字串的長度，與海量文字資料集的大小無關。這是一個非常重要且巨大的優勢。

這個FST C++開源專案Orchid-Fst有以下顯著優勢：

1. 本專案中的FST建置流程可以在建置FST的同時將剛剛建置的FST資料轉儲到輸出流（如外部檔案），以減少記憶體佔用。這一點對於規律性較大的字典資料尤其重要。因為dict不能一次全部載入到記憶體中來構造FST。然後將 FST 資料檔案用作記憶體映射。目前許多開源 FST 實作不具備此功能。這是該項目的重要亮點之一。

2. 它是用 C++ 語言實現的，如果您的專案只是 C++ 開發環境，那麼它可能會非常有用。 fst 開源工具有一些版本，但很少能在 C/C++ 語言中很好地實現高品質程​​式碼，因此您可以輕鬆地將其整合到您的 C++ 開發專案中。眾所周知，它已在 Rust 和 Java 中實作。

3. 它已經成功解析了UTF8編碼的文本字串，並解決了當文字字串不是英文字元（例如漢字等）時更嚴重的錯誤。它使用了一種更聰明的方法來解析 UTF8 編碼文字字串。

4. 該專案提供了大量自動機實現的示例，從中您可以了解更多有關許多不同目的的自動機實現的信息，無論它們是在 FST 資料結構上執行還是在其他場景中使用。本專案Demo中的多種自動機資料結構包括但不限於：GreaterThan、LessThan、Prefix、Str、StartsWith、Intersection、Union、Not、Levenshtein Automaton、Damerau Levenshtein Automation等。

5. 它不僅實現了程式碼接口，還精心實作了一個易於使用的命令列工具，即 orchid-fst: ofst ，並詳細說明如何使用參數。 ofst命令列工具具有以下功能。

   ofst map/set 可以根據輸入的字典文件建構一個fst 文件，當使用map 子命令時，它會從每一行以逗號分隔的行中獲取鍵和值，而當使用set 子命令時，它只讀取第一個逗號之前的第一項作為鍵； ofst dot可從fst文件產生dot文件，可以產生圖片文件，如png文件，透過dot指令查看fst結構，如：

   '點-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
   

   上圖顯示了由專案的命令列工具ofst的ofst dot 子命令與上面顯示的簡單字典文字資料產生的簡單 PNG 圖像效果。可以清楚顯示漢字等多位元組編碼字元的結構。需要注意的一個重要事項是，圖中的節點 17 代表「京」和「七」的第一個公共位元組。這是許多其他開源 FST 實作中的常見錯誤之一，該專案完美地解決了該問題。

6. 此fst專案實作了LRUcache和LFUcache，用於建構fst資料結構。為了防止記憶體使用過多，lruCache在建構FST的過程中起到了很好的權衡作用。

   LruCache可以為您建立一棵近似最小FST樹，達到近似最小空間效果。如果記憶體空間充足，建議建置FST時將lruCache的可用快取容量設定得盡可能大。透過這種方式，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!

關於本專案使用登入列印元件tulip-log可以在作者的另一個專案的開源發布中找到：https://github.com/apollo008/tulip-log。使用專案的命令列工具ofst和lfsort涉及的基本前提之一是需要在目前目錄中為 tuliop 日誌配置定義檔。它通常命名為 logger.conf。這個專案中也包含了豐富的C++使用單元測試CppUnit模組來保證程式碼品質的功能。 Misc/config/logger.conf 是 Tulip Log 的設定檔範例：logger.conf。

Levenshtein自動機和Damerau Levenshtein自動機的實現過程細節其實相當複雜，這個主題不是本專案的重點，儘管本專案的源代碼完全包含了Levenshtein和Dameau Levenshtein模糊查詢的巧妙高效的實現。相信對您理解Levenshtein的模糊查詢演算法和Damerau Leveshtein的編輯距離度量會有幫助。關於利用Levenshtein或Damerau Levenshtein自動機在搜尋引擎中快速查詢相似字串的話題，有興趣的讀者可以閱讀作者的另一篇文章：<搜尋引擎中相似字串查找那些事> https://mp. weixin .qq.com/s/0ODgrWSVdRnYZxGRGmEdsA。

最後，本實現的演算法效率理論上是非常有效率的，包括建立FST和查詢FST的過程。後續版本將添加更詳細的效能測試數據。

2.專案編譯安裝

此專案Orchid-Fst目前支援在類別UNIX環境下編譯安裝。它依賴以下第三方函式庫：

• 單元
• 鬱金香原木

在編譯安裝Orchid-Fst專案之前，首先要安裝上面兩個依賴函式庫，一個自研日誌庫Tulip-Log，一個單元測試庫CppUnit，它們都在share目錄下，可以事先編譯。

注意：在 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日誌設定檔放置在目前目錄下。上面是此配置的範例，或者您可以從專案的misc/config/logger.conf取得範例logger.conf 檔案。另外，不要忘記按照 logger.conf 中的配置在程式的當前路徑中建立日誌。否則程式會運行出錯並退出。或者，控制 logger.conf 日誌等級 INFO 或 DEBUG、ERROR 或 WARN 的第三行將為您提供不同動詞的日誌輸出資訊。

相關問題及其他未盡事宜請聯絡[email protected]。好好享受。