# US 9,882,582 B2 · Non-transitory computer-readable recording medium, encoding method, encoding device, decoding method, and decoding device > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 9,882,582 B2 - Document ID: US9882582B2 - Status: Granted - Kind: B2 - Application number: 15/285,060 - Filed: 2016-10-04 - Published: 2017-04-06 - Granted: 2018-01-30 - Earliest claimed: 2015-10-05 - Assignees: Fujitsu Limited - Applicants: Fujitsu Limited - Inventors: Masahiro Kataoka - Web page: https://patentgrep.com/patent/US9882582B2 ## CPC - H03M 7/3084: {using adaptive string matching, e.g. the Lempel-Ziv method} - G06F 40/14: Tree-structured documents (parsing G06F40/205; validation G06F40/226) - G06F 40/146: Coding or compression of tree-structured data - G06F 40/242: Dictionaries - H03M 7/3088: {employing the use of a dictionary, e.g. LZ78} - H03M 7/40: Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code - H03M 7/4037: {Prefix coding} - H03M 7/6029: {Pipelining} - 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 An encoding device generates static-encoded data from input text data, utilizing a static dictionary that associates a character strings and static codes, respectively the static-encoded data including a plurality of static codes corresponding to a plurality of character strings that are registered in the static dictionary, generates dynamic-encoded data from the static-encoded data by encoding a character string or the static code that occurs more than once in the static-encodes data into a dynamic code, creates a dynamic dictionary associating character strings or static codes with corresponding dynamic codes, respectively and creates a Huffman tree and data of a leaf in the Huffman tree based on an occurrence frequency of the dynamic codes and the static codes in the input text data. ## Claims ### Claim 1 A non-transitory computer-readable recording medium having stored therein an encoding program that causes a computer to execute a process comprising: first generating static-encoded data from input text data, utilizing a static dictionary that associates a character strings and static codes, respectively the static-encoded data including a plurality of static codes corresponding to a plurality of character strings that are registered in the static dictionary and character strings that are not registered in the static dictionary among the text data; second generating dynamic-encoded data from the static-encoded data by either encoding a character string that occurs more than once in the static-encoded data into a dynamic code or encoding a static code that occurs more than once in the static-encoded data; first creating a dynamic dictionary associating character strings or static codes with corresponding dynamic codes, respectively; and second creating a Huffman tree and data of a leaf in the Huffman tree based on an occurrence frequency of the dynamic codes and the static codes in the input text data. ### Claim 2 (depends on 1) The non-transitory computer-readable recording medium, according to claim 1, the process further comprising: encoding the dynamic codes and the static codes included in the dynamic-encoded data, based on the Huffman tree and the data of a leaf. ### Claim 3 (depends on 1) The non-transitory computer-readable recording medium, according to claim 1, wherein the second creating creates a Huffman tree in which codes length of codes corresponding to the dynamic codes and the static codes having a high occurrence frequency is shorter than codes length of codes corresponding to the dynamic codes and the static codes having a low occurrence frequency. ### Claim 4 (depends on 1) The non-transitory computer-readable recording medium, according to claim 1, the process further comprising: identifying an occurrence frequency of dynamic codes and an occurrence frequency of static codes included in the dynamic-encoded data; and storing data in which dynamic codes and an occurrence frequency of the dynamic codes are associated with each other, and data in which static codes and an occurrence frequency of the static codes are associated with each other. ### Claim 5 An encoding method, comprising: first generating static-encoded data from input text data, utilizing a static dictionary that associates a character strings and static codes, respectively the static-encoded data including a plurality of static codes corresponding to a plurality of character strings that are registered in the static dictionary and character strings that are not registered in the static dictionary among the text data, using a processor; second generating dynamic-encoded data from the static-encoded data by either encoding a character string that occurs more than once in the static-encoded data into a dynamic code or encoding a static code that occurs more than once in the static-encoded data, using the processor; first creating a dynamic dictionary associating character strings or static codes with corresponding dynamic codes, respectively, using the processor; and second creating a Huffman tree and data of a leaf in the Huffman tree based on an occurrence frequency of the dynamic codes and the static codes in the input text data, using the processor. ### Claim 6 (depends on 5) The encoding method according to claim 5, further comprising encoding the dynamic codes and the static codes included in the dynamic-encoded data, based on the Huffman tree and the data of a leaf. ### Claim 7 (depends on 5) The encoding method according to claim 5, wherein the second creating creates a Huffman tree in which codes length of codes corresponding to the dynamic codes and the static codes having a high occurrence frequency is shorter than codes length of codes corresponding to the dynamic codes and the static codes having a low occurrence frequency. ### Claim 8 (depends on 5) The encoding method according to claim 5, further comprising: identifying an occurrence frequency of dynamic codes and an occurrence frequency of static codes included in the dynamic-encoded data; and storing data in which dynamic codes and an occurrence frequency of the dynamic codes are associated with each other, and data in which static codes and an occurrence frequency of the static codes are associated with each other. ### Claim 9 An encoding device, comprising: a processor that executes a process comprising: first generating static-encoded data from input text data, utilizing a static dictionary that associates a character strings and static codes, respectively the static-encoded data including a plurality of static codes corresponding to a plurality of character strings that are registered in the static dictionary and character strings that are not registered in the static dictionary among the text data; second generating dynamic-encoded data from the static-encoded data by either encoding a character string that occurs more than once in the static-encoded data into a dynamic code or encoding a static code that occurs more than once in the static-encoded data; first creating a dynamic dictionary associating character strings or static codes with corresponding dynamic codes, respectively; and second creating a Huffman tree and data of a leaf in the Huffman tree based on an occurrence frequency of the dynamic codes and the static codes in the input text data. ### Claim 10 (depends on 9) The encoding device according to claim 9, the process further comprising encoding the dynamic codes and the static codes included in the dynamic-encoded data, based on the Huffman tree and the data of a leaf. ### Claim 11 (depends on 9) The encoding device according to claim 9, wherein the second creating creates a Huffman tree in which codes length of codes corresponding to the dynamic codes and the static codes having a high occurrence frequency is shorter than codes length of codes corresponding to the dynamic codes and the static codes having a low occurrence frequency. ### Claim 12 (depends on 9) The encoding device according to claim 9, the process further comprising identifying an occurrence frequency of dynamic codes and an occurrence frequency of static codes included in the dynamic-encoded data; and storing data in which dynamic codes and an occurrence frequency of the dynamic codes are associated with each other, and data in which static codes and an occurrence frequency of the static codes are associated with each other. ### Claim 13 A non-transitory computer-readable recording medium having stored therein a decoding program that causes a computer to execute a process comprising: reading occurrence-frequency table data from a header portion of an encoded file to be input; creating a Huffman tree and data of a leaf in the Huffman tree based on information relating to an occurrence frequency of dynamic codes and static codes obtained from the occurrence-frequency table data, wherein the dynamic codes include a dynamic code which is encoded from a character string that occurs more than once in a static-encodes data, a dynamic code which is encoded from a static code that occurs more than once in the static-encodes data, a dynamic code which is encoded from combination data including a character string and a static code that occur more than once in the static-encodes data; and decoding an encoded file based on the Huffman tree, the data of a leaf in the Huffman tree, and encoded data included in the encoded file. ### Claim 14 A decoding method, comprising: reading occurrence-frequency table data from a header portion of an encoded file to be input, using a processor; creating a Huffman tree and data of a leaf in the Huffman tree based on information relating to an occurrence frequency of dynamic codes and static codes obtained from the occurrence-frequency table data, wherein the dynamic codes include a dynamic code which is encoded from a character string that occurs more than once in a static-encodes data, a dynamic code which is encoded from a static code that occurs more than once in the static-encodes data, a dynamic code which is encoded from combination data including a character string and a static code that occur more than once in the static-encodes data, using the processor; and decoding an encoded file based on the Huffman tree, the data of a leaf in the Huffman tree, and encoded data included in the encoded file, using the processor. ### Claim 15 A decoding device, comprising: a processor that executes a process comprising: reading occurrence-frequency table data from a header portion of an encoded file to be input; creating a Huffman tree and data of a leaf in the Huffman tree based on information relating to an occurrence frequency of dynamic codes and static codes obtained from the occurrence-frequency table data, wherein the dynamic codes include a dynamic code which is encoded from a character string that occurs more than once in a static-encodes data, a dynamic code which is encoded from a static code that occurs more than once in the static-encodes data, a dynamic code which is encoded from combination data including a character string and a static code that occur more than once in the static-encodes data; and decoding an encoded file based on the Huffman tree, the data of a leaf in the Huffman tree, and encoded data included in the encoded file. ### Claim 16 (depends on 1) The non-transitory computer-readable recording medium, according to claim 1, wherein the second generating generates dynamic-encoded data from the static-encoded data by encoding a character string that occurs more than once in the static-encoded data into a dynamic code, by encoding a static code that occurs more than once in the static-encoded data into a dynamic code or by encoding a combination data into a dynamic code, the combination data including the character string and a static code that occur more than once. ### Claim 17 (depends on 5) The encoding method according to claim 5, wherein the second generating generates dynamic-encoded data from the static-encoded data by encoding a character string that occurs more than once in the static-encoded data into a dynamic code, by encoding a static code that occurs more than once in the static-encoded data into a dynamic code or by encoding a combination data into a dynamic code, the combination data including the character string and a static code that occur more than once. ### Claim 18 (depends on 9) The encoding device according to claim 9, wherein the second generating generates dynamic-encoded data from the static-encoded data by encoding a character string that occurs more than once in the static-encoded data into a dynamic code, by encoding a static code that occurs more than once in the static-encoded data into a dynamic code or by encoding a combination data into a dynamic code, the combination data including the character string and a static code that occur more than once.