(57)【要約】【課題】多量のファイルの中から必要なファイルを迅速に検索できるファイル管理装置を提供する。【解決手段】映像を記録したファイルの日時データに含まれる日付コードをハッシュ値に変換し、このハッシュ値が共通するファイルを、ハッシュ値に応じてルートノードを設定した多分探索木で管理するファイル構造管理手段１４と、ハッシュ値と多分探索木のルートノードアドレスとの関係が記述されたハッシュ表を管理するハッシュ表管理手段１３と、入力日時データに含まれる日付コードをハッシュ値に変換し、ハッシュ表からハッシュ値に応じた多分探索木を選択する多分探索木選択手段１５と、この多分探索木のルートノードからノードを辿り、ノードに格納されたファイル情報から、入力日時が記録範囲に含まれるファイルを検索するファイル検索手段１５とを設ける。ファイルを多分探索木構造で管理しているため、検索時の比較回数が減り、検索を迅速化できる。【選択図】      図１
2004152239.tif 000002
【特許請求の範囲】
【請求項１】
映像及び音声の少なくとも一方を記録したファイルの日時データに含まれる日付コードをハッシュ値に変換し、前記ハッシュ値を同じくする１または複数の前記ファイルを、ルートノードが前記ハッシュ値によって決まる多分探索木の構造により管理し、
指定された記録日時の映像または音声を検索するときは、前記記録日時に含まれる日付コードをハッシュ値に変換してハッシュ算出値を求め、前記ハッシュ算出値に対応するルートノードから前記多分探索木のノードを辿り、それぞれのノードに格納されたファイル情報から、指定された記録日時データをキーにして、前記記録日時データが記録範囲に含まれるファイルを検索することを特徴とするファイル管理方法。
【請求項２】
前記ルートノードから辿った全てのノードを履歴ノードとして一時記録し、前記多分探索木の終端ノードに達しても指定された記録日時データが記録範囲に含まれるファイルを検出できないときに、前記履歴ノード及び終端ノードに格納されたファイル情報を基に、指定された記録日時に最も近い時刻に記録されたファイルを検索することを特徴とする請求項１に記載のファイル管理方法。
【請求項３】
前記ハッシュ算出値に対応するルートノードが存在しないとき、指定された記録日時と最も近い時刻に記録されたファイルを管理する多分探索木を求め、得られた多分探索木のルートノードからノードを辿ってファイル検索を行うことを特徴とする請求項１または２に記載のファイル管理方法。
【請求項４】
映像及び音声の少なくとも一方を記録した複数のファイルを、前記ファイルの日時データに含まれる日付コードを変換したハッシュ値ごとに区分し、前記ハッシュ値を同じくする１または複数の前記ファイルを、前記ハッシュ値に応じてルートノードを設定した多分探索木により管理するファイル構造管理手段と、
前記ハッシュ値と前記多分探索木のルートノードを示すデータとの関係が記述されたハッシュ表を管理するハッシュ表管理手段と、
指定された日時データに含まれる日付コードをハッシュ値に変換してハッシュ算出値を求め、前記ハッシュ表から、前記ハッシュ算出値に対応するルートノードを有する前記多分探索木を選択する多分探索木選択手段と、
選択された前記多分探索木の前記ルートノードからノードを辿り、それぞれのノードに格納されたファイル情報から、指定された日時データをキーにして、前記日時データが記録範囲に含まれるファイルを検索するファイル検索手段と
を備えることを特徴とするファイル管理装置。
【請求項５】
前記ファイル検索手段が、前記ルートノードから辿った全てのノードを履歴ノードとして一時記録する探索履歴記憶手段を備え、前記ファイル検索手段は、前記多分探索木の終端ノードに達しても、指定された記録日時データが記録範囲に含まれるファイルを検出できないときに、前記探索履歴記憶手段に一時記録された前記履歴ノード及び終端ノードのそれぞれに格納されたファイル情報から、前記日時データに最も近い時刻に記録されたファイルを検索することを特徴とする請求項４に記載のファイル管理装置。
【請求項６】
前記ハッシュ表管理手段が、前記ハッシュ値と前記多分探索木のルートノードを示すデータとの他に、前記多分探索木で管理される最古のデータの記録日時と、前記多分探索木で管理される最新のデータの記録日時とが記述された前記ハッシュ表を管理し、前記多分探索木選択手段は、前記ハッシュ算出値に対応するルートノードが前記ハッシュ表に記述されていないとき、前記ハッシュ表に記述された前記最古のデータの記録日時及び最新のデータの記録日時を参照して、指定された日時データと最も近い時刻に記録されたファイルを管理する多分探索木を選択することを特徴とする請求項４または５に記載のファイル管理装置。
【請求項７】
映像及び音声の少なくとも一方を記録した複数のファイルを管理するファイル管理装置のコンピュータの動作を規定するプログラムであって、
コンピュータに、
前記ファイルの日時データに含まれる日付コードをハッシュ関数に代入してハッシュ値に変換する手順と、
前記ハッシュ値を同じくする１または複数の前記ファイルを、ルートノードが前記ハッシュ値によって決まる多分探索木の構造により管理する手順と、
指定された日時データに含まれる日付コードをハッシュ値に変換してハッシュ算出値を求める手順と、
ハッシュ値と前記多分探索木のルートノードを示すデータとの関係が記述されたハッシュ表を参照して、前記ハッシュ算出値を基に、多分探索木のルートノードを選択する手順と、
選択された前記ルートノードから前記多分探索木の探索を開始し、ノードに格納されたファイル情報を基に、指定された日時データがファイルの記録範囲に含まれるかどうかを判定する手順と、
指定された日時データがファイルの記録範囲に含まれると判定したときは、当該ファイルを検索結果とし、指定された日時データがファイルの記録範囲に含まれないと判定したときは、前記多分探索木の次に辿るノードを決定する手順と
を実行させるためのプログラム。
【請求項８】
指定された前記日時データがファイルの記録範囲に含まれないと判定したときに、前記ファイルに関する情報を探索履歴テーブルに記録する手順と、前記多分探索木の終端ノードに達しても、指定された前記日時データを記録範囲に含むファイルが検出できないとき、前記探索履歴テーブルに記録したファイル情報と前記終端ノードに格納されたファイル情報とを参照し、それらの中から、指定された前記日時データに最も近い時刻に記録されたファイルを検索する手順と
を実行させるための請求項７に記載のプログラム。
【請求項９】
指定された前記日時データに含まれる日付コードをハッシュ値に変換してハッシュ算出値を求める手順と、ハッシュ値と、前記多分探索木のルートノードを示すデータと、前記多分探索木で管理される最古のデータの記録日時と、前記多分探索木で管理される最新のデータの記録日時とが記述された前記ハッシュ表を参照して、前記ハッシュ算出値を基に、多分探索木のルートノードを選択する手順と、前記ハッシュ算出値に対応するルートノードが前記ハッシュ表に記述されていないとき、前記ハッシュ表に記述された前記最古のデータの記録日時及び最新のデータの記録日時を基に、指定された日時データと最も近い時刻に記録されたファイルを管理する多分探索木を選択する手順とを実行させるための請求項７または８に記載のプログラム。
【請求項１０】
請求項７から請求項９までのいずれかに記載のプログラムを格納したことを特徴とする記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、多数のファイルを管理するファイル管理装置と、ファイル管理方法と、その方法を実現するコンピュータプログラムに関し、特に、監視カメラの映像ファイルなどを日時データをキーに管理できるようにしたものである。
【０００２】
【従来の技術】
従来、蓄積するデータの検索・読み出しを高速化する手法として、ハッシュ法という方法が知られている。この方法では、データの内容の一部（キーワード）に所定の演算を施し、演算結果の値を格納番地として使用する。この場合、キーワードの値の範囲を、それより狭い番地の範囲に変換できるので、格納したデータを読み出す際のデータの検索を迅速化できる。
【０００３】
下記に示す特許文献１には、このハッシュ法を利用してファイルを管理するファイル検索装置が開示されている。この装置は、図１１に示すように、ファイル管理情報を記憶する記憶装置１０３と、入力されたファイル名をハッシュ関数１０２を用いてハッシュ値に変換して、該当するファイルを検索するデータ処理装置１００とを備えている。
この記憶装置１０３には、ハッシュ値にディスクブロック番号を対応付けたハッシュ表１０４と、各ディスクブロック番号に対応する、一連のディレクトリエントリ列から成るディレクトリブロック１０５とが記憶されている。ハッシュ表１０４のハッシュ値は、各ファイルのファイル名の文字コードをハッシュ関数１０２に代入して得られるハッシュ値であり、ハッシュ関数１０２にファイル名の文字コードを代入したとき、同一のハッシュ値となる複数のファイルのディレクトリエントリは、同一のディレクトリブロック１０５に格納されている。
【０００４】
一方、データ処理装置１００は、入力されたファイル名からファイルを検索するファイル検索部１０１と、ファイル名をハッシュ値に変換するために用いるハッシュ関数１０２とを備えている。
ファイル検索部１０１は、ファイル名が入力すると、そのファイル名の文字コードをハッシュ関数１０２に代入してハッシュ値を算出し、得られたハッシュ値に対応するディスクブロック番号をハッシュ表１０４から取得する。
ハッシュ値が同一であるファイルのディレクトリエントリは、同一のディスクブロック１０５の中に配置されている。ファイル検索部１０１は、ハッシュ表１０４から得られたディスクブロック番号に該当するディレクトリブロック１０５のディレクトリエントリを順方向に検索し、対象ファイルを検索する。
【０００５】
このように、この装置では、ディレクトリエントリを記憶するディスクブロックの番号を、ファイル名をハッシュ関数１０２に代入して得られるハッシュ値に対応付けている。そして、ファイル検索部１０１は、ハッシュ関数１０２を使用して検索すべきファイルのハッシュ値を算出し、そのハッシュ値に対応するディスクブロック番号をハッシュ表１０４から特定し、前記番号を持つディレクトリブロック内に限定してディレクトリエントリを検索する。
【０００６】
【特許文献１】
特開２０００−３５７１１５号公報
【０００７】
【発明が解決しようとする課題】
しかし、従来のファイル検索装置では、ディレクトリエントリ数が増加し、同一のディレクトリブロック内のディレクトリエントリが増えると、順方向検索の処理に多くの時間が掛かるという問題点がある。また、ディレクトリエントリ数の増加により、同一のハッシュ値に対応するディレクトリエントリを一つのディスクブロック内に配置することが不可能になり、それらを複数のディスクブロックに跨って配置する場合には、順方向検索におけるディスクアクセス数の最大値が、跨いで記録されたディスクブロック数と等しくなるため、順方向検索処理時間は非常に長くなる。
【０００８】
特に、交通量や人通りを監視するために道路に設置された監視カメラや、銀行内の状況を監視するために設置された監視カメラなどの画像データを圧縮して記録する「監視用デジタルレコーダ」では、監視カメラから送られた大量の画像データを記録する必要があり、また、その中から特定の日時のデータを検索したり、あるいは、その日時に最も近い時期に撮影された画像データを検索したりする必要があるが、従来のファイル検索装置では、こうした画像データの検索要求を迅速に処理することができない。
【０００９】
本発明は、こうした従来の問題点を解決するものであり、管理する多量のファイルの中から必要なファイルを迅速に検索することができるファイル管理装置を提供し、また、そのファイル管理方法と、その方法を実現するコンピュータプログラムとを提供することを目的としている。
【００１０】
【課題を解決するための手段】
そこで、本発明のファイル管理方法では、映像及び音声の少なくとも一方を記録したファイルの日時データに含まれる日付コードをハッシュ値に変換し、このハッシュ値を同じくする１または複数のファイルを、ルートノードがハッシュ値によって決まる多分探索木の構造により管理し、指定された記録日時の映像または音声を検索するときは、その記録日時に含まれる日付コードをハッシュ値に変換してハッシュ算出値を求め、このハッシュ算出値に対応するルートノードから多分探索木のノードを辿り、それぞれのノードに格納されたファイル情報から、指定された記録日時データをキーにして、この記録日時データが記録範囲に含まれるファイルを検索するようにしている。
このように、多分探索木構造でファイルを管理しているため、ファイルを検索するときの比較回数を減らすことができ、検索結果が迅速に得られる。
【００１１】
また、本発明のファイル管理装置には、映像及び音声の少なくとも一方を記録した複数のファイルを、ファイルの日時データに含まれる日付コードを変換したハッシュ値ごとに区分し、このハッシュ値を同じくする１または複数のファイルを、ハッシュ値に応じてルートノードを設定した多分探索木により管理するファイル構造管理手段と、ハッシュ値と多分探索木のルートノードを示すデータとの関係が記述されたハッシュ表を管理するハッシュ表管理手段と、指定された日時データに含まれる日付コードをハッシュ値に変換してハッシュ算出値を求め、ハッシュ表から、ハッシュ算出値に対応するルートノードを有する多分探索木を選択する多分探索木選択手段と、選択された多分探索木のルートノードからノードを辿り、それぞれのノードに格納されたファイル情報から、指定された日時データをキーにして、この日時データが記録範囲に含まれるファイルを検索するファイル検索手段とを設けている。
このファイル管理装置では、１つのハッシュ値に対応付けられるファイルを多分探索木構造で管理しているため、検索処理における比較回数を減らすことができ、短時間で検索結果が得られる。
【００１２】
また、本発明のコンピュータプログラムは、コンピュータに、ファイルの日時データに含まれる日付コードをハッシュ関数に代入してハッシュ値に変換する手順と、ハッシュ値を同じくする１または複数のファイルを、ルートノードがハッシュ値によって決まる多分探索木の構造により管理する手順と、指定された日時データに含まれる日付コードをハッシュ値に変換してハッシュ算出値を求める手順と、ハッシュ値と多分探索木のルートノードを示すデータとの関係が記述されたハッシュ表を参照して、変換したハッシュ値を基に、多分探索木のルートノードを選択する手順と、選択された多分探索木のルートノードから探索を開始し、ノードに格納されたファイル情報を基に、指定された日時データがファイルの記録範囲に含まれるかどうかを判定する手順と、指定された日時データがファイルの記録範囲に含まれると判定したときは、当該ファイルを検索結果とし、指定された日時データがファイルの記録範囲に含まれないと判定したときは、多分探索木の次に辿るノードを決定する手順とを実行させる。
こうしたプログラムにより、大量のファイルを管理する場合でも、その中から必要なファイルを迅速に検索することができる。
【００１３】
【発明の実施の形態】
（第１の実施形態）
本発明の第１の実施形態におけるファイル管理装置１０は、ファイルを多分探索木構造により管理し、ファイルの作成日時の日付コードをハッシュ関数に代入して得られたハッシュ値を、多分探索木のルートノードに対応付けている。
この装置は、図１に示すように、ハッシュ値を算出するためのハッシュ関数１１と、ハッシュ値と多分探索木のルートノードアドレスとの対応関係を記述したハッシュ表を管理するハッシュ表管理手段１３と、ファイルの作成日時の日付コードをハッシュ関数１１に代入してハッシュ値を算出し、得られたハッシュ値に対応する多分探索木のルートノードのアドレスをハッシュ表から求め、検索対象となる多分探索木を決定する多分探索木選択手段１２と、ファイルの作成日時データをキーにして多分探索木をルートノードから探索し、該当するファイルを検索するファイル検索手段１５と、ファイル作成日時をキーにしてファイルを多分探索木構造で管理するファイル構造管理手段１４と、ファイルやその管理データを記憶する記録媒体１６とを備えている。
なお、多分探索木選択手段１２、ファイル検索手段１５及びファイル構造管理手段１４の機能は、この装置が内蔵するコンピュータにプログラムで規定した処理を行わせることにより実現する。
【００１４】
ここでは、記録媒体１６上に記録されているファイルを二分探索木構造で管理する場合について説明する。
記録媒体１６は、ハードディスクのように高速アクセスが可能な記録装置であり、１つまたは複数台の装置から構成される。この記録媒体１６には、ＪＰＥＧなどのフレーム内圧縮またはＭＰＥＧ２などのフレーム間圧縮が行われた映像音声データのファイルと、そのファイルに関する情報を記述したファイル管理テーブルとが記録され、そのファイル管理テーブルの各エントリにノード間のリンクを示すデータを付加することで二分探索木構造による管理が行われる。
【００１５】
ハッシュ表管理手段１３は、図２に示すように、ハッシュ値２１と、そのハッシュ値に対応付けられた二分探索木のルートノードアドレス２２とが記述されたハッシュ表２０を管理している。ハッシュ値２１は、ファイルの作成日時を表すデータの内、日付コードをハッシュ関数１１に代入して算出した値である。ルートノードアドレス２２は、二分探索木のルートノードとなるファイル管理テーブルのエントリの番号である。なお、ハッシュ値２１に対応するファイルが存在しなければ、ハッシュ表２１の対応するルートノードアドレス２２の値は無効（ＮＵＬＬ）値が付けられる。
【００１６】
ハッシュ表２０では、ハッシュ値ごとに、ハッシュ値２１とルートノードアドレス２２とから成る１つのエントリが割り当てられている。図２のハッシュ表２０の場合、Ｎ個のエントリ（Ｈｓ０〜ＨＳＮ−１）を有している。ハッシュ値Ｈｓ０、Ｈｓ１、Ｈｓ２、ＨｓＮ−２に対応付けられている二分探索木のルートノードは、それぞれファイル管理テーブルの１９、０、７１、１０００のエントリである。
【００１７】
図３は、ファイル管理テーブルの一例を示している。このファイル管理テーブル３０では、ファイルごとに１つのエントリ（ノード）が割り当てられており、１つのエントリは、ファイル情報３１、ノードアドレス０部３２、及び、ノードアドレス１部３３から構成されている。
ファイル情報３１は、少なくとも、ファイル名、ファイル作成日時を示すデータ、ファイル・データへのポインタ、ファイルの先頭映像音声データの記録日時を示すデータ、ファイルの終端映像音声データの記録日時を示すデータ等を含んでいる。なお、ファイル作成は、そのファイルの終端映像音声データが記録される直後に行われるものとする。
ノードアドレス０部３２は、着目するノードで管理されているファイルよりも作成時刻が古いファイルを管理するリンク先ノードのエントリの番号を保持している。作成時刻の古いファイルが存在しない場合は、ＥＯＮ（エンドオブノード）コードが記録される。
ノードアドレス１部３３は、着目するノードに管理されているファイルよりも作成時刻が新しいファイルを管理するリンク先ノードのエントリの番号を保持している。作成時刻が新しいファイルが存在しない場合は、ＥＯＮコードが記録される。
【００１８】
図３に示した例では、ファイル管理テーブル３０はＭ個のエントリで構成されている。
いま、エントリ番号０〜５のエントリには、記録媒体１６に記録されている６個のファイルに関する情報がそれぞれ格納されている。また、各ファイルのファイル作成日時の日付コード（０２／０３／３１）をハッシュ関数１１に代入することにより得られるハッシュ値は同値である。すなわち、エントリ番号０〜５のエントリに対応するファイルは、同じ多分探索木で管理される。図４は、図３に示したファイル管理テーブルの例を二分探索木で表したものである。エントリ番号０のエントリのノードアドレス０部３２には、エントリ番号０のファイルの作成日時（０２／０３／３１  １０：３０：００）よりも作成日時が古いファイルを管理するリンク先ノードのエントリ番号１が記録され、ノードアドレス１部３３には、エントリ番号０のファイルの作成日時（０２／０３／３１  １０：３０：００）よりも作成日時が新しいファイルを管理するリンク先ノードのエントリ番号４が記録されている。
【００１９】
このファイル管理テーブル３０は記録媒体１６に記録されており、ファイル管理テーブルの一部のエントリのみを高速アクセス可能な半導体メモリ（不図示）上に配置しておく。
多分探索木選択手段１２は、入力された日時データの日付コードをハッシュ関数１１に代入してハッシュ値を算出し、算出したハッシュ値に対応する多分探索木のルートノードを示すデータをハッシュ表２０から求め、検索対象となる多分探索木を決定する。また、多分検索木選択手段１２は、入力された日時データをキーに、検索対象に決定した多分探索木でのファイル検索をファイル検索手段１５に指示する。
【００２０】
ファイル検索手段１５は、多分探索木選択手段１２の指示により、入力された日時データをキーにして多分探索木のルートノードから探索を開始し、ノードに格納されたファイル情報３１を基に、ファイルに含まれる映像音声データの記録範囲（先頭映像音声データの記録日時と終端映像音声データの記録日時との間）に、入力日時データが含まれるかどうかを判定する。そして、含まれる場合には検索の終了を決定し、含まれない場合には、入力日時データが、このファイルの記録範囲より古ければ、ノードアドレス０部３２に記載された番号のエントリを次に検索すべきノードに決定し、逆に、このファイルの記録範囲より新しければ、ノードアドレス１部３３に記載された番号のエントリを次に検索すべきノードに決定する。
【００２１】
ファイル構造管理手段１４は、ファイル管理テーブル３０を管理する。ファイルが作成された場合には、ファイルに関する情報をファイル管理テーブルのエントリに登録するとともに、ファイル作成時間をキーにしてファイル管理テーブルのエントリを多分検索木に追加する処理を行う。また、ファイルが削除された場合には、そのファイルに対応するファイル管理テーブルのエントリを多分検索木から削除する処理を行う。
【００２２】
図５は、このファイル管理装置１０のファイル検索動作を示すフローチャートである。図５を用いて、ファイル管理装置１０が、入力された日時の映像音声データを含むファイルを検索するときの手順について説明する。なお、フローチャートでは“ステップ”を“Ｓ”で表示している。
多分木探索選択手段１２が、入力された日時データの日付コードをハッシュ関数１１に代入し、ハッシュ値を算出する（ステップ１０１）。ハッシュ値を算出すると、多分探索木選択手段１２は、そのハッシュ値に対応付けられた多分探索木のルートノードを示すデータを、ハッシュ表管理手段１３に記憶されているハッシュ表２０から求める（ステップ１０２）。
【００２３】
次いで、多分探索木選択手段１２は、ハッシュ表２０から多分探索木のルートノードのアドレスを取り出し、ファイル検索手段１５に対して、そのアドレスに対応するノードから多分探索木を探索して、入力された日時データをキーにファイル検索を行うように指示する（ステップ１０３）。
ファイル検索手段１５は、多分探索木選択手段１２のファイル検索要求を受け、入力された日時データをキーに、指定された多分探索木によるファイル検索を開始する。
【００２４】
ファイル検索手段１５は、探索ノードに対応するファイル管理テーブル３０のエントリの取得をファイル構造管理手段１４に要求する。ファイル構造管理手段１４は、ファイル検索手段１５の指示を受けて、ファイル管理テーブル３０から該当するエントリを検索し、ファイル検索手段１５に送信する。
ファイル検索手段１５は、ファイル構造管理手段１４から送られたファイル管理テーブルのエントリからファイル情報３１を取り出し（ステップ１０４）、ファイル情報の先頭映像音声データの記録日時を示すデータと、終端映像音声データの記録日時を示すデータとから、ステップ１０１で入力された日時データが記録範囲に含まれるかどうかを判定する（ステップ１０５）。
ファイル検索手段１５は、判定結果により、次のノードを決定するか、または検索の終了かを決定し、検索の終了を決定した場合（ステップ１０５でＹｅｓの場合）には、検索結果を多分探索木選択手段１２に返送し、検索処理を完了する（ステップ１０８）。
【００２５】
また、次のノードを決定した場合（ステップ１０５でＮｏの場合）には、ファイル検索手段１５は、決定した次のノードがノード終端を示すＥＯＮであるか否かを判定する（ステップ１０６）。次のノードが終端ノードである場合（ステップ１０６でＹｅｓの場合）は、終端ノードに対応したファイルを検索対象ファイルに決定し、検索結果を多分探索木選択手段１２に返送し、検索処理を完了する（ステップ１０８）。
また、次のノードが終端ノードでない場合（ステップ１０６でＮｏの場合）は、ステップ１０４以降の手順を繰り返す。
こうして検索したノードに格納されているファイル情報３１からファイル・データへのポインタを読み出すことにより、記録媒体１６に格納されている映像音声データへのアクセスが可能になる。
【００２６】
このように、このファイル管理装置１０では、ファイルのファイル作成日時の日付コードからハッシュ値を算出し、このハッシュ値が同値である１または複数のファイルを、ファイル作成日時をキーにして多分探索木構造で管理する。一方、日時を指定して映像音声データを検索する場合は、その日時の日付データをハッシュ関数に代入してハッシュ値を算出し、そのハッシュ値に対応する多分探索木のルートノードのアドレスをハッシュ表から求め、指定された日時データをキーに、多分探索木をルートノードから探索し、その日時データが記録範囲に含まれるファイルを探索する。
【００２７】
このファイル管理装置１０で行われるファイル管理方法では、多分探索木を用いてファイルを検索するため、順方向に逐次検索する従来の手法に比べて、検索回数を減らすことができる。例えば、検索対象物の数をＮとするとき、逐次検索では最大比較回数がＮとなるが、多分探索木（二分探索木）の場合の最大比較回数はｌｏｇ２Ｎであり、Ｎに比べて極めて小さい。
【００２８】
（第２の実施形態）
本発明の第２の実施形態では、指定された日時の映像が記録されていない場合に、最も近い時刻に記録された映像音声データが含まれるファイルを検出するファイル管理装置について説明する。このように、指定された日時と最も近い時刻に記録された映像を検出することは、監視用デジタルレコーダに求められている機能である。
このファイル管理装置は、図６に示すように、ファイル検索手段１５が検索したノードを順次記憶する探索履歴記憶部１７を備えている。
【００２９】
探索履歴記憶部１７は、図７に示すように、ファイル検索手段１５が検索したノードのエントリ番号５１と、ファイル作成日時５２とを、履歴番号とともに記述した探索履歴テーブル５０を記憶している。図７は、図４の多分探索木構造に対して、エントリ０、エントリ４の順にノード探索した場合の探索履歴テーブル５０を示している。
【００３０】
ファイル検索手段１５は、多分探索木の終端ノードまで検索しても指定された日時データを記録範囲に含むファイルが検出できなかった場合に、探索履歴記憶部１７の探索履歴テーブル５０に記述された各ノード及び終端ノードの中で、ファイル作成日時が指定された日時データに最も近いノードを検索結果のノードとして決定する。
その他の構成及び動作は、第１の実施形態（図１）と変わりがない。
【００３１】
図８は、このファイル管理装置１０のファイル検索動作を示すフローチャートである。図８を用いて、ファイル管理装置１０のファイル検索手順について説明する。
ステップ１０１からステップ１０６までの手順は、第１の実施形態（図５）の場合と同じであり、多分木探索選択手段１２は、入力された日時データの日付コードをハッシュ関数１１に代入してハッシュ値を算出し（ステップ１０１）、そのハッシュ値に対応付けられた多分探索木のルートノードを示すデータを、ハッシュ表管理手段１３のハッシュ表２０から求め（ステップ１０２）、ルートノードアドレスを取り出して、ファイル検索手段１５に対し、入力日時データをキーに多分探索木のルートノードからファイル検索を行うように指示する（ステップ１０３）。
【００３２】
多分探索木選択手段１２のファイル検索要求を受けたファイル検索手段１５は、入力日時データをキーに、指定されたルートノードから多分探索木でのファイル検索を開始する。
ファイル検索手段１５は、探索ノードに対応するファイル管理テーブル３０のエントリの取得をファイル構造管理手段１４に要求し、ファイル構造管理手段１４から送られたエントリからファイル情報３１を取り出し（ステップ１０４）、ファイル情報の先頭映像音声データの記録日時と終端映像音声データの記録日時との間の記録範囲に入力日時データが含まれるかどうかを判定する（ステップ１０５）。
【００３３】
ファイル検索手段１５は、その記録範囲に入力日時データが含まれる場合（ステップ１０５でＹｅｓの場合）には、そのファイル情報を検索結果として多分探索木選択手段１２に返送し、検索処理を完了する（ステップ１０８）。また、その記録範囲に入力日時データが含まれない場合（ステップ１０５でＮｏの場合）は、次のノードを決定し、決定した次のノードがノード終端を示すＥＯＮであるか否かを判定する（ステップ１０６）。
決定した次のノードが終端ノードでない場合（ステップ１０６でＮｏの場合）には、ファイル検索手段１５は、現在のノード（ステップ１０４でエントリを取得したノード）を探索履歴記憶部１７の探索履歴記憶テーブル５０に記録し（ステップ２０１）、次いで、ステップ１０４以降の手順を繰り返す。
【００３４】
また、決定した次のノードが終端ノードである場合（ステップ１０６でＹｅｓの場合）には、ファイル検索手段１５は、探索履歴記憶部１７の探索履歴記憶テーブル５０に記録された各ノードのファイル作成日時と、決定した次のノード（終端ノード）のファイル作成日時と、入力日時データとを比較し、ファイル作成日時が入力日時データに最も近いファイルを検出し（ステップ２０２）、そのファイルのファイル情報を検索結果として多分探索木選択手段１２に返送し、検索処理を完了する（ステップ１０８）。
このように、このファイル管理装置１０では、指定された日時の映像音声データが記録されていない場合に、最も近い時刻に記録された映像音声データが含まれるファイルを検索することができる。
【００３５】
（第３の実施形態）
本発明の第３の実施形態では、入力された日時データの日付コードから算出したハッシュ値に対応するファイルが記録されていない場合に、最も近い日時に記録された映像音声データを含むファイルを検索することができるファイル管理装置について説明する。
【００３６】
本発明の第２の実施形態におけるファイル管理装置では、入力日時データの日付コードから算出したハッシュ値に対応する多分探索木は存在する（従ってファイルは存在する）が、入力日時データを記録範囲に含むファイルは存在しない場合に、その入力日時データに最も近い時刻に記録された映像音声データが含まれるファイルを検索することができる。しかし、この装置では、入力日時データの日付コードから算出したハッシュ値に対応する多分探索木が存在しない（従ってファイルが存在しないＮＵＬＬの状態）場合には、最も近い時刻に記録された映像音声データが含まれるファイルを検索することはできない。
本発明の第３の実施形態におけるファイル管理装置では、こうした場合でも、入力日時データに最も近い時刻に記録された映像音声データを含むファイルを検索することができる。
【００３７】
このファイル管理装置の構成は、第２の実施形態（図６）と変わりがない。ただ、ハッシュ表管理手段１３が管理するハッシュ表には、図９に示すように、ハッシュ値２１及びルートノードアドレス２２の他に、ルートノードアドレス２２で指定されたノードをルートノードとする多分探索木において、最も古い映像音声データの記録日時を表す最古映像音声データ記録日時２３と、最も新しい映像音声データの記録日時を表す最新映像音声データ記録日時２４とのデータを含むエントリが記録されており、この点が第２の実施形態と相違している。
【００３８】
例えば、ルートノードアドレスが“０”の図４の多分探索木の場合、最古映像音声データ記録日時２３は、“０２／０３／３１  １０：００：００”であり、最新映像音声データ記録日時２４は“０２／０３／３１  １０：５０：００”である。
このファイル管理装置１０のハッシュ表管理手段１３は、ハッシュ表２０のエントリに、ハッシュ値２１、ルートノードアドレス２２、最古映像音声データ記録日時２３、及び、最新映像音声データ記録日時２４を記録し、ハッシュ値に対応する多分探索木が存在しない場合には、ハッシュ値に対応するルートノードを示すデータをＮＵＬＬとする。
【００３９】
多分探索木選択手段１２は、ハッシュ関数１１を用いて入力された日時データの日付コードからハッシュ値を算出し、算出したハッシュ値に対応する多分探索木のルートノードアドレスをハッシュ表２０から求める。算出したハッシュ値に対応する多分探索木のルートノードアドレスがハッシュ表２０に記録されていれば、その多分探索木を検索対象と決定する。また、算出したハッシュ値に対応する多分探索木のルートノードを示すデータが無効（ＮＵＬＬ）値である場合は、ハッシュ表２０の各エントリの最古映像音声データ及び最新映像音声データの記録日時を参照して、入力された日時データに最も近い時刻に記録されたファイルが保持されている多分探索木を求め、その多分探索木を検索対象と決定する。
【００４０】
多分探索木選択手段１２は、ファイル検索手段１３に対して、入力日時データをキーに、検索対象に決定した多分探索木のファイル検索を指示する。これを受けて、ファイル検索手段１３は、第２の実施形態で説明した手順で検索動作を実行する。
図１０のフローチャートは、ハッシュ値に対応するファイル（多分探索木）が存在しなかった場合の多分探索木決定動作について示している。
ここでは、入力日時データとして「０２／０４／１３  ９：００：００」が入力されたときの動作について説明する。
【００４１】
多分探索木選択手段１２は、ハッシュ関数１１を用いて入力された日時データの日付コード「０２／０４／１３」からハッシュ値を算出し（ステップ１０１）、算出したハッシュ値に対応するルートノードアドレスを図９のハッシュ表２０を参照して取り出す（ステップ１０２）。
多分探索木選択手段１２は、取り出されたルートノードアドレスの値を判定し（ステップ３０１）、ルートノードアドレスが無効（ＮＵＬＬ）値であるならば、ハッシュ表２０の各エントリの最古映像音声データ及び最新映像音声データの記録日時を参照することにより、入力された日時データに最も近い時刻に記録されたファイルが保持されている多分探索木を求め、得られた多分探索木を検索対象とする（ステップ３０２）。
図９に示した例では、多分探索木選択手段１２は、日時データ「０２／０４／１３  ９：００：００」に最も近い時刻に記録されたファイルが保持されている多分探索木として、ハッシュ値Ｈｓ２に対応付けられた多分探索木を検索対象の決定する。
【００４２】
このように、このファイル管理装置１０では、入力日時データの日付コードのハッシュ値に対応するルートノードアドレスがＮＵＬＬである場合でも、入力日時データに最も近い時間に記録されたファイルを検索することができる。
なお、本発明の各実施形態で示した多分探索木選択手段１２、ファイル検索手段１５及びファイル構造管理手段１４の機能は、ファイル管理装置が内蔵するコンピュータにプログラムで規定した処理を行わせることにより実現することができる。また、このコンピュータプログラムは、磁気ディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ、ＩＣカードなどの記録媒体に記録し、この記録媒体を介して各ファイル管理装置に移転することができる。
また、本発明は、映像データまたは音声データを記録するファイルの管理に適用することができる。
【００４３】
【発明の効果】
以上の説明から明らかなように、本発明のファイル管理方法では、多分探索木構造でファイルを管理しているため、ファイルを検索するときの比較処理の回数を減らすことができ、大量のファイルを管理する場合でも、目的のファイルを迅速に検索することができる。
【００４４】
また、本発明のファイル管理装置は、１つのハッシュ値に対応付けられるファイルを多分探索木構造で管理しているため、検索処理における比較回数を減らすことができ、映像や音声データを記録した大量のファイルを管理する場合でも、短時間で目的のファイルを検索することができる。そのため、このファイル管理装置は、交通量や人通りを監視するために道路に設置された監視カメラや、銀行内の状況を監視するために設置された監視カメラなどの画像データを圧縮して記録する「監視用デジタルレコーダ」として好適である。また、監視用デジタルレコーダでは、指定された日時の映像が存在しない場合に、その日時と最も近い時刻に記録された映像を検出する処理が求められるが、本発明のファイル管理装置は、こうした処理についても迅速に行うことができる。
【００４５】
また、本発明のコンピュータプログラムは、このファイル管理装置の動作を実現することができる。
【図面の簡単な説明】
【図１】本発明の第１の実施形態におけるファイル管理装置の構成を示すブロック図
【図２】本発明の第１の実施形態におけるハッシュ表の例
【図３】本発明の第１の実施形態におけるファイル管理テーブルの例
【図４】本発明の第１の実施形態における二分探索木構造の例
【図５】本発明の第１の実施形態における検索動作の手順を示すフローチャート
【図６】本発明の第２の実施形態におけるファイル管理装置の構成を示すブロック図
【図７】本発明の第２の実施形態における探索履歴記憶テーブルの例
【図８】本発明の第２の実施形態における検索動作の手順を示すフローチャート
【図９】本発明の第３の実施形態におけるハッシュ表の例
【図１０】本発明の第３の実施形態における多分探索木選択動作の手順を示すフローチャート
【図１１】従来のファイル管理装置の構成を示すブロック図
【符号の説明】
１０  ファイル管理装置
１１  ハッシュ関数
１２  多分探索木選択手段
１３  ハッシュ表管理手段
１４  ファイル構造管理手段
１５  ファイル検索手段
１６  記録媒体
１７  探索履歴記憶部
２０  ハッシュ表
２１  ハッシュ値
２２  ルートノードアドレス
２３  最古映像音声データ記録日時
２４  最新映像音声データ記録日時
３０  ファイル管理テーブル
３１  ファイル情報
３２  ノードアドレス０部
３３  ノードアドレス１部
５０  探索履歴記憶テーブル
５１  エントリ番号
５２  ファイル作成日時
１００  データ処理装置
１０１  ファイル検索部
１０２  ハッシュ関数
１０３  記憶装置
１０４  ハッシュ表
１０５  ディレクトリブロック
【図１】
2004152239.tif 000003
【図２】
2004152239.tif 000004
【図３】
2004152239.tif 000005
【図４】
2004152239.tif 000006
【図５】
2004152239.tif 000007
【図６】
2004152239.tif 000008
【図７】
2004152239.tif 000009
【図８】
2004152239.tif 000010
【図９】
2004152239.tif 000011
【図１０】
2004152239.tif 000012
【図１１】
2004152239.tif 000013