Method and device for encoding a structured document and device for decoding a document thus encoded

• US 8,627,200 B2
• Filed: 07/22/2008
• Issued: 01/07/2014
• Est. Priority Date: 07/23/2007
• Status: Active Grant

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Bellessort, Romain, Fablet, Youenn
• Primary Examiner(s): Hong, Stephen
• Assistant Examiner(s): Vaughn, Gregory J
• Application Number:
  US12/668,788
• Publication Number:
  US 20100192056A1
• Time in Patent Office: 1,995 Days
• Field of Search: 715/200, 715/234, 715/237, 715/239
• US Class Current: 715/237
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/149 Adaptation of the text data for streaming purposes, e.g. Efficient XML Interchange [EXI] format
• CPC Class Codes: 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

Abstract

The method of encoding hierarchized data organized in a plurality of events comprises:

• • a step of obtaining an information set of at least one event to be encoded, and
  • a step of recovering a grammar according to the information set, said grammar making it possible to describe at least said information set,
  • a step of determining whether at least a part, defined by a predetermined criterion, of said information set of at least one event to be encoded can be predicted unequivocally from said grammar,
  • if the result of the determination step is positive, a step of encoding so-called “conformity” information representing this positive result, and
  • a step of encoding the information of each said event to be encoded not included in said information set.

Claims

1. A method of encoding hierarchized data organized in a plurality of events, comprising:

obtaining a first information set of at least one event to be encoded;

recovering a grammar based on the first information set, the grammar making it possible to describe at least the first information set;

determining a second information set including at least structural information, from the recovered grammar;

comparing the determined second information set to the first information set of at least one event to be encoded to determine whether at least a part, defined by a predetermined criterion, of the first information set of at least one event to be encoded can be predicted unequivocally from the grammar;

if the result of the comparison step is positive, encoding the unequivocally predicted part of the first information set using only a general code representing conformity information that is common to all information sets; and

encoding the information of each event to be encoded of the first information set that is not included in the determined second information set; and

if the result of the comparison step is negative, encoding the first information set using at least priorities from the recovered grammar.

2. The method according to claim 1, wherein, during the comparison step, at least one event generated from predictions of the grammar ordered in a predefined manner is recovered and the set of information is compared with at least one event generated with the first information set of at least one event to be encoded.

3. The method according to claim 1, wherein, during the obtaining step, the first information set of at least one event to be encoded comprises structure information of at least one event to be encoded.

4. The method according to claim 1, wherein, during the obtaining step, the first information set of at least one event to be encoded comprises information indicating whether the value of the event can be encoded by reference to a previously encoded value.

5. The method according to claim 1, wherein the first information set of at least one event to be encoded is divided into a plurality of subsets of information and the result of the comparison step is positive if a predetermined selection of subsets of information of at least one event to be encoded can be predicted unequivocally from the grammar.

6. The method according to claim 5, wherein a subset is selected according to the number of times that the information subset has been able to be predicted unequivocally from the grammar and/or the number of times that the information subset has not been able to be predicted, during the coding of at least one previous event to be encoded among the plurality of events.

7. The method according to claim 5, wherein, if the result of the comparison step is positive and the first information set comprises at least one non-selected information subset, the method also comprises a step of encoding each non-selected information subset.

8. The method according to claim 5, further comprising if the result of the comparison step is negative, encoding another general code different from the general code, representing non-conformity information that is common to all information sets.

9. The method according to claim 5, wherein an information subset of the first information set comprises the information relating to the events of the text type.

10. The method according to claim 5, wherein an information subset of the first information set comprises information relating to the events of the attribute type.

11. The method according to claim 5, wherein an information subset of the first information set comprises the information relating to the events of the start of element type.

12. The method according to claim 1, wherein, during the step of recovering a grammar, the grammar is recovered according to at least one previously encoded event.

13. The method according to claim 1, further comprising updating the grammar recovered from the first information set of at least one event to be encoded.

14. The method according to claim 13, wherein, during the implementation of a step of encoding all or part of the first information set, the step of updating the recovered grammar accounts for the order of the events to be encoded.

15. The method according to claim 1, wherein a structure of the event is predicted from the recovered grammar.

16. The method according to claim 15, wherein the predicted structure is compared to the event to be encoded to determine whether or not they correspond to each other.

17. The method according to claim 16, wherein in encoding the conformity information, the predicted structure is encoded when it is determined that the predicted structure corresponds to the event to be encoded.

18. The method according to claim 16, wherein the information of each event to be encoded in the encoding step includes information of the event that is not described by the predicted structure.

19. A method of decoding hierarchized data organized in a plurality of events, comprising:

obtaining conformity information representing that at least part of a first information set of at least one event to be decoded can be predicted unequivocally from a grammar, wherein whether the at least one event can be predicted unequivocally is determined by comparing the first information set with a second information set including at least structural information from the grammar, wherein the unequivocally predicted part of the first information set is encoded using only a general code representing the conformity information, wherein the conformity information is common to all information sets, and wherein the encoding encodes the information of each event to be encoded of the first information set that is not included in the second information set;

obtaining the grammar; and

generating the unequivocally predicted information from the grammar.

20. The method according to claim 19, wherein the step of obtaining the conformity information comprises decoding the conformity information.

21. The method according to claim 19, wherein, during the step of obtaining the conformity information, the conformity information is obtained according to previous decodings.

22. A device for encoding hierarchized data organized in a plurality of events, comprising:

a means for obtaining a first information set of at least one event to be encoded;

a means for recovering a grammar based on the first information set, the grammar making it possible to describe at least the first information set;

a determining means for determining a second information set including at least structural information, from the recovered grammar;

a comparing means for comparing the determined second information set to the first information set of at least one event to be encoded to determine whether at least a part, defined by a predetermined criterion, of the first information set of at least one event to be encoded can be predicted unequivocally from the grammar; and

an encoding means for encoding, if the result of the comparison step is positive, the unequivocally predicted part of the first information set using only a general code representing conformity information that is common to all information sets, and the information of each event to be encoded of the first information set that is not included in the determined second information set,

wherein if the result of the comparison step is negative, the first information set is encoded using at least priorities from the recovered grammar.

23. A device for decoding hierarchized data organized in a plurality of events, comprising:

a means for obtaining information representing that at least part of a first information set of at least one event to be decoded can be predicted unequivocally from a grammar, wherein whether the at least one event can be predicted unequivocally is determined by comparing the first information set with a second information set including at least structural information from the grammar, wherein the unequivocally predicted part of the first information set is encoded using only a general code representing conformity information that is common to all information sets, and wherein the encoding encodes the information of each event to be encoded of the first information set that is not included in the second information set;

a means for obtaining the grammar; and

a means for generating the unequivocally predicted information from the grammar.