orchid fst
To make ofst command line tool can print more petty help messages.
Этот проект Orchid-Fst реализует структуру данных быстрого поиска по словарю текстовых строк: преобразователь конечных состояний, что является сокращением от FST на языке C++. 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 или используются в других сценариях. Многие структуры данных автоматов в этом демонстрационном проекте включают, помимо прочего: GreaterThan, LessThan, Prefix, Str, StartsWith, Intersection, Union, Not, автомат Левенштейна, автоматизацию Дамерау Левенштейна и так далее.
Он не только реализует интерфейс кода, но также тщательно реализует простой в использовании инструмент командной строки, то есть orchid-fst: ofst , с подробными инструкциями по использованию параметров. Самый популярный инструмент командной строки имеет следующие функции.
ofst map/set может создать файл fst из входного файла словаря, который получает ключ и значение из каждой строки, разделенной запятой, при выполнении подкоманды карты, и читает только первый элемент перед первой запятой в качестве ключа при выполнении подкоманды set; ofst dot может создать точечный файл из файла fst, который может быть сгенерирован файлом изображения, например файлом png, чтобы увидеть структуру fst с помощью команды dot, например:
'точка -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
На изображении выше показан простой эффект PNG-изображения, созданный подкомандой ofst dot инструмента командной строки проекта ofst с простыми текстовыми данными словаря, показанными выше. Он может четко отображать структуру многобайтовых закодированных символов, таких как китайские иероглифы. Важно отметить, что узел 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 - журнал можно найти в авторской версии с открытым исходным кодом другого проекта: https://github.com/apollo008/tulip-log. Одной из основных предпосылок использования инструментов командной строки проекта ofst и lfsort является необходимость настройки файла определения для журнала tuliop в текущем каталоге. Обычно его называют logger.conf. В этот проект также включено широкое использование C++ модуля модульного тестирования CppUnit для обеспечения качества функции кода. misc/config/logger.conf — это пример файла конфигурации Tulip Log: logger.conf.
Детали процесса реализации автоматов Левенштейна и автомата Левенштейна Дамерау на самом деле довольно сложны, эта тема не является предметом внимания данного проекта, хотя исходный код этого проекта полностью содержит умную и эффективную реализацию нечетких запросов Левенштейна и Дамерау Левенштейна. Я считаю, что вам будет полезно понять алгоритм нечетких запросов Левенштейна и меру расстояния редактирования Дамерау Левештейна. На тему использования автоматов Левенштейна или Дамерау Левенштейна для быстрого запроса похожих строк в поисковых системах заинтересованные читатели могут прочитать еще одну статью автора: https://mp.weixin.qq.com/s/0ODgrWSVdRnYZxGRGmEdsA.
Наконец, эффективность алгоритма этой реализации теоретически очень эффективна, включая процесс построения FST и запроса FST. Более подробные данные тестирования производительности будут добавлены в следующих версиях.
Этот проект Orchid-Fst в настоящее время поддерживает компиляцию и установку в UNIX-подобной среде. Он опирается на следующие сторонние библиотеки:
Перед компиляцией и установкой проекта Orchid-Fst вам следует сначала установить две вышеуказанные зависимые библиотеки, одну библиотеку журналов самоисследования Tulip-Log, одну библиотеку модульных тестов CppUnit, которые находятся в общем каталоге и могут быть скомпилированы заранее.
Примечание. В 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 в текущий каталог. Пример этой конфигурации приведен выше, или вы можете получить пример файла logger.conf из misc/config/logger.conf проекта. Кроме того, не забудьте создать журналы по текущему пути программы, как указано в logger.conf. В противном случае программа выдаст ошибку и завершится. Альтернативно, управляя третьей строкой logger.conf уровня журнала INFO или DEBUG, ERROR или WARN, вы получите информацию о выводе журнала для различных вербатов.
Пожалуйста, свяжитесь с [email protected] по соответствующим вопросам и другим вопросам, которые не охвачены. Наслаждайся этим.
