orchid fst

Orquídea-Fst

1. Visão geral do projeto

Este projeto Orchid-Fst implementa uma estrutura de dados de pesquisa de dicionário de string de texto rápida: Transdutor de estado finito, que é a abreviação de FST na linguagem C++. Orchid-FST requer suporte C++ 11 (é melhor compilar com GCC 7 ou superior) e atualmente suporta compilação e execução em sistemas semelhantes a UNIX.

A estrutura de dados Fst tem sido amplamente utilizada em mecanismos de pesquisa de código aberto: Elasticsearch e Lucene core source. É tão rápido para pesquisar strings de texto que pode ser entendido como um mapa de valores-chave ou uma estrutura de dados definida. A complexidade do tempo de consulta na estrutura de dados FST é O(n), onde n é o comprimento da string de texto real com a consulta, independente do tamanho do conjunto massivo de dados de texto. Esta é uma vantagem muito importante e enorme.

Este projeto de código aberto FST C++ Orchid-Fst tem as seguintes vantagens significativas:

1. O processo de construção do FST neste projeto pode realizar o despejo no fluxo de saída (como um arquivo externo) para dados do FST que acabaram de ser construídos durante a construção do FST para reduzir a ocupação de memória. Este ponto é especialmente importante para dados de dicionário com grande regularidade. Porque o dict não pode ser carregado na memória de uma só vez para construir o FST. O arquivo de dados FST é então usado como mapa de memória. Muitas implementações atuais de FST de código aberto não possuem esse recurso. Este é um dos destaques importantes do projeto.

2. Ele é implementado na linguagem C++ e pode ser muito útil se o seu projeto for apenas um ambiente de desenvolvimento C++. Existem algumas versões de implementos de código aberto fst, mas raramente são bem implementados na linguagem C/C++ como um código de alta qualidade, portanto, você pode integrá-lo facilmente em seus projetos de desenvolvimento C++. Como sabemos, foi implementado em Rust e Java.

3. Ele resolveu com sucesso a string de texto do código UTF8 e resolveu mais bugs graves quando a string de texto não contém caracteres em inglês, como caracteres chineses e assim por diante. Ele usou uma abordagem muito mais inteligente para resolver strings de texto com codificação UTF8.

4. Este projeto apresenta um grande número de exemplos de implementações de autômatos, a partir dos quais você pode aprender mais sobre implementações de autômatos para diversos propósitos, sejam eles executados em estruturas de dados FST ou usados ​​em outros cenários. As muitas estruturas de dados de autômatos nesta demonstração de projeto incluem, mas não estão limitadas a: GreaterThan,LessThan,Prefix,Str,StartsWith,Intersection,Union,Not,Levenshtein Automaton, Damerau Levenshtein Automation e assim por diante.

5. Ele não apenas implementa uma interface de código, mas também implementa cuidadosamente uma ferramenta de linha de comando fácil de usar, que é o orchid-fst: ofst , com instruções detalhadas sobre como usar parâmetros. A ferramenta de linha de comando ofst possui as seguintes funções.

   ofst map/set pode construir um arquivo fst a partir de seu arquivo de dicionário de entrada, que obteve chave e valor de cada linha separada por vírgula quando map subcomando, e apenas leu o primeiro item antes da primeira vírgula como chave quando set subcomando; ofst dot pode gerar um arquivo de ponto a partir do arquivo fst, que pode gerar um arquivo de imagem, como um arquivo png para ver a estrutura fst pelo comando dot, como:

   'ponto -Tpng < xx.dot > xx.png' .

   Outro ponto importante é: você pode ver detalhes em fst para cada caractere chinês! Isso é emocionante.

   Os subcomandos match/prefix/range/fuzzy executam pesquisas diferentes em fst. Você pode obter instruções de uso mais detalhadas usando 'ofst --help' ou 'ofst map --help' ou 'ofst fuzzy --help'. Você pode tentar!

    ,10000
   中国,100
   中国人,50
   中国人民,40
   中国心,10
   北七,3
   北七家,10
   北京,5
   北平,2
   

   A imagem acima mostra um efeito de imagem PNG simples gerado pelo subcomando ofst dot da ferramenta de linha de comando do projeto , ofst com os dados de texto de dicionário simples mostrados acima. Ele pode exibir claramente a estrutura de caracteres codificados de vários bytes, como caracteres chineses. Uma coisa importante a notar é que o nó 17 na figura representa o primeiro byte comum de '京' e '七'. Este é um dos bugs comuns em muitas outras implementações de FST de código aberto, e este projeto resolve o problema perfeitamente.

6. Este projeto fst implementa LRUcache e LFUcache, que são usados ​​na construção da estrutura de dados fst. Para evitar o uso excessivo de memória, o lruCache desempenha um bom papel de compensação no processo de construção do FST.

   LruCache pode construir uma árvore FST mínima aproximada para você, para obter o efeito de espaço mínimo aproximado. Se o espaço de memória for suficiente, recomenda-se que a capacidade de cache disponível do lruCache seja definida como a maior possível ao construir o FST. Desta forma, o FST é construído o menor possível porque o espaço é economizado tanto quanto possível.

7. Considerando que a construção de arquivos de dicionário do FST sempre requer que a entrada seja ordenada lexicograficamente, este projeto implementa um bom módulo de função de classificação externa de arquivos grandes e também implementa uma ferramenta de linha de comando fácil de usar, lfsort, para classificar os arquivos grandes. arquivo de texto separadamente. Obviamente, a ferramenta de linha de comando FST já possui uma classificação de arquivos grandes integrada e, por padrão, ela insere arquivos de texto grandes que não estão classificados. A classificação de arquivos grandes também consome tempo. Se seus arquivos de dicionário de entrada já estiverem classificados, você poderá exibir os argumentos '-s' ou '--sorted' especificados para evitar a classificação de arquivos grandes antes de construir o FST. Você pode inserir 'lfsort --help' para ver instruções detalhadas para a ferramenta de linha de comando de classificação de arquivos 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!

Sobre este projeto, faça login para imprimir o componente tulipa - log pode ser encontrado na versão de código aberto do autor de outro projeto: https://github.com/apollo008/tulip-log. Uma das premissas básicas envolvidas no uso das ferramentas de linha de comando do projeto, ofst e lfsort , é a necessidade de configurar um arquivo de definição para o log do tuliop no diretório atual. É comumente chamado de logger.conf. Também está incluído neste projeto o rico uso em C++ do módulo CppUnit de teste de unidade para garantir a qualidade da função do código. misc/config/logger.conf é um exemplo de arquivo de configuração para Tulip Log: logger.conf.

Os detalhes do processo de implementação dos autômatos de Levenshtein e dos autômatos de Damerau Levenshtein são na verdade bastante complexos, este tópico não é o foco deste projeto, embora o código-fonte deste projeto contenha completamente a implementação inteligente e eficiente da consulta difusa de Levenshtein e Dameau Levenshtein. Acredito que será útil para você entender o algoritmo de consulta difusa da medida de distância de edição de Levenshtein e Damerau Leveshtein. Sobre o uso de autômatos Levenshtein ou Damerau Levenshtein para consultar rapidamente strings semelhantes em mecanismos de pesquisa, os leitores interessados ​​​​podem ler outro artigo do autor:<搜索引擎中相似字符串查找那些事儿> https://mp.weixin.qq.com/s/0ODgrWSVdRnYZxGRGmEdsA.

Por fim, a eficiência do algoritmo desta implementação é teoricamente muito eficiente, incluindo o processo de construção do FST e consulta do FST. Dados de teste de desempenho mais detalhados serão adicionados nas versões seguintes.

2. Compilação e instalação do projeto

Este projeto Orchid-Fst atualmente suporta compilação e instalação em um ambiente semelhante ao UNIX. Ele depende das seguintes bibliotecas de terceiros:

• unidade de cpp
• registro de tulipa

Antes de compilar e instalar o projeto Orchid-Fst, você deve primeiro instalar as duas bibliotecas dependentes acima, uma biblioteca de log de autopesquisa Tulip-Log, uma biblioteca de teste de unidade CppUnit, que estão no diretório de compartilhamento e podem ser compiladas antecipadamente.

Nota: No Ubuntu Linux, você deve instalar o zlib pelo comando: 'sudo apt install zlib1g-dev' antes de instalar este projeto. Tanto no Ubuntu quanto no Centos Linux, é melhor usar a versão gcc7/g++7 ou 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

Agora o executável lfsort e ofst será gerado em < /path/to/install >/bin; e o arquivo .so correspondente estará no diretório lib. executar o comando 'ofst --help' ou 'lfsort --help' fará com que você se familiarize com seu uso.

Nota: Antes de executar a ferramenta de linha de comando, é necessário colocar o arquivo de configuração de log logger.conf no diretório atual. Um exemplo desta configuração está acima ou você pode obter o arquivo logger.conf de exemplo em misc/config/logger.conf do projeto. Além disso, não se esqueça de criar logs no caminho atual do programa conforme configurado em logger.conf. Caso contrário, o programa executará um erro e será encerrado. Alternativamente, controlar a terceira linha do nível de log logger.conf INFO ou DEBUG, ERROR ou WARN fornecerá informações de saída de log para diferentes verbos.

Entre em contato com [email protected] para perguntas relacionadas e outros assuntos não abordados. Apreciá-lo.