Nグラム

Nグラムを取り出すC++のクラスを作成したのでメモ。
UTF-8のみ対応。

/*
 * ファイル名: ngram.hh
 */
#ifndef TOKENIZER_NGRAM_HH
#define TOKENIZER_NGRAM_HH

#include <algorithm>
#include <vector>
#include <cstring>

namespace Tokenizer {
  class Ngram {
  public:
    Ngram(unsigned min, unsigned max) 
      : min(std::max(min, 1u)), max(std::min(max, 32u)) {}
    
    template<class Callback>
    void each_token(const char* text, Callback& fn) const {
      std::vector<unsigned> char_start_pos;
      const unsigned len = strlen(text);

      for(unsigned i=0; i < len; i++) {
        if(!(text[i]&0x80))
          char_start_pos.push_back(i); // ascii
        else if (text[i]&0x40)
          char_start_pos.push_back(i); // start of a UTF-8 character byte sequence
      }
      char_start_pos.push_back(len);
      
      for(unsigned i=0; i < char_start_pos.size(); i++) 
        for(unsigned n=min; n <= max; n++) 
          if(i+n < char_start_pos.size())
            fn(text+char_start_pos[i], text+char_start_pos[i+n]);
    }
    
  private:
    const unsigned min;
    const unsigned max;
  };
}

#endif

使用例:

/*
 * ファイル名: ngram.cc
 */
#include <string>
#include <iostream>
#include <cstdlib>
#include "ngram.hh"

void print_ngram(const char* beg, const char* end) {
  std::cout << std::string(beg,end) << std::endl;
};

int main(int argc, char** argv) {
  if(argc != 3) {
    std::cerr << "Usage: ngram <min> <max>" << std::endl;
    return 1;
  }

  Tokenizer::Ngram ngram(atoi(argv[1]), atoi(argv[2]));
  std::string line;
  while(std::getline(std::cin, line)) 
    ngram.each_token(line.c_str(), print_ngram);
  return 0;
}

実行例:

$ g++ -o ngram ngram.cc

$ echo '「そりゃまたなぜです」' | ./ngram 1 3
「
「そ
「そり
そ
そり
そりゃ
り
りゃ
りゃま
ゃ
ゃま
ゃまた
ま
また
またな
た
たな
たなぜ
な
なぜ
なぜで
ぜ
ぜで
ぜです
で
です
です」
す
す」
」

$ echo '「そりゃまたなぜです」' | ./ngram 4 9
「そりゃ
「そりゃま
「そりゃまた
「そりゃまたな
「そりゃまたなぜ
「そりゃまたなぜで
そりゃま
そりゃまた
そりゃまたな
そりゃまたなぜ
そりゃまたなぜで
そりゃまたなぜです
りゃまた
りゃまたな
りゃまたなぜ
りゃまたなぜで
りゃまたなぜです
りゃまたなぜです」
ゃまたな
ゃまたなぜ
ゃまたなぜで
ゃまたなぜです
ゃまたなぜです」
またなぜ
またなぜで
またなぜです
またなぜです」
たなぜで
たなぜです
たなぜです」
なぜです
なぜです」
ぜです」