# US 8,788,509 B2 · Method and device for coding a hierarchized document > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,788,509 B2 - Document ID: US8788509B2 - Status: Granted - Kind: B2 - Application number: 12/060,965 - Filed: 2008-04-02 - Published: 2008-10-09 - Granted: 2014-07-22 - Earliest claimed: 2007-04-03 - Assignees: Canon Kabushiki Kaisha - Applicants: Hervé Ruellan; Roamin Bellessort - Inventors: Hervé Ruellan; Roamin Bellessort - Web page: https://patentgrep.com/patent/US8788509B2 ## CPC - H03M 7/30: Compression (speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N); Expansion; Suppression of unnecessary data, e.g. redundancy reduction - G06F 40/143: Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD] - G06F 40/154: Tree transformation for tree-structured or markup documents, e.g. XSLT, XSL-FO or stylesheets - H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C) - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract The method of coding a hierarchized document comprises, for at least one element contained in the document: a step (200, 210, 220) of creating at least one pattern which describes at least structural information of said element and a step (230, 330) of selecting use, or not, of at least one of the created patterns, said selection depending on the efficiency of a coding operation of a set of instances of the created pattern, said coding operation implementing said created pattern. Preferentially, the method comprises a step of creating at least two patterns which describe at least structural information of said element and a step of selecting a pattern from among the created patterns, on the basis of the efficiency of each coding operation of a set of instances of the created patterns, by implementing one of the created patterns. ## Claims ### Claim 1 A method of, using at least one processor, coding a hierarchized document comprising at least one element, the method comprising the steps of: creating at least one initial pattern which describes at least structural information of the at least one element, and associating a set of instances of the at least one initial pattern in the hierarchized document with the at least one initial pattern, creating at least one specialized pattern as a modified copy of the at least one initial pattern, wherein the at least one specialized pattern comprises additional content information common to several instances of the set of instances associated with the at least one initial pattern; dividing the set of instances associated with the at least one initial pattern into a set of instances associated with the at least one initial pattern and a set of instances associated with each at least one specialized pattern; wherein, for each initial or specialized pattern, the method further comprises: evaluating a first coding cost where the initial or specialized pattern is used for coding a set of instances associated with the initial or specialized pattern, evaluating a second coding cost where the initial or specialized pattern is not used for coding the set of instances associated with the initial or specialized pattern, comparing the evaluated first coding cost and the evaluated second coding cost, keeping the initial or specialized pattern in view of coding the at least one element when the first coding cost is lower than the second coding cost, and eliminating the initial or specialized pattern from usage in view of coding the at least one element when the first coding cost is higher than the second coding cost, and coding the at least one element, the kept initial or specialized pattern associated with the at least one element, and pieces of information present in the at least one element and not present in the initial or specialized pattern being also coded, wherein during the step of dividing, the specialized pattern is a copy of the initial pattern to which is added additional content, and wherein instances comprising the additional content are associated with the specialized pattern and instances not including the additional content remain associated with the initial pattern. ### Claim 2 (depends on 1) The method according to claim 1, wherein, during the step of creating the initial pattern, a pattern is created that is designated empty, which comprises no description of content information of the element and, for the empty pattern, a set of the values corresponding to instances associated with the empty pattern and, during the step of creating a specialized pattern, at least one initial pattern and a set of associated values are implemented. ### Claim 3 (depends on 1) The method according to claim 1, wherein the step of creating at least one specialized pattern comprises a step of separating the instances of the initial pattern into two sets, one remaining associated with the initial pattern , the other being associated with the specialized pattern. ### Claim 4 (depends on 3) The method according to claim 3, wherein, further to the step of separating the instances, a supplementary step of creating specialized patterns is applied to the patterns and instances resulting from the separating step, when the number of instances associated with a pattern is greater than a predetermined value. ### Claim 5 (depends on 1) The method according to claim 1, wherein, during the step of creating at least one specialized pattern, the specialized pattern is created by incorporating into the initial pattern at least one of the pairs of at least one of the following sets of pairs: (attribute, attribute value) possessed by all the instances associated with the initial pattern, (text content, text content value) possessed by all the instances associated with the initial pattern, and (sub-pattern, sub-pattern definition) possessed by all the instances associated with the initial pattern. ### Claim 6 (depends on 1) The method according to claim 1, wherein, during the step of creating at least one specialized pattern a specialized pattern is created by incorporating into the initial pattern at least one of the pairs: (attribute, attribute value) that is the most frequent for the instances associated with the initial pattern, (text content, text content value) that is the most frequent for the instances associated with the initial pattern, and (sub-pattern, sub-pattern definition) that is the most frequent for the instances associated with the initial pattern. ### Claim 7 (depends on 6) The method according to claim 6, wherein the step of creating at least one specialized pattern comprises a step of separating the instances of the initial pattern into two sets, one remaining associated with the initial pattern , the other being associated with the specialized pattern, the instances comprising the pair being associated with the specialized pattern, the instances not comprising the pair being associated with the initial pattern. ### Claim 8 (depends on 1) The method according to claim 1, further comprising: a step of selecting use of at least one of the created patterns, the selection depending on the efficiency of a coding operation of a set of instances of the created pattern, the coding operation implementing the created pattern, wherein the selecting step further includes: a step of determining, for each created pattern, the saving in coding in case of implementation of that created pattern, relative to the coding without implementing the pattern; and a step of eliminating created patterns for which the saving is negative. ### Claim 9 (depends on 8) The method according to claim 8, wherein the steps of creating and selecting are carried out successively, for at least one element of the document, of at least one pattern associated with at least one of the sub-elements of the element and of a pattern associated with the element. ### Claim 10 (depends on 1) The method according to claim 1, further comprising: a step of creating a pattern designated encompassing formed by the union of at least two created patterns, this union containing all the structural and content information comprised in at least one of the patterns having undergone union. ### Claim 11 A device for coding a hierarchized document comprising, for processing at least one element contained in the document: a creating device for creating at least one initial pattern which describes at least structural information of the at least one element, and associating a set of instances of the at least one initial pattern in the hierarchized document with the at least one initial pattern, for creating at least one specialized pattern as a modified copy of the at least one initial pattern, wherein the at least one specialized pattern comprises additional content information common to several instances of the set of instances associated with the at least one initial pattern, and for dividing the set of instances associated with the at least one initial pattern into a set of instances associated with the at least one initial pattern and a set of instances associated with each at least one specialized pattern, wherein, for each initial or specialized pattern, the creating device performs steps of: evaluating a first coding cost where the initial or specialized pattern is used for coding a set of instances associated with the initial or specialized pattern, evaluating a second coding cost where the initial or specialized pattern is not used for coding the set of instances, comparing the evaluated first coding cost and the evaluated second coding cost, keeping the initial or specialized pattern in view of coding the at least one element when the first coding cost is lower than the second coding cost, and eliminating the initial or specialized pattern from usage in view of coding the at least one element when the first coding cost is higher than the second coding cost; and coding the at least one element, the kept initial or specialized pattern associated with the at least one element, and pieces of information present in the at least one element and not present in the initial or specialized pattern being also coded, wherein in the dividing, the specialized pattern is a copy of the initial pattern to which is added additional content, and wherein instances comprising the additional content are associated with the specialized pattern and instances not including the additional content remain associated with the initial pattern. ### Claim 12 A non-transitory computer-readable storage medium, storing instructions of a computer program, that makes it possible to implement a method of coding a hierarchized document comprising at least one element, the method comprising the steps of: creating at least one initial pattern which describes at least structural information of the at least one element, and associating a set of instances of the at least one initial pattern in the hierarchized document with the at least one initial pattern, creating at least one specialized pattern as a modified copy of the at least one initial pattern, wherein the at least one specialized pattern comprises additional content information common to several instances of the set of instances associated with the at least one initial pattern; dividing the set of instances associated with the at least one initial pattern into a set of instances associated with the at least one initial pattern and a set of instances associated with each at least one specialized pattern; wherein, for each initial or specialized pattern, the method further comprises: evaluating a first coding cost where the initial or specialized pattern is used for coding a set of instances associated with the initial or specialized pattern, evaluating a second coding cost where the initial or specialized pattern is not used for coding the set of instances associated with the initial or specialized pattern, comparing the evaluated first coding cost and the evaluated second coding cost, keeping the initial or specialized pattern in view of coding the at least one element when the first coding cost is lower than the second coding cost, and eliminating the initial or specialized pattern from usage in view of coding the at least one element when the first coding cost is higher than the second coding cost and coding the at least one element, the kept initial or specialized pattern associated with the at least one element, and pieces of information present in the at least one element and not present in the initial or specialized pattern being also coded, wherein during the step of dividing, the specialized pattern is a copy of the initial pattern to which is added additional content, and wherein instances comprising the additional content are associated with the specialized pattern and instances not including the additional content remain associated with the initial pattern.