orchid fst下载 - orchid fst源码下载

orchid fst

其他源码

To make ofst command line tool can print more petty help messages.

下载

兰花-Fst

一、项目概况

Orchid-Fst这个项目实现了一种快速文本字符串字典搜索数据结构：有限状态转换器，它是C++语言中FST的缩写。 Orchid-FST 需要 C++11 支持（最好使用 GCC 7 或更高版本编译），目前支持在类 UNIX 系统上编译和运行。

Fst数据结构已广泛应用于开源搜索引擎：Elasticsearch和Lucene核心源码中。它对于搜索文本字符串的速度非常快，可以将其理解为键值映射或集合数据结构。 FST数据结构的查询时间复杂度为O(n)，其中n是查询的实际文本字符串的长度，与海量文本数据集的大小无关。这是一个非常重要且巨大的优势。

这个FST C++开源项目Orchid-Fst具有以下显着优势：

本项目中的FST构建过程可以在构建FST的同时将刚刚构建的FST数据转储到输出流（如外部文件），以减少内存占用。这一点对于规律性较大的字典数据尤为重要。因为dict不能一次性全部加载到内存中来构造FST。 FST 数据文件然后用作内存映射。当前许多开源 FST 实现不具备此功能。这是该项目的重要亮点之一。
它是用 C++ 语言实现的，如果您的项目只是 C++ 开发环境，它可能会非常有用。 fst 开源工具有一些版本，但很少能在 C/C++ 语言中很好地实现高质量代码，因此您可以轻松地将其集成到您的 C++ 开发项目中。众所周知，它已在 Rust 和 Java 中实现。
它已经成功解析了UTF8编码的文本字符串，并解决了当文本字符串不是英文字符（例如汉字等）时更严重的错误。它使用了一种更聪明的方法来解析 UTF8 编码文本字符串。
该项目提供了大量自动机实现的示例，从中您可以了解更多有关许多不同目的的自动机实现的信息，无论它们是在 FST 数据结构上执行还是在其他场景中使用。本项目Demo中的多种自动机数据结构包括但不限于：GreaterThan、LessThan、Prefix、Str、StartsWith、Intersection、Union、Not、Levenshtein Automaton、Damerau Levenshtein Automation等。
它不仅实现了代码接口，还精心实现了一个易于使用的命令行工具，即 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 实现中的常见错误之一，该项目完美地解决了该问题。
该fst项目实现了LRUcache和LFUcache，用于构造fst数据结构。为了防止内存使用过多，lruCache在构建FST的过程中起到了很好的权衡作用。
LruCache可以为您构建一棵近似最小FST树，达到近似最小空间效果。如果内存空间充足，建议构建FST时将lruCache的可用缓存容量设置得尽可能大。通过这种方式，FST 被构建得尽可能小，因为尽可能节省了空间。
考虑到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]。好好享受。

展开

附加信息