(57)【要約】本発明は、ハッシュを利用した全文基盤の論理演算遂行方法に関するものであり、その方法は、ロジッグオペレーター種類によってロジッグ状態を異にするハッシュ資料構造を現在のロジッグオペレーターに対応して生成する段階と、一番目オペランド資料に該当するハッシュノードらを前記ハッシュ資料構造で順に割り当てを受けたバケットに挿入する段階と、及び現在のロジッグオペレーター種類がＡＮＤである場合、前記ハッシュ資料構造で前記挿入されたバケットらまたは以前演算の結果値に選定されたバケットらのうちで二番目オペランド資料に該当するハッシュノードらと一致するバケットらだけの結果値で選定して、ＯＲである場合二番目オペランド資料に該当するハッシュノードらのうちで前記ハッシュ資料構造で検索されないハッシュノードらに対して前記ハッシュ資料構造でバケットを、順に割り当てを受けて挿入して、前記ハッシュ資料構造内の有効なすべてのバケットらを結果値で選定する段階と、を含んでなされる。
2015532498.tif 000002
【特許請求の範囲】
【請求項１】
(ａ)ロジッグオペレーター種類によってロジッグ状態を異にするハッシュ資料構造を現在のロジッグオペレーターに対応して生成する段階と、
(ｂ)一番目のオペランド資料に該当するハッシュノードらを前記ハッシュ資料構造で順に割り当てを受けたバケットに挿入する段階と、及び
(ｃ)現在のロジッグオペレーター種類がＡＮＤである場合、前記ハッシュ資料構造で前記(ｂ)段階で挿入されたバケットら、または以前演算の結果値で選定されたバケットらのうちで二番目オペランド資料に該当するハッシュノードらと一致するバケットらだけの結果値で選定して、ＯＲである場合二番目オペランド資料に該当するハッシュノードらのうちで前記ハッシュ資料構造で検索されないハッシュノードらに対して前記ハッシュ資料構造でバケットを、順に割り当てを受けて挿入して、前記ハッシュ資料構造内の有効なすべてのバケットらを結果値で選定する段階と、を含むことを特徴とするハッシュを利用した全文基盤の論理演算遂行方法。
【請求項２】
(ｄ)現在のロジッグオペレーターが前記ハッシュ資料構造のロジッグ状態と異なる場合、現在のロジッグオペレーターに対応して前記ハッシュ資料構造のロジッグ状態を変更する段階と、をさらに含むことを特徴とする請求項１に記載のハッシュを利用した全文基盤の論理演算遂行方法。
【請求項３】
前記ハッシュ資料構造は、
入力値でハッシュＩＤが使用されるＭＯＤ演算でなされたハッシュ関数と、
ハッシュキーに対応するバケットのスタート位置を指定するハッシュノードらのリスト集合であるハッシュテーブルと、
ハッシュＩＤとハッシュチェイン用ポインタをバケットの構成要素にするバケットブロックを具備することを特徴とする請求項１に記載のハッシュを利用した全文基盤の論理演算遂行方法。
【請求項４】
ロジッグ状態がＡＮＤであるハッシュ資料構造のバケットは、
ロジッグ演算の結果値を決定するためのカウンターをさらに具備することを特徴とする請求項３に記載のハッシュを利用した全文基盤の論理演算遂行方法。
【請求項５】
前記(ｂ)段階、または前記(ｃ)段階でのバケットの割り当ては、
予め設定されたバケットブロック内のバケットらのうちで使用されないバケットを、順に割り当てを受けるが、バケットブロック内に使用されないバケットが存在しない場合、新しいバケットブロックを生成した後生成された新しいバケットブロック内の使用されないバケットの割り当てを受けることを特徴とする請求項３に記載のハッシュを利用した全文基盤の論理演算遂行方法。
【請求項６】
前記バケットブロックの大きさは、
２ｎ(ここで、ｎは定数)値で決定されることを特徴とする請求項３に記載のハッシュを利用した全文基盤の論理演算遂行方法。
【請求項７】
前記ハッシュテーブルの大きさは、
前記バケットブロックの大きさより大きい小数のうちで一つで決定されることを特徴とする請求項６に記載のハッシュを利用した全文基盤の論理演算遂行方法。
【請求項８】
前記ハッシュ資料構造は、
ＡＮＤロジッグ演算の結果値の個数をカウントするＡＮＤカウンターと、
ＯＲロジッグ演算の結果値の個数をカウントするＯＲカウンターをさらに具備することを特徴とする請求項３に記載のハッシュを利用した全文基盤の論理演算遂行方法。
【請求項９】
前記(ｄ)段階で、
前記ハッシュ資料構造のロジッグ状態をＡＮＤからＯＲに変更する場合、新しいハッシュ資料構造を生成して、既存ハッシュ資料構造の結果値に該当するバケットらを新しいハッシュ資料構造に挿入して、既存のハッシュ資料構造のすべての資源を解除して、新しいハッシュ資料構造を既存のハッシュ資料構造にマッピングするものであることを特徴とする請求項２に記載のハッシュを利用した全文基盤の論理演算遂行方法。
【請求項１０】
(ｅ)現在のロジッグオペレーター種類がＡＮＤである場合、前記ハッシュ資料構造でバケットのカウンターがＡＮＤロジッグオペレーターの個数と同一なバケットのみを最終結果値に出力して、ＯＲである場合前記ハッシュ資料構造内の有効なすべてのバケットらを最終結果値に出力する段階と、を含むことを特徴とする請求項４に記載のハッシュを利用した全文基盤の論理演算遂行方法。
【請求項１１】
入力値でハッシュＩＤが使用されるＭＯＤ演算でなされたハッシュ関数と、
ハッシュキーに対応するバケットのスタート位置を指定するハッシュノードらのリスト集合であるハッシュテーブルと、
ハッシュＩＤとハッシュチェイン用ポインタをバケットの構成要素にするバケットブロックを具備するハッシュ資料構造と、及び
ロジッグオペレーター種類によってロジッグ状態を異にするハッシュ資料構造を現在のロジッグオペレーターに対応して生成してメモリーを割り当てて初期化するStartUpモジュールと、
一番目オペランド資料に該当するハッシュノードを前記ハッシュ資料構造で割り当てを受けたバケットに挿入するInsertモジュールと、
現在のロジッグオペレーター種類がＡＮＤである場合、前記ハッシュ資料構造で前記Insertモジュールで挿入されたバケットら、または以前演算の結果値で選定されたバケットらのうちで二番目オペランド資料に該当するハッシュノードと一致するバケットを結果値で選定して、ＯＲである場合二番目オペランド資料に該当するハッシュノードが前記ハッシュ資料構造で検索されなければ前記ハッシュ資料構造で割り当てを受けたバケットに挿入するLogicモジュールを具備するハッシュを利用した全文基盤の論理演算遂行のための使用者インターフェースと、を記録したコンピューターが読める記録媒体。
【請求項１２】
前記使用者インターフェースは、
現在のロジッグオペレーターが前記ハッシュ資料構造のロジッグ状態と異なる場合、現在のロジッグオペレーターに対応して、前記ハッシュ資料構造のロジッグ状態を変更するChangeLogicモジュールをさらに具備することを特徴とする請求項１１に記載のコンピューターが読める記録媒体。
【請求項１３】
ロジッグ状態がＡＮＤであるハッシュ資料構造のバケットは、
ロジッグ演算の結果値を決定するためのカウンターをさらに具備して、
前記ChangeLogicモジュールは、
前記ハッシュ資料構造のロジッグ状態をＡＮＤからＯＲに変更する場合、新しいハッシュ資料構造を生成して、既存ハッシュ資料構造の結果値に該当するバケットらを新しいハッシュ資料構造に挿入して、既存のハッシュ資料構造のすべての資源を解除して、新しいハッシュ資料構造を既存のハッシュ資料構造にマッピングすることを特徴とする請求項１２に記載のコンピューターが読める記録媒体。
【請求項１４】
前記ハッシュ資料構造は、
ＡＮＤロジッグ演算の結果値の個数をカウントするＡＮＤカウンターと、
ＯＲロジッグ演算の結果値の個数をカウントするＯＲカウンターをさらに具備して、
前記使用者インターフェースは、
前記現在のロジッグオペレーター種類によってＡＮＤカウンターまたはＯＲカウンターの値を出力するSizeモジュールをさらに具備することを特徴とする請求項１１に記載のコンピューターが読める記録媒体。
【請求項１５】
前記使用者インターフェースは、
現在のロジッグオペレーター種類がＡＮＤである場合、前記ハッシュ資料構造でバケットのカウンターがＡＮＤロジッグオペレーターの個数と同一なバケットのみを捜して最終結果値で一つずつ出力して、ＯＲである場合前記ハッシュ資料構造内の有効なすべてのバケットらを最終結果値で一つずつ出力するNextモジュールをさらに具備することを特徴とする請求項１１に記載のコンピューターが読める記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全文(Full-Text)基盤データベースでキーワード検索時に使用される論理演算を効率的に遂行するための方法に関するものであり、特に、システム資源が制限的なモバイル端末機上で最小限の資源を使って効率的にロジッグ演算を遂行することができる方法に関するものである。
【背景技術】
【０００２】
情報検索システムは、使用者が必要であると予測される情報やデータをあらかじめ収集、加工、処理して捜しやすい形態で蓄積しておいたデータベースから使用者の要求に好適な情報を速かに捜し出して使用者に提供するシステムを言う。
【０００３】
データベースに蓄積されている情報の種類によって情報検索システムは、参照検索、事実検索、全文(full-text)検索に区分される。参照検索は、使用者が分かろうとする主題を核心的に扱っている文献の書誌事項を検索することで、ＤＩＲＬＯＧ、ＢＲＳなどのオンライン情報検索システムがこれに該当する。事実検索は、一般データや数値データ及び事実データを検索することができることで、化学物質を検索するＣＡＳ(Chemical Abstracts Service On-line)、半導体材料のデータを検索するＥＭＩＳ(Electronic Information Service)などがこの範疇に属する。全文検索は文献の全文(full-text)を蓄積しておいたデータベースから書誌的データだけではなく、該当文章や原文全部を必要によって検索して見られることで法律情報を検索することができるレクシス(ＬＥＸＩＳ)やウェストロ(ＷＥＳＴＬＡＷ)、新聞記事を検索することができるネクシス(ＮＥＸＩＳ)、ダウジョーンズレトリーバー(Dow Jones/Retrieval)などがある。
【０００４】
全文(Full-Text)基盤データベースでキーワード検索時に使用される論理演算には大容量のコンピュータ資源が要求される。ところが、モバイル環境で使用することができるコンピュータ資源は限定されるしかなくて、論理演算遂行時に検索速度が遅くなる。
【０００５】
したがって、モバイル端末機上の全文(Full-Text)基盤検索システムでは提供する論理演算子使用個数が極めて制限的であるので、効果的なキーワード検索がなされないという問題点がある。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明は、前記の問題点を解決するために案出されたものであり、ハッシュを利用したフルテキスト(Full-Text)基盤論理演算子の評価方法を提案することで、システム資源が制限的なモバイル端末機上で最小限の資源を活用して、最適のＡＮＤ/ＯＲロジッグ演算を遂行できるようにして、ロジッグ演算後に外部でロジッグ演算結果データを獲得できるようにするハッシュを利用した全文基盤の論理演算遂行方法を提供することをその目的とする。
【課題を解決するための手段】
【０００７】
前記の目的らを達成するために、本発明によるハッシュを利用した全文基盤の論理演算遂行方法は、ロジッグオペレーターの種類によってロジッグ状態を異にするハッシュ資料構造を現在のロジッグオペレーターに対応して生成する段階と、一番目オペランド資料に該当するハッシュノードらを前記ハッシュ資料構造で順に割り当てを受けたバケットに挿入する段階と、及び現在のロジッグオペレーターの種類がＡＮＤである場合、前記ハッシュ資料構造で前記段階で挿入されたバケットらまたは以前演算の結果値で選定されたバケットらのうちで二番目オペランド資料に該当するハッシュノードらと一致するバケットらだけの結果値で選定して、ＯＲである場合二番目オペランド資料に該当するハッシュノードらのうちで前記ハッシュ資料構造で検索されないハッシュノードらに対して前記ハッシュ資料構造でバケットを、順に割り当てを受けて挿入して、前記ハッシュ資料構造内の有効なすべてのバケットらを結果値で選定する段階と、を含んでなされる。
【０００８】
また、前記の目的らを達成するために、本発明によるコンピューターが読めることができる記録媒体は、入力値でハッシュＩＤが使用されるＭＯＤ演算でなされたハッシュ関数とハッシュキーに対応するバケットのスタート位置を指定するハッシュノードらのリスト集合であるハッシュテーブルと、ハッシュＩＤとハッシュチェイン用ポインタをバケットの構成要素にするバケットブロックを具備するハッシュ資料構造と、及びロジッグオペレーターの種類によってロジッグ状態を異にするハッシュ資料構造を現在のロジッグオペレーターに対応して生成してメモリーを割り当てて、初期化するスタートアップ(Start Up)モジュールと、一番目オペランド資料に該当するハッシュノードを、前記ハッシュ資料構造で割り当てを受けたバケットに挿入するインサート(Insert)モジュールと、現在のロジッグオペレーター種類がＡＮＤである場合、前記ハッシュ資料構造で前記インサートモジュールで挿入されたバケットらまたは以前演算の結果値で選定されたバケットらのうちで二番目オペランド資料に該当するハッシュノードと一致するバケットを結果値で選定して、ＯＲである場合二番目オペランド資料に該当するハッシュノードが前記ハッシュ資料構造で検索されなければ、前記ハッシュ資料構造で割り当てを受けたバケットに挿入するロジックモジュールを具備するハッシュを利用した全文基盤の論理演算遂行のための使用者インターフェースと、を記録したことを特徴とする。
【発明の効果】
【０００９】
本発明によれば、ハッシュを利用して全体的なリソースを減らすことで制限されたシステム資源を効果的に活用することができるし、メモリー断片化を抑制して利用可能なシステム資源を増加させることができるし、したがって、円滑なサービスの提供が可能で、性能上の利得も確保することができる。
【００１０】
特に、メモリーコンパクション機能が一般ＰＣより単純なモバイル端末機上ではその期待効果がさらに大きい。
【図面の簡単な説明】
【００１１】
【図１】本発明によるハッシュを利用した全文基盤の論理演算遂行方法で使用するハッシュ資料構造を示した図面である。
【図２】本発明に使用される使用者インターフェースのうちでStart Upモジュールの遂行動作を示した図面である。
【図３】本発明に使用される使用者インターフェースのうちでClean Upモジュールの遂行動作を示した図面である。
【図４】本発明に使用される使用者インターフェースのうちでInsertモジュールの遂行動作を示した図面である。
【図５】本発明に使用される使用者インターフェースのうちでLogicモジュールの遂行動作を示した図面である。
【図６】本発明に使用される使用者インターフェースのうちでChange Logicモジュールの遂行動作を示した図面である。
【図７】本発明に使用される使用者インターフェースのうちでSizeモジュールの遂行動作を示した図面である。
【図８】本発明に使用される使用者インターフェースのうちでNextモジュールの遂行動作を示した図面である。
【図９ａ】本発明による例示のためのテーブル及び各索引を示した図面である。
【図９ｂ】本発明による例示のためのテーブル及び各索引を示した図面である。
【図９ｃ】本発明による例示のためのテーブル及び各索引を示した図面である。
【図１０ａ】本発明による各例示の挿入演算、ロジッグ演算、検索結果をそれぞれ説明する図面である。
【図１０ｂ】本発明による各例示の挿入演算、ロジッグ演算、検索結果をそれぞれ説明する図面である。
【図１０ｃ】本発明による各例示の挿入演算、ロジッグ演算、検索結果をそれぞれ説明する図面である。
【図１１ａ】本発明による各例示の挿入演算、ロジッグ演算、検索結果をそれぞれ説明する図面である。
【図１１ｂ】本発明による各例示の挿入演算、ロジッグ演算、検索結果をそれぞれ説明する図面である。
【図１１ｃ】本発明による各例示の挿入演算、ロジッグ演算、検索結果をそれぞれ説明する図面である。
【図１２ａ】本発明による各例示の挿入演算、ロジッグ演算、検索結果をそれぞれ説明する図面である。
【図１２ｂ】本発明による各例示の挿入演算、ロジッグ演算、検索結果をそれぞれ説明する図面である。
【図１２ｃ】本発明による各例示の挿入演算、ロジッグ演算、検索結果をそれぞれ説明する図面である。
【図１３ａ】本発明による各例示の挿入演算、ロジッグ演算、検索結果をそれぞれ説明する図面である。
【図１３ｂ】本発明による各例示の挿入演算、ロジッグ演算、検索結果をそれぞれ説明する図面である。
【図１３ｃ】本発明による各例示の挿入演算、ロジッグ演算、検索結果をそれぞれ説明する図面である。
【図１３ｄ】本発明による各例示の挿入演算、ロジッグ演算、検索結果をそれぞれ説明する図面である。
【図１４ａ】本発明による各例示の挿入演算、ロジッグ演算、検索結果をそれぞれ説明する図面である。
【図１４ｂ】本発明による各例示の挿入演算、ロジッグ演算、検索結果をそれぞれ説明する図面である。
【図１４ｃ】本発明による各例示の挿入演算、ロジッグ演算、検索結果をそれぞれ説明する図面である。
【図１４ｄ】本発明による各例示の挿入演算、ロジッグ演算、検索結果をそれぞれ説明する図面である。
【図１４ｅ】本発明による各例示の挿入演算、ロジッグ演算、検索結果をそれぞれ説明する図面である。
【発明を実施するための形態】
【００１２】
以下では添付図面を参照して本発明に対して詳しく説明する。
【００１３】
本発明によるハッシュを利用した全文基盤の論理演算遂行方法で使用するハッシュ資料構造を図１を参照して説明する。
【００１４】
本発明で使用されるハッシュ資料構造には、ハッシュ関数(図示せず)、ハッシュテーブル１０、バケットブロック２０、カーソルー４０、ＡＮＤカウンター５０、ＯＲカウンター５１などが含まれることができる。
【００１５】
ハッシュ関数は、ハッシュＩＤを入力にしてハッシュキーを生成する関数であり、ＭＯＤ演算でなされることが望ましい。また、全文(Full-Text)データベースのレコード識別子(ＩＤ)がハッシュＩＤで使用される。
【００１６】
ハッシュテーブル１０は、ハッシュキーに対応するバケット３０のスタート位置を指定するハッシュノードらのリスト集合である。ハッシュテーブル１０の大きさは、使用者によって入力されるPreCountを利用して決定されるが、バケット３０の均一な分布のためにバケットブロック２０の大きさよりすこし大きい小数(a prime number)で決められることが望ましい。
【００１７】
バケット３０は、ハッシュに挿入される資料構造として、ハッシュ衝突時に該当バケットを検索できるようにハッシュＩＤとハッシュチェイン３２用ポインタが含まれる。バケット３０にはロジッグ演算の結果値を決定するためのカウンターと使用者がハッシュノードに入力するデータ(使用者データ１、使用者データ２など)が含まれることができる。
【００１８】
バケットブロック２０は、ハッシュに挿入されるバケット３０の予想個数であるPreCountを利用してあらかじめ生成されるメモリーバッファーである。
【００１９】
カーソルー４０は、バケット凸型２０でバケット３０の位置を指定したものであり、ロジッグ演算の結果を外部で容易に獲得できるように支援するためのものである。
【００２０】
ＡＮＤカウンター５０は、ＡＮＤロジッグ演算結果値の個数をカウントするためのものであり、ＯＲカウンター５１はＯＲロジッグ演算の結果値の個数をカウントするためのものである。
【００２１】
本発明では、メモリー管理者６０というモジュールを設定して、ハッシュ内で使用するメモリーを管理して、特に、バケットブロック２０の自動追加機能及び現在のバケットが挿入される位置情報を管理するようにする。メモリー管理者６０は、一定範囲別にバケットブロックの大きさをあらかじめ決めておいて、使用者から入力を受けるPreCount値がどのような範囲に属するかによって対応する値を生成しようとするバケットブロックの大きさで決定する。ここで、バケットブロックの大きさは、メモリー管理を容易にするために２ｎ(ここで、ｎは定数)値で決定されることが望ましい。使用者によって入力されるPreCountはハッシュチェイン３２内にバケットが２〜３個になるように決定されるのが望ましいが、索引を通じてロジッグ演算の一番目オペランド資料に該当する集合でのハッシュノードの個数を使えば効果的である。
【００２２】
バケットブロックの大きさより実際に挿入されるバケットの個数が多い場合、メモリー管理者６０は自動で新しいバケットブロック２０を生成する。よって、従来のハッシュ資料構造によると、ハッシュ衝突時にバケットを毎度新しくメモリー空間の割り当てを受けて生成して連結リスト形態で構成しなければならないが、本発明によると、バケットブロック２０内に既に生成されたバケット３０らのうちで順に割り当てを受けて連結リスト形態で構成して使用することができる。
【００２３】
本発明で使用される使用者インターフェースにはStartUp、CleanUp、Insert、Logic、ChangeLogic、Size、Nextが含まれる。
【００２４】
(１)StartUpモジュール
図２に示されたところのようにStartUpモジュールは、ハッシュを使用するために初期化及び資源割り当てを遂行する。
【００２５】
入力値はロジッグオペレーター、オペレーター個数、予想バケット個数(PreCount)で構成される。
【００２６】
ロジッグオペレーターは、ＡＮＤまたはＯＲである。
【００２７】
オペレーター個数は、ＡＮＤまたはＯＲロジッグオペレーターが連続的に現われる個数である。例えば、集合Ａ、Ｂ、Ｃに対して“Ａ  ＡＮＤ  Ｂ  ＡＮＤ  Ｃ”という論理演算がある場合、オペレーター個数は２になる。
【００２８】
予想バケット個数(PreCount)は、ハッシュテーブル及びバケットブロックの大きさを決定するのに重要な入力値で使用される。
【００２９】
StartUpモジュールが遂行する動作は次のようである。
【００３０】
論理演算Hashが有するすべてのメンバー変数を初期化する(Ｓ１００)。
【００３１】
使用者が入力した値(PreCount)を利用してバケットブロック及びハッシュテーブルの大きさを決定する(Ｓ１１０)。メモリー管理者６０は、一定範囲別にバケットブロックの大きさをあらかじめ決めておいて、PreCount値がどのような範囲に属するかによって対応する値をバケットブロックの大きさで決定する。ここで、バケットブロックの大きさは、メモリー管理を容易にするために２ｎ(ここで、ｎは定数)値で決定されることが望ましい。また、ハッシュテーブルの大きさはバケットブロックの大きさよりすこし大きい小数で決められる。
【００３２】
決定されたハッシュテーブルの大きさを利用してハッシュテーブル１０にメモリーを割り当てて初期化する(Ｓ１２０)。
【００３３】
以後、入力されたロジッグオペレーターの種類(ＡＮＤまたはＯＲ)によってロジッグ状態を異にするハッシュ資料構造を生成する(Ｓ１３０、Ｓ１４０)。すなわち、バケットの種類は、ＡＮＤロジッグ用３０aとＯＲロジッグ用３０ｂに区分されているし、ＡＮＤロジッグ用バケット３０aには追加的にカウンターが含まれている。このカウンターはＡＮＤロジッグ演算時に使用される。ＡＮＤロジッグ状態のハッシュ資料構造ではＡＮＤロジッグ演算だけが可能であり、ＯＲロジッグ状態のハッシュ資料構造ではＯＲロジッグ演算だけが可能であるが、ロジッグオペレーターの種類が異なるものに変わるようになると、後で説明するようになるChangeLogicモジュールによってハッシュ資料構造のロジッグ状態を変更することができる。
【００３４】
（２）CleanUpモジュール
図３に示されたところのようにCleanUpモジュールは、すべてのロジッグ演算を終えてハッシュ内のの資源を解除する機能を遂行する。
入力値はない。
【００３５】
CleanUpモジュールが遂行する動作は次のようである。
【００３６】
バケットブロック２０のメモリーを返還して(Ｓ２００)、ハッシュテーブル１０のメモリーを返還して(Ｓ２１０)、すべてのメンバー変数を初期化する(Ｓ２２０)。
【００３７】
（３）Insertモジュール
図４に示されたところのように、Insertモジュールは初期化されたハッシュ資料構造にロジッグ演算を遂行するために一番目オペランド資料を挿入する。仮に、集合ＡとＢに対して“Ａ  ＡＮＤ  Ｂ”のような演算がある時、集合Ａの元素らのうちで一つをハッシュに挿入する機能を遂行する。
【００３８】
入力値はハッシュノードとして入力する使用者データ資料である。
【００３９】
ハッシュノード(データ資料):ハッシュ関数に使用されるハッシュＩＤとその他の使用者が入力した資料などで構成される。
【００４０】
Insertモジュールが遂行する動作は次のようである。
【００４１】
先ず、ハッシュ内に入力する資料が既に存在するかの検索を遂行する(Ｓ３００)。すなわち、ハッシュ内に入力されたハッシュノードのハッシュＩＤと同一なハッシュＩＤを有するバケットが存在するかどうかを検索する。
【００４２】
仮に、検索結果が既に存在すると何も遂行しない。
【００４３】
仮に、検索結果が存在しなければ、メモリー管理者６０から一つのバケットの割り当てを受けて(Ｓ３１０)、ハッシュ関数を利用してハッシュキーを生成した後(Ｓ３２０)ハッシュキーに該当するハッシュチェインに割り当てを受けたバケットを連結して(Ｓ３３０)、入力資料を記録する(Ｓ３４０)。
【００４４】
ＯＲカウンターを増加させる(Ｓ３５０)。
【００４５】
(４)Logicモジュール
図５に示されたところのように、Logicモジュールはロジッグオペレーター後に出るオペランドを入力してロジッグ演算を遂行する。仮に、集合ＡとＢに対して“Ａ  ＡＮＤ  Ｂ”のような演算がある時、集合Ｂの元素らのうちで一つに対してハッシュにＡＮＤ演算機能を遂行して、仮に集合ＡとＢに対して“Ａ  ＯＲ  Ｂ”のような演算がある時、集合Ｂの元素らのうちで一つに対してハッシュにＯＲ演算機能を遂行する。
【００４６】
入力値は、オペレーター番号とハッシュノード(データ資料)で構成される。
【００４７】
オペレーター番号:連続的で同一なロジッグ演算で何番目のロジッグオペレーターであるかを意味する値である。例えば、“Ａ  ＡＮＤ  Ｂ  ＡＮＤ  Ｃ  ＡＮＤ  Ｄ”というロジッグ演算がある時オペレーター個数は３であり、一番目のロジッグ演算(Ａ  ＡＮＤ  Ｂ)時のオペレーター番号は１であり、二番目のロジッグ演算((一番目のロジッグ演算結果)ＡＮＤ  Ｃ)時のオペレーター番号は２であり、三番目のロジッグ演算((二番目のロジッグ演算結果)ＡＮＤ  Ｄ)時のオペレーター番号は３になる。
【００４８】
ハッシュノード(データ資料):ハッシュ関数に使用されるハッシュＩＤとその他の使用者が入力した資料などで構成される。
【００４９】
Logicモジュールでは、現在のロジッグオペレーター種類がＡＮＤである場合ハッシュ資料構造でInsertモジュールで挿入されたバケットらまたは以前演算の結果値で選定されたバケットらのうちで二番目オペランド資料に該当するハッシュノードと一致するバケットを結果値で選定する。反面に、ＯＲである場合二番目オペランド資料に該当するハッシュノードがハッシュ資料構造で検索されなければ、ハッシュ資料構造で割り当てを受けたバケットに挿入する動作を遂行する。具体的な動作は次のようである。
【００５０】
先ず、ハッシュ内に入力する資料が既に存在するかの検索を遂行する(Ｓ４００)。すなわち、ハッシュ内に入力されたハッシュノードのハッシュＩＤと同一なハッシュＩＤを有するバケットが存在するかの可否を検索する。
【００５１】
Ｓ４００段階の検索結果が既に存在すると、現在のロジッグオペレーターがＡＮＤであるかＯＲであるかを確認する(Ｓ４１０)。現在のロジッグオペレーターは、StartUpモジュールで入力を受けたロジッグオペレーターで設定されてから、ChangeLogicモジュールが遂行されれば新たに入力を受けたロジッグオペレーターに変更される。
【００５２】
仮に、検索結果が既に存在して、現在のロジッグオペレーターがORなら、何も遂行しない。
【００５３】
仮に、検索結果が既に存在して、現在のロジッグオペレーターがＡＮＤなら、検索されたバケットのカウンターが入力を受けたオペレーター番号から１を引いた値のような場合(以前の演算までＡＮＤロジッグの結果値になるバケット)(Ｓ４２０)検索されたバケットのカウントを１増加させて(現在演算の結果値)(Ｓ４３０)、検索されたバケットの増加されたカウンターがStartUpモジュールまたはChangeLogicモジュールで入力を受けたオペレーター個数と一致すると(ＡＮＤ演算の最終結果値)(Ｓ４４０)、ＡＮＤカウンターを１増加させる(Ｓ４５０)。これに比べて、検索されたバケットのカウンターが入力を受けたオペレーター番号から１を引いた値と異なるか、または検索されたバケットの増加されたカウンターがStartUpモジュールまたはChangeLogicモジュールで入力を受けたオペレーター個数と異なる場合には何も遂行しない。
【００５４】
S４００段階の検索結果が存在しなければ現在のロジッグオペレーターがＡＮＤであるか、またはＯＲであるかを確認する(Ｓ４６０)。
【００５５】
仮に、検索結果が存在しないで、現在のロジッグオペレーターがＡＮＤなら、何も遂行しない。
【００５６】
仮に検索結果が存在しないで、現在のロジッグオペレーターがＯＲなら、メモリー管理者６０から一つのバケットの割り当てを受けて(Ｓ４７０)、ハッシュ関数を利用してハッシュキーを生成した後(Ｓ４８０)、ハッシュキーに該当するハッシュチェインに割り当てを受けたバケットを連結して(Ｓ４９０)、入力資料を記録した後(Ｓ５００)、ＯＲカウンターを増加させる(Ｓ５１０)。
【００５７】
(５)ChangeLogicモジュール
ChangeLogicモジュールは、ロジッグオペレーターが変化される時に使って、ハッシュ内部のロジッグ状態を変更させる機能を遂行する。仮に、集合Ａ、Ｂ、Ｃに対して“(Ａ  ＡＮＤ  Ｂ)ＯＲ  Ｃ”のような演算がある時、ＡＮＤロジッグ演算後ハッシュのロジッグ状態をＡＮＤからＯＲに変更する機能を遂行する。
【００５８】
入力値はロジッグオペレーター、オペレーター個数で構成される。
【００５９】
ロジッグオペレーター:ＡＮＤまたはＯＲ
オペレーター個数:ＡＮＤまたはＯＲオペレーターが連続的に現われる個数
ChangeLogicモジュールのうちでＡＮＤからORに変更する動作は、図６に示されたところのようである。
【００６０】
先ず、入力値であるロジッグオペレーター、オペレーター個数と現在のハッシュ資料構造に設定されている予想バケット個数((PreCount)を使って内部的に新しいハッシュ資料構造を生成する。この場合、前記したStartUpモジュールが利用される。
【００６１】
以後、下で説明するNextモジュールを利用して現在のハッシュ資料構造で結果値のみを獲得して新しいハッシュ資料構造に挿入して、現在のハッシュ資料構造にあるメンバー変数らを新しいハッシュ資料構造のメンバー変数にマッピングさせる。
【００６２】
以後、現在のハッシュ資料構造に対してCleanUpモジュールを利用してメモリー資源を解除させる。
【００６３】
以後、内部的に生成した新しいハッシュ資料構造のメンバー変数及びポインタなどを現在のハッシュ資料構造にマッピングさせて、内部的に生成した新しいハッシュ資料構造の客体資料のみを消滅させる。この場合、新しいハッシュ資料構造をCleanUpしない。
【００６４】
ChangeLogicモジュールの具現のためには、ハッシュ内部のメンバーらのうちで使用者の入力データを記憶するバッファー(ハッシュテーブル、バケットブロック)は、必ずポインタを使ってHeapから割り当てを受けなければならないし、これで現在ハッシュ資料構造のロジッグ状態を新しいロジッグ状態に変更することが可能である。
【００６５】
以上のような動作によってロジッグオペレーターがＡＮＤからＯＲに変更される時、ハッシュ資料構造に割り当てされるメモリーの大きさを大幅に減らすことができる。
【００６６】
一方、ChangeLogicモジュールのうちでＯＲからＡＮＤに変更する過程では割り当てされるメモリーが減らないために、単純に現在のハッシュ資料構造のロジッグ状態を変更させてくれる。この時、現在のハッシュ資料構造のバケットは、ＡＮＤロジッグ用バケット３０aに変更される。
【００６７】
(６)Sizeモジュール
図７を参照すると、Sizeモジュールはロジッグ演算の結果数を使用者に返還する機能を遂行する。
【００６８】
入力値はない。
【００６９】
現在のロジッグオペレーターがＡＮＤであるか、ＯＲであるかを確認して(Ｓ７００)、ハッシュ資料構造のロジッグ状態がＡＮＤロジッグ状態ならＡＮＤカウンター値を返還して(Ｓ７１０)、ハッシュ資料構造のロジッグ状態がＯＲロジッグ状態ならＯＲカウンター値を返還する(Ｓ７２０)。
【００７０】
(７)Nextモジュール
図８を参照すると、Nextモジュールはロジッグ演算後にロジッグ演算の結果を使用者に返還する機能を遂行する。
【００７１】
入力値はない。
【００７２】
Nextモジュールの場合、現在のロジッグオペレーター種類がＡＮＤである場合(現在のハッシュ資料構造がＡＮＤロジッグ演算を遂行した後である場合)ハッシュ資料構造でバケットのカウンターがＡＮＤロジッグオペレーターの個数と同一なバケットのみを捜して最終結果値にしてカーソルーが位置したバケット内の使用者資料を一つずつ出力して、ＯＲである場合(現在のハッシュ資料構造がＯＲロジッグ演算を遂行した後である場合)ハッシュ資料構造内の有効なすべてのバケットらを最終結果値にしてカーソルーが位置したバケット内の使用者資料を一つずつ出力する。具体的な動作は次のようである。
【００７３】
現在のロジッグオペレーターがＡＮＤであるか、またはＯＲであるかを確認して(Ｓ８００)、ハッシュ資料構造のロジッグ状態がＡＮＤロジッグ状態ならカーソルーを１増加させて、カーソルーの位置でバケットを獲得する(Ｓ８１０)。
【００７４】
獲得されたバケットが有効ではない場合、ハッシュ資料構造内のすべてのバケットブロックを巡回したものであるので、使用者に‘No Data’を返還するようになる(Ｓ８２０)。
【００７５】
獲得されたバケットが有効である場合、バケット内にあるカウンター値とオペレーター個数を比べて同じである場合、バケット内の使用者資料を返還して(Ｓ８３０)、同じではない場合Ｓ８１０段階に再び戻る。
【００７６】
ハッシュ資料構造のロジッグ状態がＯＲロジッグ状態ならカーソルーを１増加させて、カーソルーの位置でバケットを獲得する(Ｓ８４０)。
【００７７】
獲得されたバケットが有効な場合バケット内の使用者資料を返還して(Ｓ８５０)、有効でない場合ハッシュ資料構造内のすべてのバケットブロックを巡回したものであるので、使用者に‘No Data’を返還するようになる。
【００７８】
以下で、本発明によるハッシュを利用した全文基盤の論理演算遂行過程を例に挙げて説明する。
【００７９】
図９Ａに示された“テーブルＡ”に対する“名称Ｂ+索引”及び“地域Ｂ+索引”がそれぞれ図９Ｂ及び図９Ｃに示されたところのようであると仮定する。
【００８０】
(例題１)”名称”に対して”現代”と”自動車”を含むレコードを検索しなさい。
【００８１】
検索質疑を論理式で表現すると次のようである。
【００８２】
名称(“現代” ＡＮＤ “自動車”)
先ず、図１０Ａに示されたところのように、“現代”キーワードで索引から検索してハッシュに挿入演算を遂行する。
【００８３】
次に、図１０Ｂに示されたところのように、“自動車”キーワードで索引から検索してハッシュにＡＮＤロジッグ演算を遂行する。
【００８４】
そうすると、検索結果は図１０Ｃに示されたところのようである。
【００８５】
例題１に対するプログラムコードは次のように記述されることができる。
【００８６】
LogicHash hash;//ハッシュ客体
hash.StartUp(LOGIC_AND、１、１００);//ロジッグオペレーター、オペレーター個数、予想バケット個数
hash.Insert({１使用者データ});//挿入演算
hash.Insert({２使用者データ});
hash.Insert({４使用者データ});
hash.Logic(１、{１使用者データ});//ＡＮＤロジッグ演算
hash.Logic(１、{４使用者データ});
hash.Logic(１、{５使用者データ});
int size＝hash.Size();//結果個数獲得
for(int i＝０;i<size;i++){//検索結果確認
{バケット}＝hash.Next();
}
hash.CleanUp();//ハッシュ資源解除
(例題２)“名称”に対して“現代”または“自動車”を含むレコードを検索しなさい。
【００８７】
検索質疑を論理式で表現すると次のようである。
【００８８】
名称(“現代” ＯＲ “自動車”)
先ず、図１１Ａに示されたところのように、“現代”キーワードで索引から検索してハッシュに挿入演算を遂行する。
【００８９】
次に、図１１Ｂに示されたところのように、“自動車”キーワードで索引から検索してハッシュにＯＲロジッグ演算を遂行する。
【００９０】
そうすると、検索結果は図１１Ｃに示されたところのようである。
【００９１】
例題２に対するプログラムコードは次のように記述されることができる。
【００９２】
LogicHash hash;//ハッシュ客体
hash.StartUp(LOGIC_OR、１、１００);//ロジッグオペレーター、オペレーター個数、予想バケット個数
hash.Insert({１使用者データ});//挿入演算
hash.Insert({２使用者データ});
hash.Insert({４使用者データ});
hash.Logic(１、{１使用者データ});//ＯＲロジッグ演算
hash.Logic(１、{４使用者データ});
hash.Logic(１、{５使用者データ});
int size＝hash.Size();//結果個数獲得
for(int i＝０;i<size;i++){//検索結果確認
{バケット}＝hash.Next();
}
hash.CleanUp();//ハッシュ資源解除
(例題３)“名称”に対して“現代”を含んで、“地域”が“ソウル”であるレコードを検索しなさい。
【００９３】
検索質疑を論理式で表現すると次のようである。
【００９４】
名称(“現代”)  ＡＮＤ  地域(“ソウル”)
先ず、図１２Ａに示されたところのように、“現代”キーワードで索引から検索してハッシュに挿入演算を遂行する。
【００９５】
次に、図１２Ｂに示されたところのように、“ソウル”キーワードで索引から検索してハッシュにＡＮＤロジッグ演算を遂行する。
【００９６】
そうすると、検索結果は図１２Ｃに示されたところのようである。
【００９７】
例題３に対するプログラムコードは次のように記述されることができる。
【００９８】
LogicHash hash;//ハッシュ客体
hash.StartUp(LOGIC_AND、１、１００);//ロジッグオペレーター、オペレーター個数、予想バケット個数
hash.Insert({１使用者データ});//挿入演算
hash.Insert({２使用者データ});
hash.Insert({４使用者データ});
hash.Logic(１、{１使用者データ});//ＡＮＤロジッグ演算
hash.Logic(１、{２使用者データ});
int size＝hash.Size();//結果個数獲得
for(int i＝０;i<size;i++){//検索結果確認
{バケット}＝hash.Next();
}
hash.CleanUp();//ハッシュ資源解除
(例題４)“名称”に対して“現代”と“自動車”と“洗車場”を含むレコードを検索しなさい。
【００９９】
検索質疑を論理式で表現すると次のようである。
【０１００】
名称(“現代”  ＡＮＤ  “自動車”  ＡＮＤ  “洗車場”)
先ず、図１３Ａに示されたところのように、“現代”キーワードで索引から検索してハッシュに挿入演算を遂行する。
【０１０１】
次に、図１３Ｂに示されたところのように、“自動車”キーワードで索引から検索してハッシュに１次ＡＮＤロジッグ演算を遂行する。
【０１０２】
次に、図１３Ｃに示されたところのように、“洗車場”キーワードで索引から検索してハッシュに２次ＡＮＤロジッグ演算を遂行する。
【０１０３】
そうすると、検索結果は図１３Ｄに示されたところのようである。
【０１０４】
例題４に対するプログラムコードは、次のように記述されることができる。
【０１０５】
LogicHash hash;//ハッシュ客体
hash.StartUp(LOGIC_AND、２、１００);//ロジッグオペレーター、オペレーター個数、予想バケット個数
hash.Insert({１使用者データ});//挿入演算
hash.Insert({２使用者データ});
hash.Insert({４使用者データ});
hash.Logic(１、{１使用者データ});//１次ＡＮＤロジッグ演算
hash.Logic(１、{４使用者データ});
hash.Logic(１、{５使用者データ});
hash.Logic(２、{４使用者データ});//２次ＡＮＤロジッグ演算
int size＝hash.Size();//結果個数獲得
for(int i＝０;i<size;i++){//検索結果確認
{バケット}＝hash.Next();
}
hash.CleanUp();//ハッシュ資源解除
(例題５)“名称”に対して“現代”または”天国”を含んで、“地域”が“大田”であるレコードを検索しなさい。
【０１０６】
検索質疑を論理式で表現すると次のようである。
【０１０７】
名称(“現代”  ＯＲ  ”天国”)ＡＮＤ地域(“大田”)
先ず、図１４Ａに示されたところのように、“現代”キーワードで索引から検索してハッシュに挿入演算を遂行する。
【０１０８】
次に、図１４Ｂに示されたところのように、“天国”キーワードで索引から検索してハッシュにＯＲロジッグ演算を遂行する。
【０１０９】
次に、図１４Ｃに示されたところのように、ロジッグオペレーターがＯＲからＡＮＤに変更されるので、ハッシュ資料構造にロジッグ状態を変更する。
【０１１０】
次に、図１４Ｄに示されたところのように、“大田”キーワードで索引から検索してハッシュにＡＮＤロジッグ演算を遂行する。
【０１１１】
そうすると、検索結果は図１４Ｅに示されたところのようである。
【０１１２】
例題５に対するプログラムコードは、次のように記述されることができる。
【０１１３】
LogicHash hash;//ハッシュ客体
hash.StartUp(LOGIC_OR、１、１００);//ロジッグオペレーター、オペレーター個数、予想バケット個数
hash.Insert({１使用者データ});//挿入演算
hash.Insert({２使用者データ});
hash.Insert({４使用者データ});
hash.Logic(１、{３使用者データ});//ＯＲロジッグ演算
hash.ChangeLogic(LOGIC_AND、１);//ハッシュ資料構造のロジッグ状態変更
hash.Logic(１、{３使用者データ});//ＡＮＤロジッグ演算
hash.Logic(１、{４使用者データ});
int size＝hash.Size();//結果個数獲得
for(int i＝０;i<size;i++){//検索結果確認
{バケット}＝hash.Next();
}
hash.CleanUp();//ハッシュ資源解除
一方、前述した本発明の実施例は、個人用コンピューターを含んだ汎用コンピューターで使用される媒体に記録されることができる。前記媒体はマグネチック記録媒体(例えば、ロム(Read Only Memory)、フロッピー（登録商標）、ハードディスクなど)、光学的判読媒体(例えば、シーディーロム、ディーブイディーなど)、電気的記録媒体(例えば、フレッシュメモリー、メモリースティックなど)及びキャリアウエーブ(例えば、インターネットを通じた伝送)のような記録媒体を含む。
【産業上の利用可能性】
【０１１４】
以上説明したように、本発明によれば、ハッシュを利用して全体的なリソースを減らすことで制限されたシステム資源を効果的に活用することができるし、メモリー断片化を抑制して利用可能なシステム資源を増加させることができるし、したがって、円滑なサービスの提供が可能で、性能上の利得も確保することができる。
【０１１５】
特に、メモリーコンパクション機能が一般ＰＣより単純なモバイル端末機上ではその期待効果がさらに大きい。
【図１】
2015532498.tif 000003
【図２】
2015532498.tif 000004
【図３】
2015532498.tif 000005
【図４】
2015532498.tif 000006
【図５】
2015532498.tif 000007
【図６】
2015532498.tif 000008
【図７】
2015532498.tif 000009
【図８】
2015532498.tif 000010
【図９ａ】
2015532498.tif 000011
【図９ｂ】
2015532498.tif 000012
【図９ｃ】
2015532498.tif 000013
【図１０ａ】
2015532498.tif 000014
【図１１ａ】
2015532498.tif 000015
【図１１ｃ】
2015532498.tif 000016
【図１２ａ】
2015532498.tif 000017
【図１３ａ】
2015532498.tif 000018
【図１４ａ】
2015532498.tif 000019
【図１０ｂ】
2015532498.tif 000020
【図１０ｃ】
2015532498.tif 000021
【図１１ｂ】
2015532498.tif 000022
【図１２ｂ】
2015532498.tif 000023
【図１２ｃ】
2015532498.tif 000024
【図１３ｂ】
2015532498.tif 000025
【図１３ｃ】
2015532498.tif 000026
【図１３ｄ】
2015532498.tif 000027
【図１４ｂ】
2015532498.tif 000028
【図１４ｃ】
2015532498.tif 000029
【図１４ｄ】
2015532498.tif 000030
【図１４ｅ】
2015532498.tif 000031
【国際調査報告】
2015532498.tif 000032
2015532498.tif 000033
2015532498.tif 000034
2015532498.tif 000035