(57)【要約】  装置は、木構造の情報に含まれる要素情報と対応する木構造中での位置情報とからなるテーブル（６０）を、テーブル分離部（１０１）により、要素情報の値（６１）と位置情報（６２）とに分離する。要素情報並替部（１０３）は、分離された要素情報の値（６１）を辞書順に並替える。この並替えによる順序関係の変化を示すための対応情報（７０３）が、対応情報抽出部（１０４）により抽出される。位置情報符号化部（１０２）および対応情報符号化部（１０５）は、位置情報（６２）および対応情報（７０３）を各々符号化する。符号化された位置情報（６２）および対応情報（７０３）と要素情報の値（６１）とを用いて、圧縮情報形成部（１０６）は、これらの圧縮情報を形成する。【特許請求の範囲】
【請求項１】
要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される情報の符号化装置（１）であって、
所定種別の要素情報と、該所定種別の要素情報が付された前記葉の前記木構造における前記規定順序に従う位置を示す位置情報と含んだ複数の組を、前記規定順序に従い並んで有する情報群を受理する手段（１０７）と、
前記受理する手段により受理した前記情報群の前記複数の組から複数の前記要素情報を分離して、分離した前記複数の要素情報を前記所定種別の前記要素情報の検索に適した所定の順序に従い並替える並替え手段（１０１、１０３）と、
前記並替え手段による、前記規定順序から前記所定順序への並替えによる前記複数の要素情報の順番の変化に基づき、並替え後の前記複数の要素情報それぞれと、前記受理する手段により受理した前記情報群の中の該要素情報と同一組の前記位置情報との対応関係を示す対応情報を生成する対応情報生成手段（１０４、１０５）と、
前記受理する手段により受理した前記情報群の前記複数の組から複数の前記位置情報を分離して、分離した前記複数の位置情報を符号化する位置情報符号化手段（１０２）と、
前記位置情報符号化手段により符号化された前記複数の位置情報と、前記対応情報生成手段により生成された前記対応情報と、前記並替え手段による並替え後の前記複数の要素情報とを含めた所定情報を形成する所定情報形成手段（１０６）とを備える、符号化装置。
【請求項２】
前記位置情報符号化手段は、前記複数の位置情報それぞれを、
該位置情報と、当該位置情報が示す位置の前記規定順序に従う直前の位置を示す位置情報との差分に基づき符号化することを特徴とする、請求項１に記載の符号化装置。
【請求項３】
前記対応情報生成手段は、
前記対応関係を示す情報を符号化することにより前記対応情報を生成する対応情報符号化手段（１０５）を含む、請求項１に記載の符号化装置。
【請求項４】
前記所定情報形成手段による前記所定情報の形成に先立って、前記要素情報は符号化されることを特徴とする、請求項１に記載の符号化装置。
【請求項５】
前記木構造からなる情報は映像データを検索するための情報であることを特徴とする、請求項１に記載の符号化装置。
【請求項６】
要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される情報の符号化装置（１０）であって、
所定種別の要素情報と、該所定種別の要素情報が付された前記葉の前記木構造における前記規定順序に従う位置を示す位置情報と含んだ複数の組を、前記所定種別の前記要素情報の検索に適した所定順序に従い並んで有する情報群を受理する手段（９０７）と、
前記受理する手段により受理した前記情報群の前記複数の組から複数の前記要素情報を分離して出力する要素情報分離手段（９０１）と、
前記受理する手段により受理した前記情報群の前記複数の組から複数の前記位置情報を分離して、分離した前記複数の位置情報を、前記規定順序に従い並替える位置情報並替手段（９０３）と、
前記位置情報並替手段の並替えによる前記複数の位置情報の順番の変化に基づき、並替え後の前記複数の位置情報それぞれと、前記受理する手段により受理した前記情報群の中の該位置情報と同一組の前記要素情報との対応関係を示す対応情報を生成する対応情報生成手段（９０４、９０５）と、
前記位置情報並替手段により並替えられた前記複数の位置情報を符号化する位置情報符号化手段（９０２）と、
前記位置情報符号化手段により符号化された前記複数の位置情報と、前記対応情報生成手段により生成された前記対応情報と、前記要素情報分離手段から出力された前記複数の要素情報とを含めた所定情報を形成する所定情報形成手段（９０６）とを備える、符号化装置。
【請求項７】
前記位置情報符号化手段は、前記複数の位置情報それぞれを、
該位置情報と、当該位置情報が示す位置の前記規定順序に従う直前の位置を示す位置情報との差分に基づき符号化することを特徴とする、請求項６に記載の符号化装置。
【請求項８】
前記対応情報生成手段は、
前記対応関係を示す情報を符号化することにより前記対応情報を生成する対応情報符号化手段（９０５）を含む、請求項６に記載の符号化装置。
【請求項９】
前記所定情報形成手段による前記所定情報の形成に先立って、前記要素情報は符号化されることを特徴とする、請求項６に記載の符号化装置。
【請求項１０】
前記木構造からなる情報は映像データを検索するための情報であることを特徴とする、請求項６に記載の符号化装置。
【請求項１１】
要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される所定情報の復号装置（２）であって、
所定種別の前記要素情報の検索に適した所定順序で並んだ前記所定種別の複数の要素情報と、当該複数の要素情報が付された複数の葉の前記木構造における前記規定順序に従う位置を示す符号化された複数の位置情報と、前記所定順序で並んだ複数の要素情報それぞれと当該要素情報が付された前記葉の前記規定順序に従う位置を示す符号化された前記複数の位置情報との対応関係を示す対応情報と、を含んで形成された所定情報を受理する所定情報受理手段（２０７）と、
前記所定情報受理手段により受理した前記所定情報から、前記複数の要素情報と、符号化された前記複数の位置情報と、前記対応情報とを分離して出力する分離手段（２０１）と、
前記分離手段から出力された符号化された前記複数の位置情報を入力して、入力した前記複数の位置情報を復号する位置情報復号手段（２０２）と、
前記分離手段から出力された前記対応情報を入力して、入力した前記対応情報に基づき、前記位置情報復号手段により復号された前記複数の位置情報を前記所定順序に従い並替える並替え手段（２０４）と、
前記並替え手段による並替え後の前記複数の位置情報それぞれと、前記分離手段から入力した前記所定順序で並んだ前記複数の要素情報それぞれとが対応付けされた情報を生成して出力する手段（２０５）を備える、復号装置。
【請求項１２】
前記木構造からなる情報は映像データを検索するための情報であることを特徴とする、請求項１１に記載の復号装置。
【請求項１３】
要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される情報の符号化方法であって、
所定種別の要素情報と、該所定種別の要素情報が付された前記葉の前記木構造における前記規定順序に従う位置を示す位置情報と含んだ複数の組を、前記規定順序に従い並んで有する情報群を受理するステップ（Ｓ１０）と、
前記受理するステップにおいて受理した前記情報群の前記複数の組から複数の前記要素情報を分離して、分離した前記複数の要素情報を、前記所定種別の前記要素情報の検索に適した所定の順序に従い並替える並替えステップ（Ｓ１１、Ｓ１２）と、
前記並替えステップによる、前記規定順序から前記所定順序への並替えによる前記複数の要素情報の順番の変化に基づき、並替え後の前記複数の要素情報それぞれと、前記受理するステップにおいて受理した前記情報群の中の該要素情報と同一組の前記位置情報との対応関係を示す対応情報を生成する対応情報生成ステップ（Ｓ１３）と、
前記受理するステップにより受理した前記情報群の前記複数の組から複数の前記位置情報を分離して、分離した前記複数の位置情報を符号化する位置情報符号化ステップ（Ｓ１４）と、
前記位置情報符号化ステップにより符号化された前記複数の位置情報と、前記対応情報生成ステップにより生成された前記対応情報と、前記並替えステップによる並替え後の前記複数の要素情報とを含めた所定情報を形成する所定情報形成ステップ（Ｓ１６）とを備える、符号化方法。
【請求項１４】
要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される情報の符号化方法であって、
所定種別の要素情報と、該所定種別の要素情報が付された前記葉の前記木構造における前記規定順序に従う位置を示す位置情報と含んだ複数の組を、前記所定種別の前記要素情報の検索に適した所定順序に従い並んで有する情報群を受理するステップと、
前記受理するステップにより受理した前記情報群の前記複数の組から複数の前記要素情報を分離して出力する要素情報分離ステップと、
前記受理するステップにより受理した前記情報群の前記複数の組から複数の前記位置情報を分離して、分離した前記複数の位置情報を、前記規定順序に従い並替える位置情報並替ステップと、
前記位置情報並替ステップの並替えによる前記複数の位置情報の順番の変化に基づき、並替え後の前記複数の位置情報それぞれと、前記受理するステップにより受理した前記情報群の中の該位置情報と同一組の前記要素情報との対応関係を示す対応情報を生成する対応情報生成ステップと、
前記位置情報並替ステップにより並替えられた前記複数の位置情報を符号化する位置情報符号化ステップと、
前記位置情報符号化ステップにより符号化された前記複数の位置情報と、前記対応情報生成ステップにより生成された前記対応情報と、前記要素情報分離ステップから出力された前記複数の要素情報とを含めた所定情報を形成する所定情報形成ステップとを備える、符号化方法。
【請求項１５】
要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される所定情報の復号方法であって、
所定種別の前記要素情報の検索に適した所定順序で並んだ前記所定種別の複数の要素情報と、当該複数の要素情報が付された複数の葉の前記木構造における前記規定順序に従う位置を示す符号化された複数の位置情報と、前記所定順序で並んだ複数の要素情報それぞれと当該要素情報が付された前記葉の前記規定順序に従う位置を示す符号化された前記複数の位置情報との対応関係を示す対応情報と、を含んで形成された所定情報を受理する所定情報受理ステップ（Ｓ２０）と、
前記所定情報受理ステップにより受理した前記所定情報から、前記複数の要素情報と、符号化された前記複数の位置情報と、前記対応情報とを分離して出力する分離ステップ（Ｓ２１）と、
前記分離ステップから出力された符号化された前記複数の位置情報を入力して、入力した前記複数の位置情報を復号する位置情報復号ステップ（Ｓ２２）と、
前記分離ステップにより出力された前記対応情報を入力して、入力した前記対応情報に基づき、前記位置情報復号ステップにより復号された前記複数の位置情報を前記所定順序に従い並替える並替えステップ（Ｓ２４）と、
前記並替えステップによる並替え後の前記複数の位置情報それぞれと、前記分離ステップから入力した前記所定順序で並んだ前記複数の要素情報それぞれとが対応付けされた情報を生成して出力するステップ（Ｓ２５）を備える、復号方法。
【請求項１６】
要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される情報の符号化方法を、コンピュータに実行させるためのプログラムであって、
前記符号化方法は、
前記木構造における所定種別の要素情報と、該所定種別の要素情報が付された前記葉の前記木構造における前記規定順序に従う位置を示す位置情報と含んだ複数の組を、前記規定順序に従い並んで有する情報群を受理するステップと、
前記受理するステップにおいて受理した前記情報群の前記複数の組から複数の前記要素情報を分離して、分離した前記複数の要素情報を、前記所定種別の前記要素情報の検索に適した所定の順序に従い並替える並替えステップと、
前記並替えステップによる、前記規定順序から前記所定順序への並替えによる前記複数の要素情報の順番の変化に基づき、並替え後の前記複数の要素情報それぞれと、前記受理するステップにおいて受理した前記情報群の中の該要素情報と同一組の前記位置情報との対応関係を示す対応情報を生成する対応情報生成ステップと、
前記受理するステップにより受理した前記情報群の前記複数の組から複数の前記位置情報を分離して、分離した前記複数の位置情報を符号化する位置情報符号化ステップと、
前記位置情報符号化ステップにより符号化された前記複数の位置情報と、前記対応情報生成ステップにより生成された前記対応情報と、前記並替えステップによる並替え後の前記複数の要素情報とを含めた所定情報を形成する所定情報形成ステップとを備える、符号化方法をコンピュータに実行させるためのプログラム。
【請求項１７】
要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される情報の符号化方法を、コンピュータに実行させるためのプログラムであって、
前記符号化方法は、
所定種別の要素情報と、該所定種別の要素情報が付された前記葉の前記木構造における前記規定順序に従う位置を示す位置情報と含んだ複数の組を、前記所定種別の前記要素情報の検索に適した所定順序に従い並んで有する情報群を受理するステップと、
前記受理するステップにより受理した前記情報群の前記複数の組から複数の前記要素情報を分離して出力する要素情報分離ステップと、
前記受理するステップにより受理した前記情報群の前記複数の組から複数の前記位置情報を分離して、分離した前記複数の位置情報を、前記規定順序に従い並替える位置情報並替ステップと、
前記位置情報並替ステップの並替えによる前記複数の位置情報の順番の変化に基づき、並替え後の前記複数の位置情報それぞれと、前記受理するステップにより受理した前記情報群の中の該位置情報と同一組の前記要素情報との対応関係を示す対応情報を生成する対応情報生成ステップと、
前記位置情報並替ステップにより並替えられた前記複数の位置情報を符号化する位置情報符号化ステップと、
前記位置情報符号化ステップにより符号化された前記複数の位置情報と、前記対応情報生成ステップにより生成された前記対応情報と、前記要素情報分離ステップから出力された前記複数の要素情報とを含めた所定情報を形成する所定情報形成ステップとを備える、符号化方法をコンピュータに実行させるためのプログラム。
【請求項１８】
要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される所定情報の復号方法を、コンピュータに実行させるためのプログラムであって、
前記復号方法は、
所定種別の前記要素情報の検索に適した所定順序で並んだ前記所定種別の複数の要素情報と、当該複数の要素情報が付された複数の葉の前記木構造における前記規定順序に従う位置を示す符号化された複数の位置情報と、前記所定順序で並んだ複数の要素情報それぞれと当該要素情報が付された前記葉の前記規定順序に従う位置を示す符号化された前記複数の位置情報との対応関係を示す対応情報と、を含んで形成された所定情報を受理する所定情報受理ステップと、
前記所定情報受理ステップにより受理した前記所定情報から、前記複数の要素情報と、符号化された前記複数の位置情報と、前記対応情報とを分離して出力する分離ステップと、
前記分離ステップから出力された符号化された前記複数の位置情報を入力して、入力した前記複数の位置情報を復号する位置情報復号ステップと、
前記分離ステップにより出力された前記対応情報を入力して、入力した前記対応情報に基づき、前記位置情報復号ステップにより復号された前記複数の位置情報を前記所定順序に従い並替える並替えステップと、
前記並替えステップによる並替え後の前記複数の位置情報それぞれと、前記分離ステップから入力した前記所定順序で並んだ前記複数の要素情報それぞれとが対応付けされた情報を生成して出力するステップを備える、復号方法をコンピュータに実行させるためのプログラム。
【請求項１９】
要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される情報の符号化方法を、コンピュータに実行させるためのプログラムを記録した機械読取り可能な記録媒体であって、
前記符号化方法は、
所定種別の要素情報と、該所定種別の要素情報が付された前記葉の前記木構造における前記規定順序に従う位置を示す位置情報と含んだ複数の組を、前記規定順序に従い並んで有する情報群を受理するステップと、
前記受理するステップにおいて受理した前記情報群の前記複数の組から複数の前記要素情報を分離して、分離した前記複数の要素情報を、前記所定種別の前記要素情報の検索に適した所定の順序に従い並替える並替えステップと、
前記並替えステップによる、前記規定順序から前記所定順序への並替えによる前記複数の要素情報の順番の変化に基づき、並替え後の前記複数の要素情報それぞれと、前記受理するステップにおいて受理した前記情報群の中の該要素情報と同一組の前記位置情報との対応関係を示す対応情報を生成する対応情報生成ステップと、
前記受理するステップにより受理した前記情報群の前記複数の組から複数の前記位置情報を分離して、分離した前記複数の位置情報を符号化する位置情報符号化ステップと、
前記位置情報符号化ステップにより符号化された前記複数の位置情報と、前記対応情報生成ステップにより生成された前記対応情報と、前記並替えステップによる並替え後の前記複数の要素情報とを含めた所定情報を形成する所定情報形成ステップとを備える、符号化方法をコンピュータに実行させるためのプログラムを記録した機械読取り可能な記録媒体。
【請求項２０】
要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される情報の符号化方法を、コンピュータに実行させるためのプログラムを記録した機械読取り可能な記録媒体であって、
前記符号化方法は、
所定種別の要素情報と、該所定種別の要素情報が付された前記葉の前記木構造における前記規定順序に従う位置を示す位置情報と含んだ複数の組を、前記所定種別の前記要素情報の検索に適した所定順序に従い並んで有する情報群を受理するステップと、
前記受理するステップにより受理した前記情報群の前記複数の組から複数の前記要素情報を分離して出力する要素情報分離ステップと、
前記受理するステップにより受理した前記情報群の前記複数の組から複数の前記位置情報を分離して、分離した前記複数の位置情報を、前記規定順序に従い並替える位置情報並替ステップと、
前記位置情報並替ステップの並替えによる前記複数の位置情報の順番の変化に基づき、並替え後の前記複数の位置情報それぞれと、前記受理するステップにより受理した前記情報群の中の該位置情報と同一組の前記要素情報との対応関係を示す対応情報を生成する対応情報生成ステップと、
前記位置情報並替ステップにより並替えられた前記複数の位置情報を符号化する位置情報符号化ステップと、
前記位置情報符号化ステップにより符号化された前記複数の位置情報と、前記対応情報生成ステップにより生成された前記対応情報と、前記要素情報分離ステップから出力された前記複数の要素情報とを含めた所定情報を形成する所定情報形成ステップとを備える、符号化方法をコンピュータに実行させるためのプログラムを記録した機械読取り可能な記録媒体。
【請求項２１】
要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される所定情報の復号方法を、コンピュータに実行させるためのプログラムを記録した機械読取り可能な記録媒体であって、
前記復号方法は、
所定種別の前記要素情報の検索に適した所定順序で並んだ前記所定種別の複数の要素情報と、当該複数の要素情報が付された複数の葉の前記木構造における前記規定順序に従う位置を示す符号化された複数の位置情報と、前記所定順序で並んだ複数の要素情報それぞれと当該要素情報が付された前記葉の前記規定順序に従う位置を示す符号化された前記複数の位置情報との対応関係を示す対応情報と、を含んで形成された所定情報を受理する所定情報受理ステップと、
前記所定情報受理ステップにより受理した前記所定情報から、前記複数の要素情報と、符号化された前記複数の位置情報と、前記対応情報とを分離して出力する分離ステップと、
前記分離ステップから出力された符号化された前記複数の位置情報を入力して、入力した前記複数の位置情報を復号する位置情報復号ステップと、
前記分離ステップにより出力された前記対応情報を入力して、入力した前記対応情報に基づき、前記位置情報復号ステップにより復号された前記複数の位置情報を前記所定順序に従い並替える並替えステップと、
前記並替えステップによる並替え後の前記複数の位置情報それぞれと、前記分離ステップから入力した前記所定順序で並んだ前記複数の要素情報それぞれとが対応付けされた情報を生成して出力するステップを備える、復号方法をコンピュータに実行させるためのプログラムを記録した機械読取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、木構造を有する情報の符号化装置、符号化方法、復号装置、復号方法、プログラムおよび該プログラムを記録した機械読取り可能な記録媒体に関し、特に、木構造の複数の葉にあたる要素情報と、該葉の木構造における位置を示した位置情報とを対応付けて処理する符号化装置、符号化方法、復号装置、復号方法、プログラムおよび該プログラムを記録した機械読取り可能な記録媒体に関する。
【背景技術】
【０００２】
昨今の映像記録装置の記録容量の大容量化や高速／広帯域ネットワークの普及は、ユーザに対して大量の映像を一度に提供可能な環境を提供する。一方、提供される映像データをユーザが効率良く利用するためには、映像データの中から所望の映像または部分映像（ショット、カット）のデータを簡単に、高速に探し出す機能が必要とされる。この機能の１つとして、映像データに付加されるべき該映像に関する情報（以下、付加情報という）を予め用意して、付加情報に基づいて検索する機能が提供される。該機能によれば、例えば、映像のタイトルカタログから所望のものを検索して、対応する映像データを提供することもでき、また、映像に関する更に詳細な内容を記述した付加情報が用意され、内容に基づいた検索をユーザに提供することもできる。【０００３】
図１７には、従来および本発明の実施の形態において適用される、ある映像データにより提示される映像の内容を記述した付加情報の例が示される。図１７に示されるように、付加情報は映像の論理構造に対応した木構造で表される。【０００４】
一般に、映像などの動画像コンテンツは１つまたは複数のシーンによって構成され、さらに各シーンは１つまた複数のサブシーン（あるいはショット）、あるいはさらに別のシーンによって構成される、というように階層性を有する。映像の検索時の利便性を高めるために、サブシーンの特徴を示す検索情報を各サブシーンに付加する際の記述手法は、前述の階層性を表現するため、図１７に示すような木構造からなる表現手法を用いている。図１７では、映像全体が２つのシーンからなり、それぞれが２つのサブシーンと１つのサブシーンとで構成される。そして、それぞれのサブシーンについて、そのサブシーンに関する関連情報、ここではサブシーンの時刻情報（開始時刻/長さ）、タイトル、およびそのサブシーンに映っている出演者を記述している。木構造としては、映像データ全体が根（ルートノード）ＲＮにあたり、シーン、サブシーン、ならびに時刻情報、タイトル、出演者といった要素種別を表している節が節Ｎにあたる。節Ｎの中でも、シーンの階層は根ＲＮから見て最初の分岐先に相当するので、第１階層の節Ｎにあたる。また、サブシーンの階層は第２階層の節Ｎにあたる。そして、各サブシーンの関連情報である時刻情報、タイトル、出演者を表すデータが木構造の葉Ｌにあたる。【０００５】
これら葉Ｌとして付された情報をここでは検索情報の「要素情報」あるいは単に「要素」と呼ぶ。【０００６】
ここで、要素情報それぞれが木構造中のどの葉Ｌにあたるかを区別するためには、要素の値の他に、その要素の木構造における位置を示した情報を同時に保存する必要がある。言い換えると、その要素がいずれのシーンのいずれのサブシーンに関するものであるかという情報が必要となる。図１７においてシーンまたは１つのシーン内のサブシーンを区別するために付された番号「１」、「２」、サブシーン内の複数の出演者を区別するために付された番号「１」、「２」、「３」は、前述した木構造中の要素の位置を一意に示すための情報であり、「位置情報」と呼ぶ。この位置情報は木構造において規定された順序関係に従い表現される。この例を以下に説明する。【０００７】
木構造では、ある節Ｎ（または根ＲＮ）の下層に位置するすべての節Ｎについて木の左から右に順に１番、２番・・・と連番をつけ、根ＲＮからある葉Ｌに至るまでに経由する全ての節Ｎについて、該連番を列挙することで該葉Ｌの位置情報が表現される。【０００８】
図１７を参照して、この規定順序に従う位置情報の生成方法の具体例を、左から３つめの要素「Akira  ABE」の場合で説明する。木は上階層から下階層へ、かつ同一階層は左から右に走査することで出現する順番に節Ｎ（根ＲＮまたは葉Ｌ）それぞれに位置情報を割当てる。【０００９】
まず第１階層を見ると、要素「Akira  ABE」が属するシーンは、根ＲＮにあたる映像にぶら下がった一番左側の節Ｎである。このため、第１階層の位置情報は「１」番となる。次に、第２階層を見ると、要素「Akira  ABE」が属するサブシーンは１つ上の階層の節Ｎにあたるシーン「１」にぶら下がった節Ｎの中で左から１番目の節である。このため、第２階層での位置（出現順番）は「１」番となる。次に、第３階層を見ると、要素「Akira  ABE」の葉Ｌはサブシーン［１］にぶら下がった‘出演者’という節Ｎの中で左から１番目の節Ｎである。このため、第３階層での‘出演者’という要素の中での位置（出現順番）は「１」番となる。したがって、この場合、木を構成する全ての階層である第１〜第３階層あわせて（１、１、１）が要素「Akira  ABE」の位置情報となる。この形式で全ての葉Ｌの位置情報を一意に表現することが可能である。【００１０】
検索は以下のように行なう。例えば、図１７において「Wataru  WADA」が出演しているサブシーンを探す。即ち、検索条件「出演者＝Wataru  WADA」を与え、出演者を示す要素情報（葉Ｌ）から条件「Wataru  WADA」に一致するものを探す。条件を満たす要素が見つかれば、それがどのサブシーンに属するかを示す情報（「シーン１のサブシーン１」）を検索結果として返す。サブシーンの再生は、そのサブシーンの葉Ｌに付された時刻情報を見て行なう。【００１１】
図１７は極めて簡単な付加情報の例であるが、実際の要素種別はこれだけに限らず、また映像が複雑なほど木構造も複雑化するため、映像の付加情報のサイズは一般に大きい。このため、付加情報を予め分割された形で扱い、利用時に必要な部分情報だけを得て用いるといった形態がとられることも多い。【００１２】
図１８には、図１７の付加情報の木構造を扱い易い形に（サブシーン単位に）分割した例が示される。分割されたそれぞれの木は「部分木」（sub-tree）もしくは「フラグメント」（fragment）と呼ばれる。更に、上述のような「出演者」による検索を行なうために図１９に示すようなテーブルを補助情報として用意する。図１９のテーブルは、木構造中の全ての要素情報（出演者）の値と、各要素情報に対応してその要素情報がどの部分木（フラグメント）に属するかを示すフラグメント情報とを格納している。【００１３】
この場合、付加情報を用いた映像の検索は以下のように行なう。システムはまず要求に応じて図１９に示したテーブルをユーザに伝送する。ユーザは、受理したテーブルから検索条件「Wataru  WADA」に合致するものを検索して対応するフラグメント情報を読出す。そして、読出したフラグメント情報が示すフラグメント（「フラグメント１」）のデータを要求する。システムは要求に応じて「フラグメント１」のデータをユーザに伝送するので、ユーザは「フラグメント１」のデータを受理して、受理した「フラグメント１」のデータを利用する。なお、サブシーンの再生は、得られたフラグメントのデータ中の「時刻情報」を参照して行なわれる。【００１４】
図１９に示した補助情報の具体例としては、TV  Anytimeフェーズ１パート３−２規格（ETSI  TS  102  822-3-2）に示すインデキシング（Indexing）技術が挙げられる。【００１５】
図１８と図１９では、個々のフラグメントを示すための情報を図１７の付加情報とは別途設けているが、それらは図１７の付加情報に含まれている位置情報で置き換えることができる。【００１６】
図１９のテーブルは、実際に利用するか否かに拘らず常に伝送されるものである。そのため、伝送効率を考慮すると、このテーブルは圧縮符号化されて伝送されることが望ましい。これに関し、特開２００３−０９２７５７号公報（特許文献１）には、複数の位置情報を高い圧縮率で符号化する方法として、大きさの順番に連続する値の位置情報の差分符号化方法が示されている。この差分符号化方法は、木構造のある葉Ｌ（またはある節Ｎ）の位置情報をそのまま記述するのではなく、該位置情報と木構造においてその１つ前の順番に位置する葉Ｌ（または節Ｎ）の位置情報との変位（差分）のみを用いて位置情報を符号化する。これにより、より少ないビット数で効率よく符号化できるという効果をもたらす。
【特許文献１】特開２００３−０９２７５７号公報
【発明の開示】
【発明が解決しようとする課題】
【００１７】
図１９に示したように、リストアップされる付加情報の各要素（要素情報の値）の種別が該要素はテキスト形式の情報であることを示す場合、検索効率が高くなるように、該種別に基づき、それらを付加情報（木構造）中での出現順（位置情報の値の順番）の並びから辞書順（lexicographic  ordering）の並びに変更することが行なわれる。テキスト形式の情報群は情報を辞書順に並べることで該情報群から所望情報を検索する時の演算量は対数オーダに従うものとなり、辞書順でない場合に比較して検索効率に優れることが知られている。【００１８】
図１９のテーブル中の要素情報の値を辞書順に並替えた場合、対応する位置情報の値も同じく並替えられるため、位置情報の値の大きさ順に従う並び関係が崩れてしまう。そのため、要素情報の値を辞書順に並替える場合には、対応の位置情報に対して特許文献１に示された差分符号化方式を適用することはできなかった。【００１９】
それゆえにこの発明の目的は、木構造により構成される情報について、検索効率に優れる情報を得ることのできる符号化装置、符号化方法、プログラムおよび該プログラムを記録した機械読取り可能な記録媒体、ならびにこの符号化された情報を復号する復号装置、復号方法、プログラムおよび該プログラムを記録した機械読取り可能な記録媒体を提供することである。【００２０】
この発明の他の目的は、木構造により構成される情報について、符号化効率に優れる情報を得ることのできる符号化装置、符号化方法、プログラムおよび該プログラムを記録した機械読取り可能な記録媒体、ならびにこの符号化された情報を復号する復号装置、復号方法、プログラムおよび該プログラムを記録した機械読取り可能な記録媒体を提供することである。【００２１】
この発明の他の目的は、木構造により構成される情報について、符号化効率に優れる情報を得ることのできる符号化装置、符号化方法、プログラムおよび該プログラムを記録した機械読取り可能な記録媒体、ならびにこの符号化された情報を復号する復号装置、復号方法、プログラムおよび該プログラムを記録した機械読取り可能な記録媒体を提供することである。
【課題を解決するための手段】
【００２２】
この発明のある局面に従うと、要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される情報の符号化をする。【００２３】
まず、所定種別の要素情報と、該所定種別の要素情報が付された葉の前記木構造における規定順序に従う位置を示す位置情報と含んだ複数の組を、規定順序に従う順番に並んで有する情報群を、受理する部部により受理する。そして、並替え部は、受理した情報群の複数の組それぞれから複数の要素情報を分離して、分離した複数の要素情報を所定の順序に従い並替える。また対応情報生成部は、対応情報を生成する。対応情報は、規定順序から所定順序への並替えによる複数の要素情報の順番の変化に基づき、並替え後の複数の要素情報それぞれと、受理している情報群の中の該要素情報と同一組の位置情報との対応関係を示す。【００２４】
位置情報符号化部は、受理している情報群の複数の組それぞれから位置情報を分離して分離した複数の位置情報を符号化する。そして、所定情報形成部は、符号化された位置情報と、生成された対応情報と、並替え後の要素情報とを含めた所定情報を形成する。【００２５】
前述の所定順序は、所定種別の要素情報の検索に適した順序を指す。
この発明の他の局面に従うと、要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される情報の符号化をする。【００２６】
まず、所定種別の要素情報と、当該所定種別の要素情報が付された葉の木構造における規定順序に従う位置を指示する位置情報と含んだ複数の組を、所定順序に並んで有する情報群を、受理部により受理する。【００２７】
要素情報分離部は、受理した情報群の複数の組それぞれから要素情報を分離して出力する。また、位置情報並べ替部は、受理した情報群の複数の組それぞれから位置情報を分離して、分離した複数の位置情報を、規定順序に従い並替える。また、対応情報生成部は、対応情報を生成する。対応情報は、並替えによる複数の位置情報の順番の変化に基づく、並替え後の複数の位置情報それぞれと、受理している情報群の中の該位置情報と同一組の要素情報との対応関係を示す。【００２８】
位置情報符号化部は、並替えされた複数の位置情報を符号化する。そして、所定情報形成部は、符号化された位置情報と、生成された対応情報と、分離された要素情報とを含めた所定情報を生成する。【００２９】
前述の所定順序は、所定種別の要素情報の検索に適した順序を指す。
この発明のさらに他の局面に従うと、要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される符号化情報を復号する。【００３０】
まず、所定順序で並んだ複数の要素情報と、該複数の要素情報が付された複数の葉の木構造における規定順序に従う位置を示す符号化された位置情報と、複数の位置情報のうち所定順序で並んだ複数の要素情報それぞれと対応する位置情報を特定するための対応情報とを含んで生成された所定情報を、受理部により受理する。分離部は、受理した所定情報から複数の要素情報と、複数の符号化された位置情報と、対応情報とをそれぞれ分離して出力する。【００３１】
位置情報復号部は、分離された複数の符号化された位置情報を復号する。並替え部は、復号された複数の位置情報を、分離された対応情報に従って所定順序に従い並替える。【００３２】
並替え後の複数の位置情報それぞれと、分離されている所定順序で並んだ複数の要素情報それぞれとが対応付けされた情報が出力される。【００３３】
前述の所定順序は、所定種別の要素情報の検索に適した順序を指す。
【発明の効果】
【００３４】
本発明では、木構造の情報の符号化によって生成される所定情報には、木構造の複数の葉に付された所定種別の複数の要素情報が含まれる。この複数の要素情報は、所定種別の要素情報の検索に適した順番に従い並べられている。したがって、所定情報の検索に際しては高い検索効率を得ることが可能となる。【００３５】
また、位置情報の符号化は差分符号化を用いることで情報群の位置情報を効率的に符号化できる。これにより、所定情報について、復号により元の情報群を取得するのに必要な情報の種類と情報の量を有しながらも情報量を少なくできる。このことから、情報群を符号化して生成された所定情報を伝送する場合には高い伝送効率を得ることができる。また所定情報を記憶媒体に格納する場合には必要なメモリ容量を少なくできる。
【図面の簡単な説明】
【００３６】
【図１】本発明の第１の実施形態にかかる情報管理装置のうち、情報テーブル符号化装置の概略機能ブロック図である。
【図２】本発明の第１の実施形態にかかる情報管理装置のうち、情報テーブル復号装置の概略機能ブロック図である。
【図３】木構造中の出現順に従い情報を格納するテーブルの一例を示す図である。
【図４】テーブルの具体的なデータ構造の一例を示す図である。
【図５】テーブルの具体的なデータ構造の他の例を示す図である。
【図６】本発明の第１の実施形態における情報管理方法のうち、情報テーブル符号化方法を表すフローチャートである。
【図７】要素情報が辞書順に並んだテーブル形式の情報を示した例である。
【図８】第１の実施形態において対応情報を抽出する過程を示す図である。
【図９】位置情報の差分符号化時に用いる位置情報符号を示した例である。
【図１０】差分符号化された位置情報の符号列を位置情報と共に示す図である。
【図１１】本発明の第１の実施形態にかかる情報テーブル符号化装置で符号化された圧縮情報のデータ構造を示した説明図である。
【図１２】本発明の第１の実施形態における情報管理方法のうち、情報テーブル復号方法を表すフローチャートである。
【図１３】本発明の第２の実施形態にかかる情報管理装置のうち、情報テーブル符号化装置の概略機能ブロック図である。
【図１４】第２の実施形態において対応情報を抽出する過程の一例を示す図である。
【図１５】第２の実施形態において対応情報を抽出する過程の他の例を示す図である。
【図１６】第１および第２の実施形態にかかる情報管理装置のハードウェア構成図である。
【図１７】従来および本発明の実施の形態に適用される木構造からなる映像の付加情報の一例を示す図である。
【図１８】図１７の木構造を分割した部分木を示す図である。
【図１９】従来のテーブル形式の情報の一例を示す図である。
【符号の説明】
【００３７】
１０１，９０１  テーブル分離部、１０２，９０２  位置情報符号化部、１０３  要素情報並替部、１０４，９０４  対応情報抽出部、１０５，９０５  対応情報符号化部、１０６，９０６  圧縮情報形成部、２０１  圧縮情報分離部、２０２  位置情報復号部、２０３  対応情報復号部、２０４  位置情報並替部、２０５  テーブル形成部、９０３  位置情報並替部、１６０１  ＣＰＵ、１６０２  ＲＯＭ、１６０３  ＲＡＭ、１６０４  ＨＤＤ、１６０５  インターフェース、１６０６  通信デバイス、１６０７  入力部、１６０８  出力部、１６１３  バス。
【発明を実施するための最良の形態】
【００３８】
以下に説明する第１〜第３の実施の形態では、木構造から構成される情報に対し、検索用の補助情報として参照されるテーブルまたは当該テーブルに格納される情報を符号化して、その結果、当該テーブルまたは情報を圧縮する。以下、これを圧縮符号化という。このテーブルには、木構造における複数の葉Ｌそれぞれに付された要素情報と該葉Ｌの木構造における前述の規定順序に従う位置を示す位置情報とからなるレコードが複数個格納されている。圧縮符号化の際には、テーブルの複数レコードの複数の要素情報（出演者の名前を示すテキスト情報）は辞書順に並べて保持する。そして、テーブルの複数レコードの位置情報それぞれは、該位置情報の葉Ｌに対して前述の規定順序に従い直前に位置（出現）する葉Ｌの位置情報との差分に基づき符号化する。そして、複数の要素情報それぞれと位置情報との対応関係を示す情報を生成して、これを符号化する。そして、これら情報を所定形式に配置された１個の情報を形成する。形成される情報は、前述の検索用の補助情報として得られる。【００３９】
なお、ここでは、テーブルで管理される要素情報は図１７の最下位層の葉Ｌに付された「出演者」を示すデータとしているが、これに限定されない。任意の位置にある葉Ｌに対して適用可能であるし、あるいは図１７の木構造に含まれる任意の節Ｎをそれ以下に連結されている要素情報の集合として与えた仮の要素情報とみなして、本発明の方式を適用することもできる。この場合、テーブルのレコードで管理される情報は、木構造の任意の節Ｎにあたる要素情報（実際には要素情報の集合）とその位置情報の組となる。【００４０】
（第１の実施の形態）
本発明の第１の実施形態にかかる情報管理装置を、図１ないし図１２ならびに図１７を用いて説明する。本発明の第１の実施形態にかかる情報管理装置は、情報テーブル符号化装置および情報テーブル復号装置を備える。【００４１】
図１は本発明の第１の実施形態にかかる情報管理装置のうち、情報テーブル符号化装置１の概略構成を示した機能ブロック図である。情報テーブル符号化装置１は、受理部１０７を有するテーブル分離部１０１、位置情報符号化部１０２、対応情報抽出部１０４を内部に有する要素情報並替部１０３、対応情報符号化部１０５および圧縮情報形成部１０６を備える。【００４２】
図２は本発明の第１の実施形態にかかる情報管理装置のうち、情報テーブル復号装置２の概略構成を示した機能ブロック図である。情報テーブル復号装置２は、受理部２０７を有する圧縮情報分離部２０１、テーブル７０７を有する位置情報復号部２０２、対応情報復号部２０３、位置情報並替部２０４およびテーブル形成部２０５を備える。【００４３】
以下、図１７に示した映像の付加情報を例に、本実施形態にかかる情報管理装置（情報テーブル符号化装置１および情報テーブル復号装置２）の動作を説明する。図１７に示されるように、映像の付加情報は映像の論理構造に対応した木構造で表される。図１７の各節Ｎの種別名‘シーン’、‘サブシーン’および‘出演者’それぞれに付された数字「１」「２」「３」は、該節Ｎの木構造中の位置を一意に特定するための情報として付されている。【００４４】
無論、実際の映像の付加情報は構造、内容共にこれに限られるものでない。例えば、ルートノードＲＮ（木の最上位ノード）やシーンを表す各節Ｎに、対応する映像タイトルあるいはシーンタイトルを表す葉Ｌを追加したり、サブシーンを更に細かなサブシーンに分割して木の階層数を増やしたり、あるいは減らしたりといったことが可能である。付加情報に含まれる要素の種別も図１７に示したものに限定されない。また、シーン、サブシーンの組合せによる木（１つの映像を記述した木）以外にも、ルートノードＲＮが１つのチャンネルで放送される全番組（プログラム）を表し、１階層目の節Ｎそれぞれがプログラムを表し、２階層目の各節Ｎがプログラムに含まれるシーンを表すといった木を扱うこともできる。【００４５】
図３のテーブル６０は複数のレコードを含む。各レコードには、図１７の付加情報から抜出した同種の要素情報「出演者」の値６１と、該要素情報の値６１にあたる葉Ｌの位置情報６２とを格納した組を格納している。図３のテーブル６０では、図１７の付加情報の木が端から順に走査され、抜出された同種の要素情報「出演者」が木構造上での出現順にそのまま並べられている。即ち、木構造を左から右に走査した場合に現れる要素情報の値６１が出現順に従いテーブル６０の上から下に順に格納されている。したがって、位置情報６２は１〜３階層の位置の組合せにより（シーン＃、サブシーン＃、出演者＃）として示されるので、テーブル６０では例えば要素情報の値６１が「Akira  ABE」の位置情報６２は値（１，１，１）と示されて、要素情報の値６１が「Wataru  WADA」の位置情報６２は値（１，１，３）と示される。位置情報６２は、同一階層の節Ｎに対して木の左側から値が振られるため、最も左の要素情報６２の値が最小値（１，１，１）を示し、最も右の要素情報６２の値が最大値（２，１，１）を示す。【００４６】
本実施形態では、図３に示したテーブル６０を情報テーブル符号化装置１への入力とする。即ち、本実施形態では、木構造からなる付加情報に含まれる要素情報から同種の要素の値が既に選択されて抜出されていることを前提とし、それらの要素情報の値６１および対応する位置情報６２の符号化に関する処理について説明する。無論、情報テーブル符号化装置１を、木構造の情報から同種の要素情報を選び出して要素種別毎にテーブルを形成し、かつ、要素種別を表す情報も共に符号化して要素情報の値６１および位置情報６２の符号列に加えて圧縮情報を形成する機能を有するようにすることも可能である。同様に、情報テーブル復号装置２を、要素種別の情報、要素情報の値６１および位置情報６２のそれぞれを復号して要素種別毎にテーブルを形成する機能部として、図示のない上位の情報テーブル復号装置が有することも可能である。また、ここで言う符号化対象のテーブルとは、要素情報と位置情報とが一対一に対応付けられるデータ構造のことであって、実際には、図４または図５に示すような構造のデータを指す。【００４７】
図４のテーブル６３と６４は、要素情報の種別毎に、要素情報の値と対応の位置情報とが対になって格納されるグループを有する。各グループでは、図４（Ａ）のテーブル６３のように、要素情報（値Ａ１、値Ａ２、・・・、値Ｂ１、値Ｂ２、・・・）と対応している位置情報（位置情報Ａ１、位置情報Ａ２、・・・、位置情報Ｂ１、位置情報Ｂ２、・・・）とが対となり、かつ要素情報の値と位置情報とが交互に配置される構造を有する。また、各グループでは、図４（Ｂ）のテーブル６４のように、要素情報が全て連続して配置された後、対応する位置情報が全て連続して配置される構造を有してもよい。【００４８】
図５のテーブル６５と６６は、要素情報の値が位置情報とは離れた別のデータ構造に格納されている。そのため、要素情報の種別毎に、その別のデータ構造に格納された要素情報の値を参照するための参照情報が該要素情報の値の位置情報と対となって格納されるデータ構造を有する。図５（Ａ）のテーブル６５は、要素情報の値への参照情報と対応する位置情報とが対となり、かつ該参照情報と位置情報とが交互に配置される構造を有する。図５（Ｂ）のテーブル６６は、要素情報への参照情報が全て連続して配置された後、対応する位置情報が全て連続して配置される構造を有する。【００４９】
後述する位置情報の差分符号化を行なうためには、図４（Ｂ）あるいは図５（Ｂ）に示されたような、複数の位置情報が連続して配置されているデータ構造が望ましいが、要素情報の値あるいは要素情報の値への参照情報にかかる符号の量が判るような場合では、図４（Ａ）あるいは図５（Ａ）のように参照情報と位置情報が交互に配置されたデータ構造であっても、位置情報の差分符号化を行なうことは可能である。また、図４および図５では要素情報の値（または要素情報の値への参照情報）を先に、その後に対応する位置情報を配置したデータ構造を例に示したが、位置情報を先に、その後に対応する要素情報の値（または要素情報の値への参照情報）を配置するデータ構造であっても構わない。【００５０】
（情報テーブル符号化装置の動作）
本実施形態にかかる情報テーブル符号化装置１のテーブルを符号化する動作について図６のフローチャートを参照して説明する。【００５１】
テーブル分離部１０１は、木構造からなる情報に含まれた同種の要素情報を抜出すことで予め得られている図３のテーブル６０を（実際には図４または図５で示されたようなデータ構造からなるデータを）受理部１０７により受取り（ステップＳ（以下、単にＳと略す）１０）、受取ったテーブル６０の情報を要素情報の値６１と位置情報６２とに分離して出力する（Ｓ１１）。無論、テーブル６０が予め生成されておらず、図１７の木構造の付加情報を受取って、そこに含まれる要素情報の種別を解析し、同種の要素情報を集めて図３のテーブル６０を生成するまでの処理をテーブル分離部１０１が行なうようにしてもよい。【００５２】
位置情報符号化部１０２は、テーブル分離部１０１から出力された位置情報６２を入力して符号化する。この際、図３のテーブル６０において、複数の位置情報６２は、木構造における出現順序と同じく、数値の小さいものから大きいものへと順に（昇順）に並んでいるため、特許文献１で示されている差分符号化を用いて効率的に符号化することができる。以降、数値の小さいものから大きいものへと順に並ぶことを大小順に並ぶという。符号化の具体例については図９と図１０を用いて後述する。【００５３】
要素情報並替部１０３は、テーブル分離部１０１から出力された複数の要素情報の値６１を入力する。そして、入力した要素情報の値６１を、当該要素情報の値６１は図３のテーブル６０で示された木構造中の出現順、即ち位置情報６２の値の順に並んでいるが、辞書順（アルファベット順または日本語に固有の５０音順といった辞書編集上の順序）に従うように並べ直す（Ｓ１２）。【００５４】
図７は、要素情報並替部１０３の並替えによって図３のテーブル６０の情報を並替えた後のテーブル６０１を示したものである。図７のテーブル６０１はまた、後述する情報テーブル復号装置２で出力されるテーブル６０１を示す。実際に検索時の補助情報として用いられるテーブルは、図７に示したような、要素情報の値６１が辞書順に並んだ形式のものとなる。つまり、図３に示した木構造の出現順に要素情報の値６１が並べられたテーブル６０は、符号化のために作成された中間データに相当する。【００５５】
図７からも判るように、並替え後の位置情報６２は、その値の大小順関係に従って並んでいないため、上述した差分符号化を直接行なうことはできない。そこで、対応情報抽出部１０４は、図３のテーブル６０から図７のテーブル６０１への変化により示されるように要素情報の値６１を並替えた際、どう並替わったかを検出して、検出結果を示す情報を要素情報と位置情報との対応情報７０３として出力する（Ｓ１３）。この対応情報７０３を生成するための処理は要素情報６１の並替えと同期して行なわれるため、対応情報抽出部１０４は要素情報並替部１０３の内部構成となっている。【００５６】
図８（Ａ）は図８（Ｂ）の対応情報７０３を求める処理過程の例を示している。図８（Ａ）には、図３の並替え前の要素情報の値６１が要素情報７０１として、図７の並替え後の要素情報の値６１が要素情報７０２としてそれぞれ示されている。処理は、図面の左から、まず、並替え前の要素情報７０１のそれぞれに対して並びの順に（１）から（６）までの通し番号を付ける（ステップＳ（以下、単にＳという）１）。次に、通し番号を付けた状態で、要素情報７０１を辞書順に並替える（Ｓ２）。並替え後の要素情報７０２に付された通し番号は（１）、（４）、（５）、（２）、（６）、（３）の並びとなる。したがって、図８（Ｂ）の対応情報７０３は並替えの結果を示す並替え後の通し番号の並びを示す。無論、対応情報７０３はこのような通し番号で与えられるものに限らず、要素情報の値６１の並替えがどのように行なわれたかを示すことが可能な情報であればよい。また、通し番号に基づく対応情報７０３であっても、対応情報７０３の付け方および対応情報の抽出方法はここで示したものに限らず、様々な方法での実装が可能である。【００５７】
次に、位置情報符号化部１０２はテーブル分離部１０１から出力された位置情報６２を入力して、入力した位置情報６２を差分符号化して出力する（Ｓ１４）。対応情報符号化部１０５は、対応情報抽出部１０４で抽出（生成）された対応情報７０３を入力して、入力した対応情報７０３を符号化して出力する（Ｓ１５）。最後に、圧縮情報形成部１０６は、位置情報符号化部１０２、対応情報符号化部１０５および要素情報並替部１０３のそれぞれから出力された、符号化された位置情報６２、符号化された対応情報７０３、および並替え後の要素情報の値６１を入力して、これら入力した情報が所定の形式に配置された圧縮情報７０８を形成して出力する（Ｓ１６）。情報テーブル符号化装置１から出力された圧縮情報７０８（検索時の補助情報となるテーブル６０１を圧縮符号化した情報）はテーブル６０１の伝送時または蓄積時に、伝送データ量または蓄積データ量を減らしてテーブル６０１を効率良く管理するために用いられる。【００５８】
この実施形態では、要素情報の値６１自体の圧縮符号化については説明しなかったが、位置情報６２および対応情報７０３を符号化するのと共に、要素情報の値６１自体を符号化することがテーブル６０１の伝送や蓄積時の効率向上のために有効なことは言うまでもない。テーブル６０１で示した要素情報はテキスト情報である。従って、通常のテキストのコード化による圧縮や、Zip圧縮など既存の圧縮ツールを用いた圧縮が可能である。【００５９】
また、並替え後の要素情報の値６１が辞書順に並ぶことから、同じ値６１を持った要素情報をまとめて扱うといった処理や、差分符号化といった処理を適用することも可能である。前者では、例えば、同じ値６１を持つ要素情報について、該値６１とその値を有する要素情報の個数とでそれらの要素情報を符号化する。例えば図７のテーブル６０１には、値６１が「Rie  RYUSHO」の要素情報が２つあるので、圧縮情報形成時には「Rie  RYUSHO」を２回記録する代わりに「Rie  RYUSHO」を１回だけ記録し、加えて「２」という個数の情報を記録することで、テーブル６０１を記録するためにかかるデータ量を削減できる。無論、要素情報の値６１の符号化の方法はこの例に限らない。また、要素情報がテキスト情報以外の属性を有するならば、その属性に合せた符号化方法が用いられる。それらの詳細についてはここでは割愛する。【００６０】
このように要素情報の値６１を圧縮符号化した後に圧縮情報形成部１０６に与える、または圧縮情報形成部１０６において要素情報の値６１を圧縮符号化した後に圧縮情報７０８の形成に用いることで、圧縮情報７０８のデータ量をより少なくできる。【００６１】
ここで、図３、図７、および図８を参照しながら、図９と図１０を用いて本実施形態による具体的な符号化の例を示す。但し、上述したように、ここでは要素情報の符号化については触れず、位置情報６２および対応情報７０３の符号化を行なうとし、特に符号化後の符号量について評価する。【００６２】
まず、差分符号化を行なわない通常の方式で位置情報６２を符号化した場合について示す。図７のテーブル６０１の情報が検索時の補助情報となる。テーブル６０１の位置情報６２は位置情報が示す値の大小順に従い並んでいないため、通常の方式で符号化する。【００６３】
仮に、位置情報６２について１つの階層の値を５ビットで符号化すると、図７に示された位置情報６２は３個の階層の値で示されるので、符号化するには５×３＝１５ビットが１つの位置情報６２を表すために必要となる。テーブル６０１では位置情報６２が６つあるため、合計で１５×６＝９０ビットが、並替えを行なわない場合の位置情報６２にかかる符号量である（この場合、対応情報７０３は不要である）。【００６４】
なお、１つの階層を表すのに必要なビットの数は、１つ上の階層にある１つの節Ｎ（親ノード）に接続されてそこから分岐可能な節Ｎ（子ノード）の数に依存しており、上記５ビットは２の５乗個、すなわち３２個の分岐までが可能な場合を示す。実際の映像の付加情報においては更に大きなビット数を必要とする。【００６５】
次に、特許文献１に示された差分符号化による方法で位置情報６２を符号化した場合について示す。ここでは、図３のテーブル６０に示す順に並んだ位置情報６２を差分符号化する。【００６６】
図９は、本実施の形態に係る位置情報６２の差分符号化で用いられる符号７０４のそれぞれに対応して、その符号７０４が示す意味７０５のデータをテーブル形式で示す。また図１０には、図３の位置情報６２を符号化して得られる符号列７０６を、符号化される位置情報６２と対比する形で示す。位置情報符号化部１０２は位置情報６２の符号化の規則を示す符号化規則データ７０９を有する。位置情報符号化部１０２は、特許文献１に示された方法に従い、符号化規則データ７０９を参照して位置情報６２を符号化する。すなわち、テーブル６０の先頭に格納された位置情報６２を通常の方法で符号化した後、続いて格納されている位置情報６２について、どの階層で分岐したかを示す差分、即ちどの階層の値が更新（インクリメント）されるかを符号７０４で示していくことで、続く位置情報６２を符号化する。【００６７】
位置情報符号化部１０２により図３の位置情報６２を符号化した場合、次の様になる。つまり、テーブル６０の先頭に格納された位置情報６２が１５ビット（１階層あたり５ビット×３階層）で符号化されて（図１０の一番左の符号列７０６を参照）、以降に格納された５つの位置情報６２については、３ビットの符号７０４で符号化されて図１０では符号列７０６として与えられる。このビット数‘３’は、＜階層数＞３＋＜終了コード＞１＋＜欠落コード＞１＝５を表すことが可能な最小ビット数＝３ビットとして決められる。そして最後に３ビットの終了コードを示す符号７０４（図１０の一番右の符号列７０６を参照）を加える。したがって、１５＋３×６＝３３ビットで図３のテーブル６０に格納されているすべての位置情報６２が差分符号化される（図１０参照）。【００６８】
次に、圧縮情報形成部１０６では、図１０の符号列７０６に、対応情報符号化部１０５により符号化された後の図８（Ｂ）に示された対応情報７０３を加える。対応情報７０３の１つの位置情報６２に対応の情報（数値）は、テーブル６０の位置情報６２の総数が６であることから、その総数値を表すことができる最小ビット数である３ビットで符号化することができる。この総数値は、位置情報符号化部１０２の位置情報６２の符号化によって圧縮情報に含められる。そして、テーブル６０の位置情報６２の個数と同じく６個の対応情報７０３を符号化するために、対応情報符号化部１０５により、３×６＝１８ビットで図８（Ｂ）の対応情報７０３は符号化される。従って総ビット数は、位置情報符号量の３３ビット＋対応情報符号量の１８ビット＝５１ビットである。【００６９】
このように、差分符号化を行なわないで位置情報６２を符号化した場合の符号量は９０ビットであるのに対して、位置情報６２の差分符号化および対応情報７０３の符号化を行なった場合の符号量が５１ビットであるから、本実施形態のように差分情報および対応情報７０３によって位置情報６２を符号化する方が、差分符号化しない従来方式に比べて符号量を少なくできる（圧縮率を高くできる）。上記数値は一例であるが、符号化の対象となる位置情報６２の個数、あるいは位置情報６２が示す階層数が増えるとその圧縮効果は更に顕著になる。また、上記で示した対応情報７０３の符号化方法は一例であり、これに限らず、更に効率の高い符号化方法が適用されてもよい。対応情報７０３を更に効率の高い符号化方法で符号化することにより圧縮効果は更に顕著になる。【００７０】
図１１には、本実施の形態でテーブル形式の情報が符号化された圧縮情報のデータ構造例が概略的に示される。図１１（Ａ）は図４（Ｂ）のデータを符号化した圧縮情報のデータ構造を示し、図１１（Ｂ）は図５（Ｂ）のデータを符号化した圧縮情報のデータ構造を示している。図１１のそれぞれのテーブルにおいて、連続する複数の位置情報が、「位置情報符号列」および「対応情報符号列」に置き換わっている。既に説明した通り、本実施形態では要素情報の値６１の符号化については詳しく言及しないため、要素情報の値（値Ａ１、値Ａ２、・・・、値Ｂ１、値Ｂ２、・・・）については、図４（Ｂ）と図５（Ｂ）のものをそのまま図１１に図示している。但し、これらは各々符号化されて記録されているとしてもよい。あるいは、差分符号化等を適用し、連続する複数の要素情報の値６１を「値符号列」に置き換えた形で圧縮情報が構成されるとしてもよい。なお、図１１のテーブル６４１と６６１では、要素情報の値６１（または要素情報の値６１への参照情報６７）を先に、位置情報符号列６８および対応情報符号列６９を後に配置したデータ構造を有するが、位置情報符号列６８および対応情報符号列６９を先に、要素情報の値６１（または要素情報の値６１への参照情報６７）を後に配置するデータ構造を有するとしてもよい。また、位置情報符号列６８と対応情報符号列６９についてもどちらが先に配置されてもよいし、位置情報符号列６８と対応情報符号列６９の間に要素情報の値６１（または要素情報の値６１への参照情報６７）が挟まれるように配置されてもよい。【００７１】
（情報テーブル復号装置の動作）
次に、本実施形態にかかる情報テーブル復号装置２の動作について図１２のフローチャートを参照して説明する。【００７２】
圧縮情報分離部２０１は、受理部２０７により圧縮情報７０８を入力して（ステップＳ（以下、単にＳと略す）２０）入力した圧縮情報７０８から位置情報６２の符号列８０、対応情報７０３の符号列８１および要素情報の値６１（もしくは要素情報の値６１の符号列８２）を分離して出力する（Ｓ２１）。【００７３】
位置情報復号部２０２は、圧縮情報分離部２０１から出力された位置情報６２の符号列８０を受取り、受取った符号列８０を特許文献１に示された手順に従い、テーブル７０を参照して差分復号する（Ｓ２２）。差分復号は、差分符号化方法により符号化されたデータを復号することを指す。【００７４】
差分復号の過程を、図１０を参照して説明する。まず、位置情報６２の符号列７０６の先頭の１５ビットを読込んで解釈して、テーブル６０の先頭に格納された位置情報（１，１，１）が復号される。次に、以降の位置情報６２の符号列７０６から３ビットずつ符号７０４を順に読込んで解釈する。最初の３ビットの位置情報６２の符号７０４「０１１」は、図９のテーブル７０７を参照すると出演者の階層での分岐（更新）を示す符号であると解釈される。従って先頭（１番目）に復号された位置情報（１，１，１）について出演者階層の値を１更新し、２番目の位置情報（１，１，２）を得る。次の位置情報符号７０４も「０１１」であるから、３番目の位置情報は（１，１，３）である。次に読込まれる位置情報符号７０４は「０１０」で、図９のテーブル７０７を参照するとサブシーン階層での分岐（更新）を示す符号であると解釈される。またこの時、サブシーン階層で分岐が起こると、それより下位のノード、本例では出演者のノードは別のサブシーンの下に付く要素となるため、値は１からカウントし直される。従って、サブシーン階層の値は１更新され、出演者階層の値は１に戻されるため、４番目の位置情報は（１，２，１）となる。以下同様に処理することで（１，２，２）、（２，１，１）が復号結果として得られる。最後に位置情報符号７０４「０００」が読み込まれる。これは図９のテーブル７０７を参照すると、復号終了を指示する終了コードであると解釈されるので、該終了コードが読込まれたことに応答して復号は終了する。【００７５】
上述した手順に従えば、位置情報復号部２０２から出力される復号された複数の位置情報６２は、当該位置情報６２の値の大小順に従って（図３のテーブル６０の先頭から格納される値の順で）出力される。【００７６】
対応情報復号部２０３は、対応情報７０３の符号列８１を圧縮情報分離部２０１から受取り、受取った符号列８１を対応情報７０３に復号して出力する（Ｓ２３）。【００７７】
位置情報並替部２０４は、対応情報復号部２０３から出力された復号結果である対応情報７０３を入力するとともに、位置情報復号部２０２から出力された復号結果である位置情報６２の値を入力する。そして、入力した位置情報６２の値の並び順を入力した対応情報７０３に基づいて並替える（Ｓ２４）。【００７８】
例えば、図３のテーブル６０に示した順に復号された位置情報６２の値に対して、図８（Ｂ）の対応情報７０３が復号されているとする。この時、位置情報並替部２０４は、復号された対応情報７０３に示された数値が示す順番に従い復号された（入力した）位置情報６２を並べる。まず、復号された図８（Ｂ）の対応情報７０３の１番目の値‘１’に基づき、１番目に復号された位置情報（１，１，１）が１つめの位置情報６２と決まり出力される。次に、対応情報７０３の２番目の値‘４’に基づき、４番目に復号された位置情報（１，２，１）が２つめの位置情報６２と決まり出力される。次は、対応情報７０３の３番目の値‘５’に基づき、５番目に復号された位置情報（１，２，２）が３つめの位置情報６２と決まり出力される。同様にして対応情報７０３の値‘２’、‘６’および‘３’のそれぞれについて、対応する位置情報（１，１，２）、（２，１，１）、（１，１，３）が４つめ、５つめ、６つめの位置情報６２とそれぞれ決まり出力される。このように、順に位置情報６２が決まって出力される。【００７９】
最後に、テーブル形成部２０５は、圧縮情報分離部２０１から出力された要素情報の値６１と位置情報並替部２０４から上述の順番で出力された位置情報６２とを対応する形に並べて、図７に示すように要素情報の値６１が辞書順に並んだテーブル６０１を形成して出力する（Ｓ２５）。【００８０】
情報テーブル復号装置２は、伝送または蓄積時において圧縮符号化されたテーブル６０の情報７０８を復号し、検索時の補助情報として復号後のテーブル６０１を提供する。例えば、情報テーブル復号装置２は、付加情報に基づく検索機能を持ったユーザの情報端末上に実装されて、伝送路を通して該情報端末が受信した圧縮情報７０８（検索時の補助情報となるテーブル６０１を圧縮符号化した情報）を復号するために用いられる。復号により形成されたテーブル６０１は、位置情報６２が大小順から要素情報６１と対応した順に並替えられ、かつ要素情報の値６１が辞書順に並んだものであり、復号して以降、ユーザはこのテーブル６０１を用いて所望要素情報の検索を行ない、必要な部分木（フラグメント）を決定し、対応するフラグメントを入手する。これは、情報管理装置から出力されたテーブル６０１を用いてユーザが検索を行なう際に、辞書順で扱う方が検索に有利、即ち効率の良い高速な検索が可能なためである。【００８１】
図１２では、位置情報６２の復号処理を対応情報７０３の復号よりも先に行なうようにしているが、どちらの復号処理が先に行なわれても、あるいは同時に並行して処理されるとしても構わない。
（第２の実施の形態）
本発明の第２の実施形態にかかる情報管理装置を、図１３、図１４および図１５を参照して説明する。第２の実施形態にかかる情報管理装置は、情報テーブル符号化装置ならびに情報テーブル復号装置からなる。このうち、情報テーブル復号装置については、第１の実施形態にかかる図２の情報テーブル復号装置２と同一であるため、本実施形態では説明を省略する。【００８２】
図１３は、本発明の第２の実施形態にかかる情報管理装置のうち、情報テーブル符号化装置１０の機能ブロック図である。情報テーブル符号化装置１０は、受理部９０７を有するテーブル分離部９０１、位置情報符号化部９０２、対応情報抽出部９０４を有する位置情報並替部９０３、対応情報符号化部９０５および圧縮情報形成部９０６を備える。このうち、受理部９０７を有するテーブル分離部９０１、位置情報符号化部９０２、対応情報符号化部９０５および圧縮情報形成部９０６については、第１の実施形態で図１に示す受理部１０７を有するテーブル分離部１０１、位置情報符号化部１０２、対応情報符号化部１０５および圧縮情報形成部１０６と同一機能を有するので、本実施形態では以下、第１の実施形態との相違箇所を主に説明する。【００８３】
先の第１の実施形態では、図１７の映像の付加情報から所定種別の要素情報のみを抜出してテーブル６０を形成する際、木構造を上位階層から下位階層に、かつ同一階層は木の左から右に順に走査しながら木構造内での出現順に該所定種別の要素情報を抜出しテーブル６０に順に並んで格納されることを前提としていた（図３参照）。このため、第１の実施形態の情報テーブル符号化装置１（図１参照）は、テーブル６０から要素情報の値６１を含む各種情報を分離して出力して以降は、検索時の補助情報として扱う形式に合せて、分離出力された要素情報の値６１を辞書順に並替える機能部、即ち要素情報並替部１０３を備えていた。【００８４】
これに対して、第２の実施形態では、図１７の映像の付加情報から所定種別の要素情報の値６１を抜出してテーブル６０を形成する際に、予め木構造全体を走査し、該所定種別の要素情報の値６１を抜出す段階で、辞書順に並ぶように抜出してテーブル６０が形成されるものとする。即ち、図７に示したような、要素情報の値６１が辞書順に並んだテーブル６０１が、第２の実施形態における情報テーブル符号化装置１０（図１３参照）の入力とされる。この場合、要素情報の値６１は既に辞書順に並んでいるため、第１の実施形態にあった要素情報並替部１０３は情報テーブル符号化装置１０では不要となる。一方、位置情報６２は入力するテーブル６０１では位置情報が示す値の大小順に並んでいない。このため、本実施形態における情報テーブル符号化装置１０（図１３）は、位置情報６２を差分符号化するために、位置情報６２が示す値（数値）の大小順に並替える機能部、即ち位置情報並替部９０３を備える。【００８５】
動作を図１３を参照しながら、図６のフローチャートに従い説明する。
まず、受理部９０７によりテーブル６０１が入力される（Ｓ１０）。テーブル分離部９０１は入力したテーブル６０１から要素種別の値６１と位置情報６２を読出し、分離して出力する（Ｓ１１）。【００８６】
位置情報並替部９０３は、テーブル分離部９０１から出力された複数の位置情報６２を入力して、入力した複数の位置情報６２を、それぞれが示す数値の大小順に並替えた後に位置情報符号化部９０５に出力する（Ｓ１２）。またこの時、位置情報並替部９０３の内部の対応情報抽出部９０４は、位置情報６２がどう並替えられたかを検出し、検出結果に基づき要素情報の値６１と並替え後の位置情報６２との対応関係を示す対応情報７０３を入力情報から抽出して出力する（Ｓ１３）。【００８７】
図１４および図１５には、位置情報６２の並替え処理時に位置情報６２から対応情報７０３を抽出（生成）する方法が示される。図１４（Ａ）では、入力された（図７のテーブル６０１から読出した）複数の位置情報６２に対し、各位置情報６２にそれが示す値（数値）の小さい順に通し番号を振って、要素情報の値６１と並替え後の位置情報６２との対応情報７０３（図１４（Ｂ）参照）を求める例が示される。【００８８】
但し、図１４（Ａ）の例では、位置情報６２に通し番号を割振る段階で数値の大小判定を逐一行なうことが必要であるから、例えば、図１４（Ａ）の処理手順には既存のソートアルゴリズムを利用した高速な並替え処理はうまく適合しない。そこで、既存の高速な並替え処理を効果的に活用しようとしたのが図１４（Ｃ）の例である。図１４（Ｃ）では、位置情報６２にテーブル６０１で並んでいる順に通し番号を割振る処理を２回（ステップＳ１４０１とＳ１４０３参照）と、位置情報６２をそれが示す値の大小順に並替えるソート処理を２回（ステップＳ１４０２とＳ１４０４参照）行なう。その結果、図１４（Ｄ）の対応情報７０３が出力される。【００８９】
また、図１５には、階層毎の位置情報６２の値の出現個数に基づいて、対応情報７０３を計算で求める方法が示される。この方法ではまず、図１５（Ａ）に示すように、位置情報６２の値（数値）の大小順に並替えを行ない（ステップＳ１５０１）、その後、並替えされた位置情報６２の各階層の各値の出現個数を上位の階層から順にカウントする（ステップＳ１５０２）。その結果、最上位層（シーン階層）で値‘１’の個数は５個、値‘２’の個数は１個である。また最上位層の値‘１’である５個の位置情報６２のうち、第２階層（サブシーン階層）で値‘１’の個数は３個、値‘２’の個数は２個とカウントされる。次に、各々の階層のある値の出現個数から、その値が出現する前までに出現している位置情報６２の個数を累積数Ｃxxxとして求める（ステップＳ１５０３）。【００９０】
Ｓ１５０２の処理に従えば、最上位層（シーン階層）で値‘１’が初めて出現するより前に存在する位置情報６２は無い。従って累積数Ｃ1xxは０である。最上位層（シーン階層）で値‘２’が初めて出現する前には、値‘１’をとる位置情報６２が５個存在する。従って累積数Ｃ2xxは５である。同様に、最上位層の値‘１’である５個の位置情報６２うち、第２階層（サブシーン階層）で値‘１’が初めて出現する位置情報６２より前に存在する位置情報は無い。従って累積数Ｃ11xは０である。最上位層の値が‘１’である５個の位置情報６２のうち、第２階層で値‘２’が初めて出現する位置情報６２より前においては、第２階層で値‘１’をとる位置情報６２が３個存在する。従って累積数Ｃ12xは３である。【００９１】
こうして、ステップＳ１５０３に示すようにそれぞれの累積数Ｃxxxが得られたら、図１５（Ｂ）に示すように、並替え前の位置情報６２それぞれに対して、各階層の値に対応する累積数Ｃxxxの総和を求める（ステップＳ１５０４）。次に、ステップＳ１５０４で得られた各総和は、対応の位置情報６２より前に存在する位置情報６２の個数を表しているため、最後に、その位置情報６２自身をカウントするために‘１’を対応の総和に加える（ステップＳ１５０５）。これにより、図１５（Ｃ）の対応情報７０３が出力される。【００９２】
無論、対応情報７０３はここに示した位置情報６２に割振りされる通し番号で与えられるものに限らず、位置情報６２の並替えがどのように行なわれたかを示すことが可能な情報であればよい。また、通し番号に基づく対応情報７０３であっても、対応の付け方ならびに対応情報７０３の抽出方法はここで示したものに限らず様々な方法が可能である。【００９３】
以降の位置情報符号化部９０２の位置情報６２の差分符号化（Ｓ１４）、対応情報符号化部９０５の対応情報７０３の符号化（Ｓ１５）、および圧縮情報形成部９０６の圧縮情報の形成（Ｓ１６）については、第１の実施形態で記載した内容がそのまま第２の実施形態にも当てはまる。従って、ここでは重複した説明を省略する。【００９４】
要素情報の値６１が上述の各実施の形態で示したようなテキスト情報で示されない場合にも、上述した情報管理装置および方法は適用可能である。このように本発明では、伝送または蓄積の対象とされるテーブル６０（または６０１）中の要素情報の値６１と位置情報６２とが、更に一般化すれば、テーブル６０（または６０１）のようにして管理される複数の１つめの要素と対応する複数の２つめの要素とが、それぞれ異なる順序関係に従って並べたときに検索効率が最大となる、もしくは符号化効率が最大となるといった特性をもっている場合に、何れか一方の要素の特性に適した順序に双方の要素を並べた後、もう一方の要素をその特性に適した順序に並替える。それとともに、並替え後の２つの要素間での対応関係を示す対応情報を生成し並べ替えた双方の要素に付加することで、双方の要素をそれぞれの特性に適した順序に並んだ形で扱えるようにしたことに特徴がある。そして、第１および第２の実施の形態で示したように、１つめの要素が検索効率を最大化する順序に、２つめの要素が符号化効率を最大化する順序に並んだ形で伝送または蓄積の対象となる情報を形成したとすれば、形成された情報は、符号化効率と検索効率とを両立させることが可能な情報となる。この他、１つめの要素、２つめの要素それぞれが異なる順序関係に従って並べたときにそれぞれ符号化効率が最大となる場合や、１つめの要素、２つめの要素それぞれが異なる順序関係にしたがって並べたときに、それぞれ検索効率が最大となる場合もある。【００９５】
（第３の実施の形態）
上述した実施形態１と２にかかる情報管理の手順はプログラムに基づいて実行される。図１６は、実施形態１と２の情報管理装置に対応する装置のハードウェアの概略構成図である。図１６の装置はコンピュータの構成を有する。具体的には、図１６の装置は、装置の各部を集中的に制御および監視するためのＣＰＵ（Central  Processing  Unit）１６０１、各種プログラムとデータを格納するためのＲＯＭ（Read  Only  Memory）１６０２、ＲＡＭ（Random  Access  Memory）１６０３、ＨＤＤ（Hard  Disk  Drive）１６０４、ＤＶＤ（Digital  Versatile  Disk）やメモリカードなどの外部記録デバイスと接続するためのインターフェース１６０５、インターネットを含む各種の通信ネットワーク１６１４と接続するための通信デバイス１６０６、キーボード、マウス、ボタンなどからなる入力部１６０７、映像の表示、音声の出力、文字の表示などをするための出力部１６０８、着脱自在に装着されるＦＤ（flexible  Disk）１６１０をアクセスするためのＦＤ駆動部、着脱自在に装着されるＣＤ（Compact  Disk）１６１２をアクセスするためのＣＤ駆動部１６１１およびこれら各部間の通信を可能とするためのバス１６１３を備える。【００９６】
第１の実施形態において、情報テーブル符号化時には、ＲＯＭ１６０２、ＲＡＭ１６０３、またはＨＤＤ１６０４に予め格納されたテーブル分離部１０１に対応のテーブル分離プログラム、位置情報符号化部１０２に対応の位置情報符号化プログラム、要素情報並替部１０３および対応情報抽出部１０４に対応の要素情報並替えおよび対応情報抽出プログラム、対応情報符号化Ｂ１０５に対応の対応情報符号化プログラム、圧縮情報形成部１０６に対応の圧縮情報形成プログラムがＣＰＵ１６０１によりＣＰＵ１６０１の図示のない所定記憶領域にロードされる。そして、ＣＰＵ１６０１がロードされた各プログラムの命令を解釈し実行することで、以下の動作が行なわれる。この時、位置情報６２と要素情報の値６１とからなるテーブル６０は、予め生成されてＲＡＭ１６０３またはＨＤＤ１６０４に格納されている。図９のテーブル７０７、および符号化規則データ７０９はＣＰＵ１６０１が参照可能な情報としてＲＯＭ１６０２に予め格納される。【００９７】
まず、ＣＰＵ１６０１は、ロードされたテーブル分離プログラムに従い、ＲＡＭ１６０３またはＨＤＤ１６０４に既に格納されているテーブル６０を読出して、読出したテーブル６０から位置情報６２を抽出してテーブル６０から分離する（読出す）。そして、分離した位置情報６２をロードされた位置情報符号化プログラムに従い符号化して、符号化された位置情報６２をＲＡＭ１６０３またはＨＤＤ１６０４に一時的に格納する。また、ＲＡＭ１６０３またはＨＤＤ１６０４に既に格納されているテーブル６０から要素情報の値６１を抽出してテーブル６０から分離する（読出す）。そして、分離された要素情報の値６１を、ロードされた要素情報並替えおよび対応情報抽出プログラムに従い並替えるとともに対応情報７０３を抽出（生成）して、並替え後の要素情報の値６１と抽出した対応情報７０３をＲＡＭ１６０３またはＨＤＤ１６０４に一時的に格納する。更に、対応情報７０３をロードされた対応情報符号化プログラムに従い符号化して、符号化された対応情報７０３をＲＡＭ１６０３またはＨＤＤ１６０４に一時的に格納する。最後に、ロードされた圧縮情報形成プログラムに従い、符号化された位置情報６２および対応情報７０３、ならびに並替え後の要素情報の値６１を用いて圧縮情報７０８を形成し、形成した圧縮情報７０８をＲＡＭ１６０３またはＨＤＤ１６０４に格納する。【００９８】
この圧縮情報７０８は、テーブル６０の情報の効率的な蓄積および伝送のために活用され、インターフェース１６０５により接続された外部記録デバイスの記録媒体を介して、あるいは、通信デバイス１６０６で接続された通信ネットワーク１６１４を通して、あるいはＦＤ駆動部１６０９によりＦＤ１６１０を介して、あるいはＣＤ駆動部１６１１によりＣＤ１６１２を介して、他の情報テーブル復号機能を持つ機器に提供される。【００９９】
前述の第１の実施形態において、情報テーブル復号時には、ＲＯＭ１６０２、ＲＡＭ１６０３、またはＨＤＤ１６０４に予め格納された圧縮情報分離部２０１に対応の圧縮情報分離プログラム、位置情報復号部２０２に対応の位置情報復号プログラム、対応情報復号部２０３に対応の対応情報復号プログラム、位置情報並替部２０４に対応の位置情報並替えプログラム、およびテーブル形成部２０５に対応のテーブル形成プログラムがＣＰＵ１６０１により、ＣＰＵ１６０１の所定記憶領域にロードされ、ＣＰＵ１６０１はロードされたプログラムの命令を解読して実行することで、以下の動作が実現される。この時、圧縮情報７０８は、記録媒体を介してインターフェース１６０５から、あるいは通信ネットワーク１６１４を通して通信デバイス１６０６から得られて、予めＲＡＭ１６０３またはＨＤＤ１６０４に格納されている。【０１００】
ＣＰＵ１６０１は、ＲＡＭ１６０３またはＨＤＤ１６０４に格納されている圧縮情報７０８から、ロードされた圧縮情報分離プログラム２０１に従い要素情報の値６１を分離して、分離した要素情報の値６１をＲＡＭ１６０３またはＨＤＤ１６０４に一時的に格納する。また、圧縮情報７０８から符号化された位置情報６２を圧縮情報分離プログラム２０１に従い分離し、分離した位置情報６２をロードされた位置情報復号プログラムに従い復号して、復号された位置情報６２をＲＡＭ１６０３またはＨＤＤ１６０４に一時的に格納する。同様に、圧縮情報７０８から符号化された対応情報７０３を分離し、分離した対応情報７０３をロードされた対応情報復号プログラムに従い復号して、復号された対応情報７０３をＲＡＭ１６０３またはＨＤＤ１６０４に一時的に格納する。次に、復号された位置情報６２を、ロードされた位置情報並替えプログラムに従い、復号された対応情報７０３に基づいて並替えて、並替え後の位置情報６２をＲＡＭ１６０３またはＨＤＤ１６０４に一時的に格納する。最後に、ロードされたテーブル形成プログラムに従い、要素情報の値６１と（復号および並替え処理後の）位置情報６２とを用いてテーブル６０１を形成して、形成したテーブル６０１をＲＡＭ１６０３またはＨＤＤ１６０４に格納する。【０１０１】
このテーブル６０１は、付加情報による検索実行時の補助情報として活用される。または、インターフェース１６０５により接続された外部記録デバイスの記録媒体を介して、あるいは、通信デバイス１６０６で接続された通信ネットワーク１６１４を通して、あるいはＦＤ駆動部１６０９によりＦＤ１６１０を介して、あるいはＣＤ駆動部１６１１によりＣＤ１６１２を介して、他の検索機能を持つ機器に提供されるとしてもよい。【０１０２】
また、前述の第２の実施形態において、情報テーブル符号化時には、ＲＯＭ１６０２、ＲＡＭ１６０３、またはＨＤＤ１６０４に格納された、テーブル分離部９０１に対応のテーブル分離プログラム、位置情報並替部９０３および対応情報抽出部９０４に対応の位置情報並替えおよび対応情報抽出プログラム、対応情報符号化部９０５に対応の対応情報符号化プログラム、位置情報符号化部９０２に対応の位置情報符号化プログラム、圧縮情報形成部９０６に対応の圧縮情報形成プログラムがＣＰＵ１６０１により、ＣＰＵ１６０１の所定記憶領域にロードされる。ＣＰＵ１６０１は該所定記憶領域から各プログラムの命令を読出し、解釈し実行することで以下の動作が実現される。この時、位置情報６２と要素情報の値６１とからなるテーブル６０（または６０１）は、予め生成されてＲＡＭ１６０３またはＨＤＤ１６０４に格納されている。符号化規則データ７０９はＣＰＵ１６０１が参照可能な情報としてＲＯＭ１６０２に予め格納される。【０１０３】
ＣＰＵ１６０１は、ロードされているテーブル分離プログラムに従い、ＲＡＭ１６０３またはＨＤＤ１６０４に既に格納されているテーブル６０（または６０１）から位置情報６２を分離する（読出す）。次に、分離した位置情報６２をロードされた位置情報並替えおよび対応情報抽出プログラムに従い並替えおよび対応情報７０３を抽出（生成）して、並替え後の位置情報６２と抽出した対応情報７０３をＲＡＭ１６０３またはＨＤＤ１６０４に一時的に格納する。また、ロードされているテーブル分離プログラムに従い、ＲＡＭ１６０３またはＨＤＤ１６０４に既に格納されているテーブル６０（または６０１）から要素情報の値６１を分離（読出）して、分離した要素情報の値６１をＲＡＭ１６０３またはＨＤＤ１６０４に一時的に格納する。並替え後の位置情報６２は、ロードされた位置情報符号化プログラムに従い符号化して、符号化された位置情報６２をＲＡＭ１６０３またはＨＤＤ１６０４に一時的に格納する。同様に、対応情報７０３は、ロードされた対応情報符号化プログラムに従い符号化して、符号化された対応情報７０３をＲＡＭ１６０３またはＨＤＤ１６０４に一時的に格納する。最後に、ロードされた圧縮情報形成プログラムに従い、符号化された位置情報６２および対応情報７０３、ならびに要素情報の値６１を用いて圧縮情報７０８を形成して、形成した圧縮情報７０８をＲＡＭ１６０３またはＨＤＤ１６０４に格納する。【０１０４】
この圧縮情報７０８は、テーブル形式の情報の効率的な蓄積および伝送のために利用され、インターフェース１６０５により接続された外部記録デバイスの記録媒体を介して、あるいは、通信デバイス１６０６で接続された通信ネットワーク１６１４を通して、あるいはＦＤ駆動部１６０９によりＦＤ１６１０を介して、あるいはＣＤ駆動部１６１１によりＣＤ１６１２を介して、他の情報テーブル復号機能を持つ機器に提供される。【０１０５】
前述の第２の実施形態における情報テーブル復号時のＣＰＵ１６０１の動作は、既に説明した第１の実施形態における情報テーブル復号時における動作と同じであるため、説明を省略する。【０１０６】
上述の情報テーブル符号化処理は、符号化するテーブル６０を決定して以降は、あるいは復号処理は復号装置が圧縮情報７０８を受取って以降は、それぞれ、基本的にユーザからの何らの指示または情報の入力がなくても自動で実行される。但し、これに限らず、例えば、図１６の装置において、符号化／復号の指示を入力部１６０７を通してユーザが任意に与えたり、ＣＰＵ１６０１は符号化／復号処理の実行中の動作状況を出力部１６０８を介してユーザに提示したり、といった動作を実行させることも可能である。【０１０７】
第３の実施形態では、情報管理を実行する各種プログラムが、図１６の装置内のＲＯＭ１６０２、ＲＡＭ１６０３、またはＨＤＤ１６０４に格納されているとしたが、これに限定されず、コンピュータ読取可能な外部の記録媒体に記録されて、プログラム実行時にインターフェース１６０５を通してメモリにロードするといった構成で実施することもできる。外部の記録媒体としては、図示のない磁気テープ、ＣＤ−ＲＯＭ／Ｒ／ＲＷ、ＤＶＤ−ＲＯＭ／ＲＡＭ／Ｒ／ＲＷ、ＭＯ（magneto-optic）、ＳＤ（Secure  Digital）メモリカード、ＦＤ（Flexible  Disk）などがある。また、通信ネットワーク１６１４を経由して伝送されたこれらプログラムを通信デバイス１６０６により受信してＲＯＭ１６０２、ＲＡＭ１６０３、またはＨＤＤ１６０４に格納されるとしてもよい。【０１０８】
第１〜第３の実施の形態では、検索用の補助情報とされるテーブル６０（または６０１）を圧縮符号化する際に、要素情報６１（テキスト情報）は辞書順に並替えて保持し、一方、対応する各葉Ｒの位置情報６２は木構造中での出現順（数値の大小順）に基づいて差分符号化すると共に、これら情報に対して、位置情報と並替え後の要素情報（または要素情報と並べ替え後の位置情報）との対応関係を示す対応情報７０３を符号化して付加した。これにより、差分符号化を用いることでテーブル６０に含まれる位置情報を効率的に符号化することができ、かつ要素情報６１は辞書順に並べられることで高い検索効率を得ることが可能となった。【０１０９】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて請求の範囲によって示され、請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【図１】
2006035813.tif 000002
【図２】
2006035813.tif 000003
【図３】
2006035813.tif 000004
【図４】
2006035813.tif 000005
【図５】
2006035813.tif 000006
【図６】
2006035813.tif 000007
【図７】
2006035813.tif 000008
【図８】
2006035813.tif 000009
【図９】
2006035813.tif 000010
【図１０】
2006035813.tif 000011
【図１１】
2006035813.tif 000012
【図１２】
2006035813.tif 000013
【図１３】
2006035813.tif 000014
【図１４】
2006035813.tif 000015
【図１５】
2006035813.tif 000016
【図１６】
2006035813.tif 000017
【図１７】
2006035813.tif 000018
【図１８】
2006035813.tif 000019
【図１９】
2006035813.tif 000020
【手続補正書】
【提出日】平成18年7月21日(2006.7.21)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【書類名】請求の範囲
【請求項１】要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される情報の符号化装置（１）であって、
所定種別の要素情報と、該所定種別の要素情報が付された前記葉の前記木構造における前記規定順序に従う位置を示す位置情報と含んだ複数の組を、前記規定順序に従い並んで有する情報群を受理する手段（１０７）と、
前記受理する手段により受理した前記情報群の前記複数の組から複数の前記要素情報を分離して、分離した前記複数の要素情報を前記所定種別の前記要素情報の検索に適した所定の順序に従い並替える並替え手段（１０１、１０３）と、
前記並替え手段による、前記規定順序から前記所定順序への並替えによる前記複数の要素情報の順番の変化に基づき、並替え後の前記複数の要素情報それぞれと、前記受理する手段により受理した前記情報群の中の該要素情報と同一組の前記位置情報との対応関係を示す対応情報を生成する対応情報生成手段（１０４、１０５）と、
前記受理する手段により受理した前記情報群の前記複数の組から複数の前記位置情報を分離して、分離した前記複数の位置情報を符号化する位置情報符号化手段（１０２）と、
前記位置情報符号化手段により符号化された前記複数の位置情報と、前記対応情報生成手段により生成された前記対応情報と、前記並替え手段による並替え後の前記複数の要素情報とを所定の形式に配置して前記情報群に対する圧縮情報を形成する圧縮情報形成手段（１０６）とを備える、符号化装置。
【請求項２】  前記位置情報符号化手段は、前記複数の位置情報それぞれを、
該位置情報と、当該位置情報が示す位置の前記規定順序に従う直前の位置を示す位置情報との差分に基づき符号化することを特徴とする、請求項１に記載の符号化装置。
【請求項３】  前記対応情報生成手段は、
前記対応関係を示す情報を符号化することにより前記対応情報を生成する対応情報符号化手段（１０５）を含む、請求項１に記載の符号化装置。
【請求項４】前記圧縮情報形成手段による前記圧縮情報の形成に先立って、前記要素情報は符号化されることを特徴とする、請求項１に記載の符号化装置。
【請求項５】  前記木構造からなる情報は映像データを検索するための情報であることを特徴とする、請求項１に記載の符号化装置。
【請求項６】要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される情報の符号化装置（１０）であって、
所定種別の要素情報と、該所定種別の要素情報が付された前記葉の前記木構造における前記規定順序に従う位置を示す位置情報と含んだ複数の組を、前記所定種別の前記要素情報の検索に適した所定順序に従い並んで有する情報群を受理する手段（９０７）と、
前記受理する手段により受理した前記情報群の前記複数の組から複数の前記要素情報を分離して出力する要素情報分離手段（９０１）と、
前記受理する手段により受理した前記情報群の前記複数の組から複数の前記位置情報を分離して、分離した前記複数の位置情報を、前記規定順序に従い並替える位置情報並替手段（９０３）と、
前記位置情報並替手段の並替えによる前記複数の位置情報の順番の変化に基づき、並替え後の前記複数の位置情報それぞれと、前記受理する手段により受理した前記情報群の中の該位置情報と同一組の前記要素情報との対応関係を示す対応情報を生成する対応情報生成手段（９０４、９０５）と、
前記位置情報並替手段により並替えられた前記複数の位置情報を符号化する位置情報符号化手段（９０２）と、
前記位置情報符号化手段により符号化された前記複数の位置情報と、前記対応情報生成手段により生成された前記対応情報と、前記要素情報分離手段から出力された前記複数の要素情報とを所定の形式に配置して前記情報群に対する圧縮情報を形成する圧縮情報形成手段（９０６）とを備える、符号化装置。
【請求項７】  前記位置情報符号化手段は、前記複数の位置情報それぞれを、
該位置情報と、当該位置情報が示す位置の前記規定順序に従う直前の位置を示す位置情報との差分に基づき符号化することを特徴とする、請求項６に記載の符号化装置。
【請求項８】  前記対応情報生成手段は、
前記対応関係を示す情報を符号化することにより前記対応情報を生成する対応情報符号化手段（９０５）を含む、請求項６に記載の符号化装置。
【請求項９】前記圧縮情報形成手段による前記圧縮情報の形成に先立って、前記要素情報は符号化されることを特徴とする、請求項６に記載の符号化装置。
【請求項１０】  前記木構造からなる情報は映像データを検索するための情報であることを特徴とする、請求項６に記載の符号化装置。
【請求項１１】要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される情報の中の情報群が符号化された圧縮情報の復号装置（２）であって、
前記情報群は、前記木構造により構成される情報の中の所定種別の要素情報と、該所定種別の要素情報が付された前記葉の前記木構造における位置を示す位置情報とを含んだ複数の組を有し、
所定種別の前記要素情報の検索に適した所定順序で並んだ前記所定種別の複数の要素情報と、当該複数の要素情報が付された複数の葉の前記木構造における前記規定順序に従う位置を示す符号化された複数の位置情報と、前記所定順序で並んだ複数の要素情報それぞれと当該要素情報が付された前記葉の前記規定順序に従う位置を示す符号化された前記複数の位置情報との対応関係を示す対応情報と、を含んで形成された前記圧縮情報を受理する圧縮情報受理手段（２０７）と、
前記圧縮情報受理手段により受理した前記圧縮情報から、前記複数の要素情報と、符号化された前記複数の位置情報と、前記対応情報とを分離して出力する分離手段（２０１）と、
前記分離手段から出力された符号化された前記複数の位置情報を入力して、入力した前記複数の位置情報を復号する位置情報復号手段（２０２）と、
前記分離手段から出力された前記対応情報を入力して、入力した前記対応情報に基づき、前記位置情報復号手段により復号された前記複数の位置情報を前記所定順序に従い並替える並替え手段（２０４）と、
前記並替え手段による並替え後の前記複数の位置情報それぞれと、前記分離手段から入力した前記所定順序で並んだ前記複数の要素情報それぞれとが対応付けされた前記情報群を生成して出力する手段（２０５）を備える、復号装置。
【請求項１２】  前記木構造からなる情報は映像データを検索するための情報であることを特徴とする、請求項１１に記載の復号装置。
【請求項１３】要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される情報の符号化方法であって、
所定種別の要素情報と、該所定種別の要素情報が付された前記葉の前記木構造における前記規定順序に従う位置を示す位置情報と含んだ複数の組を、前記規定順序に従い並んで有する情報群を受理するステップ（Ｓ１０）と、
前記受理するステップにおいて受理した前記情報群の前記複数の組から複数の前記要素情報を分離して、分離した前記複数の要素情報を、前記所定種別の前記要素情報の検索に適した所定の順序に従い並替える並替えステップ（Ｓ１１、Ｓ１２）と、
前記並替えステップによる、前記規定順序から前記所定順序への並替えによる前記複数の要素情報の順番の変化に基づき、並替え後の前記複数の要素情報それぞれと、前記受理するステップにおいて受理した前記情報群の中の該要素情報と同一組の前記位置情報との対応関係を示す対応情報を生成する対応情報生成ステップ（Ｓ１３）と、
前記受理するステップにより受理した前記情報群の前記複数の組から複数の前記位置情報を分離して、分離した前記複数の位置情報を符号化する位置情報符号化ステップ（Ｓ１４）と、
前記位置情報符号化ステップにより符号化された前記複数の位置情報と、前記対応情報生成ステップにより生成された前記対応情報と、前記並替えステップによる並替え後の前記複数の要素情報とを所定の形式に配置して前記情報群に対する圧縮情報を形成する圧縮情報形成ステップ（Ｓ１６）とを備える、符号化方法。
【請求項１４】要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される情報の符号化方法であって、
所定種別の要素情報と、該所定種別の要素情報が付された前記葉の前記木構造における前記規定順序に従う位置を示す位置情報と含んだ複数の組を、前記所定種別の前記要素情報の検索に適した所定順序に従い並んで有する情報群を受理するステップと、
前記受理するステップにより受理した前記情報群の前記複数の組から複数の前記要素情報を分離して出力する要素情報分離ステップと、
前記受理するステップにより受理した前記情報群の前記複数の組から複数の前記位置情報を分離して、分離した前記複数の位置情報を、前記規定順序に従い並替える位置情報並替ステップと、
前記位置情報並替ステップの並替えによる前記複数の位置情報の順番の変化に基づき、並替え後の前記複数の位置情報それぞれと、前記受理するステップにより受理した前記情報群の中の該位置情報と同一組の前記要素情報との対応関係を示す対応情報を生成する対応情報生成ステップと、
前記位置情報並替ステップにより並替えられた前記複数の位置情報を符号化する位置情報符号化ステップと、
前記位置情報符号化ステップにより符号化された前記複数の位置情報と、前記対応情報生成ステップにより生成された前記対応情報と、前記要素情報分離ステップから出力された前記複数の要素情報とを所定の形式に配置して前記情報群に対する圧縮情報を形成する圧縮情報形成ステップとを備える、符号化方法。
【請求項１５】要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される情報の中の情報群が符号化された圧縮情報の復号方法であって、
前記情報群は、前記木構造により構成される情報の中の所定種別の要素情報と、該所定種別の要素情報が付された前記葉の前記木構造における位置を示す位置情報とを含んだ複数の組を有し、
所定種別の前記要素情報の検索に適した所定順序で並んだ前記所定種別の複数の要素情報と、当該複数の要素情報が付された複数の葉の前記木構造における前記規定順序に従う位置を示す符号化された複数の位置情報と、前記所定順序で並んだ複数の要素情報それぞれと当該要素情報が付された前記葉の前記規定順序に従う位置を示す符号化された前記複数の位置情報との対応関係を示す対応情報と、を含んで形成された前記圧縮情報を受理する圧縮情報受理ステップ（Ｓ２０）と、
前記圧縮情報受理ステップにより受理した前記圧縮情報から、前記複数の要素情報と、符号化された前記複数の位置情報と、前記対応情報とを分離して出力する分離ステップ（Ｓ２１）と、
前記分離ステップから出力された符号化された前記複数の位置情報を入力して、入力した前記複数の位置情報を復号する位置情報復号ステップ（Ｓ２２）と、
前記分離ステップにより出力された前記対応情報を入力して、入力した前記対応情報に基づき、前記位置情報復号ステップにより復号された前記複数の位置情報を前記所定順序に従い並替える並替えステップ（Ｓ２４）と、
前記並替えステップによる並替え後の前記複数の位置情報それぞれと、前記分離ステップから入力した前記所定順序で並んだ前記複数の要素情報それぞれとが対応付けされた前記情報群を生成して出力するステップ（Ｓ２５）を備える、復号方法。
【請求項１６】要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される情報の符号化方法を、コンピュータに実行させるためのプログラムであって、
前記符号化方法は、
前記木構造における所定種別の要素情報と、該所定種別の要素情報が付された前記葉の前記木構造における前記規定順序に従う位置を示す位置情報と含んだ複数の組を、前記規定順序に従い並んで有する情報群を受理するステップと、
前記受理するステップにおいて受理した前記情報群の前記複数の組から複数の前記要素情報を分離して、分離した前記複数の要素情報を、前記所定種別の前記要素情報の検索に適した所定の順序に従い並替える並替えステップと、
前記並替えステップによる、前記規定順序から前記所定順序への並替えによる前記複数の要素情報の順番の変化に基づき、並替え後の前記複数の要素情報それぞれと、前記受理するステップにおいて受理した前記情報群の中の該要素情報と同一組の前記位置情報との対応関係を示す対応情報を生成する対応情報生成ステップと、
前記受理するステップにより受理した前記情報群の前記複数の組から複数の前記位置情報を分離して、分離した前記複数の位置情報を符号化する位置情報符号化ステップと、
前記位置情報符号化ステップにより符号化された前記複数の位置情報と、前記対応情報生成ステップにより生成された前記対応情報と、前記並替えステップによる並替え後の前記複数の要素情報とを所定の形式に配置して前記情報群に対する圧縮情報を形成する圧縮情報形成ステップとを備える、符号化方法をコンピュータに実行させるためのプログラム。
【請求項１７】要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される情報の符号化方法を、コンピュータに実行させるためのプログラムであって、
前記符号化方法は、
所定種別の要素情報と、該所定種別の要素情報が付された前記葉の前記木構造における前記規定順序に従う位置を示す位置情報と含んだ複数の組を、前記所定種別の前記要素情報の検索に適した所定順序に従い並んで有する情報群を受理するステップと、
前記受理するステップにより受理した前記情報群の前記複数の組から複数の前記要素情報を分離して出力する要素情報分離ステップと、
前記受理するステップにより受理した前記情報群の前記複数の組から複数の前記位置情報を分離して、分離した前記複数の位置情報を、前記規定順序に従い並替える位置情報並替ステップと、
前記位置情報並替ステップの並替えによる前記複数の位置情報の順番の変化に基づき、並替え後の前記複数の位置情報それぞれと、前記受理するステップにより受理した前記情報群の中の該位置情報と同一組の前記要素情報との対応関係を示す対応情報を生成する対応情報生成ステップと、
前記位置情報並替ステップにより並替えられた前記複数の位置情報を符号化する位置情報符号化ステップと、
前記位置情報符号化ステップにより符号化された前記複数の位置情報と、前記対応情報生成ステップにより生成された前記対応情報と、前記要素情報分離ステップから出力された前記複数の要素情報とを所定の形式に配置して前記情報群に対する圧縮情報を形成する圧縮情報形成ステップとを備える、符号化方法をコンピュータに実行させるためのプログラム。
【請求項１８】要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される情報の中の情報群が符号化された圧縮情報の復号方法を、コンピュータに実行させるためのプログラムであって、
前記情報群は、前記木構造により構成される情報の中の所定種別の要素情報と、該所定種別の要素情報が付された前記葉の前記木構造における位置を示す位置情報とを含んだ複数の組を有し、
前記復号方法は、
所定種別の前記要素情報の検索に適した所定順序で並んだ前記所定種別の複数の要素情報と、当該複数の要素情報が付された複数の葉の前記木構造における前記規定順序に従う位置を示す符号化された複数の位置情報と、前記所定順序で並んだ複数の要素情報それぞれと当該要素情報が付された前記葉の前記規定順序に従う位置を示す符号化された前記複数の位置情報との対応関係を示す対応情報と、を含んで形成された前記圧縮情報を受理する圧縮情報受理ステップと、
前記圧縮情報受理ステップにより受理した前記圧縮情報から、前記複数の要素情報と、符号化された前記複数の位置情報と、前記対応情報とを分離して出力する分離ステップと、
前記分離ステップから出力された符号化された前記複数の位置情報を入力して、入力した前記複数の位置情報を復号する位置情報復号ステップと、
前記分離ステップにより出力された前記対応情報を入力して、入力した前記対応情報に基づき、前記位置情報復号ステップにより復号された前記複数の位置情報を前記所定順序に従い並替える並替えステップと、
前記並替えステップによる並替え後の前記複数の位置情報それぞれと、前記分離ステップから入力した前記所定順序で並んだ前記複数の要素情報それぞれとが対応付けされた前記情報群を生成して出力するステップを備える、復号方法をコンピュータに実行させるためのプログラム。
【請求項１９】要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される情報の符号化方法を、コンピュータに実行させるためのプログラムを記録した機械読取り可能な記録媒体であって、
前記符号化方法は、
所定種別の要素情報と、該所定種別の要素情報が付された前記葉の前記木構造における前記規定順序に従う位置を示す位置情報と含んだ複数の組を、前記規定順序に従い並んで有する情報群を受理するステップと、
前記受理するステップにおいて受理した前記情報群の前記複数の組から複数の前記要素情報を分離して、分離した前記複数の要素情報を、前記所定種別の前記要素情報の検索に適した所定の順序に従い並替える並替えステップと、
前記並替えステップによる、前記規定順序から前記所定順序への並替えによる前記複数の要素情報の順番の変化に基づき、並替え後の前記複数の要素情報それぞれと、前記受理するステップにおいて受理した前記情報群の中の該要素情報と同一組の前記位置情報との対応関係を示す対応情報を生成する対応情報生成ステップと、
前記受理するステップにより受理した前記情報群の前記複数の組から複数の前記位置情報を分離して、分離した前記複数の位置情報を符号化する位置情報符号化ステップと、
前記位置情報符号化ステップにより符号化された前記複数の位置情報と、前記対応情報生成ステップにより生成された前記対応情報と、前記並替えステップによる並替え後の前記複数の要素情報とを所定の形式に配置して前記情報群に対する圧縮情報を形成する圧縮情報形成ステップとを備える、符号化方法をコンピュータに実行させるためのプログラムを記録した機械読取り可能な記録媒体。
【請求項２０】要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される情報の符号化方法を、コンピュータに実行させるためのプログラムを記録した機械読取り可能な記録媒体であって、
前記符号化方法は、
所定種別の要素情報と、該所定種別の要素情報が付された前記葉の前記木構造における前記規定順序に従う位置を示す位置情報と含んだ複数の組を、前記所定種別の前記要素情報の検索に適した所定順序に従い並んで有する情報群を受理するステップと、
前記受理するステップにより受理した前記情報群の前記複数の組から複数の前記要素情報を分離して出力する要素情報分離ステップと、
前記受理するステップにより受理した前記情報群の前記複数の組から複数の前記位置情報を分離して、分離した前記複数の位置情報を、前記規定順序に従い並替える位置情報並替ステップと、
前記位置情報並替ステップの並替えによる前記複数の位置情報の順番の変化に基づき、並替え後の前記複数の位置情報それぞれと、前記受理するステップにより受理した前記情報群の中の該位置情報と同一組の前記要素情報との対応関係を示す対応情報を生成する対応情報生成ステップと、
前記位置情報並替ステップにより並替えられた前記複数の位置情報を符号化する位置情報符号化ステップと、
前記位置情報符号化ステップにより符号化された前記複数の位置情報と、前記対応情報生成ステップにより生成された前記対応情報と、前記要素情報分離ステップから出力された前記複数の要素情報とを所定の形式に配置して前記情報群に対する圧縮情報を形成する圧縮情報形成ステップとを備える、符号化方法をコンピュータに実行させるためのプログラムを記録した機械読取り可能な記録媒体。
【請求項２１】要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される情報の中の情報群が符号化された圧縮情報の復号方法を、コンピュータに実行させるためのプログラムを記録した機械読取り可能な記録媒体であって、
前記情報群は、前記木構造により構成される情報の中の所定種別の要素情報と、該所定種別の要素情報が付された前記葉の前記木構造における位置を示す位置情報とを含んだ複数の組を有し、
前記復号方法は、
所定種別の前記要素情報の検索に適した所定順序で並んだ前記所定種別の複数の要素情報と、当該複数の要素情報が付された複数の葉の前記木構造における前記規定順序に従う位置を示す符号化された複数の位置情報と、前記所定順序で並んだ複数の要素情報それぞれと当該要素情報が付された前記葉の前記規定順序に従う位置を示す符号化された前記複数の位置情報との対応関係を示す対応情報と、を含んで形成された前記圧縮情報を受理する圧縮情報受理ステップと、
前記圧縮情報受理ステップにより受理した前記圧縮情報から、前記複数の要素情報と、符号化された前記複数の位置情報と、前記対応情報とを分離して出力する分離ステップと、
前記分離ステップから出力された符号化された前記複数の位置情報を入力して、入力した前記複数の位置情報を復号する位置情報復号ステップと、
前記分離ステップにより出力された前記対応情報を入力して、入力した前記対応情報に基づき、前記位置情報復号ステップにより復号された前記複数の位置情報を前記所定順序に従い並替える並替えステップと、
前記並替えステップによる並替え後の前記複数の位置情報それぞれと、前記分離ステップから入力した前記所定順序で並んだ前記複数の要素情報それぞれとが対応付けされた前記情報群を生成して出力するステップを備える、復号方法をコンピュータに実行させるためのプログラムを記録した機械読取り可能な記録媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００５
【補正方法】変更
【補正の内容】
【０００５】
時の演算量は対数オーダに従うものとなり、辞書順でない場合に比較して検索効率に優れることが知られている。
［００１８］
図１９のテーブル中の要素情報の値を辞書順に並替えた場合、対応する位置情報の値も同じく並替えられるため、位置情報の値の大きさ順に従う並び関係が崩れてしまう。そのため、要素情報の値を辞書順に並替える場合には、対応の位置情報に対して特許文献１に示された差分符号化方式を適用することはできなかった。
［００１９］
それゆえにこの発明の目的は、木構造により構成される情報について、検索効率に優れる情報を得ることのできる符号化装置、符号化方法、プログラムおよび該プログラムを記録した機械読取り可能な記録媒体、ならびにこの符号化された情報を復号する復号装置、復号方法、プログラムおよび該プログラムを記録した機械読取り可能な記録媒体を提供することである。
［００２０］
この発明の他の目的は、木構造により構成される情報について、符号化効率に優れる情報を得ることのできる符号化装置、符号化方法、プログラムおよび該プログラムを記録した機械読取り可能な記録媒体、ならびにこの符号化された情報を復号する復号装置、復号方法、プログラムおよび該プログラムを記録した機械読取り可能な記録媒体を提供することである。
［００２１］
【課題を解決するための手段】
［００２２］
この発明のある局面に従うと、要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される情報の符号化をする。
［００２３］
まず、所定種別の要素情報と、該所定種別の要素情報が付された葉の木構造における規定順序に従う位置を示す位置情報を含んだ複数の組を、規定順序に従う順番に並んで有する情報群が受理される。そして、並替え部は、受理した情報群の複数の組それぞれから複数の要素情報を分離して、分離した複
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
数の要素情報を所定の順序に従い並替える。また対応情報生成部は、対応情報を生成する。対応情報は、規定順序から所定順序への並替えによる複数の要素情報の順番の変化に基づき、並替え後の複数の要素情報それぞれと、受理している情報群の中の該要素情報と同一組の位置情報との対応関係を示す。
［００２４］
位置情報符号化部は、受理している情報群の複数の組それぞれから位置情報を分離して分離した複数の位置情報を符号化する。そして、圧縮情報形成部は、符号化された位置情報と、生成された対応情報と、並替え後の要素情報とを所定の形式に配置して情報群に対する圧縮情報を形成する。
［００２５］
前述の所定順序は、所定種別の要素情報の検索に適した順序を指す。
この発明の他の局面に従うと、要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される情報の符号化をする。
［００２６］
まず、所定種別の要素情報と、当該所定種別の要素情報が付された葉の木構造における規定順序に従う位置を指示する位置情報と含んだ複数の組を、所定順序に並んで有する情報群を、受理部により受理する。
［００２７］
要素情報分離部は、受理した情報群の複数の組それぞれから要素情報を分離して出力する。また、位置情報並替部は、受理した情報群の複数の組それぞれから位置情報を分離して、分離した複数の位置情報を、規定順序に従い並替える。また、対応情報生成部は、対応情報を生成する。対応情報は、並替えによる複数の位置情報の順番の変化に基づく、並替え後の複数の位置情報それぞれと、受理している情報群の中の該位置情報と同一組の要素情報との対応関係を示す。
［００２８］
位置情報符号化部は、並替えされた複数の位置情報を符号化する。そして、圧縮情報形成部は、符号化された位置情報と、生成された対応情報と、分離された要素情報とを所定の形式に配置して情報群に対する圧縮情報を生成する。
［００２９］
前述の所定順序は、所定種別の要素情報の検索に適した順序を指す。
この発明のさらに他の局面に従うと、要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成される圧縮情報を復号する。圧縮情報は、木構造により構成される情報の中の所定種別の要素情報と、該所定種別の要素情報が付された葉の木構造における位置を示す位置情報とを含んだ複数の組を有する情報群が符号化された情報を指す。
［００３０］
まず、受理部により圧縮情報が受理される。圧縮情報は、所定順序で並んだ複数の要素情報と、該複数の要素情報が付された複数の葉の木構造における規定順序に従う位置を示す符号化された位置情報と、複数の
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０００７
【補正方法】変更
【補正の内容】
【０００７】
位置情報のうち所定順序で並んだ複数の要素情報それぞれと対応する位置情報を特定するための対応情報とを含んで生成された情報を指す。分離部は、受理した圧縮情報から複数の要素情報と、複数の符号化された位置情報と、対応情報とをそれぞれ分離して出力する。
［００３１］
位置情報復号部は、分離された複数の符号化された位置情報を復号する。並替え部は、復号された複数の位置情報を、分離された対応情報に従って所定順序に従い並替える。
［００３２］
並替え後の複数の位置情報それぞれと、分離されている所定順序で並んだ複数の要素情報それぞれとが対応付けされた情報が出力される。
［００３３］
前述の所定順序は、所定種別の要素情報の検索に適した順序を指す。
【発明の効果】
［００３４］
本発明では、木構造の情報の符号化によって生成される圧縮情報には、木構造の複数の葉に付された所定種別の複数の要素情報が含まれる。この複数の要素情報は、所定種別の要素情報の検索に適した順番に従い並べられている。したがって、圧縮情報の検索に際しては高い検索効率を得ることが可能となる。
［００３５］
また、位置情報の符号化は差分符号化を用いることで情報群の位置情報を効率的に符号化できる。これにより、圧縮情報について、復号により元の情報群を取得するのに必要な情報の種類と情報の量を有しながらも情報量を少なくできる。このことから、情報群を符号化して生成された圧縮情報を伝送する場合には高い伝送効率を得ることができる。また圧縮情報を記憶媒体に格納する場合には必要なメモリ容量を少なくできる。
【図面の簡単な説明】
［００３６］
［図１］本発明の第１の実施形態にかかる情報管理装置のうち、情報テーブル符号化装置の概略機能ブロック図である。
［図２］本発明の第１の実施形態にかかる情報管理装置のうち、情報テーブル復号装置の概略機能ブロック図である。
［図３］木構造中の出現順に従い情報を格納するテーブルの一例を示す図である。
［図４］テーブルの具体的なデータ構造の一例を示す図である。
【国際調査報告】
2006035813.tif 000021
2006035813.tif 000022