単語数の多い英和辞典

使用する辞書ファイル

ejdic2k.txtの内容は次のようなものです。2002件あります。

ejdic2k.txtのリンクを右クリックして出てくるメニューから「名前をつけてリンク先を保存」を選ぶことで、javaプログラムを入れるフォルダにダウンロードしておきましょう。

英単語と意味の間はタブで区切ってあります。

a	一つの,ある
ability	能力
able	できる,有能な
about	について,およそ,around
above	の上方へ,の上に,前に
abroad	海外へ(で),外国に(で),広く,広まって
absence	るす,欠席,ないこと
absent	欠席した,放心した
absolute	まったくの,絶対的な力を持った
accept	受け取る,認める,引き受ける
accident	偶然,事故
.....................省略.........

逐次探索の辞典

まず逐次探索にします。Jiten02.java に対して変わるところをこの色で示しましたが、削除される部分は書いてありません。

String[] word = { "blue", "green",....という部分をファイルからデータを読むように変更しているのが大きなところです。この部分はその気になればたくさん学ぶことがありますが、「String[] word = { "blue", "green",」と同様に word[] と imi[] を用意しているのだと大まかに理解することが最低限必要です。

ファイル名 Jiten04.java

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

public class Jiten04 { 
    public static void main( String[] args ) {
        String fname = "ejdic2k.txt";
        String[] word = new String[2010];
        String[] imi  = new String[2010];
        int ct = 0;
        try {
            FileReader   in  = new FileReader(fname);
            BufferedReader inb = new BufferedReader(in);
            String line;
            while ((line = inb.readLine()) != null) {
                System.out.println(line);
                String[] ndata = line.split("\t");
                word[ct]=ndata[0];
                imi[ct]=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("検索する英単語を入れてください?");
        boolean atta=false;
        for ( int i=0 ; ct>i ; i++ ){
            System.out.println( i+" : "+word[i] );
            if ( word[i].equals(s) ){
                System.out.println( word[i]+" : "+imi[i] );
                atta=true;
                break;
              }
        }//forの終わり
        if ( atta==false ) System.out.println( "見つかりません" );
    }//mainの終わり
}//classの終わり

読み込みの途中にある System.out.println(line); は、正しく読み込んでいることを確かめるために、読み込んだ内容を報告している部分です。

探索部分に加えた System.out.println( i+" : "+word[i] ); は探している途中でいま何を調べているかを報告させるようにしたものです。

ファイルの中の単語数が少し増えてもいいように、配列を多めにしているので、読み込みの時に単語数を数えて ct に記憶しておきます。繰り返しの数は word.length() ではなく、この ct を使っています。

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

$ javac Jiten04.java
$ java Jiten04
....(読んだデータを表示しますが長いので最初の部分は省略).........
yes	はい
yesterday	きのう,きのうは
yet	まだ,もう,それにもかかわらず
yield	産出する,明け渡す,作物がてきてる,屈する
you	あなた[がた]は(を)
young	若い,年下のほうの
youth	若さ,青年時代,青年
zero	0,零,零度
以上 0〜2002 の 2003 行  (ここでダイアログがでます。yetと入力したとすると)
0 : a
1 : ability
2 : able
....(と頭から順番に探していきますが、長いので省略).........
1990 : wrong
1991 : yard
1992 : year
1993 : yellow
1994 : yes
1995 : yesterday
1996 : yet
yet : まだ,もう,それにもかかわらず
$ 

yet という単語は1996番目に登録されているので、逐次探索では1996回比較して見つけることになります。a という単語ならば 1番目に登録されているので、1回の比較で見つかります。

二分探索の辞典

二分探索を使うように書き換えます。前半(ファイルからの読み込み部分)は Jiten04.java とほとんど同じです。

正しく読み込めることはJiten04.javaでわかったので、ファイルからの読み込みの時に内容を報告しないようにします。

後半(探索部分)は Jiten03.java とほとんど同じです。

ファイル名 Jiten05.java

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

public class Jiten05 { 
    public static void main( String[] args ) {
        String fname = "ejdic2k.txt";
        String[] word = new String[2010];
        String[] imi  = new String[2010];
        int ct = 0;
        try {
            FileReader   in  = new FileReader(fname);
            BufferedReader inb = new BufferedReader(in);
            String line;
            while ((line = inb.readLine()) != null) {
                //System.out.println(line);
                String[] ndata = line.split("\t");
                word[ct]=ndata[0];
                imi[ct]=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("検索する英単語を入れてください?");
        boolean atta=false;
        int i,j,m;
        i = 0;
        j = ct-1;
        while ( j >= i ){
            m = (i+j)/2;
            String format = "i=%4d | j=%4d | m=%4d | word[m]=%-10s\n";
            System.out.printf(format,i,j,m,word[m]);
            if ( word[m].equals(s) ){
                System.out.println( "発見 word["+m+"] です。");
                System.out.println( word[m]+" の意味は「"+imi[m]+"」です。" );
                atta=true;
                break;
            }
            else if (word[m].compareTo(s)>0) {
                j=m-1;
            }
            else {
                i=m+1; 
            }
        }//whileの終わり
        if ( atta==false ) System.out.println( "見つかりません" );
    }//mainの終わり
}//classの終わり

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

$ javac Jiten05.java
$ java Jiten05
以上 0〜2001 の 2002 行  (ここでダイアログがでます。yetと入力したとすると)
i=   0 | j=2001 | m=1000 | word[m]=lodge     
i=1001 | j=2001 | m=1501 | word[m]=scatter   
i=1502 | j=2001 | m=1751 | word[m]=tap       
i=1752 | j=2001 | m=1876 | word[m]=use       
i=1877 | j=2001 | m=1939 | word[m]=whenever  
i=1940 | j=2001 | m=1970 | word[m]=within    
i=1971 | j=2001 | m=1986 | word[m]=wrap      
i=1987 | j=2001 | m=1994 | word[m]=yes       
i=1995 | j=2001 | m=1998 | word[m]=you       
i=1995 | j=1997 | m=1996 | word[m]=yet       
発見 word[1996] です。
yet の意味は「まだ,もう,それにもかかわらず」です。
$ 

whileで繰り返されるたびに1行出力されますから11回の比較で見つかったことになります。

比較回数は最大で全体数を2で割りつづけて、1になる程度と言えます。ちょうど1/2のところにあったという幸運がであればもっと少なくなります。2000ならば大体 1000,500,250,125,64,32,16,8,4,2,1 ですから11回程度で見つかります。

二分探索をするには単語が文字コード順に並んでいる必要があります。

優れたアルゴリズム

約2000件のデータから探索する場合、逐次探索は平均で1000回程度、二分探索では11回程度の比較で見つけられることがわかりました。

ただし、逐次探索の比較は等しいかどうかだけですが、二分探索の比較はどちらが大きいか(ABC順で先か後か)も調べているので単純に回数だけで比べるわけには行きません。

要素の比較回数
データ数 逐次探索 二分探索
2000 1000 11
20000 10000 14
200000 100000 18
n O(n) O(log2 n)

1000と11と横に比べるだけでなく、データの数が多くなったときにどのように比較回数が増えるかが重要です。データ数(ここでは単語数)が2000⇨20000⇨200000と10倍になっていくとき、逐次探索は比較回数も同様に10倍ずつ増えていきます。二分探索は2倍にもなりません。データ数が多くなるほど逐次と二分の手間の差はますます広がります。

これだけから考えると、二分探索が優れているようですが、ちょっと待ってください。二分探索はデータが大きさの順に並んでいる必要があります。並んでいない場合は並べかえる手間も考慮に入れる必要があります。

また、複数のデータが合致する場合には二分探索では対処が難しくなります。