(57)【要約】【課題】インデックスを用いたデータ検索をおこなう際に、インデックスによるＲＡＭのメモリ容量の圧迫やＣＰＵの負荷を軽減しつつ、効率的なデータ検索をおこなうことを課題とする。【解決手段】登録データ１０４ａの中から所望の検索行を検索する際に、操作パネル１０１から検索語が受け付けると、ハッシュテーブル１０５ａとポインタを持つノードのノードテーブル１０５ｂからなるインデックス１０５を用いて検索処理部１０７が登録データ１０４ａから検索語に対応する検索行を検索する。【選択図】      図１
2004234108.tif 000002
【特許請求の範囲】
【請求項１】
相互に関連する複数の項目に関する各項目データにより形成される複数の検索行からなる登録データを有し、所望の検索語が入力された際に所定の検索構造を有するインデックスを用いて該検索語に対応する検索行を前記登録データから検索するデータ検索装置であって、
前記複数の検索行に含まれる所定の項目に関する各項目データに対してそれぞれポインタにより形成されるノードを割り当て、前記検索構造にしたがって該ノードをリンクしたインデックスと、
前記インデックスに基づいて前記登録データの中から所望の検索語に対応する検索行を検索する検索手段と
を備えたことを特徴とするデータ検索装置。
【請求項２】
前記インデックスは、所定のハッシュテーブルと各ノードが有するポインタにより形成されるリスト構造とにより形成され、前記検索手段は、前記ハッシュテーブルのうち前記検索語にハッシュ関数を適用したハッシュ値の部分にリンクされた各ノードを辿りつつ前記登録データの中から当該検索語に対応する検索行を検索することを特徴とする請求項１に記載のデータ検索装置。
【請求項３】
前記インデックスは、前記複数の検索行に含まれる所定の項目に関する各項目データに対してそれぞれハッシュ関数を適用してハッシュ値を算定し、前記ハッシュテーブルのうち該ハッシュ値の部分に前記項目データに対応するノードをリンクするとともに、各ノードに対してハッシュテーブルまたは他のノードへのポインタを付与することにより形成されることを特徴とする請求項２に記載のデータ検索装置。
【請求項４】
前記インデックスは、前記登録データに新たな検索行が追加される場合には、該新たな検索行に含まれる所定の項目に関する項目データに対してハッシュ関数を適用してハッシュ値を算定し、前記ハッシュテーブルのうち該ハッシュ値の部分に前記新たな項目データに対応するノードをリンクするとともに、該新たな検索行に含まれる所定の項目に関する項目データに割り当てたノードに対してハッシュテーブルまたは他のノードへのポインタを付与することを特徴とする請求項３に記載のデータ検索装置。
【請求項５】
前記インデックスは、前記登録データから所定の検索行が削除される場合には、該検索行に含まれる所定の項目に関する項目データに割り当てたノードのポインタを削除するとともに、該ノードにリンクされるハッシュテーブルまたは他のノードのポインタを変更することを特徴とする請求項３または４に記載のデータ検索装置。
【請求項６】
前記インデックスは、各ノードが有するポインタにより形成される２分木構造により形成され、前記検索手段は、前記検索語に所定の関数を適用した関数値にしたがって前記２分木構造をなす各ノードを辿りつつ前記登録データの中から当該検索語に対応する検索行を検索することを特徴とする請求項１に記載のデータ検索装置。
【請求項７】
前記インデックスは、前記複数の検索行に含まれる所定の項目に関する各項目データに対してそれぞれ所定の関数を適用して関数値を算定し、前記関数値に基づいて２分木構造をなすようノードをリンクするとともに、各ノードに対して連接するノードへのポインタを付与することにより形成されることを特徴とする請求項６に記載のデータ検索装置。
【請求項８】
前記インデックスは、前記登録データに新たな検索行が追加される場合には、該新たな検索行に含まれる所定の項目に関する項目データに対して所定の関数を適用して関数値を算定し、前記２分木構造に前記新たな項目データに対応するノードをリンクするとともに、該新たな検索行に含まれる所定の項目に関する項目データに割り当てたノードに対して連接するノードへのポインタを付与することを特徴とする請求項７に記載のデータ検索装置。
【請求項９】
前記インデックスは、前記登録データから所定の検索行が削除される場合には、該検索行に含まれる所定の項目に関する項目データに割り当てたノードのポインタを削除するとともに、該ノードにリンクされる他のノードのポインタを変更することを特徴とする請求項７または８に記載のデータ検索装置。
【請求項１０】
各ノードの識別番号と該ノードが割り当てられた項目データを有する検索行の行番号とを一致させることを特徴とする請求項１〜９のいずれか一つに記載のデータ検索装置。
【請求項１１】
前記インデックスは、前記登録データの各項目ごとに設けられ、前記検索手段は、所望の項目に関する検索語が入力された際に該項目に対応するインデックスに基づいて前記登録データの中から当該検索語に対応する検索行を検索することを特徴とする請求項１〜１０のいずれか一つに記載のデータ検索装置。
【請求項１２】
相互に関連する複数の項目に関する各項目データにより形成される複数の検索行からなる登録データを有し、所望の検索語が入力された際に所定の検索構造を有するインデックスを用いて該検索語に対応する検索行を前記登録データから検索するデータ検索方法であって、
前記複数の検索行に含まれる所定の項目に関する各項目データに対してそれぞれポインタにより形成されるノードを割り当てる工程と、
前記検索構造にしたがって該ノードをリンクしたインデックスに基づいて前記登録データの中から所望の検索語に対応する検索行を検索する工程と
を含んだことを特徴とするデータ検索方法。
【請求項１３】
相互に関連する複数の項目に関する各項目データにより形成される複数の検索行からなる登録データを有し、所望の検索語が入力された際に所定の検索構造を有するインデックスを用いて該検索語に対応する検索行を前記登録データから検索するデータ検索プログラムであって、
前記複数の検索行に含まれる所定の項目に関する各項目データに対してそれぞれポインタにより形成されるノードを割り当てる手順と、
前記検索構造にしたがって該ノードをリンクしたインデックスに基づいて前記登録データの中から所望の検索語に対応する検索行を検索する手順と
をコンピュータに実行させることを特徴とするデータ検索プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、相互に関連する複数の項目に関する各項目データにより形成される複数の検索行からなる登録データを有し、所望の検索語が入力された際に所定の検索構造を有するインデックスを用いて該検索語に対応する検索行を登録データから検索するデータ検索装置、データ検索方法およびデータ検索プログラムに関し、特に、インデックスを用いたデータ検索をおこなう際に、インデックスによるＲＡＭのメモリ容量の圧迫やＣＰＵの負荷を軽減しつつ、効率的なデータ検索をおこなうことができるデータ検索装置、データ検索方法およびデータ検索プログラムに関する。
【０００２】
【従来の技術】
従来、データベースに蓄積された大量のデータをリレーショナル論理を用いて検索するリレーショナルデータベースが広く知られている。このリレーショナルデータベースでは、正規化された複数の検索用テーブルを準備しておき、そのうちのいくつかの検索用テーブルを用いてデータの検索をおこなうことになる。このため、このリレーショナルデータベースによれば、複数の検索用テーブルおよびＳＱＬ言語を用いた高度なデータ検索をおこなうことができる。
【０００３】
ところで、かかるリレーショナルデータベースは、大型コンピュータやワークステーションを用いて膨大なデータを検索する場合には極めて有効なものであるが、パソコンのハードディスクに格納されたデータなどを検索する際には、その処理負荷が大きすぎて採用できない。
【０００４】
このため、簡易なインデックスを用いてハードディスク内のデータを効率良く検索する技術が知られている。たとえば、特許文献１には、ＲＡＭ上に構築されたインデックスをハードディスクの所定のエリアに書き込み、再起動時にハードディスクに待避したインデックスをＲＡＭ上に再構築する商品販売登録データ装置が開示されている。
【０００５】
【特許文献１】
特開平８−２３５０７９号公報
【０００６】
【発明が解決しようとする課題】
しかしながら、この特許文献１に代表されるインデックスを用いた従来のデータ検索技術によれば、検索効率を上げようとすればするほどインデックスのサイズが大きくなるので、インデックスがＲＡＭのメモリ容量を圧迫するとともにＣＰＵに負荷をかける原因になるという問題がある。
【０００７】
具体的には、従来のデータ検索技術に用いるインデックスは、少なくともキーワードなどの実データをその一部に含んでいるので、このインデックスのサイズが大きくなればなるほど多くのメモリ容量が必要となる。加えて、従来のデータ検索技術では、一つのインデックスですべての検索に対応することが前提となるので、主記憶であるＲＡＭ上に記憶せねばならないメモリ容量は、インデックスが大きくなればなるほど累増する。
【０００８】
特に、かかるデータ検索技術をカーナビやカーコンポなどの車載用装置に適用しようとすると、コストや搭載スペースの関係で車載用装置にはこれらデータ検索に十分なＲＡＭ容量を確保できないことが多いので、データ検索処理が該車載用装置上で動作する他のアプリケーションに悪影響を及ぼし、もって車載用装置全体のパフォーマンスの低下につながるおそれがある。
【０００９】
これらのことから、インデックスを用いたデータ検索をおこなう際に、インデックスによるＲＡＭのメモリ容量の圧迫やＣＰＵの負荷を軽減しつつ、効率的なデータ検索をいかにしておこなうかが重要な課題となっている。
【００１０】
この発明は、上述した従来技術による課題（問題点）を解消するためになされたものであって、インデックスを用いたデータ検索をおこなう際に、インデックスによるＲＡＭのメモリ容量の圧迫やＣＰＵの負荷を軽減しつつ、効率的なデータ検索をおこなうことができるデータ検索装置、データ検索方法およびデータ検索プログラムを提供することを目的とする。
【００１１】
【課題を解決するための手段】
上述した課題を解決し、目的を達成するため、請求項１の発明に係るデータ検索装置は、相互に関連する複数の項目に関する各項目データにより形成される複数の検索行からなる登録データを有し、所望の検索語が入力された際に所定の検索構造を有するインデックスを用いて該検索語に対応する検索行を前記登録データから検索するデータ検索装置であって、前記複数の検索行に含まれる所定の項目に関する各項目データに対してそれぞれポインタにより形成されるノードを割り当て、前記検索構造にしたがって該ノードをリンクしたインデックスと、前記インデックスに基づいて前記登録データの中から所望の検索語に対応する検索行を検索する検索手段とを備えたことを特徴とする。
【００１２】
この請求項１の発明によれば、複数の検索行に含まれる所定の項目に関する各項目データに対してそれぞれポインタにより形成されるノードを割り当て、検索構造にしたがって該ノードをリンクしたインデックスに基づいて前記登録データの中から所望の検索語に対応する検索行を検索することとしたので、データ容量の少ないポインタからなるインデックスによる検索をおこなうことができる。
【００１３】
また、請求項２の発明に係るデータ検索装置は、請求項１の発明において、前記インデックスは、所定のハッシュテーブルと各ノードが有するポインタにより形成されるリスト構造とにより形成され、前記検索手段は、前記ハッシュテーブルのうち前記検索語にハッシュ関数を適用したハッシュ値の部分にリンクされた各ノードを辿りつつ前記登録データの中から当該検索語に対応する検索行を検索することを特徴とする。
【００１４】
この請求項２の発明によれば、インデックスが、所定のハッシュテーブルと各ノードが有するポインタにより形成されるリスト構造とにより形成され、ハッシュテーブルのうち検索語にハッシュ関数を適用したハッシュ値の部分にリンクされた各ノードを辿りつつ登録データの中から当該検索語に対応する検索行を検索することとしたので、データ量の少ないハッシュテーブルとポインタによりインデックスを形成することができる。
【００１５】
また、請求項３の発明に係るデータ検索装置は、請求項２の発明において、前記インデックスは、前記複数の検索行に含まれる所定の項目に関する各項目データに対してそれぞれハッシュ関数を適用してハッシュ値を算定し、前記ハッシュテーブルのうち該ハッシュ値の部分に前記項目データに対応するノードをリンクするとともに、各ノードに対してハッシュテーブルまたは他のノードへのポインタを付与することにより形成されることを特徴とする。
【００１６】
この請求項３の発明によれば、複数の検索行に含まれる所定の項目に関する各項目データに対してそれぞれハッシュ関数を適用してハッシュ値を算定し、ハッシュテーブルのうち該ハッシュ値の部分に項目データに対応するノードをリンクするとともに、各ノードに対してハッシュテーブルまたは他のノードへのポインタを付与することによりインデックスを形成することとしたので、効率良くインデックスを形成することができる。
【００１７】
また、請求項４の発明に係るデータ検索装置は、請求項３の発明において、前記インデックスは、前記登録データに新たな検索行が追加される場合には、該新たな検索行に含まれる所定の項目に関する項目データに対してハッシュ関数を適用してハッシュ値を算定し、前記ハッシュテーブルのうち該ハッシュ値の部分に前記新たな項目データに対応するノードをリンクするとともに、該新たな検索行に含まれる所定の項目に関する項目データに割り当てたノードに対してハッシュテーブルまたは他のノードへのポインタを付与することを特徴とする。
【００１８】
この請求項４の発明によれば、登録データに新たな検索行が追加される場合には、該新たな検索行に含まれる所定の項目に関する項目データに対してハッシュ関数を適用してハッシュ値を算定し、ハッシュテーブルのうち該ハッシュ値の部分に新たな項目データに対応するノードをリンクするとともに、該新たな検索行に含まれる所定の項目に関する項目データに割り当てたノードに対してハッシュテーブルまたは他のノードへのポインタを付与することとしたので、登録データに新たな検索行を追加する場合のインデックスの更新を効率良くおこなうことができる。
【００１９】
また、請求項５の発明に係るデータ検索装置は、請求項３または４の発明において、前記インデックスは、前記登録データから所定の検索行が削除される場合には、該検索行に含まれる所定の項目に関する項目データに割り当てたノードのポインタを削除するとともに、該ノードにリンクされるハッシュテーブルまたは他のノードのポインタを変更することを特徴とする。
【００２０】
この請求項５の発明によれば、登録データから所定の検索行が削除される場合には、該検索行に含まれる所定の項目に関する項目データに割り当てたノードのポインタを削除するとともに、該ノードにリンクされるハッシュテーブルまたは他のノードのポインタを変更することとしたので、登録データから検索行を削除する場合のインデックスの更新を効率良くおこなうことができる。
【００２１】
また、請求項６の発明に係るデータ検索装置は、請求項１の発明において、前記インデックスは、各ノードが有するポインタにより形成される２分木構造により形成され、前記検索手段は、前記検索語に所定の関数を適用した関数値にしたがって前記２分木構造をなす各ノードを辿りつつ前記登録データの中から当該検索語に対応する検索行を検索することを特徴とする。
【００２２】
この請求項６の発明によれば、インデックスが、各ノードが有するポインタにより形成される２分木構造により形成され、検索語に所定の関数を適用した関数値にしたがって２分木構造をなす各ノードを辿りつつ登録データの中から当該検索語に対応する検索行を検索することとしたので、ハッシュテーブルなどを用いることなくノードのリンク関係のみでインデックスを形成することができる。
【００２３】
また、請求項７の発明に係るデータ検索装置は、請求項６の発明において、前記インデックスは、前記複数の検索行に含まれる所定の項目に関する各項目データに対してそれぞれ所定の関数を適用して関数値を算定し、前記関数値に基づいて２分木構造をなすようノードをリンクするとともに、各ノードに対して連接するノードへのポインタを付与することにより形成されることを特徴とする。
【００２４】
この請求項７の発明によれば、複数の検索行に含まれる所定の項目に関する各項目データに対してそれぞれ所定の関数を適用して関数値を算定し、この関数値に基づいて２分木構造をなすようノードをリンクするとともに、各ノードに対して連接するノードへのポインタを付与することによりインデックスを形成することとしたので、データ量の少ないポインタのみを用いて２分木構造を用いた効率的な検索を実現するインデックスを形成することができる。
【００２５】
また、請求項８の発明に係るデータ検索装置は、請求項７の発明において、前記インデックスは、前記登録データに新たな検索行が追加される場合には、該新たな検索行に含まれる所定の項目に関する項目データに対して所定の関数を適用して関数値を算定し、前記２分木構造に前記新たな項目データに対応するノードをリンクするとともに、該新たな検索行に含まれる所定の項目に関する項目データに割り当てたノードに対して連接するノードへのポインタを付与することを特徴とする。
【００２６】
この請求項８の発明によれば、登録データに新たな検索行が追加される場合には、該新たな検索行に含まれる所定の項目に関する項目データに対して所定の関数を適用して関数値を算定し、２分木構造に新たな項目データに対応するノードをリンクするとともに、該新たな検索行に含まれる所定の項目に関する項目データに割り当てたノードに対して連接するノードへのポインタを付与することとしたので、登録データに新たな検索行を追加する場合のインデックスの更新を効率良くおこなうことができる。
【００２７】
また、請求項９の発明に係るデータ検索装置は、請求項７または８の発明において、前記インデックスは、前記登録データから所定の検索行が削除される場合には、該検索行に含まれる所定の項目に関する項目データに割り当てたノードのポインタを削除するとともに、該ノードにリンクされる他のノードのポインタを変更することを特徴とする。
【００２８】
この請求項９の発明によれば、登録データから所定の検索行が削除される場合には、該検索行に含まれる所定の項目に関する項目データに割り当てたノードのポインタを削除するとともに、該ノードにリンクされる他のノードのポインタを変更することとしたので、登録データから検索行を削除する場合のインデックスの更新を効率良くおこなうことができる。
【００２９】
また、請求項１０の発明に係るデータ検索装置は、請求項１〜９の発明において、各ノードの識別番号と該ノードが割り当てられた項目データを有する検索行の行番号とを一致させることを特徴とする。
【００３０】
この請求項１０の発明によれば、各ノードの識別番号と該ノードが割り当てられた項目データを有する検索行の行番号とを一致させることとしたので、ノードと項目データの関係を一意に特定することができる。
【００３１】
また、請求項１１の発明に係るデータ検索装置は、請求項１〜１０の発明において、前記インデックスは、前記登録データの各項目ごとに設けられ、前記検索手段は、所望の項目に関する検索語が入力された際に該項目に対応するインデックスに基づいて前記登録データの中から当該検索語に対応する検索行を検索することを特徴とする。
【００３２】
この請求項１１の発明によれば、インデックスは、登録データの各項目ごとに設けられ、所望の項目に関する検索語が入力された際に該項目に対応するインデックスに基づいて登録データの中から当該検索語に対応する検索行を検索することとしたので、メモリ上には全てのインデックスではなく必要なインデックスのみをロードできる。
【００３３】
また、請求項１２の発明に係るデータ検索方法は、相互に関連する複数の項目に関する各項目データにより形成される複数の検索行からなる登録データを有し、所望の検索語が入力された際に所定の検索構造を有するインデックスを用いて該検索語に対応する検索行を前記登録データから検索するデータ検索方法であって、前記複数の検索行に含まれる所定の項目に関する各項目データに対してそれぞれポインタにより形成されるノードを割り当てる工程と、前記検索構造にしたがって該ノードをリンクしたインデックスに基づいて前記登録データの中から所望の検索語に対応する検索行を検索する工程とを含んだことを特徴とする。
【００３４】
この請求項１２の発明によれば、複数の検索行に含まれる所定の項目に関する各項目データに対してそれぞれポインタにより形成されるノードを割り当て、検索構造にしたがって該ノードをリンクしたインデックスに基づいて前記登録データの中から所望の検索語に対応する検索行を検索することとしたので、データ容量の少ないポインタからなるインデックスによる検索をおこなうことができる。
【００３５】
また、請求項１３の発明に係るデータ検索プログラムは、相互に関連する複数の項目に関する各項目データにより形成される複数の検索行からなる登録データを有し、所望の検索語が入力された際に所定の検索構造を有するインデックスを用いて該検索語に対応する検索行を前記登録データから検索するデータ検索プログラムであって、前記複数の検索行に含まれる所定の項目に関する各項目データに対してそれぞれポインタにより形成されるノードを割り当てる手順と、前記検索構造にしたがって該ノードをリンクしたインデックスに基づいて前記登録データの中から所望の検索語に対応する検索行を検索する手順とをコンピュータに実行させることを特徴とする。
【００３６】
この請求項１３の発明によれば、複数の検索行に含まれる所定の項目に関する各項目データに対してそれぞれポインタにより形成されるノードを割り当て、検索構造にしたがって該ノードをリンクしたインデックスに基づいて前記登録データの中から所望の検索語に対応する検索行を検索することとしたので、データ容量の少ないポインタからなるインデックスによる検索をおこなうことができる。
【００３７】
【発明の実施の形態】
以下に添付図面を参照して、この発明に係るデータ検索装置、データ検索方法およびデータ検索プログラムの好適な実施の形態を詳細に説明する。本実施の形態では、多数の音楽データを保有するカーオーディオなどの車載用音楽再生装置に本発明を適用した場合を示しており、インデックスを用いて所望の音楽データを検索し、その音楽データを再生できる場合を例示している。なお、下記に示す実施の形態１では、ハッシュテーブルを用いた検索構造を利用する場合を示し、実施の形態２では、２分木の検索構造を利用する場合を示している。
【００３８】
（実施の形態１）
まず最初に、本実施の形態１に係るデータ検索装置の構成について説明する。図１は、本実施の形態１に係るデータ検索装置１００の構成を示す機能ブロック図である。同図に示すデータ検索装置１００は、検索に用いるインデックス１０５をハッシュテーブル１０５ａとノードテーブル１０５ｂで構成した点にその特徴がある。その詳細な説明は後述するが、ノードテーブル１０５ｂの各ノードは実データではなくポインタのみを持つので、インデックス１０５のデータ容量が少なくなり、インデックス１０５のデータ量が大きくなることに起因するメインメモリの圧迫やＣＰＵの負担を軽減することができる。
【００３９】
図１に示すように、このデータ検索装置１００は、操作パネル１０１と、ディスプレイ１０２と、スピーカ１０３と、記憶部１０４と、インデックス１０５と、インデックス作成／更新処理部１０６と、検索処理部１０７と、音楽再生部１０８と、制御部１０９とを有する。
【００４０】
操作パネル１０１は、ユーザがデータ検索装置１００の各種操作をおこなうための操作部であり、ユーザが検索語を入力する場合などに利用される。ディスプレイ１０２は、液晶パネルなどの表示デバイスであり、検索結果の表示などをおこなう際に利用される。この操作パネル１０１とディスプレイ１０２は、一体のものとして形成することもできる。スピーカ１０３は、音楽データを再生する際に利用されるスピーカである。
【００４１】
記憶部１０４は、ハードディスク装置（ＨＤＤ）などの２次記憶装置であり、多数の音楽データ１０４ｂや登録データ１０４ａなどを記憶する。ここで、この音楽データ１０４ｂは、ｍｐｅｇやｍｐ３などによって圧縮された圧縮データであり、映像を伴うデータであっても構わない。登録データ１０４ａは、各音楽データの属性であるアルバム名、アーティスト名、日付、タイトルおよびファイル名を検索行として登録したデータであり、ユーザが所望の検索行をインデックスを用いて検索する際に利用される被検索対象物である。なお、本実施の形態では、登録データ１０４ａに登録された相互に関連する複数の項目に関する各項目データからなるデータを検索行と呼ぶことにするが、この検索行は、必ずしも登録データ１０４ａの一行である必要はなく一行の一部若しくは数行であっても良い。
【００４２】
インデックス１０５は、登録データ１０４ａから所望の検索行を検索する際に利用される所定の検索構造を有するインデックスであり、ハッシュテーブル１０５ａとノードテーブル１０５ｂとにより形成されている。ここで、本実施の形態１では、このインデックス１０５内に実データを保持させるのではなく、ノードの概念を利用してポインタのみで形成する点にその特徴がある。かかるインデックス１０５は、図５に示すようなハッシュテーブルとノードのリンクドリストからなるため、インデックス１０５内に実データを持たない。なお、ハッシュテーブル１０５ａとノードテーブル１０５ｂについての詳細な説明は後述する。
【００４３】
また、かかるインデックス１０５は、登録データ１０４ａの項目（列）ごとに設けられ、所望のインデックスのみを用いて検索行を検索できるようにした点にも特徴がある。その詳細な説明は後述するが、かかるインデックス１０５は、図５に示すように登録データ１０４ａの項目（列）ごと（アルバム用、アーティスト用、ファイル名用など）に設けられるので、全てのインデックスをメインメモリであるＲＡＭ上に保持する必要がなく、メインメモリの有効利用を図ることができる。
【００４４】
インデックス作成／更新処理部１０６は、インデックス１０５の作成および更新をおこなう処理部であり、具体的には、記憶部１０４に記憶した登録データ１０４ａを検索するためのインデックスが全く存在しない場合にはこの登録データ１０４ａに基づいてインデックス１０５を作成する。また、登録データ１０４ａに新たな検索行が追加された場合や登録データ１０４ａから検索行が削除された場合には、インデックス１０５の更新をおこなう。
【００４５】
検索処理部１０７は、インデックス１０５を利用して登録データ１０４ａの中から所望の検索行を検索する処理部であり、具体的には、ユーザにより操作パネル１０１から検索語が入力された場合に、図５に示したインデックス１０５を辿ってノードを特定し、このノードに対応する検索行のデータを出力する。
【００４６】
音楽再生部１０８は、音楽データ１０４ｂを再生する処理部であり、具体的には、検索結果としてディスプレイに表示された検索行のうち所望のファイル名（または検索行）を操作パネル１０１によって選択された際に、該ファイル名に対応する音楽データ１０４ｂを再生処理する。なお、音楽データの再生に係る部分は本発明の特徴部分ではないので、その詳細な説明を省略する。
【００４７】
制御部１０９は、データ検索装置１００の全体制御をおこなう制御部であり、各機能部間の各種データの授受などを司る制御部である。たとえば、インデックス作成／更新処理部１０６や検索処理部１０７が機能発揮する場合にはインデックス１０５が必要となるので、その間のデータ授受をおこなったり必要に応じてインデックスのデータ書き替えなどもおこなう。
【００４８】
次に、図１に示したデータ検索装置１００のハードウエア構成について説明する。図２は、本実施の形態１に係るデータ検索装置１００のハードウエア構成を示す図である。なお、図１に示す機能部と同様の機能を有する部位には同一の符号を付している。
【００４９】
同図に示すように、かかるデータ検索装置１００は、操作パネル１０１、ディスプレイ１０２、スピーカ１０３、ＲＡＭ１１０、ＨＤＤ１２０、ＲＯＭ１４０およびＣＰＵ１５０をバス１６０で接続した構成となる。すなわち、このデータ検索装置１００は、車載用のカーナビやカーコンポなどと同様のハードウエア構成となる。
【００５０】
ＲＯＭ１４０には、インデックス作成／更新プログラム１４１、検索処理プログラム１４２および音楽再生プログラム１４３があらかじめ記憶され、各プログラム１４１〜１４３がＣＰＵ１５０にロードし実行されて、インデックス作成／更新プロセス１５１、検索処理プロセス１５２および音楽再生プロセス１５３となる。このインデックス作成／更新プロセス１５１が図１のインデックス作成／更新処理部１０６に対応し、検索処理プロセス１５２が図１の検索処理部１０７に対応し、音楽再生プロセス１５３が図１の音楽再生部１０８に対応する。
【００５１】
また、ＨＤＤ１２０が格納および読み出し制御する記憶媒体であるハードディスク（ＨＤ）には、複数のハッシュテーブル１３１、ノードテーブル１３２、音楽データ１０４ｂおよび登録データ１０４ａが記憶されている。ハッシュテーブル１３１は、登録データ１０４ａの項目（列）ごとに設けられ、そのうちの所望のハッシュテーブル１０５ａがメインメモリであるＲＡＭ１１０上にロードされる。また、ノードテーブル１３２についてもＲＡＭ１１０上にノードテーブル１０５ｂとしてロードされる。このようにしてＲＡＭ１１０上にロードされたハッシュテーブル１０５ａとノードテーブル１０５ｂがインデックス１０５となる。
【００５２】
このため、ＲＡＭ１１０上には、すべてのインデックス１３１ではなく一部のインデックス１０５ａをロードすれば足りるので、インデックス１３１によるＲＡＭ１１０のメモリ容量の圧迫を軽減することができる。また、ＣＰＵ１５０はＲＡＭ１１０をメインメモリとして使用するので、このメインメモリを有効利用できることになり、結果的にＣＰＵ１１０の負荷を軽減することもできる。なお、ここではＨＤＤ１２０に複数のハッシュテーブル１３１およびノードテーブル１３２を記憶することとしたが、ＣＤ−Ｒ／Ｗなどの他の記憶媒体に格納することもできる。
【００５３】
次に、図１および図２に示した登録データ１０４ａの一例について説明する。図３は、図１および図２に示した登録データ１０４ａの一例を示す図である。同図に示すように、ここではアルバム名、アーティスト名、日付、タイトル、ファイル名を項目とし、データ番号０〜５の６つの検索行を有する場合を示している。
【００５４】
具体的には、データ番号０の検索行は、アルバム名「Ａｌｂｕｍ  Ａ」、アーティスト名「ａａａ」、日付「２００２．１．１」、タイトル「ｔｉｔｌｅ  ＡＢＣ」、ファイル名「ＡＢＣ．ｍｐ３」の項目データを有し、データ番号１の検索行は、アルバム名「Ａｌｂｕｍ  Ｂ」、アーティスト名「ｂｂｂ」、日付「２００２．２．２」、タイトル「ｔｉｔｌｅ  ＤＥＦ」、ファイル名「ＤＥＦ．ｍｐ３」の項目データを有する。データ番号２〜５の検索行についても同様の項目データを有する。
【００５５】
この登録データ１０４ａからいずれかの項目データを検索語として入力すると、インデックスを形成するハッシュテーブル１０５ａおよびノードテーブル１０５ｂのリンクドリストを辿って項目データの検索行（データ番号）が判明することになる。
【００５６】
次に、図１および図２に示したノードテーブル１０５ｂの一例について説明する。図４は、図１および図２に示したノードテーブル１０５ｂの一例を示す図である。同図に示すように、このノードテーブル１０５ｂは、登録データ１０４ａの各項目データに割り当てるノード群からなるテーブルであるので、少なくとも登録データ１０４ａの各項目データ分のノードを保持する。なお、ノードの追加に対応すべく項目データ数より多めのノード数を有することが望ましい。
【００５７】
具体的には、登録データ１０４ａの項目であるアルバム名、アーティスト名、日付、タイトルおよびファイル名ごとに複数のノードを設け、各ノードの識別情報と登録データ１０４ａのデータ番号（行番号）とを一致させる。たとえば、ノード００は項目データ「Ａｌｂｕｍ  Ａ」に対応させ、ノード０１は項目データ「ＡｌｂｕｍＢ」に対応し、ノード０２は項目データ「Ａｌｂｕｍ  Ｃ」に対応させ、ノード１０は項目データ「ａａａ」に対応させ、ノード１１は項目データ「ｂｂｂ」に対応させる。
【００５８】
このようにする理由は、登録データ１０４ａの各項目データと各ノードの対応関係を明確にするためである。すなわち、各ノードの識別情報と登録データ１０４ａのデータ番号（行番号）とを一致させなくとも、テーブルで両者の関係を管理すれば対応関係を保持できることになるが、その場合には新たなデータ（テーブル）を要することになる。本実施の形態では、メモリ容量の低減を主眼においているので、両者を一致させることにより、項目データとノードの対応関係に要するデータ増加を防ぐこととした。ただし、必ずしも両者を一致させる必要はなく、デフォルト値を加算するなど一定の関係にあれば両者の関係を容易に把握することができる。
【００５９】
次に、図１および図２に示したインデックス１０５の一例について説明する。図５は、図１および図２に示したインデックス１０５の一例を示す図であり、図６は、図５に示した各インデックスのデータ構造を示す図である。
【００６０】
かかるインデックス１０５は、登録データ１０４ａの項目であるアルバム名、アーティスト名、日付、タイトルおよびファイル名ごとに設けられており、図５に示すように、アルバム名用インデックス２１０、アーティスト名用インデックス２２０、ファイル名用インデックス２３０などからなる。
【００６１】
具体的には、アルバム名用インデックス２１０は、アルバム名用ハッシュテーブル２１１とアルバム名の項目データに対応するノードのリンクドリストからなり、アーティスト名用インデックス２２０は、アーティスト名用ハッシュテーブル２２１とアーティスト名の項目データに対応するノードのリンクドリストからなり、ファイル名用インデックス２３０は、ファイル名用ハッシュテーブル２３１とファイル名の項目データに対応するノードのリンクドリストからなる。ただし、各項目データに対応するノードのリンクドリストは、ノードテーブル１０５ｂのノード自身が保持しており、リンク情報をノードと別個に持つわけではない。
【００６２】
図６に示すように、ハッシュテーブル３０１の各項目には、リンクされる先頭のノードへのポインタが格納され、ノード３０２は、ハッシュテーブル３０１の項目ｉへのポインタと次ノード３０３へのポインタを有し、ノード３０３も同様のポインタを有する。ノード３０３がリンク元ノード３０２へのポインタを有する理由は、ノード３０２が削除された場合のリンク関係の更新に対応するためである。
【００６３】
ここで、Ｃ言語などの高級言語を用いて本発明に係るデータ検索プログラムを実現する場合には、たとえばハッシュテーブル３０１用の配列ＨＡＳＨ［ｌ］と、ノードテーブル１０５ｂ用の配列ＮＯＤＥ［ｍ］［ｎ］を準備しておき、配列ＮＯＤＥ［ｍ］［ｎ］の各配列値として、リンク先ノードまたはリンク先ハッシュテーブルの配列要素へのポインタを格納すれば良い。たとえば、図６の場合には、ノード３０２に対応する配列要素には、ハッシュテーブル３０１のｉ番目に対応する配列要素ＨＡＳＨ［ｌ］へのポインタを示す＆ＨＡＳＨ［ｉ］と、ノード３０３に対応する配列要素ＮＯＤＥ［ｊ］［ｋ］へのポインタを示す＆ＮＯＤＥ［ｊ］［ｋ］とが配列値として格納されることになる。なお、ここでは説明の便宜上配列を用いた場合を示したが、ポインタ変数を用いることもできる。
【００６４】
次に、図１に示したインデックス作成／更新処理部１０６によるインデックスの作成手順について説明する。図７は、図１に示したインデックス作成／更新処理部１０６によるインデックスの作成手順を示すフローチャートであり、図８は、図１に示したインデックス作成／更新処理部１０６によるインデックス作成時の概念図である。
【００６５】
図７に示すように、まず登録データ１０４ａの項目である列数分のハッシュテーブルを準備するとともに（ステップＳ７０１）、項目データを割り当てるノード数を有するノードテーブル１０５ｂを準備し（ステップＳ７０２）、登録データ１０４ａの項目データとノードテーブル１０５ｂの各ノードとを対応付ける（ステップＳ７０３）。具体的には、図８（ａ）に示すように、アーティスト名の各項目データとノードテーブルのノード１０〜ノード１５を対応付ける。
【００６６】
そして、列変数ｘと行変数ｙを０に初期化した後（ステップＳ７０３〜Ｓ７０４）、項目データｘｙのハッシュ値を算定し（ステップＳ７０６）、ハッシュテーブル１０５ａの該当項目にノードｘｙをリンクさせる（ステップＳ７０７）。具体的には、図８（ｂ）に示すように、アーティスト名の項目データ「ａａａ」にハッシュ関数ｈを適用してｈ（ａａａ）＝ｉを計算し、アーティスト名用ハッシュテーブル２１１のｉ番目の項目に項目データ「ａａａ」に対応するノード１０をリンクする。すなわち、アーティスト名用ハッシュテーブル２１１のｉ番目の項目にノード１０へのポインタを格納するとともに、ノード１０にアーティスト名用ハッシュテーブル２１１のｉ番目の項目へのポインタを格納する。
【００６７】
その後、行変数ｙをインクリメントして（ステップＳ７０８）、未処理の検索行があるか否かを確認し（ステップＳ７０９）、未処理の検索行がある場合には（ステップＳ７０９肯定）、ステップＳ７０６に移行して同様の処理をおこなう。これにより、図８（ｃ）に示したアーティスト名用インデックスが作成できる。
【００６８】
一方、未処理の検索行がない場合には（ステップＳ７０９否定）、列変数ｘをインクリメントして次の項目（列）に移行させた後（ステップＳ７１０）、未処理の項目（列）がある場合には（ステップＳ７１１肯定）、ステップＳ７０５に移行して同様の処理をおこなう。なお、未処理の項目（列）がなくなった時点で（ステップＳ７１１否定）、処理を終了する。
【００６９】
次に、図１に示した検索処理部１０７による検索手順について説明する。図９は、図１に示した検索処理部１０７による検索手順を示すフローチャートである。同図に示すように、この検索処理部１０７は、操作対象となる登録データ１０４ａの項目（列）に対応するインデックスをメインメモリ上に読み込み（ステップＳ９０１）、操作パネル１０１上で検索文字列ａ（検索語）を受け付けたならば（ステップＳ９０２）、この検索文字列ａのハッシュ値ｈ（ａ）を算定する（ステップＳ９０３）。
【００７０】
その後、ハッシュテーブル１０５ａ内の項目ｈ（ａ）にリンクされたノードを特定した後（ステップＳ９０４）、このノードから登録データ１０４ａの検索行を示すデータ番号を特定し（ステップＳ９０５）、該検索行のデータが検索文字列ａに適合するか否かを判定する（ステップＳ９０６）。
【００７１】
具体的には、かかるハッシュテーブル１０５ａの項目ｈ（ａ）には、図６を用いて説明したように、リンクされる先頭ノードへのポインタが格納されているので、このノードをまず最初に特定する。ここで、このノードの識別情報（ノードが配列として形成されている場合には配列番号）は、登録データ１０４ａの検索行を示すデータ番号（行番号）と一致させているので、検索行を示すデータ番号が特定される。したがって、登録データ１０４ａから検索行のデータを取り出し、取り出したデータが検索文字列ａに適合するか否かを判定することになる。なお、かかる適合判定は、たとえば検索文字列ａがデータ内に含まれるか否かで判定することができる。
【００７２】
そして、検索行のデータが検索文字列ａに適合しない場合には（ステップＳ９０６否定）、次のノードに移行すべくステップＳ９０４に移行して同様の処理を繰り返し（現ノードにおける次ノードへのポインタに従いノードを移行）、検索行のデータが検索文字列ａに適合した場合には（ステップＳ９０６肯定）、該当する検索行を登録データからロードして（ステップＳ９０７）、上記一連の処理を終了する。なお、ここでは一つの検索行のみがヒットする場合を示したが、複数の検索行がヒットする可能性がある場合には、ハッシュテーブル１０５ａの該当項目にリンクされたすべてのノードに対して処理をおこなった後に一連の処理を終了する。
【００７３】
次に、図１に示したインデックス作成／更新処理部１０６による検索行削除時の更新処理手順について説明する。図１０は、図１に示したインデックス作成／更新処理部１０６による検索行削除時の更新処理手順を示すフローチャートであり、図１１は、図１に示したインデックス作成／更新処理部１０６による検索行削除時のインデックス更新概念を示す図である。
【００７４】
図１０に示すように、登録データ１０４ａから削除する検索行（削除対象行）を受け付けたならば（ステップＳ１００１）、列変数ｘを０に初期化した後（ステップＳ１００２）、登録データ１０４ａから削除対象行のｘ列目の項目データｂを取り出し（ステップＳ１００３）、この項目データｂのハッシュ値ｈ（ｂ）を算定する（ステップＳ１００４）。
【００７５】
その後、ハッシュテーブル１０５ａ内の項目ｈ（ｂ）にリンクされた該当ノードを特定し（ステップＳ１００５）、このノードのリンク先のノードが有するポインタを変更する（ステップＳ１００６）。具体的には、図１１（ａ）に示すデータ番号４の検索行を削除する場合には、同図（ｂ）に示すようにアーティスト用インデックスを辿ってノード１４を特定し、このノード１４の前後にリンクするノード１０およびノード１６のポインタを更新し、ノード１０にノード１６がリンクされる状態とする。これにより、ノード１４すなわち削除対象行のアーティスト名「ｅｅｅ」がインデックス１０５から削除されることになる。
【００７６】
その後、列変数ｘをインクリメントして（ステップＳ１００７）、未処理のインデックス１０５がある場合は（ステップＳ１００８肯定）、ステップＳ１００３に移行して同様の処理を繰り返し、未処理のインデックス１０５がなくなった時点で（ステップＳ１００８否定）、登録データ１０４ａから削除対象行を削除して（ステップＳ１００９）、処理を終了する。
【００７７】
次に、図１に示したインデックス作成／更新処理部１０６による検索行追加時の更新処理手順について説明する。図１２は、図１に示したインデックス作成／更新処理部１０６による検索行追加時の更新処理手順を示すフローチャートであり、図１３は、図１に示したインデックス作成／更新処理部１０６による検索行追加時のインデックス更新概念を示す図である。
【００７８】
図１２に示すように、登録データ１０４ａに追加する検索行に係る追加データ（一行分）を受け付けたならば（ステップＳ１２０１）、列変数ｘを０に初期化した後（ステップＳ１２０２）、追加データのｘ番目の項目データｃを取り出し（ステップＳ１２０３）、項目データｃ用の新たなノードをノードテーブル１０５ｂに登録するとともに（ステップＳ１２０４）、この項目データｃのハッシュ値ｈ（ｃ）を算定する（ステップＳ１２０５）。
【００７９】
その後、ハッシュテーブル１０５ａ内の項目ｈ（ｃ）にリンクされた最終ノードに項目データｃ用の新たなノードをリンクする（ステップＳ１２０６）。具体的には、図１３（ａ）に示すデータ番号６の検索行を追加する場合には、まずノードテーブル１０５ｂに項目データ「ｇｇｇ」に対応するノード１６を追加する。その後、同図（ｂ）に示すようにアーティスト用インデックスを辿って最終ノードであるノード１４を特定し、このノード１４の後に項目データ「ｇｇｇ」に対応するノード１６をリンクする。これにより、アーティスト用インデックスに項目データ「ｇｇｇ」に対応するノードが追加されることになる。
【００８０】
その後、列変数ｘをインクリメントして（ステップＳ１２０７）、追加データに未処理の項目データがある場合は（ステップＳ１２０８肯定）、ステップＳ１２０３に移行して同様の処理を繰り返し、未処理の項目データがなくなった時点で（ステップＳ１２０８否定）、処理を終了する。
【００８１】
上述してきたように、本実施の形態１では、登録データ１０４ａの中から所望の検索行を検索する際に、操作パネル１０１から検索語が受け付けると、ハッシュテーブル１０５ａとポインタを持つノードのノードテーブル１０５ｂからなるインデックス１０５を用いて検索処理部１０７が登録データ１０４ａから検索語に対応する検索行を検索するよう構成したので、インデックスによるＲＡＭのメモリ容量の圧迫やＣＰＵの負荷を軽減しつつ、効率的なデータ検索をおこなうことができる。
【００８２】
（実施の形態２）
ところで、上記実施の形態１では、ハッシュテーブル１０５ａとノードテーブル１０５ｂからなるインデックス１０５を用いた場合を示したが、本発明はこれに限定されるものではなく、ハッシュ関数以外の他の検索構造を用いた場合に適用することもできる。そこで、本実施の形態２では、２分木を検索構造とする場合について説明する。なお、上記実施の形態１とほぼ同様の部分については簡単に説明する。
【００８３】
まず、２分木構造を用いた場合の機能ブロック図およびハードウエア構成図は、実施の形態１で示した図１および図２とほぼ同様のものとなり、インデックス１０５の構造のみが相違する。そこで、本実施の形態２では、インデックスの構造を中心に説明する。
【００８４】
図１４は、本実施の形態２で用いるインデックスの概念およびデータ構造を説明するための説明図であり、図１５は、本実施の形態２で用いるインデックスの一例を示す図である。
【００８５】
図１４（ａ）に示すように、この場合のインデックスは、ハッシュテーブルのようなものはなく、ノードのみをリンクした構造となり、図３の登録データ１０４ａのアーティスト名用インデックスを作成すると同図（ａ）のようになる。
【００８６】
具体的には、ある関数ｇを準備しておき、項目が「アーティスト名」の各項目データａａａ〜ｆｆｆに関数ｇを適用し、ｇ（ａａａ）＝０．２、ｇ（ｂｂｂ）＝０．４、ｇ（ｃｃｃ）＝０．５、ｇ（ｄｄｄ）＝０．６、ｇ（ｅｅｅ）＝０．７、ｇ（ｆｆｆ）＝０．８となった場合には、この関数値が２分木構造となるようにノード間のリンクを決定する。これにより、同図（ａ）に示すリンク関係が形成できる。
【００８７】
ここで、各ノードのリンク関係は、図１に示したノードテーブル１０５ｂで保持する点については上記実施の形態１と同様であるが、保持すべき内容が実施の形態１の場合と異なる。具体的には、図１４（ｂ）に示すように、各ノードは、上位ノードへのポインタと、左ノードへのポインタと、右ノードへのポインタの３つを有する。このため、ノードテーブル１０５ｂの各ノードは、この３種類のポインタをそれぞれ保持することになる。
【００８８】
また、本実施の形態２に係るインデックス１０５は、実施の形態１と同様に、登録データ１０４ａの項目（列）ごとに作成され、具体的には図１５に示すように、アルバム名用インデックス４１０、アーティスト名用インデックス４２０、ファイル名用インデックス４３０などからなる。各インデックスは、図１に示したハッシュテーブル１０５ａを必要としないので、より一層インデックスに係るデータ容量を低減することができる。
【００８９】
また、インデックス作成／更新処理部１０６によるインデックスの作成処理および更新処理は、ハッシュテーブル１０５ａに関する事項を除いてほぼ実施の形態１のものと同様になる。具体的には、インデックスを作成する場合には、複数の検索行に含まれる所定の項目に関する各項目データに対してそれぞれ所定の関数を適用して関数値を算定し、この関数値に基づいて２分木構造をなすようノードをリンクするとともに、各ノードに対して連接するノードへのポインタを付与することになる。
【００９０】
一方、登録データ１０４ａに新たな検索行が追加される場合には、該新たな検索行に含まれる所定の項目に関する項目データに対して所定の関数を適用して関数値を算定し、２分木構造に新たな項目データに対応するノードをリンクするとともに、該新たな検索行に含まれる所定の項目に関する項目データに割り当てたノードに対して連接するノードへのポインタを付与することになる。また、登録データ１０４ａから所定の検索行が削除される場合には、該検索行に含まれる所定の項目に関する項目データに割り当てたノードのポインタを削除するとともに、該ノードにリンクされる他のノードのポインタを変更することになる。
【００９１】
さらに、検索処理部１０７により検索をおこなう際には、インデックス１０５のノードのリンク関係（検索構造）を辿って検索をおこなうことになる。具体的には、検索語に所定の関数を適用した関数値にしたがって２分木構造をなす各ノードを辿りつつ登録データ１０４ａの中から当該検索語に対応する検索行を検索することになる。
【００９２】
上述してきたように、本実施の形態２では、登録データ１０４ａの中から所望の検索行を検索する際に、操作パネル１０１から検索語が受け付けると、２分木の検索構造を有するノードテーブル１０５ｂからなるインデックス１０５を用いて検索処理部１０７が登録データ１０４ａから検索語に対応する検索行を検索するよう構成したので、インデックスによるＲＡＭのメモリ容量の圧迫やＣＰＵの負荷をより一層軽減しつつ、効率的なデータ検索をおこなうことができる。
【００９３】
なお、本実施の形態１および２では、本発明を音楽データを検索する場合について説明したが、本発明はこれに限定されるものではなく、画像データや映像データなど各種マルチメディアデータを検索する場合など様々なデータを検索する場合に適用することができる。
【００９４】
また、本実施の形態１および２では、検索構造としてハッシュ関数と２分木構造を用いる場合を示したが、本発明はこれに限定されるものではなく、他の検索構造を用いる場合に適用することもできる。
【００９５】
【発明の効果】
以上説明したように、請求項１の発明によれば、複数の検索行に含まれる所定の項目に関する各項目データに対してそれぞれポインタにより形成されるノードを割り当て、検索構造にしたがって該ノードをリンクしたインデックスに基づいて前記登録データの中から所望の検索語に対応する検索行を検索するよう構成したので、データ容量の少ないポインタからなるインデックスによる検索をおこなうことができ、もってＲＡＭのメモリ容量の圧迫やＣＰＵの負荷を軽減することが可能となる。
【００９６】
また、請求項２の発明によれば、インデックスが、所定のハッシュテーブルと各ノードが有するポインタにより形成されるリスト構造とにより形成され、ハッシュテーブルのうち検索語にハッシュ関数を適用したハッシュ値の部分にリンクされた各ノードを辿りつつ登録データの中から当該検索語に対応する検索行を検索するよう構成したので、データ量の少ないハッシュテーブルとポインタによりインデックスを形成することができ、これによりＲＡＭのメモリ容量の圧迫やＣＰＵの負荷を軽減することが可能となる。
【００９７】
また、請求項３の発明によれば、複数の検索行に含まれる所定の項目に関する各項目データに対してそれぞれハッシュ関数を適用してハッシュ値を算定し、ハッシュテーブルのうち該ハッシュ値の部分に項目データに対応するノードをリンクするとともに、各ノードに対してハッシュテーブルまたは他のノードへのポインタを付与することによりインデックスを形成するよう構成したので、効率良くインデックスを形成することができる。
【００９８】
また、請求項４の発明によれば、登録データに新たな検索行が追加される場合には、該新たな検索行に含まれる所定の項目に関する項目データに対してハッシュ関数を適用してハッシュ値を算定し、ハッシュテーブルのうち該ハッシュ値の部分に新たな項目データに対応するノードをリンクするとともに、該新たな検索行に含まれる所定の項目に関する項目データに割り当てたノードに対してハッシュテーブルまたは他のノードへのポインタを付与するよう構成したので、登録データに新たな検索行を追加する場合のインデックスの更新を効率良くおこなうことができる。
【００９９】
また、請求項５の発明によれば、登録データから所定の検索行が削除される場合には、該検索行に含まれる所定の項目に関する項目データに割り当てたノードのポインタを削除するとともに、該ノードにリンクされるハッシュテーブルまたは他のノードのポインタを変更するよう構成したので、登録データから検索行を削除する場合のインデックスの更新を効率良くおこなうことができる。
【０１００】
また、請求項６の発明によれば、インデックスが、各ノードが有するポインタにより形成される２分木構造により形成され、検索語に所定の関数を適用した関数値にしたがって２分木構造をなす各ノードを辿りつつ登録データの中から当該検索語に対応する検索行を検索するよう構成したので、ハッシュテーブルなどを用いることなくノードのリンク関係のみでインデックスを形成することができる。
【０１０１】
また、請求項７の発明によれば、複数の検索行に含まれる所定の項目に関する各項目データに対してそれぞれ所定の関数を適用して関数値を算定し、この関数値に基づいて２分木構造をなすようノードをリンクするとともに、各ノードに対して連接するノードへのポインタを付与することによりインデックスを形成するよう構成したので、データ量の少ないポインタのみを用いて２分木構造を用いた効率的な検索を実現するインデックスを形成することができ、これによりＲＡＭのメモリ容量の圧迫やＣＰＵの負荷を軽減することが可能となる。
【０１０２】
また、請求項８の発明によれば、登録データに新たな検索行が追加される場合には、該新たな検索行に含まれる所定の項目に関する項目データに対して所定の関数を適用して関数値を算定し、２分木構造に新たな項目データに対応するノードをリンクするとともに、該新たな検索行に含まれる所定の項目に関する項目データに割り当てたノードに対して連接するノードへのポインタを付与するよう構成したので、登録データに新たな検索行を追加する場合のインデックスの更新を効率良くおこなうことができる。
【０１０３】
また、請求項９の発明によれば、登録データから所定の検索行が削除される場合には、該検索行に含まれる所定の項目に関する項目データに割り当てたノードのポインタを削除するとともに、該ノードにリンクされる他のノードのポインタを変更するよう構成したので、登録データから検索行を削除する場合のインデックスの更新を効率良くおこなうことができる。
【０１０４】
また、請求項１０の発明によれば、各ノードの識別番号と該ノードが割り当てられた項目データを有する検索行の行番号とを一致させるよう構成したので、ノードと項目データの関係を一意に特定することができ、もって検索効率をより一層高めることができる。
【０１０５】
また、請求項１１の発明によれば、インデックスは、登録データの各項目ごとに設けられ、所望の項目に関する検索語が入力された際に該項目に対応するインデックスに基づいて登録データの中から当該検索語に対応する検索行を検索するよう構成したので、メモリ上には全てのインデックスではなく必要なインデックスのみをロードすれば足り、もってＲＡＭのメモリ容量の圧迫やＣＰＵの負荷をより一層軽減することが可能となる。
【０１０６】
また、請求項１２の発明によれば、複数の検索行に含まれる所定の項目に関する各項目データに対してそれぞれポインタにより形成されるノードを割り当て、検索構造にしたがって該ノードをリンクしたインデックスに基づいて前記登録データの中から所望の検索語に対応する検索行を検索するよう構成したので、データ容量の少ないポインタからなるインデックスによる検索をおこなうことができ、もってＲＡＭのメモリ容量の圧迫やＣＰＵの負荷を軽減することが可能となる。
【０１０７】
また、請求項１３の発明によれば、複数の検索行に含まれる所定の項目に関する各項目データに対してそれぞれポインタにより形成されるノードを割り当て、検索構造にしたがって該ノードをリンクしたインデックスに基づいて前記登録データの中から所望の検索語に対応する検索行を検索するよう構成したので、データ容量の少ないポインタからなるインデックスによる検索をおこなうことができ、もってＲＡＭのメモリ容量の圧迫やＣＰＵの負荷を軽減することが可能となる。
【図面の簡単な説明】
【図１】本実施の形態１に係るデータ検索装置の構成を示す機能ブロック図である。
【図２】本実施の形態１に係るデータ検索装置のハードウエア構成図である。
【図３】図１および図２に示した登録データの一例を示す図である。
【図４】図１および図２に示したノードテーブルの一例を示す図である。
【図５】図１および図２に示したインデックスの一例を示す図である。
【図６】図５に示した各インデックスのデータ構造を示す図である。
【図７】図１に示したインデックス作成／更新処理部によるインデックスの作成手順を示すフローチャートである。
【図８】図１に示したインデックス作成／更新処理部によるインデックス作成時の概念図である。
【図９】図１に示した検索処理部による検索手順を示すフローチャートである。
【図１０】、図１に示したインデックス作成／更新処理部による検索行削除時の更新処理手順を示すフローチャートである。
【図１１】図１に示したインデックス作成／更新処理部による検索行削除時のインデックス更新概念を示す図である。
【図１２】図１に示したインデックス作成／更新処理部による検索行追加時の更新処理手順を示すフローチャートである。
【図１３】１に示したインデックス作成／更新処理部による検索行追加時のインデックス更新概念を示す図である。
【図１４】本実施の形態２で用いるインデックスの概念およびデータ構造を説明するための説明図である。
【図１５】本実施の形態２で用いるインデックスの一例を示す図である。
【符号の説明】
１０１    操作パネル
１０２    ディスプレイ
１０３    スピーカ
１０４    記憶部
１０４ａ    登録データ
１０４ｂ    音楽データ
１０５    インデックス
１０５ａ    ハッシュテーブル
１０５ｂ    ノードテーブル
１０６    インデックス作成／更新処理部
１０７    検索処理部
１０８    音楽再生部
１０９    制御部
１１０    ＲＡＭ
１２０    ＨＤＤ（ハードディスクドライブ）
１３０    ＨＤ（ハードディスク）
１４０    ＲＯＭ
１５０    ＣＰＵ
１６０    バス
【図１】
2004234108.tif 000003
【図２】
2004234108.tif 000004
【図３】
2004234108.tif 000005
【図４】
2004234108.tif 000006
【図５】
2004234108.tif 000007
【図６】
2004234108.tif 000008
【図７】
2004234108.tif 000009
【図８】
2004234108.tif 000010
【図９】
2004234108.tif 000011
【図１０】
2004234108.tif 000012
【図１１】
2004234108.tif 000013
【図１２】
2004234108.tif 000014
【図１３】
2004234108.tif 000015
【図１４】
2004234108.tif 000016
【図１５】
2004234108.tif 000017