Tokenizador para texto completo

Question

Este debería ser un caso ideal para no reinventar la rueda, pero hasta ahora mi búsqueda ha sido en vano.

En lugar de escribir uno yo mismo, me gustaría utilizar un tokenizador de C++ existente. Los tokens se deben usar en un índice para la búsqueda de texto completo. El rendimiento es muy importante, analizaré muchos gigabytes de texto.

Editar: Tenga en cuenta que los tokens se deben utilizar en un índice de búsqueda. Crear dichos tokens no es una ciencia exacta (afaik) y requiere algo de heurística. Esto se ha hecho miles de veces antes, y probablemente de mil maneras diferentes, pero ni siquiera puedo encontrar uno de ellos :)

¿Alguna buena puntería?

Gracias!

Answer 1

Escribí mi propio tokenizer como parte del motor de indexación y búsqueda de código abierto SWISH++.

También está el ICU tokenizer que maneja Unicode.

Answer 2

Si el rendimiento es una cuestión principal que probablemente debe pegarse a la vieja strtok que es seguro para ser rápido:

/* strtok example */ 
#include <stdio.h> 
#include <string.h> 

int main() 
{ 
    char str[] ="- This, a sample string."; 
    char * pch; 
    printf ("Splitting string \"%s\" into tokens:\n",str); 
    pch = strtok (str," ,.-"); 
    while (pch != NULL) 
    { 
    printf ("%s\n",pch); 
    pch = strtok (NULL, " ,.-"); 
    } 
    return 0; 
} 

Answer 3

podría mirar en std::stringstream de <sstream>. C-style strtok tiene una serie de problemas de usabilidad, y las cadenas tipo C son problemáticas.

Aquí está un ejemplo ultra-trivial de ella tokenizar una oración en palabras:

#include <sstream> 
#include <iostream> 
#include <string> 

int main(void) 
{ 
    std::stringstream sentence("This is a sentence with a bunch of words"); 
    while (sentence) 
    { 
     std::string word; 
     sentence >> word; 
     std::cout << "Got token: " << word << std::endl; 
    } 
} 

janks@phoenix:/tmp$ g++ tokenize.cc && ./a.out 
Got token: This 
Got token: is 
Got token: a 
Got token: sentence 
Got token: with 
Got token: a 
Got token: bunch 
Got token: of 
Got token: words 
Got token: 

La clase std::stringstream es "bi-direccional", en que se apoya la entrada y la salida. Probablemente quieras hacer solo una o la otra, entonces usarías std::istringstream o std::ostringstream.

La belleza de ellas es que también son std::istream y std::ostream s, respectivamente, para que pueda utilizarlos como que tendría que utilizar std::cin o std::cout, que son de esperar familiar.

Algunos podrían argumentar que estas clases son caras de usar; std::strstream desde <strstream> es más o menos lo mismo, pero está construido sobre cadenas más baratas con terminación en C estilo 0. Puede ser más rápido para ti. Pero de todos modos, no me preocuparía el rendimiento de inmediato. Consigue algo que funcione y luego haz una evaluación comparativa. Lo más probable es que pueda obtener suficiente velocidad simplemente escribiendo C++ bien escrito que minimice la creación y destrucción de objetos innecesarios. Si todavía no es lo suficientemente rápido, entonces puedes buscar en otro lado. Sin embargo, estas clases son probablemente lo suficientemente rápidas. Su CPU puede perder miles de ciclos en la cantidad de tiempo que lleva leer un bloque de datos de un disco duro o red.

Answer 4

Puede usar el Ragel State Machine Compiler para crear un tokenizador (o un analizador léxico).

El código generado no tiene dependencias externas.

Le sugiero que mire la muestra clang.rl para obtener un ejemplo relevante de la sintaxis y el uso.

Answer 5

Bueno, me gustaría empezar por buscar Boost y ... hop: Boost.Tokenizer

Lo bueno? De forma predeterminada, se rompe en los espacios en blanco y la puntuación, ya que es para texto, por lo que no se olvidará un símbolo.

de la introducción:

#include<iostream> 
#include<boost/tokenizer.hpp> 
#include<string> 

int main(){ 
    using namespace std; 
    using namespace boost; 
    string s = "This is, a test"; 
    tokenizer<> tok(s); 
    for(tokenizer<>::iterator beg=tok.begin(); beg!=tok.end();++beg){ 
     cout << *beg << "\n"; 
    } 
} 

// prints 
This 
is 
a 
test 

// notes how the ',' and ' ' were nicely removed 

y hay características adicionales:

• puede escapar caracteres
• es compatible con Iterators para que pueda usarlo con un istream directamente .. .y así con un ifstream

y algunas opciones (como conservar tokens vacíos, etc.)

¡Échale un vistazo!

Answer 6

Una biblioteca de expresiones regulares puede funcionar bien si sus tokens no son demasiado difíciles de analizar.

Answer 7

El C++ String Toolkit Library (StrTk) tiene la siguiente solución a su problema:

#include <iostream> 
#include <string> 
#include <deque> 
#include "strtk.hpp" 

int main() 
{ 
    std::deque<std::string> word_list; 
    strtk::for_each_line("data.txt", 
         [&word_list](const std::string& line) 
         { 
          const std::string delimiters = "\t\r\n ,,.;:'\"" 
                  "!@#$%^&*_-=+`~/\\" 
                  "()[]{}<>"; 
          strtk::parse(line,delimiters,word_list); 
         }); 

    std::cout << strtk::join(" ",word_list) << std::endl; 

    return 0; 
} 

Más ejemplos se pueden encontrar Here