[go: up one dir, main page]

WO2006035813A1 - 符号化装置、符号化方法、復号装置、復号方法、プログラムおよび該プログラムを記録した機械読取り可能な記録媒体 - Google Patents

符号化装置、符号化方法、復号装置、復号方法、プログラムおよび該プログラムを記録した機械読取り可能な記録媒体 Download PDF

Info

Publication number
WO2006035813A1
WO2006035813A1 PCT/JP2005/017844 JP2005017844W WO2006035813A1 WO 2006035813 A1 WO2006035813 A1 WO 2006035813A1 JP 2005017844 W JP2005017844 W JP 2005017844W WO 2006035813 A1 WO2006035813 A1 WO 2006035813A1
Authority
WO
WIPO (PCT)
Prior art keywords
information
position information
predetermined
correspondence
order
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/JP2005/017844
Other languages
English (en)
French (fr)
Inventor
Shuichi Watanabe
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Sharp Corp
Original Assignee
Sharp Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Sharp Corp filed Critical Sharp Corp
Priority to US11/664,251 priority Critical patent/US7617237B2/en
Priority to JP2006537771A priority patent/JPWO2006035813A1/ja
Priority to EP05787590A priority patent/EP1811403A4/en
Publication of WO2006035813A1 publication Critical patent/WO2006035813A1/ja
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/70—Information retrieval; Database structures therefor; File system structures therefor of video data
    • G06F16/71—Indexing; Data structures therefor; Storage structures
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/70—Information retrieval; Database structures therefor; File system structures therefor of video data
    • G06F16/78—Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
    • Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10S707/00—Data processing: database and file management or data structures
    • Y10S707/99941—Database schema or data structure
    • Y10S707/99943—Generating database or data structure, e.g. via user interface

Definitions

  • Encoding apparatus Encoding apparatus, encoding method, decoding apparatus, decoding method, program, and machine-readable recording medium recording the program
  • the present invention relates to an encoding apparatus, encoding method, decoding apparatus, and decoding method for information having a tree structure.
  • the present invention relates to a program and a machine-readable recording medium on which the program is recorded, and in particular, an encoding process in which element information corresponding to a plurality of leaves of a tree structure is associated with position information indicating a position in the tree structure of the leaves
  • the present invention relates to a device, an encoding method, a decoding device, a decoding method, a program, and a machine-readable recording medium on which the program is recorded.
  • FIG. 17 shows an example of additional information describing the content of video presented by certain video data, which is applied in the conventional and the embodiments of the present invention.
  • the additional information is represented by a tree structure corresponding to the logical structure of the video.
  • moving image content such as video is composed of one or more scenes, and each scene is composed of one or more sub-scenes (or shots), or even another scene.
  • the description when adding search information indicating the characteristics of a sub-scene to each sub-scene The description method uses a representation method consisting of a tree structure as shown in Fig. 17 in order to express the hierarchy described above.
  • the entire video consists of two scenes, each consisting of two sub-scenes and one sub-scene.
  • related information related to the sub-scene here, sub-scene time information (start time / length), title, and performers appearing in the sub-scene are described.
  • the entire video data corresponds to the root (root node) RN
  • the node representing the element type such as scene, sub-scene, time information, title, and performer corresponds to the node N.
  • the scene hierarchy corresponds to the first branch destination as seen from the root RN, so it corresponds to section N in the first hierarchy.
  • the sub-scene hierarchy corresponds to section N in the second hierarchy.
  • the time information, title, and data representing the performers, which are related information of each sub-scene correspond to the leaf L of the tree structure.
  • Position information is assigned to each node N (root RN or leaf L) in the order of appearance by scanning the tree from the upper hierarchy to the lower hierarchy, and scanning the same hierarchy from left to right.
  • N root RN or leaf L
  • the position information of the first layer is “1”.
  • the sub-scene to which the element “Akira ABE” belongs is the first section from the left in the section N hanging from the scene “1” corresponding to the node N in the next higher hierarchy. For this reason, the position (order of appearance) in the second hierarchy is “1”.
  • the element “Akira ABEJ leaf L is a performer, hanging from sub-scene [1]!” Is the first clause N from the left in clause N. For this reason, the position (order of appearance) in the element of 'performer' in the third hierarchy is “1”. Therefore, in this case, the position information of the element “Akira ABE” is (1, 1, 1) including all the first to third hierarchies constituting the tree. In this format, the position information of all leaves L can be expressed uniquely.
  • Fig. 17 is an example of extremely simple additional information.
  • the actual element type is not limited to this, and the more complex the video, the more complicated the tree structure. Big. For this reason, additional information is often handled in a divided form, and only partial information necessary for use is obtained and used.
  • FIG. 18 shows an example in which the tree structure of the additional information in FIG. 17 is divided into easy-to-handle forms (sub-scene units). Each divided tree is called a “sub-tree” or “fragment”. Further, a table as shown in FIG. 19 is prepared as auxiliary information in order to perform a search by “performer” as described above. The table in FIG. 19 stores the values of all element information (performers) in the tree structure and fragment information indicating which subtree (fragment) the element information belongs to corresponding to each element information. And speak.
  • a video search using the additional information is performed as follows.
  • the system first transmits the table shown in Fig. 19 to the user upon request.
  • User accepts the tape Luka et al. Search for a search that matches the search condition “Wataru WADA” and read the corresponding fragment information.
  • the data of the fragment (“fragment 1”) indicated by the read fragment information is requested. Since the system transmits “Fragment 1” data to the user upon request, the user accepts the “Fragment 1” data and uses the received “Fragment 1” data.
  • the reproduction of the sub-scene is performed with reference to “time information” in the obtained fragment data.
  • auxiliary information shown in Fig. 19 include the TV Anytime Phase 1 Part 3-2 standard.
  • FIG. 18 and FIG. 19 information for indicating individual fragments is provided separately from the additional information in FIG. 17, but these can be replaced with the position information included in the additional information in FIG. Togashi.
  • the table in FIG. 19 is always transmitted regardless of whether or not it is actually used.
  • Patent Document 1 discloses a differential code of position information of consecutive values in order of size as a method of encoding a plurality of pieces of position information at a high compression rate. The method of conversion is shown.
  • This differential encoding method does not describe the position information of a leaf L (or a node N) with a tree structure as it is.
  • the position information is encoded using only the displacement (difference) from the position information of the leaf L (or node N). This brings about an effect that the code can be efficiently coded with a smaller number of bits.
  • Patent Document 1 Japanese Patent Laid-Open No. 2003-092757
  • the search efficiency is increased.
  • the order of the appearance order (position information value order) in the additional information (tree structure) is changed to the lexicographic ordering order.
  • the information group in the text format searches the desired information by arranging the information in dictionary order.
  • the amount of computation at the time follows a logarithmic order, and it is known that the search efficiency is superior compared to the case of not using the dictionary order.
  • an object of the present invention is to provide an encoding device, an encoding method, a program, and a machine-readable recording of the program, which can obtain information excellent in search efficiency for information configured by a tree structure. And a decoding device, a decoding method and a program for decoding the encoded information, and a machine-readable recording medium on which the program is recorded.
  • Another object of the present invention is to provide an encoding device, an encoding method, a program, and a machine reading recording the program, which can obtain information excellent in encoding efficiency for information configured by a tree structure. It is an object to provide a possible recording medium, a decoding device that decodes the encoded information, a decoding method, a program, and a machine-readable recording medium that records the program.
  • Another object of the present invention is to provide an encoding device, an encoding method, a program, and a machine reading recording the program, which can obtain information excellent in encoding efficiency for information configured by a tree structure. It is an object to provide a possible recording medium, a decoding device that decodes the encoded information, a decoding method, a program, and a machine-readable recording medium that records the program.
  • information configured by a tree structure having a prescribed order relationship is encoded between a plurality of leaves to which element information is attached.
  • a plurality of sets including element information of a predetermined type and position information indicating a position according to a specified order in the tree structure of a leaf to which the element information of the predetermined type is attached are arranged in order according to the specified order.
  • the information group possessed by is received by the receiving unit.
  • the rearrangement unit separates the plurality of element information from each of the plurality of sets of received information groups, and separates the separated information.
  • the number of pieces of element information are rearranged according to a predetermined order.
  • the correspondence information generation unit generates correspondence information. Corresponding information is based on the change in the order of multiple element information by rearrangement from the specified order to the specified order. The correspondence with the position information of the pair is shown.
  • the position information encoding unit receives and encodes a plurality of pieces of position information obtained by separating the position information from each of a plurality of sets of information groups. Then, the predetermined information forming unit forms predetermined information including the encoded position information, the generated correspondence information, and the rearranged element information.
  • the above-described predetermined order indicates an order suitable for searching for predetermined types of element information.
  • information composed of a tree structure having a prescribed order relationship is encoded between a plurality of leaves to which element information is attached.
  • a plurality of sets including element information of a predetermined type and position information indicating a position in a prescribed order in a leaf tree structure to which the element information of the predetermined type is attached are arranged in a predetermined order.
  • the information group is received by the receiving unit.
  • the element information separation unit separates and outputs element information from each of a plurality of sets of received information groups. Further, the position information rearrangement unit separates the position information from each of the plurality of sets of received information groups, and rearranges the plurality of separated position information according to a prescribed order. Further, the correspondence information generation unit generates correspondence information. Correspondence information includes each of a plurality of rearranged position information based on a change in the order of a plurality of position information due to rearrangement, and element information of the same set as the position information in the received information group. The correspondence is shown.
  • the position information encoding unit encodes the plurality of rearranged position information. Then, the predetermined information forming unit generates predetermined information including the encoded position information, the generated correspondence information, and the separated element information.
  • the aforementioned predetermined order indicates an order suitable for searching for predetermined types of element information.
  • encoded information constituted by a tree structure having a prescribed order relationship between a plurality of leaves to which element information is attached is decoded.
  • the receiving unit receives the predetermined information generated including the plurality of pieces of element information arranged in a predetermined order in the position information and the corresponding information for specifying the corresponding position information.
  • the separating unit separates and outputs a plurality of element information, a plurality of encoded position information, and correspondence information from the received predetermined information.
  • the position information decoding unit decodes the plurality of separated encoded position information.
  • the rearrangement unit rearranges the decoded plurality of pieces of position information according to a predetermined order according to the separated correspondence information.
  • Information is output in which each of the plurality of rearranged position information and each of the plurality of pieces of element information separated in a predetermined order are associated with each other.
  • the aforementioned predetermined order indicates an order suitable for searching for predetermined types of element information.
  • the predetermined information generated by the sign of the tree structure information includes a plurality of pieces of element information of a predetermined type attached to a plurality of leaves of the tree structure.
  • the plurality of pieces of element information are arranged in an order suitable for searching for predetermined types of element information. Therefore, it is possible to obtain high search efficiency when searching for predetermined information.
  • the position information can be encoded efficiently by using differential encoding. Thereby, it is possible to reduce the amount of information for the predetermined information while having the type of information and the amount of information necessary for obtaining the original information group by decoding. For this reason, when transmitting predetermined information generated by encoding an information group, transmission efficiency can be improved. In addition, when storing predetermined information in a storage medium, the required memory capacity can be reduced.
  • FIG. 1 is a schematic functional block diagram of an information table encoding device among the information management devices related to the first embodiment of the present invention.
  • FIG. 2 is a schematic functional block diagram of an information table decoding apparatus in the information management apparatus according to the first embodiment of the present invention.
  • FIG. 3 is a diagram illustrating an example of a table that stores information in the order of appearance in a tree structure.
  • FIG. 4 is a diagram showing an example of a specific data structure of a table.
  • FIG. 5 is a diagram showing another example of a specific data structure of a table.
  • FIG. 6 is a flowchart showing an information table encoding method in the information management method according to the first embodiment of the present invention.
  • FIG. 8 is a diagram showing a process of extracting correspondence information in the first embodiment.
  • FIG. 10 is a diagram illustrating a code string of position information subjected to differential encoding together with position information.
  • FIG. 12 is a flowchart showing an information table decoding method in the information management method according to the first embodiment of the present invention.
  • FIG. 13 is a schematic functional block diagram of an information table encoding device among the information management devices related to the second embodiment of the present invention.
  • FIG. 14 is a diagram illustrating an example of a process of extracting correspondence information in the second embodiment.
  • FIG. 15 is a diagram showing another example of the process of extracting correspondence information in the second embodiment.
  • FIG. 16 is a hardware configuration diagram of an information management apparatus that works on the first and second embodiments.
  • FIG. 17 is a diagram showing an example of additional information of a video such as a tree structure applied to the conventional and embodiment of the present invention.
  • FIG. 18 is a diagram showing a partial tree obtained by dividing the tree structure of FIG.
  • FIG. 19 is a diagram showing an example of information in a conventional table format.
  • a table that is referred to as auxiliary information for search or information stored in the table is encoded with respect to the information having the tree structure power.
  • the table or information is compressed.
  • this is referred to as compression encoding.
  • This table stores a plurality of records including element information attached to each of a plurality of leaves L in the tree structure and position information indicating positions in the tree structure of the leaves L according to the above-mentioned prescribed order.
  • the compression code a plurality of element information (text information indicating the names of performers) of a plurality of records in the table are arranged and held in the dictionary order.
  • each piece of position information of a plurality of records in the table is encoded based on the difference from the position information of the leaf L that is positioned (appears) immediately before in accordance with the above-mentioned prescribed order with respect to the leaf L of the position information. Then, information indicating the correspondence between each of the plurality of pieces of element information and the position information is generated and encoded. These pieces of information are formed into one piece of information arranged in a predetermined format. The formed information is obtained as the auxiliary information for search described above.
  • the element information managed in the table is not limited to the force used as data indicating the “performer” attached to the leaf L in the lowest layer in FIG. Applicable to leaf L at any position, or any node N included in the tree structure of Fig. 17 is regarded as provisional element information given as a set of element information connected below it.
  • the method of the present invention can also be applied.
  • the information managed in the table record is a set of element information (actually a set of element information) corresponding to any node N in the tree structure and its position information.
  • An information management apparatus includes an information table encoding apparatus and an information table decoding apparatus.
  • FIG. 1 is a functional block diagram showing a schematic configuration of an information table encoding device 1 among the information management devices that are relevant to the first embodiment of the present invention.
  • the information table encoding device 1 includes a table separating unit 101 having a receiving unit 107, a position information encoding unit 102, an element information rearranging unit 103 having a corresponding information extracting unit 104 therein, a corresponding information encoding unit 105, and a compression Affection An information forming unit 106 is provided.
  • FIG. 2 is a functional block diagram showing a schematic configuration of the information table decoding device 2 in the information management device according to the first embodiment of the present invention.
  • the information table decoding apparatus 2 includes a compressed information separating unit 201 having a receiving unit 207, a position information decoding unit 202 having a table 707, a correspondence information decoding unit 203, a position information rearranging unit 204, and a table forming unit 205.
  • the operation of the information management apparatus (information table encoding apparatus 1 and information table decoding apparatus 2) according to the present embodiment will be described using the additional information of the video shown in FIG. 17 as an example.
  • the video additional information is represented by a tree structure corresponding to the logical structure of the video.
  • the numbers “1”, “2”, and “3” attached to the type names “scene”, “sub-scene”, and “performer” of each section N in FIG. 17 indicate the position in the tree structure of the section N. It is attached as information for uniquely identifying.
  • the additional information of the actual video is not limited to this both in structure and content.
  • the root node RN the top node of the tree
  • each node N that represents a scene, or a leaf L that represents the scene title is tracked, or a sub-scene is subdivided into sub-scenes. It can be divided into scenes to increase or decrease the number of tree hierarchies.
  • the types of elements included in the additional information are not limited to those shown in FIG.
  • the root node RN represents all programs (programs) broadcast on one channel. Each represents a program, and each node N in the second layer represents a scene included in the program.
  • the table 60 in FIG. 3 includes a plurality of records. Each record stores a set in which the value 61 of the same type of element information “performer” extracted from the attached information of FIG. 17 and the position information 62 of leaf L corresponding to the value 61 of the element information are stored. ing.
  • the additional information tree of FIG. 17 is scanned in order of strength, and the extracted similar element information “performers” are arranged as they appear in the tree structure. That is, element information values 61 that appear when the tree structure is scanned from left to right are stored in order from top to bottom in the order of appearance.
  • the position information 62 is indicated as (scene #, sub-scene #, performer #) by a combination of positions in the first to third layers, for example, in the table 60, the element information value 61 is “Akir”
  • the position information 62 of “a ABE” is indicated as the value (1, 1, 1)
  • the position information 62 of the element information 61 is indicated as the value (1, 1, 3).
  • the value of the left side force of the tree is given to the node N in the same hierarchy, so the value of the leftmost element information 62 indicates the minimum value (1, 1, 1)
  • the rightmost element information A value of 62 indicates the maximum value (2, 1, 1).
  • the table 60 shown in FIG. 3 is an input to the information table encoding device 1. That is, in the present embodiment, it is assumed that the value of the same kind of element has already been selected and extracted from the element information included in the additional information that is the tree structure power, and the value 61 of the element information and the corresponding position are extracted. A process related to the sign 62 of the information 62 will be described.
  • the information table encoding device 1 selects the same type of element information from the tree structure information to form a table for each element type, and also encodes the information indicating the element type together with the value of the element information 61 In addition to the code string of the position information 62, it is also possible to create a function for forming compressed information.
  • the information table decoding device 2 is used as a functional unit that decodes each of the element type information, the element information value 61, and the position information 62 to form a table for each element type. It is also possible that the decoding device has.
  • the sign target table here refers to a data structure in which element information and position information are associated one-to-one, and actually, a structure as shown in FIG. 4 or FIG. Points to the data.
  • the tables 63 and 64 in FIG. 4 have groups in which element information values and corresponding position information are stored in pairs for each type of element information.
  • position information position information A1 corresponding to element information (value Al, value A2, ..., value Bl, value B2, ...) , Position information A2, ..., position information B1, position information B2, ...), and the value of element information and position information are arranged alternately.
  • the corresponding position information may be arranged continuously.
  • Tables 65 and 66 in Fig. 5 are stored in another data structure in which the value of the element information is separated from the position information. Therefore, for each type of element information, there is a data structure in which reference information for referencing the value of element information stored in another data structure is stored in pairs with the position information of the value of the element information.
  • Table 65 in Fig. 5 (A) The reference information and the corresponding position information are paired, and the reference information and the position information are alternately arranged.
  • the table 66 in FIG. 5 (B) has a structure in which all the reference information to the element information is continuously arranged and then all corresponding position information is continuously arranged.
  • a plurality of pieces of position information as shown in Fig. 4 (B) or Fig. 5 (B) are continuously arranged. If the structure is desired, but the amount of code used for the element information value or the reference information to the element information value is known, the reference information and position as shown in Fig. 4 (A) or Fig. 5 (A). Even in a data structure in which information is alternately arranged, it is possible to perform differential signing of position information. 4 and 5 show an example of the data structure in which the element information value (or reference information to the element information value) is placed first, and the corresponding position information is placed after that, the position information is placed first. Then, a data structure in which a corresponding element information value (or reference information to the element information value) is arranged may be used.
  • the table separation unit 101 extracts the table 60 of FIG. 3 obtained in advance by extracting the same kind of element information included in the information having the tree structure power (actually shown in FIG. 4 or FIG. 5).
  • the data having such data structure power is received by the receiving unit 107 (step S (hereinafter simply referred to as S) 10), and the received information in the table 60 is separated into element information value 61 and position information 62. Output (Sl l).
  • the table 60 has not been generated in advance.
  • the additional information of the tree structure in FIG. 17 is received, the type of element information contained therein is analyzed, and the same type of element information is collected to generate the table 60 in FIG.
  • the table separation unit 101 may perform the processing up to this.
  • the position information encoding unit 102 inputs the position information 62 output from the table separation unit 101 and encodes it.
  • the plurality of pieces of position information 62 are arranged in order (in ascending order) in ascending order of power with the same numerical value as the appearance order in the tree structure. Efficiently sign using existing difference sign Can. In the following, the order from the smallest value to the largest is arranged in order of magnitude. A specific example of the sign y will be described later with reference to FIGS.
  • the element information rearrangement unit 103 receives the values 61 of the plurality of element information output from the table separation unit 101. Then, the input element information value 61 is arranged in the order of appearance in the tree structure shown in the table 60 of FIG. Reorder them so that they follow the lexicographic order (alphabetical order or Japanese syllabary order of Japanese syllabary) (S12).
  • FIG. 7 shows the table 601 after the information in the table 60 of FIG. 3 is rearranged by the rearrangement of the element information rearrangement unit 103.
  • a table 601 in FIG. 7 also indicates a table 601 output by the information table decoding device 2 described later.
  • the table actually used as auxiliary information at the time of retrieval is in a format in which element information values 61 are arranged in dictionary order as shown in FIG. That is, the table 60 in which the element information values 61 are arranged in the order of appearance of the tree structure shown in FIG. 3 corresponds to the intermediate data created for the sign key.
  • the correspondence information extraction unit 104 detects how the element information 61 is rearranged when the element information value 61 is rearranged as shown by the change from the table 60 in FIG. 3 to the table 601 in FIG. Information indicating the detection result is output as correspondence information 703 between element information and position information (S13). Since the processing for generating the correspondence information 703 is performed in synchronization with the rearrangement of the element information 61, the correspondence information extraction unit 104 has an internal configuration of the element information rearrangement unit 103.
  • FIG. 8 (A) shows an example of a process for obtaining the correspondence information 703 in FIG. 8 (B).
  • the element information value 61 before rearrangement in FIG. 3 is shown as element information 701
  • the element information value 61 after rearrangement in FIG. From the left side of the drawing, first, serial numbers from (1) to (6) are assigned to each element information 701 before rearrangement in the order of arrangement (step S (hereinafter simply referred to as S) 1) .
  • step S hereinafter simply referred to as S) 1
  • the element information 701 is rearranged in the dictionary order with the serial numbers attached (S2).
  • the serial numbers assigned to the rearranged element information 702 are in the order of (1), (4), (5), (2), (6), (3). Accordingly, the correspondence information 703 in FIG.
  • the response information 703 is not limited to that given by such a serial number, but may be any information that can indicate how the value 61 of the element information has been rearranged. Further, even with the correspondence information 703 based on the serial number, the method of attaching the correspondence information 703 and the method of extracting the correspondence information are not limited to those shown here, and can be implemented by various methods.
  • the position information encoding unit 102 receives the position information 62 output from the table separation unit 101, and encodes and outputs the input position information 62 (S14).
  • the correspondence information code unit 105 receives the correspondence information 703 extracted (generated) by the correspondence information extraction unit 104, encodes and outputs the inputted correspondence information 703 (S15).
  • the compressed information forming unit 106 is encoded with the encoded position information 62 output from each of the position information encoding unit 102, the correspondence information encoding unit 105, and the element information rearranging unit 103.
  • Corresponding information 703 and rearranged element information value 61 are input, and the input information is formed and output as compressed information 708 arranged in a predetermined format (S16).
  • Compressed information 708 (information obtained by compressing table 601 as auxiliary information at the time of search) output from one table encoding device is transmitted data amount or stored data during transmission or storage of table 601. Used to efficiently manage the table 601 by reducing the amount.
  • the compression code of the element information value 61 itself has not been described, but the position information 62 and the correspondence information 703 are encoded and the element information value 61 itself is encoded. Needless to say, it is effective to improve the efficiency during transmission and storage of table 601.
  • the element information shown in the table 601 is text information. Therefore, it is possible to perform compression using existing compression tools such as normal text code compression or Zip compression.
  • the element information values 61 after rearrangement are arranged in the dictionary order, it is possible to apply a process such as handling element information having the same value 61 together or a process such as differential encoding. It is.
  • the element information is coded by the value 61 and the number of element information having the value.
  • the table 601 in FIG. 7 has two element information with the value 61 “Rie RYUSHO”. Therefore, instead of recording “Rie RYUSHO” twice when forming compressed information, “Rie RYUSHO” is recorded once. Only record and record the number of information “2”, it takes to record table 601 Data volume can be reduced.
  • the method of signing the element information value 61 is not limited to this example. If the element information has an attribute other than text information, an encoding method that matches the attribute is used. I won't go into details here.
  • the compression information 708 is formed. By using this, the amount of compressed information 708 can be reduced.
  • FIGS. 3, 7, and 8 a specific example of encoding according to the present embodiment will be described with reference to FIGS. 9 and 10.
  • FIG. the encoding of the element information is not described here, and the position information 62 and the correspondence information 703 are encoded. Especially, the evaluation is performed based on the encoded code amount.
  • the position information 62 in the table 601 is encoded by the normal method without performing differential encoding.
  • the information in table 601 in FIG. 7 is auxiliary information at the time of search.
  • the position information 62 in the table 601 is encoded according to the normal method in order according to the order of the values indicated by the position information.
  • the position information 62 shown in FIG. 7 is represented with 3 layers.
  • the number of bits required to represent one layer is connected to one node N (parent node) in the layer one level above, and the number of bits that can branch there is the node N (child node) Depending on the number, the above 5 bits indicate the case where 2 to the 5th power, that is, up to 32 branches is possible. The actual video additional information requires a larger number of bits.
  • FIG. 9 shows data of meaning 705 indicated by the code 704 in a table format corresponding to each of the codes 704 used in the differential encoding of the position information 62 according to the present embodiment.
  • the FIG. 10 shows a code string 706 obtained by signing the position information 62 of FIG. 3 in a form that is compared with the position information 62 coded.
  • the position information code key unit 102 has coding rule data 709 indicating a coding rule of the position information 62.
  • the position information encoding unit 102 encodes the position information 62 with reference to the code rule data 709 according to the method shown in Patent Document 1.
  • the difference indicating at which hierarchy the position information 62 stored subsequently branches that is, the value of which hierarchy.
  • the subsequent position information 62 is encoded.
  • the position information 62 in FIG. 3 is encoded by the position information encoding unit 102, the following is performed.
  • the position information 62 stored at the head of the table 60 is encoded with 15 bits (5 bits per layer x 3 layers) (see the leftmost code string 706 in FIG. 10) and stored thereafter.
  • the five pieces of position information 62 thus encoded are encoded by a 3-bit code 704 and given as a code string 706 in FIG.
  • the compression information forming unit 106 adds the correspondence information 703 shown in FIG. 8B after being encoded by the correspondence information encoding unit 105 to the code string 706 in FIG.
  • the information (numerical value) corresponding to one position information 62 in the correspondence information 703 is encoded with 3 bits, which is the minimum number of bits that can represent the total value, because the total number of the position information 62 in the table 60 is 6. You can This total number value is included in the compressed information by the sign information of the position information 62 of the position information sign section 102.
  • 703 sign Since the code amount is 51 bits when encoding is performed, encoding the position information 62 using the difference information and the corresponding information 703 as in the present embodiment is a conventional method that does not use the difference code. Compared with the code amount, the compression rate can be increased.
  • the above numerical value is an example, but the compression effect becomes more prominent when the number of the position information 62 to be the target of the sign or the number of layers indicated by the position information 62 increases.
  • the code method of the correspondence information 703 described above is an example, and the present invention is not limited to this, and a more efficient code method may be applied. By compressing the correspondence information 703 by a more efficient encoding method, the compression effect becomes more prominent.
  • FIG. 11 schematically shows an example of a data structure of compressed information in which table format information is encoded in the present embodiment.
  • Fig. 11 (A) shows the data structure of the compressed information encoded with the data of Fig. 4 (B)
  • Fig. 11 (B) shows the data structure of the compressed information encoded with the data of Fig. 5 (B).
  • a plurality of consecutive position information is replaced with “position information code string” and “corresponding information code string”.
  • the element information values (value Al, value A2,..., Value Bl, value B2,. ) Is shown in FIG. 11 as it is in FIG. 4 (B) and FIG. 5 (B).
  • the compression information may be configured by applying differential encoding or the like and replacing the value 61 of a plurality of continuous element information with a “value code string”.
  • the element information value 61 (or reference information 67 to the element information value 61) is preceded, and the position information code string 68 and the corresponding information code string 69 are arranged after the data.
  • it may have a structure, it may have a data structure in which the position information code string 68 and the correspondence information code string 69 are arranged first, and the element information value 61 (or reference information 67 to the element information value 61) is arranged later.
  • Either of the position information code string 68 and the corresponding information code string 69 may be arranged first, and the element information value 61 (or element information) is placed between the position information code string 68 and the corresponding information code string 69. Reference information 67) to the value 61 may be placed between them.
  • the compression information separation unit 201 inputs the compression information 708 from the reception unit 207 (step S (hereinafter, simply abbreviated as S) 20).
  • the code string 81 of the information 703 and the element information value 61 (or the code string 82 of the element information value 61) are separated and output (S21).
  • the position information decoding unit 202 receives the code string 80 of the position information 62 output from the compressed information separation unit 201, and refers to the received code string 80 according to the procedure shown in Patent Document 1 and the table 70. Then, differential decoding is performed (S22). Differential decoding refers to decoding data encoded by the differential encoding method.
  • the differential decoding process will be described with reference to FIG. First, the first 15 bits of the code string 706 of the position information 62 are read and interpreted, and the position information (1, 1, 1) stored at the head of the table 60 is decoded. Next, the code 704 is sequentially read from the code string 706 of the subsequent position information 62 every three bits and interpreted. The code 704 “011” of the first 3-bit position information 62 is interpreted as a code indicating a branch (update) in the performer hierarchy with reference to the table 707 in FIG. Therefore, the position information (1, 1, 1) decoded at the top (first) is updated by one for the performer hierarchy value, and the second position information (1, 1, 2) is obtained.
  • next position information code 704 is also “0 11”
  • the third position information is (1, 1, 3).
  • the next position information code 704 to be read is “010”, and is interpreted as a code indicating a branch (update) in the sub-scene hierarchy with reference to the table 707 in FIG.
  • the lower-order node, in this example, the performer's node is an element attached under another sub-scene, so the value is re-counted from 1. Therefore, the value of the sub-scene hierarchy is updated by 1 and the value of the performer hierarchy is returned to 1, so the fourth location information is (1, 2, 1). In the same way, (1, 2, 2) and (2, 1, 1) are obtained as decoding results.
  • the position information code 704 “000” is read. Since this is interpreted as an end code for instructing the end of decoding with reference to the table 707 in FIG. 9, decoding ends in response to the end code being read.
  • the plurality of decoded position information 62 output from the position information decoding unit 202 is in the order of the value of the position information 62 (whether the head of the table 60 in FIG. Output in the order of stored values).
  • the correspondence information decoding unit 203 receives the code string 81 of the correspondence information 703 from the compressed information separation unit 201, decodes the received code string 81 into the correspondence information 703, and outputs it (S23).
  • the position information rearrangement unit 204 receives the correspondence information 703 that is the decoding result output from the correspondence information decoding unit 203 and the position information 62 that is the decoding result output from the position information decoding unit 202. Enter a value for. Then, the order of the values of the input position information 62 is rearranged based on the input correspondence information 703 (S24).
  • the position information rearrangement unit 204 arranges the decoded (input) position information 62 in the order indicated by the numerical values indicated in the decoded correspondence information 703.
  • the first decoded position information (1, 1, 1) is determined as the first position information 62 based on the first value “1” of the correspondence information 703 in FIG. 8B decoded. Is output.
  • the fourth decoded position information (1, 2, 1) is determined and output as the second position information 62.
  • the fifth decoded position information (1, 2, 2) is determined and output as the third position information 62.
  • the corresponding location information (1, 1, 2), (2, 1, 1), (1, 1, 3 ) is determined as the 4th, 5th, and 6th position information 62 and output.
  • the position information 62 is output in order.
  • the table forming unit 205 associates the element information value 61 output from the compression information separating unit 201 with the position information 62 output in the above order from the position information rearranging unit 204. As shown in FIG. 7, a table 601 in which element information values 61 are arranged in dictionary order is formed and output (S25).
  • the information table decoding device 2 decodes the information 708 of the table 60 compressed and encoded at the time of transmission or storage, and provides the decoded table 601 as auxiliary information at the time of search.
  • the information table decoding device 2 is mounted on a user information terminal having a search function based on additional information, and the compressed information received by the information terminal through the transmission path 7 08 (the auxiliary information and the search information).
  • the table 601 formed by decoding is such that the position information 62 is rearranged in the order corresponding to the magnitude information 61 and the element information 61, and the element information values 61 are arranged in the dictionary order.
  • the desired element information is searched using this table 601, the necessary subtree (fragment) is determined, and the corresponding fragment is obtained. This is because when the user performs a search using the table 601 to which the information management apparatus power is also output, it is more advantageous for the search to handle in the dictionary order, that is, an efficient and high-speed search is possible.
  • the decoding process of the position information 62 is performed prior to the decoding of the correspondence information 703, but either decoding process is performed first or simultaneously. It does n’t matter.
  • the information management device includes an information table encoding device and an information table decoding device.
  • the information table decoding device is the same as the information table decoding device 2 of FIG. 2 that works in the first embodiment, and thus the description thereof is omitted in this embodiment.
  • FIG. 13 is a functional block diagram of the information table encoding device 10 among the information management devices that are relevant to the second embodiment of the present invention.
  • the information table encoding device 10 includes a table separation unit 901 having a receiving unit 907, a position information encoding unit 902, a position information rearranging unit 903 having a corresponding information extracting unit 904, a corresponding information code key unit 905, and compressed information.
  • a forming unit 906 is provided.
  • the table separation unit 901 having the receiving unit 907, the position information encoding unit 902, the correspondence information encoding unit 905, and the compressed information forming unit 906 have the receiving unit 107 shown in FIG. 1 in the first embodiment. Since this table has the same functions as the table separation unit 101, the position information coding unit 102, the corresponding information coding unit 105, and the compression information forming unit 106, in the present embodiment, differences from the first embodiment are mainly described below. Explained.
  • the table 60 when the table 60 is formed by extracting only the predetermined type of element information from the additional information power of the video in FIG. 17, the tree structure is changed from the upper hierarchy to the lower hierarchy and the same hierarchy. Is based on the premise that the element information of the predetermined type is extracted and stored in order in the extraction table 60 in the order of appearance in the tree structure while scanning from the left to the right of the tree (see Fig. 3). ). For this reason, the information table encoding device 1 (see FIG. 1) of the first embodiment separates and outputs various types of information including the element information value 61 from the table 60, and thereafter, as auxiliary information at the time of search. In accordance with the format to be handled, a function unit for rearranging the element information values 61 that were separated and output in the order of the dictionary, that is, the element information rearrangement unit 103 was provided.
  • the additional information power of the video in FIG. 17 also extracts the value 61 of the predetermined type of element information and forms the table 60
  • the table 60 is formed by extracting in order of dictionary. That is, a table 601 in which element information values 61 are arranged in a dictionary order as shown in FIG. 7 is used as an input to the information table encoding device 10 (see FIG. 13) in the second embodiment.
  • the element information rearranging unit 103 in the first embodiment is not required in the information table encoding device 10.
  • the position information 62 is not arranged in order of the value indicated by the position information in the input table 601.
  • the information table code device 10 (FIG. 13) according to the present embodiment rearranges the position information 62 in order of the value (numerical value) indicated by the position information 62 in order to obtain the difference code. That is, a position information rearranging unit 903 is provided.
  • the table 601 is input by the receiving unit 907 (S10).
  • the table separation unit 901 reads the element type value 61 and the position information 62 from the input table 601 and separates and outputs them (Sl l).
  • the position information rearrangement unit 903 receives the plurality of position information 62 output from the table separation unit 901, and after rearranging the plurality of input position information 62 in order of the numerical value indicated by each, the position information rearrangement unit 903 The data is output to the information code key section 905 (S12).
  • the correspondence information extraction unit 904 inside the position information rearrangement unit 9 03 detects how the position information 62 is rearranged, and based on the detection result, the element information value 61 and the rearranged position information Correspondence information 703 indicating the correspondence with 62 is also extracted and output as input information power (S13).
  • FIG. 14 and FIG. 15 show a method of extracting (generating) correspondence information 703 from position information 62 at the time of rearrangement processing of position information 62.
  • FIG. 14A for each piece of position information 62 that has been input (read from table 601 in FIG. 7), each position information 62 has a value (numerical value).
  • An example is shown in which serial numbers are assigned in ascending order to obtain correspondence information 703 (see FIG. 14B) between element information value 61 and rearranged position information 62.
  • FIG. 14 (C) tried to make effective use of the existing high-speed rearrangement process.
  • the position information 62 is arranged in the table 601 in the position information 62, and the serial number is assigned twice in the order (see steps S1401 and S1403), and the position information 62 is rearranged in order of the value indicated by the position information 62.
  • the sorting process is performed twice (see steps S 1402 and S 1404).
  • correspondence information 703 in FIG. 14D is output.
  • FIG. 15 shows a method for calculating the correspondence information 703 based on the number of appearances of the value of the position information 62 for each layer.
  • the values (numerical values) of the position information 62 are rearranged in order of magnitude (step S1501), and then each value of each layer of the rearranged position information 62 is obtained.
  • the number of occurrences is counted in order from the upper layer (step S1502).
  • the number of values '1' is 5
  • the number of values '2' is 1 in the top layer (scene hierarchy).
  • the number of the value '1' is three and the number of the value '2' is two in the second layer (sub-scene layer). Be counted. Next, from the number of occurrences of a certain value in each layer, the number of position information 62 appearing before the value appears is obtained as the cumulative number Cxxx (step S 1503).
  • the value '1' is taken at the second layer before the position information 62 where the value '2' first appears in the second layer.
  • the cumulative number C12x is 3.
  • step S 1504 since each sum obtained in step S 1504 represents the number of pieces of position information 62 existing before the corresponding position information 62, finally, in order to count the position information 62 itself, 1 'is added to the corresponding sum (step S1505). As a result, the correspondence information 703 in FIG. 15C is output.
  • the correspondence information 703 is not limited to the serial number assigned to the position information 62 shown here, but can indicate how the position information 62 has been rearranged. Any information may be used. Further, even with the correspondence information 703 based on the serial number, the method of assigning correspondence and the method of extracting the correspondence information 703 are not limited to those shown here, and various methods are possible.
  • the above-described information management apparatus and method can be applied.
  • the element information value 61 and the position information 62 in the table 60 (or 601) to be transmitted or stored are further generalized as shown in the table 60 (or 601).
  • the search efficiency is maximized when the first elements managed in this way and the corresponding second elements are arranged according to different order relationships, or the sign efficiency is maximized. If both elements are arranged in an order suitable for the characteristic of one of the elements, the other element is rearranged in an order suitable for the characteristic.
  • both elements are arranged in an order suitable for their characteristics.
  • the feature is that it can be handled in a form.
  • the first element is transmitted in the order that maximizes the search efficiency
  • the second element is transmitted in the order that maximizes the encoding efficiency. If you have formed the information that you want to accumulate
  • the formed information is information that can achieve both code efficiency and search efficiency.
  • the search efficiency may be maximized when they are arranged.
  • FIG. 16 is a schematic configuration diagram of hardware of an apparatus corresponding to the information management apparatus according to the first and second embodiments.
  • the apparatus in FIG. 16 has a computer configuration.
  • the apparatus of FIG. 16 includes a CPU (Central Processing Unit) 1601 for centrally controlling and monitoring each part of the apparatus, and a ROM (Read Only Memory) 1602 for storing various programs and data.
  • CPU Central Processing Unit
  • ROM Read Only Memory
  • RAM Random Access Memory
  • HDD Hard Disk Drive
  • Interface 1605 for connecting to external recording devices such as DVD (Digital Versatile Disk) and memory cards, etc.
  • output unit 1608 detachable FD (flexible disk) FD drive unit to access 1610
  • CD Compact Disk
  • CD drive unit 1611 to access 1612
  • bus 1613 to enable communication between these units Is provided.
  • the compressed information forming program corresponding to is loaded into a predetermined storage area (not shown) of the CPU 1601 from the CPU 1601.
  • the CPU 1601 interprets and executes the instructions of each program loaded, and the following operations are performed.
  • the table 60 composed of the position information 62 and the element information value 61 is generated in advance and stored in the RAM 1603 or It is stored in HDD1604.
  • the table 707 and the encoding rule data 709 in FIG. 9 are stored in advance in the ROM 1602 as information that can be referred to by the CPU 1601.
  • CPU 1601 reads table 60 already stored in RAM 1603 or HDD 1604 according to the loaded table separation program, extracts position information 62 from read table 60, and separates it from table 60. Do (read). Then, the separated position information 62 is encoded according to the loaded position information encoding program, and the encoded position information 62 is temporarily stored in the RAM 1603 or HDD 1604. Further, the element information value 61 is extracted from the table 60 already stored in the RAM 1603 or the HDD 1604 and separated (read) from the table 60. Then, the separated element information value 61 is rearranged according to the loaded element information rearrangement and correspondence information extraction program, and the correspondence information 703 is extracted (generated), and the rearranged element information value 61 is obtained.
  • the extracted correspondence information 703 is temporarily stored in RAM1603 or HDD1604. Further, the correspondence information 703 is encoded according to the loaded correspondence information code program, and the encoded correspondence information 703 is temporarily stored in the RAM 1603 or HDD 1604. Finally, in accordance with the loaded compression information formation program, the compression information 708 is formed by using the encoded position information 62, correspondence information 703, and element information value 61 after rearrangement, and forming the compression information 708. Store 708 in RAM1603 or HDD1604.
  • the compressed information 708 is used for efficient storage and transmission of information in the table 60, and is connected via a recording medium of an external recording device connected by the interface 1605 or by the communication device 1606. It is provided to other devices having an information table decoding function through the communication network 1614, the FD driving unit 1609 through the FD 1610, or the CD driving unit 1611 through the CD1 612.
  • the compression information separation program corresponding to the compression information separation unit 201 stored in advance in the ROM 1602, the RAMI 603, or the HDD 1604, and the position information decoding unit 202 The position information decoding program, the corresponding information decoding program corresponding to the decoding section 203, the position information rearranging program corresponding to the position information rearranging section 204, and the table forming program corresponding to the table forming section 205 are CPU1601, CPU1601 is loaded to the specified storage area.
  • the following operations are realized by decoding and executing the instructions of the stored program.
  • the compression information 708 is obtained from the interface 1605 via the recording medium or from the communication device 1606 via the communication network 1614 and is stored in advance in the RAM 1603 or HDDI 604.
  • the CPU 1601 separates the element information value 61 from the compression information 708 stored in the RAM 1603 or the HDD 1604 according to the loaded compression information separation program 201, and the separated element information value 61 is stored in the RAM 1603 or Store temporarily in HDD 1604. Further, the position information 62 encoded from the compression information 708 is separated according to the compression information separation program 201, and the separated position information 62 is decoded according to the loaded position information decoding program. Information 62 is temporarily stored in RAM 1603 or HDD 1604. Similarly, the encoded correspondence information 703 is separated from the compressed information 708, the separated correspondence information 703 is decoded according to the loaded correspondence information decoding program, and the decoded correspondence information 703 is temporarily stored in the RAM 1603 or the HDD 1604.
  • the decoded position information 62 is rearranged based on the decoded correspondence information 7003 according to the loaded position information rearrangement program, and the rearranged position information 62 is temporarily stored in the RAM 1603 or HDD 1604.
  • the table 601 is formed using the element information value 61 and the position information 62 (after the decoding and rearrangement processing), and the formed table 601 is stored in the RAM 1603 or Store in HDD 1604.
  • This table 601 is used as auxiliary information at the time of executing a search using additional information. Or, via the recording medium of the external recording device connected by the interface 1605, through the communication network 1614 connected by the communication device 1606, or by the FD drive unit 1609 via the FD1610, or CD drive It may be provided to another device having a search function by the unit 1611 via the CD1 612.
  • Iprog A compression information formation program corresponding to the RAM and compression information formation unit 906 is loaded into a predetermined storage area of the CPU 1601 by the CPU 1601. The CPU 1601 reads out the instructions of each program from the predetermined storage area, interprets and executes them, thereby realizing the following operations.
  • the table 60 (or 601) composed of the position information 62 and the element information value 61 is generated in advance and stored in the RAM 1603 or the HDD 1604.
  • the encoding rule data 709 is stored in advance in the ROM 1602 as information that can be referred to by the CPU 1601.
  • the CPU 1601 separates (reads out) the position information 62 in accordance with the table 60 (or 601) force already stored in the RAM 1603 or the HDD 1604 according to the loaded table separation program.
  • the rearrangement and correspondence information 703 is extracted (generated) in accordance with the loaded position information rearrangement and correspondence information extraction program, and the rearranged position information 62 and the extracted correspondence information 703 are obtained. Is temporarily stored in RAM1603 or HDD1604.
  • the table 60 (or 601) force already stored in the RAM 1603 or HDD 1604 also separates (reads) the element information value 61, and the separated element information value 61 is stored in the RAM. Store temporarily in 1603 or HDD 1604.
  • the rearranged position information 62 is encoded according to the loaded position information code program, and the encoded position information 62 is temporarily stored in the RAM 1603 or HDD 1604.
  • the correspondence information 703 is encoded according to the loaded correspondence information encoding program, and the encoded correspondence information 703 is temporarily stored in the RAM 1603 or the HDD 1604.
  • the compression information 708 is formed using the encoded position information 62, correspondence information 703, and element information value 61, and the formed compression information 708 is stored in the RAM. Store in 1603 or HDD 1604.
  • This compressed information 708 is used for efficient storage and transmission of information in a table format, and is connected via a recording medium of an external recording device connected by the interface 1605 or by the communication device 1606. It is provided to other devices having the information table decoding function through the communication network 1614, the FD driving unit 1609 through the FD 1610, or the CD driving unit 1611 through the CD 1612.
  • the decoding process basically does nothing from the user. It is automatically executed without any instructions or information input.
  • the present invention is not limited to this.
  • the user arbitrarily gives an instruction for encoding Z decoding through the input unit 1607, or the CPU 1601 outputs the operation status during execution of the encoding Z decoding process. It is also possible to perform operations such as presenting to the user via the unit 1608.
  • ROM 1602, RAM 1603, or HDD 1604 in the apparatus of FIG. It can be implemented in any configuration by being recorded on an external recording medium and loaded into the memory through the interface 1605 during program execution.
  • External recording media include magnetic tape not shown, CD—ROMZRZRW, DV D-ROM / RAM / R / RW, MO (magneto—optic), SD (Secure Digital) memory, FD (Flexible Disk) and so on.
  • these programs transmitted via the communication network 1614 may be received by the communication device 1606 and stored in the ROM 1602, RAM 1603, or HDD 1604.
  • element information 61 (text information) is rearranged in dictionary order and stored.
  • the position information 62 of each corresponding leaf R is differentially encoded based on the order of appearance in the tree structure (numerical order), and the information is rearranged with the position information.
  • Correspondence information 703 indicating the correspondence between element information (or element information and rearranged position information) was encoded and added. As a result, it is possible to efficiently encode the position information included in the table 60 by using differential encoding, and the element information 61 is arranged in the order of the dictionary, so that high search efficiency can be obtained. It became.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Multimedia (AREA)
  • Data Mining & Analysis (AREA)
  • Databases & Information Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Library & Information Science (AREA)
  • Software Systems (AREA)
  • Compression Or Coding Systems Of Tv Signals (AREA)

Abstract

　装置は、木構造の情報に含まれる要素情報と対応する木構造中での位置情報とからなるテーブル（６０）を、テーブル分離部（１０１）により、要素情報の値（６１）と位置情報（６２）とに分離する。要素情報並替部（１０３）は、分離された要素情報の値（６１）を辞書順に並替える。この並替えによる順序関係の変化を示すための対応情報（７０３）が、対応情報抽出部（１０４）により抽出される。位置情報符号化部（１０２）および対応情報符号化部（１０５）は、位置情報（６２）および対応情報（７０３）を各々符号化する。符号化された位置情報（６２）および対応情報（７０３）と要素情報の値（６１）とを用いて、圧縮情報形成部（１０６）は、これらの圧縮情報を形成する。

Description

明 細 書
符号化装置、符号化方法、復号装置、復号方法、プログラムおよび該プ ログラムを記録した機械読取り可能な記録媒体
技術分野
[0001] 本発明は、木構造を有する情報の符号化装置、符号化方法、復号装置、復号方法
、プログラムおよび該プログラムを記録した機械読取り可能な記録媒体に関し、特に 、木構造の複数の葉にあたる要素情報と、該葉の木構造における位置を示した位置 情報とを対応付けて処理する符号化装置、符号化方法、復号装置、復号方法、プロ グラムおよび該プログラムを記録した機械読取り可能な記録媒体に関する。
背景技術
[0002] 昨今の映像記録装置の記録容量の大容量ィヒゃ高速 Z広帯域ネットワークの普及 は、ユーザに対して大量の映像を一度に提供可能な環境を提供する。一方、提供さ れる映像データをユーザが効率良く利用するためには、映像データの中から所望の 映像または部分映像 (ショット、カット）のデータを簡単に、高速に探し出す機能が必 要とされる。この機能の 1つとして、映像データに付加されるべき該映像に関する情 報 (以下、付加情報という）を予め用意して、付加情報に基づいて検索する機能が提 供される。該機能によれば、例えば、映像のタイトルカタログカゝら所望のものを検索し て、対応する映像データを提供することもでき、また、映像に関する更に詳細な内容 を記述した付加情報が用意され、内容に基づいた検索をユーザに提供することもで きる。
[0003] 図 17には、従来および本発明の実施の形態において適用される、ある映像データ により提示される映像の内容を記述した付加情報の例が示される。図 17に示される ように、付加情報は映像の論理構造に対応した木構造で表される。
[0004] 一般に、映像などの動画像コンテンツは 1つまたは複数のシーンによって構成され 、さらに各シーンは 1つまた複数のサブシーン（あるいはショット）、あるいはさらに別の シーンによって構成される、というように階層性を有する。映像の検索時の利便性を 高めるために、サブシーンの特徴を示す検索情報を各サブシーンに付加する際の記 述手法は、前述の階層性を表現するため、図 17に示すような木構造からなる表現手 法を用いている。図 17では、映像全体が 2つのシーンからなり、それぞれが 2つのサ ブシーンと 1つのサブシーンとで構成される。そして、それぞれのサブシーンについ て、そのサブシーンに関する関連情報、ここではサブシーンの時刻情報（開始時刻/ 長さ）、タイトル、およびそのサブシーンに映っている出演者を記述している。木構造 としては、映像データ全体が根 (ルートノード) RNにあたり、シーン、サブシーン、なら びに時刻情報、タイトル、出演者といった要素種別を表している節が節 Nにあたる。 節 Nの中でも、シーンの階層は根 RNから見て最初の分岐先に相当するので、第 1階 層の節 Nにあたる。また、サブシーンの階層は第 2階層の節 Nにあたる。そして、各サ ブシーンの関連情報である時刻情報、タイトル、出演者を表すデータが木構造の葉 L にあたる。
[0005] これら葉 Lとして付された情報をここでは検索情報の「要素情報」あるいは単に「要 素」と呼ぶ。
[0006] ここで、要素情報それぞれが木構造中のどの葉 Lにあたるかを区別するためには、 要素の値の他に、その要素の木構造における位置を示した情報を同時に保存する 必要がある。言い換えると、その要素がいずれのシーンのいずれのサブシーンに関 するものであるかという情報が必要となる。図 17においてシーンまたは 1つのシーン 内のサブシーンを区別するために付された番号「1」、「2」、サブシーン内の複数の出 演者を区別するために付された番号「1」、「2」、「3」は、前述した木構造中の要素の 位置を一意に示すための情報であり、「位置情報」と呼ぶ。この位置情報は木構造に おいて規定された順序関係に従い表現される。この例を以下に説明する。
[0007] 木構造では、ある節 N (または根 RN)の下層に位置するすべての節 Nにつ!/、て木 の左力も右に順に 1番、 2番* · ·と連番をつけ、根 RN力もある葉 Lに至るまでに経由 する全ての節 Nにつ 、て、該連番を列挙することで該葉 Lの位置情報が表現される。
[0008] 図 17を参照して、この規定順序に従う位置情報の生成方法の具体例を、左から 3 つめの要素「Akira ABE」の場合で説明する。木は上階層から下階層へ、かつ同一 階層は左力 右に走査することで出現する順番に節 N (根 RNまたは葉 L)それぞれ に位置情報を割当てる。 [0009] まず第 1階層を見ると、要素「Akira ABE」が属するシーンは、根 RNにあたる映像 にぶら下がった一番左側の節 Nである。このため、第 1階層の位置情報は「1」番とな る。次に、第 2階層を見ると、要素「Akira ABE」が属するサブシーンは 1つ上の階層 の節 Nにあたるシーン「1」にぶら下がった節 Nの中で左から 1番目の節である。この ため、第 2階層での位置（出現順番）は「1」番となる。次に、第 3階層を見ると、要素「 Akira ABEJの葉 Lはサブシーン [1]にぶら下がった '出演者，と!、う節 Nの中で左か ら 1番目の節 Nである。このため、第 3階層での'出演者，という要素の中での位置（出 現順番）は「1」番となる。したがって、この場合、木を構成する全ての階層である第 1 〜第 3階層あわせて（1、 1、 1)が要素「Akira ABE」の位置情報となる。この形式で全 ての葉 Lの位置情報を一意に表現することが可能である。
[0010] 検索は以下のように行なう。例えば、図 17において「Wataru WADA」が出演してい るサブシーンを探す。即ち、検索条件「出演者 =Wataru WADA」を与え、出演者を 示す要素情報 (葉 L)から条件「WatarU WADA」に一致するものを探す。条件を満た す要素が見つかれば、それがどのサブシーンに属するかを示す情報（「シーン 1のサ ブシーン 1」）を検索結果として返す。サブシーンの再生は、そのサブシーンの葉しに 付された時刻情報を見て行なう。
[0011] 図 17は極めて簡単な付加情報の例である力 実際の要素種別はこれだけに限ら ず、また映像が複雑なほど木構造も複雑ィ匕するため、映像の付加情報のサイズは一 般に大きい。このため、付加情報を予め分割された形で扱い、利用時に必要な部分 情報だけを得て用いるといった形態がとられることも多い。
[0012] 図 18には、図 17の付加情報の木構造を扱い易い形に (サブシーン単位に)分割し た例が示される。分割されたそれぞれの木は「部分木」（sub-tree)もしくは「フラグメン ト」（fragment)と呼ばれる。更に、上述のような「出演者」による検索を行なうために図 19に示すようなテーブルを補助情報として用意する。図 19のテーブルは、木構造中 の全ての要素情報（出演者)の値と、各要素情報に対応してその要素情報がどの部 分木 (フラグメント）に属するかを示すフラグメント情報とを格納して ヽる。
[0013] この場合、付加情報を用いた映像の検索は以下のように行なう。システムはまず要 求に応じて図 19に示したテーブルをユーザに伝送する。ユーザは、受理したテープ ルカゝら検索条件「Wataru WADA」に合致するものを検索して対応するフラグメント情 報を読出す。そして、読出したフラグメント情報が示すフラグメント（「フラグメント 1」）の データを要求する。システムは要求に応じて「フラグメント 1」のデータをユーザに伝送 するので、ユーザは「フラグメント 1」のデータを受理して、受理した「フラグメント 1」の データを利用する。なお、サブシーンの再生は、得られたフラグメントのデータ中の「 時刻情報」を参照して行なわれる。
[0014] 図 19に示した補助情報の具体例としては、 TV Anytimeフェーズ 1パート 3— 2規格
(ETSI TS 102 822-3-2)に示すインデキシング（Indexing)技術が挙げられる。
[0015] 図 18と図 19では、個々のフラグメントを示すための情報を図 17の付加情報とは別 途設けているが、それらは図 17の付加情報に含まれている位置情報で置き換えるこ とがでさる。
[0016] 図 19のテーブルは、実際に利用するか否かに拘らず常に伝送されるものである。
そのため、伝送効率を考慮すると、このテーブルは圧縮符号化されて伝送されること が望ましい。これに関し、特開 2003— 092757号公報 (特許文献 1)には、複数の位 置情報を高 、圧縮率で符号化する方法として、大きさの順番に連続する値の位置情 報の差分符号化方法が示されている。この差分符号化方法は、木構造のある葉 L (ま たはある節 N)の位置情報をそのまま記述するのではなぐ該位置情報と木構造にお V、てその 1つ前の順番に位置する葉 L (または節 N)の位置情報との変位 (差分)のみ を用いて位置情報を符号ィ匕する。これにより、より少ないビット数で効率よく符号ィ匕で きるという効果をもたらす。
特許文献 1 :特開 2003— 092757号公報
発明の開示
発明が解決しょうとする課題
[0017] 図 19に示したように、リストアップされる付加情報の各要素（要素情報の値)の種別 が該要素はテキスト形式の情報であることを示す場合、検索効率が高くなるように、該 種別に基づき、それらを付加情報 (木構造）中での出現順 (位置情報の値の順番)の 並びから辞書順（lexicographic ordering)の並びに変更することが行なわれる。テキ スト形式の情報群は情報を辞書順に並べることで該情報群力 所望情報を検索する 時の演算量は対数オーダに従うものとなり、辞書順でない場合に比較して検索効率 に優れることが知られて 、る。
[0018] 図 19のテーブル中の要素情報の値を辞書順に並替えた場合、対応する位置情報 の値も同じく並替えられるため、位置情報の値の大きさ順に従う並び関係が崩れてし まう。そのため、要素情報の値を辞書順に並替える場合には、対応の位置情報に対 して特許文献 1に示された差分符号化方式を適用することはできなかった。
[0019] それゆえにこの発明の目的は、木構造により構成される情報について、検索効率に 優れる情報を得ることのできる符号ィ匕装置、符号化方法、プログラムおよび該プログ ラムを記録した機械読取り可能な記録媒体、ならびにこの符号化された情報を復号 する復号装置、復号方法、プログラムおよび該プログラムを記録した機械読取り可能 な記録媒体を提供することである。
[0020] この発明の他の目的は、木構造により構成される情報について、符号化効率に優 れる情報を得ることのできる符号ィ匕装置、符号化方法、プログラムおよび該プログラム を記録した機械読取り可能な記録媒体、ならびにこの符号化された情報を復号する 復号装置、復号方法、プログラムおよび該プログラムを記録した機械読取り可能な記 録媒体を提供することである。
[0021] この発明の他の目的は、木構造により構成される情報について、符号化効率に優 れる情報を得ることのできる符号ィ匕装置、符号化方法、プログラムおよび該プログラム を記録した機械読取り可能な記録媒体、ならびにこの符号化された情報を復号する 復号装置、復号方法、プログラムおよび該プログラムを記録した機械読取り可能な記 録媒体を提供することである。
課題を解決するための手段
[0022] この発明のある局面に従うと、要素情報が付された複数の葉の間に、規定順序の 関係を有する木構造により構成される情報の符号化をする。
[0023] まず、所定種別の要素情報と、該所定種別の要素情報が付された葉の前記木構造 における規定順序に従う位置を示す位置情報と含んだ複数の組を、規定順序に従う 順番に並んで有する情報群を、受理する部部により受理する。そして、並替え部は、 受理した情報群の複数の組それぞれから複数の要素情報を分離して、分離した複 数の要素情報を所定の順序に従い並替える。また対応情報生成部は、対応情報を 生成する。対応情報は、規定順序から所定順序への並替えによる複数の要素情報 の順番の変化に基づき、並替え後の複数の要素情報それぞれと、受理している情報 群の中の該要素情報と同一組の位置情報との対応関係を示す。
[0024] 位置情報符号化部は、受理して!/、る情報群の複数の組それぞれから位置情報を 分離して分離した複数の位置情報を符号化する。そして、所定情報形成部は、符号 化された位置情報と、生成された対応情報と、並替え後の要素情報とを含めた所定 情報を形成する。
[0025] 前述の所定順序は、所定種別の要素情報の検索に適した順序を指す。
この発明の他の局面に従うと、要素情報が付された複数の葉の間に、規定順序の 関係を有する木構造により構成される情報の符号化をする。
[0026] まず、所定種別の要素情報と、当該所定種別の要素情報が付された葉の木構造に おける規定順序に従う位置を指示する位置情報と含んだ複数の組を、所定順序に並 んで有する情報群を、受理部により受理する。
[0027] 要素情報分離部は、受理した情報群の複数の組それぞれから要素情報を分離し て出力する。また、位置情報並べ替部は、受理した情報群の複数の組それぞれから 位置情報を分離して、分離した複数の位置情報を、規定順序に従い並替える。また 、対応情報生成部は、対応情報を生成する。対応情報は、並替えによる複数の位置 情報の順番の変化に基づぐ並替え後の複数の位置情報それぞれと、受理している 情報群の中の該位置情報と同一組の要素情報との対応関係を示す。
[0028] 位置情報符号化部は、並替えされた複数の位置情報を符号化する。そして、所定 情報形成部は、符号化された位置情報と、生成された対応情報と、分離された要素 情報とを含めた所定情報を生成する。
[0029] 前述の所定順序は、所定種別の要素情報の検索に適した順序を指す。
この発明のさらに他の局面に従うと、要素情報が付された複数の葉の間に、規定順 序の関係を有する木構造により構成される符号化情報を復号する。
[0030] まず、所定順序で並んだ複数の要素情報と、該複数の要素情報が付された複数の 葉の木構造における規定順序に従う位置を示す符号化された位置情報と、複数の 位置情報のうち所定順序で並んだ複数の要素情報それぞれと対応する位置情報を 特定するための対応情報とを含んで生成された所定情報を、受理部により受理する 。分離部は、受理した所定情報から複数の要素情報と、複数の符号化された位置情 報と、対応情報とをそれぞれ分離して出力する。
[0031] 位置情報復号部は、分離された複数の符号化された位置情報を復号する。並替え 部は、復号された複数の位置情報を、分離された対応情報に従って所定順序に従 い並替える。
[0032] 並替え後の複数の位置情報それぞれと、分離されて!、る所定順序で並んだ複数の 要素情報それぞれとが対応付けされた情報が出力される。
[0033] 前述の所定順序は、所定種別の要素情報の検索に適した順序を指す。
発明の効果
[0034] 本発明では、木構造の情報の符号ィ匕によって生成される所定情報には、木構造の 複数の葉に付された所定種別の複数の要素情報が含まれる。この複数の要素情報 は、所定種別の要素情報の検索に適した順番に従い並べられている。したがって、 所定情報の検索に際しては高い検索効率を得ることが可能となる。
[0035] また、位置情報の符号化は差分符号化を用いることで情報群の位置情報を効率的 に符号ィ匕できる。これにより、所定情報について、復号により元の情報群を取得する のに必要な情報の種類と情報の量を有しながらも情報量を少なくできる。このことから 、情報群を符号化して生成された所定情報を伝送する場合には高!、伝送効率を得 ることができる。また所定情報を記憶媒体に格納する場合には必要なメモリ容量を少 なくできる。
図面の簡単な説明
[0036] [図 1]本発明の第 1の実施形態に力かる情報管理装置のうち、情報テーブル符号ィ匕 装置の概略機能ブロック図である。
[図 2]本発明の第 1の実施形態に力かる情報管理装置のうち、情報テーブル復号装 置の概略機能ブロック図である。
[図 3]木構造中の出現順に従い情報を格納するテーブルの一例を示す図である。
[図 4]テーブルの具体的なデータ構造の一例を示す図である。 [図 5]テーブルの具体的なデータ構造の他の例を示す図である。
[図 6]本発明の第 1の実施形態における情報管理方法のうち、情報テーブル符号ィ匕 方法を表すフローチャートである。
圆 7]要素情報が辞書順に並んだテーブル形式の情報を示した例である。
圆 8]第 1の実施形態において対応情報を抽出する過程を示す図である。
圆 9]位置情報の差分符号ィ匕時に用いる位置情報符号を示した例である。
圆 10]差分符号化された位置情報の符号列を位置情報と共に示す図である。
圆 11]本発明の第 1の実施形態にかかる情報テーブル符号ィ匕装置で符号化された 圧縮情報のデータ構造を示した説明図である。
[図 12]本発明の第 1の実施形態における情報管理方法のうち、情報テーブル復号方 法を表すフローチャートである。
圆 13]本発明の第 2の実施形態に力かる情報管理装置のうち、情報テーブル符号ィ匕 装置の概略機能ブロック図である。
圆 14]第 2の実施形態において対応情報を抽出する過程の一例を示す図である。 圆 15]第 2の実施形態において対応情報を抽出する過程の他の例を示す図である。 圆 16]第 1および第 2の実施形態に力かる情報管理装置のハードウェア構成図であ る。
圆 17]従来および本発明の実施の形態に適用される木構造カゝらなる映像の付加情 報の一例を示す図である。
圆 18]図 17の木構造を分割した部分木を示す図である。
[図 19]従来のテーブル形式の情報の一例を示す図である。
符号の説明
101, 901 テーブル分離部、 102, 902 位置情報符号化部、 103 要素情報並 替部、 104, 904 対応情報抽出部、 105, 905 対応情報符号化部、 106, 906 圧縮情報形成部、 201 圧縮情報分離部、 202 位置情報復号部、 203 対応情報 復号部、 204 位置情報並替部、 205 テーブル形成部、 903 位置情報並替部、 1 601 CPU, 1602 ROM, 1603 RAM, 1604 HDD, 1605 インターフェース 、 1606 通信デバイス、 1607 入力部、 1608 出力部、 1613 パス。 発明を実施するための最良の形態
[0038] 以下に説明する第 1〜第 3の実施の形態では、木構造力 構成される情報に対し、 検索用の補助情報として参照されるテーブルまたは当該テーブルに格納される情報 を符号ィ匕して、その結果、当該テーブルまたは情報を圧縮する。以下、これを圧縮符 号化という。このテーブルには、木構造における複数の葉 Lそれぞれに付された要素 情報と該葉 Lの木構造における前述の規定順序に従う位置を示す位置情報とからな るレコードが複数個格納されている。圧縮符号ィ匕の際には、テーブルの複数レコード の複数の要素情報（出演者の名前を示すテキスト情報）は辞書順に並べて保持する 。そして、テーブルの複数レコードの位置情報それぞれは、該位置情報の葉 Lに対し て前述の規定順序に従 、直前に位置（出現)する葉 Lの位置情報との差分に基づき 符号化する。そして、複数の要素情報それぞれと位置情報との対応関係を示す情報 を生成して、これを符号化する。そして、これら情報を所定形式に配置された 1個の 情報を形成する。形成される情報は、前述の検索用の補助情報として得られる。
[0039] なお、ここでは、テーブルで管理される要素情報は図 17の最下位層の葉 Lに付さ れた「出演者」を示すデータとしている力 これに限定されない。任意の位置にある葉 Lに対して適用可能であるし、あるいは図 17の木構造に含まれる任意の節 Nをそれ 以下に連結されている要素情報の集合として与えた仮の要素情報とみなして、本発 明の方式を適用することもできる。この場合、テーブルのレコードで管理される情報は 、木構造の任意の節 Nにあたる要素情報 (実際には要素情報の集合)とその位置情 報の組となる。
[0040] (第 1の実施の形態）
本発明の第 1の実施形態にかかる情報管理装置を、図 1ないし図 12ならびに図 17 を用いて説明する。本発明の第 1の実施形態にかかる情報管理装置は、情報テープ ル符号化装置および情報テーブル復号装置を備える。
[0041] 図 1は本発明の第 1の実施形態に力かる情報管理装置のうち、情報テーブル符号 化装置 1の概略構成を示した機能ブロック図である。情報テーブル符号ィ匕装置 1は、 受理部 107を有するテーブル分離部 101、位置情報符号化部 102、対応情報抽出 部 104を内部に有する要素情報並替部 103、対応情報符号化部 105および圧縮情 報形成部 106を備える。
[0042] 図 2は本発明の第 1の実施形態に力かる情報管理装置のうち、情報テーブル復号 装置 2の概略構成を示した機能ブロック図である。情報テーブル復号装置 2は、受理 部 207を有する圧縮情報分離部 201、テーブル 707を有する位置情報復号部 202、 対応情報復号部 203、位置情報並替部 204およびテーブル形成部 205を備える。
[0043] 以下、図 17に示した映像の付加情報を例に、本実施形態にかかる情報管理装置（ 情報テーブル符号化装置 1および情報テーブル復号装置 2)の動作を説明する。図 17に示されるように、映像の付加情報は映像の論理構造に対応した木構造で表され る。図 17の各節 Nの種別名'シーン'、 'サブシーン'および'出演者，それぞれに付さ れた数字「1」「2」「3」は、該節 Nの木構造中の位置を一意に特定するための情報と して付されている。
[0044] 無論、実際の映像の付加情報は構造、内容共にこれに限られるものでない。例え ば、ルートノード RN (木の最上位ノード)やシーンを表す各節 Nに、対応する映像タ ィトルある 、はシーンタイトルを表す葉 Lを追カ卩したり、サブシーンを更に細かなサブ シーンに分割して木の階層数を増やしたり、あるいは減らしたりといったことが可能で ある。付加情報に含まれる要素の種別も図 17に示したものに限定されない。また、シ ーン、サブシーンの組合せによる木（1つの映像を記述した木）以外にも、ルートノー ド RNが 1つのチャンネルで放送される全番組 (プログラム）を表し、 1階層目の節 Nそ れぞれがプログラムを表し、 2階層目の各節 Nがプログラムに含まれるシーンを表すと V、つた木を扱うこともできる。
[0045] 図 3のテーブル 60は複数のレコードを含む。各レコードには、図 17の付カ卩情報から 抜出した同種の要素情報「出演者」の値 61と、該要素情報の値 61にあたる葉 Lの位 置情報 62とを格納した組を格納している。図 3のテーブル 60では、図 17の付加情報 の木が端力 順に走査され、抜出された同種の要素情報「出演者」が木構造上での 出現順にそのまま並べられている。即ち、木構造を左から右に走査した場合に現れ る要素情報の値 61が出現順に従いテーブル 60の上から下に順に格納されている。 したがって、位置情報 62は 1〜3階層の位置の組合せにより（シーン #、サブシーン #、出演者 # )として示されるので、テーブル 60では例えば要素情報の値 61が「Akir a ABE」の位置情報 62は値（1, 1, 1)と示されて、要素情報の値 61が「Wataru WA DA」の位置情報 62は値（1, 1, 3)と示される。位置情報 62は、同一階層の節 Nに対 して木の左側力も値が振られるため、最も左の要素情報 62の値が最小値（1, 1, 1) を示し、最も右の要素情報 62の値が最大値 (2, 1, 1)を示す。
[0046] 本実施形態では、図 3に示したテーブル 60を情報テーブル符号化装置 1への入力 とする。即ち、本実施形態では、木構造力 なる付加情報に含まれる要素情報から 同種の要素の値が既に選択されて抜出されていることを前提とし、それらの要素情報 の値 61および対応する位置情報 62の符号ィ匕に関する処理について説明する。無論 、情報テーブル符号化装置 1を、木構造の情報から同種の要素情報を選び出して要 素種別毎にテーブルを形成し、かつ、要素種別を表す情報も共に符号化して要素情 報の値 61および位置情報 62の符号列に加えて圧縮情報を形成する機能を有する よう〖こすることも可能である。同様に、情報テーブル復号装置 2を、要素種別の情報、 要素情報の値 61および位置情報 62のそれぞれを復号して要素種別毎にテーブル を形成する機能部として、図示のな 、上位の情報テーブル復号装置が有することも 可能である。また、ここで言う符号ィ匕対象のテーブルとは、要素情報と位置情報とが 一対一に対応付けられるデータ構造のことであって、実際には、図 4または図 5に示 すような構造のデータを指す。
[0047] 図 4のテーブル 63と 64は、要素情報の種別毎に、要素情報の値と対応の位置情 報とが対になって格納されるグループを有する。各グループでは、図 4 (A)のテープ ル 63のように、要素情報（値 Al、値 A2、 · · ·、値 Bl、値 B2、 · · と対応している位 置情報 (位置情報 A1、位置情報 A2、 · · ·、位置情報 B1、位置情報 B2、 · · ·）とが対 となり、かつ要素情報の値と位置情報とが交互に配置される構造を有する。また、各 グループでは、図 4 (B)のテーブル 64のように、要素情報が全て連続して配置された 後、対応する位置情報が全て連続して配置される構造を有してもょ ヽ。
[0048] 図 5のテーブル 65と 66は、要素情報の値が位置情報とは離れた別のデータ構造 に格納されている。そのため、要素情報の種別毎に、その別のデータ構造に格納さ れた要素情報の値を参照するための参照情報が該要素情報の値の位置情報と対と なって格納されるデータ構造を有する。図 5 (A)のテーブル 65は、要素情報の値へ の参照情報と対応する位置情報とが対となり、かつ該参照情報と位置情報とが交互 に配置される構造を有する。図 5 (B)のテーブル 66は、要素情報への参照情報が全 て連続して配置された後、対応する位置情報が全て連続して配置される構造を有す る。
[0049] 後述する位置情報の差分符号ィ匕を行なうためには、図 4 (B)あるいは図 5 (B)に示 されたような、複数の位置情報が連続して配置されて 、るデータ構造が望ま 、が、 要素情報の値あるいは要素情報の値への参照情報に力かる符号の量が判るような 場合では、図 4 (A)あるいは図 5 (A)のように参照情報と位置情報が交互に配置され たデータ構造であっても、位置情報の差分符号ィ匕を行なうことは可能である。また、 図 4および図 5では要素情報の値 (または要素情報の値への参照情報)を先に、その 後に対応する位置情報を配置したデータ構造を例に示したが、位置情報を先に、そ の後に対応する要素情報の値 (または要素情報の値への参照情報)を配置するデー タ構造であっても構わない。
[0050] (情報テーブル符号化装置の動作）
本実施形態にカゝかる情報テーブル符号ィ匕装置 1のテーブルを符号ィ匕する動作に つ ヽて図 6のフローチャートを参照して説明する。
[0051] テーブル分離部 101は、木構造力もなる情報に含まれた同種の要素情報を抜出す ことで予め得られている図 3のテーブル 60を (実際には図 4または図 5で示されたよう なデータ構造力もなるデータを)受理部 107により受取り（ステップ S (以下、単に Sと 略す） 10)、受取ったテーブル 60の情報を要素情報の値 61と位置情報 62とに分離 して出力する（Sl l)。無論、テーブル 60が予め生成されておらず、図 17の木構造の 付加情報を受取って、そこに含まれる要素情報の種別を解析し、同種の要素情報を 集めて図 3のテーブル 60を生成するまでの処理をテーブル分離部 101が行なうよう にしてもよい。
[0052] 位置情報符号ィ匕部 102は、テーブル分離部 101から出力された位置情報 62を入 力して符号化する。この際、図 3のテーブル 60において、複数の位置情報 62は、木 構造における出現順序と同じぐ数値の小さいもの力も大きいものへと順に (昇順）に 並んでいるため、特許文献 1で示されている差分符号ィ匕を用いて効率的に符号ィ匕す ることができる。以降、数値の小さいものから大きいものへと順に並ぶことを大小順に 並ぶと 、う。符号ィ匕の具体例にっ 、ては図 9と図 10を用いて後述する。
[0053] 要素情報並替部 103は、テーブル分離部 101から出力された複数の要素情報の 値 61を入力する。そして、入力した要素情報の値 61を、当該要素情報の値 61は図 3のテーブル 60で示された木構造中の出現順、即ち位置情報 62の値の順に並んで いるが、辞書順 (アルファベット順または日本語に固有の 50音順といった辞書編集上 の順序）に従うように並べ直す (S 12)。
[0054] 図 7は、要素情報並替部 103の並替えによって図 3のテーブル 60の情報を並替え た後のテーブル 601を示したものである。図 7のテーブル 601はまた、後述する情報 テーブル復号装置 2で出力されるテーブル 601を示す。実際に検索時の補助情報と して用いられるテーブルは、図 7に示したような、要素情報の値 61が辞書順に並んだ 形式のものとなる。つまり、図 3に示した木構造の出現順に要素情報の値 61が並べら れたテーブル 60は、符号ィ匕のために作成された中間データに相当する。
[0055] 図 7からも判るように、並替え後の位置情報 62は、その値の大小順関係に従って並 んでいないため、上述した差分符号ィ匕を直接行なうことはできない。そこで、対応情 報抽出部 104は、図 3のテーブル 60から図 7のテーブル 601への変化により示される ように要素情報の値 61を並替えた際、どう並替わつたかを検出して、検出結果を示 す情報を要素情報と位置情報との対応情報 703として出力する（S13)。この対応情 報 703を生成するための処理は要素情報 61の並替えと同期して行なわれるため、対 応情報抽出部 104は要素情報並替部 103の内部構成となっている。
[0056] 図 8 (A)は図 8 (B)の対応情報 703を求める処理過程の例を示して!/、る。図 8 (A) には、図 3の並替え前の要素情報の値 61が要素情報 701として、図 7の並替え後の 要素情報の値 61が要素情報 702としてそれぞれ示されている。処理は、図面の左か ら、まず、並替え前の要素情報 701のそれぞれに対して並びの順に（1)から（6)まで の通し番号を付ける (ステップ S (以下、単に Sという） 1)。次に、通し番号を付けた状 態で、要素情報 701を辞書順に並替える（S2)。並替え後の要素情報 702に付され た通し番号は（1)、（4)、 (5)、 (2)、（6)、（3)の並びとなる。したがって、図 8 (B)の 対応情報 703は並替えの結果を示す並替え後の通し番号の並びを示す。無論、対 応情報 703はこのような通し番号で与えられるものに限らず、要素情報の値 61の並 替えがどのように行なわれたかを示すことが可能な情報であればよい。また、通し番 号に基づく対応情報 703であっても、対応情報 703の付け方および対応情報の抽出 方法はここで示したものに限らず、様々な方法での実装が可能である。
[0057] 次に、位置情報符号ィ匕部 102はテーブル分離部 101から出力された位置情報 62 を入力して、入力した位置情報 62を差分符号化して出力する (S14)。対応情報符 号ィ匕部 105は、対応情報抽出部 104で抽出（生成)された対応情報 703を入力して 、入力した対応情報 703を符号化して出力する (S15)。最後に、圧縮情報形成部 1 06は、位置情報符号化部 102、対応情報符号化部 105および要素情報並替部 103 のそれぞれから出力された、符号化された位置情報 62、符号化された対応情報 703 、および並替え後の要素情報の値 61を入力して、これら入力した情報が所定の形式 に配置された圧縮情報 708を形成して出力する（S16)。情報テーブル符号化装置 1 カゝら出力された圧縮情報 708 (検索時の補助情報となるテーブル 601を圧縮符号ィ匕 した情報）はテーブル 601の伝送時または蓄積時に、伝送データ量または蓄積デー タ量を減らしてテーブル 601を効率良く管理するために用いられる。
[0058] この実施形態では、要素情報の値 61自体の圧縮符号ィ匕については説明しなかつ たが、位置情報 62および対応情報 703を符号化するのと共に、要素情報の値 61自 体を符号ィ匕することがテーブル 601の伝送や蓄積時の効率向上のために有効なこと は言うまでもない。テーブル 601で示した要素情報はテキスト情報である。従って、通 常のテキストのコードィ匕による圧縮や、 Zip圧縮など既存の圧縮ツールを用いた圧縮 が可能である。
[0059] また、並替え後の要素情報の値 61が辞書順に並ぶことから、同じ値 61を持った要 素情報をまとめて扱うといった処理や、差分符号化といった処理を適用することも可 能である。前者では、例えば、同じ値 61を持つ要素情報について、該値 61とその値 を有する要素情報の個数とでそれらの要素情報を符号ィ匕する。例えば図 7のテープ ル 601には、値 61が「Rie RYUSHO」の要素情報が 2つあるので、圧縮情報形成時 には「Rie RYUSHO」を 2回記録する代わりに「Rie RYUSHO」を 1回だけ記録し、カロ えて「2」という個数の情報を記録することで、テーブル 601を記録するためにかかる データ量を削減できる。無論、要素情報の値 61の符号ィ匕の方法はこの例に限らない 。また、要素情報がテキスト情報以外の属性を有するならば、その属性に合せた符号 化方法が用いられる。それらの詳細にっ 、てはここでは割愛する。
[0060] このように要素情報の値 61を圧縮符号ィ匕した後に圧縮情報形成部 106に与える、 または圧縮情報形成部 106において要素情報の値 61を圧縮符号ィ匕した後に圧縮 情報 708の形成に用いることで、圧縮情報 708のデータ量をより少なくできる。
[0061] ここで、図 3、図 7、および図 8を参照しながら、図 9と図 10を用いて本実施形態によ る具体的な符号化の例を示す。但し、上述したように、ここでは要素情報の符号化に ついては触れず、位置情報 62および対応情報 703の符号ィ匕を行なうとし、特に符号 化後の符号量にっ 、て評価する。
[0062] まず、差分符号化を行なわな!/ヽ通常の方式で位置情報 62を符号ィ匕した場合につ いて示す。図 7のテーブル 601の情報が検索時の補助情報となる。テーブル 601の 位置情報 62は位置情報が示す値の大小順に従 、並んで 、な 、ため、通常の方式 で符号化する。
[0063] 仮に、位置情報 62について 1つの階層の値を 5ビットで符号ィ匕すると、図 7に示され た位置情報 62は 3個の階層の値で示されるので、符号ィ匕するには 5 X 3 = 15ビット 力 つの位置情報 62を表すために必要となる。テーブル 601では位置情報 62が 6つ あるため、合計で 15 X 6 = 90ビットが、並替えを行なわない場合の位置情報 62にか かる符号量である（この場合、対応情報 703は不要である）。
[0064] なお、 1つの階層を表すのに必要なビットの数は、 1つ上の階層にある 1つの節 N ( 親ノード）に接続されてそこ力 分岐可能な節 N (子ノード)の数に依存しており、上記 5ビットは 2の 5乗個、すなわち 32個の分岐までが可能な場合を示す。実際の映像の 付加情報においては更に大きなビット数を必要とする。
[0065] 次に、特許文献 1に示された差分符号化による方法で位置情報 62を符号化した場 合について示す。ここでは、図 3のテーブル 60に示す順に並んだ位置情報 62を差 分符号化する。
[0066] 図 9は、本実施の形態に係る位置情報 62の差分符号化で用いられる符号 704の それぞれに対応して、その符号 704が示す意味 705のデータをテーブル形式で示 す。また図 10には、図 3の位置情報 62を符号ィ匕して得られる符号列 706を、符号ィ匕 される位置情報 62と対比する形で示す。位置情報符号ィ匕部 102は位置情報 62の符 号化の規則を示す符号化規則データ 709を有する。位置情報符号化部 102は、特 許文献 1に示された方法に従 、、符号ィ匕規則データ 709を参照して位置情報 62を 符号化する。すなわち、テーブル 60の先頭に格納された位置情報 62を通常の方法 で符号ィ匕した後、続いて格納されている位置情報 62について、どの階層で分岐した かを示す差分、即ちどの階層の値が更新 (インクリメント）されるかを符号 704で示し ていくことで、続く位置情報 62を符号ィ匕する。
[0067] 位置情報符号ィ匕部 102により図 3の位置情報 62を符号ィ匕した場合、次の様になる 。つまり、テーブル 60の先頭に格納された位置情報 62が 15ビット（1階層あたり 5ビッ ト X 3階層）で符号化されて（図 10の一番左の符号列 706を参照）、以降に格納され た 5つの位置情報 62については、 3ビットの符号 704で符号化されて図 10では符号 列 706として与えられる。このビット数' 3，は、く階層数〉 3 +く終了コード〉 1 +く 欠落コード〉 1 = 5を表すことが可能な最小ビット数 = 3ビットとして決められる。そし て最後に 3ビットの終了コードを示す符号 704 (図 10の一番右の符号列 706を参照） を加える。したがって、 15 + 3 X 6 = 33ビットで図 3のテーブル 60に格納されている すべての位置情報 62が差分符号化される（図 10参照)。
[0068] 次に、圧縮情報形成部 106では、図 10の符号列 706に、対応情報符号化部 105 により符号化された後の図 8 (B)に示された対応情報 703を加える。対応情報 703の 1つの位置情報 62に対応の情報 (数値）は、テーブル 60の位置情報 62の総数が 6 であることから、その総数値を表すことができる最小ビット数である 3ビットで符号ィ匕す ることができる。この総数値は、位置情報符号ィ匕部 102の位置情報 62の符号ィ匕によ つて圧縮情報に含められる。そして、テーブル 60の位置情報 62の個数と同じく 6個 の対応情報 703を符号ィ匕するために、対応情報符号ィ匕部 105により、 3 X 6 = 18ビッ トで図 8 (B)の対応情報 703は符号化される。従って総ビット数は、位置情報符号量 の 33ビット +対応情報符号量の 18ビット = 51ビットである。
[0069] このように、差分符号化を行なわな!/、で位置情報 62を符号ィ匕した場合の符号量は 90ビットであるのに対して、位置情報 62の差分符号ィ匕および対応情報 703の符号 化を行なった場合の符号量が 51ビットであるから、本実施形態のように差分情報およ び対応情報 703によって位置情報 62を符号ィ匕する方が、差分符号ィ匕しない従来方 式に比べて符号量を少なくできる (圧縮率を高くできる)。上記数値は一例であるが、 符号ィ匕の対象となる位置情報 62の個数、あるいは位置情報 62が示す階層数が増え るとその圧縮効果は更に顕著になる。また、上記で示した対応情報 703の符号ィ匕方 法は一例であり、これに限らず、更に効率の高い符号ィ匕方法が適用されてもよい。対 応情報 703を更に効率の高い符号ィ匕方法で符号ィ匕することにより圧縮効果は更に 顕著になる。
[0070] 図 11には、本実施の形態でテーブル形式の情報が符号化された圧縮情報のデー タ構造例が概略的に示される。図 11 (A)は図 4 (B)のデータを符号ィ匕した圧縮情報 のデータ構造を示し、図 11 (B)は図 5 (B)のデータを符号ィ匕した圧縮情報のデータ 構造を示している。図 11のそれぞれのテーブルにおいて、連続する複数の位置情 報が、「位置情報符号列」および「対応情報符号列」に置き換わっている。既に説明 した通り、本実施形態では要素情報の値 61の符号ィ匕については詳しく言及しないた め、要素情報の値（値 Al、値 A2、 · · ·、値 Bl、値 B2、 · · -)については、図 4 (B)と図 5 (B)のものをそのまま図 11に図示している。但し、これらは各々符号化されて記録さ れているとしてもよい。あるいは、差分符号化等を適用し、連続する複数の要素情報 の値 61を「値符号列」に置き換えた形で圧縮情報が構成されるとしてもよい。なお、 図 11のテーブル 641と 661では、要素情報の値 61 (または要素情報の値 61への参 照情報 67)を先に、位置情報符号列 68および対応情報符号列 69を後に配置した データ構造を有するが、位置情報符号列 68および対応情報符号列 69を先に、要素 情報の値 61 (または要素情報の値 61への参照情報 67)を後に配置するデータ構造 を有するとしてもよい。また、位置情報符号列 68と対応情報符号列 69についてもど ちらが先に配置されてもよいし、位置情報符号列 68と対応情報符号列 69の間に要 素情報の値 61 (または要素情報の値 61への参照情報 67)が挟まれるように配置され てもよい。
[0071] (情報テーブル復号装置の動作）
次に、本実施形態に力かる情報テーブル復号装置 2の動作について図 12のフロー チャートを参照して説明する。
[0072] 圧縮情報分離部 201は、受理部 207により圧縮情報 708を入力して (ステップ S (以 下、単に Sと略す) 20)入力した圧縮情報 708から位置情報 62の符号列 80、対応情 報 703の符号列 81および要素情報の値 61 (もしくは要素情報の値 61の符号列 82) を分離して出力する（S21)。
[0073] 位置情報復号部 202は、圧縮情報分離部 201から出力された位置情報 62の符号 列 80を受取り、受取った符号列 80を特許文献 1に示された手順に従い、テーブル 7 0を参照して差分復号する (S22)。差分復号は、差分符号化方法により符号化され たデータを復号することを指す。
[0074] 差分復号の過程を、図 10を参照して説明する。まず、位置情報 62の符号列 706の 先頭の 15ビットを読込んで解釈して、テーブル 60の先頭に格納された位置情報（ 1 , 1, 1)が復号される。次に、以降の位置情報 62の符号列 706から 3ビットずつ符号 70 4を順に読込んで解釈する。最初の 3ビットの位置情報 62の符号 704「011」は、図 9 のテーブル 707を参照すると出演者の階層での分岐 (更新)を示す符号であると解 釈される。従って先頭（1番目）に復号された位置情報（1, 1, 1)について出演者階 層の値を 1更新し、 2番目の位置情報（1, 1, 2)を得る。次の位置情報符号 704も「0 11」であるから、 3番目の位置情報は（1, 1, 3)である。次に読込まれる位置情報符 号 704は「010」で、図 9のテーブル 707を参照するとサブシーン階層での分岐（更 新)を示す符号であると解釈される。またこの時、サブシーン階層で分岐が起こると、 それより下位のノード、本例では出演者のノードは別のサブシーンの下に付く要素と なるため、値は 1からカウントし直される。従って、サブシーン階層の値は 1更新され、 出演者階層の値は 1に戻されるため、 4番目の位置情報は（1, 2, 1)となる。以下同 様に処理することで（1, 2, 2)、 (2, 1, 1)が復号結果として得られる。最後に位置情 報符号 704「000」が読み込まれる。これは図 9のテーブル 707を参照すると、復号終 了を指示する終了コードであると解釈されるので、該終了コードが読込まれたことに 応答して復号は終了する。
[0075] 上述した手順に従えば、位置情報復号部 202から出力される復号された複数の位 置情報 62は、当該位置情報 62の値の大小順に従って（図 3のテーブル 60の先頭か ら格納される値の順で）出力される。
[0076] 対応情報復号部 203は、対応情報 703の符号列 81を圧縮情報分離部 201から受 取り、受取った符号列 81を対応情報 703に復号して出力する（S23)。
[0077] 位置情報並替部 204は、対応情報復号部 203から出力された復号結果である対 応情報 703を入力するとともに、位置情報復号部 202から出力された復号結果であ る位置情報 62の値を入力する。そして、入力した位置情報 62の値の並び順を入力 した対応情報 703に基づいて並替える（S24)。
[0078] 例えば、図 3のテーブル 60に示した順に復号された位置情報 62の値に対して、図 8 (B)の対応情報 703が復号されているとする。この時、位置情報並替部 204は、復 号された対応情報 703に示された数値が示す順番に従い復号された (入力した)位 置情報 62を並べる。まず、復号された図 8 (B)の対応情報 703の 1番目の値' 1 'に基 づき、 1番目に復号された位置情報（1, 1, 1)が 1つめの位置情報 62と決まり出力さ れる。次に、対応情報 703の 2番目の値' 4'に基づき、 4番目に復号された位置情報 (1, 2, 1)が 2つめの位置情報 62と決まり出力される。次は、対応情報 703の 3番目 の値' 5'に基づき、 5番目に復号された位置情報（1, 2, 2)が 3つめの位置情報 62と 決まり出力される。同様にして対応情報 703の値' 2'、 '6'および' 3'のそれぞれに ついて、対応する位置情報（1, 1, 2)、 (2, 1, 1)、 (1, 1, 3)が 4つめ、 5つめ、 6つ めの位置情報 62とそれぞれ決まり出力される。このように、順に位置情報 62が決まつ て出力される。
[0079] 最後に、テーブル形成部 205は、圧縮情報分離部 201から出力された要素情報の 値 61と位置情報並替部 204から上述の順番で出力された位置情報 62とを対応する 形に並べて、図 7に示すように要素情報の値 61が辞書順に並んだテーブル 601を 形成して出力する（S25)。
[0080] 情報テーブル復号装置 2は、伝送または蓄積時において圧縮符号ィ匕されたテープ ル 60の情報 708を復号し、検索時の補助情報として復号後のテーブル 601を提供 する。例えば、情報テーブル復号装置 2は、付加情報に基づく検索機能を持ったュ 一ザの情報端末上に実装されて、伝送路を通して該情報端末が受信した圧縮情報 7 08 (検索時の補助情報となるテーブル 601を圧縮符号ィ匕した情報)を復号するため に用いられる。復号により形成されたテーブル 601は、位置情報 62が大小順力も要 素情報 61と対応した順に並替えられ、かつ要素情報の値 61が辞書順に並んだもの であり、復号して以降、ユーザはこのテーブル 601を用いて所望要素情報の検索を 行ない、必要な部分木 (フラグメント）を決定し、対応するフラグメントを入手する。これ は、情報管理装置力も出力されたテーブル 601を用いてユーザが検索を行なう際に 、辞書順で扱う方が検索に有利、即ち効率の良い高速な検索が可能なためである。
[0081] 図 12では、位置情報 62の復号処理を対応情報 703の復号よりも先に行なうように しているが、どちらの復号処理が先に行なわれても、あるいは同時に並行して処理さ れるとしても構わない。
(第 2の実施の形態）
本発明の第 2の実施形態にかかる情報管理装置を、図 13、図 14および図 15を参 照して説明する。第 2の実施形態にかかる情報管理装置は、情報テーブル符号化装 置ならびに情報テーブル復号装置からなる。このうち、情報テーブル復号装置につ いては、第 1の実施形態に力かる図 2の情報テーブル復号装置 2と同一であるため、 本実施形態では説明を省略する。
[0082] 図 13は、本発明の第 2の実施形態に力かる情報管理装置のうち、情報テーブル符 号化装置 10の機能ブロック図である。情報テーブル符号化装置 10は、受理部 907 を有するテーブル分離部 901、位置情報符号化部 902、対応情報抽出部 904を有 する位置情報並替部 903、対応情報符号ィ匕部 905および圧縮情報形成部 906を備 える。このうち、受理部 907を有するテーブル分離部 901、位置情報符号化部 902、 対応情報符号化部 905および圧縮情報形成部 906については、第 1の実施形態で 図 1に示す受理部 107を有するテーブル分離部 101、位置情報符号化部 102、対 応情報符号ィ匕部 105および圧縮情報形成部 106と同一機能を有するので、本実施 形態では以下、第 1の実施形態との相違箇所を主に説明する。
[0083] 先の第 1の実施形態では、図 17の映像の付加情報力も所定種別の要素情報のみ を抜出してテーブル 60を形成する際、木構造を上位階層から下位階層に、かつ同 一階層は木の左から右に順に走査しながら木構造内での出現順に該所定種別の要 素情報を抜出しテーブル 60に順に並んで格納されることを前提としていた（図 3参照 )。このため、第 1の実施形態の情報テーブル符号化装置 1 (図 1参照）は、テーブル 60から要素情報の値 61を含む各種情報を分離して出力して以降は、検索時の補助 情報として扱う形式に合せて、分離出力された要素情報の値 61を辞書順に並替える 機能部、即ち要素情報並替部 103を備えていた。
[0084] これに対して、第 2の実施形態では、図 17の映像の付加情報力も所定種別の要素 情報の値 61を抜出してテーブル 60を形成する際に、予め木構造全体を走査し、該 所定種別の要素情報の値 61を抜出す段階で、辞書順に並ぶように抜出してテープ ル 60が形成されるものとする。即ち、図 7に示したような、要素情報の値 61が辞書順 に並んだテーブル 601が、第 2の実施形態における情報テーブル符号化装置 10 (図 13参照）の入力とされる。この場合、要素情報の値 61は既に辞書順に並んでいるた め、第 1の実施形態にあった要素情報並替部 103は情報テーブル符号化装置 10で は不要となる。一方、位置情報 62は入力するテーブル 601では位置情報が示す値 の大小順に並んでいない。このため、本実施形態における情報テーブル符号ィ匕装 置 10 (図 13)は、位置情報 62を差分符号ィ匕するために、位置情報 62が示す値 (数 値)の大小順に並替える機能部、即ち位置情報並替部 903を備える。
[0085] 動作を図 13を参照しながら、図 6のフローチャートに従い説明する。
まず、受理部 907によりテーブル 601が入力される（S10)。テーブル分離部 901は 入力したテーブル 601から要素種別の値 61と位置情報 62を読出し、分離して出力 する（Sl l)。
[0086] 位置情報並替部 903は、テーブル分離部 901から出力された複数の位置情報 62 を入力して、入力した複数の位置情報 62を、それぞれが示す数値の大小順に並替 えた後に位置情報符号ィ匕部 905に出力する（S 12)。またこの時、位置情報並替部 9 03の内部の対応情報抽出部 904は、位置情報 62がどう並替えられたかを検出し、 検出結果に基づき要素情報の値 61と並替え後の位置情報 62との対応関係を示す 対応情報 703を入力情報力も抽出して出力する（S13)。
[0087] 図 14および図 15には、位置情報 62の並替え処理時に位置情報 62から対応情報 703を抽出（生成)する方法が示される。図 14 (A)では、入力された（図 7のテーブル 601から読出した)複数の位置情報 62に対し、各位置情報 62にそれが示す値 (数値 )の小さい順に通し番号を振って、要素情報の値 61と並替え後の位置情報 62との対 応情報 703 (図 14 (B)参照）を求める例が示される。
[0088] 但し、図 14 (A)の例では、位置情報 62に通し番号を割振る段階で数値の大小判 定を逐一行なうことが必要であるから、例えば、図 14 (A)の処理手順には既存のソー トアルゴリズムを利用した高速な並替え処理はうまく適合しない。そこで、既存の高速 な並替え処理を効果的に活用しょうとしたのが図 14 (C)の例である。図 14 (C)では、 位置情報 62にテーブル 601で並んで 、る順に通し番号を割振る処理を 2回 (ステツ プ S1401と S1403参照）と、位置情報 62をそれが示す値の大小順に並替えるソート 処理を 2回 (ステップ S 1402と S 1404参照）行なう。その結果、図 14 (D)の対応情報 703が出力される。
[0089] また、図 15には、階層毎の位置情報 62の値の出現個数に基づいて、対応情報 70 3を計算で求める方法が示される。この方法ではまず、図 15 (A)に示すように、位置 情報 62の値 (数値)の大小順に並替えを行ない (ステップ S1501)、その後、並替え された位置情報 62の各階層の各値の出現個数を上位の階層から順にカウントする（ ステップ S1502)。その結果、最上位層（シーン階層）で値' 1，の個数は 5個、値' 2， の個数は 1個である。また最上位層の値' 1 'である 5個の位置情報 62のうち、第 2階 層（サブシーン階層）で値' 1 'の個数は 3個、値' 2'の個数は 2個とカウントされる。次 に、各々の階層のある値の出現個数から、その値が出現する前までに出現している 位置情報 62の個数を累積数 Cxxxとして求める（ステップ S 1503)。
[0090] S1502の処理に従えば、最上位層（シーン階層）で値' 1 'が初めて出現するより前 に存在する位置情報 62は無い。従って累積数 Clxxは 0である。最上位層（シーン階 層）で値' 2'が初めて出現する前には、値' 1 'をとる位置情報 62が 5個存在する。従 つて累積数 C2xxは 5である。同様に、最上位層の値' 1 'である 5個の位置情報 62うち 、第 2階層（サブシーン階層）で値 ' 1，が初めて出現する位置情報 62より前に存在す る位置情報は無い。従って累積数 Cllxは 0である。最上位層の値が' 1 'である 5個の 位置情報 62のうち、第 2階層で値' 2'が初めて出現する位置情報 62より前において は、第 2階層で値' 1 'をとる位置情報 62が 3個存在する。従って累積数 C12xは 3であ る。 [0091] こうして、ステップ SI 503に示すようにそれぞれの累積数 Cxxxが得られたら、図 15 (B)に示すように、並替え前の位置情報 62それぞれに対して、各階層の値に対応す る累積数 Cxxxの総和を求める（ステップ S 1504)。次に、ステップ S 1504で得られた 各総和は、対応の位置情報 62より前に存在する位置情報 62の個数を表しているた め、最後に、その位置情報 62自身をカウントするために' 1 'を対応の総和に加える（ ステップ S1505)。これにより、図 15 (C)の対応情報 703が出力される。
[0092] 無論、対応情報 703はここに示した位置情報 62に割振りされる通し番号で与えら れるものに限らず、位置情報 62の並替えがどのように行なわれたかを示すことが可 能な情報であればよい。また、通し番号に基づく対応情報 703であっても、対応の付 け方ならびに対応情報 703の抽出方法はここで示したものに限らず様々な方法が可 能である。
[0093] 以降の位置情報符号化部 902の位置情報 62の差分符号化 (S 14)、対応情報符 号化部 905の対応情報 703の符号化 (S15)、および圧縮情報形成部 906の圧縮情 報の形成 (S16)については、第 1の実施形態で記載した内容がそのまま第 2の実施 形態にも当てはまる。従って、ここでは重複した説明を省略する。
[0094] 要素情報の値 61が上述の各実施の形態で示したようなテキスト情報で示されな 、 場合にも、上述した情報管理装置および方法は適用可能である。このように本発明 では、伝送または蓄積の対象とされるテーブル 60 (または 601)中の要素情報の値 6 1と位置情報 62とが、更に一般化すれば、テーブル 60 (または 601)のようにして管 理される複数の 1つめの要素と対応する複数の 2つめの要素とが、それぞれ異なる順 序関係に従って並べたときに検索効率が最大となる、もしくは符号ィ匕効率が最大とな るといった特性をもっている場合に、何れか一方の要素の特性に適した順序に双方 の要素を並べた後、もう一方の要素をその特性に適した順序に並替える。それととも に、並替え後の 2つの要素間での対応関係を示す対応情報を生成し並べ替えた双 方の要素に付加することで、双方の要素をそれぞれの特性に適した順序に並んだ形 で扱えるようにしたことに特徴がある。そして、第 1および第 2の実施の形態で示したよ うに、 1つめの要素が検索効率を最大化する順序に、 2つめの要素が符号化効率を 最大化する順序に並んだ形で伝送または蓄積の対象となる情報を形成したとすれば 、形成された情報は、符号ィ匕効率と検索効率とを両立させることが可能な情報となる
。この他、 1つめの要素、 2つめの要素それぞれが異なる順序関係に従って並べたと きにそれぞれ符号化効率が最大となる場合や、 1つめの要素、 2つめの要素それぞ れが異なる順序関係にしたがって並べたときに、それぞれ検索効率が最大となる場 合もある。
[0095] (第 3の実施の形態）
上述した実施形態 1と 2にかかる情報管理の手順はプログラムに基づいて実行され る。図 16は、実施形態 1と 2の情報管理装置に対応する装置のハードウェアの概略 構成図である。図 16の装置はコンピュータの構成を有する。具体的には、図 16の装 置は、装置の各部を集中的に制御および監視するための CPU (Central Processing Unit) 1601、各種プログラムとデータを格納するための ROM (Read Only Memor y) 1602、 RAM (Random Access Memory) 1603、 HDD (Hard Disk Drive) 160 4、 DVD (Digital Versatile Disk)やメモリカードなどの外部記録デバイスと接続する ためのインターフェース 1605、インターネットを含む各種の通信ネットワーク 1614と 接続するための通信デバイス 1606、キーボード、マウス、ボタンなど力もなる入力部 1607、映像の表示、音声の出力、文字の表示などをするための出力部 1608、着脱 自在に装着される FD (flexible Disk) 1610をアクセスするための FD駆動部、着脱自 在に装着される CD (Compact Disk) 1612をアクセスするための CD駆動部 1611お よびこれら各部間の通信を可能とするためのバス 1613を備える。
[0096] 第 1の実施形態において、情報テーブル符号化時には、 ROM1602、 RAM 1603 、または HDD1604に予め格納されたテーブル分離部 101に対応のテーブル分離 プログラム、位置情報符号ィ匕部 102に対応の位置情報符号ィ匕プログラム、要素情報 並替部 103および対応情報抽出部 104に対応の要素情報並替えおよび対応情報 抽出プログラム、対応情報符号化 B105に対応の対応情報符号化プログラム、圧縮 情報形成部 106に対応の圧縮情報形成プログラムが CPU 1601〖こより CPU 1601の 図示のない所定記憶領域にロードされる。そして、 CPU1601がロードされた各プロ グラムの命令を解釈し実行することで、以下の動作が行なわれる。この時、位置情報 62と要素情報の値 61とからなるテーブル 60は、予め生成されて RAM1603または HDD1604に格納されている。図 9のテーブル 707、および符号化規則データ 709 は CPU 1601が参照可能な情報として ROM 1602に予め格納される。
[0097] まず、 CPU1601は、ロードされたテーブル分離プログラムに従い、 RAM1603ま たは HDD1604に既に格納されているテーブル 60を読出して、読出したテーブル 6 0から位置情報 62を抽出してテーブル 60から分離する（読出す)。そして、分離した 位置情報 62をロードされた位置情報符号ィ匕プログラムに従い符号ィ匕して、符号化さ れた位置情報 62を RAM1603または HDD1604に一時的に格納する。また、 RAM 1603または HDD 1604に既に格納されているテーブル 60から要素情報の値 61を 抽出してテーブル 60から分離する（読出す)。そして、分離された要素情報の値 61を 、ロードされた要素情報並替えおよび対応情報抽出プログラムに従い並替えるととも に対応情報 703を抽出（生成)して、並替え後の要素情報の値 61と抽出した対応情 報 703を RAM1603または HDD1604に一時的に格納する。更に、対応情報 703 をロードされた対応情報符号ィ匕プログラムに従 ヽ符号ィ匕して、符号化された対応情 報 703を RAM1603または HDD1604に一時的に格納する。最後に、ロードされた 圧縮情報形成プログラムに従い、符号化された位置情報 62および対応情報 703、な らびに並替え後の要素情報の値 61を用いて圧縮情報 708を形成し、形成した圧縮 情報 708を RAM1603または HDD1604に格納する。
[0098] この圧縮情報 708は、テーブル 60の情報の効率的な蓄積および伝送のために活 用され、インターフェース 1605により接続された外部記録デバイスの記録媒体を介し て、あるいは、通信デバイス 1606で接続された通信ネットワーク 1614を通して、ある いは FD駆動部 1609により FD1610を介して、あるいは CD駆動部 1611により CD1 612を介して、他の情報テーブル復号機能を持つ機器に提供される。
[0099] 前述の第 1の実施形態において、情報テーブル復号時には、 ROM1602、 RAMI 603、または HDD1604に予め格納された圧縮情報分離部 201に対応の圧縮情報 分離プログラム、位置情報復号部 202に対応の位置情報復号プログラム、対応情報 復号部 203に対応の対応情報復号プログラム、位置情報並替部 204に対応の位置 情報並替えプログラム、およびテーブル形成部 205に対応のテーブル形成プロダラ ムが CPU1601により、 CPU1601の所定記憶領域にロードされ、 CPU1601はロー ドされたプログラムの命令を解読して実行することで、以下の動作が実現される。この 時、圧縮情報 708は、記録媒体を介してインターフェース 1605から、あるいは通信ネ ットワーク 1614を通して通信デバイス 1606から得られて、予め RAM1603または H DDI 604【こ格糸内されて!ヽる。
[0100] CPU1601は、 RAM1603または HDD1604に格納されている圧縮情報 708から 、ロードされた圧縮情報分離プログラム 201に従い要素情報の値 61を分離して、分 離した要素情報の値 61を RAM 1603または HDD 1604に一時的に格納する。また 、圧縮情報 708から符号化された位置情報 62を圧縮情報分離プログラム 201に従 V、分離し、分離した位置情報 62をロードされた位置情報復号プログラムに従 、復号 して、復号された位置情報 62を RAM 1603または HDD 1604に一時的に格納する 。同様に、圧縮情報 708から符号化された対応情報 703を分離し、分離した対応情 報 703をロードされた対応情報復号プログラムに従い復号して、復号された対応情 報 703を RAM1603または HDD1604に一時的に格納する。次に、復号された位 置情報 62を、ロードされた位置情報並替えプログラムに従い、復号された対応情報 7 03に基づいて並替えて、並替え後の位置情報 62を RAM1603または HDD1604 に一時的に格納する。最後に、ロードされたテーブル形成プログラムに従い、要素情 報の値 61と (復号および並替え処理後の）位置情報 62とを用いてテーブル 601を形 成して、形成したテーブル 601を RAM 1603または HDD 1604に格納する。
[0101] このテーブル 601は、付加情報による検索実行時の補助情報として活用される。ま たは、インターフェース 1605により接続された外部記録デバイスの記録媒体を介し て、あるいは、通信デバイス 1606で接続された通信ネットワーク 1614を通して、ある いは FD駆動部 1609により FD1610を介して、あるいは CD駆動部 1611により CD1 612を介して、他の検索機能を持つ機器に提供されるとしてもよい。
[0102] また、前述の第 2の実施形態において、情報テーブル符号ィ匕時には、 ROM1602 、 RAM1603、または HDD1604に格納された、テーブル分離部 901に対応のテー ブル分離プログラム、位置情報並替部 903および対応情報抽出部 904に対応の位 置情報並替えおよび対応情報抽出プログラム、対応情報符号化部 905に対応の対 応情報符号ィ匕プログラム、位置情報符号ィ匕部 902に対応の位置情報符号ィ匕プログ ラム、圧縮情報形成部 906に対応の圧縮情報形成プログラムが CPU1601により、 C PU1601の所定記憶領域にロードされる。 CPU 1601は該所定記憶領域から各プロ グラムの命令を読出し、解釈し実行することで以下の動作が実現される。この時、位 置情報 62と要素情報の値 61とからなるテーブル 60 (または 601)は、予め生成され て RAM 1603または HDD 1604に格納されている。符号化規則データ 709は CPU 1601が参照可能な情報として ROM 1602に予め格納される。
[0103] CPU1601は、ロードされているテーブル分離プログラムに従い、 RAM1603また は HDD 1604に既に格納されて 、るテーブル 60 (または 601 )力も位置情報 62を分 離する (読出す)。次に、分離した位置情報 62をロードされた位置情報並替えおよび 対応情報抽出プログラムに従い並替えおよび対応情報 703を抽出（生成)して、並替 え後の位置情報 62と抽出した対応情報 703を RAM1603または HDD1604に一時 的に格納する。また、ロードされているテーブル分離プログラムに従い、 RAM 1603 または HDD1604に既に格納されているテーブル 60 (または 601)力も要素情報の 値 61を分離 (読出）して、分離した要素情報の値 61を RAM 1603または HDD 1604 に一時的に格納する。並替え後の位置情報 62は、ロードされた位置情報符号ィ匕プロ グラムに従い符号ィ匕して、符号ィ匕された位置情報 62を RAM1603または HDD160 4に一時的に格納する。同様に、対応情報 703は、ロードされた対応情報符号化プロ グラムに従い符号ィ匕して、符号ィ匕された対応情報 703を RAM1603または HDD16 04に一時的に格納する。最後に、ロードされた圧縮情報形成プログラムに従い、符 号化された位置情報 62および対応情報 703、ならびに要素情報の値 61を用いて圧 縮情報 708を形成して、形成した圧縮情報 708を RAM 1603または HDD 1604に 格納する。
[0104] この圧縮情報 708は、テーブル形式の情報の効率的な蓄積および伝送のために 利用され、インターフェース 1605により接続された外部記録デバイスの記録媒体を 介して、あるいは、通信デバイス 1606で接続された通信ネットワーク 1614を通して、 あるいは FD駆動部 1609により FD1610を介して、あるいは CD駆動部 1611により C D1612を介して、他の情報テーブル復号機能を持つ機器に提供される。
[0105] 前述の第 2の実施形態における情報テーブル復号時の CPU1601の動作は、既に 説明した第 1の実施形態における情報テーブル復号時における動作と同じであるた め、説明を省略する。
[0106] 上述の情報テーブル符号化処理は、符号ィ匕するテーブル 60を決定して以降は、 あるいは復号処理は復号装置が圧縮情報 708を受取って以降は、それぞれ、基本 的にユーザからの何らの指示または情報の入力がなくても自動で実行される。但し、 これに限らず、例えば、図 16の装置において、符号化 Z復号の指示を入力部 1607 を通してユーザが任意に与えたり、 CPU 1601は符号化 Z復号処理の実行中の動 作状況を出力部 1608を介してユーザに提示したり、といった動作を実行させることも 可能である。
[0107] 第 3の実施形態では、情報管理を実行する各種プログラムが、図 16の装置内の R OM1602、 RAM1603、または HDD1604に格納されているとした力 これに限定 されず、コンピュータ読取可能な外部の記録媒体に記録されて、プログラム実行時に インターフェース 1605を通してメモリにロードするといつた構成で実施することもでき る。外部の記録媒体としては、図示のない磁気テープ、 CD—ROMZRZRW、 DV D-ROM/RAM/R/RW, MO (magneto— optic)、 SD (Secure Digital)メモリ力 ード、 FD (Flexible Disk)などがある。また、通信ネットワーク 1614を経由して伝送さ れたこれらプログラムを通信デバイス 1606により受信して ROM 1602、 RAM 1603 、または HDD 1604に格納されるとしてもよい。
[0108] 第 1〜第 3の実施の形態では、検索用の補助情報とされるテーブル 60 (または 601 )を圧縮符号化する際に、要素情報 61 (テキスト情報)は辞書順に並替えて保持し、 一方、対応する各葉 Rの位置情報 62は木構造中での出現順 (数値の大小順）に基 づいて差分符号化すると共に、これら情報に対して、位置情報と並替え後の要素情 報 (または要素情報と並べ替え後の位置情報)との対応関係を示す対応情報 703を 符号化して付加した。これにより、差分符号化を用いることでテーブル 60に含まれる 位置情報を効率的に符号ィ匕することができ、かつ要素情報 61は辞書順に並べられ ることで高 、検索効率を得ることが可能となった。
[0109] 今回開示された実施の形態はすべての点で例示であって制限的なものではないと 考えられるべきである。本発明の範囲は上記した説明ではなくて請求の範囲によって 示され、請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが 意図される。

Claims

請求の範囲
[1] 要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成 される情報の符号化装置（1)であって、
所定種別の要素情報と、該所定種別の要素情報が付された前記葉の前記木構造 における前記規定順序に従う位置を示す位置情報と含んだ複数の組を、前記規定 順序に従い並んで有する情報群を受理する手段（107)と、
前記受理する手段により受理した前記情報群の前記複数の組から複数の前記要 素情報を分離して、分離した前記複数の要素情報を前記所定種別の前記要素情報 の検索に適した所定の順序に従い並替える並替え手段（101、 103)と、
前記並替え手段による、前記規定順序から前記所定順序への並替えによる前記複 数の要素情報の順番の変化に基づき、並替え後の前記複数の要素情報それぞれと 、前記受理する手段により受理した前記情報群の中の該要素情報と同一 の前記 位置情報との対応関係を示す対応情報を生成する対応情報生成手段（104、 105) と、
前記受理する手段により受理した前記情報群の前記複数の組から複数の前記位 置情報を分離して、分離した前記複数の位置情報を符号ィヒする位置情報符号ィ匕手 段（102)と、
前記位置情報符号化手段により符号化された前記複数の位置情報と、前記対応 情報生成手段により生成された前記対応情報と、前記並替え手段による並替え後の 前記複数の要素情報とを含めた所定情報を形成する所定情報形成手段（106)とを 備える、符号化装置。
[2] 前記位置情報符号化手段は、前記複数の位置情報それぞれを、
該位置情報と、当該位置情報が示す位置の前記規定順序に従う直前の位置を示 す位置情報との差分に基づき符号化することを特徴とする、請求項 1に記載の符号 化装置。
[3] 前記対応情報生成手段は、
前記対応関係を示す情報を符号化することにより前記対応情報を生成する対応情 報符号化手段（105)を含む、請求項 1に記載の符号化装置。 [4] 前記所定情報形成手段による前記所定情報の形成に先立って、前記要素情報は 符号化されることを特徴とする、請求項 1に記載の符号化装置。
[5] 前記木構造力 なる情報は映像データを検索するための情報であることを特徴とす る、請求項 1に記載の符号化装置。
[6] 要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成 される情報の符号化装置（10)であって、
所定種別の要素情報と、該所定種別の要素情報が付された前記葉の前記木構造 における前記規定順序に従う位置を示す位置情報と含んだ複数の組を、前記所定 種別の前記要素情報の検索に適した所定順序に従い並んで有する情報群を受理 する手段（907)と、
前記受理する手段により受理した前記情報群の前記複数の組から複数の前記要 素情報を分離して出力する要素情報分離手段 (901)と、
前記受理する手段により受理した前記情報群の前記複数の組から複数の前記位 置情報を分離して、分離した前記複数の位置情報を、前記規定順序に従い並替える 位置情報並替手段 (903)と、
前記位置情報並替手段の並替えによる前記複数の位置情報の順番の変化に基づ き、並替え後の前記複数の位置情報それぞれと、前記受理する手段により受理した 前記情報群の中の該位置情報と同一組の前記要素情報との対応関係を示す対応 情報を生成する対応情報生成手段（904、 905)と、
前記位置情報並替手段により並替えられた前記複数の位置情報を符号ィ匕する位 置情報符号化手段 (902)と、
前記位置情報符号化手段により符号化された前記複数の位置情報と、前記対応 情報生成手段により生成された前記対応情報と、前記要素情報分離手段から出力さ れた前記複数の要素情報とを含めた所定情報を形成する所定情報形成手段 (906) とを備える、符号化装置。
[7] 前記位置情報符号化手段は、前記複数の位置情報それぞれを、
該位置情報と、当該位置情報が示す位置の前記規定順序に従う直前の位置を示 す位置情報との差分に基づき符号化することを特徴とする、請求項 6に記載の符号 化装置。
[8] 前記対応情報生成手段は、
前記対応関係を示す情報を符号化することにより前記対応情報を生成する対応情 報符号化手段 (905)を含む、請求項 6に記載の符号化装置。
[9] 前記所定情報形成手段による前記所定情報の形成に先立って、前記要素情報は 符号化されることを特徴とする、請求項 6に記載の符号ィ匕装置。
[10] 前記木構造力 なる情報は映像データを検索するための情報であることを特徴とす る、請求項 6に記載の符号化装置。
[11] 要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成 される所定情報の復号装置 (2)であって、
所定種別の前記要素情報の検索に適した所定順序で並んだ前記所定種別の複 数の要素情報と、当該複数の要素情報が付された複数の葉の前記木構造における 前記規定順序に従う位置を示す符号化された複数の位置情報と、前記所定順序で 並んだ複数の要素情報それぞれと当該要素情報が付された前記葉の前記規定順序 に従う位置を示す符号化された前記複数の位置情報との対応関係を示す対応情報 と、を含んで形成された所定情報を受理する所定情報受理手段 (207)と、
前記所定情報受理手段により受理した前記所定情報から、前記複数の要素情報と 、符号化された前記複数の位置情報と、前記対応情報とを分離して出力する分離手 段（201)と、
前記分離手段力も出力された符号化された前記複数の位置情報を入力して、入力 した前記複数の位置情報を復号する位置情報復号手段 (202)と、
前記分離手段から出力された前記対応情報を入力して、入力した前記対応情報に 基づき、前記位置情報復号手段により復号された前記複数の位置情報を前記所定 順序に従!、並替える並替え手段（204)と、
前記並替え手段による並替え後の前記複数の位置情報それぞれと、前記分離手 段力 入力した前記所定順序で並んだ前記複数の要素情報それぞれとが対応付け された情報を生成して出力する手段 (205)を備える、復号装置。
[12] 前記木構造力 なる情報は映像データを検索するための情報であることを特徴とす る、請求項 11に記載の復号装置。
[13] 要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成 される情報の符号化方法であって、
所定種別の要素情報と、該所定種別の要素情報が付された前記葉の前記木構造 における前記規定順序に従う位置を示す位置情報と含んだ複数の組を、前記規定 順序に従 、並んで有する情報群を受理するステップ (S10)と、
前記受理するステップにおいて受理した前記情報群の前記複数の組から複数の前 記要素情報を分離して、分離した前記複数の要素情報を、前記所定種別の前記要 素情報の検索に適した所定の順序に従 、並替える並替えステップ（S 11、 S 12)と、 前記並替えステップによる、前記規定順序から前記所定順序への並替えによる前 記複数の要素情報の順番の変化に基づき、並替え後の前記複数の要素情報それぞ れと、前記受理するステップにおいて受理した前記情報群の中の該要素情報と同一 組の前記位置情報との対応関係を示す対応情報を生成する対応情報生成ステップ (S13)と、
前記受理するステップにより受理した前記情報群の前記複数の組から複数の前記 位置情報を分離して、分離した前記複数の位置情報を符号ィ匕する位置情報符号ィ匕 ステップ（S 14)と、
前記位置情報符号化ステップにより符号化された前記複数の位置情報と、前記対 応情報生成ステップにより生成された前記対応情報と、前記並替えステップによる並 替え後の前記複数の要素情報とを含めた所定情報を形成する所定情報形成ステツ プ (S16)とを備える、符号化方法。
[14] 要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成 される情報の符号化方法であって、
所定種別の要素情報と、該所定種別の要素情報が付された前記葉の前記木構造 における前記規定順序に従う位置を示す位置情報と含んだ複数の組を、前記所定 種別の前記要素情報の検索に適した所定順序に従い並んで有する情報群を受理 するステップと、
前記受理するステップにより受理した前記情報群の前記複数の組から複数の前記 要素情報を分離して出力する要素情報分離ステップと、
前記受理するステップにより受理した前記情報群の前記複数の組から複数の前記 位置情報を分離して、分離した前記複数の位置情報を、前記規定順序に従い並替 える位置情報並替ステップと、
前記位置情報並替ステップの並替えによる前記複数の位置情報の順番の変化に 基づき、並替え後の前記複数の位置情報それぞれと、前記受理するステップにより 受理した前記情報群の中の該位置情報と同一組の前記要素情報との対応関係を示 す対応情報を生成する対応情報生成ステップと、
前記位置情報並替ステップにより並替えられた前記複数の位置情報を符号ィ匕する 位置情報符号化ステップと、
前記位置情報符号化ステップにより符号化された前記複数の位置情報と、前記対 応情報生成ステップにより生成された前記対応情報と、前記要素情報分離ステップ から出力された前記複数の要素情報とを含めた所定情報を形成する所定情報形成 ステップとを備える、符号化方法。
要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成 される所定情報の復号方法であって、
所定種別の前記要素情報の検索に適した所定順序で並んだ前記所定種別の複 数の要素情報と、当該複数の要素情報が付された複数の葉の前記木構造における 前記規定順序に従う位置を示す符号化された複数の位置情報と、前記所定順序で 並んだ複数の要素情報それぞれと当該要素情報が付された前記葉の前記規定順序 に従う位置を示す符号化された前記複数の位置情報との対応関係を示す対応情報 と、を含んで形成された所定情報を受理する所定情報受理ステップ (S20)と、 前記所定情報受理ステップにより受理した前記所定情報から、前記複数の要素情 報と、符号化された前記複数の位置情報と、前記対応情報とを分離して出力する分 離ステップ（S21)と、
前記分離ステップ力も出力された符号化された前記複数の位置情報を入力して、 入力した前記複数の位置情報を復号する位置情報復号ステップ (S22)と、
前記分離ステップにより出力された前記対応情報を入力して、入力した前記対応 情報に基づき、前記位置情報復号ステップにより復号された前記複数の位置情報を 前記所定順序に従 ヽ並替える並替えステップ (S24)と、
前記並替えステップによる並替え後の前記複数の位置情報それぞれと、前記分離 ステップ力 入力した前記所定順序で並んだ前記複数の要素情報それぞれとが対 応付けされた情報を生成して出力するステップ (S25)を備える、復号方法。
[16] 要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成 される情報の符号ィ匕方法を、コンピュータに実行させるためのプログラムであって、 前記符号化方法は、
前記木構造における所定種別の要素情報と、該所定種別の要素情報が付された 前記葉の前記木構造における前記規定順序に従う位置を示す位置情報と含んだ複 数の組を、前記規定順序に従 、並んで有する情報群を受理するステップと、 前記受理するステップにおいて受理した前記情報群の前記複数の組から複数の前 記要素情報を分離して、分離した前記複数の要素情報を、前記所定種別の前記要 素情報の検索に適した所定の順序に従い並替える並替えステップと、
前記並替えステップによる、前記規定順序から前記所定順序への並替えによる前 記複数の要素情報の順番の変化に基づき、並替え後の前記複数の要素情報それぞ れと、前記受理するステップにおいて受理した前記情報群の中の該要素情報と同一 組の前記位置情報との対応関係を示す対応情報を生成する対応情報生成ステップ と、
前記受理するステップにより受理した前記情報群の前記複数の組から複数の前記 位置情報を分離して、分離した前記複数の位置情報を符号ィ匕する位置情報符号ィ匕 ステップと、
前記位置情報符号化ステップにより符号化された前記複数の位置情報と、前記対 応情報生成ステップにより生成された前記対応情報と、前記並替えステップによる並 替え後の前記複数の要素情報とを含めた所定情報を形成する所定情報形成ステツ プとを備える、符号ィ匕方法をコンピュータに実行させるためのプログラム。
[17] 要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成 される情報の符号ィ匕方法を、コンピュータに実行させるためのプログラムであって、 前記符号化方法は、
所定種別の要素情報と、該所定種別の要素情報が付された前記葉の前記木構造 における前記規定順序に従う位置を示す位置情報と含んだ複数の組を、前記所定 種別の前記要素情報の検索に適した所定順序に従い並んで有する情報群を受理 するステップと、
前記受理するステップにより受理した前記情報群の前記複数の組から複数の前記 要素情報を分離して出力する要素情報分離ステップと、
前記受理するステップにより受理した前記情報群の前記複数の組から複数の前記 位置情報を分離して、分離した前記複数の位置情報を、前記規定順序に従い並替 える位置情報並替ステップと、
前記位置情報並替ステップの並替えによる前記複数の位置情報の順番の変化に 基づき、並替え後の前記複数の位置情報それぞれと、前記受理するステップにより 受理した前記情報群の中の該位置情報と同一組の前記要素情報との対応関係を示 す対応情報を生成する対応情報生成ステップと、
前記位置情報並替ステップにより並替えられた前記複数の位置情報を符号ィ匕する 位置情報符号化ステップと、
前記位置情報符号化ステップにより符号化された前記複数の位置情報と、前記対 応情報生成ステップにより生成された前記対応情報と、前記要素情報分離ステップ から出力された前記複数の要素情報とを含めた所定情報を形成する所定情報形成 ステップとを備える、符号ィ匕方法をコンピュータに実行させるためのプログラム。
要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成 される所定情報の復号方法を、コンピュータに実行させるためのプログラムであって、 前記復号方法は、
所定種別の前記要素情報の検索に適した所定順序で並んだ前記所定種別の複 数の要素情報と、当該複数の要素情報が付された複数の葉の前記木構造における 前記規定順序に従う位置を示す符号化された複数の位置情報と、前記所定順序で 並んだ複数の要素情報それぞれと当該要素情報が付された前記葉の前記規定順序 に従う位置を示す符号化された前記複数の位置情報との対応関係を示す対応情報 と、を含んで形成された所定情報を受理する所定情報受理ステップと、
前記所定情報受理ステップにより受理した前記所定情報から、前記複数の要素情 報と、符号化された前記複数の位置情報と、前記対応情報とを分離して出力する分 離ステップと、
前記分離ステップ力も出力された符号化された前記複数の位置情報を入力して、 入力した前記複数の位置情報を復号する位置情報復号ステップと、
前記分離ステップにより出力された前記対応情報を入力して、入力した前記対応 情報に基づき、前記位置情報復号ステップにより復号された前記複数の位置情報を 前記所定順序に従 ヽ並替える並替えステップと、
前記並替えステップによる並替え後の前記複数の位置情報それぞれと、前記分離 ステップ力 入力した前記所定順序で並んだ前記複数の要素情報それぞれとが対 応付けされた情報を生成して出力するステップを備える、復号方法をコンピュータに 実行させるためのプログラム。
要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成 される情報の符号ィ匕方法を、コンピュータに実行させるためのプログラムを記録した 機械読取り可能な記録媒体であって、
前記符号化方法は、
所定種別の要素情報と、該所定種別の要素情報が付された前記葉の前記木構造 における前記規定順序に従う位置を示す位置情報と含んだ複数の組を、前記規定 順序に従い並んで有する情報群を受理するステップと、
前記受理するステップにおいて受理した前記情報群の前記複数の組から複数の前 記要素情報を分離して、分離した前記複数の要素情報を、前記所定種別の前記要 素情報の検索に適した所定の順序に従い並替える並替えステップと、
前記並替えステップによる、前記規定順序から前記所定順序への並替えによる前 記複数の要素情報の順番の変化に基づき、並替え後の前記複数の要素情報それぞ れと、前記受理するステップにおいて受理した前記情報群の中の該要素情報と同一 組の前記位置情報との対応関係を示す対応情報を生成する対応情報生成ステップ と、 前記受理するステップにより受理した前記情報群の前記複数の組から複数の前記 位置情報を分離して、分離した前記複数の位置情報を符号ィ匕する位置情報符号ィ匕 ステップと、
前記位置情報符号化ステップにより符号化された前記複数の位置情報と、前記対 応情報生成ステップにより生成された前記対応情報と、前記並替えステップによる並 替え後の前記複数の要素情報とを含めた所定情報を形成する所定情報形成ステツ プとを備える、符号ィ匕方法をコンピュータに実行させるためのプログラムを記録した機 械読取り可能な記録媒体。
要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成 される情報の符号ィ匕方法を、コンピュータに実行させるためのプログラムを記録した 機械読取り可能な記録媒体であって、
前記符号化方法は、
所定種別の要素情報と、該所定種別の要素情報が付された前記葉の前記木構造 における前記規定順序に従う位置を示す位置情報と含んだ複数の組を、前記所定 種別の前記要素情報の検索に適した所定順序に従い並んで有する情報群を受理 するステップと、
前記受理するステップにより受理した前記情報群の前記複数の組から複数の前記 要素情報を分離して出力する要素情報分離ステップと、
前記受理するステップにより受理した前記情報群の前記複数の組から複数の前記 位置情報を分離して、分離した前記複数の位置情報を、前記規定順序に従い並替 える位置情報並替ステップと、
前記位置情報並替ステップの並替えによる前記複数の位置情報の順番の変化に 基づき、並替え後の前記複数の位置情報それぞれと、前記受理するステップにより 受理した前記情報群の中の該位置情報と同一組の前記要素情報との対応関係を示 す対応情報を生成する対応情報生成ステップと、
前記位置情報並替ステップにより並替えられた前記複数の位置情報を符号ィ匕する 位置情報符号化ステップと、
前記位置情報符号化ステップにより符号化された前記複数の位置情報と、前記対 応情報生成ステップにより生成された前記対応情報と、前記要素情報分離ステップ から出力された前記複数の要素情報とを含めた所定情報を形成する所定情報形成 ステップとを備える、符号ィ匕方法をコンピュータに実行させるためのプログラムを記録 した機械読取り可能な記録媒体。
要素情報が付された複数の葉の間に、規定順序の関係を有する木構造により構成 される所定情報の復号方法を、コンピュータに実行させるためのプログラムを記録し た機械読取り可能な記録媒体であって、
前記復号方法は、
所定種別の前記要素情報の検索に適した所定順序で並んだ前記所定種別の複 数の要素情報と、当該複数の要素情報が付された複数の葉の前記木構造における 前記規定順序に従う位置を示す符号化された複数の位置情報と、前記所定順序で 並んだ複数の要素情報それぞれと当該要素情報が付された前記葉の前記規定順序 に従う位置を示す符号化された前記複数の位置情報との対応関係を示す対応情報 と、を含んで形成された所定情報を受理する所定情報受理ステップと、
前記所定情報受理ステップにより受理した前記所定情報から、前記複数の要素情 報と、符号化された前記複数の位置情報と、前記対応情報とを分離して出力する分 離ステップと、
前記分離ステップ力も出力された符号化された前記複数の位置情報を入力して、 入力した前記複数の位置情報を復号する位置情報復号ステップと、
前記分離ステップにより出力された前記対応情報を入力して、入力した前記対応 情報に基づき、前記位置情報復号ステップにより復号された前記複数の位置情報を 前記所定順序に従 ヽ並替える並替えステップと、
前記並替えステップによる並替え後の前記複数の位置情報それぞれと、前記分離 ステップ力 入力した前記所定順序で並んだ前記複数の要素情報それぞれとが対 応付けされた情報を生成して出力するステップを備える、復号方法をコンピュータに 実行させるためのプログラムを記録した機械読取り可能な記録媒体。
PCT/JP2005/017844 2004-09-30 2005-09-28 符号化装置、符号化方法、復号装置、復号方法、プログラムおよび該プログラムを記録した機械読取り可能な記録媒体 Ceased WO2006035813A1 (ja)

Priority Applications (3)

Application Number Priority Date Filing Date Title
US11/664,251 US7617237B2 (en) 2004-09-30 2005-09-28 Encoding device, encoding method, decoding device, decoding method, program and machine readable recording medium containing the program
JP2006537771A JPWO2006035813A1 (ja) 2004-09-30 2005-09-28 符号化装置、符号化方法、復号装置、復号方法、プログラムおよび該プログラムを記録した機械読取り可能な記録媒体
EP05787590A EP1811403A4 (en) 2004-09-30 2005-09-28 CODING DEVICE, CODING METHOD, DECODING DEVICE, DECODING METHOD, PROGRAM AND THE PROGRAM COMPRISING THE MACHINE READABLE RECORDING MEDIUM

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP2004287084 2004-09-30
JP2004-287084 2004-09-30

Publications (1)

Publication Number Publication Date
WO2006035813A1 true WO2006035813A1 (ja) 2006-04-06

Family

ID=36118959

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2005/017844 Ceased WO2006035813A1 (ja) 2004-09-30 2005-09-28 符号化装置、符号化方法、復号装置、復号方法、プログラムおよび該プログラムを記録した機械読取り可能な記録媒体

Country Status (4)

Country Link
US (1) US7617237B2 (ja)
EP (1) EP1811403A4 (ja)
JP (1) JPWO2006035813A1 (ja)
WO (1) WO2006035813A1 (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103686451A (zh) * 2012-09-21 2014-03-26 财团法人资讯工业策进会 媒体场景播放系统及其方法

Families Citing this family (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP5813872B2 (ja) * 2012-07-13 2015-11-17 株式会社東芝 通信制御装置、通信装置およびプログラム
US9280575B2 (en) * 2012-07-20 2016-03-08 Sap Se Indexing hierarchical data
US9425823B1 (en) * 2015-03-23 2016-08-23 Avago Technologies General Ip (Singapore) Pte. Ltd. State-split based encoder and decoder with table compression

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2000339390A (ja) * 1999-05-31 2000-12-08 Taabo Data Laboratory Kk 表形式データの結合方法、結合された表形式データの提示方法、上記方法を実現するプログラムを記憶した記憶媒体、および、表形式データ提示システム
JP2003092757A (ja) * 2001-07-10 2003-03-28 Sharp Corp 符号化装置及び方法、並びに復号装置及び方法

Family Cites Families (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4944023A (en) * 1987-05-19 1990-07-24 Ricoh Company, Ltd. Method of describing image information
US5982938A (en) * 1997-03-31 1999-11-09 Iterated Systems, Inc. System and method for compressing data using differential coding of coefficient addresses
US5956026A (en) * 1997-12-19 1999-09-21 Sharp Laboratories Of America, Inc. Method for hierarchical summarization and browsing of digital video
EP1619596A3 (en) * 2000-10-20 2006-05-24 Sharp Kabushiki Kaisha Search information managing apparatus for moving image contents
JP4622087B2 (ja) * 2000-11-09 2011-02-02 ソニー株式会社 情報処理装置、および情報処理方法、並びにプログラム記憶媒体
US20030009472A1 (en) * 2001-07-09 2003-01-09 Tomohiro Azami Method related to structured metadata
CN1768480B (zh) * 2003-02-03 2012-03-14 夏普株式会社 编码装置和方法、解码装置和方法

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2000339390A (ja) * 1999-05-31 2000-12-08 Taabo Data Laboratory Kk 表形式データの結合方法、結合された表形式データの提示方法、上記方法を実現するプログラムを記憶した記憶媒体、および、表形式データ提示システム
JP2003092757A (ja) * 2001-07-10 2003-03-28 Sharp Corp 符号化装置及び方法、並びに復号装置及び方法

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See also references of EP1811403A4 *

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103686451A (zh) * 2012-09-21 2014-03-26 财团法人资讯工业策进会 媒体场景播放系统及其方法

Also Published As

Publication number Publication date
EP1811403A1 (en) 2007-07-25
US20080027973A1 (en) 2008-01-31
US7617237B2 (en) 2009-11-10
EP1811403A4 (en) 2011-05-11
JPWO2006035813A1 (ja) 2008-07-31

Similar Documents

Publication Publication Date Title
KR100316725B1 (ko) 오브젝트데이터복호장치,데이터복호장치,부호화데이터선택장치,오브젝트데이터기록장치,부호화데이터송출장치,다중데이터송출장치,및오브젝트데이터처리장치
JP2005534101A (ja) メタデータのインデックス構造と記録媒体
JP2005209214A5 (ja)
CN102156734B (zh) 一种基于语义隐藏标引的视频内容管理方法
JP5656593B2 (ja) 符号化データを復号する装置及び方法
JP2004536481A (ja) 構造化文書の木構造におけるパスの符号化および復号化方法
KR20120090101A (ko) 디지털 비디오 고속 정합 시스템
JPH10304353A (ja) オブジェクトデータ処理装置，オブジェクトデータ記録装置，データ記憶媒体，及び伝送用データ構造
CN106446241A (zh) 使用书籍的isbn条码检索播放对应音频的方法及系统
WO2006035813A1 (ja) 符号化装置、符号化方法、復号装置、復号方法、プログラムおよび該プログラムを記録した機械読取り可能な記録媒体
JP2003256432A (ja) 映像素材情報記述方法、遠隔検索システム、遠隔検索方法、編集装置および遠隔検索端末、遠隔編集システム、遠隔編集方法、編集装置および遠隔編集端末、ならびに、映像素材情報記憶装置および方法
WO2004070955A1 (ja) 符号化装置及び方法、復号装置及び方法、プログラム、並びに記録媒体
JP4309127B2 (ja) 動画像コンテンツを検索するための検索情報を管理する装置
US7362909B2 (en) Coding device and method and decoding device and method
JP2011145883A (ja) 圧縮装置、方法及びプログラム、並びに展開装置、方法及びプログラム
KR100619031B1 (ko) 부가 데이터의 인터랙티브한 이용방법 및 장치, 그에 따른수신장치
US20090274435A1 (en) Reproduction device, reproduction method, recording device, recording medium, program storage medium, and program
JP4120980B2 (ja) 符号化装置及び方法、並びに復号装置及び方法
JP4251869B2 (ja) 動画像コンテンツを検索するための検索情報を管理する装置および方法
CN111656784A (zh) 解码方法、解码器和解码系统
US20060222071A1 (en) Object priority order compositor for MPEG-4 player
JPH03164980A (ja) 画像ファイル装置
CN111699687A (zh) 编码方法、编码器和编码系统
JP2005311774A (ja) 画像処理装置
JP2002344326A (ja) 合成インデックスによるデータ圧縮方法及び圧縮データの完全復元方法

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): AE AG AL AM AT AU AZ BA BB BG BR BW BY BZ CA CH CN CO CR CU CZ DE DK DM DZ EC EE EG ES FI GB GD GE GH GM HR HU ID IL IN IS JP KE KG KM KP KR KZ LC LK LR LS LT LU LV LY MA MD MG MK MN MW MX MZ NA NG NI NO NZ OM PG PH PL PT RO RU SC SD SE SG SK SL SM SY TJ TM TN TR TT TZ UA UG US UZ VC VN YU ZA ZM ZW

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): BW GH GM KE LS MW MZ NA SD SL SZ TZ UG ZM ZW AM AZ BY KG KZ MD RU TJ TM AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HU IE IS IT LT LU LV MC NL PL PT RO SE SI SK TR BF BJ CF CG CI CM GA GN GQ GW ML MR NE SN TD TG

121 Ep: the epo has been informed by wipo that ep was designated in this application
WWE Wipo information: entry into national phase

Ref document number: 2006537771

Country of ref document: JP

WWE Wipo information: entry into national phase

Ref document number: 11664251

Country of ref document: US

NENP Non-entry into the national phase

Ref country code: DE

WWE Wipo information: entry into national phase

Ref document number: 2005787590

Country of ref document: EP

WWP Wipo information: published in national office

Ref document number: 2005787590

Country of ref document: EP

WWP Wipo information: published in national office

Ref document number: 11664251

Country of ref document: US