Tokenizer for full-text

Question

Это должен быть идеальный случай, когда вы не изобретаете колесо, но до сих пор мои поиски были напрасны.

Вместо того, чтобы писать сам, я хотел бы использовать существующий токенизатор C++. Токены должны использоваться в индексе полнотекстового поиска. Производительность очень важна, я буду разбирать много гигабайт текста.

Редактировать: Обратите внимание, что маркеры должны использоваться в индексе поиска. Создание таких токенов не является точной наукой (afaik) и требует некоторой эвристики. Это было сделано тысячу раз раньше и, вероятно, тысячами разных способов, но я не могу найти ни одного из них :)

Любые хорошие указатели?

Спасибо!

Answer 1

Я написал свой собственный токенизатор как часть открытого индекса SWISH++ индексации и поиска.

Существует также ICU tokenizer , который обрабатывает Unicode.

Answer 2

Если производительность является основной проблемой, вы должны, вероятно, придерживаться старой доброй strtok который обязательно должен быть быстрым:

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

я мог смотреть в std::stringstream от <sstream>. C-style strtok имеет ряд проблем с удобством использования, а строки в стиле C просто хлопотны.

Вот ультра-тривиальный пример его tokenizing фразы слов:

#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: 

std::stringstream класс «двунаправленный», в том, что он поддерживает ввод и вывод. Вы, вероятно, захотите сделать только один или другой, так что вы бы использовали std::istringstream или std::ostringstream.

Красота из них является то, что они также являются std::istream и std::ostream s соответственно, так что вы можете использовать их, как вы будете использовать std::cin или std::cout, которые являются надеюсь, вам знакомы.

Некоторые могут утверждать, что эти классы дороги в использовании; std::strstream от <strstream> - это в основном то же самое, но построено на вершине более дешевых строк с 0-концевыми строками C-стиля. Это может быть быстрее для вас. Но в любом случае, я бы не стал беспокоиться о производительности сразу. Получите что-то работающее, а затем сравните его. Скорее всего, вы можете получить достаточную скорость, просто написав хорошо написанный C++, который минимизирует ненужное создание и уничтожение объектов. Если это еще не достаточно быстро, вы можете посмотреть в другом месте. Тем не менее, эти классы, вероятно, достаточно быстры. Ваш процессор может тратить тысячи циклов на время, затрачиваемое на чтение блока данных с жесткого диска или сети.

Answer 4

Вы можете использовать Ragel State Machine Compiler для создания токенизатора (или лексического анализатора).

Сгенерированный код не имеет внешних зависимостей.

Предлагаю вам ознакомиться с образцом clang.rl для соответствующего примера синтаксиса и использования.

Answer 5

Ну, я хотел бы начать с поиска подталкивание и ... хоп: Boost.Tokenizer

Хорошая вещь? По умолчанию он разбивается на пробелы и пунктуацию, потому что он предназначен для текста, поэтому вы не забудете символ.

Из введения:

#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 

И есть дополнительные возможности:

• он может бежать символы
• он совместим с Iterators так что вы можете использовать его с istream непосредственно .. и, таким образом, с использованием ifstream

и несколько вариантов (например, сохранение пустых токенов и т. Д.)

Проверьте это!

Answer 6

Библиотека регулярных выражений может работать хорошо, если ваши токены не слишком сложны для синтаксического анализа.

Answer 7

C++ String Toolkit Library (StrTk) имеет следующее решение проблемы:

#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; 
} 

Больше примеров можно найти Here