JPH0528194A - データアクセス方式 - Google Patents

Abstract

(57)【要約】 【目的】チェイン付きハッシュ法におけるキー衝突時の
チェックに際し、データサイズの縮小と検索の高速性維
持を同時に実現することができるようにする。 【構成】チェイン付きインデックス内のチェインポイン
タに、キーに関する情報を示す識別子を付加するように
し、このキー識別子に基づいて衝突時のチェックを行う
ようにした。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は、データアクセス方式
に関し、特にチェイン付きハッシュ法の衝突処理方式に
関する。

【０００２】

【従来の技術】従来、キーに基づいたデータ検索におけ
る高速なデータ構造としては、ハッシュ法が良く知られ
ている（参考文献：Ａ．Ａｈｏ他著，大野義夫訳，「デ
ータ構造とアルゴリズム」［情報処理シリーズ１１］，
培風館（１９８７））。ハッシュ法においては、キー衝
突時の取り扱いが問題となり、解決策として様々な方法
が提案されている。ハッシュ法は、オープンハッシュ法
とチェイン付きハッシュ法に大別され、一般に衝突が多
い場合はチェイン付きハッシュ法が採用されている。特
に、辞書的なデータを扱う場合は、本質的に衝突が多い
うえ、キーが一意でない場合も多い。また、こうした辞
書的なデータは規模が非常に大きいことがしばしばであ
り、主記憶容量の制限などから、データの実体をファイ
ルなどの２次記憶上に持つため、チェイン付きハッシュ
法が用いられている。

【０００３】

【発明が解決しようとする課題】ところで、チェイン付
きハッシュ法では、衝突の際にチェインを辿って、求め
るキーとの比較によるチェックを順次行うが、この比較
のためのキー情報をいかに保持するかが問題となる。例
えば、キー情報をチェイン中に包含すると高速性は維持
されるが、本来データサイズが大きいためインデックス
情報が巨大なものとなる。また、チェインにはポインタ
のみ持ち、データの実体を参照するようにするとアクセ
スが遅くなってしまう。特に、逆引きのためのインデッ
クスを保持する場合にこの問題は顕著となり、さらに挿
入や削除も遅くなる。上述した参考文献「データ構造と
アルゴリズム」でも、こうした二次インデックスを用い
た場合の問題が述べられている。

【０００４】一般に、英和辞書を代表とする電子辞書で
は、数万から数十万語の見出し語を持ち、さらに見出し
語以外の派生語、意味などからのインデックスまで含め
ると、データサイズも非常に大きくなる。そのうえ、対
話的に利用されることが多いため、検索には高速性が要
求される。したがって、これまでのデータアクセス方式
では、用途やハードウェアの制限などに応じて速度と容
量のいずれかを選択する形で妥協せざるを得なかったの
が現状である。

【０００５】この発明は、辞書的なデータを対象とした
ハッシュ法におけるキー衝突のチェックに際し、データ
サイズの縮小と検索の高速性維持を同時に実現すること
ができるデータアクセス方式を提供することを目的とす
る。

【０００６】

【課題を解決するための手段】この発明に係わるデータ
アクセス方式では、複数の検索キーと、ハッシュ表と、
チェイン付きインデックスと、実データファイルとを有
するデータ構造を具え、前記チェイン付きインデックス
内のチェインポインタに、キーに関する情報を示すキー
識別子を付加するようにしている。

【０００７】前記キー識別子は、通常の検索キーに関し
ては識別に必要な情報のみを持つようにする。また、キ
ー識別子はチェインのリンクにおいて直前のキーと同一
である場合は、省略するように指定してもよい。さら
に、対象とするデータが名前を有し、検索キーが名前そ
のものである場合は、キー識別子は実データの名前を参
照するように指定することができる。同様に、対象とす
るデータが名前を有し、検索キーが名前から解釈可能で
ある場合は、キー識別子は実データの名前を解釈して参
照するように指定することができる。

【０００８】

【作用】上記データアクセス方式では、まず、与えられ
た検索キーのハッシュ値を求め、ハッシュ表の該当する
位置の内容を読み込む。ここで、チェインポインタにキ
ー識別子が付加されているときは、このキー識別子に基
づいて現在のインデックスレコードがキーに対応するか
どうかを判別する。インデックスレコードがキーに対応
するときは、データポインタを読み込み、実データファ
イル上の位置からデータレコードを取り出して結果のリ
ストに追加する。

【０００９】このように、チェイン付きインデックス内
にキーに関する情報を圧縮した形式でキー識別子として
埋め込むことにより、キー衝突時の比較のためのキー情
報を効率よく利用できるようになり、データサイズの縮
小と検索の高速性維持を同時に実現することが可能とな
る。

【００１０】

【実施例】以下、この発明に係わるデータアクセス方式
を英和電子辞書システムに適用した場合の実施例を説明
する。

【００１１】図２は、英和電子辞書システムの概略構成
を示すブロック図である。この計算機システムは、表示
画面上に各種のデータなどを表示するＣＲＴ２１と、前
記ＣＲＴ２１での表示を制御するＣＲＴドライバ２２
と、コマンドや文字列、数値などの入力を行うキーボー
ド２３と、ポインティングデバイスであるマウス２４
と、ユーザーによるキーボード２３やマウス２４の操作
によって、各種のデータを出力するキーボード／マウス
ドライバ２５と、ディスク装置２６、ディスク装置ドラ
イバ２７、主記憶装置２８、ＣＰＵ（中央処理装置）２
９とから構成されている。

【００１２】ディスク装置２６は、大量のデータを格納
するための二次記憶装置であり、後述するチェイン付き
インデックスや実データファイルなどが格納されてい
る。また、ディスク装置２６のデータの入出力はディス
ク装置ドライバ２７で制御されている。

【００１３】主記憶装置２８は、アプリケーションプロ
グラム、及びキーボード２３やマウス２４から入力され
た文字や数値などのデータのほか、後述するハッシュ表
を格納している。

【００１４】ＣＰＵ２９は、システム全体の制御を行う
と共に、各種の命令に基づいて所定のデータに対する演
算処理を行う回路であり、後述のフローチャートに基づ
いてデータの検索処理を実行する。

【００１５】上記英和電子辞書システムにおけるデータ
構造の概要を図１に示す。図１のデータ構造は、基本的
にはハッシュ表１１、チェイン付きインデックス１２、
実データファイル１３の３つから構成されている。図に
示すように、通常の見出し語（ａ、Ａなど）からの検索
に加え、転置キーの設定により単語の語義（ひとつの、
イ音など）や発音のカタカナ表記（エ、アなど）からの
検索を行えるようになっており、このため、キー／レコ
ード数ともに非常に多く、またあるキーに対するレコー
ドも一意ではない。

【００１６】まず、ハッシュ表１１は検索キーｋのハッ
シュ値ｈ（ｋ）が指すアドレスよりチェイン付きインデ
ックス１２へのポインタを３バイトで保持する。対応す
るキーが未登録の場合、ＦＦＦＦＦＦＨを保持する。

【００１７】次に、チェイン付きインデックス１２の詳
細を説明する。チェイン付きインデックス１２は、デー
タレコードに一対一で対応する情報を持つインデックス
レコードの集合である。インデックスレコードの構造を
図３に示す。インデックスレコードは、レコードに設定
された全てのキーに関するチェインポインタ１〜ｎと、
キー識別子１〜ｎのペアの並び、及びデータファイルへ
のポインタ（データポインタ）を保持している。

【００１８】チェインポインタは、対応するキーに関す
る次のインデックスレコードへのポインタであり、衝突
により同じハッシュ値を持つ登録キーのリスト（データ
のつながり）が構成される。各リストの先頭はハッシュ
表から直接指されており、衝突がある場合、各ポインタ
は図４に示すように次のチェインポインタのアドレスを
保持し、リストの終端の場合にはｎｉｌとして００００
００Ｈが格納される。チェインポインタは３バイトで表
現され、００００００Ｈから７ＦＦＦＦＦＨの値を取り
得る。

【００１９】キー識別子はチェインポインタの直後に存
在し、入力キーが登録キーに対応するか否かのチェック
に用いられる。この実施例におけるキー識別子の記述ル
ールを以下に示す。なお、文字コードはＥＵＣである。

【００２０】（１）通常の検索キーにおいては、登録キ
ーの文字コード列の各文字コードの下位１バイトと００
８０Ｈの論理和のバイト列を順に格納する。

【００２１】（２）登録キーが見出し語から導出できる
場合であれば８０Ｈを格納する。これは、キーが見出し
語そのものである場合はもちろん、“Ａ，ａ”や“colo
(u)r”といった見出し語では一般的な表記をルール化す
ることで解釈できる。

【００２２】（３）登録キーがチェインの直前と同じで
ある場合は省略される。

【００２３】このように、キー識別子を導入することに
より、衝突のチェックのために見出し語以外のキーでは
実データを参照する必要がなくなる。ただし、その場
合、登録キーの情報量は落ちている。これにより、万一
異なるキーにもかかわらずキー下位１バイトが全て同じ
で、かつハッシュ値も等しい場合の区別ができなくなる
が、ハッシュ関数を十分吟味すれば実用上問題ないと考
えられる。また、検索のみを対象にした電子辞書では、
登録キーの情報はデータレコードに持つ必要はないた
め、データ量を節約することができる。例えば、発音の
カタカナ表記はキー設定時に用意したものであるが、実
際には実データにも含まれていないし、キー識別子にも
他のキーとの識別のための情報しか存在していない。

【００２４】データポインタには実データにおける実際
のデータレコードの先頭を指すアドレスが、デリミタＦ
ＦＨに続けて３バイトで格納されている。データポイン
タがＦＦＦＦＦＦＨである場合は、データレコードが削
除されていることを示す。

【００２５】実データファイルはデータレコードの集合
であり、データレコードは次の形式を持つ。

【００２６】（見出し語）（見出し区切り［NULL］）
（内容部）（レコード区切り［LF］）キー識別子に前述
のように８０Ｈが用いられた場合、このデータレコード
の見出し語を参照することでキーの識別を行う。ただ
し、このように実データを参照することは、ポインタを
手操る回数や次記憶へのアクセスが増える点で速度の低
下を招くため、速度を重視する場合であれば通常の検索
キーと同様のキー識別子を用いてもよい。

【００２７】実データファイル１３（内容部）は実際の
辞書記述部分であるが、この実施例ではキー識別子によ
り検索キーの情報を含まないため、この内部にフィール
ドなどの概念は不要であり、内容はフラットなテキスト
でよい。データレコードは全体で一つのテキストファイ
ルとなる。

【００２８】次に、上述した英和電子辞書システムによ
るデータ検索のアルゴリズムを、図５のフローチャート
を用いて説明する。

【００２９】まず、初期化（ステップ１０１）の後、検
索キーのハッシュ値ｈを求め、ハッシュ表の位置ｈの内
容をインデックスポジションｉｐとして読み込む（ステ
ップ１０２）。次に、ｉｐ＝ＦＦＦＦＦＦＨであるかど
うかを判定する（ステップ１０３）。ここで、ｉｐ＝Ｆ
ＦＦＦＦＦＨであれば未登録キーとわかるので終了す
る。また、ｉｐ＝ＦＦＦＦＦＦＨでないときは、チェイ
ン付きインデックス上の位置ｉｐから３バイトをチェイ
ンポジションｃｐとして読み込み（ステップ１０４）、
［ｉｐ＋３］≧８０Ｈかどうかを判定する（ステップ１
０５）。ここで、ｉｐ＋３から８０Ｈ以上のバイト列が
続けば、それをキー識別子ｋｒとして読み込む（ステッ
プ１０６）。また、省略されている場合は直前のものを
用いる。次に、ｋｒに基づいて現在のインデックスレコ
ードがキーに対応するか否かを判定し（ステップ１０
７）、対応するときはチェイン付きインデックス上のＦ
ＦＨまでスキップし、続く３バイトをデータポインタｄ
ｐとして読み込む（ステップ１０８）。続いて、ｄｐ＝
ＦＦＦＦＦＦＨであるかどうかを判定する（ステップ１
０９。ここで、ｄｐ＝ＦＦＦＦＦＦＨでなければデータ
レコードは存在するので、データファイル上の位置ｄｐ
から、データレコードのフォーマットに従い０ＡＨ（＝
LF）までを結果のリストに追加する（ステップ１１
０）。次に、ｃｐ＝０かどうかを判定し（ステップ１０
１）、ｃｐ＝０であるなら終了、そうでなければチェイ
ンが続いているので、ｉｐにｃｐを代入して（ステップ
１１２）、ステップ１０４へ戻る。

【００３０】なお、挿入、削除に関しても、チェインの
インデックスとデータの実体が分離されているため、ポ
インタのつなぎかえにより高速に実現可能である。

【００３１】上記実施例ではインデックスをディスク装
置２６に保持することを前提にしているが、主記憶装置
２８の容量に余裕があれば主記憶装置２８に保持するこ
とによりさらに高速化を図ることができる。

【００３２】また、この発明に係わるデータアクセス方
式は、チェイン付きハッシュ法一般に適用可能であり、
上記実施例に示した英和電子辞書システムだけに限定さ
れるものではない。例えば、テキストデータベースなど
の大量の情報を高速に探索するシステムにおける基本的
なデータ構造として利用することもできる。

【００３３】

【発明の効果】以上説明したように、この発明に係わる
データアクセス方式では、チェイン付きインデックス内
のチェインポインタに、キーに関する情報を示す識別子
を付加するようにしたため、キーの比較のためのキー情
報を効率よく利用できるようになり、データ検索の高速
性とデータサイズの節約が同時に可能となる。これによ
り、電子辞書を代表とする検索キーを主体とした検索を
非常に効率的に実現することが可能となる。

【図面の簡単な説明】

【図１】英和電子辞書システムにおけるデータ構造の概
要を示す図。

【図２】英和電子辞書システムの概略構成を示すブロッ
ク図。

【図３】インデックスレコードの構造を示す図。

【図４】インデックスレコードにおけるチェインポイン
タのリストを示す図。

【図５】英和電子辞書システムによるデータ検索のアル
ゴリズムを示すフローチャート。

【符号の説明】

１１…ハッシュ表、１２…チェイン付きインデックス、
１３…実データファイル

Claims (1)

1. 【特許請求の範囲】 【請求項１】ハッシュ表と、チェイン付きインデックス
   と、実データファイルとを有するデータ構造を具えたデ
   ータアクセス方式であって、前記チェイン付きインデッ
   クス内のチェインポインタに、キーに関する情報を示す
   識別子を付加したことを特徴とするデータアクセス方
   式。