HashMapを使った英和辞典

使用する辞書ファイル

ejdic2k2.txtをダウンロードしていない場合はあらかじめダウンロードしてプログラムと同じ場所に置くこと。

HashMapで探索する辞典

HashMapはJavaが持っているクラスで、簡単に使用することができます。しかも、元々のデータがあらかじめabc順に並べ替えられている必要がありません。下線の部分が大切なところです。

ファイル名 HMJiten01.java

import javax.swing.*;
import java.io.*;
import java.util.*;

public class HMJiten01 { 
    public static void main( String[] args ) {
        String fname = "ejdic2k2.txt";
        HashMap<String,String> dic = new HashMap<String,String>();
        int ct = 0;
        try {
            FileReader   in  = new FileReader(fname);
            BufferedReader inb = new BufferedReader(in);
            String line;
            while ((line = inb.readLine()) != null) {
                String[] ndata = line.split("\t");
                dic.put(ndata[0],ndata[1]);
                ct++;
            } 
            System.out.println("以上 0〜" + (ct-1) + " の " + ct + " 行");
            inb.close();
            in.close();
        }
        catch (IOException e) {
            System.err.println( fname + " がないのでは？" );
            System.err.println( e);
        }

        String s;
        s = JOptionPane.showInputDialog("検索する英単語を入れてください？","aaa");
        if ( dic.containsKey(s) ){
            System.out.println( s+"は「"+dic.get(s)+"」です。" );
        }
        else {
            System.out.println( "見つかりません" );
        }
    }//mainの終わり
}//classの終わり

コンパイルと実行は次のようにします。

$ javac HMJiten01.java
$ java HMJiten01
以上 0〜2002 の 2003 行
yetは「まだ,もう,それにもかかわらず」です。
$ 

HashMapの仕組み

英単語で探すのでこれをkey、取り出すのは意味なのでこれをvalueとします。

HashMap<String,String> dic = new HashMap<String,String>();

は、key,value共に文字列であるようなHashMapを作るという事です。これで新規にHashMapをつくり、dicという名前をつけたということです。

これに単語を登録するには次のようにします。

dic.put("red","赤");
dic.put("green","緑");
dic.put("blue","青");

いくつ登録されたかは、

dic.size();

で知ることができます。

keyとしてredが含まれているか調べるには、

dic.containsKey("red");

で調べることができます。trueかfalseで答えが返ってきますから、ifなどで利用します。

valueを取り出すときは、

dic.get("red");

で、「赤」が返ってきます。

HashMapはputの時に探しやすい構造を作りながら登録していきますから、予め順序良く並んでいないデータを登録しても素早く探すことができます。

速度比較

HashMapはどれほどの性能なのでしょうか。実際に速度を測定して、単純前方探索、二分法探索と比較してみましょう。

データはejdic2k2.txtを使います。どの単語を検索するかによって変わってきますので、全部の単語を検索する時間を計測します。2002回検索することになりますがこれを1セットとして、1000セットまで各アルゴリズムごとに計測します。

結果を全部表示するとスクロールのために余計な時間をとられるので表示は少なくしています。

HashMapは整列済みの辞書である必要はありません。そこでわざと項目は同じだけどkeyで整列させていないデータを元に検索させたものを加えました。結果として時間はほとんど変化ありません。

所要時間が 単純前方探索 > 二分法探索 > HashMap とほぼ予想どおりの結果です。時間はやるたびに異なりますが傾向は同じです。

しかし、理解に苦しむところもあります。辞書の大きさは同じですから、繰り返しの回数に時間が比例するはずですが、そうなっているのは単純前方検索だけです。最初はメモリ上に作業領域を確保するなどの作業がかかるのかもしれません。

使用したプログラム

使用したプログラムのソース。繰り返しのセット回数を変えるには、mainのint made=10;の数値を変えてコンパイルする必要があります。

上記プログラムの一部です。

    public static void main( String[] args ) {
       //辞書データをdiclistに入れるgetDicは共通のスタティックメソッド
        String fname = "ejdic2k.txt";
        LinkedList<String> diclist = getDic(fname);
       //wordslistはすべての単語を順に検索するためのリスト。辞書とは独立させる
        LinkedList<String> wordslist = new LinkedList<String>();
       //それぞれのアルゴリズムにあわせて辞書データをdiclistから変換する。
        String[] words = new String[2010];
        String[] imis  = new String[2010];
        int ct = 0;
        for( String line : diclist ){
            String[] ndata = line.split("\t");
            words[ct]=ndata[0];
            imis[ct]=ndata[1];
            ct++;
            wordslist.add(ndata[0]);
         }
       //データ数の確認
        System.out.println(ct);
        System.out.println(wordslist.size());
       //kaiを数えなからmadeまで繰り返す。全部の単語を検索して1kaiとする。
        int kai=0;
        int made=10;
        long time0 = System.currentTimeMillis();  //計測開始
        while( made>kai){
            for( String word : wordslist ){
                //辞書を検索するのはそれぞれのアルゴリズムで解くスタティックメソッド
                String imi = wordSearch(words,imis,ct,word);
                //スクロールの抑制のため yet の時だけ意味を表示。動作の確認にする。
                if (word.equals("yet")) System.out.println(imi);
           　}
            kai++;
        }
        long time1 = System.currentTimeMillis();  //計測終了
        System.out.println( (time1-time0) + "msec" );
    }