ここまでの授業では、配列(データ検索は、登録順保存ならO(N)、２分探索ならO(log N)となる、2分探索ができるのは配列がランダムアクセスができるからこそ)、単純リスト(データ検索(シーケンシャルアクセスしかできないのでO(N)となる)、2分探索木( O(log N) ) といった手法を説明してきた。しかし、もっと高速なデータ検索はできないのであろうか？

究極のシンプルなやり方(メモリの無駄)

最も簡単なアルゴリズムは、電話番号から名前を求めるようなデータベースであれば、電話番号自身を配列添え字番号とする方法がある。しかしながら、この方法は大量のメモリを必要とする。

import java.util.*;

class PhoneName {
    int    phone ;  // (例) 27-2925
    String name ;
    
    PhoneName( int ph , String nm ) {
        this.phone = ph ;
        this.name  = nm ;
    }
}

public class Main {
    public static PhoneName[] table ;
    public static void entry( int ph , String nm ) {
        table[ ph ] = new PhoneName( ph , nm ) ;
    }
    public static String find( int ph ) {
        return table[ ph ].name ;
    } 
    public static void main(String[] args) throws Exception {
        table = new PhoneName[ 1000000 ] ; // 無駄にでかい
        entry( 272925 , "tsaitoh" ) ;
        entry( 621111 , "nit-fukui") ;
        entry( 123456 , "forger" ) ;
        System.out.println( find( 621111 ) ) ;
    }
}

• ハッシュ法ムダ版

しかし、50人程度のデータであれば、電話番号の末尾2桁を取り出した場合、同じ数値の人がいることは少ないであろう。であれば、電話番号の末尾2桁の値を配列の添え字番号として、データを保存すれば、配列サイズは100件となり、メモリの無駄を減らすことができる。

ハッシュ法

先に述べたように、データの一部を取り出して、それを配列の添え字番号として保存することで、高速にデータを読み書きできるようにするアルゴリズムはハッシュ法と呼ばれる。データを格納する表をハッシュ表、データの一部を取り出した添え字番号はハッシュ値、ハッシュ値を得るための関数がハッシュ関数と呼ばれる。

import java.util.*;

class PhoneName {
    int    phone ;  // 27-2925
    String name ;
    
    PhoneName( int ph , String nm ) {
        this.phone = ph ;
        this.name  = nm ;
    }
}

public class Main {
    public static PhoneName[] table ;
    public static void entry( int ph , String nm ) {
        table[ ph ] = new PhoneName( ph , nm ) ;
    }
    public static String find( int ph ) {
        return table[ ph ].name ;
    } 
    public static void main(String[] args) throws Exception {
        table = new PhoneName[ 1000000 ] ;
        entry( 272925 , "tsaitoh" ) ;
        entry( 621111 , "nit-fukui") ;
        entry( 123456 , "forger" ) ;
        System.out.println( find( 621111 ) ) ;
    }
}

• ハッシュ法(衝突を考えない版)

ただし、上記のプログラムでは、電話番号の末尾2桁が偶然他の人と同じになることを考慮していない。
例えば、データ件数が100件あれば、同じ値の人も出てくるであろう。このように、異なるデータなのに同じハッシュ値が求まることを、ハッシュ衝突と呼ぶ。

ハッシュ関数に求められる特性

ハッシュ関数は、できる限り同じような値が求まるものは、ハッシュ衝突が多発するので、避けなければならない。例えば、6桁の電話番号の先頭2桁であれば、電話番号の局番であり、同じ学校の人でデータを覚えたら、同じ地域の人でハッシュ衝突が発生してしまう。また、ハッシュ値を計算するのに、配列の空き場所を一つ一つ探すような方式では、データ件数に比例した時間がかかり、高速なアルゴリズムとは言えない。このことから、ハッシュ関数には以下のような特徴が必要となる。

• 同じハッシュ値が発生しづらい(一見してデタラメのように見える値)
• 簡単な計算で求まること。
• 同じデータに対し常に、同じハッシュ値が求まること。

---

ここで改めて、異なるデータでも同じハッシュ値が求まった場合、どうすれば良いのだろうか？

ハッシュ法を簡単なイメージで説明すると、100個の椅子(ハッシュ表)が用意されていて、1クラスの学生が自分の電話番号の末尾2桁(ハッシュ関数)の場所(ハッシュ値)に座るようなもの。自分のイスに座ろうとしたら、同じハッシュ値の人が先に座っていたら、どこに座るべきだろうか？

オープンアドレス法

先の椅子取りゲームの例え話であれば、先に座っている人がいた場合、最も簡単な椅子に座る方法は、隣が空いているか確認して空いていたらそこに座ればいい。

これをプログラムにしてみると、以下のようになる。このハッシュ法は、求まったアドレスの場所にこだわらない方式でオープンアドレス法と呼ばれる。

import java.util.*;

class PhoneName {
    int    phone ;  // 27-2925
    String name ;
    
    PhoneName( int ph , String nm ) {
        this.phone = ph ;
        this.name  = nm ;
    }
}

public class Main {
    public static PhoneName[] table ;
    public static int hash_func( int ph ) {
        return ph % 100 ;
    }
    public static void entry( int ph , String nm ) {
        int idx = hash_func( ph ) ;
        while( table[ idx ] != null )
            idx = (idx + 1) % 100 ;
        table[ idx ] = new PhoneName( ph , nm ) ;
    }
    public static String find( int ph ) {
        int idx = hash_func( ph ) ;
        for( ; table[ idx ] != null ; idx = (idx + 1) % 100 )
            if ( table[ idx ].phone == ph )
                return table[ idx ].name ;
        return null ;
    }
    public static void main(String[] args) throws Exception {
        table = new PhoneName[ 100 ] ;
        entry( 272925 , "tsaitoh" ) ;
        entry( 621111 , "nit-fukui") ;
        entry( 123425 , "forger" ) ;
        System.out.println( find( 272925 ) ) ;
        System.out.println( find( 123425 ) ) ;
    }
}

• (オープンアドレス法)

注意：このプログラムは、ハッシュ表すべてにデータが埋まった場合、無限ループとなるので、実際にはもう少し改良が必要である。

この実装方法であれば、ハッシュ表にデータが少ない場合は、ハッシュ値を計算すれば終わり。よって、処理時間のオーダはO(1)となる。しかし、ハッシュ表がほぼ埋まっている状態だと、残りわずかな空き場所を探すようなもの。

文字列のハッシュ値

ここまでで説明した事例は、電話番号をキーとするものであり、余りを求めるだけといったような簡単な計算で、ハッシュ値が求められた。しかし、一般的には文字列といったような名前から、ハッシュ値が欲しいことが普通だろう。

ハッシュ値は、簡単な計算で、見た目デタラメな値が求まればいい。 (ただしく言えば、ハッシュ値の出現確率ができるだけ一様であること)。一見規則性が解らない値として、文字であれば文字コードが考えられる。複数の文字で、これらの文字コードを加えるなどの計算をすれば、 偏りの少ない値を取り出すことができる。

public static int hash_func( String nm ) {
    int s = 0 ;
    for( int i = 0 ; i < nm.length() ; i++ )
        s += nm.charAt( i ) ;
    return s % 100 ;
}

文字列順で異なる値となるように

前述のハッシュ関数は、”ABC”さんと”CBA”さんでは、同じハッシュ値が求まってしまう。文字列順で異なる値が求まるように改良してみる。

public static int hash_func( String nm ) {
    int s = 0 ;
    for( int i = 0 ; i < nm.length() ; i++ )
        s += (nm.charAt( i ) + s * 小さい素数) % 大きい素数 ;
    return s % 100 ;
}

以下の方法は、繰り返しの度に s に小さい素数を掛けることで、数値全体に文字の影響がでるようにしている。これだけだと計算途中の s の値が最終的な100個に収めるための “% 100” で下2桁に影響がでないことから、大きい素数で余りを求めてみた。この計算方法は、疑似乱数を生み出す線形合同法の考え方を参考にした。

チェイン法

前に述べたオープンアドレス法は、ハッシュ衝突が発生した場合、別のハッシュ値を求めそこに格納する。配列で実装した場合であれば、ハッシュ表のサイズ以上の データ件数を保存することはできない。

チェイン法は、同じハッシュ値のデータをグループ化して保存する方法。 同じハッシュ値のデータは、リスト構造とするのが一般的。ハッシュ値を求めたら、そのリスト構造の中からひとつづつ目的のデータを探す処理となる。

この処理にかかる時間は、データ件数が少なければ、O(1) となる。しかし、ハッシュ表のサイズよりかなり多いデータ件数が保存されているのであれば、ハッシュ表の先に平均「N/ハッシュ表サイズ」件のデータがリスト構造で並んでいることになるので、O(N) となってしまう。

import java.util.*;

class PhoneNameNode {
    int             phone ;  // 27-2925
    String          name ;
    PhoneNameNode   next ;
    
    PhoneNameNode( int ph , String nm , PhoneNameNode nx ) {
        this.phone = ph ;
        this.name  = nm ;
        this.next  = nx ;
    }
}

public class Main {
    public final static int table_size = 100 ;
    public static PhoneNameNode[] table ;
    public static int hash_func( int ph ) {
        return ph % table_size ;
    }
    public static void entry( int ph , String nm ) {
        int idx = hash_func( ph ) ;
        table[ idx ] = new PhoneNameNode( ph , nm , table[ idx ] ) ;
    }
    public static String find( int ph ) {
        int idx = hash_func( ph ) ;
        for( PhoneNameNode p = table[ idx ] ; p != null ; p = p.next )
            if ( p.phone == ph )
                return p.name ;
        return null ;
    }
    public static void main(String[] args) throws Exception {
        table = new PhoneNameNode[ table_size ] ;
        for( int i = 0 ; i < table_size ; i++ )
            table[ i ] = null ;
        entry( 521125 , "tomoko" ) ;
        entry( 272925 , "saitoh" ) ;
        entry( 621160 , "mike"   ) ;
        System.out.println( find( 272925 ) ) ;
        System.out.println( find( 521125 ) ) ;
    }
}

• チェイン法

理解度確認

毎年、冬休み期間中の自主的な理解度確認として、CBT を用いた理解度確認を行っています。今年も実施しますので、下記のシステムにログインし情報構造論では「ソフトウェア」(50分) を受講して下さい。

• https://cbt.kosen-ac.jp/
• 認証には、MS-365 のアカウントとパスワードでログインしてください。

深さ優先探索(前順)

以前紹介した2分木の表示では、再帰呼び出しで木の処理を記述していた。

しかし、スタックを使って未処理のノードを保存しながらノードに対する処理を行えば、ループ処理で「すべての木のノード」に対する処理を記述できる。このような木に対する処理は、末端方向に処理が進むことが優先されるため深さ優先探索と呼ぶ。

以下のプログラムで示す深さ優先探索では、ノードに対する処理を行ってから左の枝葉の処理が行われる。このような深さ優先探索は前順(pre-order)と呼ぶ。

このような探索は、ゲームですべての戦略の先読みを行う処理で用いられる。

import java.util.*;

class BTreeNode {
    int       data ;
    BTreeNode left ;
    BTreeNode right ;
    
    BTreeNode( int x , BTreeNode l , BTreeNode r ) {
        this.data  = x ;
        this.left  = l ;
        this.right = r ;
    }
}

public class Main {
    // 再帰呼び出しによる木の操作 = 深さ優先探索(前順)
    public static void print_rec_depth_first_pre_order( BTreeNode p ) {
        if ( p != null ) {
            System.out.print( p.data + " " ) ;
            print_rec_depth_first_pre_order( p.left ) ;
            print_rec_depth_first_pre_order( p.right ) ;
        }
    }
    // 深さ優先探索(前順)
    public static void print_depth_first_pre_order( BTreeNode p ) {
        // 未処理ノードを保存するスタック
        LinkedList stack = new LinkedList<>() ;
        stack.addFirst( p ) ; // push
        while( !stack.isEmpty() ) {
            // スタックトップを取り出す
            p = stack.removeFirst() ; // pop
            if ( p != null ) {
                System.out.print( p.data + " " ) ;
                // 枝を未処理スタックに保存
                stack.addFirst( p.right ) ; // 右を後回し
                stack.addFirst( p.left ) ;
            }    
        }
    }
    public static void main(String[] args) throws Exception {
        BTreeNode top =
            new BTreeNode( 42 ,
                    new BTreeNode( 27 ,
                            new BTreeNode( 13 , null , null ) ,
                            new BTreeNode( 38 , null , null ) ) ,
                    new BTreeNode( 72 ,
                            new BTreeNode( 64 , null , null ) ,
                            new BTreeNode( 81 , null , null ) ) ) ;
        // 再帰による深さ優先探索(前順)
        print_rec_depth_first_pre_order( top ) ;
        System.out.println() ;
        // スタックを使った深さ優先探索(前順)
        print_depth_first_pre_order( top ) ;
        System.out.println() ;
    }
}

• 2分探索木の深さ優先探索、幅優先探索(Paiza.io)

幅優先探索

同じように、未処理のノードを待ち行列に保存しながら、ノードに対する処理を行うことでも、すべての木に対する処理が記述できる。この場合、根本の処理をすべて終えてから、末端に対する処理が行われる。このような処理は幅優先探索と呼ぶ。

幅優先探索の処理と、前順の深さ優先探索を比べると、ノードを覚えるデータ構造に待ち行列を使う(幅優先探索)か、スタックを使う(深さ優先探索)の違いしかない。

幅優先探索は、ゲームの戦略で先読みを行う場合に用いられるが、チェス・将棋・囲碁といったすべての先読みを行うと手数が爆発的に増加するため、不利な戦略の先読みを途中で打ち切る必要がある場合に有用である。

public class Main {
    // 幅優先探索
    public static void print_breadth_first( BTreeNode p ) {
        // 未処理ノードを保存する待ち行列
        LinkedList queue = new LinkedList<>() ;
        queue.addFirst( p ) ; // put
        while( !queue.isEmpty() ) {
            // 待ち行列の先頭を取り出す
            p = queue.removeLast() ; // get
            if ( p != null ) {
                System.out.print( p.data + " " ) ;
                // 枝を未処理待ち行列に追加
                queue.addFirst( p.left ) ; // 左から処理
                queue.addFirst( p.right ) ;
            }    
        }
    }
    public static void main(String[] args) throws Exception {
        BTreeNode top = (略) ;
        // 幅優先探索で表示
        print_breadth_first( top ) ;
        System.out.println() ;
    }
}

深さ優先探索(中順)

2分探索木のようなデータで、昇順で並べて表示する必要がある場合、再帰呼び出しのプログラムでは、「左枝の処理、ノードへの処理、右枝の処理」の順で記述する必要がある。このような深さ優先探索は中順(in-order)と呼ばれる。しかし、先に説明した再帰による深さ優先探索(前順/pre-order)では、「ノードへの処理、左枝の処理、右の枝の処理」で記述されている。

スタックを用いた深さ優先探索で、2分探索木の昇順のように中順で処理を行うには、未処理のノードの保存順序に工夫が必要となる。

import java.util.*;
public class Main {
    // 再帰呼び出しによる木の操作 = 深さ優先探索(中順)
    public static void print_rec_depth_first_in_order( BTreeNode p ) {
        if ( p != null ) {
            print_rec_depth_first_in_order( p.left ) ;
            System.out.print( p.data + " " ) ;
            print_rec_depth_first_in_order( p.right ) ;
        }
    }
    // 深さ優先探索(中順)
    public static void print_depth_first_in_order( BTreeNode p ) {
        // 未処理ノードを保存するスタック
        LinkedList stack = new LinkedList<>() ;
        for( ;; ) {
            // ノードを保存しながら左末端まで進む
            while( p != null ) {
                stack.addFirst( p ) ;
                p = p.left ;
            }
            // 未処理が残っていないなら終了
            if ( stack.isEmpty() )
                break ;
            // スタックトップを取り出す
            p = stack.removeFirst() ; // pop
            System.out.print( p.data + " " ) ;
            p = p.right ;
        }
    }
    public static void main(String[] args) throws Exception {
        BTreeNode top = (略) ;

        // 再帰による深さ優先探索(中順)
        print_rec_depth_first_in_order( top ) ;
        System.out.println() ;
        // スタックを使った深さ優先探索(中順)
        print_depth_first_in_order( top ) ;
        System.out.println() ;
    }
}