Tokenizer per full-text

Question

Questo dovrebbe essere un caso ideale per non reinventare la ruota, ma finora la mia ricerca è stata vana.

Invece di scriverne uno, vorrei utilizzare un tokenizer C++ esistente. I token devono essere utilizzati in un indice per la ricerca di testo completo. Le prestazioni sono molto importanti, analizzerò molti gigabyte di testo.

Modifica: notare che i token devono essere utilizzati in un indice di ricerca. La creazione di tali token non è una scienza esatta (afaik) e richiede alcune euristiche. Questo è stato fatto migliaia di volte prima e probabilmente in mille modi diversi, ma non riesco nemmeno a trovarne uno :)

Qualsiasi buon suggerimento?

Grazie!

Answer 1

Ho scritto il mio tokenizer come parte del motore di ricerca e indicizzazione open source .

C'è anche il ICU tokenizer che gestisce Unicode.

Answer 2

Se le prestazioni sono un problema principale, probabilmente si dovrebbe attenersi al buon vecchio strtok che è sicuro di essere veloce:

/* 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

potrei guardare in std::stringstream da <sstream>. Lo stile C strtok ha un numero di problemi di usabilità e le stringhe in stile C sono solo fastidiose.

Ecco un esempio ultra-banale di esso creazione di token una frase in parole:

#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 classe std::stringstream è "bidirezionale", nel senso che supporta input e output. Probabilmente vorrai fare solo uno o l'altro, quindi useresti std::istringstream o std::ostringstream.

La bellezza di loro è che essi sono anche std::istream e std::ostream s, rispettivamente, in modo da poterli usare come usereste std::cin o std::cout, che sono si spera familiare.

Alcuni potrebbero sostenere che queste classi sono costose da utilizzare; std::strstream da <strstream> è per lo più la stessa cosa, ma costruita su corde meno costose con terminazione a 0 in stile C. Potrebbe essere più veloce per te. Ma comunque, non mi preoccuperei delle prestazioni subito. Ottieni qualcosa di funzionante, quindi confrontalo. È possibile ottenere una velocità sufficiente semplicemente scrivendo un C++ ben scritto che riduce al minimo la creazione e la distruzione di oggetti non necessari. Se non è ancora abbastanza veloce, puoi guardare altrove. Queste classi sono probabilmente abbastanza veloci, però. La tua CPU può sprecare migliaia di cicli nella quantità di tempo necessaria per leggere un blocco di dati da un disco rigido o da una rete.

Answer 4

È possibile utilizzare Ragel State Machine Compiler per creare un tokenizer (o un analizzatore lessicale).

Il codice generato non ha dipendenze esterne.

Suggerisco di guardare l'esempio clang.rl per un esempio pertinente della sintassi e dell'utilizzo.

Answer 5

Beh, comincerei con la ricerca Boost e ... hop: Boost.Tokenizer

La cosa bella? Di default si rompe su spazi bianchi e punteggiatura perché è pensato per il testo, quindi non dimenticherete un simbolo.

Dall'introduzione:

#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 

e ci sono funzioni aggiuntive:

• può sfuggire caratteri
• è compatibile con Iterators in modo da poter utilizzare con un istream direttamente .. e quindi con un ifstream

e alcune opzioni (come tenere gettoni vuoti ecc ...)

Check it out!

Answer 6

Una libreria di espressioni regolari potrebbe funzionare bene se i token non sono troppo difficili da analizzare.

Answer 7

Il C++ String Toolkit Library (StrTk) ha la seguente soluzione al vostro 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; 
} 

Più esempi si possono trovare Here