UNF-0.0.4: サイズ削減
今日は久しぶりにUNF(ユニコード正規化ライブラリ)に手を加えていた。
大きな変更点は、正規化用変換テーブルを実現していたTRIEをDAWGにしたこと。
もともとは正規分解と互換分解用に、内容がほぼ等しいTRIEを別々に持っていたので、それを一つDAWGにして共有することでだいぶサイズが節約できた。
# unf-0.0.3 $ ls -lh unf-0.0.3/bin/unf -rwxrwxr-x 1 user user 596K 2011-11-19 17:54 unf-0.0.3/bin/unf # 596KB # unf-0.0.4 $ ls -lh unf-0.0.4/bin/unf -rwxrwxr-x 1 user user 411K 2011-11-19 20:20 unf-0.0.4/bin/unf # 411KB
処理速度も、ごく僅かだけど新しいバージョンの方が速くなっているように見える。
# 17MBのテキストデータの正規化時間 # unf-0.0.3 $ unf-0.0.3/bin/unf-time < 17MB.txt = read: == 172090 lines == average(line length): 99 byte = time: == NFD : 0.203354 sec == NFC : 0.109814 sec == NFKD: 0.215196 sec == NFKC: 0.137385 sec DONE # unf-0.0.4 $ unf-0.0.4/bin/unf-time < 17MB.txt = read: == 172090 lines == average(line length): 99 byte = time: == NFD : 0.199866 sec == NFC : 0.104912 sec == NFKD: 0.206675 sec == NFKC: 0.137277 sec DONE
Sanmoku(0.0.4): 辞書データサイズ縮小
この一週間でSanmokuの辞書データサイズの縮小をいろいろ試していたので、その結果を載せておく。
現時点でのバージョンは 0.0.4。
やったこと
試した主なこと。
| データ | 内容 | サイズ (Gomoku-0.0.4 => Sanmoku-0.0.4) |
|---|---|---|
| 連接コストデータ (matrix.bin) |
類似品詞の連接コストを併合*1 + コスト値を14bitで保持 | 3.5MB => 2.2MB |
| 形態素辞書引きインデックス (surface-id.bin) |
2バイト文字(UTF-16)DAWGから、1バイト文字(UTF-8)DAWGに変更。 かつIPADICに合わせてノードレイアウトを最適化 |
2.7MB => 1.5MB |
| 形態素データ (morpheme.bin,id-morphems-map.bin) |
4バイト(品詞情報:2バイト、単語コスト:2バイト)から2バイトに | 1.8MB => 1.0MB |
比較
IgoとGomokuとSanmokuの比較。
| 辞書データサイズ(IPADIC) | 最小所要メモリ(-Xmx) | 起動(≒辞書ロード)時間*2 | 10MBテキストの解析時間 | |
|---|---|---|---|---|
| Igo-0.4.3 | 40MB | 73MB | 0.058秒 | 2.729秒 |
| Gomoku-0.0.4 | 8.2MB | 23MB | 0.371秒 | 2.621秒 |
| Sanmoku-0.0.4 | 4.8MB | 2MB | 0.057秒 | 5.807秒 |
Sanmokuは所要メモリや辞書ロード時間が短いが、辞書データを圧縮するためにビット演算や間接参照等を多用しているため、解析速度は他に比べて二倍以上遅くなっている。
Igoは辞書データサイズ自体は大きいが、mmap(java.nio.MappedByteBuffer)を利用しているため、ロード時間は高速となっている。
Sanmoku: 省メモリな形態素解析器
GomokuをベースにしたSanmokuという形態素解析器を実装した。
Gomokuに比べて解析時に必要なメモリ量が少ないのと初期ロード時間が短いのが特徴。
将来的には解析精度を若干落として、辞書サイズ*1をさらに削減する可能性もあるけど、現状は解析結果はGomoku互換。
Android等のリソースの制限が厳しい環境での使用を想定。
最低メモリ所要量とロード時間
以下、自分の環境*2での計測結果。
## 最低メモリ所要量 # Gomoku(0.0.4)は 26MBのメモリが必要 $ java -Xmx26m -cp gomoku-0.0.4.jar net.reduls.gomoku.bin.Gomoku < /path/to/natsume-soseki.txt > /dev/null # Sanmoku(0.0.1)は 11MBのメモリが必要 $ java -Xmx11m -cp sanmoku-0.0.1.jar net.reduls.sanmoku.bin.Sanmoku < /path/to/natsume-soseki.txt > /dev/null ## ロード時間 # Gomoku(0.0.4)は 0.633秒 (内 0.094秒はJVM起動時間) time echo 'a' | java -Xmx26m -cp gomoku-0.0.4.jar net.reduls.gomoku.bin.Gomoku a 名詞,固有名詞,組織,*,*,* EOS real 0m0.633s user 0m0.808s sys 0m0.044s # Sanmoku(0.0.1)は 0.217秒 (内 0.094秒はJVM起動時間) time echo 'a' | java -Xmx11m -cp sanmoku-0.0.1.jar net.reduls.sanmoku.bin.Sanmoku a 名詞,固有名詞,組織,*,*,* EOS real 0m0.217s user 0m0.244s sys 0m0.024s
Android
https://github.com/sile/sanmoku/downloads に Sanmoku-0.0.1.apk という名前でサンプルAndroidアプリを配置。
自分の環境(HTC EVO WiMAX ISW11HT)でしか動作確認していないので、他のスマートフォンで正常に動くかどうかは不明。
辞書ロード時間は、Gomokuに比べるとだいぶ短縮されてはいるが、それでも一番初めの解析が始まるまで、現状では数秒程度の時間を要する。
Igo-0.4.3の辞書引きにDAWGを試す
Igo-0.4.3: 若干のパフォーマンス向上 - sileの日記の続き。
Gomoku(0.0.4)では辞書引き部分*1にDAWGを使っているので、それもIgoに取り込んで処理速度の変化を図ってみた。
比較
諸々の条件は前回と同様。
今回は新たにIgoのDAWG版が加わる。
| 総処理時間(1) | 起動+行読み込み+辞書ロード 時間(2) | 解析時間(1 - 2) | |
| MeCab(0.98) | 15.381s | 0.101s | 15.280s |
| Gomoku(0.0.4) | 16.458s | 0.565s | 15.893s |
| Igo(0.4.2) | 20.351s | 0.638s | 19.713s |
| Igo(0.4.3) | 18.792s | 0.638s | 18.154s |
| Igo-DAWG(0.4.3) | 17.168s | 0.638s | 16.529s |
ただこの変更はバイナリ辞書のフォーマットが変わってしまうので、少なくとも当面は正式なリリースとして公開することはしない。
DAWG版作成方法
手順のメモ。
基本的には、従来使っていた辞書引きクラスをdic-androidにあるDAWGのそれに置き換えるだけ。
# 1: DAWG版へのパッチ適用 $ tar zxvf igo-0.4.3-src.tar.gz $ patch -p0 -E < igo-0.4.3-dawg.patch # igo-0.4.3-dawg.patch に関しては末尾を参照 # 2: ソースビルド $ cd igo-0.4.3-src $ ant # 3: 辞書構築 # - 単語名のリストが標準出力に出力されるので、それを保存しておく $ java -cp igo-0.4.3.jar net.reduls.igo.bin.BuildDic バイナリ辞書 テキスト辞書 > word.list # 4: 辞書引き用のインデックスを作成する # 4-1: dic-androidのソースを取得 $ wget https://download.github.com/sile-dic-android-v0.0.1-0-ga45cd32.tar.gz $ tar zxvf sile-dic-android-v0.0.1-0-ga45cd32.tar.gz # 4-2: インデックス構築 $ cd sile-dic-android-a45cd32/dicbuilder/ $ sbcl # sbcl起動 ※common-lisp処理系 > (require :asdf) > (asdf:load-system :dic) ;; 単語リスト読み込み > (defvar *words* (with-open-file (in "/path/to/word.list") (loop FOR line = (read-line in nil nil) WHILE line COLLECT line))) ;; DAWGインデックス作成: Igoバイナリ辞書ディレクトリに追加 > (dic.trie.double-array:build *words* "バイナリ辞書/") > (quit) # 終了
パッチ
ファイル名はigo-0.4.3-dawg.patch:
diff -rcN igo-0.4.3-src-orig/src/net/reduls/igo/dictionary/WordDic.java igo-0.4.3-src/src/net/reduls/igo/dictionary/WordDic.java *** igo-0.4.3-src-orig/src/net/reduls/igo/dictionary/WordDic.java 2011-06-17 17:24:58.000000000 -0700 --- igo-0.4.3-src/src/net/reduls/igo/dictionary/WordDic.java 2011-06-18 12:15:57.167778148 -0700 *************** *** 3,12 **** import java.io.IOException; import java.util.List; import net.reduls.igo.trie.Searcher; import net.reduls.igo.util.FileMappedInputStream; public final class WordDic { ! private final Searcher trie; private final String data; private final int[] indices; --- 3,13 ---- import java.io.IOException; import java.util.List; import net.reduls.igo.trie.Searcher; + import net.reduls.igo.trie.DawgSearcher; import net.reduls.igo.util.FileMappedInputStream; public final class WordDic { ! private final DawgSearcher trie; private final String data; private final int[] indices; *************** *** 16,22 **** public final int[] dataOffsets; // dataOffsets[単語ID] = 単語の素性データの開始位置 public WordDic(String dataDir) throws IOException { ! trie = new Searcher(dataDir+"/word2id"); data = FileMappedInputStream.getString(dataDir+"/word.dat"); indices = FileMappedInputStream.getIntArray(dataDir+"/word.ary.idx"); --- 17,23 ---- public final int[] dataOffsets; // dataOffsets[単語ID] = 単語の素性データの開始位置 public WordDic(String dataDir) throws IOException { ! trie = new DawgSearcher(dataDir); data = FileMappedInputStream.getString(dataDir+"/word.dat"); indices = FileMappedInputStream.getIntArray(dataDir+"/word.ary.idx"); diff -rcN igo-0.4.3-src-orig/src/net/reduls/igo/dictionary/build/WordDic.java igo-0.4.3-src/src/net/reduls/igo/dictionary/build/WordDic.java *** igo-0.4.3-src-orig/src/net/reduls/igo/dictionary/build/WordDic.java 2010-03-29 02:35:02.000000000 -0700 --- igo-0.4.3-src/src/net/reduls/igo/dictionary/build/WordDic.java 2011-06-18 12:15:57.167778148 -0700 *************** *** 50,56 **** // 単語辞書からキーを集める for(File csvFile : new File(inputDir).listFiles(new onlyCsv())) collectKey(csvFile.getPath(), keyList, ""); ! final Builder bld = Builder.build(keyList); bld.save(outputDir+"/word2id"); } --- 50,56 ---- // 単語辞書からキーを集める for(File csvFile : new File(inputDir).listFiles(new onlyCsv())) collectKey(csvFile.getPath(), keyList, ""); ! final Builder bld = Builder.build(keyList); bld.save(outputDir+"/word2id"); } diff -rcN igo-0.4.3-src-orig/src/net/reduls/igo/trie/Builder.java igo-0.4.3-src/src/net/reduls/igo/trie/Builder.java *** igo-0.4.3-src-orig/src/net/reduls/igo/trie/Builder.java 2010-03-29 02:35:02.000000000 -0700 --- igo-0.4.3-src/src/net/reduls/igo/trie/Builder.java 2011-06-18 12:15:57.167778148 -0700 *************** *** 23,30 **** java.util.Collections.sort(keyList); String prev=null; for(String k : keyList) ! if(k.equals(prev)==false) ! ksList.add(new KeyStream(prev=k)); } /** --- 23,33 ---- java.util.Collections.sort(keyList); String prev=null; for(String k : keyList) ! if(k.equals(prev)==false) { ! System.out.println(k); ! ksList.add(new KeyStream(prev=k)); ! } ! } /** diff -rcN igo-0.4.3-src-orig/src/net/reduls/igo/trie/Char.java igo-0.4.3-src/src/net/reduls/igo/trie/Char.java *** igo-0.4.3-src-orig/src/net/reduls/igo/trie/Char.java 1969-12-31 16:00:00.000000000 -0800 --- igo-0.4.3-src/src/net/reduls/igo/trie/Char.java 2011-06-18 12:15:57.167778148 -0700 *************** *** 0 **** --- 1,39 ---- + package net.reduls.igo.trie; + + import java.io.DataInputStream; + import java.io.FileInputStream; + import java.io.IOException; + import java.util.List; + import java.util.ArrayList; + + public final class Char { + private final char[] charCode; + private final List<Character> arcs; + + public Char(String dictionaryDirectory) throws IOException { + final DataInputStream in = + new DataInputStream(new FileInputStream(dictionaryDirectory+"/code-map.bin")); + try { + final int codeLimit = in.readInt(); + charCode = new char[codeLimit]; + + arcs = new ArrayList<Character>(); + + for(int i=0; i < codeLimit; i++) { + charCode[i] = in.readChar(); + if(charCode[i] != 0) + arcs.add(charCode[i]); + } + } finally { + in.close(); + } + } + + public char code(char ch) { + return charCode[ch]; + } + + public List<Character> arcs() { + return arcs; + } + } diff -rcN igo-0.4.3-src-orig/src/net/reduls/igo/trie/DawgSearcher.java igo-0.4.3-src/src/net/reduls/igo/trie/DawgSearcher.java *** igo-0.4.3-src-orig/src/net/reduls/igo/trie/DawgSearcher.java 1969-12-31 16:00:00.000000000 -0800 --- igo-0.4.3-src/src/net/reduls/igo/trie/DawgSearcher.java 2011-06-18 12:15:57.167778148 -0700 *************** *** 0 **** --- 1,70 ---- + package net.reduls.igo.trie; + + import java.io.FileInputStream; + import java.io.IOException; + import java.nio.ByteBuffer; + import java.nio.channels.FileChannel; + + + /** + * DoubleArray検索用のクラス + */ + public final class DawgSearcher { + private final long[] nodes; + private final Char charcode; + + public DawgSearcher(String dictionaryDirectory) throws IOException { + final FileChannel cnl = + new FileInputStream(dictionaryDirectory+"/surface-id.bin").getChannel(); + try { + final ByteBuffer buf = cnl.map(FileChannel.MapMode.READ_ONLY, 0, cnl.size()); + final int nodeCount = buf.getInt(); + nodes = new long[nodeCount]; + buf.asLongBuffer().get(nodes); + } finally { + cnl.close(); + } + + charcode = new Char(dictionaryDirectory); + } + + public void eachCommonPrefix(CharSequence text, int start, Searcher.Callback fn) { + int node = 0; + int id = -1; + + for(int i=start;; i++) { + if(isTerminal(node)) + fn.call(start, i-start, id); + + if(i==text.length()) + return; + + final char arc = charcode.code(text.charAt(i)); + final int next = base(node)+arc; + if(chck(next) != arc) + return; + node = next; + id = nextId(id,node); + } + } + + private char chck(int node) { + return (char)((nodes[node]>>24) & 0xFFFF); + } + + private int base(int node) { + return (int)(nodes[node] & 0xFFFFFF); + } + + private boolean isTerminal(int node) { + return ((nodes[node]>>40) & 0x1) == 0x1; + } + + private int siblingTotal(int node) { + return (int)(nodes[node]>>41); + } + + private int nextId(int id, int node) { + return id + siblingTotal(node) + (isTerminal(node) ? 1 : 0); + } + }
Igo-0.4.3: 若干のパフォーマンス向上
Gomoku(0.0.4)で得た知見の一部をIgo(0.4.3)に取り込んでみた。
形態素解析の部分が少し速くなっている。
比較
MeCab(0.98)、Gomoku(0.0.4)、Igo(0.4.2,0.4.3)の処理速度の比較*1。
以前とはマシンも変わっているので、全部計り直した。
計時には約80MBの日本語テキストデータを用いた。
※ その詳細と計時に使用したプログラムに関しては後述
辞書には全てMeCabのサイトより入手可能なmecab-ipadic-2.7.0-20070801を使用している。
| 総処理時間(1) | 起動+行読み込み+辞書ロード 時間(2) | 解析時間(1 - 2) | |
| MeCab(0.98) | 15.381s | 0.101s | 15.280s |
| Gomoku(0.0.4) | 16.458s | 0.565s | 15.893s |
| Igo(0.4.2) | 20.351s | 0.638s | 19.713s |
| Igo(0.4.3) | 18.792s | 0.638s | 18.154s |
MeCab、Gomokuよりはまだ一段遅いけど。
テキストデータ
計時に用いたデータは、次のようにして取得可能。
$ wget http://file.reduls.net/blog/20110618/20110618.txt.tar.xz # ダウンロード $ tar Jxvf 20110618.txt.tar.xz # 解凍 $ ls -lh 20110618.txt -rw-r--r-- 1 user user 78M 2011-06-18 00:33 20110618.txt
内容的は以下の二種類のデータの混合:
計時方法
# 計時用ソースコードを取得 # - 使い方等に関しては、ソースコードのコメントも参照のこと $ wget http://file.reduls.net/blog/20110618/mec.cc $ wget http://file.reduls.net/blog/20110618/read_line.h # コンパイル ※ MeCab本体は既にインストール済みと仮定する $ g++ -O3 -omec mec.cc `mecab-config --libs` # 計時 $ time ./mec 20110618.txt
Gomoku:
# 計時用ソースコードを取得 $ wget http://file.reduls.net/blog/20110618/GomokuBench.java # コンパイル $ javac -cp gomoku-0.0.4.jar GomokuBench.java # 計時 $ time java -server -cp .:gomoku-0.0.4.jar GomokuBench < 20110618.txt
Igo:
# 計時用ソースコードを取得 $ wget http://file.reduls.net/blog/20110618/IgoBench.java # コンパイル $ javac -cp igo-0.4.2.jar IgoBench.java # 計時 $ time java -server -cp .:igo-0.4.2.jar IgoBench Igoバイナリ辞書 < 20110618.txt # ver0.4.2用 $ time java -server -cp .:igo-0.4.3.jar IgoBench Igoバイナリ辞書 < 20110618.txt # ver0.4.3用
*1:例によって厳密では全くない。参考程度。
Igo: GAE版の辞書データ読み込み速度向上
igo-gaeを修正して、辞書データ読み込みを速度を向上させた。
※ igo-gaeの現在のバージョンは0.0.2。
修正内容概要
オリジナルのIgoでは、データ読み込みにはnio系パッケージのjava.nio.channels.FileChannelとjava.nio.MappedByteBufferを使っていた。
// MappedByteBufferを使ったデータ(int列)読み込み例 FileChannel in = new FileInputStream("/path/to/dic-data").getChannel(); MappedByteBuffer buffer = in.map(FileChannel.MapMode.READ_ONLY, 0, in.size()); int[] data = new int[(int)in.size()/4]; buffer.asIntBuffer().get(data);
この方法だとバイナリファイルのデータを高速に読み出すことができる。
ただGoogle App EngineではMappedByteBufferクラスが使用不可となっていたため、初期のigo-gae(ver0.0.1)ではjava.io.DataInputStreamを使った方法で代替していた。
// DataInputStreamを使ったデータ(int列)読み込み例 DataInputSream in = new DataInputStream(new BufferedInputStream(new FileInputStream("/path/to/dic-data"))); int[] data = new int[new File("/path/to/dic-data").length()/4]; for(int i=0; i < data.length; i++) data[i] = in.readInt();
今回のver0.0.2では、データ読み込み部に再びnio系のパッケージを採用。
MappedByteBufferは使えないので、代わりにjava.nio.ByteBufferを使用。
ByteBufferに対して必要な分(= ファイルサイズ)の領域を明示的に確保し、そこに(コンストラクタ内で)あらかじめファイルの全データを読み込んでおくようにした。
こうしておけば、後の使い方はMappedByteBufferとただのByteBufferの間にほとんど差異はない。
// (マッピングなしの)ByteBufferを使ったデータ(int列)読み込み FileChannel in = new FileInputStream("/path/to/dic-data").getChannel(); ByteBuffer buffer = ByteBuffer.allocateDirect((int)in.size()/4); in.read(buffer); // ここでファイルのデータを全て読み込んでおく buffer.flip(); int[] data = new int[(int)in.size()/4]; buffer.asIntBuffer().get(data);
この方法は、初めのMappedByteBufferを使うものに比べると若干速度は落ちるが、DataInputStreamを使う方法比べればだいぶ高速。
現時点のigo-gaeのサンプルWebアプリ(http://igo-morp.appspot.com/)はver0.0.2のソースで動いているが、スピンアップ時間がver0.0.1では5秒前後掛かっていたのが、現在は2.5秒前後、と半分程度に短縮されていた。
Gomoku: 辞書込みの形態素解析器
IgoをベースにしてJARファイルに辞書データを同梱した形態素解析器を作成した。
名前は同系統のGomoku(ver 0.0.1)。
特徴
開発コンセプト(?)は「JARファイルのみで形態素解析」と「サイズを(比較的)小さく」の二点。
このJARファイル一つで形態素解析が行える(外部の辞書データ不要)、という点が最大の特徴。
ただし、その分辞書のカスタマイズ性には乏しい。
※ 辞書を変更する場合はjarファイルごと取り替える必要がある
その他の特徴を列挙:
- 辞書データサイズがIgoより小さい
- (デフォルトの)辞書にはIPADIC(mecab-ipadic-2.7.0-20070801)を使用
- 現状IPADICに特化 ※ 他の辞書での動作は未確認。動かないということはないと思うけど・・・
- テキスト辞書からバイナリ辞書を構築する処理はCommon Lispで記述
- 辞書をカスタマイズする場合はSBCL(Common Lisp処理系)が必要
- 形態素の辞書引き用のデータ構造にはDAWG(Double-Array)を使用
- 解析結果はIgo互換 ※ 素性情報に品詞しか含まない点を除いて
試してはいないけどGoogle App Engine上でも問題なく動作するはず。
使用例
使用例:
# jarファイル取得 $ wget --no-check-certificate https://github.com/downloads/sile/gomoku/gomoku-0.0.1.jar $ ls -lh gomoku-0.0.1.jar -rw-r--r-- 1 user user 3.9M 2011-01-24 22:04 gomoku-0.0.1.jar # 形態素解析 $ echo すもももももももものうち | java -cp gomoku-0.0.1.jar net.reduls.gomoku.bin.Gomoku すもも 名詞,一般,*,*,*,* も 助詞,係助詞,*,*,*,* もも 名詞,一般,*,*,*,* も 助詞,係助詞,*,*,*,* もも 名詞,一般,*,*,*,* の 助詞,連体化,*,*,*,* うち 名詞,非自立,副詞可能,*,*,* EOS # 分かち書き $ echo すもももももももものうち | java -cp gomoku-0.0.1.jar net.reduls.gomoku.bin.Gomoku -wakati すもも も もも も もも の うち
Gomokuを使用したJavaプログラム例:
import java.util.List; import net.reduls.gomoku.Tagger; import net.reduls.gomoku.Morpheme; public class GomokuSample { public static void main(String[] args) { final String text = args[0]; List<Morpheme> result = Tagger.parse(text); for(Morpheme m : result) System.out.println(m.surface+"\t"+m.feature); } }
# コンパイル $ javac -cp gomoku-0.0.1.jar GomokuSample.java # 実行: 第一引数で渡された文字列を形態素解析する $ java -cp .:gomoku-0.0.1.jar GomokuSample すもももももももものうち すもも 名詞,一般,*,*,*,* も 助詞,係助詞,*,*,*,* もも 名詞,一般,*,*,*,* も 助詞,係助詞,*,*,*,* もも 名詞,一般,*,*,*,* の 助詞,連体化,*,*,*,* うち 名詞,非自立,副詞可能,*,*,*
まだソースコードとかがいろいろ未整理だけど、一応問題なく動作はしている(ように見える)。
*1:2011/01/25追記: version-0.0.1では、JARファイルサイズが3.3MBで、解凍時が8.3MB。
