Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Схема сжатия данных без потерь
Lossless data compression scheme
В теории информации энтропийное кодирование (или энтропийное кодирование) – это любой метод сжатия данных без потерь, который стремится приблизиться к нижней границе, установленной теоремой кодирования источника Шеннона. Эта теорема утверждает, что любой метод сжатия данных без потерь должен иметь ожидаемую длину кода, большую или равную энтропии источника. Более точно, теорема кодирования источника гласит, что для любого распределения источника ожидаемая длина кода удовлетворяет условию , где – число символов в кодовом слове, – функция кодирования, – число символов, используемых для формирования выходных кодов, а – вероятность символа источника. Энтропийное кодирование стремится к достижению этой нижней границы. Два наиболее распространенных метода энтропийного кодирования – кодирование Хаффмана и арифметическое кодирование. Если приблизительные характеристики энтропии потока данных известны заранее (особенно при сжатии сигналов), может оказаться полезным более простой статический код. К таким статическим кодам относятся универсальные коды (например, гамма-кодирование Элиаса или кодирование Фибоначчи) и коды Голомба (например, унитарное кодирование или кодирование Райса). С 2014 года компрессоры данных стали использовать семейство асимметричных систем счисления для энтропийного кодирования, что позволяет сочетать степень сжатия арифметического кодирования с вычислительной сложностью, сопоставимой с кодированием Хаффмана.
In information theory, an entropy coding (or entropy encoding) is any lossless data compression method that attempts to approach the lower bound declared by Shannon's source coding theorem, which states that any lossless data compression method must have an expected code length greater than or equal to the entropy of the source. More precisely, the source coding theorem states that for any source distribution, the expected code length satisfies , where is the number of symbols in a code word, is the coding function, is the number of symbols used to make output codes and is the probability of the source symbol. An entropy coding attempts to approach this lower bound. Two of the most common entropy coding techniques are Huffman coding and arithmetic coding. If the approximate entropy characteristics of a data stream are known in advance (especially for signal compression), a simpler static code may be useful. These static codes include universal codes (such as Elias gamma coding or Fibonacci coding) and Golomb codes (such as unary coding or Rice coding). Since 2014, data compressors have started using the asymmetric numeral systems family of entropy coding techniques, which allows combination of the compression ratio of arithmetic coding with a processing cost similar to Huffman coding.
Энтропия как мера сходства
Помимо использования энтропийного кодирования для сжатия цифровых данных, энтропийный кодер также может применяться для оценки степени сходства между потоками данных и существующими классами данных. Это достигается путем создания энтропийного кодера/компрессора для каждого класса данных; неизвестные данные затем классифицируются путем подачи некомпрессированных данных в каждый компрессор и определения того, какой из компрессоров обеспечивает наибольшую степень сжатия. Кодер, обеспечивающий наилучшее сжатие, скорее всего, был обучен на данных, наиболее похожих на неизвестные данные.
Besides using entropy coding as a way to compress digital data, an entropy encoder can also be used to measure the amount of similarity between streams of data and already existing classes of data. This is done by generating an entropy coder/compressor for each class of data; unknown data is then classified by feeding the uncompressed data to each compressor and seeing which compressor yields the highest compression. The coder with the best compression is probably the coder trained on the data that was most similar to the unknown data.