METHOD AND DEVICE FOR ENCODING A STRUCTURED DOCUMENT AND DEVICE FOR DECODING A DOCUMENT THUS ENCODED

• US 20100192056A1
• Filed: 07/22/2008
• Published: 07/29/2010
• Est. Priority Date: 07/23/2007
• Status: Active Grant

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Fablet, Youenn, Bellessort, Romain
• Granted Patent: US 8,627,200 B2
• Time in Patent Office: Days
• 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. Method of encoding hierarchized data organized in a plurality of events, comprising:

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,

characterized in that it also comprises;

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.

2. Method according to claim 1, characterized in that, during the determination step, at least one event generated from productions of said grammar ordered in a predefined manner is recovered and the set of information is compared with at least one event generated with the set of information of at least one event to be encoded.

3. Method according to any one of claims 1 to 2, characterized in that it comprises, if the result of the determination step is negative, a step of encoding said set of information.

4. Method according to any one of claims 1 to 3, characterized in that, during the obtaining step, said set of information of at least one event to be encoded comprises structure information of at least one event to be encoded.

5. Method according to any one of claims 1 to 4, characterized in that, during the obtaining step, said set of information of at least one event to be encoded comprises information indicating whether the value of said event can be encoded by reference to a previously encoded value.

6. Method according to any one of claims 1 to 5, characterized in that the set of information of at least one event to be encoded is divided into a plurality of subsets of information and in that the result of the determination step is positive if a predetermined selection of subsets of information of at least one event to be encoded can be predicted unequivocally from said grammar.

7. Method according to claim 6, characterized in that a subset is selected according to the number of times that said information subset has been able to be predicted unequivocally from said grammar and/or the number of times that said 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.

8. Method according to either one of claims 6 to 7, characterized in that, if the result of the determination step is positive and the information set comprises at least one non-selected information subset, the method also comprises a step of encoding each non-selected information subset.

9. Method according to any one of claims 6 to 8, characterized in that, if the result of the determination step is negative and the information set comprises at least one selected information subset, the method comprises a step of encoding so-called “

non-conformity”

information representing this negative result.

10. Method according to any one of claims 6 to 9, characterized in that an information subset of said information set comprises the information relating to the events of the text type.

11. Method according to either one of claim 6 or 10, characterized in that an information subset of said information set comprises information relating to the events of the attribute type.

12. Method according to any one of claims 6 to 11, characterized in that an information subset of said information set comprises the information relating to the events of the start of element type.

13. Method according to any one of claims 1 to 12, characterized in that, during the step of recovering a grammar, said grammar is recovered according to at least one previously encoded event.

14. Method according to any one of claims 1 to 13, characterized in that it also comprises a step of updating the grammar recovered from the information set of at least one event to be encoded.

15. Method according to claim 14, characterized in that, during the implementation of a step of encoding all or part of said information set, the step of updating the recovered grammar takes into account the order of the events to be encoded.

16. Method according to any one of claims 1 to 15, characterized in that the hierarchized data is the data of a structured XML document.

17. Method according to any one of claims 1 to 16, characterized in that at least one said grammar is an EXI grammar.

23. Computer program that can be loaded into a computer system, said program containing instructions for implementing the encoding method according to any one of claims 1 to 17 or the decoding method according to any one of claim 18 or 20.

24. Information carrier that can be read by a computer or a microprocessor, removable or not, storing instructions of a computer program, characterized in that it allows the implementation of the encoding method according to any one of claims 1 to 17 or of the decoding method according to any one of claim 18 or 20.

18. Method of decoding hierarchized data organized in a plurality of events, characterized in that it comprises:

a step of obtaining so-called “

conformity”

information representing the fact that at least part of an information set of at least one event to be decoded can be predicted unequivocally from a grammar,

a step of obtaining said grammar, and

a step of generating the unequivocally predicted information from said grammar.

19. Method according to claim 18, characterized in that the step of obtaining the so-called “

conformity”

information comprises a step of decoding the conformity information.

20. Method according to claim 18, characterized in that, during the step of obtaining the so-called “

conformity”

information, the conformity information is obtained according to past decodings.

21. Device for encoding hierarchized data organized in a plurality of events, comprising:

a means of obtaining an information set of at least one event to be encoded, and

a means of recovering a grammar according to the information set, said grammar making it possible to describe at least said information set,

characterized in that it also comprises;

a means 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,

an encoding means adapted, if the result of the determination step is positive, to encode so-called “

conformity”

information representing this positive result, and adapted to encode the information of each said event to be encoded not included in said information set.

22. Device for decoding hierarchized data organized in a plurality of events, characterized in that it comprises:

a means of obtaining so-called “

conformity”

information representing the fact that at least part of an information set of at least one event to be decoded can be predicted unequivocally from a grammar,

a means of obtaining said grammar, and

a means of generating the unequivocally predicted information from said grammar.