论文标题
单个文本压缩的最佳字母
Optimal alphabet for single text compression
论文作者
论文摘要
可以使用Huffman代码来压缩使用给定字母的符号编写的文本，该代码可最大程度地减少编码文本的长度。但是，有必要使用特定于文本的代码簿，即符号代码字典来解码原始文本。因此，应通过完整的代码长度，即编码文本的长度以及代码簿的长度来评估压缩性能。我们研究了几个字母，用于压缩文本 - 字母，字母，音节，单词和短语。如果仅保留足够短的文本，则最佳字母或两倍的字母字母是最佳的。对于大多数Project Gutenberg文本，根据代码书的表示，最好的字母（将完整代码长度最小化的字母最小化）是由音节或单词给出的。字母3和4克，平均具有与音节/单词相当长的长度，其性能比音节或单词差。在拥有非常大的代码簿的帐户上，Word 2-grams也从来都不是最好的字母。我们还表明，代码书表示很重要 - 从幼稚的表示变为紧凑的表示可以显着改善具有大量符号的字母的事项，最值得注意的是单词。 因此，语言（音节或单词）表达意义的元素提供了最佳的压缩字母。
A text written using symbols from a given alphabet can be compressed using the Huffman code, which minimizes the length of the encoded text. It is necessary, however, to employ a text-specific codebook, i.e. the symbol-codeword dictionary, to decode the original text. Thus, the compression performance should be evaluated by the full code length, i.e. the length of the encoded text plus the length of the codebook. We studied several alphabets for compressing texts -- letters, n-grams of letters, syllables, words, and phrases. If only sufficiently short texts are retained, an alphabet of letters or two-grams of letters is optimal. For the majority of Project Gutenberg texts, the best alphabet (the one that minimizes the full code length) is given by syllables or words, depending on the representation of the codebook. Letter 3 and 4-grams, having on average comparable length to syllables/words, perform noticeably worse than syllables or words. Word 2-grams also are never the best alphabet, on the account of having a very large codebook. We also show that the codebook representation is important -- switching from a naive representation to a compact one significantly improves the matters for alphabets with large number of symbols, most notably the words. Thus, meaning-expressing elements of the language (syllables or words) provide the best compression alphabet.
