orchid fst
To make ofst command line tool can print more petty help messages.
Dieses Projekt Orchid-Fst implementiert eine schnelle Suchdatenstruktur für Textzeichenfolgenwörterbücher: Finite State Transducer, die Abkürzung für FST in der C++-Sprache. Orchid-FST erfordert C++11-Unterstützung (am besten mit GCC 7 oder höher kompilieren) und unterstützt derzeit die Kompilierung und Ausführung auf UNIX-ähnlichen Systemen.
Die erste Datenstruktur wird häufig in Open-Source-Suchmaschinen verwendet: Elasticsearch und Lucene-Kernquelle. Die Suchtextzeichenfolge ist so schnell, dass sie als Schlüsselwertzuordnung oder festgelegte Datenstruktur verstanden werden kann. Die Abfragezeitkomplexität für die FST-Datenstruktur beträgt O(n), wobei n die Länge der tatsächlichen Textzeichenfolge mit der Abfrage ist, unabhängig von der Größe des umfangreichen Textdatensatzes. Das ist ein sehr wichtiger und großer Vorteil.
Dieses FST C++ Open-Source-Projekt Orchid-Fst bietet die folgenden wesentlichen Vorteile:
Der FST-Konstruktionsprozess in diesem Projekt kann eine Ausgabe in einen Ausgabestream (z. B. eine externe Datei) für FST-Daten realisieren, die gerade erstellt wurden, während FST erstellt wird, um die Speicherbelegung zu reduzieren. Dieser Punkt ist besonders wichtig für Wörterbuchdaten mit großer Regelmäßigkeit. Weil dict nicht auf einmal in den Speicher geladen werden kann, um FST zu erstellen. Die FST-Datendatei wird dann als Speicherzuordnung verwendet. Viele aktuelle Open-Source-FST-Implementierungen verfügen nicht über diese Funktion. Dies ist einer der wichtigen Höhepunkte des Projekts.
Es ist in der Sprache C++ implementiert und kann sehr nützlich sein, wenn Ihr Projekt nur eine C++-Entwicklungsumgebung ist. Es gibt einige Versionen von fst-Open-Source-Implementierungen, aber es ist sehr selten, dass es gut in der C/C++-Sprache als qualitativ hochwertiger Code implementiert ist, sodass Sie es problemlos in Ihre C++-Entwicklungsprojekte integrieren können. Wie wir wissen, wurde es in Rust und Java implementiert.
Es hat die UTF8-Code-Textzeichenfolge erfolgreich aufgelöst und weitere schwerwiegende Fehler behoben, wenn die Textzeichenfolge keine englischen Zeichen enthält, wie z. B. chinesische Zeichen usw. Es wurde ein viel clevererer Ansatz zur Auflösung von UTF8-kodierten Textzeichenfolgen verwendet.
Dieses Projekt präsentiert eine große Anzahl von Beispielen für Automatenimplementierungen, anhand derer Sie mehr über Automatenimplementierungen für viele verschiedene Zwecke erfahren können, unabhängig davon, ob sie auf FST-Datenstrukturen ausgeführt oder in anderen Szenarien verwendet werden. Zu den vielen Automatendatenstrukturen in dieser Projektdemo gehören unter anderem: GreaterThan, LessThan, Prefix, Str, StartsWith, Intersection, Union, Not, Levenshtein Automaton, Damerau Levenshtein Automation und so weiter.
Es implementiert nicht nur eine Codeschnittstelle, sondern implementiert auch sorgfältig ein benutzerfreundliches Befehlszeilentool, nämlich orchid-fst: ofst , mit detaillierten Anweisungen zur Verwendung von Parametern. Das ofst -Befehlszeilentool verfügt über die folgenden Funktionen.
ofst map/set kann aus Ihrer Eingabewörterbuchdatei eine FST-Datei erstellen, die beim Unterbefehl „map“ Schlüssel und Wert aus jeder durch Komma getrennten Zeile erhält und beim Unterbefehl „set“ nur das erste Element vor dem ersten Komma als Schlüssel liest. ofst dot kann eine dot-Datei aus einer fst-Datei generieren, die eine Bilddatei generieren kann, z. B. eine PNG-Datei, um die fst-Struktur mit dem dot-Befehl anzuzeigen, z. B.:
'dot -Tpng < xx.dot > xx.png' .
Ein weiterer wichtiger Punkt ist: Sie können im fst Details zu jedem chinesischen Schriftzeichen sehen! Das ist berauschend.
Die Unterbefehle „match/prefix/range/fuzzy“ führen eine andere Suche in fst aus. Sie können detailliertere Gebrauchsanweisungen erhalten, indem Sie „ofst --help“ oder „ofst map --help“ oder „ofst fuzzy --help“ verwenden. Sie können es ausprobieren!
,10000
中国,100
中国人,50
中国人民,40
中国心,10
北七,3
北七家,10
北京,5
北平,2
Das Bild oben zeigt einen einfachen PNG-Bildeffekt, der durch den Unterbefehl ofst dot des Befehlszeilentools ofst des Projekts mit den oben gezeigten einfachen Wörterbuchtextdaten generiert wird. Es kann die Struktur von Multibyte-codierten Zeichen wie chinesischen Schriftzeichen klar darstellen. Es ist wichtig zu beachten, dass Knoten 17 in der Abbildung das erste gemeinsame Byte von „京“ und „七“ darstellt. Dies ist einer der häufigsten Fehler in vielen anderen Open-Source-FST-Implementierungen, und dieses Projekt geht dieses Problem perfekt an.
Dieses erste Projekt implementiert LRUcache und LFUcache, die beim Aufbau der ersten Datenstruktur verwendet werden. Um eine übermäßige Speichernutzung zu verhindern, spielt lruCache eine gute Kompromissrolle beim Erstellen von FST.
LruCache kann für Sie einen ungefähren minimalen FST-Baum erstellen, um den ungefähren minimalen Platzeffekt zu erzielen. Wenn der Speicherplatz ausreicht, wird empfohlen, beim Erstellen des FST die verfügbare Cache-Kapazität des lruCache so groß wie möglich festzulegen. Auf diese Weise wird der FST so klein wie möglich gebaut, da so viel Platz wie möglich gespart wird.
Da die Wörterbuchdateikonstruktion von FST immer eine lexikografische Reihenfolge der Eingaben erfordert, implementiert dieses Projekt ein gutes Modul für die externe Sortierfunktion für große Dateien sowie ein benutzerfreundliches Befehlszeilentool, lfsort, zum Sortieren großer Dateien Textdatei separat. Natürlich verfügt das FST-Befehlszeilentool bereits über eine integrierte Sortierung großer Dateien und gibt standardmäßig große Textdateien ein, die unsortiert sind. Auch das Sortieren großer Dateien ist zeitaufwändig. Wenn Ihre Eingabewörterbuchdateien bereits sortiert sind, können Sie die angegebenen Argumente „-s“ oder „--sorted“ anzeigen, um das Sortieren großer Dateien vor dem Erstellen von FST zu vermeiden. Sie können „lfsort --help“ eingeben, um detaillierte Anweisungen für das Befehlszeilentool lfsort zum Sortieren großer Dateien anzuzeigen.
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!
Über dieses Projekt können Sie sich anmelden, um die Tulip-Komponente auszudrucken. Das Protokoll finden Sie in der Open-Source-Version eines anderen Projekts des Autors: https://github.com/apollo008/tulip-log. Eine der Grundvoraussetzungen für die Verwendung der Befehlszeilentools des Projekts, ofst und lfsort , ist die Notwendigkeit, eine Definitionsdatei für das Tuliop-Protokoll im aktuellen Verzeichnis zu konfigurieren. Es wird üblicherweise logger.conf genannt. In diesem Projekt ist auch die umfassende C++-Nutzung des Unit-Testing-Moduls CppUnit enthalten, um die Qualität der Codefunktion sicherzustellen. misc/config/logger.conf ist ein Beispiel einer Konfigurationsdatei für Tulip Log: logger.conf.
Die Details des Implementierungsprozesses von Levenshtein-Automaten und Damerau Levenshtein-Automaten sind tatsächlich recht komplex. Dieses Thema steht nicht im Mittelpunkt dieses Projekts, obwohl der Quellcode dieses Projekts vollständig die clevere und effiziente Implementierung der Fuzzy-Abfrage von Levenshtein und Dameau Levenshtein enthält. Ich glaube, es wird für Sie hilfreich sein, den Fuzzy-Abfragealgorithmus des Bearbeitungsentfernungsmaßes von Levenshtein und Damerau Leveshtein zu verstehen. Zum Thema der Verwendung von Levenshtein- oder Damerau Levenshtein-Automaten zur schnellen Abfrage ähnlicher Zeichenfolgen in Suchmaschinen können interessierte Leser einen weiteren Artikel des Autors lesen:<搜索引擎中相似字符串查找那些事儿> https://mp.weixin.qq.com/s/0ODgrWSVdRnYZxGRGmEdsA.
Schließlich ist die Algorithmuseffizienz dieser Implementierung theoretisch sehr effizient, einschließlich des Prozesses zum Erstellen von FST und zum Abfragen von FST. Detailliertere Leistungstestdaten werden in den folgenden Versionen hinzugefügt.
Dieses Projekt Orchid-Fst unterstützt derzeit die Kompilierung und Installation in einer UNIX-ähnlichen Umgebung. Es basiert auf den folgenden Bibliotheken von Drittanbietern:
Bevor Sie das Orchid-Fst-Projekt kompilieren und installieren, sollten Sie zunächst die beiden oben genannten abhängigen Bibliotheken installieren, eine Selbstforschungsprotokollbibliothek Tulip-Log und eine Komponententestbibliothek CppUnit, die sich im Freigabeverzeichnis befinden und vorab kompiliert werden können.
Hinweis: Unter Ubuntu Linux sollten Sie zlib möglicherweise mit dem Befehl „sudo apt install zlib1g-dev“ installieren, bevor Sie dieses Projekt installieren. Sowohl in Ubuntu als auch in Centos Linux sollten Sie besser die Version gcc7/g++7 oder höher verwenden.
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
Jetzt werden lfsort und ofst executable in < /path/to/install >/bin generiert; und die entsprechende .so-Datei befindet sich im lib-Verzeichnis. Führen Sie den Befehl „ofst --help“ oder „lfsort --help“ aus, um Sie mit deren Verwendung vertraut zu machen.
Hinweis: Bevor Sie das Befehlszeilentool ausführen, müssen Sie die Protokollkonfigurationsdatei logger.conf im aktuellen Verzeichnis ablegen. Ein Beispiel für diese Konfiguration finden Sie oben. Alternativ können Sie die Beispieldatei logger.conf unter misc/config/logger.conf des Projekts abrufen. Vergessen Sie außerdem nicht, Protokolle im aktuellen Pfad des Programms zu erstellen, wie in logger.conf konfiguriert. Andernfalls gibt das Programm einen Fehler aus und wird beendet. Alternativ erhalten Sie durch Steuern der dritten Zeile der Protokollebene INFO oder DEBUG, ERROR oder WARN von logger.conf Protokollausgabeinformationen für verschiedene Verbate.
Bei diesbezüglichen Fragen und anderen nicht abgedeckten Angelegenheiten wenden Sie sich bitte an [email protected]. Genießen Sie es.
