Artikel ieu geus kadua dina topik komprési data-speed tinggi. Artikel kahiji ngajelaskeun hiji compressor operasi dina laju 10 GB / detik. per inti processor (komprési minimum, RTT-Min).
Kompresor ieu parantos dilaksanakeun dina alat-alat duplikator forensik pikeun komprési anu berkecepatan tinggi tina dumps média panyimpen sareng ningkatkeun kakuatan kriptografi; éta ogé tiasa dianggo pikeun ngompres gambar mesin virtual sareng file swap RAM nalika nyimpen dina laju anu gancang. drive SSD.
Artikel kahiji ogé ngumumkeun ngembangkeun hiji algoritma komprési pikeun compressing salinan cadangan HDD na SSD disk drive (komprési sedeng, RTT-Mid) kalawan parameter komprési data nyata ningkat. Ayeuna, compressor ieu tos siap sareng tulisan ieu ngeunaan éta.
Kompresor anu ngalaksanakeun algoritma RTT-Mid nyayogikeun rasio komprési anu dibandingkeun sareng arsip standar sapertos WinRar, 7-Zip, beroperasi dina modeu-speed tinggi. Dina waktu nu sarua, laju operasi na sahenteuna urutan gedena luhur.
Laju packing / unpacking data mangrupakeun parameter kritis nu nangtukeun wengkuan aplikasi tina téhnologi komprési. Teu aya kamungkinan yén saha waé bakal mikirkeun komprési terabyte data dina laju 10-15 MegaBytes per detik (ieu persis laju arsip dina modeu komprési standar), sabab éta bakal nyandak ampir dua puluh jam kalayan beban prosesor pinuh. .
Di sisi anu sanés, terabyte anu sami tiasa disalin dina laju 2-3Gigabytes per detik dina sapuluh menit.
Ku alatan éta, komprési inpormasi volume ageung penting upami dilaksanakeun dina laju anu henteu langkung handap tina laju input/output nyata. Pikeun sistem modern ieu sahenteuna 100 Megabytes per detik.
compressors modern bisa ngahasilkeun speeds misalna ngan dina mode "gancang". Dina modeu ayeuna urang bakal ngabandingkeun algoritma RTT-Mid sareng compressor tradisional.
Uji komparatif tina algoritma komprési énggal
The RTT-Mid compressor digawé salaku bagian tina program test. Dina aplikasi nyata "kerja" gawéna leuwih gancang, ngagunakeun multithreading bijaksana tur ngagunakeun "normal" compiler, teu C #.
Kusabab compressor anu dianggo dina uji komparatif diwangun dina prinsip anu béda sareng jinis data anu béda-béda dikomprés, pikeun objéktivitas tés, metode ngukur "suhu rata-rata di rumah sakit" dianggo ...
File dump séktor-demi-sektor tina disk logis sareng sistem operasi Windows 10 diciptakeun; ieu mangrupikeun campuran anu paling alami tina sababaraha struktur data anu sayogi dina unggal komputer. Compressing file ieu bakal ngidinan Anjeun pikeun ngabandingkeun laju sarta darajat komprési tina algoritma anyar jeung compressors paling canggih dipaké dina archivers modern.
Ieu file dump:
File dump dikomprés nganggo kompresor PTT-Mid, 7-zip, sareng WinRar. Kompresor WinRar sareng 7-zip disetel ka laju maksimal.
Compressor ngajalankeun 7-pos:
Ieu beban processor ku 100%, bari laju rata-rata maca dump aslina nyaeta ngeunaan 60 MegaBytes / detik.
Compressor ngajalankeun Winrar:
Kaayaanana sami, beban prosesor ampir 100%, rata-rata laju bacaan dump sakitar 125 Megabytes / detik.
Sapertos dina kasus saméméhna, laju arsip dibatesan ku kamampuan prosesor.
Program uji compressor ayeuna jalan RTT-Mid:
Potret layar nunjukkeun yén prosésor dimuat dina 50% sareng dianggurkeun sesa waktosna, sabab teu aya tempat pikeun unggah data anu dikomprés. Disk unggah data (Disk 0) ampir pinuh dimuat. Laju maca data (Disk 1) variasina pisan, tapi rata-rata leuwih ti 200 MegaBytes/detik.
Laju compressor diwatesan dina hal ieu ku kamampuhan pikeun nulis data dikomprés kana piringan 0.
Ayeuna rasio komprési tina arsip anu dihasilkeun:
Ieu tiasa katingali yén compressor RTT-Mid ngalakukeun padamelan anu pangsaéna pikeun komprési; arsip anu diciptakeun nyaéta 1,3 GigaBytes langkung alit tibatan arsip WinRar sareng 2,1 GigaBytes langkung alit tibatan arsip 7z.
Waktos waktos nyiptakeun arsip:
- 7-pos - 26 menit 10 detik;
- WinRar - 17 menit 40 detik;
- RTT-Mid - 7 menit 30 detik.
Ku kituna, sanajan hiji test, program non-dioptimalkeun, ngagunakeun algoritma RTT-Mid, éta bisa nyieun arsip leuwih ti dua satengah kali leuwih gancang, bari arsip tétéla jadi nyata leuwih leutik batan pesaing na ...
Anu henteu percanten kana layar tiasa pariksa kaaslianana sorangan. Program tés sayogi di , ngundeur tur pariksa.
Tapi ngan dina prosesor kalayan rojongan AVX-2, tanpa rojongan pikeun parentah ieu compressor teu jalan, sarta teu nguji algoritma dina prosesor AMD heubeul, aranjeunna slow dina watesan executing parentah AVX ...
Metoda komprési dipaké
Algoritma ngagunakeun métode pikeun ngindeks fragmen téks anu diulang dina granularitas bait. Metoda komprési ieu geus dipikawanoh pikeun lila, tapi teu dipaké sabab operasi cocog pisan mahal dina watesan sumberdaya diperlukeun tur merlukeun leuwih waktos ti ngawangun kamus. Janten algoritma RTT-Mid mangrupikeun conto klasik pikeun mindahkeun "deui ka hareup" ...
Kompresor PTT ngagunakeun panyeken panéangan pertandingan-speed tinggi anu unik, anu ngamungkinkeun urang nyepetkeun prosés komprési. A scanner timer dijieun, ieu téh "pesona abdi ...", "Éta rada mahal, sabab sagemblengna handmade" (ditulis dina assembler).
Panyeken milarian pertandingan dilakukeun dumasar kana skéma probabilistik dua tingkat: kahiji, ayana "tanda" pertandingan di-scan, sareng ngan saatos "tanda" diidentifikasi di tempat ieu, prosedur pikeun ngadeteksi pertandingan nyata. dimimitian.
Jandéla pilarian cocok boga ukuran unpredictable, gumantung kana darajat éntropi dina blok data olahan. Pikeun data lengkep acak (incompressible) boga ukuran megabytes, pikeun data kalawan pangulangan sok leuwih badag batan megabyte a.
Tapi seueur format data modéren anu teu tiasa dikomprés sareng ngajalankeun alat panyeken sumberdaya-intensif ngalangkungan aranjeunna henteu aya gunana sareng boros, janten panyeken ngagunakeun dua modeu operasi. Mimiti, milarian bagian tina téks sumber anu tiasa diulangan; operasi ieu ogé dilaksanakeun nganggo metode probabilistik sareng dilaksanakeun gancang pisan (dina laju 4-6 GigaBytes / detik). Wewengkon anu tiasa cocog teras diolah ku scanner utama.
Komprési indéks henteu éfisién pisan, anjeun kedah ngagentos fragmen duplikat sareng indéks, sareng susunan indéks sacara signifikan ngirangan rasio komprési.
Pikeun ningkatkeun rasio komprési, teu ukur patandingan lengkep string bait anu indéks, tapi ogé parsial, lamun string ngandung loyog jeung bait unmatched. Jang ngalampahkeun ieu, format indéks ngawengku widang topeng cocok nu nunjukkeun bait cocog dua blok. Pikeun komprési malah leuwih gede, indexing dipaké pikeun superimpose sababaraha blok sawaréh cocog kana blok ayeuna.
Sadaya ieu ngamungkinkeun pikeun ménta dina PTT-Mid compressor rasio komprési comparable mun compressors dijieun maké métode kamus, tapi gawéna leuwih gancang.
Laju algoritma komprési énggal
Lamun compressor nu ngoperasikeun kalawan pamakéan éksklusif memori cache (4 Megabytes diperlukeun per thread), laju operasi dibasajankeun 700-2000 Megabytes / detik. per inti processor, gumantung kana jenis data keur dikomprés sarta gumantung saeutik kana frékuénsi operasi processor.
Kalayan palaksanaan multi-threaded of compressor nu, scalability éféktif ditangtukeun ku ukuran tina cache tingkat katilu. Salaku conto, gaduh 9 MegaBytes mémori cache "dina papan", teu aya gunana pikeun ngaluncurkeun langkung ti dua benang komprési; lajuna moal ningkat tina ieu. Tapi kalayan cache 20 Megabytes, anjeun parantos tiasa ngajalankeun lima benang komprési.
Ogé, latency RAM janten parameter penting anu nangtukeun laju compressor nu. Algoritma ngagunakeun aksés acak ka OP, sababaraha nu teu meunang kana mémori cache (ngeunaan 10%) sarta kudu dianggurkeun, ngantosan data ti OP, nu ngurangan kagancangan operasi.
Nyata mangaruhan laju compressor jeung operasi sistem input / output data. Requests ka OP ti I / O block requests pikeun data ti CPU, nu ogé ngurangan laju komprési. Masalah ieu penting pikeun laptop sareng desktop; pikeun server éta kirang signifikan kusabab unit kontrol aksés beus sistem anu langkung maju sareng RAM multi-kanal.
Sakuliah téks dina artikel urang ngobrol ngeunaan komprési; decompression tetep di luar lingkup artikel ieu saprak "sagala katutupan di coklat". Decompression leuwih gancang sarta diwatesan ku speed I / O. Hiji inti fisik dina hiji thread gampang nyadiakeun speeds unpacking 3-4 GB / detik.
Ieu alatan henteuna operasi pilarian cocok salila prosés decompression, nu "eats up" sumberdaya utama processor na cache memori salila komprési.
Reliabiliti neundeun data dikomprés
Sakumaha nami sadaya kelas parangkat lunak anu nganggo komprési data (arsip) nunjukkeun, aranjeunna dirancang pikeun neundeun inpormasi jangka panjang, sanés mangtaun-taun, tapi salami abad sareng millennia ...
Salila neundeun, média panyimpen leungit sababaraha data, ieu conto:
Pamawa inpormasi "analog" ieu umurna sarébu taun, sababaraha fragmen leungit, tapi sacara umum inpormasina "bisa dibaca" ...
Henteu aya produsén anu tanggung jawab pikeun sistem panyimpen data digital modern sareng média digital pikeun aranjeunna nyayogikeun jaminan kaamanan data lengkep salami langkung ti 75 taun.
Sareng ieu mangrupikeun masalah, tapi masalah anu ditunda, turunan urang bakal ngarengsekeunana ...
Sistem panyimpen data digital tiasa leungit data henteu ngan saatos 75 taun, kasalahan dina data tiasa muncul iraha waé, bahkan nalika ngarékamna, aranjeunna nyobian ngaminimalkeun distorsi ieu ku ngagunakeun redundansi sareng koréksi ku sistem koréksi kasalahan. Sistem redundansi sareng koréksi teu tiasa salawasna mulangkeun inpormasi anu leungit, sareng upami éta, henteu aya jaminan yén operasi restorasi parantos réngsé leres.
Sarta ieu ogé masalah badag, tapi lain nunggak, tapi ayeuna.
Kompresor modern anu dianggo pikeun ngarsipkeun data digital diwangun dina sababaraha modifikasi tina metode kamus, sareng pikeun arsip sapertos kitu leungitna sapotong inpormasi bakal janten kajadian anu fatal; bahkan aya istilah anu ditetepkeun pikeun kaayaan sapertos kitu - arsip "rusak" ...
Kaandalan anu rendah pikeun nyimpen inpormasi dina arsip nganggo komprési kamus pakait sareng struktur data anu dikomprés. Inpormasi dina arsip sapertos kitu henteu ngandung téks sumber, jumlah éntri dina kamus disimpen di dinya, sareng kamus sorangan sacara dinamis dirobih ku téks anu dikomprés ayeuna. Upami sempalan arsip leungit atanapi rusak, sadaya éntri arsip saterasna teu tiasa diidentifikasi ku eusi atanapi panjangna éntri dina kamus, sabab henteu écés naon anu cocog sareng nomer éntri kamus.
Teu mungkin pikeun mulangkeun inpormasi tina arsip "rusak" sapertos kitu.
Algoritma RTT dumasar kana metode anu langkung dipercaya pikeun nyimpen data anu dikomprés. Éta ngagunakeun metode indéks akuntansi pikeun ngulang fragmen. Pendekatan komprési ieu ngamungkinkeun anjeun pikeun ngaminimalkeun akibat tina distorsi inpormasi dina médium panyimpen, sareng dina sababaraha kasus sacara otomatis ngabenerkeun distorsi anu timbul nalika neundeun inpormasi.
Ieu alatan kanyataan yén file arsip dina kasus komprési indéks ngandung dua widang:
- widang téks sumber kalawan bagian ulang dihapus ti dinya;
- médan indéks.
Widang indéks, anu penting pikeun pamulihan inpormasi, ukuranna henteu ageung sareng tiasa diduplikasi pikeun neundeun data anu dipercaya. Ku alatan éta, sanajan sempalan tina téks sumber atawa Asép Sunandar Sunarya indéks leungit, sagala informasi sejenna bakal disimpen deui tanpa masalah, sakumaha dina gambar kalawan médium gudang "analog".
Kalemahan tina algoritma
Teu aya kaunggulan tanpa kalemahan. Métode komprési indéks henteu niiskeun sekuen pengulangan pondok. Ieu alatan watesan métode indéks. Indéks sahenteuna sahenteuna 3 bait sareng tiasa dugi ka 12 bait. Upami pangulangan dipanggihan kalayan ukuran anu langkung alit tibatan indéks anu ngajelaskeun éta, maka éta henteu dipertimbangkeun, henteu paduli sabaraha sering pangulangan sapertos dideteksi dina file anu dikomprés.
Metoda komprési kamus tradisional éféktif compresses sababaraha pangulangan panjang pondok sahingga ngahontal rasio komprési luhur batan komprési indéks. Leres, ieu dihontal kusabab beban anu luhur dina prosésor sentral; supados metode kamus ngamimitian ngompres data langkung éfisién tibatan metode indéks, éta kedah ngirangan laju ngolah data ka 10-20 megabytes per detik sacara nyata. pamasangan komputasi kalayan beban CPU pinuh.
speeds low misalna teu bisa ditarima keur sistem panyimpen data modern jeung leuwih dipikaresep "akademik" ti praktis.
Darajat komprési informasi bakal ngaronjat sacara signifikan dina modifikasi salajengna tina algoritma RTT (RTT-Max), nu geus di ngembangkeun.
Janten, sapertos biasa, diteruskeun ...
sumber: www.habr.com