id:d-kamiさんから改良版Make2Gram付きトラックバックを頂きました(連絡方法がわからんのでトラックバックで - マイペースなプログラミング日記)(はてなダイヤリーから移転前)。d-kamiさん、ありがとうございます。
上記のページにあるコードから、TreeMapやsubstringを用いたbigramの切り出し・カウント方法などを学ばせて頂きました。
さて、今回の実装その2は以下の機能を加えました。
今回はN-gramでテキストを分解します。N-gram法とは対象の文字列を一定のN文字単位で分解し、それの出現頻度を求める方法です。これによって、検索エンジンに使われる転置インデックスを作成したいと思います。転置インデックスの作成方法にはN-gramの他に形態素解析があります。両者の性能の長短は全文検索 - Wikipediaに詳しく載っています。
さて、まずは文字列を2単語に切り分けるプログラムを作成しました。データ構造は単純にArrayListで、出現頻度も求めていません。
import java.io.*;
import java.util.*;
/**
* N-gram法
*/
public class Make2gram {
public static void main(String[] args) {
final short nsepa = 1; // 2gram
String line;
ArrayList<stringBuffer> filelist = new ArrayList<stringBuffer>();
ArrayList<stringBuffer> bigram = new ArrayList<stringBuffer>();
if (args.length < 1) { // コマンドライン引数の数
System.out.println("How to use: java Make2gram [filename]");
System.exit(1);
}
try {
BufferedReader br = new BufferedReader(new FileReader(args[0]));
while ((line = br.readLine()) != null) {
//System.out.println(line);
filelist.add(new StringBuffer(line)); // 入力ファイルは一行=一要素として格納
}
br.close();
}
catch (Exception e) {
System.err.println("[main] : " + e.toString());
}
for (Iterator it = filelist.iterator(); it.hasNext(); ) {
StringBuffer str = (StringBuffer) it.next();
int lm = str.length() - nsepa;
for (int i = 0; i < lm; i++) {
StringBuffer bi = new StringBuffer(4); // 4Byte(2文字)分の容量(Javaの内部文字コードはUnicode)
bi.append(str.charAt(i)); // append():文字列の末尾に追加
bi.append(str.charAt(i+1));
bigram.add(bi);
//System.out.print(str.charAt(i));
//System.out.println(str.charAt(i+1));
}
}
// 2-gramを表示
for (Iterator it = bigram.iterator(); it.hasNext(); ) {
System.out.println(it.next());
}
}
}
検索された文書は「更新順」「ファイル名順」「文書のタイトル順」などにソートされる。
一般的な検索エンジンでは独自のランク付けルールも適用し「重要度」などと呼んでいるものもある。
検索
索さ
され
れた
た文
文書
書は
は「
「更
更新
新順
順」
」「
…＜省略＞…
javaのArrayListのコンストラクタにはオーバーロードで幾つかの種類がありますが、その一つに以下のようなものがあります。
ArrayList(int initialCapacity) 指定された初期サイズで空のリストを作成します。 Java 2 Platform SE 1.3: クラス ArrayList
ArrayListは動的に容量を確保しますが、そのメモリ割り当て処理はCPUにそれなりの負荷を与えます。そこで、予め格納する容量が分かっていればコンストラクタの引数で初期容量を指定することで、その負荷の掛かる処理を事前に省くことが出来、その結果、処理時間の短縮につながります。
ちなみに、このint initialCapacityの容量の単位はコレクションの要素数です(2008/3/7修正)。
以下に初期容量を指定したときとしないときのでの処理時間を計るJavaのソースコードを示します。
import java.io.*; // for BufferedReader
import java.util.*; // for ArrayList
public class DumpFile {
/**
* @param args : 入力ファイル名
*/
public static void main(String[] args) {
String line;
ArrayList filelist = new ArrayList();
ArrayList mlist = new ArrayList(4000000); // 計測用リスト：4898304バイトのファイル
if (args.length < 1) { // コマンドライン引数の数
System.out.println("How to use: java DumpFile [filename]");
System.exit(1);
}
try {
BufferedReader br = new BufferedReader(new FileReader(args[0]));
while ((line = br.readLine()) != null) {
filelist.add(line); // 入力ファイルは一行=一要素として格納
//System.out.println(line);
}
br.close();
}
catch (Exception e) {
System.err.println(e.toString());
}
int n = filelist.size();
long start = System.currentTimeMillis(); // 処理時間の計測開始
for (int i = 0; i < n; i++) {
//System.out.println(list.get(i));
mlist.add(filelist.get(i));
}
long end = System.currentTimeMillis();
System.out.println("実行時間:" + (end - start) + "ms");
/*for (int i = 0; i < n; i++) {
System.out.println(mlist.get(i));
}*/
}
}
入力ファイルは日本語単語405,000語で4898304Byteです。
…< 中略>…
楽観
楽観さ
楽観し
楽観した
楽観したら
楽観したり
楽観したろう
楽観しちゃ
…< 中略>…
結果は、
mlistに対して初期容量を指定しない場合：17ms mlistに対して初期容量を指定した 場合：8ms
となり、今回の場合は処理時間を1/2に短縮できていることが分かりました。 ちなみに、ArrayListのメモリ動的割り当て容量は、現在の容量の1.5倍のようです。
int newCapacity = (oldCapacity * 3)/2 + 1; ArrayList#ensureCapacityメソッド内の一文 - ArrayList.java 1.56 06/04/21
1．コンストラクタでインスタンス容量を指定するものとして、StringBufferクラスがあります。これも、
StringBuffer sb = new StringBuffer(40000); // 40KByteを確保
のように指定します。
これによって、append()やinsert()によって予め割り当てられたバッファを越す際に呼び出されるメモリ動的割り当て処理を軽減することが出来ます。
2．ArrayListのコンストラクタに引数を指定しない場合は10個の要素を持った配列が作られます。
/** * Constructs an empty list with an initial capacity of ten. */ public ArrayList() { this(10); } ArrayList.java 1.56 06/04/21
RubyのコードをJavaに書き直す際に注意する相違点が幾つかあったので、そのうちの一つを挙げてみます。特に文字列関係は色々やりにくいです。
a = "4321"
p a[4] #=> nil
Rubyでは文字を[]で指すとき終端文字の次の添え字を指すとnilを返します。これをCで言う文字列の終端文字'\0'のように考え、if文などの判定に用いることが出来ます。
対して、Javaで同じような書式で書こうものなら、
public class Test {
public static void main(String[] args) {
String str = "abcdef";
char[] arr = str.toCharArray(); // String型をchar型の配列に変換
System.out.println(arr);
System.out.println(str.length()+ " == " + arr.length);
try {
System.out.println(arr[6]);
} catch (java.lang.ArrayIndexOutOfBoundsException e) {
System.out.println("キャッチ：" + e);
- }
try {
System.out.println(str.charAt(6));
} catch (java.lang.StringIndexOutOfBoundsException e) {
System.out.println("キャッチ：" + e);
}
// 最後の文字を知るためには
System.out.println(str.charAt(str.length() - 1));
}
}
のように例外でキャッチしなければなりません。
6 == 6
abcdef
キャッチ：java.lang.ArrayIndexOutOfBoundsException: 6
キャッチ：java.lang.StringIndexOutOfBoundsException: String index out of range: 6
f
まぁ、str.length()を用いて文字列長でcharAtで指す文字が文字列の末尾かどうかを判定することで制御すればよいまでの話かもしれません。
今回はとあるアルゴリズムを移植上、気づきが色々あったのでこうした機会に言語仕様に対する理解を深めていきたいです。
統合開発環境のEclipseでJavaのオセロプログラム(講義の課題)を制作中に一度クラス図を作成しようと試みました。使用プラグインはAmaterasUMLでこちらのサイト(軽量なUMLプラグインAmaterasUML (1/4) - @IT)を参考にしながらインストールを進めました。 さて、数あるUMLデザイナの中でこのプラグインのアドバンテージの一つはJavaクラスの継承関係などを包含したクラス図をソースコードから生成できる点にあると私は考えます。 その作り方は、まず「ファイル」→「新規」→「その他」から「AmaterasUML」→「クラス図」と選択してクラス図ファイルを作成し、そのファイルをダブルクリックしクラス図エディタを起動します。その上にクラスファイルをドラックアンドドロップすれば、そのクラスのクラス図が作成されます。また継承関係などを表したい場合は、その関係のクラスを選択した上でドラッグ＆ドロップすればOK。下図にその使用状況を示します。 
ちなみに、これによって作成された図は画像形式でエクスポートできます。 人にプログラムの構造の説明する際に役立つので重宝しています。