orchid fst
To make ofst command line tool can print more petty help messages.
이 프로젝트 Orchid-Fst는 빠른 텍스트 문자열 사전 검색 데이터 구조인 Finite state transducer(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 구현에는 이 기능이 없습니다. 이는 프로젝트의 중요한 하이라이트 중 하나입니다.
이는 C++ 언어로 구현되며 프로젝트가 단지 C++ 개발 환경인 경우 매우 유용할 수 있습니다. fst 오픈 소스 구현의 일부 버전이 있지만 C/C++ 언어에서 고품질 코드로 잘 구현되는 경우는 거의 없으므로 C++ 개발 프로젝트에 쉽게 통합할 수 있습니다. 우리가 알고 있듯이 이는 Rust와 Java로 구현되었습니다.
UTF8 코드 텍스트 문자열을 성공적으로 해결했으며, 텍스트 문자열이 중국어 등 영어 문자가 아닌 경우 더 많은 서버 버그를 해결했습니다. UTF8 코딩 텍스트 문자열을 해결하기 위해 훨씬 더 영리한 접근 방식을 사용했습니다.
이 프로젝트는 FST 데이터 구조에서 수행되거나 다른 시나리오에서 사용되는지 여부에 관계없이 다양한 목적으로 오토마타 구현에 대해 자세히 알아볼 수 있는 수많은 오토마타 구현 예를 제시합니다. 이 프로젝트 데모의 많은 오토마타 데이터 구조에는 GreaterThan,LessThan,Prefix,Str,StartsWith,Intersection,Union,Not,Levenshtein Automaton, Damerau Levenshtein Automation 등이 포함되지만 이에 국한되지는 않습니다.
코드 인터페이스를 구현할 뿐만 아니라 매개 변수 사용 방법에 대한 자세한 지침과 함께 사용하기 쉬운 명령줄 도구인 orchid-fst: ofst 도 신중하게 구현합니다. ofst 명령줄 도구에는 다음과 같은 기능이 있습니다.
ofst map/set는 입력 사전 파일에서 fst 파일을 구성할 수 있습니다. 이 파일은 map 하위 명령 시 쉼표로 구분된 모든 줄에서 키와 값을 얻었으며, set 하위 명령 시 첫 번째 쉼표 앞의 첫 번째 항목만 키로 읽습니다. ofst 도트는 fst 파일에서 도트 파일을 생성할 수 있으며, 이는 도트 명령으로 fst 구조를 보기 위해 png 파일과 같은 그림 파일을 생성할 수 있습니다.
'점 -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 프로젝트는 fst 데이터 구조를 구성하는 데 사용되는 LRUcache와 LFUcache를 구현합니다. 과도한 메모리 사용을 방지하기 위해 lruCache는 FST를 구성하는 과정에서 좋은 균형 역할을 합니다.
LruCache는 대략적인 최소 공간 효과를 달성하기 위해 대략적인 최소 FST 트리를 구축할 수 있습니다. 메모리 공간이 충분하다면 FST를 구축할 때 lruCache의 사용 가능한 캐시 용량을 최대한 크게 설정하는 것이 좋습니다. 이런 식으로 FST는 공간을 최대한 절약하기 때문에 최대한 작게 제작됩니다.
FST의 사전 파일 구성에서는 입력이 항상 사전순으로 정렬되어야 한다는 점을 고려하여 이 프로젝트는 대용량 파일 외부 정렬 기능의 좋은 모듈을 구현하고 사용하기 쉬운 명령줄 도구인 lfsort를 구현하여 대용량 파일을 정렬합니다. 텍스트 파일을 별도로. 물론 FST 명령줄 도구에는 이미 대용량 파일 정렬 기능이 통합되어 있으며 기본적으로 정렬되지 않은 대용량 텍스트 파일을 입력합니다. 대용량 파일을 정렬하는 데도 시간이 많이 걸립니다. 입력 사전 파일이 이미 정렬된 경우 지정된 '-s' 또는 '--sorted' 인수를 표시하여 FST를 구성하기 전에 큰 파일을 정렬하지 않도록 할 수 있습니다. 대용량 파일 정렬 명령줄 도구 lfsort에 대한 자세한 지침을 보려면 'lfsort --help'를 입력할 수 있습니다.
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라고 합니다. 또한 이 프로젝트에는 코드 기능의 품질을 보장하기 위해 CppUnit 모듈을 테스트하는 풍부한 C++ 사용이 포함되어 있습니다. misc/config/logger.conf는 Tulip Log: 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를 쿼리하는 프로세스를 포함하여 이 구현의 알고리즘 효율성은 이론적으로 매우 효율적입니다. 보다 자세한 성능 테스트 데이터는 다음 버전에 추가될 예정입니다.
Orchid-Fst 프로젝트는 현재 UNIX와 유사한 환경에서의 컴파일 및 설치를 지원합니다. 이는 다음 타사 라이브러리에 의존합니다.
Orchid-Fst 프로젝트를 컴파일하고 설치하기 전에 먼저 위의 두 가지 종속 라이브러리, 즉 자가 연구 로그 라이브러리인 Tulip-Log와 유닛 테스트 라이브러리인 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 로그 수준 INFO, DEBUG, ERROR 또는 WARN의 세 번째 줄을 제어하면 다양한 동사에 대한 로그 출력 정보가 제공됩니다.
관련 질문이나 다루지 않은 기타 문제는 [email protected]으로 문의하세요. 즐겨보세요.
