orchid fst
To make ofst command line tool can print more petty help messages.
Este proyecto Orchid-Fst implementa una estructura de datos de búsqueda de diccionario de cadenas de texto rápido: Transductor de estado finito, que es la abreviatura de FST en lenguaje C++. Orchid-FST requiere compatibilidad con C++ 11 (es mejor compilar con GCC 7 o superior) y actualmente admite la compilación y la ejecución en sistemas tipo UNIX.
La primera estructura de datos se ha utilizado ampliamente en motores de búsqueda de código abierto: Elasticsearch y Lucene core source. Es tan rápido para buscar cadenas de texto que puede entenderse como un mapa de valores clave o una estructura de datos establecida. La complejidad del tiempo de consulta en la estructura de datos FST es O(n), donde n es la longitud de la cadena de texto real con la consulta, independientemente del tamaño del conjunto de datos de texto masivo. Esta es una ventaja muy importante y enorme.
Este proyecto de código abierto FST C++ Orchid-Fst tiene las siguientes ventajas significativas:
El proceso de construcción de FST en este proyecto puede realizar un volcado en un flujo de salida (como un archivo externo) para los datos de FST que se acaban de construir mientras se creaba FST para reducir la ocupación de memoria. Este punto es especialmente importante para datos de diccionario con gran regularidad. Porque dict no se puede cargar en la memoria de una sola vez para construir FST. Luego, el archivo de datos FST se utiliza como mapa de memoria. Muchas implementaciones actuales de FST de código abierto no tienen esta característica. Este es uno de los aspectos más importantes del proyecto.
Se implementa en lenguaje C++ y puede ser muy útil si su proyecto es solo un entorno de desarrollo C++. Existen algunas versiones de los primeros implementos de código abierto, pero rara vez se implementan bien en lenguaje C/C++ como código de alta calidad, por lo que puede integrarlo fácilmente en sus proyectos de desarrollo de C++. Como sabemos, se ha implementado en Rust y Java.
Ha resuelto con éxito cadenas de texto con código UTF8 y resuelve errores más graves cuando la cadena de texto no contiene caracteres ingleses, como caracteres chinos, etc. Utilizó un enfoque mucho más inteligente para resolver cadenas de texto con codificación UTF8.
Este proyecto presenta una gran cantidad de ejemplos de implementaciones de autómatas, de los cuales puede aprender más sobre las implementaciones de autómatas para muchos propósitos diferentes, ya sea que se realicen en estructuras de datos FST o se utilicen en otros escenarios. Las muchas estructuras de datos de autómatas en esta demostración del proyecto incluyen, entre otras: Mayor que, Menor que, Prefijo, Cadena, Comienza con, Intersección, Unión, No, Levenshtein Automaton, Damerau Levenshtein Automation, etc.
No solo implementa una interfaz de código, sino que también implementa cuidadosamente una herramienta de línea de comandos fácil de usar, es decir, orquídea-fst: ofst , con instrucciones detalladas sobre cómo usar los parámetros. La herramienta de línea de comandos más frecuente tiene las siguientes funciones.
ofst map/set puede construir un archivo fst a partir de su archivo de diccionario de entrada, que obtuvo la clave y el valor de cada línea separada por coma cuando se asigna el subcomando, y solo lee el primer elemento antes de la primera coma como clave cuando se establece el subcomando; ofst dot puede generar un archivo de puntos a partir del archivo fst, que puede generar un archivo de imagen, como un archivo png para ver la estructura del fst mediante el comando dot, como por ejemplo:
'punto -Tpng < xx.punto > xx.png' .
Otro punto importante es: ¡puedes ver los detalles en primer lugar de cada carácter chino! Esto es estimulante.
Los subcomandos match/prefix/range/fuzzy ejecutan búsquedas diferentes en fst. Puede obtener instrucciones de uso más detalladas utilizando 'ofst --help' o 'ofst map --help' o 'ofst fuzzy --help'. ¡Puede probarlo!
,10000
中国,100
中国人,50
中国人民,40
中国心,10
北七,3
北七家,10
北京,5
北平,2
La imagen de arriba muestra un efecto de imagen PNG simple generado por el subcomando ofst dot de la herramienta de línea de comandos del proyecto con los datos de texto del diccionario simple que se muestran arriba. Puede mostrar claramente la estructura de caracteres codificados de varios bytes, como los caracteres chinos. Una cosa importante a tener en cuenta es que el nodo 17 en la figura representa el primer byte común de '京' y '七'. Este es uno de los errores comunes en muchas otras implementaciones de FST de código abierto y este proyecto aborda perfectamente el problema.
Este primer proyecto implementa LRUcache y LFUcache, que se utilizaron en la construcción de la primera estructura de datos. Para evitar el uso excesivo de memoria, lruCache desempeña un buen papel de compensación en el proceso de construcción de FST.
LruCache puede construir un árbol FST mínimo aproximado para usted, para lograr el efecto de espacio mínimo aproximado. Si el espacio de memoria es suficiente, se recomienda que la capacidad de caché disponible de lruCache se establezca lo más grande posible al crear el FST. De esta manera, el FST se construye lo más pequeño posible porque se ahorra el máximo espacio posible.
Teniendo en cuenta que la construcción de archivos de diccionario de FST siempre requiere que la entrada esté ordenada lexicográficamente, este proyecto implementa un buen módulo de función de clasificación externa de archivos grandes y también implementa una herramienta de línea de comandos fácil de usar, lfsort, para ordenar archivos grandes. archivo de texto por separado. Por supuesto, la herramienta de línea de comandos FST ya tiene integrada la clasificación de archivos grandes y, de forma predeterminada, ingresa archivos de texto grandes que no están ordenados. La clasificación de archivos de gran tamaño también requiere mucho tiempo. Si sus archivos de diccionario de entrada ya están ordenados, puede mostrar los argumentos '-s' o '--sorted' especificados para evitar ordenar archivos grandes antes de construir FST. Puede ingresar 'lfsort --help' para ver instrucciones detalladas para la herramienta de línea de comandos de clasificación de archivos grandes 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!
Acerca de este proyecto, utilice el componente de impresión tulip para iniciar sesión; el registro se puede encontrar en la versión de código abierto del autor de otro proyecto: https://github.com/apollo008/tulip-log. Una de las premisas básicas involucradas en el uso de las herramientas de línea de comandos del proyecto, ofst y lfsort , es la necesidad de configurar un archivo de definición para el registro de tuliop en el directorio actual. Comúnmente se denomina logger.conf. También se incluye en este proyecto el uso enriquecido de C++ del módulo CppUnit de prueba unitaria para garantizar la calidad de la función del código. misc/config/logger.conf es un ejemplo de archivo de configuración para Tulip Log: logger.conf.
Los detalles del proceso de implementación de los autómatas Levenshtein y Damerau Levenshtein son en realidad bastante complejos, este tema no es el enfoque de este proyecto, aunque el código fuente de este proyecto contiene completamente la implementación inteligente y eficiente de las consultas difusas de Levenshtein y Dameau Levenshtein. Creo que le resultará útil comprender el algoritmo de consulta difusa de la medida de distancia de edición de Levenshtein y Damerau Leveshtein. Sobre el tema del uso de autómatas Levenshtein o Damerau Levenshtein para consultar rápidamente cadenas similares en motores de búsqueda, los lectores interesados pueden leer otro artículo del autor:<搜索引擎中相似字符串查找那些事儿> https://mp.weixin.qq.com/s/0ODgrWSVdRnYZxGRGmEdsA.
Por último, la eficiencia del algoritmo de esta implementación es teóricamente muy eficiente, incluido el proceso de creación de FST y consulta de FST. Se agregarán datos de pruebas de rendimiento más detallados en las siguientes versiones.
Este proyecto Orchid-Fst actualmente admite la compilación e instalación en un entorno similar a UNIX. Se basa en las siguientes bibliotecas de terceros:
Antes de compilar e instalar el proyecto Orchid-Fst, primero debe instalar las dos bibliotecas dependientes anteriores, una biblioteca de registro de autoinvestigación Tulip-Log y una biblioteca de prueba unitaria CppUnit, que se encuentran en el directorio compartido y se pueden compilar con anticipación.
Nota: En Ubuntu Linux, es posible que deba instalar zlib con el comando: 'sudo apt install zlib1g-dev' antes de instalar este proyecto. Tanto en Ubuntu como en Centos Linux, será mejor que uses la versión gcc7/g++7 o superior.
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
Ahora los ejecutables lfsort y ofst se generarán en < /path/to/install >/bin; y el archivo .so correspondiente estará en el directorio lib. Ejecute el comando 'ofst --help' o 'lfsort --help' le permitirá familiarizarse con su uso.
Nota: Antes de ejecutar la herramienta de línea de comandos, debe colocar el archivo de configuración de registro logger.conf en el directorio actual. Un ejemplo de esta configuración está arriba o puede obtener el archivo logger.conf de ejemplo desde misc/config/logger.conf del proyecto. Además, no olvide crear registros en la ruta actual del programa según lo configurado en logger.conf. De lo contrario, el programa ejecutará un error y se cerrará. Alternativamente, controlar la tercera línea del nivel de registro de logger.conf INFO o DEBUG, ERROR o WARN le brindará información de salida del registro para diferentes verbates.
Comuníquese con [email protected] si tiene preguntas relacionadas y otros asuntos no cubiertos. Disfrútala.
