Patent ID: 7617237

Claim:
An encoding device for encoding information formed in a tree-structure in which a defined order relation holds among a plurality of leaves having element information added, comprising: means for receiving an information group having a plurality of sets, arranged in said defined order, containing element information of a prescribed type and position information representing a position of a leaf having the element information of the prescribed type added, in accordance with said defined order in said tree-structure; rearranging means for dividing a plurality of pieces of said element information from said plurality of sets of said information group received by said receiving means, and for rearranging said divided plurality of pieces of element information to a prescribed order suitable for searching of said element information of said prescribed type; correspondence information generating means for generating correspondence information representing correspondence between each of said plurality of pieces of element information after rearrangement and said position information of the same set as the element information in said information group received by said receiving means, based on a change in order of said plurality of pieces of element information caused by the rearrangement from said defined order to said prescribed order by said rearranging means; position information encoding means for dividing a plurality of pieces of said position information from said plurality of sets in said information group received by said receiving means, and for encoding the divided plurality of pieces of position information; and compressed information forming means for forming compressed information corresponding to said information group by arranging said plurality of pieces of position information encoded by said position information encoding means, said correspondence information generated by said correspondence information generating means, and said plurality of pieces of element information after rearrangement by said rearranging means in a prescribed form.