JPH02227735A - ネームテーブル探索装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は情報処理における言語処理系のネームテーブル
の管理に利用する。本発明は言語処理系のネームテーブ
ルの探索に関する。

〔冬既要〕

本発明は連鎖ハツシュ法を用いたネームチーフル上への
名標の登録およびその探索を行うネームテーブル探索装
置において、 同一のハツシュ値をもつネームテーブルの名標の連鎖を
３氏木構造で格納し、３氏木構造で連鎖されている名標
を探索することにより、格納される名標が増加しても名
標探索に要する時間を少なくできるようにしたものであ
る。

〔従来の技術〕

従来、この種のネームテーブル探索は、名標から一意に
決まるハッンユ関数を用いて有限の大きさを持つハツシ
ュテーブルから同一のハッンユ関数を持つ名標を連鎖さ
せる連鎖ハツシュ法が用いられていた。

〔発明が解決しようとする問題点〕

上述した従来の連鎖ハツシュ法は、理想的なハツシュ関
数を想定したときでもハツシュ値の幅をｎ、構成要素の
数をｍとすると探索に必要な時間のオーダーはｍ／ｎに
比例する値となるために名標の数が多くなると探索効率
が著しく低下する欠点がある。

本発明はこのような欠点を除去するもので、名標が増加
しても探索に要する時間を少なくすることができる装置
を提供することを目的とする。

〔問題点を解決するための手段〕

本発明は、名標が順不同に格納された定義ワークファイ
ルから名標を取り出し、連鎖ハツシュ法を用いたネーム
テーブルに含まれるハツシュテーブル上に登録する名標
登録手段と、参照すべき名標が格納された参照ワークフ
ァイルの名標にしたがい前記ネームテーブルに登録され
た名標を探索するネームテーブル探索手段とを備えたネ
ームテーブル探索装置において、前記名標登録手段に、
同一のハツシュ値を持つ前記ネームテーブルの名標の連
鎖を前記ハツシュテーブルに８氏木構造で格納する手段
を含み、前記ネームテーブル探索手段に、前記ハツシュ
テーブルから８氏木構造で連鎖されている名標を探索す
る手段を含むことを特徴とする。

ここで８氏木構造とは、データの変動とともに、索引を
動的に保守し、いつでも相応のデータ呼出し効率と記憶
空間利用率とを保証する編成であり、データベース応用
に好んで取り上げられ、ＶＳＡＭ（Ｖｉｒｔｕａｌ　Ｓ
ｔｏｒａｇｅ　Ａｃｃｅｓｓ　Ｍｅｔｈｏｄ）の基本概
念としても知られる。（情報処理ハンドブック：情報処
理学会編参照） 〔作用〕 名標登録手段が定義ワークファイルから名標を取り出し
、ネームテーブル上のハツシュテーブルに同一のハツシ
ュ値をもつネームテーブルの名標の連鎖を８氏木構造で
格納する。ネームテーブル探索手段が参照ワークファイ
ルに格納されている名標にしたがってハツシュテーブル
から８氏木構造で連鎖されている名標を探索する。

これにより、格納される名標が増加しても名標探索に要
する時間を短縮することができる。

〔実施例〕

次に、本発明実施例を図面に基づいて説明する。

第１図は本発明実施例の構成を示すブロック図、第２図
は本発明実施例ネームテーブル１３の連鎖の例を示す図
である。

本発明実施例は、名標が順不同に格納された定義ワーク
ファイル１１から名標を取り出し、連鎖ハツシュ法を用
いたネームテーブル１３に含まれるハツシュテーブル２
１上に登録する名標登録手段１２と、参照すべき名標が
格納された参照ワークファイル１４の名標にしたがいネ
ームテーブル１３に登録された名標を探索するネームテ
ーブル探索手段１５とを備え、本発明の特徴として、名
標登録手段１２に、同一のハツシュ値を持つネームテー
ブル１３の名標の連鎖をハツシュテーブル２１に８氏木
構造で格納する手段を含み、ネームテーブル探索手段１
５に、ハツシュテーブル２１から８氏木構造で連鎖され
ている名標を探索する手段を含む。

次に、このように構成された本発明実施例の動作につい
て説明する。

定義ワークファイル１１の中には名標が順不同に格納さ
れており、ネームテーブルへの名標登録手段１２は定義
ワークファイル１１の中から一つずつ名標を取り出しネ
ームテーブル１３に登録する。

第２図は本発明実施例のネームテーブル１３を示す図で
ある。ハツシュテーブル２１は名標からバッジμ関数（
０からｎまでの値を取る）によってハツシュ値ｎ１を得
てｎｌに対応するエントリから連鎖するためのオリジン
ポインタの配列で名標を格納する。構成要素がひとつも
連鎖されていないときＮＵＬＬの値をとる。

ネームテーブル１３の各構成要素はハツシュテーブル２
１から構成要素の１エントリ２２の形（ただしに＝１の
場合）で連鎖されており、それぞれの名標の左隣のポイ
ンタはその名標より小さいかまたは等しい名標を持つ構
成要素を指し、右隣のポインタはその名標より大きい名
標を持つ構成要素を指す。

また、指すものが無いときはＮＵＬＬとなる。

この形式のネームテーブル１３に名標ＡＢＣ＜ＢＣＤ＜
ＢＣＥ＜ＢＣＧ＜ＢＤＥ＜ＣＤＥ＜ＤＥＦ＜ＥＡＢ＜Ｅ
ＦＧ＜ＦＧＨ＜ＦＧＪが連鎖された（これらが同じハツ
シュ値を持つようなハツシュ関数を使っていると仮定す
る）例が連鎖の例２３〜３０である。

ネームテーブル１３への名標登録手段１２は第３図に示
す処理によって第２図に示すネームテーブル１３へ名標
を登録する。第３図では定義ワークファイル１１から読
み込んだ名標からハツシュテーブル２１の位置ｎ１を決
定しＢ成木の要素として登録する処理を全て名標に対し
て繰り返す。

すなわち、定義ワークファイル１１から名標を１件読み
込み（ステップ３０２）、終了か否かを判定しくステッ
プ３０３）、終了でなければ名標よりハツシュ値ｎ１を
計算しくステップ３０４）、ハツシュテーブル２１のｎ
ｌに名標をＢ成木の節の要素として登録しくステップ３
０５）、すべての名標に対して繰り返し、ステップ３０
３の判定が終了であればその処理を終了する（ステップ
３０６）。ネームテーブルの探索手段１５はＢ成木を用
いて参照ワークファイル１４中の名標で第４図に示すよ
うにネームテーブル１３を探索する。第４図は参照ワー
クファイル１４から名標を取り出してそのハツシュ値を
決定しハツシュテーブル２１上の連鎖の開始ポインタか
らＢ成木を探索する手順を示したものである。

すなわち、参照ワークファイル１４から参照名標を読み
込みくステップ４０２）、終了か否かを判定しくステッ
プ４０３）、終了でなければ名標からハツシュ値ｎ２を
決定する（ステップ４θ４）。次いでハツシュテーブル
のハツシュ値ｎ２がＮＵＬＬであるか否かを判断しくス
テップ４０５）、ＮＵＬＬであれば未定義エラーとして
処理を戻しくステップ４１０）、ＮＵＬＬでなければハ
ツシュテーブルのハツシュ値ｎ２を指すＢ成木を探索し
くステップ４０７）、見つかったか否かを判定しくステ
ップ４０８）、見つからなければ未定義エラーしとて処
理を戻しくステップ４１０）、見つかれば二重に定義さ
れていないかを判断しくステップ４０９）、二重定義の
ときには多重定義エラーとして処理を戻しくステップ４
１２）、二重定義されていなければ探索結果として見つ
かった名標を処理する（ステップ４１１）。この手順を
参照名標読み込みが終了するまで繰り返しステ・ツブ４
０３で終了と判定されたときに処理を終了する（ステッ
プ４０６）。

〔発明の効果〕 以上説明したように本発明によれば、連鎖ノ飄、ソシュ
法の連鎖を３氏木構造にすることにより、／’％ッシュ
の幅をｎ構成要素の数をｍとすると探索に必要な時間を
ｌｏｇ（ｍ／ｎ）に比例する値にすることができ、従来
の連鎖ハツシュ法を用いたネームテーブルの探索に比べ
て名標が増加したときの探索に要する時間を少なくする
ことができる効果がある。

【図面の簡単な説明】

第１図は本発明実施例の構成を示すプロ・ツク図。 第２図は本発明実施例のネームテーブルの形式第３図は
本発明実施例の名標登録手段の処理の流れを示す流れ図
。 第４図は本発明実施例のネームテーブル探索手段の処理
の流れを示す流れ図。 １１・・・定義ワークファイル、１２・・・名標登録手
段、１３・・・ネームテーブル、１４・・・参照ワーク
ファイル、１５・・・ネームテーブル探索手段。

Claims (1)

1. 【特許請求の範囲】 １、名標が順不同に格納された定義ワークファイルから
   名標を取り出し、連鎖ハッシュ法を用いたネームテーブ
   ルに含まれるハッシュテーブル上に登録する名標登録手
   段と、 参照すべき名標が格納された参照ワークファイルの名標
   にしたがい前記ネームテーブルに登録された名標を探索
   するネームテーブル探索手段とを備えたネームテーブル
   探索装置において、前記名標登録手段に、同一のハッシ
   ュ値を持つ前記ネームテーブルの名標の連鎖を前記ハッ
   シュテーブルにＢ氏木構造で格納する手段を含み、前記
   ネームテーブル探索手段に、前記ハッシュテーブルから
   Ｂ氏木構造で連鎖されている名標を探索する手段を含む ことを特徴とするネームテーブル探索装置。