* Originally in RU.COMPRESS
Приятного тебе дня и незабываемой ночи, Ivan!
Friday January 06 2006, Ivan Kuvshinov writes to Evgeniy Zykov:
EZ>> Посоветуйте, пожалуйста, алгоритмы сжатия для использования в
EZ>> файловых системах. Hапример, что используется в NTFS? Где об этом
EZ>> можно почитать? У меня есть идейка написать модуль ядра для
EZ>> FreeBSD. А то там огромное количество просто текстовых файлов -
EZ>> исходники,
алгоритмов существует множество, нужно определиться с тем, какое ты выберешь
соотношение между скоростью распаковки/упаковки/сжатием
а для этого нужно найти результаты тестирований (погугли, например, archivers
comparision test) и затем загрузить заинтересовавшие тебя программы с сорцами и
потестировать их самому
навскидку из быстрых современных алгоритмов - ucl/lzo (читай в конце), zlib,
lzp (заюючен в конце). ещё для улучшения сжатия текстов при маленьком словаре
(большой словарь ты сделать не сможешь, поскольку при этом пострадает скорость
произвольного доступа к файлу) - очень поможет алгоритм с общим словарём lipt
(ищи на comression.ru/ds)
да, если воспользуешься алгоритмом lzp - копирайты ставь Ильи Гребнева и
Дмитрия Шкарина
IK> Для начала требуется определиться с критериями сжатия, обычно
IK> используют вариации Zip'а, а критерии: скорейшая распаковка,
IK> достаточно быстрая упаковка и на третьем месте коэффицент сжатия. Hу и
IK> ещё, надо определиться с блоками: потому что толку от выигранных
IK> обрезков - ноль, а разбить файл по другому, на переменные блоки,
IK> значит нарушить логику доступа, да и проблемматично это. В
IK> общем дальше думай сам. :-Р
IK> А лучше не NTFS, а начинай с DriveSpace и Stacker, наверняка это
IK> доступней и даже можно самому дизассемблировать, благо всё под DOS
IK> пашет запросто.
смысла никакого. большая часть этих программ - драйверы файловой системы, а
сами алгоритмы там несложные (зато быстрые), как и в ntfs впрочем. вообще, в
этой области нет сложных proprietary алгоритомв, всё интересное доступно в
сорцах
=== Cut ===
ooooo ooo .oooooo. ooooo
`888' `8' d8P' `Y8b `888'
888 8 888 888
888 8 888 888
888 8 888 888
`88. .8' `88b ooo 888 o
`YbodP' `Y8bood8P' o888ooooood8
The UCL Compression Library
Version 1.02
Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003
Markus F.X.J Oberhumer <***@oberhumer.com>
http://www.oberhumer.com
Abstract
--------
UCL is a portable lossless data compression library written in ANSI C.
UCL implements a number of compression algorithms that achieve an
excellent compression ratio while allowing *very* fast decompression.
Decompression requires no additional memory.
UCL is distributed under the terms of the GNU General Public License (GPL).
Overview
--------
UCL implements a number of algorithms with the following features:
- Decompression is simple and *very* fast.
- Requires no memory for decompression.
- The decompressors can be squeezed into less than 200 bytes of code.
- Includes compression levels for generating pre-compressed
data which achieve an excellent compression ratio.
- Allows you to dial up extra compression at a speed cost in the
compressor. The speed of the decompressor is not reduced.
- Algorithm is thread safe.
- Algorithm is lossless.
UCL supports in-place decompression.
Design criteria
---------------
UCL's main design goal was a very high decompression speed while
achieving an excellent compression ratio. Real-time decompression should
be possible for virtually any application. The implementation of the
NRV2B decompressor in optimized i386 assembler code runs about at
the fifth of the speed of a memcpy() - and even faster for many files.
Related work
------------
This section describes how UCL compares to some of my other
compression technologies.
* LZO
---
http://www.oberhumer.com/opensource/lzo/
LZO is distributed under the terms of the GNU GPL.
LZO is a data compression library that focuses on
*extremly* fast decompression, and also implements some
pretty fast compression algorithms.
* NRV
---
http://www.oberhumer.com/nrv
NRV is not publicly available.
NRV started life as an experimental compression library and has since
grown into a meta-generator for compression algorithms of almost any kind.
NRV supports a virtually unlimited number of different algorithms by
glueing typical data compression components. By using a combination
of sophisticated high level abstractions and advanced information
theory concepts it usually achieves an incredible compression ratio.
* UCL
---
http://www.oberhumer.com/opensource/ucl/
UCL is distributed under the terms of the GNU GPL.
UCL is a re-implementation of some concrete algorithms that have
proven especially useful during the NRV development.
As compared to LZO, the UCL algorithms achieve a better compression
ratio but decompression is somewhat slower. See below.
* UPX
---
http://www.oberhumer.com/opensource/upx/
UPX is distributed under the terms of the GNU GPL.
UPX is a very powerful executable packer that can be configured
to use either NRV or UCL for actual compression services. It
currently supports the NRV2B and NRV2D algorithms.
Portability
-----------
UCL's decompressors should work on any system around - they could even
get ported to 8-bit processors such as the Z-80 or 6502.
UCL's compressors currently require at least 32-bit integers. While
porting them to more restricted environments (such as 16-bit DOS)
should be possible without too much effort this is not considered
important at this time.
How fast is fast ?
------------------
Here are some rough timings originally done on an ancient Intel Pentium 133:
memcpy(): ~60 MB/sec
LZO decompression in optimized assembler: ~20 MB/sec
LZO decompression in C: ~16 MB/sec
UCL decompression in optimized assembler: ~13 MB/sec
Your mileage may vary and you're encouraged to run your own benchmarks.
Also note that UCL's C language decompressors are not optimized very
much yet, so you should use the assembler versions whenever possible.
Documentation (preliminary)
---------------------------
Currently UCL implements 3 of NRV's algorithms, namely NRV2B,
NRV2D and NRV2E.
UCL is a block compressor, i.e. each memory block passed to the
compressor will get compressed independently.
The API of UCL is basically identical to that of LZO. Due to current
lack of documentation you are strongly advised to download LZO
and study its documentation and example programs first:
http://www.oberhumer.com/opensource/lzo/
The API of UCL is actually very simple: there's a compress() function
that compresses a block of memory, and there's a decompress() function
that handles decompression. That's more or less all you need to know.
See the `examples' directory for some demo programs.
UCL will expand non-compressible data by a little amount. I suggest
using this formula for a worst-case expansion calculation:
output_block_size = input_block_size + (input_block_size / 8) + 256
COPYRIGHT
---------
The UCL library is Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002,
2003 by Markus Franz Xaver Johannes Oberhumer <***@oberhumer.com>.
The UCL library is distributed under the terms of the GNU General Public
License (GPL). See the file COPYING.
Special licenses for commercial and other applications which
are not willing to accept the GNU General Public License
are available by contacting the author.
=== Cut ===
=== Cut ===
section 1 of 1 of file lzp.rar < uuencode 97 (v58) by R.E.M. >
begin 644 lzp.rar
M4F%R(1H'`#O0<P@`#0````````#->G2`D"P`OP(``"T'```"HTX;K):$LC(=
M-0<`(````$-?3%I0+F@`L)"M<:DO(***@17S._8-X]ELT,R9/%,D_6JM+@TSW&
M](DD#U?*<+4CQY2G.JX35ZMV[1R<?;*9K[=CPI;$4\BUSC0-=***@7YW)"VW
M:^VMGTP3J_GC4?S3VAMI:#!N;\(8W(:'@N8#S]WN8$\V_\+]CK"NYY1XN7T1
MD&.$&*SJ_XCSO(9</0%D0?&74(/QS]<6/:(@\UL,_49O=JU84%A7=T7FP[9D
MHK91]](VO\$V%WF&6XW`(=01J<#CO;P3EBPJ7N-I]"U1<G4RZB4</_[:KH73
MYHJQ':$'`Q>U:*ZU\\^XBN?S/YP0F%5(3JD]1:5I<***@OJ''YU1D(I
M[ZRVB49[D*C(]B")[A\F[KN_8>7JB\*^]DVJXQ%!K8QE2O[>JZE[4?1P?IS<
MOB$GBX"@)R%3UQ!@Z4)!'>$D*BJ\[I+=C&+KMZ"U^(8-^9O,3T9RW6>M^.LM
M6J*7T098:SA$K4Q#+:R2;8)!KNO960<0.,QYQ]9&O$?'M78FV;Z.:,:G4YA_
MI7AL]ZK,Q$ZCQ6GG$(]X.G;?OB:/CY<1/,?_90=&DD]PML3LLB6L#TA??A:@
M@">;BQ%XC22"U-8^@8/J1"3/[CJSW^,VO04+)?[+<T6BR3N!D(+&I(-E+JP&
MZB$^FW:X+B&=/:L.9[!5'D-V!5:JSZ39OV+SU,/"(0O$CS0>R*.;R_C7<`C_
M?;!)S^C%$YP!]"&*AVX-QQ/UT(-P&H%;Q64Q?T6J8EPK5-`'?8(***@G&]A=,
M6^U3Q_,-L>94:]K?+UZ4,(Z?%4MD<Z12;`[Z=@*N6S;+/J7!-VM`Z<&SR)2*
MFPHN+X_\#BA?'$***@0)N)RI9BR@$?S;@VVT"P$IM"1+H<8U%1Q[[O%XL4"NX
MC"(***@ZU>4'1#P,@10\O.J9(R\`2RV*9L]H*/<98S#/Q9]@%QL54``+^(9_:I
M_]2HN'20D"X`S@@``"P?```".39]FB2JH3(=-0D`(````$-?3%I0+F-P<`#P
M8(2.B=Z5RZDV%WX4[6`83Z@&2`>60FSBF?Q<IZ-=I-:FF:%E#Z)07`&YR[N9
M*YQ$B/6N*4D#3%'4'2S:]\4<\K.6<5=2FJUMFN+F$5=B%/?5-#Y=CX"0S;.`
M]4V#\***@2`W!AZO3B6O]>S01(***@7?%!V'>N#O<3S-UR$JH;X+3=#_>1?L2"#
M<%4F*8.7&>YDG",R\\8$JLQ`(]L2,;OJ-4[FK&W&T(***@H"65CQ_0ZU#)%
M^,4!'XO_T0-I/\B^-D9D%\*)6#T1=?;0R?DTO$``1,"F<!1/%N"NM$/:"'JD
MR^<=DWK6;XG\.?;OM+_>3$B-7.1PUC4^\F;O*V@/)=Z\Q<ZUAW;M)B^$R^@@
M5V3)NP!0;"Z0ERE+A\Z8L;A>K5(%Q>Q^0"FHIS\)Z92W%-[ITV>-U2Q^V,=S
M25)!M+EEIV,&?5C_]UQ*RF;.^EF:X5D9U`_*NL_KX1^LO[_UJ7,-^E"Q]7;R
M(&NM)W/(MAR+9O_+,&H?XT7'***@D_28VA[35GE,W(_8YD>`>0AS]6S.M*>F
MF<XL[@2$6/09,"/]$LZW\`'ZA+TV08*P/=(HX-P/`3&A%5^SQN,$D*RB4]*M
MR!U\:OS**_>4#YVX(IL,<PU,(W8[_KH!R3>`70"``9IK>=;VUQHO-***@Y
M8.B4JYN8#YS'TRZE5_:`[E=DH3M@*?]=2OW-3&RT.S*%E#`P!_F^=GL%LC#<
MR+6^-(@)LW(21.G&/XPQ3B:>A;`2ZX251$-***@Z:PW69RIX-0R]ZJHH3VW6?
M:)C^@`S?5[H41)4;***@Z^)4,&'\:BNOR+UXT_XT2W[:WRU%R1N<<<01GR
M!05O&!N.T%=Q>BFW?[=P"%Z`[8/K$/VX`)0Y7ZV,@Z"8D=5MQ44#%@COE6U4
M3NI^3.TA0</;H?:^=&'[FAWGM'NN4VXU-X0>FU%5/T]X605`WAURQ2P886B/
MA=1N,.!2M^V/OAXW9.>R>[D2,<P'?C2H[)N;Y0<4%NV^T)#$/*@[V)]VZ3*)
M7I3EO]TT1Y0J[5>J[<+<8>(***@68%17K<)***@IH`V=?OQFI,B8$NXL'?(6
M%F%R\C^CT=C90*@:+Y9FC$B#W^5[C`DD5LGVZF;0%G@,2LZZ(L<G>$F%!0=6
MMG&5GTL&FY*6(M>A<F37Q6*3[6^$#L^\,)A&#FT.(RY#V*.[G/8T`E]E%$WF
M?HP^$%DY^EA-TD?2&N["EN=2(L(&E'!?ZS-69UE@<'&Y_0R^RS8.@`T^1BU<
M"792S?Z(8$`A&,4G5M?J[-\]H=?Q_0WD?@,)]WO=E9`<550\TR?OIY]Z:I4X
M-C]YTCQ:*P=;`?;J]<SWB602/PZN[0B0D/1*J=-.SC]$CEC@[E.,GE7H`9._
M5X"71620NPY;2L+]J4JXX/CV+-FH*RUNQ&(@?***@S*WPY=3,9RT;LSGJ53;^^
M;13H(J8OF,(&!24B"0.-JT_?IDQ3;=!UW.1E++GOC#;O8,^2AR($43MBZ-"X
M-0<S3&LI+DIJJ20-M+&IL;)F09+W@'J[3^/(S):^LI#GIV6$L8]PMIFDIEPO
M.($R!'***@F3IEPE/P6)HQ1'DOL_[3>.(7VMWL/Z6EI.-J^^`"(#MWM11L%^MX
MN9I2T^-W<.:<3=7G[I1EH[$:MSO/Q/'UEI[X-A'@QT";K>7N"^Z:87T4OGHV
M<$$$;:3CC$)IKDVMY`BK[@4.[/S?,O+P^TEQ2+G7YPA1D!14QU]6021R>%=]
M2).T1JJ@'ULIFCQ^U&/YFLX?<@\IXP[7=A;"@0^,U`DPX.NC5-RJ7()`I`-G
M1ZY2ZQMO,JQ0!;">W*XZF![_&T8;\+D5JK&[&>MG`IKZ/YRP,)1L$%T0IK"8
M3W@]__VGE=?\@3T?.9M.<&>!4B/EI!=F?@U#">E1XIH]?N1MA?%AAJ+3>+8?
M0S_(T.VU'<;YJ3"?9U\S"X<E8X;J69P\J[1."<$RPN""C<UM2+NM6#T60C1[
MY*P/0LX$"]G:-!&P^***@6M*XTD?W3JOO2]\^MNH$0S&5:***@SY1KV\)3FTR1W
M?O]IS:@],P!=7MTMH3?X9/,Y)+Y3Z/6Y-.1)U;FA^E?)(%V?_\1!)/`\$!,>
M_HEC61$5,L-***@BB0%B0%C,+>D7?;YGS$UK$:W8`D)\8]:"#,$:)6)Y$:;SY?
MK9#-:<L\8_)OKAF"J!'7DJF^Z$73:Z\5(G*++X-K4OKIDQ"N#=L^&B=!EK(T
M&"DE]/]OC2]***@7I46FD]GOD'0)3/***@JN_;3>U:@++GX:R1%L*FY`HC,
MX?(U0,>_<]NI&N=G-<]U6%#`QP^G9+E.[_CT#]^I&+^+41(JDWH:+JQ]#J@$
MDZB9R;++)^3RQ2N%#2PYV#T\;<DV^;7EAK<\^(4"EPI="MZ<$*OM5Z:;KM+A
MHT/[DT>2X-+#W1MH.M"\/K-:#U=WFD3LT1=CGN3D/B:U@>)G"E2A(^RJ\3^2
MWX2Z)<***@96V_FM7YRCE?;"]6ZNCF?:9XL3B)>SAU'HG63).C8'N.1V')AXW5
MN=+0ZJH\HU`H-'W#\4R$AW;BTVX[RP3".$B5BZQJ&3"*N^N[F_L>K*T$SY=Q
MI,%>`/56M<4`NLJ4X"8K"!T?!`$1,F/\`3+.NC$FL%AVT(F0*".?B6V/!Q0(
MGMN:&%=!&/3&W"$9WQ;%>!CLN2LY;A7_FB.?Z;K*X40]>4EZJY7[[E3_I!9H
M,J(`5:UNE%>D0$\_O#C1P/@;XMC'[;+/)AM,'`6&VE%Y3R%&\&:TL\Z,QOP,
M_,D2#HT*0G-Z7UBX)YO&*EUZH&D6O.)J.=2LEX5VLS_C2_06[1[9E(Z!2VSP
MUH6`U+O&VH,%CG,B9XU0`?Z,I8[F8$>"UU[D#`"`%MU&:7-2O1S#CQ,9B2-D
M\QR,`PGE"!X_U;1OS_<STTTK]9[JS4))OG9C=FFA<V4*#:C(3/,Z]X*?&<^L
MY@<DVL2-.]9CU;A!?C_<E>MW\%3VF`L=2-KH)C,'9CY%'6""U%==3LEX50``
.OXAG]JG_U,0]>P!`!P``
`
end
sum -r/size 56239/4262 section (from "begin" to "end")
sum -r/size 28023/3074 entire input file
=== Cut ===
Bulat, mailto:bulat_z-AT-mail.ru
... Иногда для того, чтобы изменить свое восприятие мира,
... люди пытаются изменить сам мир