jp.gr.java_conf.dangan.util.lha

Class HashAndChainedListSearch

Implemented Interfaces:
LzssSearchMethod

public class HashAndChainedListSearch
extends 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, String HashMethodClassName)
ハッシュと連結リストを使用した LzssSearchMethod を構築する。
探索試行回数の上限値にはデフォルトのものが使用される。
HashAndChainedListSearch(int DictionarySize, int MaxMatch, int Threshold, byte[] TextBuffer, String HashMethodClassName, int SearchLimitCount)
ハッシュと連結リストを使用した LzssSearchMethod を構築する。
HashAndChainedListSearch(int DictionarySize, int MaxMatch, int Threshold, byte[] TextBuffer, 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内のデータと矛盾しないように 前方へ移動する処理を行う。

Constructor Details

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,
                                String HashMethodClassName)
ハッシュと連結リストを使用した LzssSearchMethod を構築する。
探索試行回数の上限値にはデフォルトのものが使用される。
Parameters:
DictionarySize - 辞書サイズ
MaxMatch - 最長一致長
Threshold - 圧縮、非圧縮の閾値
TextBuffer - LZSS圧縮を施すためのバッファ
HashMethodClassName - Hash関数を提供するクラス名

HashAndChainedListSearch

public HashAndChainedListSearch(int DictionarySize,
                                int MaxMatch,
                                int Threshold,
                                byte[] TextBuffer,
                                String HashMethodClassName,
                                int SearchLimitCount)
ハッシュと連結リストを使用した LzssSearchMethod を構築する。
Parameters:
DictionarySize - 辞書サイズ
MaxMatch - 最長一致長
Threshold - 圧縮、非圧縮の閾値
TextBuffer - LZSS圧縮を施すためのバッファ
HashMethodClassName - Hash関数を提供するクラス名
SearchLimitCount - 探索試行回数の上限

HashAndChainedListSearch

public HashAndChainedListSearch(int DictionarySize,
                                int MaxMatch,
                                int Threshold,
                                byte[] TextBuffer,
                                int SearchLimitCount)
ハッシュと連結リストを使用した LzssSearchMethod を構築する。
ハッシュ関数にはデフォルトのものが使用される。
Parameters:
DictionarySize - 辞書サイズ
MaxMatch - 最長一致長
Threshold - 圧縮、非圧縮の閾値
TextBuffer - LZSS圧縮を施すためのバッファ
SearchLimitCount - 探索試行回数の上限

Method Details

put

public void put(int position)
position から始まるデータパタンを ハッシュと連結リストから成る検索機構に登録する。
Specified by:
put in interface LzssSearchMethod
Parameters:
position - TextBuffer内のデータパタンの開始位置

putRequires

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

search

public int search(int position,
                  int lastPutPos)
ハッシュと連結リストを使用した検索機構に登録された データパタンを検索し position から始まるデータパタンと 最長の一致を持つものを得る。
Specified by:
search in interface LzssSearchMethod
Parameters:
position - TextBuffer内のデータパタンの開始位置。
lastPutPos - 最後に登録したデータパタンの開始位置。
Returns:
一致が見つかった場合は LzssOutputStream.createSearchReturn によって生成された一致位置と一致長の情報を持つ値、 一致が見つからなかった場合は LzssOutputStream.NOMATCH。

searchAndPut

public int searchAndPut(int position)
ハッシュと連結リストから成る検索機構に登録された データパタンから position から始まるデータパタンと 最長の一致を持つものを検索し、 同時に position から始まるデータパタンを ハッシュと連結リストから成る検索機構に登録する。
Specified by:
searchAndPut in interface LzssSearchMethod
Parameters:
position - TextBuffer内のデータパタンの開始位置。
Returns:
一致が見つかった場合は LzssOutputStream.createSearchReturn によって生成された一致位置と一致長の情報を持つ値、 一致が見つからなかった場合は LzssOutputStream.NOMATCH。

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 が返される。

slide

public void slide()
TextBuffer内のpositionまでのデータを 前方へ移動する際、それに応じて SearchMethod内の データも TextBuffer内のデータと矛盾しないように 前方へ移動する処理を行う。
Specified by:
slide in interface LzssSearchMethod

When you found typographical errors or omissions, Please mail to cqw10305@nifty.com
The company name and product name which are used in this document, it is the trademark or registered trademark of each company generally.
Copyright © 2001-2002 Michel Ishizuka. All Rights Reserved.