2008-03

今回実装したことは、

• IndexRecordクラスにフィールド更新用のメソッドやハッシュフィールドを追加（今後改善の必要大）。
• 検索語を含んでいるファイルをピックアップする（色々と無駄な部分あり）。

辺りです。

後述に現在の問題点とその解決案を考えてみましたが、先ずはソースコードと実行結果(デバッグプリント)を示します。

追記：こちらに→ 検索エンジンを実装 (4)AND演算 - Yukun's Blog 完成版を書きましたので、そちらをご覧ください。↓以下、黒歴史(>_<)↓

IndexRecord.java

import java.util.ArrayList;
import java.util.TreeMap;

public class IndexRecord {
  // 総出現回数
  Integer count;
  // 出現したファイルID
  ArrayList<integer> file_ids;
  // ファイル内の出現位置(ファイルの先頭からのオフセット)
  ArrayList<integer> word_poses;
  // ファイルIDごとに出現数をカウント<ファイルid, 出現数>
  TreeMap<integer, Integer> idcntMap;

  private IndexRecord() {}
  public IndexRecord(int id, int pos) {
    count = 1;
    file_ids = new ArrayList<integer>();
    file_ids.add(id);
    word_poses = new ArrayList<integer>();
    word_poses.add(pos);
    idcntMap = new TreeMap<integer, Integer>();
    idcntMap.put(id, 1);
  }

  public void renewal(int id, int pos) {
    count++;
    file_ids.add(id);
    word_poses.add(pos);

    if(idcntMap.containsKey(id)){
      Integer idcnt = idcntMap.get(id);
      idcnt++;
      idcntMap.put(id, idcnt);
    } else {
      idcntMap.put(id, 1);
    }
  }

  public String toString() {
    StringBuffer sb = new StringBuffer();
    sb.append(count);
    for(int i = 0; i < file_ids.size(); i++){
      sb.append(" (" + file_ids.get(i) + ", " + word_poses.get(i) + ")");
    }
    sb.append(" "+ idcntMap);
    return sb.toString();
  }
}

Make2Gram.java

import java.io.File;
import java.io.FileReader;
import java.io.BufferedReader;
import java.io.IOException;

import java.util.ArrayList;
import java.util.TreeMap;

public class Make2Gram{
  public static final boolean DEBUG = true; // デバッグ用フラグ
  public static void main(String[] args) throws IOException{
    if(args.length == 0){
      System.out.println("引数にディレクトリ名を指定してください");
      System.exit(1);
    }
    int N = 2; // bigram

    // http://sattontanabe.blog86.fc2.com/blog-entry-55.html
    // Java 再帰的にファイルを検索 ／ Chat&Messenger
    // のクラスFileSearchを使用しています
    FileSearch search = new FileSearch();
    File[] files = search.listFiles(args[0], null); // 全てのファイルを取得
    // ファイルIDとパスの対応表
    TreeMap<integer, File> fileMap = new TreeMap<integer, File>();
    ArrayList<string> docs = new ArrayList<string>();

    for(int i=0; i < files.length; i++){
      fileMap.put(i, files[i].getAbsoluteFile());
      BufferedReader br = new BufferedReader(new FileReader(files[i]));
      StringBuilder sb = new StringBuilder();
      String line;
      while((line = br.readLine()) != null)
        sb.append(line);
      br.close(); // ファイル内容(RAW)を格納
      String text = sb.toString(); // ファイルの内容 改行抜き
      docs.add(text);
    }

    //テキストの部分文字列とそのIndexRecordクラスを関連付けるMap
    //TreeMapなのでMapのキーにした部分文字列でソートされる
    TreeMap<string, IndexRecord> gramMap = new TreeMap<string, IndexRecord>();
    for(int i = 0; i < fileMap.size(); i++){
      // ファイルごとの処理
      String text = docs.get(i);
      for(int j = 0; j < text.length() - N; j++){
        //テキストからN文字取り出す
        String gram = text.substring(j, j + N);
        if(gramMap.containsKey(gram)){
          //gramMapに登録されてる文字列ならカウント等を増やす
          IndexRecord ir = gramMap.get(gram);
          ir.renewal(i, j);
          gramMap.put(gram, ir);
        }else{
          //gramMapに登録されていない文字列なら登録
          gramMap.put(gram, new IndexRecord(i, j));
        }
      }
    }

    //for(String part : gramMap.keySet())
      //System.out.printf("%s : %sn", part, gramMap.get(part));
    String input = "N文字"; // 検索語(e.g.)
    if(DEBUG) System.out.println("input #=> "+ input);
    String[] swords = new String[(input.length()+1)/2];
    boolean odd = false; // 文字列長の偶奇判定
    if (input.length() < 2){
      System.out.println("2文字未満の処理は未実装");
      System.exit(1);
    }
    // 検索文字列をN文字単位に分割
    for(int i = 0, j = 0; i < input.length()-N; i += N, j++){
      swords[j] = input.substring(i, i+N);
    }
    if ((input.length() & 1) == 1){ // 文字列長が奇数
      swords[swords.length-1] = input.substring(input.length()-N, input.length());
      odd = true;
    }
    if(DEBUG){
      System.out.print("swords #=> ");
      for(String part : swords) System.out.print(part +" ");
      System.out.println();
    } // [N文, 文字](e.g.)
    TreeMap<integer, Integer> id_per_cnt = new TreeMap<integer, Integer>();
    // N文字単位のIndexRecordを格納する配列
    IndexRecord[] ng_records = new IndexRecord[swords.length];
    // 2文字ごとにgramMapと照合
    for(int i = 0; i < swords.length; i++){
      if(!gramMap.containsKey(swords[i])) {
        System.out.println("  検索語：【"+ input +"】はありません。");
        System.exit(1);
      }
      IndexRecord ir = gramMap.get(swords[i]);
      ng_records[i] = ir;
      TreeMap<integer, Integer> _idcntMap = ir.idcntMap;
      for(Integer id : _idcntMap.keySet()){
        if(id_per_cnt.containsKey(id)){
          int cnt = id_per_cnt.get(id);
          cnt += _idcntMap.get(id);
          id_per_cnt.put(id, cnt);
        } else {
          id_per_cnt.put(id, _idcntMap.get(id));
        }
      }
      if(DEBUG) System.out.println("  "+ swords[i] +"："+ ng_records[i]);
    }
    if(DEBUG) System.out.println("id_per_cnt #=> "+ id_per_cnt);

    for(Integer id : id_per_cnt.keySet()){
      // ↓以下の部分の評価は中途段階。出現位置を考慮に入れた判定に変更予定。
      // それに伴い、IndexRecordのデータ構造は要変更。
      if(id_per_cnt.get(id) / swords.length > 0){
        if(DEBUG) System.out.println("  検索語はファイルid["+ id +"]中に存在する可能性あり。");
        String target_doc = docs.get(id);
        int pos = target_doc.indexOf(input);
        String mch = target_doc.substring(pos, pos + input.length());
        System.out.println("  照合文字列 : "+ mch);
      }
    }
  }
}

実行結果(コマンドライン引数部分は省略)

input #=> N文字
swords #=> N文 文字
  N文：2 (0, 1) (0, 42) {0=2}
  文字：3 (0, 2) (0, 43) (1, 61) {0=2, 1=1}
id_per_cnt #=> {0=4, 1=1}
  検索語はファイルid[0]中に存在する可能性あり。
  照合文字列 : N文字

現在の問題点

IndexRecordクラス:ArrayList型ではフィールド(ファイルidと出現位置)の関係性を取りづらい。

解決案

IndexRecordクラスのフィールドにファイルidを主キーとして、その部分単語の全ての出現位置を求められるハッシュデータが必要かと考えました。

今回もうすうすは感じていましたが、データ構造を設計し間違えるとプログラム構造が煩雑になりやすいです。初めから仕様を明確にしておけばデータモデリングでミスることもなかったかな。

しばらくは、今後の実装機能の洗い出しとそれに対応できるクラス構造を考えてみようかな。また、N-gramに分割する処理部分は別クラスのインスタンスメソッドとしてまとめたほうが良いですね。並行してデザインパターンも復習しておこう。

id:d-kamiさんから改良版Make2Gram付きトラックバックを頂きました(連絡方法がわからんのでトラックバックで - マイペースなプログラミング日記)(はてなダイヤリーから移転前)。d-kamiさん、ありがとうございます。

上記のページにあるコードから、TreeMapやsubstringを用いたbigramの切り出し・カウント方法などを学ばせて頂きました。

さて、今回の実装その2は以下の機能を加えました。

1. コマンドライン引数にディレクトリ名を指定して、そのディレクトリ以下のファイル全てを処理の対象とする。
2. N-gram情報には文書IDと部分文字列の出現位置を格納するようにデータ構造の拡張。

Continue reading

今回はN-gramでテキストを分解します。N-gram法とは対象の文字列を一定のN文字単位で分解し、それの出現頻度を求める方法です。これによって、検索エンジンに使われる転置インデックスを作成したいと思います。転置インデックスの作成方法にはN-gramの他に形態素解析があります。両者の性能の長短は全文検索 - Wikipediaに詳しく載っています。

Javaソースコード(Make2gram.java)

さて、まずは文字列を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());
    }
  }
}

入力ファイル(text.txt)

検索された文書は「更新順」「ファイル名順」「文書のタイトル順」などにソートされる。
一般的な検索エンジンでは独自のランク付けルールも適用し「重要度」などと呼んでいるものもある。

実行結果

検索
索さ
され
れた
た文
文書
書は
は「
「更
更新
新順
順」
」「

…＜省略＞…

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

参考にしたサイト

• Java 入門 | ArrayList クラス

追記(2008/3/7)：

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で指す文字が文字列の末尾かどうかを判定することで制御すればよいまでの話かもしれません。

今回はとあるアルゴリズムを移植上、気づきが色々あったのでこうした機会に言語仕様に対する理解を深めていきたいです。