orchid fst
To make ofst command line tool can print more petty help messages.
このプロジェクト 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データを出力ストリーム(外部ファイルなど)にダンプすることができます。この点は、規則性の大きい辞書データでは特に重要です。 FST を構築するために dict を一度にメモリにロードすることはできないためです。 FST データ ファイルはメモリ マップとして使用されます。現在のオープンソース FST 実装の多くには、この機能がありません。これはプロジェクトの重要なハイライトの 1 つです。
これは C++ 言語で実装されており、プロジェクトが単なる C++ 開発環境である場合に非常に便利です。 fst オープン ソース実装にはいくつかのバージョンがありますが、高品質のコードとして C/C++ 言語で適切に実装されることはほとんどないため、C++ 開発プロジェクトに簡単に統合できます。ご存知のとおり、これは Rust と Java で実装されています。
UTF8コードのテキスト文字列を解決することに成功し、テキスト文字列が中国語などの英語文字ではない場合のさらに多くのサーバーバグを解決します。 UTF8 コーディングのテキスト文字列を解決するために、より賢いアプローチが使用されました。
このプロジェクトでは、オートマトン実装の多数の例を紹介します。そこから、FST データ構造で実行されるか、他のシナリオで使用されるかにかかわらず、さまざまな目的でのオートマトン実装について詳しく学ぶことができます。このプロジェクトのデモの多くのオートマトン データ構造には、GreaterThan、LessThan、Prefix、Str、StartsWith、Intersection、Union、Not、レーベンシュタイン オートマトン、ダメラウ レーベンシュタイン オートメーションなどが含まれますが、これらに限定されません。
コード インターフェイスを実装するだけでなく、パラメータの使用方法に関する詳細な手順を含む、使いやすいコマンドライン ツール、つまり orchid-fst: ofstも慎重に実装します。 ofstコマンドライン ツールには次の機能があります。
ofst map/set は入力辞書ファイルから fst ファイルを構築できます。これは、map サブコマンドのときにカンマで区切られたすべての行からキーと値を取得し、set サブコマンドのときに最初のカンマの前の最初の項目のみをキーとして読み取ります。 ofst dot は、fst ファイルからドット ファイルを生成できます。fst ファイルは、次のような dot コマンドで fst 構造を確認するための png ファイルなどの画像ファイルを生成できます。
'ドット -Tpng < xx.dot > xx.png' 。
もう 1 つの重要な点は、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 画像効果を示しています。漢字などのマルチバイトエンコード文字の構造をわかりやすく表示します。注意すべき重要な点の 1 つは、図のノード 17 が「京」と「七」の両方の最初の共通バイトを表していることです。これは、他の多くのオープンソース FST 実装によくあるバグの 1 つであり、このプロジェクトはこの問題に完全に対処します。
この fst プロジェクトは、fst データ構造の構築に使用される LRUcache と LFUcache を実装します。過度のメモリ使用を防ぐために、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 を印刷するためにログインするために使用します。ログは、別のプロジェクトの作成者のオープン ソース リリースにあります: https://github.com/apollo008/tulip-log。プロジェクトのコマンドライン ツールofstおよびlfsort を使用する際の基本前提の 1 つは、現在のディレクトリに tuliop ログの定義ファイルを構成する必要があることです。通常、logger.conf という名前が付けられます。このプロジェクトには、コード関数の品質を保証するための単体テスト CppUnit モジュールの豊富な C++ の使用も含まれています。 miss/config/logger.conf は、Tulip Log の構成ファイルの例です: logger.conf。
レーベンシュタイン オートマトンとダメラウ レーベンシュタイン オートマトンの実装プロセスの詳細は、実際には非常に複雑です。このトピックはこのプロジェクトの焦点ではありませんが、このプロジェクトのソース コードにはレーベンシュタインとダメラウ レーベンシュタインのファジー クエリの賢くて効率的な実装が完全に含まれています。レーベンシュタインのファジー クエリ アルゴリズムとダメラウ レーベシュタインの編集距離測定を理解するのに役立つと思います。レーベンシュタインまたはダメラウ レーベンシュタイン オートマトンを使用して検索エンジンで同様の文字列をすばやくクエリする方法について、興味のある読者は著者による別の記事を読むことができます:<搜索引擎中相似字符串查找那珂事儿> https://mp.weixin .qq.com/s/0ODgrWSVdRnYZxGRGmEdsA。
最後に、この実装のアルゴリズム効率は、FST の構築と FST のクエリのプロセスを含め、理論的には非常に効率的です。より詳細なパフォーマンス テスト データは、次のバージョンで追加される予定です。
このプロジェクト Orchid-Fst は現在、UNIX のような環境でのコンパイルとインストールをサポートしています。これは、次のサードパーティ ライブラリに依存します。
Orchid-Fst プロジェクトをコンパイルしてインストールする前に、まず上記の 2 つの依存ライブラリ、1 つの自己調査ログ ライブラリ Tulip-Log、1 つの単体テスト ライブラリ CppUnit をインストールする必要があります。これらは共有ディレクトリにあり、事前にコンパイルできます。
注: Ubuntu Linux では、このプロジェクトをインストールする前に、「sudo apt install zlib1g-dev」コマンドで zlib をインストールする必要があります。 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 の 3 行目のログ レベル INFO または DEBUG、ERROR、または WARN を制御すると、さまざまな動詞のログ出力情報が得られます。
関連する質問や取り上げられていない事項については、[email protected] までお問い合わせください。楽しめ。
