UNF : Unicode正規化ライブラリ

UNFという名前*1で、C++Unicode正規化を行うライブラリを実装 (ver 0.0.1)
ついでに、それを利用したRuby拡張ライブラリも作成。

C++Rubyで使える、軽くて高速なUnicode正規化ライブラリは、一年以上前から欲しい(作りたい)と思っていたので、作り終えてみると少し人心地ついた感じがする。

特徴(?)

  • NFD,NFC,NFKD,NFKC
  • Unicode 5.2.0に準拠
    • まだバグが残っている可能性はあるが正規化テストはパスしているので、それほど致命的なものはないと思われる*2
  • UTF-8にのみ対応
    • 中間的にUnicodeのコードポイントへの変換を経由せずに、UTF-8文字列を直接操作しているため
    • その内他のエンコーディングにも対応するかもしれない
  • 正規化に用いる変換テーブルおよび各種文字属性はDoubleArray(Trie)を使って保持
    • DoubleArrayの配列データは、C++のヘッダファイル(unf/table.hh)に書き出し保存
    • コンパイル後のデータサイズ(= 配列サイズの合計)は570KB程度
  • ヘッダファイルライブラリ
    • 上記のDoubleArrayデータ用のヘッダを除けば、全部で540行くらい
  • C++ANSI標準準拠(多分...)
  • 割合高速
    • 以下に計時結果

計時

他のUnicode正規化ライブラリなどと処理速度を比較。
参考までに。


対象テキスト:
正規化対象テキストにはhamの時にも用いた青空文庫の作家別書籍とYahoo!ブログのカテゴリ別ブログ記事を使用。
※ 以下で使われているrubyスクリプトに関しては、上のリンク先を参照

# 青空文庫から夏目漱石の作品を取得
$ ruby -Ku download.rb http://www.aozora.gr.jp/index_pages/person148.html souseki
$ ls souseki/ | wc -l
88
$ cat souseki/* > souseki.txt
$ head -2 /tmp/souseki.txt 

 公園の片隅に通りがかりの人を相手に演説をしている者がある。向うから来た釜形の尖った帽子を被ずいて古ぼけた外套を猫背に着た爺さんがそこへ歩みを佇めて演説者を見る。演説者はぴたりと演説をやめてつかつかとこの村夫子のたたずめる前に出て来る。二人の視線がひたと行き当る。演説者は濁りたる田舎調子にて御前はカーライルじゃないかと問う。いかにもわしはカーライルじゃと村夫子が答える。チェルシーの哲人と人が言囃すのは御前の事かと問う。なるほど世間ではわしの事をチェルシーの哲人と云うようじゃ。セージと云うは鳥の名だに、人間のセージとは珍らしいなと演説者はからからと笑う。村夫子はなるほど猫も杓子も同じ人間じゃのにことさらに哲人などと異名をつけるのは、あれは鳥じゃと渾名すると同じようなものだのう。人間はやはり当り前の人間で善かりそうなものだのに。と答えてこれもからからと笑う。
$ ls -lh souseki.txt
-rw-r--r-- 1 user user 9.3M 2010-08-20 19:34 souseki.txt

# Yahoo!ブログから"ビジネスと経済"カテゴリに属する記事を取得
$ mkdir keizai
$ ruby -Ku download_yahoo_blog.rb ビジネスと経済 keizai
$ ls keizai/ | wc -l
2331
$ cat keizai/* > keizai.txt
$ head keizai.txt 
ブログ素材−わ〜い♪その2♪−顔文字

お持ち帰りはコメント等をよろしくお願いいたします♪ミ★(*^▽゚)v
直リンクではなくPCに落としてお使いくださいませ♪( *^艸^)
トラブルを避ける為、二次配布はお断りいたします♪(*_ _)ペコリ
使用は転載元よりお願いいたします♪
n.e.oプレミアムジンジャーエール…♪
皆さま♪ハロハロ〜♪
 
暑さ…ハンパじゃないですね〜〜〜♪(;´▽`A``
$ ls -lh keizai.txt 
-rw-r--r-- 1 user user 3.3M 2010-08-20 19:41 keizai.txt


計時結果:
上述のファイルの各行*3に対して、正規化を施し、終了までの時間を計測した結果。
計時に用いたプログラムは、末尾に掲載。

java.text.Normalizerはコンスタントに良好な結果を出している*4
unfは全体的にそれよりは劣っているが悪くもなく、keizei.txtのNFKCに関して云えば、この中で最速となっている。
unf-rubyC++のchar*型からRubyのString型に変換するコストが掛かるためか、いずれもunfの結果に0.07〜0.10秒を足したくらいの処理時間となっている。

計時用プログラムと実行例

計時に用いた各プログラムとその実行例。

unf-0.0.1:

$ g++ -v
gcc version 4.4.3 (Ubuntu 4.4.3-4ubuntu5)

$ tar zxvf unf-0.0.1.tar.gz
$ cd unf-0.0.1
$ make
$ bin/unf-time < souseki.txt
= read: 
  == 33072 lines
  == average(line length): 293 byte
= time: 
  == NFD :  0.157628 sec
  == NFC :  0.089492 sec
  == NFKD:  0.16303 sec
  == NFKC:  0.091775 sec
DONE

unf-ruby-0.0.1:

$ ruby -v
ruby 1.8.7 (2010-01-10 patchlevel 249) [i486-linux]

$ tar zxvf unf-ruby-0.0.1.tar.gz
$ cd unf-ruby-0.0.1
$ ruby extconf.rb
$ make
$ sudo make install
$ ruby unf-time.rb souseki.txt  # unf-time.rbの中身は後述
nfd:	0.224087 sec
nfc:	0.153629 sec
nfkd:	0.237982 sec
nfkc:	0.157734 sec
>||
>|ruby|
# ファイル名: unf-time.rb
$KCODE='u'

require 'unf'

Norm = UNF::Normalizer.new

def norm_time(text, form)
  beg = Time.now
  text.each{|line|
    Norm.normalize(line,form)
  }
  puts "#{form}:\t#{Time.now-beg} sec"
end

text = open(ARGV[0]).read

norm_time(text,:nfd)
norm_time(text,:nfc)
norm_time(text,:nfkd)
norm_time(text,:nfkc)

java.text.Normalizer:

$ java -version
java version "1.6.0_18"
OpenJDK Runtime Environment (IcedTea6 1.8.1) (6b18-1.8.1-0ubuntu1)
OpenJDK Server VM (build 16.0-b13, mixed mode)

$ javac -g:none Normalize.java  # Normalize.javaの中身は後述
$ java -server Normalize < souseki.txt 
NFD:	0.067 sec 
NFC:	0.043 sec 
NFKD:	0.068 sec 
NFKC:	0.073 sec 
// ファイル名: Normalize.java
import java.text.Normalizer;
import java.text.Normalizer.Form;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Normalize {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<String> lines = new ArrayList<String>();

        for(String line=br.readLine(); line!=null; line=br.readLine())
            lines.add(line);
        
        for(int i=0; i < 10; i++) {
            normalizeTime(lines, Normalizer.Form.NFC, false);   
            normalizeTime(lines, Normalizer.Form.NFD, false);
            normalizeTime(lines, Normalizer.Form.NFKC, false);
            normalizeTime(lines, Normalizer.Form.NFKD, false);  
        }

        normalizeTime(lines, Normalizer.Form.NFD, true);
        normalizeTime(lines, Normalizer.Form.NFC, true);
        normalizeTime(lines, Normalizer.Form.NFKD, true);
        normalizeTime(lines, Normalizer.Form.NFKC, true);
    }
    
    private static void normalizeTime(ArrayList<String> lines, Normalizer.Form form, boolean print) {
        long beg_t = System.currentTimeMillis();
        for(String line : lines)
            Normalizer.normalize(line, form).length();
        long end_t = System.currentTimeMillis();

        if(print)
            System.out.println(form+":\t"+(end_t-beg_t)/1000d+" sec ");
    }
}

Ruby-GLib2:

$ sudo apt-get install libglib2-ruby
$ ruby glib2-time.rb souseki.txt  # glib2-time.rbの中身は後述
nfd:	0.791289 sec
nfc:	1.055483 sec
nfkd:	0.777088 sec
nfkc:	1.028141 sec
# ファイル名: glib2-time.rb
$KCODE='u'

require 'glib2'

def norm_time(text, form, name)
  beg = Time.now
  text.each{|line|
    GLib::UTF8.normalize(line, form)
  }
  puts "#{name}:\t#{Time.now-beg} sec"
end

text = open(ARGV[0]).read

norm_time(text, GLib::NormalizeMode::NFD, :nfd)
norm_time(text, GLib::NormalizeMode::NFC, :nfc)
norm_time(text, GLib::NormalizeMode::NFKD, :nfkd)
norm_time(text, GLib::NormalizeMode::NFKC, :nfkc)

senna-nfkc:
sennaで使われているnfkc。
デフォルトでは、独自に拡張した正規化処理を行うようなので、それを抑止してコンパイル
使い方がいまいち分かっていないので不適切な可能性がある...。

$ sudo apt-get install libicu-dev  # sennaがnfkc.c(NFKC正規化用ソースファイル)を自動生成するのに必要

$ tar zxvf senna-1.1.5.tar.gz 
$ cd senna-1.1.5
$ cd util/unicode
$ ruby nfkc.rb -s -c   # 独自拡張を抑止して、NFKC正規化用ソースファイルを生成
$ cp nfkc.c ../../lib/
$ cd ../../

$ ./configure
$ make
$ g++ -O2 -o senna-nfkc-time senna-nfkc-time.cc lib/*.o `mecab-config --libs`  # senna-nfkc-time.ccの中身は後述
$ ./senna-nfkc-time < souseki.txt
Elapsed: 0.18836 sec
// ファイル名: senna-nfkc-time.cc

// 以下、型が定義されていないというエラーが出たので、それらしいものを自前で定義
typedef unsigned size_t;
typedef unsigned uint_least8_t;
typedef short int16_t;
typedef long long int64_t;

#include "config.h"
#include "senna.h"
#include "lib/str.h"
#include <iostream>
#include <string>
#include <vector>
#include <cstring>

#include <sys/time.h>

inline double gettime(){
  timeval tv;
  gettimeofday(&tv,NULL);
  return static_cast<double>(tv.tv_sec)+static_cast<double>(tv.tv_usec)/1000000.0;
}

int main(int argc, char** argv) {
  std::string line;
  std::vector<std::string> lines; 
  while(std::getline(std::cin, line))
    lines.push_back(line);

  double beg_t = gettime();
  for(unsigned i=0; i < lines.size(); i++)
    sen_nstr* psn = sen_nstr_open(lines[i].data(), lines[i].size(), sen_enc_utf8, 0);
  std::cerr << "Elapsed: " << gettime()-beg_t << " sec" << std::endl;
  return 0;
}

*1:Unicode Normalization Formsの略

*2:実装を一通り終え、このテストにはパスした段階で、大量テキストに対してJavaUnicode正規化メソッドを適用した結果と比べてみたところ、数は多くないが相違点(バグ)がいくつか見つかったので、NormalizationTest.txt内のテストを網羅するだけでは、完全ではないよう

*3:IOの影響を除外するために、全ての行はあらかじめメモリ上に読み込んでおく

*4:ちなみに、java.text.Normalizerは何故かNFKCの場合だけ、テキストサイズが大きくなると性能が顕著に劣化していた。例えば、10MB程度のテキストを投げると、結果が返ってこない感じとなる