Токенизатор для полнотекстового

Question

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

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

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

Есть хорошие указатели?

Спасибо!

Answer 1

Библиотека C ++ String Toolkit (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;
}

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

Answer 2

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

Answer 3

Если производительность является основной проблемой, вы, вероятно, должны придерживаться старого доброго 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 4

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

Существует также токенизатор ICU это обрабатывает Unicode.

Answer 5

Ну, я бы начал с поиска Boost и ... hop: 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

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

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

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

Answer 7

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

Вот ультра-тривиальный пример того, как это предложение разбивается на слова:

#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 ++, который сводит к минимуму ненужное создание и уничтожение объектов. Если это все еще не достаточно быстро, то вы можете посмотреть в другом месте. Эти классы, вероятно, достаточно быстрые. Ваш процессор может тратить тысячи циклов на количество времени, которое требуется для чтения блока данных с жесткого диска или сети.