KR20020097389A - Method of Making Encoding Table for Hangul Compression and Method of Hangul Compression By Using It - Google Patents

Abstract

1. TECHNICAL FIELD OF THE INVENTION

The present invention relates to a method of generating an encoding table for Hangul compression coding, a Hangul compression coding method using the same, and a computer-readable recording medium having recorded thereon a program for realizing the method.

2. The technical problem to be solved by the invention

The present invention provides a method of generating an encoding table for Hangul compression coding, a Hangul compression coding method using the same, and a program for realizing the method for compressing and transmitting Hangul using Huffman coding in a high-capacity data service. To provide a record medium.

3. Summary of Solution to Invention

The present invention provides an encoding table generating method for Korean compression encoding, which is applied to an encoding table generating apparatus, comprising: a first step of extracting a sample of Korean data; Calculating a probability of occurrence of each symbol in the extracted Korean data sample; And a third step of generating an encoding table by performing Huffman coding after confirming that a probability of occurrence of the symbol of the second step is equal to or greater than a predetermined value for each symbol.

4. Important uses of the invention

The present invention is used for digital broadcasting.

Description

Method of Making Encoding Table for Hangul Compression and Method of Hangul Compression By Using It}

The present invention relates to a method for generating an encoding table for Korean compression encoding, a method for encoding Korean characters using the same, and a computer-readable recording medium having recorded thereon a program for realizing the method, and more particularly, to data broadcasting in digital television broadcasting. And a method of generating an encoding table for Hangul compression coding, a Hangul compression coding method using the same, and a program for realizing the method, for compressing and transmitting the Hangul text information used in the program information using the Huffman coding technique. The present invention relates to a recording medium which can be used.

Since TV broadcasting began in the 1940s, research on digital TV has been actively conducted in the 1990s, and the American system called the Advanced Television System Committee (ATSC) method and the European DTV named DVB (Digital Video Broadcasting). Was developed.

The DTV standard adopted in Korea is based on the ATSC method and can transmit information such as video, sound, and data as needed within the maximum range of 19.4 Mbps. This is a characteristic of digital TV that guarantees clear picture quality in the visible region and transmits High Definition TeleVision (HDTV) signal, but the viewer's desire is to prefer interactive services such as data broadcasting. The provision of is required.

As described above, since the amount of information of data broadcasting that provides various functions related to the program such as multiple services, high-speed data transmission, Internet service, etc. is likely to increase day by day, the need for compression of Korean character data emerges. In other words, in caption broadcasting in analog TV, the data volume is not large, and a speed of about 9600bps is sufficient, but in data broadcasting, information as much as video data needs to be transmitted, which requires compression.

On the other hand, ATSC of the United States has established the PSSC (ATSC Program and System Information Protocol) standard for text data transmission in English. In this standard, Huffman code is used to compress English letters and separate table is used according to title and contents. Huffman codes are defined as quadratic, and low frequency alphabets are exception coded.

However, the Korean digital broadcasting standard does not have a Korean code compression table, so it has been used to transmit Korean characters without compressing them. Since 2001, when digital broadcasting starts and data broadcasting starts in earnest, the amount of data occupied by Korean data is severe. It is expected that problems will arise.

In addition, although the efficiency increases when the second Huffman code is applied as in the PSIP standard, the maximum number of symbols in Korean is 11,172 characters. Therefore, when the second Huffman coding is performed, the number of codes reaches a square.

The present invention has been proposed to solve the above problems, and a method of generating an encoding table for Hangul compression coding and a Hangul compression coding method using the same for compressing and transmitting Hangul using Huffman coding in a high capacity data service. And a computer readable recording medium having recorded thereon a program for realizing the above method.

1 is a flowchart illustrating a method of generating an encoding table for Korean compression encoding according to the present invention.

2 is an exemplary diagram of an average code length of a symbol as a result of performing encoding according to a probability of occurrence of the symbol.

3 is an exemplary diagram of Hangul Huffman coding according to the present invention.

4 is an exemplary diagram of a Hangul decoding table according to the present invention;

5 is a structural diagram of an embodiment of a tree for Hangul decoding according to the present invention;

6A-6J illustrate an Huffman encoding table in accordance with one embodiment of the present invention.

7A-7Y illustrate an Huffman decoding table in accordance with an embodiment of the present invention.

8 is a flowchart illustrating an embodiment of a Hangul compression coding method according to the present invention.

An encoding table generating method of the present invention for achieving the above object comprises: a encoding table generating method for Korean compression encoding applied to an encoding table generating apparatus, comprising: a first step of extracting a sample of Korean data; Calculating a probability of occurrence of each symbol in the extracted Korean data sample; And a third step of generating an encoding table by performing Huffman coding after checking whether a probability of occurrence of the symbol of the second step is equal to or greater than a predetermined value for each symbol.

In addition, the Hangul compression coding method of the present invention, the Hangul compression coding method applied to the Hangul compression coding apparatus, comprising: a first step of generating an encoding table for Hangul compression coding; A second step of confirming whether a given symbol for transmission is included in the encoding table; A third step of encoding a value of the encoding table when the symbol is included in the encoding table as a result of the checking of the second step; And a fourth step of encoding the predetermined Hangul code together with an exception code if the symbol is not included in the encoding table as a result of the checking of the second step.

On the other hand, the present invention provides an encoding table generating apparatus having a processor, comprising: a first function of extracting a sample of Hangul data; A second function of calculating a probability of occurrence of each symbol in the extracted Korean data sample; And a program for realizing a third function of generating an encoding table by performing Huffman coding after confirming that a probability of occurrence of a symbol by the second function is equal to or greater than a predetermined value for each symbol. Provide a record carrier.

The present invention also provides a Hangul compression coding apparatus having a processor, comprising: a first function of generating an encoding table for Hangul compression coding; A second function of confirming whether a given symbol for transmission is included in the encoding table; A third function of encoding a value of the encoding table when the symbol is included in the encoding table as a result of the confirmation by the second function; And a computer-readable recording medium having recorded thereon a program for realizing a fourth function of encoding a predetermined Hangul code with an exception code if the symbol is not included in the encoding table as a result of the confirmation by the second function. do.

The above objects, features and advantages will become more apparent from the following detailed description taken in conjunction with the accompanying drawings. Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings.

1 is a flowchart illustrating a method of generating an encoding table for Korean compression encoding according to the present invention.

Hangul code is a character set that defines Korean and Korean as binary. Currently, there are two types of Hangul code that are widely used, standard completion code and standard combination code, and the use of Unicode, which is established as an international standard, is expected to increase gradually.

In order to compress-encode such Hangul code and use it for digital broadcasting, an encoding table for compression encoding is required.

A method of generating an encoding table for Korean compression encoding according to the present invention is as follows.

First, a sample of Hangul used for broadcasting should be extracted (11). This is to obtain a probability by extracting a sample since each use probability is required for compression coding by the Huffman coding method.

In a preferred embodiment of the present invention, the Hangul data to be generated in the digital broadcast is assumed to be similar to the data used in the current analog broadcast broadcasts, such as KBS, MBC, SBS for three months from May 2000 to October 2000 Broadcast news, drama, and movie data were collected.

The data collected above includes 22,000 special characters, including 67.5 million standardized Hangul characters (2 bytes / character), 3,380,000 ASCII characters (1 byte / character), and other Chinese characters. I) is included, and only Korean and English data are included in the experiment.

At this time, when comparing the probability of occurrence of Hangul in each field (drama, news, movie, etc.) with each other, the probability of occurrence of distribution in each field is almost the same.

Then, the entropy of the entire symbol is obtained from the extracted sample (12). The probability of occurrence of a symbol is identified through the entropy of the symbol thus obtained. If the determined probability of occurrence of the symbol is equal to or greater than a certain value (13), encoding by the Huffman encoding method is performed (14).

In the encoding process according to the Huffman coding method, a short code is assigned to a symbol having a high probability of occurrence and a long code is assigned to a symbol having a low probability of occurrence according to the probability of occurrence of a symbol.

In this case, although the efficiency increases according to the second-order Huffman coding that encodes two symbols by not combining each symbol independently, the Hangul performs the first-order Huffman coding because the maximum number of symbols reaches 11,172 characters and the number of codes increases by the square. .

Then, a compression encoding table for all symbols having a predetermined probability of occurrence or more is configured (15-16).

Even when the encoding is performed by the first Huffman coding as described above, the code is assigned only to symbols having a predetermined probability or more, and the rest is the original Korean code combined with the exception code (ESC). Transmit Hangul completion code or Unicode.

In the preferred embodiment of the present invention, a Huffman code is assigned to 1000 Korean codes having a probability of 0.0043 or more, and the encoding table and the decoding table are used to perform encoding by the Huffman coding method of FIG. 1. Devised.

2 is an exemplary diagram of an average code length of a symbol as a result of performing encoding according to a probability of occurrence of a symbol.

2 shows entropy and Huffman coding results of Korean data used in domestic TV broadcasting. Entropy is represented by dotted line as 7.14 bits / symbol, average code length of Huffman code except symbols with probability of occurrence less than 0.0043 is indicated by big dotted line, and average code length of all codes including exception coding is represented by solid line. That is, the best coding efficiency can be found.

In the preferred embodiment of the present invention, the best coding efficiency is found to have a probability of occurrence of 0.0043.

3 is an exemplary diagram of Hangul Huffman coding according to the present invention.

3 is " Here is an example showing the Hangul Huffman encoding process for the string ". "Is not a standard completion type code, so Korean Huffman coding is not applied. This character is used for" ESC "and" "Will be used.

In this case, the use of the "ESC" key as an exception code is because the Korean Huffman coding is a first order Huffman coding, unlike the English PSIP.

Other "rooms", "angles", and "ha" are encoded by the Hangul Huffman coding method.

4 is an exemplary diagram of a Hangul decoding table according to the present invention.

As shown in Fig. 4, when the decoding table for the string “to go” is seen, unlike the English decoding table, since each symbol occupies 2 bytes, the upper byte is tied to the upper byte and the lower byte is lowered to each other. Display. Bind two from the top and assign "1" and "0" to each node. The top is root, and the rest are nodes in turn. In Korean, since both nodes and codes are composed of two bytes (16 bits), in order to distinguish between nodes and codes, a larger value is added to the code value than the number of encoded characters. Here, 1024 is added to the upper byte. 5 shows an example in which this is represented by a tree structure.

<Table 1> is a compression format for applying the Korean compression code obtained by the method to the PSIP multi-string structure of the domestic terrestrial DTV standard.

Compression format Compression method 0x00 No compression 0x01 Huffman code method defined in Table C.4 and Table C.5 in Appendix C of ATSC A / 65 0x02 Huffman code method defined in Table C.6 and Table C.7 in Appendix C of ATSC A / 65 0x03 to 0x9F Reserved 0xA0 Huffman code method for Unicode (KS C 5700) 0xA1 to 0xAF Reserved 0xB0 Huffman code method for standard finished codes (KS C 5601-1987) 0xB1 Huffman code method for standard combination code (KS C 5601-1992) 0xB2 to 0xFF User private

As the Korean compression format, 0xA0 is used for the Unicode Huffman code, 0xB0 for the standardized Hangul code, and 0xB1 for the standard combined Korean Huffman code. However, the same Huffman code is used because the statistical characteristics of Korean characters do not vary depending on the type of Korean code.

Syntax Bits Format decode_table () {for (j == 0; j <N; j ++) {left_child_word_offset_or_char_leafright_child_word_offset_or_char_leaf}} 1616 uimsbfuimsbf

<Table 2> shows the decoding table format. Hangul consists of 2 bytes (16 bits), and since 1-D Huffman coding does not require the tree root of each character, unlike 2-D, only the left / right offset is included in the decoding table. Defined by byte.

6 is an exemplary diagram of a Huffman encoding table according to an embodiment of the present invention, and FIG. 7 is an exemplary diagram of a Huffman decoding table according to an embodiment of the present invention.

Herein, an embodiment of the present invention refers to Korean data to be generated in digital broadcasting, which is similar to data used in analog broadcasting currently being broadcast, and is broadcasted by three broadcasting companies including KBS, MBC, and SBS. After collecting news, drama, and movie data that has been broadcast for months, entropy is calculated, classified according to the probability of occurrence of each symbol, and Huffman coding is performed on symbols having an occurrence probability of 0.0043 or more.

8 is a flowchart illustrating a Hangul compression coding method according to the present invention.

First, an encoding table for compression encoding is generated for Korean compression encoding (81). As the encoding table, the encoding table generated in FIG. 1 is used.

Then, it is checked whether the target symbol to be compressed is included in the encoding table generated above (82). If the symbol is included in the encoding table as a result of the verification, the encoding is performed by the value of the encoding table (83).

On the other hand, if the symbol is not included in the encoding table as a result of the verification, the Korean code is encoded with the exception code (84). Here, the exception code uses the "ESC" key, because the Hangul compression coding is based on the first-order Huffman coding, so one exception code is sufficient. In addition, the Hangul code used with the exception code may be one of Unicode, Standard Combination Code, and Standard Completion Code. The Korean code is to be distinguished according to the compression format of Table 1.

As described above, the method of the present invention may be implemented as a program and stored in a recording medium (CD-ROM, RAM, ROM, floppy disk, hard disk, magneto-optical disk, etc.) in a computer-readable form.

The present invention described above is not limited to the above-described embodiments and the accompanying drawings, and various substitutions, modifications, and changes are possible in the art without departing from the technical spirit of the present invention. It will be apparent to those of ordinary knowledge.

As described above, the present invention has an effect of compressing and transmitting a large amount of Korean data transmission amount generated when data broadcasting is performed using digital TV.

In addition, the present invention provides one Huffman compression code for Hangul combination type, Hangul completion type and Unicode, and has the effect of defining the syntax in consideration of compression transmission in PSIP for program transmission.

In addition, the present invention has the effect of reducing the number of cases for encoding caused by the large number of Korean symbols because it is performed by the first order Huffman coding.

Claims (10)

In the encoding table generating method for Korean compression encoding applied to the encoding table generating apparatus, Extracting a sample of Hangul data; Calculating a probability of occurrence of each symbol in the extracted Korean data sample; And A third step of generating an encoding table by performing Huffman encoding after confirming that the probability of occurrence of the symbol of the second step is equal to or greater than a predetermined value for each symbol; Method of generating an encoding table for Hangul compression coding comprising a. The method of claim 1, The Huffman encoding process, An encoding table for Korean compression encoding, characterized in that a short code is assigned to a symbol having a high probability of occurrence and a long code is assigned to a symbol having a low probability of occurrence in consideration of the occurrence probability of each symbol and the encoding efficiency of all symbols. How to produce. The method according to claim 1 or 2, The Huffman encoding process, A method of generating an encoding table for Korean compression encoding, characterized by performing first order Huffman encoding. In the Hangul compression coding method applied to the Hangul compression coding apparatus, A first step of generating an encoding table for Hangul compression coding; A second step of confirming whether a given symbol for transmission is included in the encoding table; A third step of encoding a value of the encoding table when the symbol is included in the encoding table as a result of the checking of the second step; And A fourth step of encoding the predetermined Hangul code together with an exception code if the symbol is not included in the encoding table as a result of the checking of the second step Hangul compression coding method comprising a. The method of claim 4, wherein The first step is, A fifth step of extracting a sample of Hangul data; Calculating a probability of occurrence of each symbol in the extracted Korean data sample; And A seventh step of generating an encoding table by performing Huffman encoding after confirming that a probability of occurrence of the symbol of the second step is equal to or greater than a predetermined value for each symbol; Hangul compression coding method comprising a. The method of claim 5, The Huffman encoding process, A short code is assigned to a symbol having a high probability of occurrence and a long code is assigned to a symbol having a low probability of occurrence in consideration of the probability of occurrence of each symbol and the coding efficiency of all symbols. The method according to claim 5 or 6, The Huffman encoding process, Hangul compression coding method characterized in that the first Huffman coding. The method according to any one of claims 4 to 6, The predetermined Hangul code is, Hangul compression coding method characterized in that any one of Unicode, standard combination type code and standard completion type code. In the encoding table generating apparatus having a processor, A first function of sampling Korean data; A second function of calculating a probability of occurrence of each symbol in the extracted Korean data sample; And A third function of generating an encoding table by performing Huffman coding after confirming that a probability of occurrence of a symbol by the second function is equal to or greater than a predetermined value for each symbol; A computer-readable recording medium having recorded thereon a program for realizing this. In the Hangul compression coding apparatus having a processor, A first function of generating an encoding table for Hangul compression coding; A second function of confirming whether a given symbol for transmission is included in the encoding table; A third function of encoding a value of the encoding table when the symbol is included in the encoding table as a result of the confirmation by the second function; And A fourth function of encoding a predetermined Hangul code with an exception code if the symbol is not included in the encoding table as a result of the confirmation by the second function A computer-readable recording medium having recorded thereon a program for realizing this.