| 词条 | Run-length encoding |
| 释义 |
Run-length encoding (RLE) is a very simple form of lossless data compression in which runs of data (that is, sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as the original run. This is most useful on data that contains many such runs. Consider, for example, simple graphic images such as icons, line drawings, Conway’s Game of Life, and animations. It is not useful with files that don't have many runs as it could greatly increase the file size. RLE may also be used to refer to an early graphics file format supported by CompuServe for compressing black and white images, but was widely supplanted by their later Graphics Interchange Format. RLE also refers to a little-used image format in Windows 3.x, with the extension rle, which is a Run Length Encoded Bitmap, used to compress the Windows 3.x startup screen. ExampleFor example, consider a screen containing plain black text on a solid white background. There will be many long runs of white pixels in the blank space, and many short runs of black pixels within the text. A hypothetical scan line, with B representing a black pixel and W representing white, might read as follows: With a run-length encoding (RLE) data compression algorithm applied to the above hypothetical scan line, it can be rendered as follows: This can be interpreted as a sequence of twelve Ws, one B, twelve Ws, three Bs, etc.., The run-length code represents the original 67 characters in only 18. While the actual format used for the storage of images is generally binary rather than ASCII characters like this, the principle remains the same. Even binary data files can be compressed with this method; file format specifications often dictate repeated bytes in files as padding space. However, newer compression methods such as DEFLATE often use LZ77-based algorithms, a generalization of run-length encoding that can take advantage of runs of strings of characters (such as Run-length encoding can be expressed in multiple ways to accommodate data properties as well as additional compression algorithms. For instance, one popular method encodes run lengths for runs of two or more characters only, using an "escape" symbol to identify runs, or using the character itself as the escape, so that any time a character appears twice it denotes a run. On the previous example, this would give the following: This would be interpreted as a run of twelve Ws, a B, a run of twelve Ws, a run of three Bs, etc. In data where runs are less frequent, this can significantly improve the compression rate. One other matter is the application of additional compression algorithms. Even with the runs extracted, the frequencies of different characters may be large, allowing for further compression; however, if the run lengths are written in the file in the locations where the runs occurred, the presence of these numbers interrupts the normal flow and makes it harder to compress. To overcome this, some run-length encoders separate the data and escape symbols from the run lengths, so that the two can be handled independently. For the example data, this would result in two outputs, the string " History and applicationsRun-length encoding schemes were employed in the transmission of television signals as far back as 1967. It is particularly well suited to palette-based bitmapped images such as computer icons, and was a popular image compression method on early online services such as CompuServe before the advent of more sophisticated formats such as GIF.[2] It does not work well at all on continuous-tone images such as photographs, although JPEG uses it quite effectively on the coefficients that remain after transforming and quantizing image blocks. Common formats for run-length encoded data include Truevision TGA, PackBits, PCX and ILBM. The ITU also describes a standard to encode run-length-colour for fax machines, known as T.45.[3] The standard, which is combined with other techniques into Modified Huffman coding,{{cn|date=December 2015}} is relatively efficient because most faxed documents are generally white space, with occasional interruptions of black. See also
References1. ^1 {{cite journal |authorlink=Christopher Dunn (computer enthusiast) |journal=The Transactor |date=1987 |volume=7 |number=6 |publisher=Transactor Publishing |author-last=Dunn |author-first=Christopher |title=Smile! You're on RLE! |pages=16–18 |url=http://csbruce.com/cbm/transactor/pdfs/trans_v7_i06.pdf |accessdate=2015-12-06}} [1][2]2. ^1 {{cite book |title=Recommendation T.45 (02/00): Run-length colour encoding |date=2000 |publisher=International Telecommunication Union |url=http://www.itu.int/rec/T-REC-T.45 |accessdate=2015-12-06}} }} External links
1 : Lossless compression algorithms |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。