Компресиране на информация, както тя се превръща
Всеки ден ние използваме различни архиватор: ZIP, RAR, асо навсякъде около нас.
Графични и аудио файлове да съдържат и компресирани данни. Ако се наложи да използвате
компресия в прог, а след това ние използваме различни dll'ki, много от които са платени.
Sharevarnost - не е единствената собственост на софтуерни компоненти, пречи на нормалния им
използвате. Ако, например, да компресирате WAW или BMP-файл архиватор, а след това
тя ще даде начин значително специален метод за конкретен тип данни, т.е.
метод трябва да се вземат предвид особеностите на определен тип данни. Ето защо е полезно да бъде в състояние да осъзнае собствената си компресия.
В тази статия ще ви покажем как да компресирате цялата информация и разгледа един от методите за компресия.
Класификация на методите за компресиране
На първо място, нито един от метода на компресия не може да изтръгне всички данни, като кодиране
трябва да бъдат недвусмислени. Предизвикателството е да се изгради правилото за кодиране на която
най-често срещаните доклади биха съответствали на мнения по дължина. Ето защо, всеки метод компресия трябва да се основава на каквито и да било предположения за
вероятностен структура компресирани данни. Например, за текста на конкретен език, известен
писма честота. Най-често използваният Предполага се, че по-
вероятно докладът ще се срещне с една и съща поредица от букви. Така например, в текста на тази
статия думата "компресия" е най-често. Ако ние не знаем нищо за вероятностна структура
сгъстен данни и лечение на всички съобщения със същата дължина, са еднакво вероятни, ние не правим нищо
компресиране.
методи на компресиране се разделят на статистическа и лексика. Речникът методи са, че
в случай на подниз на срещата, която вече е била намерена преди, за кодиране на връзката, която
Той заема по-малко място, отколкото действителната подниз. Един класически метод е лексиката
Lempel-Ziv (LZ). Всички използвани методи дата речника са само
модификации LZ.
Ентропията кодиране е за кодиране на всеки един от героите, но
използват кодове с различна дължина. Един пример на такива методи е метод Huffman
(Huffman). Обикновено речник и статистически методи се обединяват, тъй като всеки има своя собствена
ползи.
Трябва да отбележим едно нещо, което по някаква причина не е очевидно за някои "теоретици".
кодираща правило определена структура вероятностен данни, което означава, че декомпресора
Аз ще, преди началото на декодирането вече го знаеш. Ако го вземете от конкретните статистиката
мнения (както го компресира по-добре), а след това ще трябва да минат, пряко или непряко, заедно с компресирания
съобщение и не е ясно дали на общия размер по-малък.
Доказано е, че най-малката възможна средна компресиран размер на съобщението е равна на ентропията
ансамбъла на възможните съобщения, закръглени излишък. Ентропията се изчислява както следва:
Н = -Sum (р [Ь] * дневник (р [Ь]))
където Сума - сумата от I, Р [Ь] - вероятността на аз-ти съобщение, дневник - логаритъм на основата 2.
Ентропията на една сложна съобщение е сумата от ентропии на съставните й прости съобщения.
Ако се кодира всеки знак отделно, дължината на всеки код съобщение трябва да бъде
е равна -log (п). Т.е. например, ако вероятността на символа 0.3, кода трябва да има дължина
1,73 бита наведнъж, тъй като действителната дължина на цялото. Можете да подобрите резултатите, ако не се намали
задача за кодиране на отделните герои.
Този метод е коренно различна от всички обсъдени по-рано методи. основната му
се постига предимството, че теоретичната граница на компресия. Помислете за този метод в детайли. Цялото съобщение е представена от един номер по следния начин. Числото трябва
в интервала от 0 до 1. Този интервал е разделена на части, които са пропорционални на вероятностите
първите стойности характер. Избрани част съответстват на характера и е разделен на части
вероятната стойност на втория символ и т.н.
novaya_nizhnyaya_granitsa nizhnyaya_granitsa + = ширина * S [Ь]
novaya_shirina = ширина * р [Ь]
където [I] р - вероятността от I-ия символ, S [Ь] - сумата от вероятностите за символи с индекси
по-малко аз.
След обработката на всички съобщения от този алгоритъм може да записва само някоя
брой на получения интервал. Броят на битовете, необходими за записване на този номер,
приблизително равна на минус логаритъма на ширината на слот. Ширината на канала е равна на произведението от
Символ вероятности, т.е. вероятността за цялото съобщение. по този начин Дължина на кода е
-дневник (р), т.е. теоретичната граница. На практика, ние ще работим с променливите с ограничена дължина,
и точността на изчисленията ще бъдат ограничени, което означава, че компресията е все още малко по-зле.
Проектът е свързан с тази статия, съставени от Visual Studio .NET.
Това е прилагането на аритметично кодиране, компресиране на файлове, лечение на байта като герои.
съдържанието на файла се разглежда като процес, Марков на първо ред, т.е.. д. разпространение
знака зависи от вероятността за предходният знак. Клас CMarkovProcessDef процеси
данни, съхранявани в ресурса в специален формат. Тези данни са получени в резултат на
обработка на големи обеми от текст, т.е.. д. на текстови файлове, най-вероятно, ще бъдат компресирани
добре, и ако се опитате да изтръгне някакъв двоичен, размерът на "компресиран" файлът ще бъде по-голям
източник. За да получите метод за компресиране за вашия тип данни, данните трябва да се замени с
Символ вероятности. В допълнение, символът - не е задължително един байт на некомпресирани данни. Например,
ако има колона на таблицата, където стойностите трябва да са уникални, всяка стойност - това
символ и след е намерена характер, ние го нулира вероятност. Долната граница на широчината на интервала се съхранява в целочислени променливи dwBuf1 и dwBuf2.
Ако след обработка горни граници байта следващите символи са равни
(Имайте предвид, че това не е едно и също нещо, че ако високо ширината на байт е равен на нула), а след това
съответстващ байта крайният резултат ще бъде равна на тази стойност, и тя може да бъде
пише във файл. Напиши го и да се премести на буферите 1 байт. Когато разопаковате освен променливи се задават същите като в опаковката, ние
Имам нужда от един, където ще има информация от файла. За да се определи следващия знак, трябва да се
намерите символ с най-малък брой, така че S [п] * dwBuf2> = dwBuf3, т.е. P [п]> = dwBuf3 / dwBuf2. Когато се работи с числа, че има проблем: ние представляваме вероятността (фракционна
числа от 0 до 1) цяло число променлива (0x100000000 * р). За умножение и деление те се нуждаят от
специфични процедури: като се умножи вземе по-възрастен 32-битова дума за 64-битов резултат и деленето
разделят на броя умножава по 2 ^ 32. Компилаторът не може да umnozhitv DWORD да DWORD, сложи резултата
64-битова променлива - е липсата на ++ езика C. Така че аз трябваше да пиша специални процедури
асемблер.
анулира CArithmCompressorDlg :: OnBnClickedCompress ()
CFileDialog dlg1 (истина);
ако (dlg1.DoModal () = IDOK!) връщане;
CFileDialog dlg2 (FALSE, «сгъстен», 0, OFN_HIDEREADONLY | OFN_OVERWRITEPROMPT, «* .compressed | * .compressed | Всички файлове | * * ||.»);
ако (dlg2.DoModal () = IDOK!) връщане;
CFile ФАЙЛ_1 (dlg1.GetPathName (), CFile :: modeRead);
CFile ФАЙЛ_2 (dlg2.GetPathName (), CFile :: modeCreate | CFile :: modeWrite);
BYTE б;
ULONGLONG FS = file1.GetLength ();
file2.Write (# 038; FS, 8); // Напиши размера на оригиналния файл
// m_mpd - CMarkovProcessDef обект клас
m_mpd.ResetProcess (); // нулиране на данните от предишните герои
// започва Тази компресия
// Започнете интервал - от 0x00000000 да 0xFFFFFFFF
DWORD dwBuf1 = 0; // долна граница
DWORD dwBuf2 = 0xFFFFFFFF; // Ширина
DWORD dww; // Временната променлива
докато (file1.Read (# 038; б, 1))
// Изчислете новия интервал
ако (б> 0) dww = MulHigh (m_mpd.GetDistribution (Ь-1), dwBuf2); друго dww = 0;
/ *
m_mpd.GetDistribution (Ь-1) - Този S [Ь] М ..
р [Ь] - това m_mpd.GetDistribution (б) - m_mpd.GetDistribution (Ь-1)
Замяна на тази функция по прилагането му и да получите метод за компресиране за вашия тип данни.
* /
dwBuf1 + = dww;
ако (б = 0; J-) ако (file1.Read (((LPBYTE) # 038; dwBuf3) + J, 1) == 0) ((LPBYTE) # 038; dwBuf3) [J] = 0xFF;
// Търсене метод разполовяване
правя
m = (L + Н) / 2;
ако (H 0) dww = MulHigh (m_mpd.GetDistribution (m-1), dwBuf2); друго dww = 0;
dwBuf1 + = dww;
dwBuf3 - = dww;
ако (т
Покажете тази статия на приятел: