rzip – 900МБ сөздікпен жұмыс істейтін, жоғары деңгейдегі деректерді қысу бағдарламасы. LZ77, Bzip2 және Huffman кодтауын қолданады. Жақсы қысу нәтижесі!
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Деректерді сығыстыру компьютерлік бағдарламасы.
Data compression computer program
rzip – 900 МБ көлемді сөздік терезесінде бастапқы LZ77 стиліндегі тізбектерді салыстыру, содан кейін bzip2 негізіндегі Burrows–Wheeler түрлендіруі және энтропиялық кодтау (Хуффман) 900 кБ шығыс бөліктері бойынша жасалған, өте кең көлемді деректерді сығыстыруға арналған компьютерлік бағдарлама.
rzip is a huge scale data compression computer program designed around initial LZ77 style string matching on a 900 MB dictionary window, followed by bzip2 based Burrows–Wheeler transform and entropy coding (Huffman) on 900 kB output chunks.
Анықтамалық іске асыру
rsync-тегі алгоритмге негізделген жылжымалы тексеру сомасының алгоритмі осы үлкен деректер жиынтығынан мүмкін сәйкестіктерді анықтау үшін қолданылады. Хеш-бөшкелер толғанда, бұрынғы хештер ("маркерлер") екі еселенген мөлшерде жойылады. Маркерлердің жойылуы жақсы жабуды қамтамасыз етеді, ал қашықтық артқан сайын сәйкестіктердің дәлдігі біртіндеп төмендейді. Бұл жүзеге асыру 31 тізбекті байттан кем ұзындықтағы сәйкестіктерді іздемейді.
A rolling checksum algorithm based on the one in rsync is used to locate potential matches from over such a large dataset. As the hash buckets fill up, previous hashes ("tags") are discarded based on twice. The tags are discarded in such a manner as to provide fairly good coverage, with a gradually decreasing match granularity as the distance increases. This implementation does not search for match lengths of fewer than 31 consecutive bytes.
Артықшылықтар
Rzip пен басқа белгілі қысылу алгоритмдерінің басты айырмашылығы – оның өте ұзақ қашықтықтағы қайталануды пайдалану қабілеті. Gzip-те қолданылатын танымал deflate алгоритмі 32 КиБ көлеміндегі ең үлкен тарих буферін қолданады. Bzip2-де қолданылатын Burrows-Wheeler түрлендіру блогын сұрыптау алгоритмі 900 КиБ тарихпен шектелген. Rzip-тегі тарих буфері 900 МБ-қа дейін жете алады, бұл gzip немесе bzip2-ден бірнеше есе үлкен. Rzip, bzip2 кітапханасын қолданғанына қарамастан, көбінесе bzip2-ден жылдам жұмыс істейді. Мұның себебі rzip bzip2-ге қысқартылған деректерді жібереді, сондықтан bzip2-ге аз жұмыс жасау қалады. Шамалы салыстырулар жасалды (бірақ бұл сенімді өлшемдеме үшін жеткіліксіз).
The key difference between rzip and other well known compression algorithms is its ability to take advantage of very long distance redundancy. The well known deflate algorithm used in gzip uses a maximum history buffer of 32 KiB. The Burrows–Wheeler transform block sorting algorithm used in bzip2 is limited to 900 KiB of history. The history buffer in rzip can be up to 900 MiB long, several orders of magnitude larger than gzip or bzip2. Rzip is often much faster than bzip2, despite using the bzip2 library as a back end. This is because rzip feeds bzip2 with shrunken data, so that bzip2 has to do less work. Simple comparisons (although too small for it to be an authoritative benchmark) have been produced.
Кемшіліктер
rzip әр мақсатқа сай келмейді. rzip-тің ең басты екі кемшілігі – оны конвейерге қосу мүмкін емес (сондықтан ол стандарттық кірістен дерек оқи алмайды немесе стандарттық шығысқа жаза алмайды), және ол көп жадты пайдаланады: үлкен файлды сығымдау кезінде әдетте жүздеген мегабайт жедел жад (RAM) қолданылуы мүмкін. Егер жеткілікті жедел жад болса және өте жоғары сығымдалу қажет болса, rzip қолданылуы керек, бірақ егер бұл шарттар орындалмаса, gzip және bzip2 сияқты, жадты аз пайдаланатын басқа сығымдалу әдістерін пайдалану керек. Конвейерлік өңдеуді қосуға мүмкіндік беретін кем дегенде бір түзету бар.
rzip is not suited for every purpose. The two biggest disadvantages of rzip are that it cannot be pipelined (so it cannot read from standard input or write to standard output), and that it uses a high amount of memory: a typical compression run on a large file might use hundreds of megabytes of RAM. If there is a lot of RAM to spare and a very high compression ratio is required, rzip should be used, but if these conditions are not satisfied, alternate compression methods such as gzip and bzip2, which are less memory intensive, should be used instead of rzip. There is at least one patch to enable pipelining.
Тарих
rzip бастапқыда Эндрю Триджелл өзінің PhD диссертациялық зерттеуінің бір бөлігі ретінде жазылған.
rzip was originally written by Andrew Tridgell as part of his PhD research.
rzip64
rzip64 – бірнеше CPU ядросын параллель қолдана алатын, өте үлкен файлдарға арналған rzip кеңейтімі. Осыған қатысты өлшемдердің нәтижелері бар. Бірақ ең маңыздысы – rzip64 кез келген сәтте тоқтатылуы мүмкін. Осы арқылы, ағымдағы сығылу міндеті (үлкен файлдар үшін бірнеше сағатқа созылуы мүмкін) тіпті жүйелік техникалық жөндеу үшін жүйені қайта жүктеу кезінде де аяқталған жұмысты жоғалтпай, кейін жалғастырыла алады. rzip64 файл форматы бастапқы rzip форматымен бірдей.
rzip64 is an extension of rzip for very large files that can utilize multiple CPU cores in parallel. There are benchmark results. Most important, however, is the ability of rzip64 to be interrupted at any time. Thereby a running compression task (that may easily take several hours for large files) survives even a system maintenance reboot without losing already completed work and can be resumed later. The file format of rzip64 is identical to the original rzip.
РЕП
REP – Булат Зиганшиннің FreeArc архивінде LZMA/Tornado сығылу алгоритмдерінің алдын ала өңдеушісі ретінде қолданылатын rzip алгоритмінің баламалы нұсқасы. FreeArc-та REP үлкен арақашықтықтағы сәйкестіктерді табады, содан кейін LZMA қалған деректерді сығымдайды. Мысалы, 2 ГБ жедел жады бар компьютерде REP 1 ГБ дейінгі арақашықтықта кем дегенде 512 байттық сәйкестіктерді табады, ал LZMA 128 МБ дейінгі арақашықтықта қалған сәйкестіктерді табады. Осылайша, олар бірлесіп жұмыс істеп, 2 ГБ жедел жад шегінде ең жақсы сығылуды қамтамасыз етеді. Ағынмен шығаруға және LZMA-мен бірлесіп жұмыс істеуге бағытталғандықтан, REP бастапқы RZIP нұсқасынан кейбір ерекшеліктері бар. Біріншіден, ол әдепкі бойынша 512 байттан асатын сәйкестіктерді ғана табады, себебі сынақтар көрсеткендей, бұл REP+LZMA сығылуы үшін ең оңтайлы параметр. Екіншіден, ол шамамен жартылай жедел жад көлеміндегі жылжымалы сөздікті пайдаланады, сондықтан сығылған файлдан деректерді қайта оқу қажеттілігі тумайды. REP-тің артықшылығы – оның көбейтуші дөңгелек хэші, ол есептеуде жылдам және дерлік идеал таралымға ие. Үлкен минималды сәйкестік ұзындығы (rzip-тегі 32 байтқа қарағанда 512 байт) қосымша жылдамдық оптимизациясына мүмкіндік берді, сондықтан REP өте жылдам сығылуды қамтамасыз етеді (Intel i3 2100 процессорда шамамен 200 МБ/с).
REP is an alternative implementation of rzip algorithm by Bulat Ziganshin used in his FreeArc archiver as preprocessor for LZMA/Tornado compression algorithms. In FreeArc, REP finds large distance matches and then LZMA compress the remaining data. For example, on computer with 2 GB RAM, REP finds matches that is at least 512 bytes long at the distances up to 1 GB, and then LZMA finds any remaining matches at the distances up to 128 MB. So, working together, they provide the best compression possible on 2 GB RAM budget. Being optimized for stream decompression and collaborative work with LZMA, REP has some differences from the original RZIP implementation. First, by default it finds only matches that are 512+ byte long, since benchmarking proved that this is optimal setting for overall REP+LZMA compression. Second, it uses a sliding dictionary that's about 1/2 RAM long, so decompression doesn't need to reread data from decompressed file. REP's advantage is its multiplicative rolling hash that is both quick to compute and has near ideal distribution. Larger minimal match length (512 bytes compared to 32 bytes in rzip) allowed for additional speed optimizations, so that REP provides very fast compression (about 200 MB/s on Intel i3 2100).
SREP
SREP (SuperREP) – бұл Tridgell-дің LZ компрессор идеясының іске асырылуы, ол сөздікті RAM-да сақтамайды, оның орнына өңделген блоктардың SHA1 хэштерін пайдаланып, олардың мазмұнын салыстырады. Бұл бағдарламаға RAM көлемінен 10 есе үлкен файлдарды сығуға мүмкіндік береді. Декомпрессия файлдың декомпрессияланған бөлігінен деректерді оқу арқылы немесе болашақ сәйкестіктерді жадта сақтау арқылы (болашақ LZ компрессия алгоритмі) жүзеге асырылады. Әрине, болашақ LZ компрессиясы кіріс файлды 2 рет қарауды қажет етеді, бірақ декомпрессияға өте аз жад керек. Бір тәжірибеде 22 ГБ файлды 512 байттық ең кішкентай сәйкестік ұзындығымен және толық 22 ГБ сөздікпен сығыу үшін декомпрессияға бар болғаны 2 ГБ RAM қажет болды.
SREP (SuperREP) is an implementation of Tridgell's idea of LZ compressor that doesn't store its dictionary in RAM, using instead SHA1 hashes of processed blocks to compare their contents. It allows the program to compress files that are about 10x larger than RAM available. Decompression performed either by reading data from decompressed part of file, or by storing in the memory future matches (future LZ compression algorithm). Of course, future LZ compression requires 2 passes over input file but decompression needs tiny memory. In one experiment, 22 GB file compressed with minimum match length of 512 bytes and full 22 GB dictionary required just 2 GB of RAM for decompression.