jp.gr.java_conf.dangan.util.lha
Class HashAndChainedListSearch

java.lang.Object
  jp.gr.java_conf.dangan.util.lha.HashAndChainedListSearch

All Implemented Interfaces:

LzssSearchMethod

public class HashAndChainedListSearch
extends java.lang.Object
implements LzssSearchMethod

ハッシュと単方向連結リストを使って高速化された LzssSearchMethod。
検索を打ち切ることによる高速化も行っているため、 必ず最長一致を見つけることが出来るとは限らない。

 -- revision history --
 $Log: HashAndChainedListSearch.java,v $
 Revision 1.0  2002/08/05 00:00:00  dangan
 add to version control
 [change]
     LzssSearchMethod のインタフェイス変更にあわせてインタフェイス変更
 [improvement]
     ar940528 の TEST5相当 の実装に変更。
 [maintenance]
     ソース整備
     タブ廃止
     ライセンス文の修正

 

Version:

$Revision: 1.0 $

Author:

$Author: dangan $

Constructor Summary

HashAndChainedListSearch(int DictionarySize, int MaxMatch, int Threshold, byte[] TextBuffer)
ハッシュと連結リストを使用した LzssSearchMethod を構築する。
ハッシュ関数と探索試行回数の上限値にはデフォルトのものが使用される。

HashAndChainedListSearch(int DictionarySize, int MaxMatch, int Threshold, byte[] TextBuffer, int SearchLimitCount)
ハッシュと連結リストを使用した LzssSearchMethod を構築する。
ハッシュ関数にはデフォルトのものが使用される。

HashAndChainedListSearch(int DictionarySize, int MaxMatch, int Threshold, byte[] TextBuffer, java.lang.String HashMethodClassName)
ハッシュと連結リストを使用した LzssSearchMethod を構築する。
探索試行回数の上限値にはデフォルトのものが使用される。

HashAndChainedListSearch(int DictionarySize, int MaxMatch, int Threshold, byte[] TextBuffer, java.lang.String HashMethodClassName, int SearchLimitCount)
ハッシュと連結リストを使用した LzssSearchMethod を構築する。

Method Summary

void	put(int position) position から始まるデータパタンを ハッシュと連結リストから成る検索機構に登録する。
int	putRequires() put() で LzssSearchMethodにデータを 登録するときに使用されるデータ量を得る。 HashAndChainedListSearch では、 内部で使用している HashMethod の実装が hash() のために必要とするデータ量 ( HashMethod.hashRequires() の戻り値 ) を返す。
int	search(int position, int lastPutPos) ハッシュと連結リストを使用した検索機構に登録された データパタンを検索し position から始まるデータパタンと 最長の一致を持つものを得る。
int	searchAndPut(int position) ハッシュと連結リストから成る検索機構に登録された データパタンから position から始まるデータパタンと 最長の一致を持つものを検索し、 同時に position から始まるデータパタンを ハッシュと連結リストから成る検索機構に登録する。
int	searchAndPut(int position, int[] matchposs) より良い LZSS 圧縮のための選択肢を提供する searchAndPut()。 例えば一致長 3, 一致位置 4 と 一致長 4, 一致位置 1024 では 一致長 3, 一致位置 4 + 非圧縮1文字 の方が出力ビット数が 少なくなる事がある。そのような場合に対処するため一致長毎に positionに一番近い一致位置を列挙する。
void	slide() TextBuffer内のpositionまでのデータを 前方へ移動する際、それに応じて SearchMethod内の データも TextBuffer内のデータと矛盾しないように 前方へ移動する処理を行う。

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

HashAndChainedListSearch

public HashAndChainedListSearch(int DictionarySize,
                                int MaxMatch,
                                int Threshold,
                                byte[] TextBuffer)

ハッシュと連結リストを使用した LzssSearchMethod を構築する。
ハッシュ関数と探索試行回数の上限値にはデフォルトのものが使用される。

Parameters:

DictionarySize - 辞書サイズ

MaxMatch - 最長一致長

Threshold - 圧縮、非圧縮の閾値

TextBuffer - LZSS圧縮を施すためのバッファ

HashAndChainedListSearch

public HashAndChainedListSearch(int DictionarySize,
                                int MaxMatch,
                                int Threshold,
                                byte[] TextBuffer,
                                int SearchLimitCount)

ハッシュと連結リストを使用した LzssSearchMethod を構築する。
ハッシュ関数にはデフォルトのものが使用される。

Parameters:

DictionarySize - 辞書サイズ

MaxMatch - 最長一致長

Threshold - 圧縮、非圧縮の閾値

TextBuffer - LZSS圧縮を施すためのバッファ

SearchLimitCount - 探索試行回数の上限

Throws:

java.lang.IllegalArgumentException - SearchLimitCount が0以下の場合

HashAndChainedListSearch

public HashAndChainedListSearch(int DictionarySize,
                                int MaxMatch,
                                int Threshold,
                                byte[] TextBuffer,
                                java.lang.String HashMethodClassName)

ハッシュと連結リストを使用した LzssSearchMethod を構築する。
探索試行回数の上限値にはデフォルトのものが使用される。

Parameters:

DictionarySize - 辞書サイズ

MaxMatch - 最長一致長

Threshold - 圧縮、非圧縮の閾値

TextBuffer - LZSS圧縮を施すためのバッファ

HashMethodClassName - Hash関数を提供するクラス名

Throws:

java.lang.NoClassDefFoundError - HashMethodClassName で与えられたクラスが 見つからない場合。

java.lang.InstantiationError - HashMethodClassName で与えられたクラスが abstract class であるためインスタンスを生成できない場合。

java.lang.NoSuchMethodError - HashMethodClassName で与えられたクラスが コンストラクタ HashMethod( byte[] )を持たない場合

HashAndChainedListSearch

public HashAndChainedListSearch(int DictionarySize,
                                int MaxMatch,
                                int Threshold,
                                byte[] TextBuffer,
                                java.lang.String HashMethodClassName,
                                int SearchLimitCount)

ハッシュと連結リストを使用した LzssSearchMethod を構築する。

Parameters:

DictionarySize - 辞書サイズ

MaxMatch - 最長一致長

Threshold - 圧縮、非圧縮の閾値

TextBuffer - LZSS圧縮を施すためのバッファ

HashMethodClassName - Hash関数を提供するクラス名

SearchLimitCount - 探索試行回数の上限

Throws:

java.lang.IllegalArgumentException - SearchLimitCount が0以下の場合

java.lang.NoClassDefFoundError - HashMethodClassName で与えられたクラスが 見つからない場合。

java.lang.InstantiationError - HashMethodClassName で与えられたクラスが abstract class であるためインスタンスを生成できない場合。

java.lang.NoSuchMethodError - HashMethodClassName で与えられたクラスが コンストラクタ HashMethod( byte[] )を持たない場合

Method Detail

put

public void put(int position)

position から始まるデータパタンを ハッシュと連結リストから成る検索機構に登録する。

Specified by:

put in interface LzssSearchMethod

Parameters:

position - TextBuffer内のデータパタンの開始位置

searchAndPut

public int searchAndPut(int position)

ハッシュと連結リストから成る検索機構に登録された データパタンから position から始まるデータパタンと 最長の一致を持つものを検索し、 同時に position から始まるデータパタンを ハッシュと連結リストから成る検索機構に登録する。

Specified by:

searchAndPut in interface LzssSearchMethod

Parameters:

position - TextBuffer内のデータパタンの開始位置。

Returns:

一致が見つかった場合は LzssOutputStream.createSearchReturn によって生成された一致位置と一致長の情報を持つ値、 一致が見つからなかった場合は LzssOutputStream.NOMATCH。

See Also:

LzssOutputStream.createSearchReturn(int,int), LzssOutputStream.NOMATCH

search

public int search(int position,
                  int lastPutPos)

ハッシュと連結リストを使用した検索機構に登録された データパタンを検索し position から始まるデータパタンと 最長の一致を持つものを得る。

Specified by:

search in interface LzssSearchMethod

Parameters:

position - TextBuffer内のデータパタンの開始位置。

lastPutPos - 最後に登録したデータパタンの開始位置。

Returns:

一致が見つかった場合は LzssOutputStream.createSearchReturn によって生成された一致位置と一致長の情報を持つ値、 一致が見つからなかった場合は LzssOutputStream.NOMATCH。

See Also:

LzssOutputStream.createSearchReturn(int,int), LzssOutputStream.NOMATCH

slide

public void slide()

TextBuffer内のpositionまでのデータを 前方へ移動する際、それに応じて SearchMethod内の データも TextBuffer内のデータと矛盾しないように 前方へ移動する処理を行う。

Specified by:

slide in interface LzssSearchMethod

putRequires

public int putRequires()

put() で LzssSearchMethodにデータを 登録するときに使用されるデータ量を得る。 HashAndChainedListSearch では、 内部で使用している HashMethod の実装が hash() のために必要とするデータ量 ( HashMethod.hashRequires() の戻り値 ) を返す。

Specified by:

putRequires in interface LzssSearchMethod

Returns:

内部で使用している HashMethod の実装が hash() のために必要とするデータ量

searchAndPut

public int searchAndPut(int position,
                        int[] matchposs)

より良い LZSS 圧縮のための選択肢を提供する searchAndPut()。 例えば一致長 3, 一致位置 4 と 一致長 4, 一致位置 1024 では 一致長 3, 一致位置 4 + 非圧縮1文字 の方が出力ビット数が 少なくなる事がある。そのような場合に対処するため一致長毎に positionに一番近い一致位置を列挙する。

Parameters:

position - 検索対象のデータパタンの開始位置

matchposs - 一致位置の列挙を格納して返すための配列
matchpos[0] には 一致長が Threshold の一致位置が、
matchpos[1] には 一致長が Threshold + 1 の一致位置が格納される。
一致が見つからなかった場合には LzssOutputStream.NOMATCH が格納される。

Returns:

一致が見つかった場合は LzssOutputStream.createSearchReturn で生成された SearchReturn が返される。
一致が見つからない場合は LzssOutputStream.NOMATCH が返される。