orchid fst
To make ofst command line tool can print more petty help messages.
Ce projet Orchid-Fst implémente une structure de données de recherche rapide dans un dictionnaire de chaînes de texte : Finite state transducer , qui est l'abréviation de FST en langage C++. Orchid-FST nécessite la prise en charge de C++11 (il est préférable de compiler avec GCC 7 ou supérieur) et prend actuellement en charge la compilation et l'exécution sur des systèmes de type UNIX.
La première structure de données a été largement utilisée dans les moteurs de recherche open source : Elasticsearch et Lucene core source. Il est si rapide de rechercher une chaîne de texte qu'il peut être compris comme une carte clé-valeur ou une structure de données définie. La complexité temporelle de la requête sur la structure de données FST est O(n), où n est la longueur de la chaîne de texte réelle avec la requête, indépendamment de la taille de l'ensemble massif de données texte. C’est un avantage très important et énorme.
Ce projet open source FST C++ Orchid-Fst présente les avantages significatifs suivants :
Le processus de construction FST dans ce projet peut réaliser un vidage vers le flux de sortie (tel qu'un fichier externe) pour les données FST qui viennent d'être construites lors de la construction de FST afin de réduire l'occupation de la mémoire. Ce point est particulièrement important pour les données du dictionnaire avec une grande régularité. Parce que dict ne peut pas être chargé en mémoire d’un seul coup pour construire FST. Le fichier de données FST est ensuite utilisé comme carte mémoire. De nombreuses implémentations open source actuelles de FST ne disposent pas de cette fonctionnalité. C’est l’un des points forts du projet.
Il est implémenté en langage C++ et peut être très utile si votre projet est uniquement un environnement de développement C++. Il existe quelques versions des premiers implémentations open source, mais elles sont rarement bien implémentées en langage C/C++ en tant que code de haute qualité, vous pouvez donc facilement l'intégrer dans vos projets de développement C++. Comme nous le savons, il a été implémenté dans Rust et Java.
Il a résolu avec succès la chaîne de texte de code UTF8 et a résolu des bogues plus graves lorsque la chaîne de texte ne contient pas de caractères anglais, tels que des caractères chinois, etc. Il a utilisé une approche beaucoup plus intelligente pour résoudre la chaîne de texte codée en UTF8.
Ce projet présente un grand nombre d'exemples d'implémentations d'automates, à partir desquels vous pouvez en apprendre davantage sur les implémentations d'automates à de nombreuses fins différentes, qu'elles soient effectuées sur des structures de données FST ou utilisées dans d'autres scénarios. Les nombreuses structures de données d'automates de ce projet de démonstration incluent, sans s'y limiter : GreaterThan, LessThan, Prefix, Str, StartsWith, Intersection, Union, Not, Levenshtein Automaton, Damerau Levenshtein Automation, etc.
Non seulement il implémente une interface de code, mais il implémente également soigneusement un outil de ligne de commande facile à utiliser, à savoir orchid-fst: ofst , avec des instructions détaillées sur la façon d'utiliser les paramètres. Le principal outil de ligne de commande a les fonctions suivantes.
ofst map/set peut construire un fichier fst à partir de votre fichier de dictionnaire d'entrée, qui obtient la clé et la valeur de chaque ligne séparée par une virgule lors de la sous-commande map, et il ne lit que le premier élément avant la première virgule comme clé lors de la sous-commande set ; ofst dot peut générer un fichier dot à partir du fichier fst, qui peut être généré un fichier image, tel qu'un fichier png pour voir la structure fst par commande dot, telle que :
'dot -Tpng < xx.dot > xx.png' .
Un autre point important est : vous pouvez voir les détails en premier pour chaque caractère chinois ! C’est exaltant.
Les sous-commandes match/prefix/range/fuzzy exécutent différentes recherches dans fst. Vous pouvez obtenir des instructions d'utilisation plus détaillées en utilisant 'ofst --help' ou 'ofst map --help' ou 'ofst fuzzy --help', vous pouvez l'essayer !
,10000
中国,100
中国人,50
中国人民,40
中国心,10
北七,3
北七家,10
北京,5
北平,2
L'image ci-dessus montre un simple effet d'image PNG généré par la sous-commande ofst dot de l'outil de ligne de commande du projet ofst avec les données textuelles simples du dictionnaire présentées ci-dessus. Il peut afficher clairement la structure des caractères codés sur plusieurs octets tels que les caractères chinois. Une chose importante à noter est que le nœud 17 sur la figure représente le premier octet commun à « 京 » et « 七 ». C'est l'un des bugs courants dans de nombreuses autres implémentations open source de FST, et ce projet résout parfaitement le problème.
Ce premier projet implémente LRUcache et LFUcache, qui sont utilisés dans la construction de la première structure de données. Afin d'éviter une utilisation excessive de la mémoire, lruCache joue un bon rôle de compromis dans le processus de construction de FST.
LruCache peut créer une arborescence FST minimale approximative pour vous, afin d'obtenir l'effet d'espace minimum approximatif. Si l'espace mémoire est suffisant, il est recommandé que la capacité de cache disponible de lruCache soit définie aussi grande que possible lors de la construction du FST. De cette manière, le FST est construit aussi petit que possible car l'espace est économisé autant que possible.
Considérant que la construction du fichier dictionnaire de FST nécessite toujours que l'entrée soit ordonnée lexicographiquement, ce projet implémente un bon module de fonction de tri externe de gros fichiers, et implémente également un outil de ligne de commande facile à utiliser, lfsort, pour trier les gros fichiers. fichier texte séparément. Bien sûr, l'outil de ligne de commande FST intègre déjà le tri des fichiers volumineux et, par défaut, il saisit de gros fichiers texte non triés. Le tri des fichiers volumineux prend également du temps. Si vos fichiers de dictionnaire d'entrée sont déjà triés, vous pouvez afficher les arguments '-s' ou '--sorted' spécifiés pour éviter de trier des fichiers volumineux avant de construire FST. Vous pouvez saisir « lfsort --help » pour voir les instructions détaillées de l'outil de ligne de commande de tri de fichiers volumineux 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!
À propos de ce projet, utilisez pour vous connecter au composant d'impression tulip - le journal peut être trouvé dans la version open source de l'auteur d'un autre projet : https://github.com/apollo008/tulip-log. L'un des prémisses de base impliquées dans l'utilisation des outils de ligne de commande du projet, ofst et lfsort , est la nécessité de configurer un fichier de définition pour le journal tuliop dans le répertoire courant. Il est communément nommé logger.conf. Ce projet comprend également l'utilisation riche en C++ du module de tests unitaires CppUnit pour garantir la qualité de la fonction de code. misc/config/logger.conf est un exemple de fichier de configuration pour Tulip Log : logger.conf.
Les détails du processus de mise en œuvre des automates Levenshtein et Damerau Levenshtein sont en fait assez complexes, ce sujet n'est pas l'objet de ce projet, bien que le code source de ce projet contienne entièrement l'implémentation intelligente et efficace de la requête floue Levenshtein et Dameau Levenshtein. Je pense qu'il vous sera utile de comprendre l'algorithme de requête floue de la mesure de distance d'édition de Levenshtein et Damerau Leveshtein. Sur le thème de l'utilisation des automates Levenshtein ou Damerau Levenshtein pour interroger rapidement des chaînes similaires dans les moteurs de recherche, les lecteurs intéressés peuvent lire un autre article de l'auteur :<搜索引擎中相似字符串查找那些事儿> https://mp.weixin.qq.com/s/0ODgrWSVdRnYZxGRGmEdsA.
Enfin, l'efficacité de l'algorithme de cette implémentation est théoriquement très efficace, y compris le processus de construction de FST et d'interrogation de FST. Des données de tests de performances plus détaillées seront ajoutées dans les versions suivantes.
Ce projet Orchid-Fst prend actuellement en charge la compilation et l'installation dans un environnement de type UNIX. Il s'appuie sur les bibliothèques tierces suivantes :
Avant de compiler et d'installer le projet Orchid-Fst, vous devez d'abord installer les deux bibliothèques dépendantes ci-dessus, une bibliothèque de journaux d'auto-recherche Tulip-Log, une bibliothèque de tests unitaires CppUnit, qui se trouvent dans le répertoire de partage et peuvent être compilées à l'avance.
Remarque : sous Ubuntu Linux, vous devez installer zlib par la commande : "sudo apt install zlib1g-dev" avant d'installer ce projet. Sous Ubuntu et Centos Linux, vous feriez mieux d'utiliser la version gcc7/g++7 ou supérieure.
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
Désormais, les exécutables lfsort et ofst seront générés dans < /path/to/install >/bin ; et le fichier .so correspondant sera dans le répertoire lib. exécuter la commande 'ofst --help' ou 'lfsort --help' vous familiarisera avec leur utilisation.
Remarque : Avant d'exécuter l'outil de ligne de commande, vous devez placer le fichier de configuration du journal logger.conf dans le répertoire actuel. Un exemple de cette configuration est ci-dessus ou vous pouvez obtenir l'exemple de fichier logger.conf à partir de misc/config/logger.conf du projet. N'oubliez pas non plus de créer des journaux sur le chemin actuel du programme tel que configuré dans logger.conf. Sinon, le programme générera une erreur et se terminera. Alternativement, contrôler la troisième ligne du niveau de journalisation logger.conf INFO ou DEBUG, ERROR ou WARN vous donnera des informations de sortie de journal pour différents verbates.
Veuillez contacter [email protected] pour les questions connexes et autres sujets non couverts. Profitez-en.
