• R/O
  • SSH
  • HTTPS

igo: コミット


コミットメタ情報

リビジョン57 (tree)
日時2010-03-18 13:01:12
作者phjgt

ログメッセージ

タグ作成: igo-0.4.0

変更サマリ

差分

--- tags/igo-0.4.0/build.xml (nonexistent)
+++ tags/igo-0.4.0/build.xml (revision 57)
@@ -0,0 +1,33 @@
1+<?xml version="1.0" encoding="UTF-8"?>
2+
3+<project name="igo" default="jar" basedir=".">
4+ <property name="version" value="0.4.0" />
5+ <property name="src.dir" value="src"/>
6+ <property name="classes.dir" value="classes"/>
7+ <property name="javadoc.dir" value="docs"/>
8+
9+ <target name="jar" depends="compile">
10+ <jar jarfile="igo-${version}.jar" basedir="${classes.dir}">
11+ <metainf dir=".">
12+ <include name="COPYING" />
13+ </metainf>
14+ </jar>
15+ </target>
16+
17+ <target name="compile">
18+ <mkdir dir="${classes.dir}" />
19+ <javac debug="off" encoding="UTF-8" srcdir="${src.dir}" destdir="${classes.dir}" />
20+ </target>
21+
22+ <target name="javadoc">
23+ <javadoc destdir="${javadoc.dir}">
24+ <fileset dir="${src.dir}"/>
25+ </javadoc>
26+ </target>
27+
28+ <target name="clean">
29+ <delete dir="${classes.dir}" />
30+ <delete dir="${javadoc.dir}" />
31+ <delete file="${jar.name}" />
32+ </target>
33+</project>
--- tags/igo-0.4.0/src/net/reduls/igo/dictionary/Word.java (nonexistent)
+++ tags/igo-0.4.0/src/net/reduls/igo/dictionary/Word.java (revision 57)
@@ -0,0 +1,30 @@
1+package net.reduls.igo.dictionary;
2+
3+import java.io.IOException;
4+import net.reduls.igo.util.FileMappedInputStream;
5+
6+/**
7+ * 辞書内の単語を扱うクラス
8+ * クラス名は単数形だが、個々の単語というよりは、単語セット全体を扱っている
9+ */
10+final class Word {
11+ public final int count; // 単語数
12+ public final short[] costs; // consts[単語ID] = 単語のコスト
13+ public final short[] leftIds; // leftIds[単語ID] = 単語の左文脈ID
14+ public final short[] rightIds; // rightIds[単語ID] = 単語の右文脈ID
15+ public final int[] dataOffsets; // dataOffsets[単語ID] = 単語の素性データの開始位置
16+
17+ public Word(String filepath) throws IOException {
18+ final FileMappedInputStream fmis = new FileMappedInputStream(filepath);
19+ count = fmis.size()/(2+2+2+4);
20+
21+ try {
22+ dataOffsets= fmis.getIntArray(count);
23+ leftIds = fmis.getShortArray(count);
24+ rightIds = fmis.getShortArray(count);
25+ costs = fmis.getShortArray(count);
26+ } finally {
27+ fmis.close();
28+ }
29+ }
30+}
\ No newline at end of file
--- tags/igo-0.4.0/src/net/reduls/igo/dictionary/WordDic.java (nonexistent)
+++ tags/igo-0.4.0/src/net/reduls/igo/dictionary/WordDic.java (revision 57)
@@ -0,0 +1,230 @@
1+package net.reduls.igo.dictionary;
2+
3+import java.io.File;
4+import java.io.FileFilter;
5+import java.io.IOException;
6+import java.util.List;
7+import java.util.ArrayList;
8+import net.reduls.igo.trie.Builder;
9+import net.reduls.igo.trie.Searcher;
10+import net.reduls.igo.util.ReadLine;
11+import net.reduls.igo.util.FileMappedInputStream;
12+import net.reduls.igo.util.FileMappedOutputStream;
13+
14+public final class WordDic {
15+ private final Searcher trie;
16+ private final String data;
17+ private final Word word;
18+ private final int[] indices;
19+
20+ public WordDic(String dataDir) throws IOException {
21+ trie = new Searcher(dataDir+"/word2id");
22+ word = new Word(dataDir+"/word.inf");
23+ data = FileMappedInputStream.getString(dataDir+"/word.dat");
24+ indices = FileMappedInputStream.getIntArray(dataDir+"/word.ary.idx");
25+ }
26+
27+ public short cost(int wordId) { return word.costs[wordId]; }
28+ public short leftId(int wordId) { return word.leftIds[wordId]; }
29+ public short rightId(int wordId) { return word.rightIds[wordId]; }
30+ public int dataOffset(int wordId) { return word.dataOffsets[wordId]; }
31+
32+ public void search(CharSequence text, int start, List<ViterbiNode> result) {
33+ trie.eachCommonPrefix(text, start, new Collect(result));
34+ }
35+
36+ public void searchFromTrieId(int trieId, int start, int wordLength, boolean isSpace, List<ViterbiNode> result) {
37+ final int end = indices[trieId+1];
38+ for(int i=indices[trieId]; i < end; i++)
39+ result.add(new ViterbiNode(i, start, (short)wordLength, leftId(i), rightId(i), isSpace));
40+ }
41+
42+ public String wordData(int wordId){
43+ return data.substring(dataOffset(wordId), dataOffset(wordId+1));
44+ }
45+
46+ private class Collect implements Searcher.Callback {
47+ public final List<ViterbiNode> ms;
48+ public Collect(List<ViterbiNode> result) { ms = result; }
49+
50+ public void call(int start, int offset, int trieId) {
51+ final int end = indices[trieId+1];
52+ for(int i=indices[trieId]; i < end; i++)
53+ ms.add(new ViterbiNode(i, start, (short)offset, leftId(i), rightId(i), false));
54+ }
55+ }
56+
57+ // TODO: delimiterを指定可能にする
58+ private static void collectKey(ReadLine rl, List<String> keyList, String prefix) throws IOException {
59+ try {
60+ for(String line=rl.read(); line!=null; line=rl.read()) {
61+ final String key = line.substring(0, line.indexOf(','));
62+ keyList.add(prefix+key);
63+ }
64+ } finally {
65+ rl.close();
66+ }
67+ }
68+
69+ public static void genWordIdMap(String inputDir, String outputDir, String encoding) throws IOException {
70+ final List<String> keyList = new ArrayList<String>();
71+
72+ // 未知語定義からキーを集める
73+ collectKey(new ReadLine(inputDir+"/unk.def", encoding), keyList, CharCategory.KEY_PREFIX);
74+
75+ // 単語辞書からキーを集める
76+ for(File csvFile : new File(inputDir).listFiles(new onlyCsv()))
77+ collectKey(new ReadLine(csvFile.getPath(), encoding), keyList, "");
78+
79+ final Builder bld = Builder.build(keyList);
80+ bld.save(outputDir+"/word2id");
81+ }
82+
83+ // TODO: delimiter
84+ private static void collectWordInfo(String filepath, String encoding, Searcher wid, String prefix,
85+ ArrayList<ArrayList<WordInfo>> ws) throws IOException {
86+ final ReadLine rl = new ReadLine(filepath, encoding);
87+ try {
88+ for(String s=rl.read(); s!=null; s=rl.read()) {
89+ final int p1 = s.indexOf(','); // key
90+ final int p2 = s.indexOf(',',p1+1); // left id
91+ final int p3 = s.indexOf(',',p2+1); // right id
92+ final int p4 = s.indexOf(',',p3+1); // cost
93+ final String data = s.substring(p4+1); // data
94+
95+ final int id = wid.search(prefix+s.substring(0,p1));
96+ if(id < 0)
97+ throw new IOException("Word '"+s.substring(0,p1)+"' is unregistered in trie"); // TODO: parse exception
98+
99+ ws.get(id).add(new WordInfo(Short.valueOf(s.substring(p1+1,p2)),
100+ Short.valueOf(s.substring(p2+1,p3)),
101+ Short.valueOf(s.substring(p3+1,p4)),
102+ data));
103+ }
104+ } catch (Exception e) {
105+ throw new IOException(filepath+": "+rl.lineNumber(), e); // XXX: for debug
106+ } finally {
107+ rl.close();
108+ }
109+ }
110+
111+ private static void removeUnusedEntry(ArrayList<ArrayList<WordInfo>> ws) {
112+ for(ArrayList<WordInfo> wlist : ws) {
113+ java.util.Collections.sort(wlist);
114+ int last=0;
115+ for(int i=1; i < wlist.size(); i++) {
116+ if(!(wlist.get(last).leftId == wlist.get(i).leftId &&
117+ wlist.get(last).rightId == wlist.get(i).rightId))
118+ wlist.set(++last, wlist.get(i));
119+ }
120+ for(int i=wlist.size()-1; i > last; i--)
121+ wlist.remove(i);
122+ }
123+ }
124+
125+ public static void genWordInfo(String inputDir, String outputDir, String encoding) throws IOException {
126+ final Searcher wid = new Searcher(outputDir+"/word2id");
127+ final ArrayList<ArrayList<WordInfo>> ws = new ArrayList<ArrayList<WordInfo>>(wid.size());
128+ for(int i=0; i < wid.size(); i++)
129+ ws.add(new ArrayList<WordInfo>());
130+
131+ // 未知語定義からデータを集める
132+ collectWordInfo(inputDir+"/unk.def", encoding, wid, CharCategory.KEY_PREFIX, ws);
133+
134+ // 単語辞書からデータを集める
135+ for(File csvFile : new File(inputDir).listFiles(new onlyCsv()))
136+ collectWordInfo(csvFile.getPath(), encoding, wid, "", ws);
137+
138+ // 無駄な項目を削除する
139+ // NOTE:
140+ removeUnusedEntry(ws);
141+
142+ // 単語情報を出力
143+ final StringBuilder wdat = new StringBuilder();
144+
145+ int size=0;
146+ for(ArrayList<WordInfo> wlist : ws)
147+ size += wlist.size();
148+
149+ final FileMappedOutputStream fmosInf =
150+ new FileMappedOutputStream(outputDir+"/word.inf", (size+1)*(2+2+2+4));
151+ try {
152+ for(ArrayList<WordInfo> wlist : ws) // dataOffset
153+ for(WordInfo w : wlist) {
154+ fmosInf.putInt(wdat.length());
155+ wdat.append(w.data);
156+ }
157+ fmosInf.putInt(wdat.length());
158+
159+ for(ArrayList<WordInfo> wlist : ws) // leftId
160+ for(WordInfo w : wlist)
161+ fmosInf.putShort(w.leftId);
162+ fmosInf.putShort((short)0);
163+
164+ for(ArrayList<WordInfo> wlist : ws) // rightId
165+ for(WordInfo w : wlist)
166+ fmosInf.putShort(w.rightId);
167+ fmosInf.putShort((short)0);
168+
169+ for(ArrayList<WordInfo> wlist : ws) // cost
170+ for(WordInfo w : wlist)
171+ fmosInf.putShort(w.cost);
172+ fmosInf.putShort((short)0);
173+ } finally {
174+ fmosInf.close();
175+ }
176+
177+ // 単語データを出力
178+ final FileMappedOutputStream fmosDat =
179+ new FileMappedOutputStream(outputDir+"/word.dat", wdat.length()*2);
180+ try {
181+ fmosDat.putString(wdat.toString());
182+ } finally {
183+ fmosDat.close();
184+ }
185+
186+ // 単語情報の配列へのインデックスを保存する
187+ {
188+ final FileMappedOutputStream fmosIdx =
189+ new FileMappedOutputStream(outputDir+"/word.ary.idx", (ws.size()+1)*4);
190+ int begIndex=0;
191+ try {
192+ for(ArrayList<WordInfo> wlist : ws) {
193+ fmosIdx.putInt(begIndex);
194+ begIndex += wlist.size();
195+ }
196+ fmosIdx.putInt(begIndex);
197+ } finally {
198+ fmosIdx.close();
199+ }
200+ }
201+ }
202+
203+ private static class WordInfo implements Comparable<WordInfo> {
204+ public short leftId;
205+ public short rightId;
206+ public short cost;
207+ public String data;
208+
209+ public WordInfo(short lid, short rid, short c, String dat) {
210+ leftId = lid;
211+ rightId = rid;
212+ cost = c;
213+ data = dat;
214+ }
215+
216+ public int compareTo(WordInfo wi) {
217+ if(leftId != wi.leftId)
218+ return leftId - wi.leftId;
219+ if(rightId != wi.rightId)
220+ return rightId - wi.rightId;
221+ return cost - wi.cost;
222+ }
223+ }
224+
225+ private static class onlyCsv implements FileFilter {
226+ public boolean accept(File file) {
227+ return file.isFile() && file.toString().matches(".*\\.csv$");
228+ }
229+ }
230+}
\ No newline at end of file
--- tags/igo-0.4.0/src/net/reduls/igo/dictionary/Unknown.java (nonexistent)
+++ tags/igo-0.4.0/src/net/reduls/igo/dictionary/Unknown.java (revision 57)
@@ -0,0 +1,46 @@
1+package net.reduls.igo.dictionary;
2+
3+import java.io.IOException;
4+import java.util.List;
5+
6+/**
7+ * 未知語の検索を行うクラス
8+ */
9+public final class Unknown {
10+ private final CharCategory category; // 文字カテゴリ管理クラス
11+ private final int spaceId; // 文字カテゴリがSPACEの文字のID
12+
13+ public Unknown(String dataDir) throws IOException {
14+ category = new CharCategory(dataDir);
15+ spaceId = category.category(' ').id; // NOTE: ' 'の文字カテゴリはSPACEに予約されている
16+ }
17+
18+ public void search(CharSequence text, int start, WordDic wdic, List<ViterbiNode> result) {
19+ final char ch = text.charAt(start);
20+ final CharCategory.Category ct = category.category(ch);
21+
22+ if(result.isEmpty()==false && ct.invoke==false)
23+ return;
24+
25+ final boolean isSpace = ct.id==spaceId;
26+ final int limit = Math.min(text.length(), ct.length+start);
27+ boolean finished = false;
28+ int i=start;
29+ for(; i < limit; i++) {
30+ wdic.searchFromTrieId(ct.id, start, (i-start)+1, isSpace, result);
31+ if(i+1!=limit && category.isCompatible(ch, text.charAt(i+1)) == false) {
32+ finished = true;
33+ break;
34+ }
35+ }
36+
37+ if(ct.group && !finished && i < text.length()) {
38+ for(; i < text.length(); i++)
39+ if(category.isCompatible(ch, text.charAt(i)) == false) {
40+ wdic.searchFromTrieId(ct.id, start, i-start, isSpace, result);
41+ return;
42+ }
43+ wdic.searchFromTrieId(ct.id, start, text.length()-start, isSpace, result);
44+ }
45+ }
46+}
\ No newline at end of file
--- tags/igo-0.4.0/src/net/reduls/igo/dictionary/Matrix.java (nonexistent)
+++ tags/igo-0.4.0/src/net/reduls/igo/dictionary/Matrix.java (revision 57)
@@ -0,0 +1,104 @@
1+package net.reduls.igo.dictionary;
2+
3+import java.io.IOException;
4+import java.io.EOFException;
5+import java.text.ParseException;
6+import net.reduls.igo.util.ReadLine;
7+import net.reduls.igo.util.FileMappedInputStream;
8+import net.reduls.igo.util.FileMappedOutputStream;
9+
10+/**
11+ * 形態素の連接コスト表を扱うクラス
12+ */
13+public final class Matrix {
14+ private final int leftSize;
15+ private final int rightSize;
16+ private final short[] matrix;
17+
18+ public Matrix(String dataDir) throws IOException {
19+ final FileMappedInputStream fmis = new FileMappedInputStream(dataDir+"/matrix.bin");
20+ try {
21+ leftSize = fmis.getInt();
22+ rightSize= fmis.getInt();
23+ matrix = fmis.getShortArray(leftSize*rightSize);
24+ } finally {
25+ fmis.close();
26+ }
27+ }
28+
29+ /**
30+ * 形態素同士の連接コストを求める
31+ */
32+ public short linkCost(int leftId, int rightId) {
33+ return matrix[rightId*rightSize + leftId];
34+ }
35+
36+ /**
37+ * 連接コスト表のバイナリデータを作成する
38+ *
39+ * @params inputDir ソース辞書があるディレクトリ。{@code inputDir+"/matrix.def"}ファイルが使用される
40+ * @params outputDir バイナリデータが保存されるディレクトリ。{@code outputDir+"/matrix.bin"}ファイルが作成される
41+ * @throws ParseException 入力ファイルのパースに失敗した場合に送出される
42+ * @throws IOException 入出力エラーが発生した場合に送出される
43+ */
44+ public static void build(String inputDir, String outputDir) throws ParseException, IOException {
45+ final ReadLine rl = new ReadLine(inputDir+"/matrix.def", "UTF-8");
46+ try {
47+ // 一行目はサイズ: [左文脈IDの数] [右文脈IDの数]
48+ String s = rl.readEof();
49+ final int leftNum = Integer.valueOf(s.substring(0,s.indexOf(' ')));
50+ final int rightNum= Integer.valueOf(s.substring(s.indexOf(' ')+1));
51+ final FileMappedOutputStream fmos =
52+ new FileMappedOutputStream(outputDir+"/matrix.bin", 4*2+leftNum*rightNum*2);
53+ try {
54+ fmos.putInt(leftNum);
55+ fmos.putInt(rightNum);
56+
57+ // 二行目以降はデータ: [左文脈ID] [右文脈ID] [連接コスト]
58+ final short[] tmpMatrix = new short[leftNum*rightNum];
59+ for(int i=0; i < leftNum; i++)
60+ for(int j=0; j < rightNum; j++) {
61+ s = rl.readEof();
62+ final int p1 = s.indexOf(' ');
63+ final int p2 = s.indexOf(' ',p1+1);
64+
65+ final int lftID = Integer.valueOf(s.substring(0, p1));
66+ final int rgtID = Integer.valueOf(s.substring(p1+1, p2));
67+ final short cost = Short.valueOf(s.substring(p2+1));
68+
69+ if(i != lftID) throw new ParseException
70+ ("Unexpected left context ID. ID="+lftID+", expedted="+i+"\t"+
71+ "{file: matrix.def, line: "+rl.lineNumber()+"}", rl.lineNumber());
72+ if(j != rgtID) throw new ParseException
73+ ("Unexpected right context ID. ID="+rgtID+", expedted="+j+"\t"+
74+ "{file: matrix.def, line: "+rl.lineNumber()+"}", rl.lineNumber());
75+
76+ // NOTE: tmpMatrixという一時配列を用いている理由
77+ //
78+ // この段階で、fmos.putShort(cost)、などとしてファイルに書き出した場合、
79+ // matrix[leftId][rightId]=cost、といった配列ができる。
80+ //
81+ // それでも特に問題はないのだが、今回のケースでは、
82+ // 「rightIdが固定で、leftIdのみが変動する」といったようなメモリアクセスパターンが多い。
83+ //
84+ // そのためtmpMatrix配列を用いて、コスト値の並び順を変更し、
85+ // matrix[rightId][leftId]とったように、rightIdが第一添字になるようにした方が
86+ // メモリアクセスの局所性が高まり、若干だが処理速度が向上する。
87+ tmpMatrix[j*rightNum + i] = cost;
88+ }
89+ for(short cost : tmpMatrix)
90+ fmos.putShort(cost);
91+ } finally {
92+ fmos.close();
93+ }
94+ } catch (NumberFormatException e) {
95+ throw new ParseException("Parse short integer failed. "+e.getMessage()+"\t"+
96+ "{file: matrix.def, line: "+rl.lineNumber()+"}", rl.lineNumber());
97+ } catch (EOFException e) {
98+ throw new ParseException("End of file reached\t"+
99+ "{file: matrix.def, line: "+rl.lineNumber()+"}", rl.lineNumber());
100+ } finally {
101+ rl.close();
102+ }
103+ }
104+}
\ No newline at end of file
--- tags/igo-0.4.0/src/net/reduls/igo/dictionary/ViterbiNode.java (nonexistent)
+++ tags/igo-0.4.0/src/net/reduls/igo/dictionary/ViterbiNode.java (revision 57)
@@ -0,0 +1,30 @@
1+package net.reduls.igo.dictionary;
2+
3+/**
4+ * Viterbiアルゴリズムで使用されるノード
5+ */
6+public final class ViterbiNode {
7+ public int cost = 0; // 始点からノードまでの総コスト
8+ public ViterbiNode prev = null; // コスト最小の前方のノードへのリンク
9+
10+ public final int wordId; // 単語ID
11+ public final short leftId; // 左文脈ID
12+ public final short rightId; // 右文脈ID
13+ public final int start; // 入力テキスト内での形態素の開始位置
14+ public final short length; // 形態素の表層形の長さ(文字数)
15+
16+ public final boolean isSpace; // 形態素の文字種(文字カテゴリ)が空白文字かどうか
17+
18+ public ViterbiNode(int wid, int beg, short len, short l, short r, boolean space) {
19+ wordId = wid;
20+ leftId = l;
21+ rightId =r;
22+ length = len;
23+ isSpace = space;
24+ start = beg;
25+ }
26+
27+ public static ViterbiNode makeBOSEOS() {
28+ return new ViterbiNode(0,0,(short)0,(short)0,(short)0,false);
29+ }
30+}
\ No newline at end of file
--- tags/igo-0.4.0/src/net/reduls/igo/dictionary/CharCategory.java (nonexistent)
+++ tags/igo-0.4.0/src/net/reduls/igo/dictionary/CharCategory.java (revision 57)
@@ -0,0 +1,194 @@
1+package net.reduls.igo.dictionary;
2+
3+import java.io.IOException;
4+import java.util.Map;
5+import java.util.HashMap;
6+import java.util.List;
7+import java.util.ArrayList;
8+import net.reduls.igo.trie.Searcher;
9+import net.reduls.igo.util.ReadLine;
10+import net.reduls.igo.util.FileMappedInputStream;
11+import net.reduls.igo.util.FileMappedOutputStream;
12+
13+public final class CharCategory {
14+ public static final String KEY_PREFIX="\002";
15+
16+ private final Category[] categorys;
17+ private final int[] char2id;
18+ private final int[] eqlMasks;
19+
20+ public CharCategory (String dataDir) throws IOException {
21+ categorys = readCategorys(dataDir);
22+
23+ final FileMappedInputStream fmis = new FileMappedInputStream(dataDir+"/code2category");
24+ try {
25+ char2id = fmis.getIntArray(fmis.size()/4/2);
26+ eqlMasks= fmis.getIntArray(fmis.size()/4/2);
27+ } finally {
28+ fmis.close();
29+ }
30+ }
31+
32+ public Category category(char code) {
33+ return categorys[char2id[code]];
34+ }
35+
36+ public boolean isCompatible(char code1, char code2) {
37+ return (eqlMasks[code1] & eqlMasks[code2]) != 0;
38+ }
39+
40+ public static void build(String inputDir, String outputDir, String encoding) throws IOException {
41+ // 文字カテゴリの定義を取得する
42+ final Map<String,Category> ccmap = parseCharCategoryDef(inputDir, outputDir, encoding);
43+
44+ // 文字カテゴリの定義を保存する
45+ List<Category> categorys = new ArrayList<Category>();
46+ for(Category e : ccmap.values())
47+ categorys.add(e);
48+ genCharCategoryMap(categorys, outputDir);
49+
50+ // 文字とカテゴリのマッピングを取得/保存する
51+ genCodeCategoryMap(ccmap, inputDir, outputDir, encoding);
52+ }
53+
54+ private static void genCharCategoryMap(List<Category> categorys, String outputDir) throws IOException {
55+ final FileMappedOutputStream fmos =
56+ new FileMappedOutputStream(outputDir+"/char.category", categorys.size()*4*4);
57+ try {
58+ java.util.Collections.sort(categorys);
59+ for(Category e : categorys) {
60+ fmos.putInt(e.id);
61+ fmos.putInt(e.length);
62+ fmos.putInt(e.invoke ? 1 : 0);
63+ fmos.putInt(e.group ? 1 : 0);
64+ }
65+ } finally {
66+ fmos.close();
67+ }
68+ }
69+
70+ private static Map<String,Category> parseCharCategoryDef(String inputDir,String outputDir,String encoding)
71+ throws IOException {
72+ final ReadLine rl = new ReadLine(inputDir+"/char.def",encoding);
73+ final Searcher srch = new Searcher(outputDir+"/word2id");
74+ final Map<String,Category> map = new HashMap<String,Category>();
75+ String line;
76+
77+ try {
78+ while((line=rl.read()) != null) {
79+ if(line.isEmpty() || line.startsWith("#") || line.startsWith("0"))
80+ continue;
81+
82+ // TODO: 不正な入力をチェックする
83+ final String[] ss = line.split("\\s+");
84+ final String name = ss[0];
85+ final boolean invoke = ss[1].equals("1"); // 0 or 1
86+ final boolean group = ss[2].equals("1"); // 0 or 1
87+ final int length = Short.valueOf(ss[3]); // positive integer
88+ final int id = srch.search(KEY_PREFIX+name);
89+ if(id < 0)
90+ throw new IOException("Category '"+name+"' is unregistered in trie"); // TODO: parse exception
91+ map.put(name, new Category(id,length,invoke,group));
92+ }
93+ } finally {
94+ rl.close();
95+ }
96+ // TODO: 'DEFAULT' and 'SPACE'(?) カテゴリがあるかどうかをチェックする
97+ return map;
98+ }
99+
100+ public static class Category implements Comparable<Category> {
101+ public final int id;
102+ public final int length;
103+ public final boolean invoke;
104+ public final boolean group;
105+
106+ public Category(int i, int l, boolean iv, boolean g) {
107+ id = i;
108+ length = l;
109+ invoke = iv;
110+ group = g;
111+ }
112+
113+ public int compareTo(Category e) { return id - e.id; }
114+ }
115+
116+ private Category[] readCategorys(String dataDir) throws IOException {
117+ final int[] data = FileMappedInputStream.getIntArray(dataDir+"/char.category");
118+ final int size = data.length/4;
119+
120+ final Category[] ary = new Category[size];
121+ for(int i=0; i < size; i++)
122+ ary[i] = new Category(data[i*4],data[i*4+1],data[i*4+2]==1,data[i*4+3]==1);
123+ return ary;
124+ }
125+
126+ private static class CharId {
127+ public final int id;
128+ public int mask;
129+
130+ public CharId(int i) {
131+ id = i;
132+ add(id);
133+ }
134+ public CharId(int i, int m) {
135+ id=i;
136+ mask=m;
137+ }
138+ public void add(int i) {
139+ mask |= 1<<i;
140+ }
141+ }
142+
143+ private static void genCodeCategoryMap
144+ (Map<String,Category> map, String inputDir, String outputDir, String encoding) throws IOException {
145+ final CharId[] chars = new CharId[0x10000];
146+ {
147+ final CharId dft = new CharId(map.get("DEFAULT").id);
148+ for(int i=0; i < 0x10000; i++)
149+ chars[i] = dft;
150+ }
151+
152+ final ReadLine rl = new ReadLine(inputDir+"/char.def", encoding);
153+ try {
154+ String line;
155+ while((line=rl.read()) != null) {
156+ if(line.startsWith("0")==false)
157+ continue;
158+
159+ // TODO: 不正な入力をチェックする
160+ final String[] ss = line.split("\\s+");
161+ int beg;
162+ int end;
163+ if(ss[0].indexOf("..") != -1) {
164+ final String[] ss2 = ss[0].split("\\.\\.");
165+ beg = Integer.parseInt(ss2[0].substring(2),16);
166+ end = Integer.parseInt(ss2[1].substring(2),16);
167+ } else {
168+ beg = end = Integer.parseInt(ss[0].substring(2),16);
169+ }
170+
171+ CharId ch = new CharId(map.get(ss[1]).id);
172+ for(int i=2; i < ss.length; i++) {
173+ if(ss[i].startsWith("#"))
174+ break;
175+ ch.add(map.get(ss[i]).id);
176+ }
177+
178+ for(int i=beg; i <= end; i++)
179+ chars[i] = ch;
180+ }
181+ } finally {
182+ rl.close();
183+ }
184+
185+ final FileMappedOutputStream fmos
186+ = new FileMappedOutputStream(outputDir+"/code2category", chars.length*4*2);
187+ try {
188+ for(CharId c : chars) fmos.putInt(c.id);
189+ for(CharId c : chars) fmos.putInt(c.mask);
190+ } finally {
191+ fmos.close();
192+ }
193+ }
194+}
\ No newline at end of file
--- tags/igo-0.4.0/src/net/reduls/igo/bin/Igo.java (nonexistent)
+++ tags/igo-0.4.0/src/net/reduls/igo/bin/Igo.java (revision 57)
@@ -0,0 +1,36 @@
1+package net.reduls.igo.bin;
2+
3+import java.io.IOException;
4+import net.reduls.igo.Tagger;
5+import net.reduls.igo.Morpheme;
6+import net.reduls.igo.util.ReadLine;
7+
8+/**
9+ * 形態素解析コマンド
10+ */
11+public final class Igo {
12+ public static void main(String[] args) throws IOException {
13+ if(!(args.length==1 || args.length==2) ||
14+ (args.length==2 && args[0].equals("-wakati")==false)) {
15+ System.err.println("Usage: java net.reduls.igo.bin.Igo [-wakati] <dictionary directory>");
16+ System.exit(1);
17+ }
18+ final String dicDir = args.length==2 ? args[1] : args[0];
19+ final boolean doWakati = args.length==2 ? true : false;
20+ final Tagger tagger = new Tagger(dicDir);
21+
22+ final ReadLine rl = new ReadLine(System.in);
23+ if(doWakati)
24+ for(String s=rl.read(); s != null; s=rl.read()) {
25+ for(String w : tagger.wakati(s))
26+ System.out.print(w+" ");
27+ System.out.println("");
28+ }
29+ else
30+ for(String s=rl.read(); s != null; s=rl.read()) {
31+ for(Morpheme m : tagger.parse(s))
32+ System.out.println(m.surface+"\t"+m.feature);
33+ System.out.println("EOS");
34+ }
35+ }
36+}
--- tags/igo-0.4.0/src/net/reduls/igo/bin/BuildDic.java (nonexistent)
+++ tags/igo-0.4.0/src/net/reduls/igo/bin/BuildDic.java (revision 57)
@@ -0,0 +1,47 @@
1+package net.reduls.igo.bin;
2+
3+import java.io.File;
4+import java.io.IOException;
5+import java.text.ParseException;
6+import net.reduls.igo.dictionary.Matrix;
7+import net.reduls.igo.dictionary.WordDic;
8+import net.reduls.igo.dictionary.CharCategory;
9+
10+/**
11+ * テキスト辞書からバイナリ辞書を作成するコマンド
12+ */
13+public final class BuildDic {
14+ public static void main(String[] args) {
15+ if(args.length != 3) {
16+ System.err.println("Usage: java net.reduls.igo.bin.BuildDic <output directory> <input directory> <encoding>");
17+ System.exit(1);
18+ }
19+ final String outputDir = args[0];
20+ final String inputDir = args[1];
21+ final String encoding = args[2];
22+
23+ new File(outputDir).mkdirs();
24+
25+ try {
26+ System.err.println("### Build word trie");
27+ WordDic.genWordIdMap(inputDir, outputDir, encoding);
28+
29+ System.err.println("### Build word dictionary");
30+ WordDic.genWordInfo(inputDir, outputDir, encoding);
31+
32+ System.err.println("### Build matrix");
33+ Matrix.build(inputDir, outputDir);
34+
35+ System.err.println("### Build char-category dictionary");
36+ CharCategory.build(inputDir, outputDir, encoding);
37+
38+ System.err.println("DONE");
39+ } catch (ParseException e) {
40+ System.err.println("[PARSE ERROR] "+e.getMessage());
41+ System.exit(1);
42+ } catch (IOException e) {
43+ System.err.println("[ERROR] "+e.getMessage());
44+ System.exit(1);
45+ }
46+ }
47+}
\ No newline at end of file
--- tags/igo-0.4.0/src/net/reduls/igo/trie/KeyStream.java (nonexistent)
+++ tags/igo-0.4.0/src/net/reduls/igo/trie/KeyStream.java (revision 57)
@@ -0,0 +1,44 @@
1+package net.reduls.igo.trie;
2+
3+/**
4+ * 文字列を文字のストリームとして扱うためのクラス。
5+ * readメソッドで個々の文字を順に読み込み、文字列の終端に達した場合には{@code Node.Chck.TERMINATE_CODE}が返される。
6+ * XXX: クラス名は不適切
7+ */
8+final class KeyStream implements Comparable<KeyStream> {
9+ private final CharSequence s;
10+ private int cur;
11+
12+ public KeyStream(CharSequence key) {
13+ s = key;
14+ cur = 0;
15+ }
16+
17+ public KeyStream(CharSequence key, int start) {
18+ s = key;
19+ cur = start;
20+ }
21+
22+ public int compareTo(KeyStream ks) {
23+ return rest().compareTo(ks.rest());
24+ }
25+
26+ /**
27+ * このメソッドは動作的には、{@code rest().startsWith(prefix.substring(beg, len))}、と等価。
28+ * ほんの若干だが、パフォーマンスを改善するために導入。
29+ * 簡潔性のためになくしても良いかもしれない。
30+ */
31+ public boolean startsWith(CharSequence prefix, int beg, int len) {
32+ if(s.length()-cur < len)
33+ return false;
34+
35+ for(int i=0; i < len; i++)
36+ if(s.charAt(cur+i) != prefix.charAt(beg+i))
37+ return false;
38+ return true;
39+ }
40+
41+ public String rest() { return s.subSequence(cur,s.length()).toString(); }
42+ public char read() { return eos() ? Node.Chck.TERMINATE_CODE : s.charAt(cur++); }
43+ public boolean eos() { return cur == s.length(); }
44+}
\ No newline at end of file
--- tags/igo-0.4.0/src/net/reduls/igo/trie/Searcher.java (nonexistent)
+++ tags/igo-0.4.0/src/net/reduls/igo/trie/Searcher.java (revision 57)
@@ -0,0 +1,123 @@
1+package net.reduls.igo.trie;
2+
3+import java.io.IOException;
4+import net.reduls.igo.util.FileMappedInputStream;
5+
6+/**
7+ * DoubleArray検索用のクラス
8+ */
9+public final class Searcher {
10+ private final int keySetSize;
11+ private final int[] base;
12+ private final char[] chck;
13+ private final int[] begs;
14+ private final short[] lens;
15+ private final String tail;
16+
17+ /**
18+ * 保存されているDoubleArrayを読み込んで、このクラスのインスタンスを作成する
19+ *
20+ * @params filepath DoubleArrayが保存されているファイルのパス
21+ * @throws IOException filepathで示されるファイルの読み込みに失敗した場合に送出される
22+ */
23+ public Searcher(String filepath) throws IOException {
24+ final FileMappedInputStream fmis = new FileMappedInputStream(filepath);
25+ try {
26+ final int nodeSz = fmis.getInt();
27+ final int tindSz = fmis.getInt();
28+ final int tailSz = fmis.getInt();
29+ keySetSize = tindSz;
30+ begs = fmis.getIntArray(tindSz);
31+ base = fmis.getIntArray(nodeSz);
32+ lens = fmis.getShortArray(tindSz);
33+ chck = fmis.getCharArray(nodeSz);
34+ tail = fmis.getString(tailSz);
35+ } finally {
36+ fmis.close();
37+ }
38+ }
39+
40+ /**
41+ * DoubleArrayに格納されているキーの数を返す
42+ * @return DoubleArrayに格納されているキー数
43+ */
44+ public int size() { return keySetSize; }
45+
46+ /**
47+ * キーを検索する
48+ *
49+ * @params key 検索対象のキー文字列
50+ * @return キーが見つかった場合はそのIDを、見つからなかった場合は-1を返す
51+ */
52+ public int search(CharSequence key) {
53+ int node = base[0];
54+ KeyStream in = new KeyStream(key);
55+
56+ for(char code=in.read();; code=in.read()) {
57+ final int idx = node+code;
58+ node = base[idx];
59+
60+ if(chck[idx]==code)
61+ if(node >= 0) continue;
62+ else if(in.eos() || keyExists(in,node)) return Node.Base.ID(node);
63+ return -1;
64+ }
65+ }
66+
67+ /**
68+ * common-prefix検索でキーが見つかった場合に呼び出されるコールバッククラスのインターフェース
69+ */
70+ public interface Callback {
71+ /**
72+ * eachCommonPrefixメソッドで該当するキーの部分文字列が見つかった都度に呼び出されるメソッド
73+ *
74+ * @params start 入力テキストの検索開始位置
75+ * @params offset 一致した部分文字列の終端位置
76+ * @params id 一致した部分文字列のID
77+ */
78+ public void call(int start, int offset, int id);
79+ }
80+
81+ /**
82+ * common-prefix検索を行う
83+ * 条件に一致するキーが見つかる度に、fn.call(...)メソッドが呼び出される
84+ *
85+ * @params key 検索対象のキー文字列
86+ * @params start 検索対象となるキー文字列の最初の添字
87+ * @params fn 一致を検出した場合に呼び出されるメソッドを定義したコールバッククラス
88+ */
89+ public void eachCommonPrefix(CharSequence key, int start, Callback fn) {
90+ int node = base[0];
91+ int offset=0;
92+ KeyStream in = new KeyStream(key, start);
93+
94+ for(char code=in.read();; code=in.read(),offset++) {
95+ final int terminalIdx = node + Node.Chck.TERMINATE_CODE;
96+
97+ if(chck[terminalIdx] == Node.Chck.TERMINATE_CODE) {
98+ fn.call(start, offset, Node.Base.ID(base[terminalIdx]));
99+ if(code==Node.Chck.TERMINATE_CODE)
100+ return;
101+ }
102+
103+ final int idx = node + code;
104+ node = base[idx];
105+ if(chck[idx] == code)
106+ if(node >= 0) continue;
107+ else call_if_keyIncluding(in, node, start, offset, fn);
108+ return;
109+ }
110+ }
111+
112+ private void call_if_keyIncluding(KeyStream in, int node, int start, int offset, Callback fn) {
113+ final int id = Node.Base.ID(node);
114+ if(in.startsWith(tail, begs[id], lens[id]))
115+ fn.call(start, offset+lens[id]+1, id);
116+ }
117+
118+ private boolean keyExists(KeyStream in, int node) {
119+ final int id = Node.Base.ID(node);
120+ final String s = tail.substring(begs[id], begs[id]+lens[id]);
121+ return in.rest().equals(s);
122+ }
123+}
\ No newline at end of file
--- tags/igo-0.4.0/src/net/reduls/igo/trie/Builder.java (nonexistent)
+++ tags/igo-0.4.0/src/net/reduls/igo/trie/Builder.java (revision 57)
@@ -0,0 +1,125 @@
1+package net.reduls.igo.trie;
2+
3+import java.io.IOException;
4+import java.util.List;
5+import java.util.ArrayList;
6+import net.reduls.igo.util.FileMappedOutputStream;
7+
8+/**
9+ * DoubleArrayの構築を行うクラス
10+ */
11+public final class Builder {
12+ private final ArrayList<KeyStream> ksList;
13+ private final AutoArray<Integer> base = new AutoArray<Integer>();
14+ private final AutoArray<Character> chck = new AutoArray<Character>();
15+ private final ArrayList<Integer> begs = new ArrayList<Integer>();
16+ private final ArrayList<Short> lens = new ArrayList<Short>();
17+ private final StringBuilder tail = new StringBuilder();
18+
19+ private Builder(List<String> keyList) {
20+ ksList = new ArrayList<KeyStream>(keyList.size());
21+
22+ // ソート and ユニーク
23+ java.util.Collections.sort(keyList);
24+ String prev=null;
25+ for(String k : keyList)
26+ if(k.equals(prev)==false)
27+ ksList.add(new KeyStream(prev=k));
28+ }
29+
30+ /**
31+ * キー文字列のリストから、DoubleArrayを構築する
32+ *
33+ * @params keyList DoubleArrayのキーとなる文字列のリスト. 破壊的に更新される
34+ * @return 構築済みDoubleArrayを有するBuilderインスタンス
35+ */
36+ public static Builder build(List<String> keyList) {
37+ Builder bld = new Builder(keyList);
38+ bld.buildImpl(new Allocator(), 0, bld.ksList.size(), 0);
39+ return bld;
40+ }
41+
42+ /**
43+ * 構築したDoubleArrayをファイルに保存する
44+ *
45+ * @params filepath DoubleArrayを保存するファイルのパス
46+ * @throws IOException filepathで示されたファイルへの書き込みに失敗した場合に送出される
47+ */
48+ public void save (String filepath) throws IOException {
49+ new ShrinkTail(tail,begs,lens).shrink();
50+
51+ int nodeSize = chck.size();
52+
53+ // 末尾の未使用部分を取り除く
54+ for(; nodeSize > 0 && chck.get(nodeSize-1) == Node.Chck.VACANT_CODE; nodeSize--);
55+ nodeSize += Node.Chck.CODE_LIMIT; // 検索時の範囲外アクセスを防ぐために、余白を設ける
56+
57+ final int total = 4*3 + nodeSize*6 + begs.size()*6 + tail.length()*2;
58+ final FileMappedOutputStream fmos = new FileMappedOutputStream(filepath, total);
59+ try {
60+ fmos.putInt(nodeSize);
61+ fmos.putInt(begs.size());
62+ fmos.putInt(tail.length());
63+
64+ // 4byte
65+ for(Integer n : begs) fmos.putInt(n);
66+ for(int i=0; i < nodeSize; i++)
67+ fmos.putInt(base.get(i, Node.Base.INIT_VALUE));
68+
69+ // 2byte
70+ for(Short n : lens) fmos.putShort(n);
71+ for(int i=0; i < nodeSize; i++)
72+ fmos.putChar(chck.get(i, Node.Chck.VACANT_CODE));
73+
74+ fmos.putString(tail.toString());
75+ } finally {
76+ fmos.close();
77+ }
78+ }
79+
80+ /**
81+ * 実際にDoubleArrayの構築を行うメソッド
82+ */
83+ private void buildImpl(Allocator alloca, int beg, int end, int rootIdx) {
84+ if(end-beg==1) {
85+ // これ以降は単一の遷移パスしかないので、まとめてTAILに挿入してしまう
86+ insertTail(ksList.get(beg), rootIdx);
87+ return;
88+ }
89+
90+ final List<Integer> endList = new ArrayList<Integer>();
91+ final List<Character> codeList = new ArrayList<Character>();
92+ char prev=Node.Chck.VACANT_CODE;
93+
94+ // rootIdxから遷移する文字を集める
95+ for(int i=beg; i < end; i++) {
96+ char cur = ksList.get(i).read();
97+
98+ if(prev != cur) {
99+ codeList.add(prev=cur);
100+ endList.add(i);
101+ }
102+ }
103+ endList.add(end);
104+
105+ // rootIdxから派生(遷移)するノードを設定し、その各ノードに対して再帰的に処理を繰り返す
106+ final int x = alloca.xCheck(codeList);
107+ for(int i=0; i < codeList.size(); i++)
108+ buildImpl(alloca, endList.get(i), endList.get(i+1), setNode(codeList.get(i),rootIdx,x));
109+ }
110+
111+ private int setNode(char code, int prev, int xNode) {
112+ final int next = xNode+code;
113+ base.set(prev,xNode,Node.Base.INIT_VALUE);
114+ chck.set(next,code, Node.Chck.VACANT_CODE);
115+ return next;
116+ }
117+
118+ private void insertTail(KeyStream in, int node) {
119+ base.set(node,Node.Base.ID(begs.size()),Node.Base.INIT_VALUE);
120+
121+ begs.add(tail.length());
122+ tail.append(in.rest());
123+ lens.add((short)in.rest().length());
124+ }
125+}
\ No newline at end of file
--- tags/igo-0.4.0/src/net/reduls/igo/trie/Allocator.java (nonexistent)
+++ tags/igo-0.4.0/src/net/reduls/igo/trie/Allocator.java (revision 57)
@@ -0,0 +1,69 @@
1+package net.reduls.igo.trie;
2+
3+import java.util.BitSet;
4+import java.util.List;
5+import java.util.ArrayList;
6+
7+/**
8+ * DoubleArray構築時に使用可能なノードを割り当てるためのクラス
9+ */
10+final class Allocator {
11+ private ArrayList<LinkNode> lnk = new ArrayList<LinkNode>();
12+ private BitSet bset = new BitSet();
13+
14+ public Allocator() {
15+ lnk.add(new LinkNode(0,0));
16+ resizeLink(Node.Chck.CODE_LIMIT*10);
17+ }
18+
19+ /**
20+ * 遷移に使用される文字のリストを受け取り、それらを割り当て可能なベースノードのインデックスを返す。
21+ *
22+ * @params codes 遷移文字リスト。昇順にソートされている必要がある
23+ * @return 引数の遷移文字群を割り当て可能なベースノードのインデックス
24+ */
25+ public int xCheck(List<Character> codes) {
26+ int cur = lnk.get(Node.Chck.CODE_LIMIT).next;
27+ for(;; cur=lnk.get(cur).next) {
28+ final int x = cur-codes.get(0);
29+ if(bset.get(x)==false && canAllocate(codes, x)) {
30+ bset.flip(x); // このベースノードは使用中だというマークをつける
31+
32+ for(int i=0; i < codes.size(); i++)
33+ alloc(x+codes.get(i));
34+ return x;
35+ }
36+ }
37+ }
38+
39+ private boolean canAllocate(List<Character> codes, int x) {
40+ for(int i=1; i < codes.size(); i++)
41+ if(x+codes.get(i) < lnk.size() && lnk.get(x+codes.get(i)).next==0)
42+ return false;
43+ return true;
44+ }
45+
46+ private void alloc(int node) {
47+ while(node >= lnk.size()-1) resizeLink(0);
48+
49+ lnk.get(lnk.get(node).prev).next = lnk.get(node).next;
50+ lnk.get(lnk.get(node).next).prev = lnk.get(node).prev;
51+ lnk.get(node).next = 0;
52+ }
53+
54+ private void resizeLink(int hint) {
55+ final int newSize = Math.max(hint, lnk.size()*2);
56+ lnk.get(lnk.size()-1).next = lnk.size();
57+
58+ for(int i=lnk.size(); i < newSize; i++)
59+ lnk.add(new LinkNode(i-1, i+1));
60+
61+ lnk.get(newSize-1).next = 0;
62+ }
63+
64+ private static class LinkNode {
65+ public LinkNode(int p, int n) { prev=p; next=n; }
66+ public int next;
67+ public int prev;
68+ }
69+}
\ No newline at end of file
--- tags/igo-0.4.0/src/net/reduls/igo/trie/Node.java (nonexistent)
+++ tags/igo-0.4.0/src/net/reduls/igo/trie/Node.java (revision 57)
@@ -0,0 +1,42 @@
1+package net.reduls.igo.trie;
2+
3+/**
4+ * DoubleArrayのノード用の定数などが定義されているクラス
5+ */
6+final class Node {
7+ /**
8+ * BASEノード用の定数およびメソッドが定義されているクラス
9+ */
10+ public static class Base {
11+ /**
12+ * BASEノードの初期値
13+ */
14+ public static final int INIT_VALUE = Integer.MIN_VALUE;
15+ /**
16+ * BASEノードに格納するID値をエンコードするためのメソッド
17+ * BASEノードに格納されているID値をデコードするためにも用いられる
18+ */
19+ public static int ID(int id) { return id*-1-1; }
20+ }
21+ /**
22+ * CHECKノード用の定数が定義されているクラス
23+ */
24+ public static class Chck {
25+ /**
26+ * 文字列の終端を表す文字定数
27+ *
28+ * この文字はシステムにより予約されており、辞書内の形態素の表層形および解析対象テキストに含まれていた場合の動作は未定義
29+ */
30+ public static final char TERMINATE_CODE=0;
31+ /**
32+ * CHECKノードが未使用だということを示すための文字定数
33+ *
34+ * この文字はシステムにより予約されており、辞書内の形態素の表層形および解析対象テキストに含まれていた場合の動作は未定義
35+ */
36+ public static final char VACANT_CODE=1;
37+ /**
38+ * 使用可能な文字の最大値
39+ */
40+ public static final char CODE_LIMIT=0xFFFF;
41+ }
42+}
\ No newline at end of file
--- tags/igo-0.4.0/src/net/reduls/igo/trie/AutoArray.java (nonexistent)
+++ tags/igo-0.4.0/src/net/reduls/igo/trie/AutoArray.java (revision 57)
@@ -0,0 +1,50 @@
1+package net.reduls.igo.trie;
2+
3+/**
4+ * java.util.ArrayListの拡張。
5+ * 非負の範囲外アクセスがあった場合に自動的にリストの拡張が行われる。
6+ */
7+final class AutoArray<E> extends java.util.ArrayList<E> {
8+ /**
9+ * 基本的な動作はjava.util.ArrayList.getに準ずる。
10+ *
11+ * 非負の範囲外アクセスがあった場合は、自動的にリストが拡張され、デフォルト値が返される。
12+ * 拡張された領域にはデフォルト値が格納される。
13+ * 添字として負数が指定された場合の動作は未定義。
14+ *
15+ * @params index リストの添字
16+ * @params defaultValue リスト要素のデフォルト値
17+ * @return 添字に対応する要素
18+ */
19+ public E get(int index, E defaultValue) {
20+ try {
21+ return get(index);
22+ } catch(IndexOutOfBoundsException e) {
23+ for(int i=size(); i <= index*2; i++)
24+ add(defaultValue);
25+ return get(index);
26+ }
27+ }
28+
29+ /**
30+ * 基本的な動作はjava.util.ArrayList.setに準ずる。
31+ *
32+ * 非負の範囲外アクセスがあった場合は、十分なサイズにまで自動的にリストが拡張される。
33+ * 拡張された領域にはデフォルト値が格納される。
34+ * 添字として負数が指定された場合の動作は未定義。
35+ *
36+ * @params index リストの添字
37+ * @params element 添字の位置に格納する値
38+ * @params defaultValue リスト要素のデフォルト値
39+ * @return 添字の位置に以前格納されていた値
40+ */
41+ public E set(int index, E element, E defaultValue) {
42+ try {
43+ return set(index,element);
44+ } catch(IndexOutOfBoundsException e) {
45+ for(int i=size(); i <= index*2; i++)
46+ add(defaultValue);
47+ return set(index,element);
48+ }
49+ }
50+}
\ No newline at end of file
--- tags/igo-0.4.0/src/net/reduls/igo/trie/ShrinkTail.java (nonexistent)
+++ tags/igo-0.4.0/src/net/reduls/igo/trie/ShrinkTail.java (revision 57)
@@ -0,0 +1,69 @@
1+package net.reduls.igo.trie;
2+
3+import java.util.ArrayList;
4+
5+/**
6+ * TAIL配列(文字列)の圧縮を行うクラス
7+ * TAILに格納されている文字列群の内で、末尾部分が重複するものは、同じ領域を使用するようにする。
8+ */
9+final class ShrinkTail {
10+ private final StringBuilder tail;
11+ private final ArrayList<Integer> begs;
12+ private final ArrayList<Short> lens;
13+
14+ /**
15+ * 圧縮対象となるTAIL配列および、TAIL配列へのインデックスを渡してインスタンスを初期化する。
16+ * 引数に渡した各オブジェクトはshrinkメソッドの呼び出しに伴い、破壊的に更新される。
17+ */
18+ public ShrinkTail(StringBuilder tail, ArrayList<Integer> begs, ArrayList<Short> lens) {
19+ this.tail = tail;
20+ this.begs = begs;
21+ this.lens = lens;
22+ }
23+
24+ public void shrink() {
25+ // TAILに格納されている文字列群を、その末尾から比較してソートする
26+ final ArrayList<TailString> sorted = new ArrayList<TailString>(begs.size());
27+ for(int i=0; i < begs.size(); i++)
28+ sorted.add(new TailString(i));
29+ java.util.Collections.sort(sorted);
30+
31+ // 新しいTAILを用意する
32+ // その際に、末尾部分が重複する文字列同士は、領域を共有するようにする
33+ final StringBuilder newTail = new StringBuilder();
34+ for(int i=0; i < sorted.size(); i++) {
35+ final TailString ts = sorted.get(i);
36+
37+ int begIndex = newTail.length();
38+ if(i > 0 && sorted.get(i-1).s.endsWith(ts.s))
39+ begIndex -= ts.s.length(); // 末尾文字列を共有する
40+ else
41+ newTail.append(ts.s); // 新しく追加する
42+
43+ // TAIL配列へのポインタを更新する
44+ begs.set(ts.id, begIndex);
45+ lens.set(ts.id, (short)ts.s.length());
46+ }
47+
48+ tail.replace(0, tail.length(), newTail.toString());
49+ }
50+
51+ private class TailString implements Comparable<TailString> {
52+ public final int id;
53+ public final String s;
54+
55+ public TailString(int id) {
56+ this.id = id;
57+ this.s = tail.substring(begs.get(id), begs.get(id)+lens.get(id));
58+ }
59+
60+ // TailStringを文字列の末尾から順に比較する
61+ public int compareTo(TailString ts) {
62+ for(int i=s.length()-1, j=ts.s.length()-1;; i--, j--)
63+ if(i < 0) return j < 0 ? 0 : 1;
64+ else if(j < 0) return -1;
65+ else if(s.charAt(i) > ts.s.charAt(j)) return -1;
66+ else if(s.charAt(i) < ts.s.charAt(j)) return 1;
67+ }
68+ }
69+}
\ No newline at end of file
--- tags/igo-0.4.0/src/net/reduls/igo/Tagger.java (nonexistent)
+++ tags/igo-0.4.0/src/net/reduls/igo/Tagger.java (revision 57)
@@ -0,0 +1,140 @@
1+package net.reduls.igo;
2+
3+import java.io.IOException;
4+import java.io.FileNotFoundException;
5+import java.util.List;
6+import java.util.ArrayList;
7+import net.reduls.igo.dictionary.Matrix;
8+import net.reduls.igo.dictionary.WordDic;
9+import net.reduls.igo.dictionary.Unknown;
10+import net.reduls.igo.dictionary.ViterbiNode;
11+
12+/**
13+ * 形態素解析を行うクラス
14+ */
15+public final class Tagger {
16+ private static final ArrayList<ViterbiNode> BOS_NODES = new ArrayList<ViterbiNode>(1);
17+ static {
18+ BOS_NODES.add(ViterbiNode.makeBOSEOS());
19+ }
20+
21+ private final WordDic wdc;
22+ private final Unknown unk;
23+ private final Matrix mtx;
24+
25+ /**
26+ * バイナリ辞書をもとに、この形態素解析器のインスタンスを作成する
27+ *
28+ * @params バイナリ辞書があるディレクトリ
29+ * @throws FileNotFoundException 間違ったディレクトリが指定された場合に送出される
30+ * @throws IOException その他の入出力エラーが発生した場合に送出される
31+ */
32+ public Tagger(String dataDir) throws FileNotFoundException, IOException {
33+ wdc = new WordDic(dataDir);
34+ unk = new Unknown(dataDir);
35+ mtx = new Matrix(dataDir);
36+ }
37+
38+ /**
39+ * 形態素解析を行う
40+ *
41+ * @params text 解析対象テキスト
42+ * @return 解析結果の形態素のリスト
43+ */
44+ public List<Morpheme> parse(CharSequence text) {
45+ return parse(text, new ArrayList<Morpheme>(text.length()/2));
46+ }
47+
48+ /**
49+ * 形態素解析を行う
50+ *
51+ * @params text 解析対象テキスト
52+ * @params result 解析結果の形態素が追加されるリスト
53+ * @return 解析結果の形態素リスト. {@code parse(text,result)=result}
54+ */
55+ public List<Morpheme> parse(CharSequence text, List<Morpheme> result) {
56+ for(ViterbiNode vn=parseImpl(text); vn!=null; vn=vn.prev) {
57+ final String surface = text.subSequence(vn.start, vn.start+vn.length).toString();
58+ final String feature = wdc.wordData(vn.wordId);
59+ result.add(new Morpheme(surface, feature, vn.start));
60+ }
61+ return result;
62+ }
63+
64+ /**
65+ * 分かち書きを行う
66+ *
67+ * @params text 分かち書きされるテキスト
68+ * @return 分かち書きされた文字列のリスト
69+ */
70+ public List<String> wakati(CharSequence text) {
71+ return wakati(text, new ArrayList<String>(text.length()/2));
72+ }
73+
74+ /**
75+ * 分かち書きを行う
76+ *
77+ * @params text 分かち書きされるテキスト
78+ * @params result 分かち書き結果の文字列が追加されるリスト
79+ * @return 分かち書きされた文字列のリスト. {@code wakati(text,result)=result}
80+ */
81+ public List<String> wakati(CharSequence text, List<String> result) {
82+ for(ViterbiNode vn=parseImpl(text); vn!=null; vn=vn.prev)
83+ result.add(text.subSequence(vn.start, vn.start+vn.length).toString());
84+ return result;
85+ }
86+
87+ private ViterbiNode parseImpl(CharSequence text) {
88+ final int len = text.length();
89+ final ArrayList<ArrayList<ViterbiNode>> nodesAry = new ArrayList<ArrayList<ViterbiNode>>(len+1);
90+ final ArrayList<ViterbiNode> perResult = new ArrayList<ViterbiNode>();
91+
92+ nodesAry.add(BOS_NODES);
93+ for(int i=1; i <= len; i++)
94+ nodesAry.add(new ArrayList<ViterbiNode>());
95+
96+ for(int i=0; i < len; i++, perResult.clear()) {
97+ if(nodesAry.get(i).isEmpty()==false) {
98+ wdc.search(text, i, perResult); // 単語辞書から形態素を検索
99+ unk.search(text, i, wdc, perResult); // 未知語辞書から形態素を検索
100+
101+ final ArrayList<ViterbiNode> prevs = nodesAry.get(i);
102+ for(int j=0; j < perResult.size(); j++) {
103+ final ViterbiNode vn = perResult.get(j);
104+ if(vn.isSpace)
105+ nodesAry.get(i+vn.length).addAll(prevs);
106+ else
107+ nodesAry.get(i+vn.length).add(setMincostNode(vn,prevs));
108+ }
109+ }
110+ }
111+
112+ ViterbiNode cur = setMincostNode(ViterbiNode.makeBOSEOS(), nodesAry.get(len)).prev;
113+
114+ // reverse
115+ ViterbiNode head = null;
116+ while(cur.prev != null) {
117+ final ViterbiNode tmp = cur.prev;
118+ cur.prev = head;
119+ head = cur;
120+ cur = tmp;
121+ }
122+ return head;
123+ }
124+
125+ private ViterbiNode setMincostNode(ViterbiNode vn, ArrayList<ViterbiNode> prevs) {
126+ final ViterbiNode f = vn.prev = prevs.get(0);
127+ vn.cost = f.cost + mtx.linkCost(f.rightId, vn.leftId);
128+
129+ for(int i=1; i < prevs.size(); i++) {
130+ final ViterbiNode p = prevs.get(i);
131+ final int cost = p.cost + mtx.linkCost(p.rightId, vn.leftId);
132+ if(cost < vn.cost) {
133+ vn.cost = cost;
134+ vn.prev = p;
135+ }
136+ }
137+ vn.cost += wdc.cost(vn.wordId);
138+ return vn;
139+ }
140+}
--- tags/igo-0.4.0/src/net/reduls/igo/Morpheme.java (nonexistent)
+++ tags/igo-0.4.0/src/net/reduls/igo/Morpheme.java (revision 57)
@@ -0,0 +1,25 @@
1+package net.reduls.igo;
2+
3+/**
4+ * 形態素クラス
5+ */
6+public final class Morpheme {
7+ /**
8+ * 形態素の表層形
9+ */
10+ public final String surface;
11+ /**
12+ * 形態素の素性
13+ */
14+ public final String feature;
15+ /**
16+ * テキスト内での形態素の出現開始位置
17+ */
18+ public final int start;
19+
20+ public Morpheme(String surface, String feature, int start) {
21+ this.surface = surface;
22+ this.feature = feature;
23+ this.start = start;
24+ }
25+}
--- tags/igo-0.4.0/src/net/reduls/igo/util/FileMappedInputStream.java (nonexistent)
+++ tags/igo-0.4.0/src/net/reduls/igo/util/FileMappedInputStream.java (revision 57)
@@ -0,0 +1,84 @@
1+package net.reduls.igo.util;
2+
3+import java.io.IOException;
4+import java.io.FileInputStream;
5+import java.nio.ByteBuffer;
6+import java.nio.ByteOrder;
7+import java.nio.channels.FileChannel;
8+
9+/**
10+ * ファイルにマッピングされた入力ストリーム
11+ * net.reduls.igo以下のパッケージではファイルからバイナリデータを取得する場合、必ずこのクラスを使うようになっている
12+ */
13+public final class FileMappedInputStream {
14+ private final FileChannel cnl;
15+ private int cur=0;
16+
17+ /**
18+ * 入力ストリームを作成する
19+ *
20+ * @params filepath マッピングするファイルのパス
21+ */
22+ public FileMappedInputStream(String filepath) throws IOException {
23+ cnl = new FileInputStream(filepath).getChannel();
24+ }
25+
26+ public int getInt() throws IOException {
27+ return map(4).getInt();
28+ }
29+
30+ public int[] getIntArray(int elementCount) throws IOException {
31+ final int[] ary = new int[elementCount];
32+ map(elementCount*4).asIntBuffer().get(ary);
33+ return ary;
34+ }
35+
36+ public static int[] getIntArray(String filepath) throws IOException {
37+ final FileMappedInputStream fmis = new FileMappedInputStream(filepath);
38+ try {
39+ return fmis.getIntArray(fmis.size()/4);
40+ } finally {
41+ fmis.close();
42+ }
43+ }
44+
45+ public short[] getShortArray(int elementCount) throws IOException {
46+ final short[] ary = new short[elementCount];
47+ map(elementCount*2).asShortBuffer().get(ary);
48+ return ary;
49+ }
50+
51+ public char[] getCharArray(int elementCount) throws IOException {
52+ final char[] ary = new char[elementCount];
53+ map(elementCount*2).asCharBuffer().get(ary);
54+ return ary;
55+ }
56+
57+ public String getString(int elementCount) throws IOException {
58+ return map(elementCount*2).asCharBuffer().toString();
59+ }
60+
61+ public static String getString(String filepath) throws IOException {
62+ final FileMappedInputStream fmis = new FileMappedInputStream(filepath);
63+ try {
64+ return fmis.getString(fmis.size()/2);
65+ } finally {
66+ fmis.close();
67+ }
68+ }
69+
70+ public int size() throws IOException {
71+ return (int)cnl.size();
72+ }
73+
74+ public void close() {
75+ try {
76+ cnl.close();
77+ } catch (IOException e) {}
78+ }
79+
80+ private ByteBuffer map(int size) throws IOException {
81+ cur += size;
82+ return cnl.map(FileChannel.MapMode.READ_ONLY, cur-size, size).order(ByteOrder.nativeOrder());
83+ }
84+}
\ No newline at end of file
--- tags/igo-0.4.0/src/net/reduls/igo/util/FileMappedOutputStream.java (nonexistent)
+++ tags/igo-0.4.0/src/net/reduls/igo/util/FileMappedOutputStream.java (revision 57)
@@ -0,0 +1,46 @@
1+package net.reduls.igo.util;
2+
3+import java.io.File;
4+import java.io.IOException;
5+import java.io.RandomAccessFile;
6+import java.nio.MappedByteBuffer;
7+import java.nio.ByteOrder;
8+import java.nio.channels.FileChannel;
9+
10+/**
11+ * ファイルにマッピングされた出力ストリーム
12+ * net.reduls.igo以下のパッケージではファイルにバイナリデータを出力する場合、必ずこのクラスを使うようになっている
13+ */
14+public final class FileMappedOutputStream {
15+ private final MappedByteBuffer mbb;
16+
17+ /**
18+ * サイズを指定して出力ストリームを作成する
19+ *
20+ * @params filepath マッピングされるファイルのパス
21+ * @params size ファイル(=出力するデータ)のサイズ。このサイズを超えて出力が行われた場合の動作は未定義。
22+ */
23+ public FileMappedOutputStream(String filepath, int size) throws IOException {
24+ new File(filepath).delete();
25+
26+ final FileChannel cnl = new RandomAccessFile(filepath,"rw").getChannel();
27+ try {
28+ mbb = cnl.map(FileChannel.MapMode.READ_WRITE, 0, size);
29+ mbb.order(ByteOrder.nativeOrder());
30+ } finally {
31+ cnl.close();
32+ }
33+ }
34+
35+ public void putInt(int value) throws IOException { mbb.putInt(value); }
36+ public void putChar(char value) throws IOException { mbb.putChar(value); }
37+ public void putShort(short value) throws IOException { mbb.putShort(value); }
38+ public void putString(String src) throws IOException {
39+ mbb.asCharBuffer().put(src);
40+ mbb.position(mbb.position()+src.length()*2);
41+ }
42+
43+ public void close() {
44+ mbb.force();
45+ }
46+}
\ No newline at end of file
--- tags/igo-0.4.0/src/net/reduls/igo/util/ReadLine.java (nonexistent)
+++ tags/igo-0.4.0/src/net/reduls/igo/util/ReadLine.java (revision 57)
@@ -0,0 +1,77 @@
1+package net.reduls.igo.util;
2+
3+import java.io.InputStream;
4+import java.io.LineNumberReader;
5+import java.io.FileInputStream;
6+import java.io.IOException;
7+import java.io.EOFException;
8+import java.io.InputStreamReader;
9+
10+/**
11+ * 行読み込み用のクラス
12+ */
13+public class ReadLine {
14+ private final LineNumberReader br;
15+
16+ /**
17+ * 入力ストリームを元に、このクラスのインスタンスを作成する
18+ *
19+ * @throws IOException 入出力エラーが発生した場合に送出される
20+ */
21+ public ReadLine(InputStream in) throws IOException {
22+ br = new LineNumberReader(new InputStreamReader(in));
23+ }
24+
25+ /**
26+ * ファイルを元に、このクラスのインスタンスを作成する
27+ *
28+ * @params filepath 読み込むファイルのパス
29+ * @params encoding 読み込むファイルのエンコーディング
30+ * @throws IOException 入出力エラーが発生した場合に送出される
31+ */
32+ public ReadLine(String filepath, String encoding) throws IOException {
33+ br = new LineNumberReader(new InputStreamReader(new FileInputStream(filepath), encoding));
34+ }
35+
36+ /**
37+ * 読み込みを終了する
38+ */
39+ public void close() {
40+ try {
41+ br.close();
42+ } catch (IOException e) {}
43+ }
44+
45+ /**
46+ * 一行読み込む
47+ *
48+ * @return 読み込んだ文字列. ストリームの終端に達してしる場合は、nullを返す
49+ * @throws IOException 入出力エラーが発生した場合に送出される
50+ */
51+ public String read() throws IOException {
52+ return br.readLine();
53+ }
54+
55+ /**
56+ * 一行読み込む
57+ *
58+ * @return 読み込んだ文字列
59+ * @throws EOFException ストリームの終端に達している場合に送出される
60+ * @throws IOException 入出力エラーが発生した場合に送出される
61+ */
62+ public String readEof() throws IOException, EOFException {
63+ final String s=br.readLine();
64+ if(s==null)
65+ throw new EOFException();
66+ return s;
67+ }
68+
69+ /**
70+ * これまでに読み込んだ行数を返す
71+ *
72+ * @return これまでに読み込んだ行数
73+ */
74+ public int lineNumber() {
75+ return br.getLineNumber();
76+ }
77+}
\ No newline at end of file
--- tags/igo-0.4.0/COPYING (nonexistent)
+++ tags/igo-0.4.0/COPYING (revision 57)
@@ -0,0 +1,21 @@
1+The MIT License
2+
3+Copyright (c) 2010 Takeru Ohta <phjgt308@ybb.ne.jp>
4+
5+Permission is hereby granted, free of charge, to any person obtaining a copy
6+of this software and associated documentation files (the "Software"), to deal
7+in the Software without restriction, including without limitation the rights
8+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9+copies of the Software, and to permit persons to whom the Software is
10+furnished to do so, subject to the following conditions:
11+
12+The above copyright notice and this permission notice shall be included in
13+all copies or substantial portions of the Software.
14+
15+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
21+THE SOFTWARE.
旧リポジトリブラウザで表示