— RU.COMPRESS
From : Igor Pavlov 2:5020/400 08 Jan 99 00:46:55
To : All
Subj : Re: Êàê ðóëèòü ïîòîêè ìåæäó êîäåðîì è äîæèìàëêîé ???!!!
From: "Igor Pavlov" <igor@znanie.ufanet.ru>
Bulat Ziganshin wrote in message <915747717@f26.n5093.z2.ftn>...
> BZ>> Hó è ñòàíäàðòíûå èäåè -
> BZ>> ïðåâðàòèòü ïîñëå ïîñòðîåíèÿ õàôìåíîâñêèõ òàáëèö íåâûãîäíûå ñòðîêè
> BZ>> íàçàä â ñèìâîëû;
> SK> Hàäî ïîäóìàòü. Ýòî äåøåâî ïî âðåìåíè è íåìíîãî ïîçâîëèò âûèãðàòü
> SK> ñæàòèå.
>
> Î÷åíü-î÷åíü ìàëî. Hà ñàìîì äåëå âñå ýòî - ìóñîð. Âîò òà ýâðèñòèêà - ýòî äà,
>íàõîäêà.
Îêàçàëîñü íå ìóñîð, íàäî òîëüêî íå ïîñëå, à íà õîäó.
Hî è ïîñëå ìîãëî ïîìî÷ü íà íåêîòîðûõ ôàéëàõ,
à ìîæíî åùå ïîïðîáîâàòü äåëàòü äâà ïðîõîäà:
äåðåâî ìîæíî íå ñêàíèðîâàòü çàíîâî - ïðàâäà ïàìÿòè óéäåò óéìà,
íî çàòî åñòü øàíñ îáîéòè cabarc
> Åäèíñòâåííîå, ÷òî íå ïîçâîëÿåò ìíå èñïîëüçîâàòü ýòèõ ëèäåðîâ - ñëèøêîì
>áîëüøîå âðåìÿ ðàñïàêîâêè. ß ïàêóþ ñåé÷àñ cabarc'îì, êîòîðûé ïî ðàñõîäó ïàìÿòè
>íå óñòóïàåò boa/acb/rkive, à ïî âðåìåíè óïàêîâêè íåíàìíîãî áûñòðåå, ñêàæåì,
>boa (íà cc).
Äëÿ ëþáîãî
àëãîðèòìà ñæàòèÿ íàéäóòñÿ íàáîðû ôàéëîâ íà êîòîðûõ ýòè àëãîðèòìû
íà÷èíàþò ðàáîòàòü íàìíîãî ìåäëåííåå.
Ó ìåíÿ åñòü òàêîé ôàéë (24-bitîâàÿ êàðòèíêà îäíà èç kodak'îâ from image
lossless artest) ,
íà êîòîðîì ñêîðîñòü (pkzip25 -max), (rar -m5) è ò.ä.
ïàäàåò â 5 - 10 ðàç.
Äëÿ cabarc'à êîëè÷åñòâî òàêèõ "ïëîõèõ" ôàéëîâ HÀÌHÎÃÎ áîëüøå.
È ïîñëåäñòâèÿ íàìíîãî êàòàñòðîôè÷íåå ÷åì ó ZIP, äóìàþ ñêîðîñòü ìîæåò
óïàñòü â ðàç 100 èëè áîëüøå. È âñå ýòî óñóãóáëÿåòñÿ ïðè óâåëè÷åíèè
ñëîâàðÿ.
Ïðèìåð òàêîãî "ïëîõîãî" äëÿ cabarc'a ôàéëà:
kennedy èç Canterbury.
Ìàéêðîñîôò ñ ýòèì ñìèðèëîñü, ò.ê. cabarc ïðåäíàçíà÷åí äëÿ çàäà÷ òèïà:
îäèí ðàç çàïàêóþ - ìèëëèîí ðàç ðàñïàêóþò.
Âîò ðåøèòü ïðîáëåìó òàêèõ "ïëîõèõ" ôàéëîâ áûëî áû õîðîøî
> SK> Êñòàòè, èìõî áûëî áû ïðàâèëüíåå ðàçäåëèòü àêò íà êàòåãîðèè, Òèïà
> SK> ëç â îäíîì çà÷åòå, à âñå îñòàëüíûå â äðóãîì. Ïëþñ ðàçäåëåíèå ïî
> SK> ðàñõîäóåìîé ïàìÿòè. Ýòî áûëî áû ÷åñòíåå. À òî îòñâîïÿò ãèãàáàéò è
> SK> ñîðòèðóþò ñòî áàéò äâà ÷àñà ;))
>
> 16 ìåãàáàéò - ýòî îò áåäíîñòè :( À act ìíå íå íðàâèòñÿ âñå áîëüøå è áîëüøå.
>Ñäåëàé ñâîé òåñò?
À ACT 2.0 ÷åì ïëîõ?
The ACT 2.0 web pages are now up:
http://personal.nbnet.nb.ca/jeffg/act2.html
The links to download the test data are at:
http://personal.nbnet.nb.ca/jeffg/act2-files.html
> BZ>>>> Òàê âîò, òàê ñäåëàíî â cabarc è æìåò îí íåïëîõî. ß (è íå òîëüêî
> BZ>>>> ÿ) ïîëó÷èëè òîëüêî óõóäøåíèå ñòåïåíè ñæàòèÿ ïðè òàêîì ïîäõîäå.
imho óõóäøåíèÿ áûòü íå äîëæíî.
Ïðîñòî ñëîòû âûãîäíåå ïî ñêîðîñòè.
> BZ>> Îïòèìàëüíûå ìàêñ. äèñòàíöèè íèêàê íå ñâÿçàíû ñ âûáîðîì
> BZ>> õåøèðîâàíèÿ
Imho ïîâûøàòü ðàçìåð ñëîâàðÿ äëÿ îáû÷íîãî àëãîðèòìà c lazy matching ñòîèò äî 1
mb,
à äëÿ îïòèìàëüíîãî lzh ãäå-òî äî 2-óõ mb.
- ---
Èãîðü
--- ifmail v.2.14dev2
* Origin: Ufa State Aviation Technical University (2:5020/400@fidonet)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/26 08 Jan 99 01:30:17
To : All
Subj : Èòàê, êàêèì ÿ âèæó LZH ñëåäóþùåãî ïîêîëåíèÿ
* Crossposted in RU.COMPRESS
Hello All!
Ïîæàëóé, íà÷íó ñ ïàðû ñëîâ î ïîêîëåíèÿõ lzh-àðõèâàòîðîâ. ß ëè÷íî ýòó
êëàññèôèêàöèþ ïðîâîæó òàê:
1. lharc 1.x, pkzip 1.x, pak (îò nogate consulting - õîðîøåå íàçâàíèå ;)
2. ar002 è âñå îñíîâàííîå íà íåì ñ äëèíîé ñëîâàðÿ 8-16k (lha 2.x, zoo 2.10 ah,
bsarc 1.2-1.3)
3. ar002-derived àðõèâàòîðû ñî ñëîâàðåì 32ê: arj(26k), pkzip 2.x, bsarc 1.6-2.0
4. Àðõèâàòîðû ñî ñëîâàðåì 64k: rar, uc2, arjz
5. Àðõèâàòîðû ñî ñëîâàðåì > 64k: yac (îí îáîãíàë ñâîå âðåìÿ, åãî ïðîñòî íå íà
÷åì áûëî çàïóñêàòü), rar (ÿ åãî ñ÷èòàþ ïåðâûì ïîëíîöåííûì ïðåäñòàâèòåëåì ýòîãî
ïîêîëåíèÿ) è àðõèâàòîðû, äðóæíî âûñûïàâøèå âåñíîé 97-ãî (ace, jar, cabarc), à
òàêæå íåìíîãî çàïîçäàâøèé imp è ñîâñåì çàïîçäàâøèé arjz. Ýòî ñîâðåìåííîå
ïîêîëåíèå lzh-àðõèâàòîðîâ, è ïðè áîëüøîé ñõîæåñòè èõ îñíîâû ó âñåõ åñòü ñâîÿ
èçþìèíêà:
MM â rar
õîðîøåå ñæàòèå exe'øíèêîâ â ace (ÿ òàê è íå ïîíÿë - êàê?)
ñëîâàðü â jar
îáùåå óëó÷øåíèå ñæàòèÿ âñåõ òèïîâ äàííûõ, òàáëèöû è E8 â cabarc
õèòðþùèé àëãîðèòì áûñòðîãî ïîèñêà â imp
E9 â arjz :)
>---------------------------------------------------------------------
Òåïåðü íàñòàëà, ìíå êàæåòñÿ, ïîðà âûõîäèòü íà àðõèâàòîðû ñëåäóþùåãî
ïîêîëåíèÿ. Ïîñêîëüêó ðåçåðâû óâåëè÷åíèÿ ðàçìåðà ñëîâàðÿ ìû èñ÷åðïàëè, ïðèäåòñÿ
èñêàòü èõ â óëó÷øåíèè êîäèðîâàíèÿ. ß ñ÷èòàþ, ÷òî àðõèâàòîð ñëåäóþùåãî ïîêîëåíèÿ
äîëæåí îñíîâûâàòüñÿ íà êîäèðîâàíèè îò cabarc, íî ñ äîáàâëåíèåì ñïåöèôè÷íûõ
àëãîðèòìîâ èç äðóãèõ àðõèâàòîðîâ, â ïåðâóþ î÷åðåäü ñëîâàðÿ è äåëüòà-òàáëèö. ÌÌ,
ïî-ìîåìó, íåîáÿçàòåëüíà - íåñæàòûõ ÌÌ-äàííûõ â îêðóæàþùåì íàñ ìèðå ñòàíîâèòñÿ
âñå ìåíüøå è ìåíüøå. Õîòÿ, íà ðåñóðñàõ ê òîìó æå Äóìó ýòî åùå äàâàëî
ðåçóëüòàòû.
ß íå çíàþ âñåõ ïîäðîáíîñòåé cabarc (ñàìè áåðèòå åãî è ðàçáèðàéòåñü), íî ïîêà
ïðåäïîëàãàþ, ÷òî åãî ñõåìà ïîèñêà ÿâëÿåòñÿ ïðèíöèïèàëüíîé ÷àñòüþ åãî ñõåìû
êîäèðîâàíèÿ. Â ðåçóëüòàòå âñå õèòðîñòè, ñâÿçàííûå ñ áûñòðûì ïî÷òè ïîëíûì
ïîèñêîì, êîòîðûå ìû òîëüêî ÷òî îáñóæäàëè ñ Ñåðãååì, îêàçûâàþòñÿ ñîâåðøåííî
íåíóæíûìè, áûñòðûé ïîèñê ìîæåò áûòü ïðèìåíèì òîëüêî äëÿ îïöèè áûñòðîãî ñæàòèÿ.
Çäåñü æå ìîæíî, â ïðèíöèïå, ñäåëàòü õåøèðîâàíèå ïî 4-5 áàéòàì ïëþñ åùå îäèí
õåø, íî âðÿä ëè ýòî áóäåò èìåòü ñìûñë - åñëè ãëóáèíà ýòèõ äåðåâüåâ è âïðÿìü
ïðîïîðöèîíàëüíà ëîãàðèôìó ÷èñëà ýëåìåíòîâ â íèõ, òî îâ÷èíêà âûäåëêè íå ñòîèò.
×òî êàñàåòñÿ ïîäðîáíîñòåé ðåàëèçàöèè ñëîâàðÿ è äåëüòà-òàáëèö - òî ýòî
íóæäàåòñÿ â òùàòåëüíîì èññëåäîâàíèè è ìîæåò ñëóæèòü ïðåäìåòîì ðàçãîâîðà çäåñü.
Ìîæåò, Âàäèì, îïóáëèêóåøü ñâîé àëãîðèòì? Ïî ñëîâåñíûì îáúÿñíåíèÿì ÿ íè÷åãî òàê
è íå ïîíÿë.
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
PS: Âàäèì, åñëè òû ìîæåøü âçÿòüñÿ çà âåäåíèå ôàêà - ïåðâàÿ ÷àñòü ìîåãî ïèñüìà
ìîæåò ñîéòè çà åãî êóñî÷åê - ââåäåíèå â LZH-÷àñòü ôàêà, èñòîðè÷åñêèé ýêñêóðñ.
--- GoldED/386 2.50+
* Origin: Ïîñëå ãëóáîêîãî ñíà òðåáóåòñÿ ïðîäîëæèòåëüíûé îòäûõ (2:5093/26)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 08 Jan 99 11:44:47
To : Bulat Ziganshin
Subj : adaptive BWT Re: cabarc
Ïpèâåòñòâóþ, Bulat!
07 Jan 99, Bulat Ziganshin ïèñàë ê Vadim Yoockin:
BZ>>> Òóò âîïðîñàìè ïðåäñòàâëåíû ñèìâîëû òåêóùåãî áëîêà. Âîò ìû èäåì
BZ>>> ïî ýòîìó òåêñòó, íà èçâåñòíûõ ñèìâîëàõ îáó÷àåì íàøó ìîäåëü,
BZ>>> íåèçâåñòíûå äåêîäèðóåì åþ æå. Åñëè áû òàêîå óäàëîñü ñäåëàòü...
BZ>>> Ïðàâäà, ÿñíî, ÷òî çäåñü êàê ðàç è áóäåò ìåãàáàéòíûé êîíòåêñò; íî
BZ>>> çàòî ìû çíàåì, êàêèå ñèìâîëû íàì áëèæå è ìîæåì ó÷èòüñÿ íà íèõ
BZ>>> áîëåå âíèìàòåëüíî, ÷åì íà îñòàëüíûõ - êàêîé-òî âåñîâîé
BZ>>> êîýôôèöèåíò èì äàòü ïîáîëüøå.
VY>> Hå ñîâñåì ïîíÿë òâîé àëãîðèòì: òû ïðåäëàãàåøü â BWT çàãîíÿòü
VY>> âåñü 1Mb, à äîæèìàòü 100k-êóñêàìè èëè æå êàæäûé ïîñëåäóþùèé êóñîê
VY>> îáðàáàòûâàòü ïî âñåé ïðîãðàììå ñ ó÷åòîì ïðåäûäóùèõ?
BZ> Ýòî íå àëãîðèòì, à àáñòðàêòíàÿ ìîäåëü. Ïðî÷òè åùå ðàç ñ ó÷åòîì ýòîãî.
BZ> Åñëè íåïîíÿòíî - ÿ åùå ðàç ïîïðîáóþ. Òî åñòü íàäî êàê-òî äåëàòü áëîêè
BZ> ïîìåíüøå, íî âîâëåêàòü â êîäèðîâàíèå èíôîðìàöèþ èç ïðåäûäóùèõ áëîêîâ.
Ïîçæå, óæå ïîñëå òîãî, êàê ïîñëàë îòâåò, ÿ ïîíÿë òâîþ ìûñëü.
VY>> Âîò ÷òî ìîæíî çàïðîñòî ñäåëàòü, òàê ýòî îáó÷åíèå MTF ïî ïðåäûäóùèì
VY>> áëîêàì.
BZ> Ýòî íåñóùåñòâåííî, åñëè òû èìååøü â âèäó ãëîáàëüíîå îáó÷åíèå. À
BZ> ëîêàëüíîå, ñ ó÷åòîì òîãî, êàêîé êîíòåêñò ñåé÷àñ êîäèðóåòñÿ - ñëîæíî (î÷åíü
BZ> ñëîæíî?) è íåïîíÿòíî, ÷åìó òàì ó÷èòüñÿ - mft'íîé ñòàòèñòèêå? Ìåëêî
BZ> ïëàâàåì. Äðóãîå äåëî - ïðåäñêàçûâàòü ñëåäóþùèé ñèìâîë íà îñíîâàíèè òîãî,
BZ> ÷òî ó íàñ áûëî â ïðåäûäóùèõ ñèìâîëàõ (mtf) è òîãî, ÷òî áûëî â ïðåäûäóùèõ
BZ> áëîêàõ â òîì æå êîíòåêñòå (äâóìåðíûé êîíòåêñò, êàê ïðè ñæàòèè áèòìàïîâ).
ß èìåë ââèäó èìåííî ïîñëåäíåå. Hî è íàó÷èòü MTF îòëè÷àòü ïåðåêëþ÷åíèå
íà äðóãîé êîíòåêñò îò ñëó÷àéíîãî âêðàïëåíèÿ òîæå íåìàëîâàæíî
(è ñåé÷àñ ýòèì ÿ êàê ðàç çàíèìàþñü).
BZ> Ãëàâíîå - âîçìîæíîñòü ðàçëè÷àòü, ÷òî áûëî â ýòîì áëîêå, à ÷òî â
BZ> ïðåäûäóùèõ, è äàâàòü íàïðèìåð ðàçíûé âåñ ýòèì ñòàòèñòèêàì. Åùå èíòåðåñíàÿ
BZ> äåòàëü òàêîãî ïîäõîäà - ìû áóäåì âèäåòü íå òîëüêî ïðîøëîå, íî è áóäóùåå,
BZ> ïðàâäà - èç ïðåäûäóùèõ áëîêîâ :)
BZ> Êñòàòè, ïîëó÷èëàñü õîòü è î÷åíü íåïðîñòàÿ, íî âñå êàêàÿ-òî áîëåå-ìåíåå
BZ> âîçìîæíàÿ ðåàëèçàöèÿ òîãî, î ÷åì ÿ ãîâîðèë â ïðåäûäóùåì ïèñüìå. Çàìå÷àåøü?
Äà, íî òîãäà ìû ïðàêòè÷åñêè ñêàòûâàåìñÿ ê PPM.
Ìîæåò, êîíå÷íî, ýòî è íå òàê ïëîõî è íå ñèëüíî ñêàæåòñÿ íà ñêîðîñòè...
Âñåãî äîáðîãî. Vadim Yoockin
... 2.000.000 Lemmings can't be wrong.
--- Ñòàpûé Äåä ñòîèìîñòüþ 3.00.Alpha4 äîïëàòà â ÑÊÂ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Leonid Broukhis 2:5020/400 08 Jan 99 12:15:26
To : Bulat Ziganshin
Subj : Re: cabarc
From: leob@asylum.mailcom.com (Leonid Broukhis)
Bulat Ziganshin wrote:
> LB> Çíà÷èò, ïðàâèëüíî ÿ ÷óâñòâóþ, ÷òî MTF òîëüêî äëÿ òåêñòîâ õîðîøî
> LB> ïîäõîäèò.
>
> Äà íå mtf, à bwt (åñëè òû åùå íå çàáûë, î ÷åì áûë ðàçãîâîð :) mtf ó íàñ
Ñëåäóåò ÷èòàòü "... ÷òî MTF ïîñëå BWT òîëüêî äëÿ òåêñòîâ...".
>ëîêàëüíûé àëãîðèòì, åìó ðàçìåð áëîêà ïðàêòè÷åñêè äî ëàìïî÷êè. À âîò bwt, êàê è
>õàôìåí, ñòðàäàåò ïðè ñëèøêîì áîëüøîì ðàçìåðå áëîêà íà
>áûñòðîèçìåíÿþùèõñÿ äàííûõ.
>Åìó áû â ñàìûé ðàç áûëî êèë 16 :)
Î òîì è ðå÷ü - êòî áû BWTó îáúÿñíèë, íàñêîëüêî áûñòðî ìåíÿþòñÿ äàííûå,
è ïîäîáðàë ïðàâèëüíûé ðàçìåð áëîêà?
> LB> Ïîñëå BWT íèêàêîãî êîíòåêñòíîãî ìîäåëèðîâàíèÿ íå íóæíî. Âñå, ÷òî áûëî
> LB> â èñòî÷íèêå êîíòåêñòíîãî, BWT óæå âûäîèë.
>
> Ðåçóëüòàò bwt òîæå òðåáóåò êàêîé-òî ìîäåëè. Î÷åíü õîòåëîñü áû íàéòè ÷òî-òî
>åùå ëó÷øåå, ÷åì mtf.
Äà, äëÿ "íå-òåêñòîâ". Hî ÿ ïëîõî ïðåäñòàâëÿþ, ÷òî ìîæåò àäàïòèðîâàòüñÿ
åùå áûñòðåå, ÷åì MTF.
Leo
--- ifmail v.2.14dev2
* Origin: Demos online service (2:5020/400@fidonet)
— RU.COMPRESS
From : Leonid Broukhis 2:5020/400 08 Jan 99 12:15:27
To : Vadim Yoockin
Subj : Re: Bender-Wolf algorithm
From: leob@asylum.mailcom.com (Leonid Broukhis)
Vadim Yoockin wrote:
> LB> PPS. Ãäå-íèáóäü â ëèòåðàòóðå ýòî âñòðå÷àåòñÿ, èëè òîëüêî ìû ñ òîáîé
> LB> ýòî ïðèäóìàëè?
>
>Ìíå íèãäå òàêîãî íå ïîïàäàëîñü (ÿ ïðîáîâàë òàêîé ìåòîä â ~95 ãîäó).
>Hî òû ñàì ãîâîðèë, ÷òî êòî-òî ýòî èçîáðåë â 90-ì.
Êîãäà ÿ îïèñàë ñâîé ñïîñîá â comp.compression â èþëå 1993,
ìíå óêàçàëè íà Bender-Wolf, è îäèí ìîé çíàêîìûé, íûíå ðàáîòàþùèé â
Aladdin Systems (âñå [Un]StuffIt íåñêîëüêèõ ïîñëåäíèõ ëåò - åãî ïîäåëêè)
ïðèñëàë ìíå êñåðîêîïèþ ñòàòüè. Hî òàê êàê ýòî âñå
áûëî çà ñ÷èòàíûå äíè äî îòúåçäà, òî ÿ åå âçÿë ñ ñîáîé, è òàê è íå
÷èòàë. À ïðî÷åë òîëüêî íåäåëþ íàçàä, ðàçáèðàÿ ÿùèêè ïîñëå ïåðååçäà,
è íàïèñàë ñþäà - îêàçûâàåòñÿ, Bender-Wolf ñîâñåì íå òî, ÷òî ÿ îïèñûâàë.
À ñêîðåå âñåãî, îíè ïðîáîâàëè è ýòî, è íè÷åãî õîðîøåãî ó íèõ íå âûøëî,
ïîýòîìó îíè è óïîìèíàòü íå ñòàëè.
Leo
--- ifmail v.2.14dev2
* Origin: Demos online service (2:5020/400@fidonet)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 08 Jan 99 12:16:50
To : Bulat Ziganshin
Subj : Èòàê, êàêèì ÿ âèæó LZH ñëåäóþùåãî ïîêîëåíèÿ
Ïpèâåòñòâóþ, Bulat!
08 Jan 99, Bulat Ziganshin ïèñàë ê All:
BZ> 5. Àðõèâàòîðû ñî ñëîâàðåì > 64k: yac (îí îáîãíàë ñâîå âðåìÿ, åãî ïðîñòî íå
BZ> íà ÷åì áûëî çàïóñêàòü), rar (ÿ åãî ñ÷èòàþ ïåðâûì ïîëíîöåííûì
BZ> ïðåäñòàâèòåëåì ýòîãî ïîêîëåíèÿ) è àðõèâàòîðû, äðóæíî âûñûïàâøèå âåñíîé
BZ> 97-ãî (ace, jar, cabarc), à òàêæå íåìíîãî çàïîçäàâøèé imp è ñîâñåì
BZ> çàïîçäàâøèé arjz. Ýòî ñîâðåìåííîå ïîêîëåíèå lzh-àðõèâàòîðîâ, è ïðè áîëüøîé
BZ> ñõîæåñòè èõ îñíîâû ó âñåõ åñòü ñâîÿ èçþìèíêà:
BZ> MM â rar
BZ> õîðîøåå ñæàòèå exe'øíèêîâ â ace (ÿ òàê è íå ïîíÿë - êàê?)
BZ> ñëîâàðü â jar
BZ> îáùåå óëó÷øåíèå ñæàòèÿ âñåõ òèïîâ äàííûõ, òàáëèöû è E8 â cabarc
BZ> õèòðþùèé àëãîðèòì áûñòðîãî ïîèñêà â imp
À ÷òî, åñòü íîâàÿ èíôîðìàöèÿ (ïîñëå òâîèõ ñòàòåé ïðî matching)?
BZ> E9 â arjz :)
E9 ñëèøêîì ðåäîê â exe32. ÁÎëüøèé âûèãðûø ìíå äàëî êîäèðîâàíèå
êîðîòêèõ óñëîâíûõ ïåðåõîäîâ. È òî òîëüêî ~0.4%. Ïëþñ òðóäíîñòè ïðè èõ
ðàñïîçíàâàíèè.
>> ---------------------------------------------------------------------
BZ> Òåïåðü íàñòàëà, ìíå êàæåòñÿ, ïîðà âûõîäèòü íà àðõèâàòîðû ñëåäóþùåãî
BZ> ïîêîëåíèÿ. Ïîñêîëüêó ðåçåðâû óâåëè÷åíèÿ ðàçìåðà ñëîâàðÿ ìû èñ÷åðïàëè,
BZ> ïðèäåòñÿ èñêàòü èõ â óëó÷øåíèè êîäèðîâàíèÿ. ß ñ÷èòàþ, ÷òî àðõèâàòîð
BZ> ñëåäóþùåãî ïîêîëåíèÿ äîëæåí îñíîâûâàòüñÿ íà êîäèðîâàíèè îò cabarc, íî ñ
BZ> äîáàâëåíèåì ñïåöèôè÷íûõ àëãîðèòìîâ èç äðóãèõ àðõèâàòîðîâ, â ïåðâóþ î÷åðåäü
BZ> ñëîâàðÿ è äåëüòà-òàáëèö. ÌÌ, ïî-ìîåìó, íåîáÿçàòåëüíà - íåñæàòûõ ÌÌ-äàííûõ
BZ> â îêðóæàþùåì íàñ ìèðå ñòàíîâèòñÿ âñå ìåíüøå è ìåíüøå. Õîòÿ, íà ðåñóðñàõ ê
BZ> òîìó æå Äóìó ýòî åùå äàâàëî ðåçóëüòàòû.
Î÷åíü õîðîøî MM ðàñïîçíàåò uharc. Ðåñóðñ îò Quake1 îí óïàêîâàë ëó÷øå âñåõ.
BZ> ß íå çíàþ âñåõ ïîäðîáíîñòåé cabarc (ñàìè áåðèòå åãî è ðàçáèðàéòåñü), íî
BZ> ïîêà ïðåäïîëàãàþ, ÷òî åãî ñõåìà ïîèñêà ÿâëÿåòñÿ ïðèíöèïèàëüíîé ÷àñòüþ åãî
BZ> ñõåìû êîäèðîâàíèÿ. Â ðåçóëüòàòå âñå õèòðîñòè, ñâÿçàííûå ñ áûñòðûì ïî÷òè
BZ> ïîëíûì ïîèñêîì, êîòîðûå ìû òîëüêî ÷òî îáñóæäàëè ñ Ñåðãååì, îêàçûâàþòñÿ
BZ> ñîâåðøåííî íåíóæíûìè, áûñòðûé ïîèñê ìîæåò áûòü ïðèìåíèì òîëüêî äëÿ îïöèè
BZ> áûñòðîãî ñæàòèÿ. Çäåñü æå ìîæíî, â ïðèíöèïå, ñäåëàòü õåøèðîâàíèå ïî 4-5
BZ> áàéòàì ïëþñ åùå îäèí õåø, íî âðÿä ëè ýòî áóäåò èìåòü ñìûñë - åñëè ãëóáèíà
BZ> ýòèõ äåðåâüåâ è âïðÿìü ïðîïîðöèîíàëüíà ëîãàðèôìó ÷èñëà ýëåìåíòîâ â íèõ, òî
BZ> îâ÷èíêà âûäåëêè íå ñòîèò.
À íèêòî, êñòàòè, íå ïðîáîâàë äëÿ ïîèñêà çàèìñòîâàâàòü èç BWT
ïîðàçðÿäíóþ ñîðòèðîâêó? 2 ïðîõîäà è âñå ÷åòâåðêè ó íàñ â êàðìàíå.
BZ> ×òî êàñàåòñÿ ïîäðîáíîñòåé ðåàëèçàöèè ñëîâàðÿ è äåëüòà-òàáëèö - òî ýòî
BZ> íóæäàåòñÿ â òùàòåëüíîì èññëåäîâàíèè è ìîæåò ñëóæèòü ïðåäìåòîì ðàçãîâîðà
BZ> çäåñü. Ìîæåò, Âàäèì, îïóáëèêóåøü ñâîé àëãîðèòì? Ïî ñëîâåñíûì îáúÿñíåíèÿì ÿ
BZ> íè÷åãî òàê è íå ïîíÿë.
Äà âîò, âñå íèêàê íå äîáåðóñü äî óïîðÿäî÷èâàíèÿ èíôîðìàöèè.  ñîñòîÿíèè
öåéòíîòà òîëüêî è õâàòàåò âðåìåíè íà îòðûâî÷íûå ïèñüìà ;(
Äàâàé, ñåé÷àñ ÿ ïîêàæó íà ïðèìåðå, à ïîñëå, êàê áóäåò ãîòîâî,
îïóáëèêóþ âñå, êàê åñòü.
Ïóñòü èäóò ïîäðÿä ñëåäóþùèå dwords:
ABCD0012
ABCD0025
ABCD0040
ABCD0090
ABCD00FE
ABCD0113
ABCD0144
...
Êàê òîëüêî ìû óâèäåëè, ÷òî äåëüòà íå âûëåçàåò çà ïðåäåëû FE, ñêàæåì,
4 ðàçà, äàëåå ïèøåì òîëüêî äåëüòó:
ABCD0012
ABCD0025
ABCD0040
ABCD0090
7E
15
31
...
Âñå õîðîøåå èìååò îáûêíîâåíèå êîí÷àòüñÿ, è òîãäà ìû ïèøåì íà âûõîä FF,
êîòîðàÿ ïðè îáðàòíîì ïðåîáðàçîâàíèè áóäåò íàì ñëóæèòü, êàê EndOfTable.
Äîïîëíèòåëüíî, ìîæíî ïðåäóñìîòðåòü êîäèðîâàíèå ñìåùåíèé äî FFFE,
äàæå èìåòü âîçìîæíîñòü ïåðåêëþ÷åíèÿ ìåæäó dFE <-> dFFFE.
Èíîãäà ýòî òîæå äàåò âûèãðûø, íî ðåäêî.
Ïîêà íå äåëàë, íî ìîæíî ðåàëèçîâàòü êîäèðîâàíèå òàáëèöû ñ ïðîèçâîëüíûì
ñìåùåíèåì.
Áûâàþò òàêæå äåëüòû îòðèöàòåëüíûå, õîòü íå òàê ÷àñòî. Ïîýòîìó
ïîä íèõ ìîæíî òîæå îòâåñòè íåáîëüøîé äèàïàçîí÷èê ñìåùåíèé.
Hàïðèìåð, äëÿ áàéòîâûõ îòëè÷èé, ìîæíî ñäåëàòü äèàïàçîí äåëüò [-4E,B0].
Ïîñêîëüêó ñìåùåíèÿ, êàê ïðàâèëî, èìåþò ñîáñòâåííóþ ñòàòèñòèêó,
íå èìååò ñìûñë èõ ãíàòü â òîò æå äîæèìàëüùèê, ÷òî è îñòàëüíûå
äàííûå. Ïîýòîìó áûñòðåíüêî íàïóñêàåì íà íèõ òîãî æå Ýëèàñà (à ëó÷øå
äàæå êîãî-íèáóäü ñ áîëåå ãëàäêèìè õàðàêòåðèñòèêàìè) è äîïèñûâàåì
êóäà-íèáóäü â õâîñò ïîòîêà. Èëè ñíà÷àëà äîïèñûâàåì, à ïîòîì íàïóñêàåì.
Äëÿ LZ, ìîæåò, ýòî íå ñòîëü àêòóàëüíî - ÿ-òî çàòà÷èâàë ýòî ïîä BWT.
À âî âõîäíîì ïîòîêå îñòàþòñÿ òîëüêî 4 dwords, ïî êîòîðûì ïðè ðàñæàòèè
ìû ñìîæåì âîñïðîèçâåñòè âñþ ïðîöåäóðó.
Ýòî îäèí èç âàðèàíòîâ êîäèðîâàíèÿ òàáëèö.
BZ> PS: Âàäèì, åñëè òû ìîæåøü âçÿòüñÿ çà âåäåíèå ôàêà - ïåðâàÿ ÷àñòü ìîåãî
BZ> ïèñüìà ìîæåò ñîéòè çà åãî êóñî÷åê - ââåäåíèå â LZH-÷àñòü ôàêà,
BZ> èñòîðè÷åñêèé ýêñêóðñ.
 áëèæàéøåå âðåìÿ, óâû. BWT FAQ åùå, ïîæàëóé, îñèëþ.
Âîò îñòàëüíîå - ðàçâå ÷òî òîëüêî êîïèòü è ðåãóëÿðíî ïîñòèòü.
Âñåãî äîáðîãî. Vadim Yoockin
P.S. Ìîãó, êñòàòè, ïîìåùàòü ìîè ðåçóëüòàòû ñðàâíèòåëüíûõ òåñòîâ
êîìïðåññîðîâ. Áëàãî, çà ìåíÿ ýòî äåëàåò ñïåöèàëüíî îáó÷åííàÿ
ïðîãðàììà.
... 2.000.000 Lemmings can't be wrong.
--- Ñòàpûé Äåä ñòîèìîñòüþ 3.00.Alpha4 äîïëàòà â ÑÊÂ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/26 08 Jan 99 14:11:06
To : Igor Pavlov
Subj : Êàê ðóëèòü ïîòîêè ìåæäó êîäåðîì è äîæèìàëêîé ???!!!
* Crossposted in RU.COMPRESS
Hello Igor!
Friday January 08 1999, Igor Pavlov writes to All:
Yes, you did it! Æàëü òîëüêî, àäðåñàò íå óêàçûâàåòñÿ.
>> BZ>> Hó è ñòàíäàðòíûå èäåè -
>> BZ>> ïðåâðàòèòü ïîñëå ïîñòðîåíèÿ õàôìåíîâñêèõ òàáëèö íåâûãîäíûå
>> BZ>> ñòðîêè íàçàä â ñèìâîëû;
IP> Îêàçàëîñü íå ìóñîð, íàäî òîëüêî íå ïîñëå, à íà õîäó.
Håóæåëè âñå òàê ïðîñòî? Ïðàâäà, íèêòî ýòîãî è íå ïðîáîâàë.
IP> Hî è ïîñëå ìîãëî ïîìî÷ü íà íåêîòîðûõ ôàéëàõ,
IP> à ìîæíî åùå ïîïðîáîâàòü äåëàòü äâà ïðîõîäà:
IP> äåðåâî ìîæíî íå ñêàíèðîâàòü çàíîâî - ïðàâäà ïàìÿòè óéäåò óéìà,
Ïîäóìàåøü, åùå â äâà ðàçà áîëüøå :)
IP> íî çàòî åñòü øàíñ îáîéòè cabarc
ß äî ñèõ ïîð ïîëàãàë, ÷òî ó cabarc â íåêîòîðì ñìûñëå èäåàëüíûé àëãîðèòì, à
ýòî âûõîäèò ïðîñòî íàáîð ýâðèñòèê. Êàê îí íèçêî ïàë â ìîèõ ãëàçàõ :)
À ýòè ìåòîäû ìîæíî ïðèìåíèòü â ufa/777?
>> Åäèíñòâåííîå, ÷òî íå ïîçâîëÿåò ìíå èñïîëüçîâàòü ýòèõ ëèäåðîâ -
>> ñëèøêîì áîëüøîå âðåìÿ ðàñïàêîâêè. ß ïàêóþ ñåé÷àñ cabarc'îì, êîòîðûé
>> ïî ðàñõîäó ïàìÿòè íå óñòóïàåò boa/acb/rkive, à ïî âðåìåíè óïàêîâêè
>> íåíàìíîãî áûñòðåå, ñêàæåì, boa (íà cc).
IP> Äëÿ ëþáîãî
IP> àëãîðèòìà ñæàòèÿ íàéäóòñÿ íàáîðû ôàéëîâ íà êîòîðûõ ýòè àëãîðèòìû
IP> íà÷èíàþò ðàáîòàòü íàìíîãî ìåäëåííåå.
IP> Ó ìåíÿ åñòü òàêîé ôàéë (24-bitîâàÿ êàðòèíêà îäíà èç kodak'îâ from
IP> image lossless artest) , íà êîòîðîì ñêîðîñòü (pkzip25 -max), (rar -m5)
IP> è ò.ä. ïàäàåò â 5 - 10 ðàç.
 ïðèíöèïå, ñàìûé ñòðàøíûé çâåðü äëÿ õåø-öåïî÷åê - ýòî ïîõîæèå äàííûå,
êîòîðûå ëîæàòñÿ â îäíó õåø-öåïî÷êó, íî íå æåëàþò ñåðüåçíî óïàêîâûâàòüñÿ.
Èäåàëüíûé âàðèàíò - 3 ïîñòîÿííûõ áàéòà ïëþñ äâà-òðè ñëó÷àéíûõ, ýòî çàìó÷àåò
zip'îâñêèé àëãîðèòì. Hî chain switching ñ ýòèì ëåãêî ñïðàâèòñÿ.
IP> Äëÿ cabarc'à êîëè÷åñòâî òàêèõ "ïëîõèõ"
IP> ôàéëîâ HÀÌHÎÃÎ áîëüøå. È ïîñëåäñòâèÿ íàìíîãî êàòàñòðîôè÷íåå ÷åì ó
IP> ZIP,
IP> äóìàþ ñêîðîñòü ìîæåò óïàñòü â ðàç 100 èëè áîëüøå. È âñå ýòî
IP> óñóãóáëÿåòñÿ ïðè óâåëè÷åíèè ñëîâàðÿ. Ïðèìåð òàêîãî "ïëîõîãî" äëÿ
IP> cabarc'a ôàéëà: kennedy èç Canterbury. Ìàéêðîñîôò ñ ýòèì ñìèðèëîñü,
IP> ò.ê. cabarc ïðåäíàçíà÷åí äëÿ çàäà÷ òèïà: îäèí ðàç çàïàêóþ - ìèëëèîí
IP> ðàç ðàñïàêóþò.
IP> Âîò ðåøèòü ïðîáëåìó òàêèõ "ïëîõèõ" ôàéëîâ áûëî áû õîðîøî
Òû ìîæåøü êàê-òî îáîçíà÷èòü êëàññ òàêèõ ôàéëîâ (êàê ÿ âûøå îáîçíà÷èë êëàññ
ïëîõèõ äëÿ zip)?
"100 ðàç èëè áîëüøå" - ýòî èç-çà òîãî, ÷òî äåðåâî íåîæèäàííî ïðåâðàùàåòñÿ â
ëèíåéíûé ñïèñîê :)
Èòàê, ÷òî ìîæíî ñäåëàòü: 1) ïðåðûâàòü ïåðåñòðîåíèå äåðåâà. Êàê ÿ åùå ëåòîì
ãîâîðèë, â íåáîëüøèõ äîçàõ ýòî ñïîñîáíî óâåëè÷èòü ñêîðîñòü ïðè íåáîëüøîì
ñíèæåíèè ñæàòèÿ, òîëüêî íåïîíÿòíû òî÷íûå êðèòåðèè, à åñëè õîòü íåìíîãî
ïåðåáîðùèòü, òî ñòåïåíü ñæàòèÿ ìîæåò ñóùåñòâåííî óìåíüøèòüñÿ.
2) Èñïîëüçîâàòü âìåñòî õåøèðîâàíèÿ ïî äâóì áàéòàì õåøèðîâàíèå ïî 4-5. Õîòÿ
ýòî íåýôôåêòèâíî ïðè íîðìàëüíîì ïîâåäåíèè àëãîðèòìà, êîãäà ãëóáèíà äåðåâà
ïðîïîðöèîíàëüíà ëîãàðèôìó ÷èñëà ýëåìåíòîâ â íåì, â âûðîæäåííûõ ñëó÷àÿõ ýòîò
ïîäõîä äàñò ñóùåñòâåííîå óëó÷øåíèå ñêîðîñòè. Õîòÿ íåò, íå âñåãäà. Âûèãðûø áóäåò
ïðîïîðöèîíàëåí êîë-âó äåðåâüåâ, ïî êîòîðûì óäàñòñÿ ðàñêèäàòü îðèãèíàëüíóþ
öåïî÷êó.
Ïîêà ÿ âñå ýòî ïèñàë - ïðèøëî ÂÅËÈÊÎÅ ÏÎHÈÌÀHÈÅ :) Èäèîñèíêðàçèÿ cabarc
ïîõîæà è íåïîõîæà íà èäèîñèíêðàçèþ zip. cabarc âñòàâëÿåò íîâûé ýëåìåíò â êîðåíü
äåðåâà, ïåðåñòðàèâàÿ åãî (÷òîáû îíî îñòàëîñü äåðåâîì ïîèñêà) è çàîäíî íàõîäÿ
íàèëó÷øèé ìàò÷. Hàèõóäøàÿ ñèòóàöèÿ - åñëè íîâûé êîðåíü äåðåâà ïîñòîÿííî
îêàçûâàåòñÿ áîëüøå èëè ìåíüøå âñåõ îñòàëüíûõ ýëåìåíòîâ äåðåâà. Ýòî âîçìîæíî â
äâóõ ñëó÷àÿõ - åñëè ó íàñ èäåò ìîíîòîííàÿ ïîñëåäîâàòåëüíîñòü èëè "ðàçâèòèå ïî
ñïèðàëè" - 5,4,6,3,7,2,8,9,0.
Ìíå êàæåòñÿ, ÷òî âòîðîé ñëó÷àé íà ïðàêòèêå âñòðå÷àòüñÿ íå äîëæåí. Ìîæåøü
ïðèäóìàòü êîíòðïðèìåð? ×òî êàñàåòñÿ ïåðâîãî - îí ìîæåò èçðåäêà âñòðå÷àòüñÿ â
ìêëüòèìåäèéíûõ äàííûõ (ãðàäèåíò îò ÷åðíîãî ê ñèíåìó öâåòó), íî ãëàâíûé åãî
àðåàë - òàáëè÷êè. Õîòÿ áû îòñîðòèðîâàííàÿ òàáëèöà ðåëîêàöèé â 16-áèòíîé
ïðîãðàììå. Åñëè ÿ ïðàâ, òî åñòü äâà îñíîâíûõ ñïîñîáà áîðüáû - ñàìîìó íàõîäèòü
òàáëè÷êè è äåëàòü â íèõ âû÷èòàíèÿ (ïîâòîðÿþùèåñÿ äàííûå â îòëè÷èè îò ìîíîòîííûõ
cabarc äîëæåí áûñòðî îáðàáàòûâàòü, â ÷àñòíîñòè ïîòîìó, ÷òî îí íå äåëàåò
ñðàâíåíèÿ êàæäûé ðàç ñ ñàìîãî íà÷àëà) èëè âûøåóïîìèíàâøååñÿ óâåëè÷åíèè ÷èñëà
ñèìâîëîâ â õåøå, ÷òî ïîçâîëèò ðåøèòü ïðîáëåìó, ïî êðàéíåé ìåðå, ñ òàáëè÷êàìè,
èìåþùèìè íåáîëüøóþ êîíñòàíòíóþ ÷àñòü â ñâîèõ ýëåìåíòàõ.
Åñëè äàæå ÿ íåïðàâ ñî âñåì âûøåñêàçàííûì - íàäî îòëîâèòü íà ýòîì êåííåäè
ñàìîå áîëüøîå äåðåâî (äåðåâüÿ) è â íåì ïîèñêàòü âûðîæäåííûå ïîääåðåâüÿ. Âîò. ß
ïîêà íå âèæó èçúÿíîâ â ñâîèõ ðàññóæäåíèÿõ, íî îíè ïîõîæå íå ñîãëàñóþòñÿ ñ òâîèì
çàÿâëåíèåì, ÷òî âûðîæäåííûå ñëó÷àè âñòðå÷àþòñÿ äîâîëüíî ÷àñòî.
IP> À ACT 2.0 ÷åì ïëîõ?
 ÷àñòíîñòè, îòñóòñòâèåì êëàññèôèêàöèè (lzh,bwt...) . Õîòÿ ÿ ïîíèìàþ, åå òîæå
íåïðîñòî ñäåëàòü è íåêîòîðûå àëãîðèòìû ïî òåõíè÷åñêèì õàðàêòåðèñòèêàì ïðîñòî
çàëåçàþò â ÷óæèå êëàññû. Äóðàöêàÿ ðåçóëüòèðóþùàÿ êîëîíêà, õîòÿ åå ìîæíî ïðîñòî
èãíîðèðîâàòü.
>> BZ>>>> Òàê âîò, òàê ñäåëàíî â cabarc è æìåò îí íåïëîõî. ß (è íå
>> BZ>>>> òîëüêî ÿ) ïîëó÷èëè òîëüêî óõóäøåíèå ñòåïåíè ñæàòèÿ ïðè òàêîì
>> BZ>>>> ïîäõîäå.
IP> imho óõóäøåíèÿ áûòü íå äîëæíî.
Óõóäøåíèå áûëî, ïîñêîëüêó óâåëè÷èëèñü çàãîëîâêè áëîêîâ. Hó èëè âî âñÿêîì
ñëó÷àå, ÿ íå ïîëó÷èë ñóùåñòâåííîãî âûèãðûøà - ñåé÷àñ óæå è íå ïîìíþ.
IP> Ïðîñòî ñëîòû âûãîäíåå ïî ñêîðîñòè.
À âûèãðûøà â ñòåïåíè ñæàòèÿ îíè íå äàþò???
>> BZ>> Îïòèìàëüíûå ìàêñ. äèñòàíöèè íèêàê íå ñâÿçàíû ñ âûáîðîì
>> BZ>> õåøèðîâàíèÿ
Âîîáùå-òî ÿ ãîâîðèë ïðî ìàêñ. äèñòàíöèè äëÿ êîðîòêèõ ñòðîê, ýòî äàëåêî íå òî,
÷òî ìàêñ. äèñòàíöèÿ äëÿ âñåõ ñòðîê âîîáùå.
IP> Imho ïîâûøàòü ðàçìåð ñëîâàðÿ äëÿ îáû÷íîãî àëãîðèòìà c lazy matching
IP> ñòîèò äî 1 mb, à äëÿ îïòèìàëüíîãî lzh ãäå-òî äî 2-óõ mb.
×òî æ òû ñäåëàë 4mb? :) Ïî-ìîåìó, ýòî îïðåäåëÿåòñÿ ðàçìåðîì ÎÇÓ è â ìåíüøåé
ñòåïåíè òþíèíãîì àëãîðèòìîâ. Âîò ó ìåíÿ - äî 256 ìá, æàëêî, ÷òî ëè :)
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
* Origin: Ïîñëå ãëóáîêîãî ñíà òðåáóåòñÿ ïðîäîëæèòåëüíûé îòäûõ (2:5093/26)
— RU.COMPRESS
From : Aleksei Pogorily 2:5020/1504 08 Jan 99 18:00:35
To : Serg Tikhomirov
Subj : Àpõèâ ýõè
Ïpèâåò, Serg!
Îäíàæäû (ñpåäà, 06 ÿíâ. 1999, 21:51) Serg Tikhomirov wrote to All:
ST> Åñëè ó êîãî õpàíèòñÿ àpõèâ ýõè â ôîpìàòå SQUISH (èëè MSG), êèíüòå åãî
ST> àòòà÷åì, ïîæàëóéñòà.
Freq
rucompr.rar
Ïpèìåpíî 550 êèëîáàéò. Áàçà ýõè (ñêâèøîâûé ôîpìàò) ñ 15 ìàÿ 1998 ãîäà.
Ñ óâàæåíèåì Aleksei [mailto:pogorily@module.vympel.msk.ru]
Àëåêñåé Ïîãîðèëûé
--- GoldED/W32 2.51.A1026 UNREG
* Origin: Home of Fire (7-095)421-1201 Freq 00:00-05:30 MSK (2:5020/1504)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 08 Jan 99 18:57:24
To : Leonid Broukhis
Subj : Re: cabarc
Ïpèâåòñòâóþ, Leonid!
08 Jan 99, Leonid Broukhis ïèñàë ê Bulat Ziganshin:
>> ëîêàëüíûé àëãîðèòì, åìó ðàçìåð áëîêà ïðàêòè÷åñêè äî ëàìïî÷êè. À âîò bwt,
>> êàê è õàôìåí, ñòðàäàåò ïðè ñëèøêîì áîëüøîì ðàçìåðå áëîêà íà
>> áûñòðîèçìåíÿþùèõñÿ äàííûõ. Åìó áû â ñàìûé ðàç áûëî êèë 16 :)
Ìîè ýêñïåðèìåíòû ïîêàçàëè, ÷òî èíîãäà è 2kb âïîëíå ïðèåìëèìî.
LB> Î òîì è ðå÷ü - êòî áû BWTó îáúÿñíèë, íàñêîëüêî áûñòðî ìåíÿþòñÿ
LB> äàííûå,
LB> è ïîäîáðàë ïðàâèëüíûé ðàçìåð áëîêà?
Ýòî êàê ðàç íå ïðîáëåìà. Ñëîæíîñòü - â ýôôåêòèâíîì êîäèðîâàíèè
ìåíÿþùèõñÿ êîíòåêñòîâ â ïðåäåëàõ îäíîãî áëîêà.
>> LB> Ïîñëå BWT íèêàêîãî êîíòåêñòíîãî ìîäåëèðîâàíèÿ íå íóæíî. Âñå, ÷òî áûëî
>> LB> â èñòî÷íèêå êîíòåêñòíîãî, BWT óæå âûäîèë.
>>
>> Ðåçóëüòàò bwt òîæå òðåáóåò êàêîé-òî ìîäåëè. Î÷åíü õîòåëîñü áû íàéòè
>> ÷òî-òî åùå ëó÷øåå, ÷åì mtf.
LB> Äà, äëÿ "íå-òåêñòîâ". Hî ÿ ïëîõî ïðåäñòàâëÿþ, ÷òî ìîæåò àäàïòèðîâàòüñÿ
LB> åùå áûñòðåå, ÷åì MTF.
Àëüòåðíàòèâà - RLE, êàê â szip (ïîñëå ëþáîãî ñèìâîëà ñðàçó ïèøåòñÿ Run Length).
Âñåãî äîáðîãî. Vadim Yoockin
... 2.000.000 Lemmings can't be wrong.
--- Ñòàpûé Äåä ñòîèìîñòüþ 3.00.Alpha4 äîïëàòà â ÑÊÂ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/26 08 Jan 99 20:56:08
To : Vadim Yoockin
Subj : Èòàê, êàêèì ÿ âèæó LZH ñëåäóþùåãî ïîêîëåíèÿ
*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).
* Crossposted in RU.COMPRESS
Hello Vadim!
Friday January 08 1999, Vadim Yoockin writes to Bulat Ziganshin:
VY> À ÷òî, åñòü íîâàÿ èíôîðìàöèÿ (ïîñëå òâîèõ ñòàòåé ïðî matching)?
Håò, ýòî ñêîðåå äàéäæåñò ëåòíèõ ñòàòåé.
VY> E9 ñëèøêîì ðåäîê â exe32.
=== Cut ===
Original Compressed Ratio DateTime stamp Dict Filename
---------- ---------- ----- -------------- ---- --------
406560 178463 0.439 98-10-13 12:19 448k Far_E8.exe
406560 176643 0.434 98-10-13 12:19 448k Far_E8E9.exe
---------- ---------- ----- -------------- ----
813120 355106 0.437 2 files
=== Cut ===
1%. Ìîæåò, FAR 1.60 è íåòèïè÷åí, ÿ ìàññîâûõ òåñòîâ íå ïðîâîäèë.
VY> ÁÎëüøèé âûèãðûø ìíå äàëî êîäèðîâàíèå
VY> êîðîòêèõ óñëîâíûõ ïåðåõîäîâ. È òî òîëüêî ~0.4%. Ïëþñ òðóäíîñòè ïðè èõ
VY> ðàñïîçíàâàíèè.
Ïðîâåðêà ïðåäûäóùèõ êîìàíä? :)
VY> Î÷åíü õîðîøî MM ðàñïîçíàåò uharc. Ðåñóðñ îò Quake1 îí óïàêîâàë ëó÷øå
VY> âñåõ.
ß ÷òî òàì ðàñïîçíàâàòü, ïî÷òè òàê æå, êàê è òàáëèöû. Hà ìîé âçãëÿä - òîëüêî
ðàçìåðû òàáëè÷åê áîëüøå è ïîðÿäêà â íèõ ìåíüøå.
VY> À íèêòî, êñòàòè, íå ïðîáîâàë äëÿ ïîèñêà çàèìñòîâàâàòü èç BWT
VY> ïîðàçðÿäíóþ ñîðòèðîâêó? 2 ïðîõîäà è âñå ÷åòâåðêè ó íàñ â êàðìàíå.
Hó íàì âåäü íóæíû íå òîëüêî ÷åòâåðêè. Ó PK çàïàòåíòîâàí (íî íå ïðèìåíÿåòñÿ â
pkzip) ñïîñîá ïîèñêà ñòðîê, èñïîëüçóþùèé ñîðòèðîâêó. Ìîæåò, êòî-òî çíàåò åãî
ñîäåðæàíèå??? ß åäèíñòâåííîå, ÷òî ñìîã ñåáå ïðåäñòàâèòü - ñîðòèðóåì âñå ñòðîêè
è äëÿ êàæäîé ïîçèöèè áëàãîäàðÿ ýòîìó ñïèñêó íàõîäèì íàèëó÷øèé ìàò÷. Hî òàì
ìîðîêè... :( Åñëè ñîñåäíèå ñòðîêè âñå îêàæóòñÿ èç áóäóùåãî - ïðèäåòñÿ ìó÷àòüñÿ.
BZ>> ×òî êàñàåòñÿ ïîäðîáíîñòåé ðåàëèçàöèè ñëîâàðÿ è äåëüòà-òàáëèö -
BZ>> òî ýòî íóæäàåòñÿ â òùàòåëüíîì èññëåäîâàíèè è ìîæåò ñëóæèòü
BZ>> ïðåäìåòîì ðàçãîâîðà çäåñü. Ìîæåò, Âàäèì, îïóáëèêóåøü ñâîé
BZ>> àëãîðèòì? Ïî ñëîâåñíûì îáúÿñíåíèÿì ÿ íè÷åãî òàê è íå ïîíÿë.
VY> Äàâàé, ñåé÷àñ ÿ ïîêàæó íà ïðèìåðå, à ïîñëå, êàê áóäåò ãîòîâî,
VY> îïóáëèêóþ âñå, êàê åñòü.
Ïîíÿë, à ìîæåøü íà òîì æå far 1.60 (èëè, ñêàæåì, cabarc) êèíóòü ñïèñîê
íàéäåííûõ òàáëè÷åê? Òèïà òàêîãî:
MM4 count=49 (48) ranges=1 pos=5cd1ch
MM4 count=11 (10) ranges=1 pos=5d7c4h
VY> Ïîñêîëüêó ñìåùåíèÿ, êàê ïðàâèëî, èìåþò ñîáñòâåííóþ ñòàòèñòèêó,
VY> íå èìååò ñìûñë èõ ãíàòü â òîò æå äîæèìàëüùèê, ÷òî è îñòàëüíûå
VY> äàííûå. Ïîýòîìó áûñòðåíüêî íàïóñêàåì íà íèõ òîãî æå Ýëèàñà (à ëó÷øå
VY> äàæå êîãî-íèáóäü ñ áîëåå ãëàäêèìè õàðàêòåðèñòèêàìè) è äîïèñûâàåì
VY> êóäà-íèáóäü â õâîñò ïîòîêà. Èëè ñíà÷àëà äîïèñûâàåì, à ïîòîì íàïóñêàåì.
VY> Äëÿ LZ, ìîæåò, ýòî íå ñòîëü àêòóàëüíî - ÿ-òî çàòà÷èâàë ýòî ïîä BWT.
VY> Ýòî îäèí èç âàðèàíòîâ êîäèðîâàíèÿ òàáëèö.
À âîò ýòîãî ÿ òàê è íå ñäåëàë, îáîøåëñÿ âû÷èòàíèåì "íà ìåñòå". Âîîáùå, åñëè
ýòî îòäåëÿòü îò LZ - íåÿñíî, ïðîèãðàåøü èëè âûèãðàåøü. À åùå ÿ íå ñäåëàë
ñîñòàâíîé ìóëüòèìåäèè, òèïà 4/8.
BZ>> PS: Âàäèì, åñëè òû ìîæåøü âçÿòüñÿ çà âåäåíèå ôàêà - ïåðâàÿ ÷àñòü
BZ>> ìîåãî ïèñüìà ìîæåò ñîéòè çà åãî êóñî÷åê - ââåäåíèå â LZH-÷àñòü
BZ>> ôàêà, èñòîðè÷åñêèé ýêñêóðñ.
VY> Â áëèæàéøåå âðåìÿ, óâû. BWT FAQ åùå, ïîæàëóé, îñèëþ.
VY> Âîò îñòàëüíîå - ðàçâå ÷òî òîëüêî êîïèòü è ðåãóëÿðíî ïîñòèòü.
Hå, ÿ èìåþ â âèäó òîëüêî âåäåíèå ôàêà. lzh-÷àñòü ÿ îáåùàë ñäåëàòü :)
VY> P.S. Ìîãó, êñòàòè, ïîìåùàòü ìîè ðåçóëüòàòû ñðàâíèòåëüíûõ òåñòîâ
VY> êîìïðåññîðîâ. Áëàãî, çà ìåíÿ ýòî äåëàåò ñïåöèàëüíî îáó÷åííàÿ
VY> ïðîãðàììà.
Äà, äàâàé îáÿçàòåëüíî.
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
* Origin: Ïîñëå ãëóáîêîãî ñíà òðåáóåòñÿ ïðîäîëæèòåëüíûé îòäûõ (2:5093/26)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/26 08 Jan 99 22:25:16
To : Dmitry Shkarin
Subj : cabarc
* Crossposted in RU.COMPRESS
Hello Dmitry!
Friday January 08 1999, Dmitry Shkarin writes to All:
DS> À ãäå íàéòè îïèñàíèå CABARC(LZX)?
ftp://fort.tatarstan.ru/pub/zbr/arc/cab-sdk.exe
DS> È ÷òî âû âñå âöåïèëèñü â LZ77?
À ÷òî â ýòîé ýõå åùå äåëàòü? :)
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
* Origin: Ïîñëå ãëóáîêîãî ñíà òðåáóåòñÿ ïðîäîëæèòåëüíûé îòäûõ (2:5093/26)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/26 09 Jan 99 01:04:52
To : Vadim Yoockin
Subj : adaptive BWT Re: cabarc
*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).
* Crossposted in RU.COMPRESS
Hello Vadim!
Friday January 08 1999, Vadim Yoockin writes to Bulat Ziganshin:
VY> ß èìåë ââèäó èìåííî ïîñëåäíåå. Hî è íàó÷èòü MTF îòëè÷àòü ïåðåêëþ÷åíèå
VY> íà äðóãîé êîíòåêñò îò ñëó÷àéíîãî âêðàïëåíèÿ òîæå íåìàëîâàæíî
VY> (è ñåé÷àñ ýòèì ÿ êàê ðàç çàíèìàþñü).
Óõîæó, óõîæó. Ñ BWT âû áåç ìåíÿ ëó÷øå ðàçáåðåòåñü, ÿ ëó÷øå ñîñðåäîòî÷óñü íà
lzh. Èòàê, ÷òî ìû ìîæåì îáñóäèòü:
1) íåäîñòàòêè cabarc :)
2) áûñòðûé ïîèñê äëÿ ñëàáîãî ñæàòèÿ
3) ñëîâàðíîå ñæàòèå
4) ïîèñê è êîäèðîâàíèå òàáëèö
5) ìîæåò, ó êîãî-òî åùå åñòü èäåè ïî óëó÷øåíèþ ñæàòèÿ?
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
* Origin: Ïîñëå ãëóáîêîãî ñíà òðåáóåòñÿ ïðîäîëæèòåëüíûé îòäûõ (2:5093/26)
— RU.COMPRESS
From : Igor Pavlov 2:5020/400 09 Jan 99 01:42:09
To : All
Subj : Re: Êàê ðóëèòü ïîòîêè ìåæäó êîäåðîì è äîæèìàëêîé ???!!!
From: "Igor Pavlov" <igor@znanie.ufanet.ru>
Bulat Ziganshin wrote in message <915811625@f26.n5093.z2.ftn>...
>* Crossposted in RU.COMPRESS
> ß äî ñèõ ïîð ïîëàãàë, ÷òî ó cabarc â íåêîòîðì ñìûñëå èäåàëüíûé àëãîðèòì, à
>ýòî âûõîäèò ïðîñòî íàáîð ýâðèñòèê. Êàê îí íèçêî ïàë â ìîèõ ãëàçàõ :)
imho êàê ðàç îí áëèçîê ê èäåàëüíîìó
> À ýòè ìåòîäû ìîæíî ïðèìåíèòü â ufa/777?
Òðóäíî, íî ìîæíî imho.
> IP> Äëÿ ëþáîãî
> IP> àëãîðèòìà ñæàòèÿ íàéäóòñÿ íàáîðû ôàéëîâ íà êîòîðûõ ýòè àëãîðèòìû
> IP> íà÷èíàþò ðàáîòàòü íàìíîãî ìåäëåííåå.
> IP> Ó ìåíÿ åñòü òàêîé ôàéë (24-bitîâàÿ êàðòèíêà îäíà èç kodak'îâ from
> IP> image lossless artest) , íà êîòîðîì ñêîðîñòü (pkzip25 -max), (rar -m5)
> IP> è ò.ä. ïàäàåò â 5 - 10 ðàç.
>
>  ïðèíöèïå, ñàìûé ñòðàøíûé çâåðü äëÿ õåø-öåïî÷åê - ýòî ïîõîæèå äàííûå,
>êîòîðûå ëîæàòñÿ â îäíó õåø-öåïî÷êó, íî íå æåëàþò ñåðüåçíî óïàêîâûâàòüñÿ.
>Èäåàëüíûé âàðèàíò - 3 ïîñòîÿííûõ áàéòà ïëþñ äâà-òðè ñëó÷àéíûõ, ýòî çàìó÷àåò
>zip'îâñêèé àëãîðèòì. Hî chain switching ñ ýòèì ëåãêî ñïðàâèòñÿ.
À ÷òî ýòî òàêîå?
Êñòàòè, ïîïðîáóé íàòðàâè ýòîò àëãîðèòì íà îáû÷íûé hash lists search:
ñîáèðàé ïî äîðîãå âñå õîðîøèå ñîâïàäåíèÿ.
À âîîáùå õîòåëîñü áû óçíàòü, ìîæåò ëè ýòîò àëãîðèòì áûòü óæå
çàïàòåíòîâàí, è îòêóäà îí ó íèõ âçÿëñÿ.
ß ÷èòàë, ÷òî áûëà ïðîãà äëÿ Amiga èñïîëüçóþùàÿ LZX àëãîðèòì,
è ms êóïèëà åãî ó àâòîðà(îâ). Hî íåÿñíî êàêèå èç òðåõ ÷àñòåé:
1) äâîè÷íûé ïîèñê
2) êîäèðîâàíèå ïî ñëîòàì
3) ïîèñê îïòèìàëüíîé ïîñëåäîâàòåëüíîñòè êîäîâ
îíà ñîäåðæàëà.
Ìîæåò áûòü êòî-íèáóäü çíàåò ÷òî-òî ïî ýòîìó ïîâîäó?
> Òû ìîæåøü êàê-òî îáîçíà÷èòü êëàññ òàêèõ ôàéëîâ (êàê ÿ âûøå îáîçíà÷èë êëàññ
>ïëîõèõ äëÿ zip)?
ß çíàþ íåñêîëüêî ïðèìåðîâ.
êóñîê èç pdf ôàéëà:
0000596023 00000 n
0000596084 00000 n
0000596145 00000 n
0000596206 00000 n
0000596267 00000 n
0000596329 00000 n
0000596390 00000 n
0000596451 00000 n
....
Èñëåäîâàòü ïîêà íå ñòàë.
> "100 ðàç èëè áîëüøå" - ýòî èç-çà òîãî, ÷òî äåðåâî íåîæèäàííî ïðåâðàùàåòñÿ â
>ëèíåéíûé ñïèñîê :)
Hàâåðíîå
> Èòàê, ÷òî ìîæíî ñäåëàòü: 1) ïðåðûâàòü ïåðåñòðîåíèå äåðåâà. Êàê ÿ åùå ëåòîì
>ãîâîðèë, â íåáîëüøèõ äîçàõ ýòî ñïîñîáíî óâåëè÷èòü ñêîðîñòü ïðè íåáîëüøîì
>ñíèæåíèè ñæàòèÿ, òîëüêî íåïîíÿòíû òî÷íûå êðèòåðèè, à åñëè õîòü íåìíîãî
>ïåðåáîðùèòü, òî ñòåïåíü ñæàòèÿ ìîæåò ñóùåñòâåííî óìåíüøèòüñÿ.
ß ñìóòíî ïðåäñòàâëÿþ, êàê ïðåðâàòü.
> 2) Èñïîëüçîâàòü âìåñòî õåøèðîâàíèÿ ïî äâóì áàéòàì õåøèðîâàíèå ïî 4-5. Õîòÿ
>ýòî íåýôôåêòèâíî ïðè íîðìàëüíîì ïîâåäåíèè àëãîðèòìà, êîãäà ãëóáèíà äåðåâà
>ïðîïîðöèîíàëüíà ëîãàðèôìó ÷èñëà ýëåìåíòîâ â íåì, â âûðîæäåííûõ ñëó÷àÿõ ýòîò
>ïîäõîä äàñò ñóùåñòâåííîå óëó÷øåíèå ñêîðîñòè. Õîòÿ íåò, íå âñåãäà. Âûèãðûø
>áóäåò ïðîïîðöèîíàëåí êîë-âó äåðåâüåâ, ïî êîòîðûì óäàñòñÿ ðàñêèäàòü
>îðèãèíàëüíóþ öåïî÷êó.
Imho ìîæåò íå ïîìî÷ü (èëè ïîìî÷ü, íî íå âî âñåõ ñëó÷àÿõ), ÿ ïðîâåðþ.
Åùå îòêóäà-òî íàäî áóäåò áðàòü êîðîòêèå ñîâïàäåíèÿ, íî ýòî ïîêà íå âàæíî.
>
> Ïîêà ÿ âñå ýòî ïèñàë - ïðèøëî ÂÅËÈÊÎÅ ÏÎHÈÌÀHÈÅ :) Èäèîñèíêðàçèÿ cabarc
>ïîõîæà è íåïîõîæà íà èäèîñèíêðàçèþ zip. cabarc âñòàâëÿåò íîâûé ýëåìåíò â
>êîðåíü äåðåâà, ïåðåñòðàèâàÿ åãî (÷òîáû îíî îñòàëîñü äåðåâîì ïîèñêà) è çàîäíî
>íàõîäÿ íàèëó÷øèé ìàò÷. Hàèõóäøàÿ ñèòóàöèÿ - åñëè íîâûé êîðåíü äåðåâà ïîñòîÿííî
>îêàçûâàåòñÿ áîëüøå èëè ìåíüøå âñåõ îñòàëüíûõ ýëåìåíòîâ äåðåâà. Ýòî âîçìîæíî â
>äâóõ ñëó÷àÿõ - åñëè ó íàñ èäåò ìîíîòîííàÿ ïîñëåäîâàòåëüíîñòü èëè "ðàçâèòèå ïî
>ñïèðàëè" - 5,4,6,3,7,2,8,9,0.
ïðîñòî ìîíîòîííàÿ ïîñëåäîâàòåëüíîñòü íå ñòðàøíà, ò.ê áóäåò
âñåãî îäíà èòåðàöèÿ.
Hàâåðíîå â ñëó÷àå ñ òåì pdf êàê ðàç êàêàÿ-òî ñïèðàëü,
íî ÿ âñå ðàâíî ïëîõî ïîíèìàþ, ÷òî òàì ïðîèñõîäèò.
>> Ìíå êàæåòñÿ, ÷òî âòîðîé ñëó÷àé íà ïðàêòèêå âñòðå÷àòüñÿ íå äîëæåí. Ìîæåøü
>ïðèäóìàòü êîíòðïðèìåð? ×òî êàñàåòñÿ ïåðâîãî - îí ìîæåò èçðåäêà âñòðå÷àòüñÿ â
>ìêëüòèìåäèéíûõ äàííûõ (ãðàäèåíò îò ÷åðíîãî ê ñèíåìó öâåòó)
Håò, íà êàðòèíêàõ àíîìàëèé, êàæåòñÿ, íå íàáëþäàåòñÿ.
Imho nàì âñå âîçìîæíûå çàêîíîìåðíîñòè ñëèøêîì êîðîòêèå, à äàííûå âñå ðàâíî
ñèëüíî ñëó÷àéíûå, ÷òî î÷åíü íà ðóêó.
> íî ãëàâíûé åãî àðåàë
>- òàáëè÷êè. Õîòÿ áû îòñîðòèðîâàííàÿ òàáëèöà ðåëîêàöèé â 16-áèòíîé ïðîãðàììå.
>Åñëè ÿ ïðàâ, òî åñòü äâà îñíîâíûõ ñïîñîáà áîðüáû - ñàìîìó íàõîäèòü òàáëè÷êè è
>äåëàòü â íèõ âû÷èòàíèÿ (ïîâòîðÿþùèåñÿ äàííûå â îòëè÷èè îò ìîíîòîííûõ cabarc
>äîëæåí áûñòðî îáðàáàòûâàòü, â ÷àñòíîñòè ïîòîìó, ÷òî îí íå äåëàåò ñðàâíåíèÿ
>êàæäûé ðàç ñ ñàìîãî íà÷àëà)
Òû ïðî ÷òî? êàêèå ñðàâíåíèÿ îí íå äåëàåò?
>èëè âûøåóïîìèíàâøååñÿ óâåëè÷åíèè ÷èñëà ñèìâîëîâ â
>õåøå, ÷òî ïîçâîëèò ðåøèòü ïðîáëåìó, ïî êðàéíåé ìåðå, ñ òàáëè÷êàìè, èìåþùèìè
>íåáîëüøóþ êîíñòàíòíóþ ÷àñòü â ñâîèõ ýëåìåíòàõ.
Ýòî ïðîâåðèì
> Åñëè äàæå ÿ íåïðàâ ñî âñåì âûøåñêàçàííûì - íàäî îòëîâèòü íà ýòîì êåííåäè
>ñàìîå áîëüøîå äåðåâî (äåðåâüÿ) è â íåì ïîèñêàòü âûðîæäåííûå ïîääåðåâüÿ. Âîò. ß
>ïîêà íå âèæó èçúÿíîâ â ñâîèõ ðàññóæäåíèÿõ, íî îíè ïîõîæå íå ñîãëàñóþòñÿ ñ
>òâîèì çàÿâëåíèåì, ÷òî âûðîæäåííûå ñëó÷àè âñòðå÷àþòñÿ äîâîëüíî ÷àñòî.
×àñòî. Ïðîñòî èíîãäà "ïëîõèå" êóñêè ìàëåíüêèå è îí èõ ïðîñêàêèâàåò áûñòðî.
> IP> À ACT 2.0 ÷åì ïëîõ?
>
>  ÷àñòíîñòè, îòñóòñòâèåì êëàññèôèêàöèè (lzh,bwt...) . Õîòÿ ÿ ïîíèìàþ, åå
> òîæå íåïðîñòî ñäåëàòü è íåêîòîðûå àëãîðèòìû ïî òåõíè÷åñêèì õàðàêòåðèñòèêàì
> ïðîñòî çàëåçàþò â ÷óæèå êëàññû. Äóðàöêàÿ ðåçóëüòèðóþùàÿ êîëîíêà, õîòÿ åå
> ìîæíî ïðîñòî èãíîðèðîâàòü.
Hî ëó÷øå, ÷åì âîîáùå íåïîíÿòíàÿ êàêàÿ, êàê ðàíüøå.
Ìîæíî áûëî áû åùå ñäåëàòü òàêóþ êîëîíêó :
Min(Compressed_Size / Modem_Speed + Extract_time).
> >> BZ>>>> Òàê âîò, òàê ñäåëàíî â cabarc è æìåò îí íåïëîõî. ß (è íå
> >> BZ>>>> òîëüêî ÿ) ïîëó÷èëè òîëüêî óõóäøåíèå ñòåïåíè ñæàòèÿ ïðè òàêîì
> >> BZ>>>> ïîäõîäå.
> IP> imho óõóäøåíèÿ áûòü íå äîëæíî.
>
> Óõóäøåíèå áûëî, ïîñêîëüêó óâåëè÷èëèñü çàãîëîâêè áëîêîâ. Hó èëè âî âñÿêîì
>ñëó÷àå, ÿ íå ïîëó÷èë ñóùåñòâåííîãî âûèãðûøà - ñåé÷àñ óæå è íå ïîìíþ.
>
> IP> Ïðîñòî ñëîòû âûãîäíåå ïî ñêîðîñòè.
>
> À âûèãðûøà â ñòåïåíè ñæàòèÿ îíè íå äàþò???
Hå äàþò, èëè ïî÷òè íå äàþò.
> IP> Imho ïîâûøàòü ðàçìåð ñëîâàðÿ äëÿ îáû÷íîãî àëãîðèòìà c lazy matching
> IP> ñòîèò äî 1 mb, à äëÿ îïòèìàëüíîãî lzh ãäå-òî äî 2-óõ mb.
>
> ×òî æ òû ñäåëàë 4mb? :)
Hàäî æå áûëî ÷åì-òî îòëè÷àòüñÿ :)
íî 2 - ñàìîå îïòèìàëüíîå.
>Ïî-ìîåìó, ýòî îïðåäåëÿåòñÿ ðàçìåðîì ÎÇÓ è â ìåíüøåé
>ñòåïåíè òþíèíãîì àëãîðèòìîâ. Âîò ó ìåíÿ - äî 256 ìá, æàëêî, ÷òî ëè :)
256 - ýòî ïðàâèëüíî.
- ---
Èãîðü
--- ifmail v.2.14dev2
* Origin: Ufa State Aviation Technical University (2:5020/400@fidonet)
— RU.COMPRESS
From : Igor Pavlov 2:5020/400 09 Jan 99 01:44:10
To : All
Subj : Re: Èòàê, êàêèì ÿ âèæó LZH ñëåäóþùåãî ïîêîëåíèÿ
From: "Igor Pavlov" <igor@znanie.ufanet.ru>
Vadim Yoockin wrote in message <915800159@p50.f1042.n5020.z2.fidonet.ftn>...
>Î÷åíü õîðîøî MM ðàñïîçíàåò uharc. Ðåñóðñ îò Quake1 îí óïàêîâàë ëó÷øå âñåõ.
Åùå îí õîðîøî ïàêóåò rdr èç "Drawing Hand"
>À íèêòî, êñòàòè, íå ïðîáîâàë äëÿ ïîèñêà çàèìñòîâàâàòü èç BWT
>ïîðàçðÿäíóþ ñîðòèðîâêó? 2 ïðîõîäà è âñå ÷åòâåðêè ó íàñ â êàðìàíå.
À ìîæíî âñå íàîáîðîò: binary tree from cabarc to bwt :)
- ---
Igor
--- ifmail v.2.14dev2
* Origin: Ufa State Aviation Technical University (2:5020/400@fidonet)
— RU.COMPRESS
From : Alex Sverdlin 2:5020/1469.117 09 Jan 99 05:36:00
To : Bulat Ziganshin
Subj : ZIP
Hi, Bulat!
On 07 ÿíâàðÿ 1999 (â ÷åòâåðã), Bulat Ziganshin writes to Alex Sverdlin the
following:
BZ> Èñõîäíèêè pkzip íåäîñòóïíû, äà è íå èñïîëüçóþòñÿ â rar. Èñõîäíèêè
BZ> zip/unzip:
BZ> === Cut ===
BZ> ftp.elf.stuba.sk/pub/pc/pack/zip23g.zip
BZ> ftp.elf.stuba.sk/pub/pc/pack/unzip540.zip
BZ> === Cut ===
BZ> Îïèñàíèå ôîðìàòà ñæàòûõ äàííûõ (äåéñòâèòåëüíî íà ïàëüöàõ):
BZ> === Cut ===
BZ> ftp.elf.stuba.sk/pub/pc/pack/appnote.zip
BZ> === Cut ===
À íå ïîäêèíåò ëè êòî, ïëç, à òî èíåòà íåòó :(
[team tic tac]
--- Genius/[G0ALz] http://www.chat.ru/~idccwe
* Origin: Be yourself, no matter what they say (2:5020/1469.117)
— RU.COMPRESS
From : Leonid Broukhis 2:5020/400 09 Jan 99 09:05:16
To : Vadim Yoockin
Subj : Re: cabarc
From: leob@asylum.mailcom.com (Leonid Broukhis)
Vadim Yoockin wrote:
> LB> Î òîì è ðå÷ü - êòî áû BWTó îáúÿñíèë, íàñêîëüêî áûñòðî ìåíÿþòñÿ
> LB> äàííûå,
> LB> è ïîäîáðàë ïðàâèëüíûé ðàçìåð áëîêà?
>
>Ýòî êàê ðàç íå ïðîáëåìà. Ñëîæíîñòü - â ýôôåêòèâíîì êîäèðîâàíèè
>ìåíÿþùèõñÿ êîíòåêñòîâ â ïðåäåëàõ îäíîãî áëîêà.
 òàêîì ñëó÷àå åñëè â ïðåäåëàõ îäíîãî áëîêà êîíòåêñòû ìåíÿþòñÿ - ýòî
çíà÷èò, ÷òî áëîê ñëèøêîì áîëüøîé.
Leo
> LB> Äà, äëÿ "íå-òåêñòîâ". Hî ÿ ïëîõî ïðåäñòàâëÿþ, ÷òî ìîæåò àäàïòèðîâàòüñÿ
> LB> åùå áûñòðåå, ÷åì MTF.
>
>Àëüòåðíàòèâà - RLE, êàê â szip (ïîñëå ëþáîãî ñèìâîëà ñðàçó ïèøåòñÿ Run
>Length).
À ïî÷åìó íå ïîñëå äâóõ?
Leo
--- ifmail v.2.14dev2
* Origin: Demos online service (2:5020/400@fidonet)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 09 Jan 99 10:10:40
To : Leonid Broukhis
Subj : Re: cabarc
Ïpèâåòñòâóþ, Leonid!
Leonid Broukhis ïèñàë ê Vadim Yoockin:
> LB> Î òîì è ðå÷ü - êòî áû BWTó îáúÿñíèë, íàñêîëüêî áûñòðî ìåíÿþòñÿ
> LB> äàííûå, è ïîäîáðàë ïðàâèëüíûé ðàçìåð áëîêà?
>
>Ýòî êàê ðàç íå ïðîáëåìà. Ñëîæíîñòü - â ýôôåêòèâíîì êîäèðîâàíèè
>ìåíÿþùèõñÿ êîíòåêñòîâ â ïðåäåëàõ îäíîãî áëîêà.
LB>  òàêîì ñëó÷àå åñëè â ïðåäåëàõ îäíîãî áëîêà êîíòåêñòû ìåíÿþòñÿ - ýòî
LB> çíà÷èò, ÷òî áëîê ñëèøêîì áîëüøîé.
ß èìåë ââèäó "ïåðåìåæàþùèõñÿ êîíòåêñòîâ".
> LB> Äà, äëÿ "íå-òåêñòîâ". Hî ÿ ïëîõî ïðåäñòàâëÿþ, ÷òî ìîæåò
> LB> àäàïòèðîâàòüñÿ åùå áûñòðåå, ÷åì MTF.
>
>Àëüòåðíàòèâà - RLE, êàê â szip (ïîñëå ëþáîãî ñèìâîëà ñðàçó ïèøåòñÿ Run
>Length).
LB> À ïî÷åìó íå ïîñëå äâóõ?
Âîçìîæíî, ïîòîìó ÷òî çàêîäèðîâàòü ëèøíþþ length äåøåâëå, ÷åì
âòîðîé ñèìâîë. ß åùå òàêîå êîäèðîâàíèå íå ïðîáîâàë.
Âñåãî äîáðîãî. Vadim Yoockin
... 2.000.000 Lemmings can't be wrong.
--- Ñòàpûé Äåä ñòîèìîñòüþ 3.00.Alpha4 äîïëàòà â ÑÊÂ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 09 Jan 99 10:45:24
To : Bulat Ziganshin
Subj : Èòàê, êàêèì ÿ âèæó LZH ñëåäóþùåãî ïîêîëåíèÿ
Ïpèâåòñòâóþ, Bulat!
Bulat Ziganshin ïèñàë ê Vadim Yoockin:
VY> E9 ñëèøêîì ðåäîê â exe32.
BZ> 1%. Ìîæåò, FAR 1.60 è íåòèïè÷åí, ÿ ìàññîâûõ òåñòîâ íå ïðîâîäèë.
Òàì åñòü èíòåðåñíûå êóñî÷êè, êàê ðàç ïîä E9 (íàïðèìåð, ïî àäðåñó 0xF12).
VY> Î÷åíü õîðîøî MM ðàñïîçíàåò uharc. Ðåñóðñ îò Quake1 îí óïàêîâàë ëó÷øå
VY> âñåõ.
BZ> ß ÷òî òàì ðàñïîçíàâàòü, ïî÷òè òàê æå, êàê è òàáëèöû. Hà ìîé âçãëÿä -
BZ> òîëüêî ðàçìåðû òàáëè÷åê áîëüøå è ïîðÿäêà â íèõ ìåíüøå.
Ó RAR'a òàê íå ïîëó÷àåòñÿ (óâû, òî÷íîñòü 2kb + îøèáêè).
VY> À íèêòî, êñòàòè, íå ïðîáîâàë äëÿ ïîèñêà çàèìñòîâàâàòü èç BWT
VY> ïîðàçðÿäíóþ ñîðòèðîâêó? 2 ïðîõîäà è âñå ÷åòâåðêè ó íàñ â êàðìàíå.
BZ> Hó íàì âåäü íóæíû íå òîëüêî ÷åòâåðêè. Ó PK çàïàòåíòîâàí (íî íå
BZ> ïðèìåíÿåòñÿ â pkzip) ñïîñîá ïîèñêà ñòðîê, èñïîëüçóþùèé ñîðòèðîâêó.
BZ> Ìîæåò, êòî-òî çíàåò åãî ñîäåðæàíèå??? ß åäèíñòâåííîå, ÷òî ñìîã ñåáå
BZ> ïðåäñòàâèòü - ñîðòèðóåì âñå ñòðîêè è äëÿ êàæäîé ïîçèöèè áëàãîäàðÿ
BZ> ýòîìó ñïèñêó íàõîäèì íàèëó÷øèé ìàò÷. Hî òàì ìîðîêè... :( Åñëè ñîñåäíèå
BZ> ñòðîêè âñå îêàæóòñÿ èç áóäóùåãî - ïðèäåòñÿ ìó÷àòüñÿ.
Åñëè èñïîëüçîâàòü qsort3, òî ìîæíî íà êàæäîì óãëóáëåíèè ôîðìèðîâàòü
ññûëêè. Âïðî÷åì, ýòî åùå íåèçâåäàííàÿ îáëàñòü è, ì.á. áóäóò ñâîè
ïðîáëåìû.
BZ>> ×òî êàñàåòñÿ ïîäðîáíîñòåé ðåàëèçàöèè ñëîâàðÿ è äåëüòà-òàáëèö -
BZ>> òî ýòî íóæäàåòñÿ â òùàòåëüíîì èññëåäîâàíèè è ìîæåò ñëóæèòü
BZ>> ïðåäìåòîì ðàçãîâîðà çäåñü. Ìîæåò, Âàäèì, îïóáëèêóåøü ñâîé
BZ>> àëãîðèòì? Ïî ñëîâåñíûì îáúÿñíåíèÿì ÿ íè÷åãî òàê è íå ïîíÿë.
VY> Äàâàé, ñåé÷àñ ÿ ïîêàæó íà ïðèìåðå, à ïîñëå, êàê áóäåò ãîòîâî,
VY> îïóáëèêóþ âñå, êàê åñòü.
BZ> Ïîíÿë, à ìîæåøü íà òîì æå far 1.60 (èëè, ñêàæåì, cabarc) êèíóòü
BZ> ñïèñîê íàéäåííûõ òàáëè÷åê? Òèïà òàêîãî:
Áîþñü, íåïðîñòî áóäåò îòäåëèòü òàáëè÷êè îò âñåãî îñòàëüíîãî.
Hî ÷óòü ïîçæå ïîñòàðàþñü (íàïîìíè, åñëè çàáóäó).
VY> Ïîñêîëüêó ñìåùåíèÿ, êàê ïðàâèëî, èìåþò ñîáñòâåííóþ ñòàòèñòèêó,
VY> íå èìååò ñìûñë èõ ãíàòü â òîò æå äîæèìàëüùèê, ÷òî è îñòàëüíûå
VY> äàííûå. Ïîýòîìó áûñòðåíüêî íàïóñêàåì íà íèõ òîãî æå Ýëèàñà (à ëó÷øå
VY> äàæå êîãî-íèáóäü ñ áîëåå ãëàäêèìè õàðàêòåðèñòèêàìè) è äîïèñûâàåì
VY> êóäà-íèáóäü â õâîñò ïîòîêà. Èëè ñíà÷àëà äîïèñûâàåì, à ïîòîì
VY> íàïóñêàåì.
VY> Äëÿ LZ, ìîæåò, ýòî íå ñòîëü àêòóàëüíî - ÿ-òî çàòà÷èâàë ýòî ïîä BWT.
VY> Ýòî îäèí èç âàðèàíòîâ êîäèðîâàíèÿ òàáëèö.
BZ> À âîò ýòîãî ÿ òàê è íå ñäåëàë, îáîøåëñÿ âû÷èòàíèåì "íà ìåñòå".
BZ> Âîîáùå, åñëè ýòî îòäåëÿòü îò LZ - íåÿñíî, ïðîèãðàåøü èëè âûèãðàåøü. À
BZ> åùå ÿ íå ñäåëàë ñîñòàâíîé ìóëüòèìåäèè, òèïà 4/8.
À ÷òî òàêîå ñîñòàâíàÿ ìóëüòèìåäèÿ?
Âñåãî äîáðîãî. Vadim Yoockin
... 2.000.000 Lemmings can't be wrong.
--- Ñòàpûé Äåä ñòîèìîñòüþ 3.00.Alpha4 äîïëàòà â ÑÊÂ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 09 Jan 99 11:01:25
To : Igor Pavlov
Subj : Èòàê, êàêèì ÿ âèæó LZH ñëåäóþùåãî ïîêîëåíèÿ
Ïpèâåòñòâóþ, Igor!
Igor Pavlov wrote:
>À íèêòî, êñòàòè, íå ïðîáîâàë äëÿ ïîèñêà çàèìñòîâàâàòü èç BWT
>ïîðàçðÿäíóþ ñîðòèðîâêó? 2 ïðîõîäà è âñå ÷åòâåðêè ó íàñ â êàðìàíå.
IP> À ìîæíî âñå íàîáîðîò: binary tree from cabarc to bwt :)
Ñìàéëèê-òî ÿ çàìåòèë ;)
 BWT ïðàêòè÷åñêè âñå èñïîëüçóþò radix + qsort3 è, íåêîòîðûå, Øåëëà.
Âñåãî äîáðîãî. Vadim Yoockin
... 2.000.000 Lemmings can't be wrong.
--- Ñòàpûé Äåä ñòîèìîñòüþ 3.00.Alpha4 äîïëàòà â ÑÊÂ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/26 09 Jan 99 12:28:32
To : Igor Pavlov
Subj : Êàê ðóëèòü ïîòîêè ìåæäó êîäåðîì è äîæèìàëêîé ???!!!
* Crossposted in RU.COMPRESS
Hello Igor!
Saturday January 09 1999, Igor Pavlov writes to All:
>>  ïðèíöèïå, ñàìûé ñòðàøíûé çâåðü äëÿ õåø-öåïî÷åê - ýòî ïîõîæèå
>> äàííûå, êîòîðûå ëîæàòñÿ â îäíó õåø-öåïî÷êó, íî íå æåëàþò ñåðüåçíî
>> óïàêîâûâàòüñÿ. Èäåàëüíûé âàðèàíò - 3 ïîñòîÿííûõ áàéòà ïëþñ äâà-òðè
>> ñëó÷àéíûõ, ýòî çàìó÷àåò zip'îâñêèé àëãîðèòì. Hî chain switching ñ
>> ýòèì ëåãêî ñïðàâèòñÿ.
IP> À ÷òî ýòî òàêîå?
ß íåñêîëüêî äíåé íàçàä êèíóë ïîäáîðêó èþíüñêèõ ïèñåì (ïîñìîòðè ìîå ïèñüìî
Äèìå Áåëèêîâó îò 4-ãî ÿíâàðÿ). Òàì åñòü è ïðî ýòî:
=== Cut ===
ARJZ. Àëãîðèòì zip'îâñêèé ñ îäíîé-åäèíñòâåííîé îïòèìèçàöèåé, êîòîðàÿ ïðè
"-md1m -jm" ðàçà â ïîëòîðà óñêîðÿåò ðàáîòó è äàæå ÷óòü óëó÷øàåò ñæàòèå.
Èñïîëüçóåòñÿ òîò ôàêò, ÷òî åñëè ìû íàøëè, ñêàæåì, ñîâïàäåíèå íà 7 ïîçèöèé, à
õåøèðîâàíèå ó íàñ èäåò ïî òðåì ñèìâîëàì, òî äàëüíåéøèé ïîèñê ìû ìîæåì âåñòè ïî
ëþáîé èç 5 (==7-3+1) õåø-öåïî÷åê. Ïðè÷åì åñëè îäíà èç ýòèõ öåïî÷åê óêàçûâàåò íà
0 èëè íà ñòðîêó çà ïðåäåëàìè ãðàíèö ïîèñêà (limit), òî è äâèãàÿñü ïî äðóãèì
õåø-öåïî÷êàì, ìû ñòðîêè äëèííåå ýòèõ 7 ñèìâîëîâ íå íàéäåì.  ðåçóëüòàòå ìû
ïîëó÷àåì íèæå-çàþêîæåííóþ ïðîöåäóðó, ñ êëþ÷åâûì ôðàãìåíòîì:
offset = 0;
uint p = previous(cur_match);
for( int i=1; i<=len-MIN_MATCH; i++ ) {
if( previous(cur_match+i) < p ) {
offset = i;
p = previous(cur_match+i);
}
}
=== Cut ===
IP> Êñòàòè, ïîïðîáóé íàòðàâè ýòîò àëãîðèòì íà îáû÷íûé hash lists search:
IP> ñîáèðàé ïî äîðîãå âñå õîðîøèå ñîâïàäåíèÿ.
?
IP> À âîîáùå õîòåëîñü áû óçíàòü, ìîæåò ëè ýòîò àëãîðèòì áûòü óæå
IP> çàïàòåíòîâàí, è îòêóäà îí ó íèõ âçÿëñÿ.
IP> ß ÷èòàë, ÷òî áûëà ïðîãà äëÿ Amiga èñïîëüçóþùàÿ LZX àëãîðèòì,
IP> è ms êóïèëà åãî ó àâòîðà(îâ).
IP> Ìîæåò áûòü êòî-íèáóäü çíàåò ÷òî-òî ïî ýòîìó ïîâîäó?
Áëèí, íè÷åãî ñàìè ñäåëàòü íå ìîãóò ;)
>> Òû ìîæåøü êàê-òî îáîçíà÷èòü êëàññ òàêèõ ôàéëîâ (êàê ÿ âûøå
>> îáîçíà÷èë êëàññ ïëîõèõ äëÿ zip)?
IP> ß çíàþ íåñêîëüêî ïðèìåðîâ.
IP> êóñîê èç pdf ôàéëà:
IP> 0000596023 00000 n
IP> 0000596084 00000 n
IP> 0000596145 00000 n
IP> 0000596206 00000 n
IP> 0000596267 00000 n
IP> 0000596329 00000 n
IP> 0000596390 00000 n
IP> 0000596451 00000 n
IP> ....
ß áûë ïðàâ. Òèïè÷íåéøàÿ òàáëè÷êà. Âîò òåáå ïðîñòåíüêèé ðåöåïò - ëîâèøü åå ïî
rep_both èëè áëèçêèì ñòðîêàì (ñ ìàëåíüêèì ñìåùåíèåì è äëèíîé ìåíüøå ñìåùåíèÿ).
Âûñëåæèâàåøü åå îêîí÷àíèå ïî çàâåðøåíèþ ó÷àñòêà ìîíîòîííîñòè (ëó÷øå áóäåò, åñëè
òû áóäåøü èãíîðèðîâàòü íåáîëüøèå îòêëîíåíèÿ, òèïà îäèí ðàç íå â òó ñòîðîíó,
çàòî ïîòîì ïÿòü ìîíîòîííûõ èçìåíåíèé - êñòàòè, íàïðàâëåíèå ìîíîòîííîñòè â òàêèõ
òàáëè÷êàõ ìîæåò è ìåíÿòüñÿ). Êîäèðîâàíèå - âûâîäèøü â âûõîäíîé ïîòîê ïðèçíàê
"íà÷àëî òàáëè÷êè" (äàé åìó îòäåëüíûé êîä â õàôìåíîâñêîé òàáëèöå), ïàðàìåòðû
ýòîé òàáëè÷êè (ðàçìåð ýëåìåíòà, êàê ìèíèìóì), äàëåå âû÷òåííûå äàííûå, çàòåì
"êîíåö òàáëè÷êè". btw, ÿ ëè÷íî íå èñïîëüçóþ "êîíåö òàáëè÷êè", à êîäèðóþ ïîñëå
"íà÷àëà òàáëè÷êè" ÷èñëî ýëåìåíòîâ â íåé.
Âû÷òåííûå äàííûå ëó÷øå ïèñàòü íå íàïðÿìóþ (ñ êó÷åé íóëåâûõ áàéòîâ), à ïî
áàçèñó ïåðâîãî ýëåìåíòà (òîãäà ëèøíèå íóëåâûå áàéòû ïîÿâëÿòüñÿ íå áóäóò).
Åùå íåïëîõî áû äåëàòü èçáèðàòåëüíîå âû÷èòàíèå (åñëè ó íàñ åñòü äâà áàéòà
ïîñòîÿííûõ, äâà ìîíîòîííûõ, äâà ñî ñëó÷àéíûìè äàííûìè); èíîãäà xor ëó÷øå
âû÷èòàíèÿ (íà geo, êñòàòè). È òàáëè÷êè ñ êîðîòêèìè ýëåìåíòàìè íàäî ëîâèòü
ïî-äðóãîìó - ïðîñòî ñðàâíåíèÿìè, ïðè íûíåøíèõ òîðìîçíûõ àëãîðèòìàõ ýòî íå òàê
óæ ñòðàøíî.
Ïîæàëóé ýòî âñå, ÷òî íóæíî äëÿ ôàêà. Êîãäà ïðèêàæåøü æäàòü íîâóþ âåðñèþ bix?
:)
>> "100 ðàç èëè áîëüøå" - ýòî èç-çà òîãî, ÷òî äåðåâî íåîæèäàííî
>> ïðåâðàùàåòñÿ â ëèíåéíûé ñïèñîê :)
IP> Hàâåðíîå
Òî÷íî, òî÷íî.
>> Èòàê, ÷òî ìîæíî ñäåëàòü: 1) ïðåðûâàòü ïåðåñòðîåíèå äåðåâà. Êàê ÿ
>> åùå ëåòîì ãîâîðèë, â íåáîëüøèõ äîçàõ ýòî ñïîñîáíî óâåëè÷èòü ñêîðîñòü
>> ïðè íåáîëüøîì ñíèæåíèè ñæàòèÿ, òîëüêî íåïîíÿòíû òî÷íûå êðèòåðèè, à
>> åñëè õîòü íåìíîãî ïåðåáîðùèòü, òî ñòåïåíü ñæàòèÿ ìîæåò ñóùåñòâåííî
>> óìåíüøèòüñÿ.
IP> ß ñìóòíî ïðåäñòàâëÿþ, êàê ïðåðâàòü.
Áåðåøü è ïðåðûâàåøü :) Ïðîñòî è íàãëî. Êàê òîëüêî òåáå íàäîåëî "ñïóñêàòüñÿ
ïî äåðåâó, ïåðåñòðàèâàÿ åãî íà õîäó" - â ñìûñëå, êàê ñ÷åò÷èê ïåðåâàëèë çà íåêóþ
îòìåòêó. Ìîæåò ñäåëàòü è òîíüøå - ïðè ñïóñêå âëåâî ïðîâåðÿòü, áûëà ëè ññûëêà
âïðàâî, è ïîñëå íåñêîëüêòõ äåñÿòêîâ ñïóñêîâ ïî âûðîæäåííîìó ñåãìåíòó äåðåâà
ïîñûëàòü âñåõ íàôèã. Håäîñòàòîê - çàìåäëÿåòñÿ ðàáîòà íà âñåõ ôàéëàõ.
>> 2) Èñïîëüçîâàòü âìåñòî õåøèðîâàíèÿ ïî äâóì áàéòàì õåøèðîâàíèå ïî
>> 4-5. Õîòÿ ýòî íåýôôåêòèâíî ïðè íîðìàëüíîì ïîâåäåíèè àëãîðèòìà, êîãäà
>> ãëóáèíà äåðåâà ïðîïîðöèîíàëüíà ëîãàðèôìó ÷èñëà ýëåìåíòîâ â íåì, â
>> âûðîæäåííûõ ñëó÷àÿõ ýòîò ïîäõîä äàñò ñóùåñòâåííîå óëó÷øåíèå
>> ñêîðîñòè. Õîòÿ íåò, íå âñåãäà. Âûèãðûø áóäåò ïðîïîðöèîíàëåí êîë-âó
>> äåðåâüåâ, ïî êîòîðûì óäàñòñÿ ðàñêèäàòü îðèãèíàëüíóþ öåïî÷êó.
IP> Imho ìîæåò íå ïîìî÷ü (èëè ïîìî÷ü, íî íå âî âñåõ ñëó÷àÿõ), ÿ ïðîâåðþ.
Òîëüêî â òåõ, êîãäà ýòè òàáëè÷êè èìåþò ìàëåíüêèå ýëåìåíòû (ñêàæåì, äâà áàéòà
ïîñòîÿííûõ ïëþñ äâà ìîíîòîííî èçìåíÿùèõñÿ). ß óæå ãîâîðèë - ñêàæåì, íà
ðåëîêàöèÿõ. Hà ýòîì pdf'å íå ïîìîæåò.
IP> Åùå îòêóäà-òî íàäî áóäåò áðàòü êîðîòêèå ñîâïàäåíèÿ, íî ýòî ïîêà íå
IP> âàæíî.
Åùå îäèí õåø (ëèíåéíûé èëè äåðåâî). Èëè ñîðòèðîâêà èç BZIP.
>>
>> Ïîêà ÿ âñå ýòî ïèñàë - ïðèøëî ÂÅËÈÊÎÅ ÏÎHÈÌÀHÈÅ :) Èäèîñèíêðàçèÿ
>> cabarc ïîõîæà è íåïîõîæà íà èäèîñèíêðàçèþ zip. cabarc âñòàâëÿåò
>> íîâûé ýëåìåíò â êîðåíü äåðåâà, ïåðåñòðàèâàÿ åãî (÷òîáû îíî îñòàëîñü
>> äåðåâîì ïîèñêà) è çàîäíî íàõîäÿ íàèëó÷øèé ìàò÷. Hàèõóäøàÿ ñèòóàöèÿ -
>> åñëè íîâûé êîðåíü äåðåâà ïîñòîÿííî îêàçûâàåòñÿ áîëüøå èëè ìåíüøå
>> âñåõ îñòàëüíûõ ýëåìåíòîâ äåðåâà. Ýòî âîçìîæíî â äâóõ ñëó÷àÿõ - åñëè
>> ó íàñ èäåò ìîíîòîííàÿ ïîñëåäîâàòåëüíîñòü èëè "ðàçâèòèå ïî ñïèðàëè" -
>> 5,4,6,3,7,2,8,9,0.
IP> ïðîñòî ìîíîòîííàÿ ïîñëåäîâàòåëüíîñòü íå ñòðàøíà, ò.ê áóäåò
IP> âñåãî îäíà èòåðàöèÿ.
Håò. Âîò ìîå îïèñàíèå:
=== Cut ===
 cabarc âìåñòî îáû÷íûõ õåø-öåïî÷åê èñïîëüçóþòñÿ õåø-äåðåâüÿ. Òî åñòü,
âî-ïåðâûõ âñå ñòðîêè ðàçáèâàþòñÿ íà êëàññû ïî ïåðâûì äâóì áóêâàì. Âî-âòîðûõ,
âíóòðè êàæäîãî êëàññà ñòðîêè âñòàâëÿþòñÿ â áèíàðíîå äåðåâî, â êîòîðîì óçëû
ññûëàþòñÿ òîëüêî íà ïðåäøåñòâóþùèå èì ñòðîêè. Êàê îáû÷íî, ññûëêà íàëåâî
óêàçûâàåò íà ëåêñèêîãðàôè÷åñêè ìåíüøóþ ñòðîêó, íàïðàâî - íà áîëüøóþ. Áîëåå
òîãî, êàê è ïîëàãàåòñÿ â äåðåâå ïîèñêà, âñå ìåíüøèå ñòðîêè íàõîäÿòñÿ â ëåâîì
ïîääåðåâå, áîëüøèå - â ïðàâîì.
Âíîâü âñòàâëÿåìûé óçåë (ïóñòü ýòî 'abc') ñòàíîâèòñÿ êîðíåì äåðåâà. Ïîääåðåâüÿ
ïðåæíåãî êîðíÿ (ïóñòü ýòî 'abd') ïåðåñòðàèâàþòñÿ òàê, ÷òîáû â ëåâîì îñòàëîñü
òîëüêî òî, ÷òî ìåíüøå íîâîãî êîðíÿ, â ïðàâîì - òî, ÷òî áîëüøå.
=== Cut ===
Òåïåðü ñàì ñìîòðè - îäíîâðåìåííîå âûïîëíåíèå òðåáîâàíèé "äåðåâî ïîèñêà" è
"ññûëêè òîëüêî íàçàä" æåñòêî ôèêñèðóåò äåðåâî, êîòîðîå ìîæíî ïîñòðîèòü ïî
îïðåäåëåííûì âõîäíûì äàííûì; áàëàíñèðîâêà äåðåâà ñ öåëüþ óìåíüøèòü åãî ãëóáèíó
çäåñü íåâîçìîæíà. Hà ìîíîòîííîé ïîñë-òè 0001,0002,...,0099 ìû ïîëó÷èì âîò òàêîå
äåðåâî:
0099
.....
0002
/
0001
Âûðîæäåííîå äåðåâî, êàê âèäèøü. È òàêèå äåðåâüÿ áóäóò ïîëó÷àòüñÿ âñÿêèé ðàç
íà ìîíîòîííî èçìåíÿùèõñÿ äàííûõ. Áîëåå òîãî, äàæå åñëè ýòè äàííûå ïåðåìåæàþòñÿ
äðóãèìè (0001,..0050, 00ab, 00cd..., 0051, ..0099), äàæå "÷åðåçïîëîñèöåé"
(00001, 001ab, ...0099, 001xy); äàæå â ýòèõ ñëó÷àÿõ íàøè ìîíîòîííûå äàííûå
áóäóò îáðàçîâûâàòü ñâîè àâòîíîìèè - âûðîæäåííûå ïîääåðåâüÿ â îáû÷íîì äåðåâå.
Ïðè÷åì ýòà âûðîæäåííîñòü áóäåò ñêàçûâàòüñÿ òîëüêî ïðè ïîèñêå òàêèõ æå äàííûõ -
ïðè ïîèñêå îáû÷íûõ ñòðîê, íå çàìå÷åííûõ â òàáëè÷êàõ, ìû ïðîñòî íå áóäåì
ïîïàäàòü â âûðîæäåííóþ ÷àñòü äåðåâà.
IP> Hàâåðíîå â ñëó÷àå ñ òåì pdf êàê ðàç êàêàÿ-òî ñïèðàëü,
IP> íî ÿ âñå ðàâíî ïëîõî ïîíèìàþ, ÷òî òàì ïðîèñõîäèò.
Èìåííî ìîíîòîííàÿ ïîñëåäîâàòåëüíîñòü, ïîñìîòðè ñàì, ðàçâå åå ñëîæíî çàìåòèòü?
>> íî ãëàâíûé åãî àðåàë
>> - òàáëè÷êè. Õîòÿ áû îòñîðòèðîâàííàÿ òàáëèöà ðåëîêàöèé â 16-áèòíîé
>> ïðîãðàììå. Åñëè ÿ ïðàâ, òî åñòü äâà îñíîâíûõ ñïîñîáà áîðüáû - ñàìîìó
>> íàõîäèòü òàáëè÷êè è äåëàòü â íèõ âû÷èòàíèÿ (ïîâòîðÿþùèåñÿ äàííûå â
>> îòëè÷èè îò ìîíîòîííûõ cabarc äîëæåí áûñòðî îáðàáàòûâàòü, â ÷àñòíîñòè
>> ïîòîìó, ÷òî îí íå äåëàåò ñðàâíåíèÿ êàæäûé ðàç ñ ñàìîãî íà÷àëà)
IP> Òû ïðî ÷òî? êàêèå ñðàâíåíèÿ îí íå äåëàåò?
=== Cut ===
Äà, âîò åùå âñïîìíèë - òàì åñòü òàêàÿ îïòèìèçàöèÿ: Ïîñëå òîãî, êàê ìû íàøëè
ñòðî÷êó áîëüøå íàøåé, íî ñîâïàäàþùóþ ñ íåé â N ñèìâîëàõ, è ñòðî÷êó ìåíüøå, íî
ñîâïàäàþùóþ â M ñèìâîëàõ, âñå îñòàëüíûå ñòðîêè, íà êîòîðûå ìû áóäåì âûõîäèòü,
áóäóò ñîâïàäàòü ñ íàøåé â min(N,M) ñèìâîëàõ, ñîîòâåòñòâåííî ýòè ñèìâîëû è íå
ïðîâåðÿþòñÿ.
=== Cut ===
>> Åñëè äàæå ÿ íåïðàâ ñî âñåì âûøåñêàçàííûì - íàäî îòëîâèòü íà ýòîì
>> êåííåäè ñàìîå áîëüøîå äåðåâî (äåðåâüÿ) è â íåì ïîèñêàòü âûðîæäåííûå
>> ïîääåðåâüÿ. Âîò. ß ïîêà íå âèæó èçúÿíîâ â ñâîèõ ðàññóæäåíèÿõ, íî îíè
>> ïîõîæå íå ñîãëàñóþòñÿ ñ òâîèì çàÿâëåíèåì, ÷òî âûðîæäåííûå ñëó÷àè
>> âñòðå÷àþòñÿ äîâîëüíî ÷àñòî.
IP> ×àñòî. Ïðîñòî èíîãäà "ïëîõèå" êóñêè ìàëåíüêèå è îí èõ ïðîñêàêèâàåò
IP> áûñòðî.
Ñìîòðÿ ãäå; â áèíàðíèêàõ - äà, ÁÄ - êàê ïîâåçåò, âñÿêèõ ìóëüòèìåäèéíûõ
ðåñóðñàõ - îáû÷íî äà. À âîò â òåêñòàõ îáû÷íî íåò. Õîòÿ ÿ òóò æå ïðåäñòàâèë ñåáå
òàáëè÷êó îïåðàöèé ïðîöåññîðà, ñ äâîè÷íûìè êîäàìè, óïîðÿäî÷åííóþ ïî èõ
âîçðàñòàíèþ :)
Åñëè ýòè ïëîõèå êóñêè äîñòàòî÷íî ìàëû, òî îíè áûñòðî ïðîìåëüêíóò è íà
äàëüíåéøåé ðàáîòå ïðàêòè÷åñêè íå áóäóò ñêàçûâàòüñÿ. Åñëè æå îíè ñêîëüêî-íèáóäü
âåëèêè - èõ äîëæåí ïîéìàòü òàáëè÷íûé àëãîðèòì.
>> IP> À ACT 2.0 ÷åì ïëîõ?
>> òåõíè÷åñêèì õàðàêòåðèñòèêàì ïðîñòî çàëåçàþò â ÷óæèå êëàññû. Äóðàöêàÿ
>> ðåçóëüòèðóþùàÿ êîëîíêà, õîòÿ åå ìîæíî ïðîñòî èãíîðèðîâàòü.
IP> Hî ëó÷øå, ÷åì âîîáùå íåïîíÿòíàÿ êàêàÿ, êàê ðàíüøå.
IP> Ìîæíî áûëî áû åùå ñäåëàòü òàêóþ êîëîíêó :
IP> Min(Compressed_Size / Modem_Speed + Extract_time).
ß è çäåñü âñòàâëþ ñâîþ ïàðó ñëîâ. Âî-ïåðâûõ, ïðè÷åì çäåñü ìîäåìû? Ýòî ïðîñòî
ïîïóëèçì. Ñêëàäûâàåì óòÿò ñ öûïëÿòàìè, èñïîëüçóÿ ïåðâûé ïîïàâøèéñÿ êîýôô.
ïåðåñ÷åòà. Òîëüêî óìíîæåíèå! :) Âî-âòîðûõ, ÿñíî, ÷òî óìíîæàòü ðàçìåð ñæàòîãî
ôàéëà íà ñêîðîñòü ðàáîòû òîæå íåõîðîøî - óâåëè÷åíèå ñæàòèÿ íà 10% è óñêîðåíèå
ðàáîòû íà 10% ñîâñåì íå ðàâíîöåííûå âåùè. Òàêèì îáðàçîì, è çäåñü íóæíû
êîýôôèöèåíòû, ïðåäñòàâëåííûå â âèäå ñòåïåíåé. Ðàçóìååòñÿ, îíè â íåêîòîðîé
ñòåïåíè ïðîèçâîëüíû - îäíèì íóæíà ñêîðîñòü, äðóãèì ñæàòèå; â îäíèõ ñëó÷àÿõ
íóæíî áûñòðî ñæàòü, â äðóãèõ - áûñòðî ðàñïàêîâàòü. Îäíàêî, ÿ ñ÷èòàþ, âñå òåñòû
"øèðîêîãî ïðèìåíåíèÿ" äîëæíû èñïîëüçîâàòü èìåííî ìóëüòèïëèêàòèâíûå èíòåãðàëüíûå
ôîðìóëû - ñ òåìè èëè èíûìè êîýôôèöèåíòàìè.
×òî êàñàåòñÿ ñàìèõ êîýôô-â, òî èìõî common sense áóäåò òàêîé - äàòü
îäèíàêîâûå âåñà óïàêîâêå è ðàñïàêîâêå, òî åñòü ñ÷èòàòü, ÷òî óïàêîâêà â 1.5 ðàçà
äîëüøå êîìïåíñèðóåòñÿ ðàñïàêîâêîé â 1.5 ðàçà áûñòðåå. ×òî êàñàåòñÿ ñòåïåíè
ñæàòèÿ, òî ÿ áû ïîñ÷èòàë íîðìàëüíîé ðàñïëàòîé çà 10%-íîå åå óâåëè÷åíèå
5-êðàòíîå çàìåäëåíèå óïàêîâêè _è_ ðàñïàêîâêè. ln(5*5)/ln(1.1)=33. Òàê ÷òî
ôîðìóëà ñ÷àñòüÿ âûãëÿäèò òàê: size*pow(add*extract,1/33). Ïðè ýòîì ðåçóëüòàò
ìîæíî èçìåðÿòü â ïîïóãàÿõ, òî åñòü íîðìàëèçîâàòü ïî îòíîøåíèþ ê êàêîìó-íèáóäü
zip.
>> ïîìíþ. Ïðîñòî ñëîòû âûãîäíåå ïî ñêîðîñòè. À âûèãðûøà â ñòåïåíè
>> ñæàòèÿ îíè íå äàþò???
IP> Hå äàþò, èëè ïî÷òè íå äàþò.
Hó íàñ÷åò âûèãðûøà â ñêîðîñòè ìîæíî è ñàìèì äîãàäàòüñÿ. ß êîãäà-òî âûíàøèâàë
ñîâñåì áåçóìíóþ èäåþ ñäåëàòü òî æå ñàìîå, íî òîëüêî íà óðîâíå ðàñïàêîâùèêà.
Òîãäà îñòàëñÿ òîëüêî îäèí âîïðîñ - à ýòîìó àëãîðèòìó îïòèìàëüíûõ ìàò÷åé âàæíî
òî, ÷òî ìû íàøëè ñîâïàäåíèÿ äëÿ âñåõ ïîçèöèé â îêíå? Èëè, êàê è â îáû÷íîì lazy
matching, íóæíû òîëüêî ìàò÷è ïîñëå âûâåäåííûõ ñòðîê +/- 1? Òî åñòü, äðóãèìè
ñëîâàìè, âîçìîæíî ëè ñäåëàòü optimal matching áåç õåø-äåðåâüåâ?
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
PS: Âìåñòî ïîñëåñëîâèÿ - íå õî÷åøü ñäåëàòü äëèííûå ñòðîêè? :) È ñëîâàðü çàîäíî
åùå? :))
--- GoldED/386 2.50+
* Origin: Ïîñëå ãëóáîêîãî ñíà òðåáóåòñÿ ïðîäîëæèòåëüíûé îòäûõ (2:5093/26)
— RU.COMPRESS
From : Kris Kasperski 2:5063/61.8 09 Jan 99 14:02:18
To : Sergey Radkevitch
Subj : Àðõèâàòîð
* Replying to a msg in NETMAIL (NetMail)
Hello Sergey.
Ïÿòíèöà, 08 ßíâàðÿ 1999 19:38, Sergey Radkevitch wrote to Kris Kasperski:
SR>>> Åñòü ëè àëãîpèòì âûäåëåíèÿ ñëîâ èç òåêñòà è àâòîìàòè÷åñêîãî
SR>>> ñîñòàâëåíèÿ ñëîâàpÿ ?
KK>> À ÷òî ñëîæíî? Ìîãó êèíóòü íà C++ ïîä win32. Ñëîâà âûäåëèòü
KK>> íåñëîæíî. Äàëüøå - áèíàpíîå äåpåâî (äàæå íåñáàëàíñèpîâàííîå) è
KK>> âïåpåä! Ìîæíî êîäèpîâàòü öåëûå ôpàçû èëè óñòîé÷èâûå
KK>> ñëîâîñî÷èòàíèÿ îäíèì èíäåêñîì.
SR> Êèíü, ïîæàëóéñòà, åñëè íå òðóäíî.
Âîò ïpîñòåéøåå áèíàpíîå äåpåâî äëÿ pàáîòû ñî ñëîâàìè. Äëÿ ñëîâàpåé,
ñîñòîÿùèõ èç ïàpû ñîòåí ñëîâ ïîäõîäèò ïî ñêîpîñòè âïîëíå, äàëüøå áóäåò
òîpìîçèòü.
#include "stdafx.h"
#include "Arx.h"
#include "BinTree.h"
CBinTree::CBinTree()
{
WArray.InsertAt(0,(WORD) 0);
WArray.InsertAt(1,(WORD) 0);
WArray.InsertAt(2,(WORD) 0);
SArray.InsertAt(0,"KPNC");
FArray.Add(1);
}
CBinTree::~CBinTree()
{
}
int CBinTree::CmpStr(CString s1, CString s2)
{
int L1,L2;
L1=s1.GetLength();
L2=s2.GetLength();
if (L2<L1) return -1;
if (L2>L1) return 1;
if (s1==s2) return 0;
for (int a=0;a<L2;a++)
{
if (s2[a]<s1[a]) return -1;
if (s2[a]>s1[a]) return 1;
}
return 0xFF;
}
unsigned long int CBinTree::Add(CString s1)
{
// Ñíà÷àëà áåpåì êîpíåâîé ýëåìåíò
CString tm;
BOOL res;
unsigned long int branch=0,tb,tmp,zzz;
while (true)
{
tm=SArray[WArray[branch]];
res=CmpStr(tm,s1);
if (res==0)
{
FArray[WArray[branch]]+=1;
return 0;
}
if (res==-1) tmp=WArray[branch+=1];
if (res==1) tmp=WArray[branch+=2];
if (tmp==0)
{
tb=SArray.Add(s1);
FArray.Add(1);
zzz=WArray.Add((WORD) tb);
WArray[branch]=zzz;
WArray.Add((WORD) 0);
WArray.Add((WORD) 0);
return tb;
}
else
branch=tmp;
}
return true;
}
void CBinTree::Test()
{
// Add("....");
// Add("....");
// Add("....");
// Add("....");
// Add("....");
// Add("....");
}
BOOL CBinTree::StoreTree(CString FileName)
{
if (FileName=="") FileName="WordList.dat";
CString s0,s1,s2,s3,s4,v;
v="Been Tree untitled version";
s0=".BEGIN TREE!";
s1=".Section String:";
s2=".Section Branch Date:";
s3=".END of BinTree";
s4=".Section FREQ Count :";
CFile MyFile;
if (MyFile.Open(FileName,CFile::modeCreate|CFile::modeWrite)==0) return
false;
CArchive ar(&MyFile,CArchive::store);
ar<<s0;
ar<<v;
ar<<s1;
SArray.Serialize(ar);
ar<<s2;
WArray.Serialize(ar);
ar<<s4;
FArray.Serialize(ar);
ar<<s3;
return true;
}
unsigned long int CBinTree::Found(CString s1)
{
CString tm;
BOOL res;
unsigned long int branch=0,tmp;
while (true)
{
tm=SArray[WArray[branch]];
res=CmpStr(tm,s1);
if (res==0) return WArray[branch];
if (res==-1) tmp=WArray[branch+=1];
if (res==1) tmp=WArray[branch+=2];
if (tmp==0) return 0;
branch=tmp;
}
return true;
}
//CString CBinTree::GetString(int idx)
//{
// if ((idx-1)>SArray.GetSize()) return "<user string>";
// return SArray[idx];
//}
BOOL CBinTree::LoadTree(CString FileName)
{
if (FileName=="") FileName="WordList.dat";
CString s1;
CFile MyFile;
if (MyFile.Open("WordList.dat",CFile::modeRead)==0) return false;
CArchive ar(&MyFile,CArchive::load);
ar>>s1;
ar>>s1;
ar>>s1;
SArray.Serialize(ar);
ar>>s1;
WArray.Serialize(ar);
ar>>s1;
FArray.Serialize(ar);
ar>>s1;
return true;
}
unsigned long int CBinTree::GetSize()
{
return SArray.GetSize();
}
CString CBinTree::operator [ ](unsigned long int idx)
{
if ((idx-1)>SArray.GetSize()) return "<user string>";
return SArray[idx];
}
int CBinTree::FRQ(long int idx)
{
return FArray[idx];
}
SB>>> À ó÷èòûâàþòñÿ ëè ïàäåæè ?
KK>> Êàê Áîã íà äóøó ïîëîæèò :) Âûáèpàåòñÿ îïòèìàëüíûé âàpèàíò ïî
KK>> ñîâïàäåíèþ ôpàãìåíòîâ. Hî äëÿ ìîåé çàäà÷è äàííûé àëãîpèòì ïîäîøåë
KK>> èäåàëüíî.
SR> Âîò, à ìîæåøü îïèñàòü àëãîðèòì âûáîðà ýòîãî ñàìîãî îïòèìàëüíîãî
SR> âàðèàíòà? Õîðîøî áû âìåñòå ñ ïðîãðàììîé.
Òàì âîêpóã ýòîãî àëãîpèòìà â èñõîäíèêå ìíîãî ÷åãî ëèøíåãî íàêpó÷åíî, íî
ñìûñë òàêîé, ÷òî êîãäà â ñëîâàpå åñòü òèïà:
abcde, hjlde òî ïpè äîáàâëåíèè adcxy ìû påîpãàíèçóåì ñëîâàpü -
abc,^de,hjl. Çíàê ^ îçíà÷åò ïpåôèêñ. Ò.å. ìû òåïåpü êîäèpóåì abcde ññûëêîé íà
^de. Ïpè ýòîì äåëàåì ïîèñê ïåpâîé áåñïpåôèêñíîé ïîäñòîêè ñëåâà è âëåâî åå
âñòàâëÿåì. Ò.å. ïpè abc,^de,fe,zz^ äëÿ ññûëêè fe ïåpâîé áåç-ïpåôèêñíîé ïîñëåä.
áóäåò abc. Ïpôèêñû äëÿ îïòèìàëüíîãî ñæàòèÿ êîäèpóþòñÿ ïî-pàçíîìó.
Ìû ìîæåì ñòàâèòü ïpåôèêñ ïåpåä êàæäûé ñèìâîëîì, èëè îêàéìëÿòü ãpóïïó ñèìâîëîâ.
Ïîñêîëüêó ñëîâàpü äëÿ óïàêîâøèêà _âíåøíèé_ è íå âõîäèò â ïîòîê ñæàòûõ äàííûõ,
òî åãî pàçìåp íèêàê íå îòpàæàåòñÿ íà êîô. ñæàòèÿ è ìîæåò áûòü ñêîëü óãîäíî
âåëèê,ïîýòîìó îñòàåòñÿ åäèíñòâåííàÿ ïpîáëåììà êîpîòêîãî êîäèpîâàíèÿ èíäåêñîâ.
Hó òóò âàpèàíòîâ - ìîpå.
SR> Hàñêîëüêî ýòî ïðèìåíèìî ê ôèäîøíûì êîíôåðåíöèÿì?
Ãîpàçäî õóæå. ß ñåé÷àñ ïîýêñïåpåìåíòèpîâàë - ñæàòèå âàpüèpóåòñÿ îò 1/7 äî 1/12
(ïpè óñëîâèè, ÷òî íåò UUE :)
Kris
---
* Origin: Æèçíü - ñêâåpíàÿ øòóêà, íî íè÷åãî ëó÷øåãî ïîêà íå ïpèä (2:5063/61.8)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/26 09 Jan 99 16:04:37
To : All
Subj : ZIP
* Crossposted in RU.COMPRESS
Hello All!
Saturday January 09 1999, Alex Sverdlin writes to Bulat Ziganshin:
BZ>> === ftp.elf.stuba.sk/pub/pc/pack/zip23g.zip ftp.elf.stuba.sk/pub/p
BZ>> c/pack/unzip540.zip === Cut === Îïèñàíèå ôîðìàòà ñæàòûõ äàííûõ
BZ>> (äåéñòâèòåëüíî íà ïàëüöàõ): === Cut
BZ>> === ftp.elf.stuba.sk/pub/pc/pack/appnote.zip === Cut ===
AS> À íå ïîäêèíåò ëè êòî, ïëç, à òî èíåòà íåòó :(
Äà, êñòàòè - ÿ ýòî âñå (ïëþñ cabarc sdk) êèíó â ôýõó adevcomp ïîñëå
ïðàçäíèêîâ. À â autlcomp - jar, imp, cabarc.exe, bix.
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
--- GoldED/386 2.50+
* Origin: Ïîñëå ãëóáîêîãî ñíà òðåáóåòñÿ ïðîäîëæèòåëüíûé îòäûõ (2:5093/26)
— RU.COMPRESS
From : Dmitry Shkarin 2:5020/400 10 Jan 99 16:23:04
To : All
Subj : Re: cabarc
From: "Dmitry Shkarin" <shkarin@arstel.ru>
Hi, Bulat!
>
> DS> È ÷òî âû âñå âöåïèëèñü â LZ77?
>
> À ÷òî â ýòîé ýõå åùå äåëàòü? :)
>
1) ïðîöåññîðû ñîçðåëè äî áîëåå ñëîæíûõ àëãîðèòìîâ (ãëÿäèøü, ÷åðåç ïàðó
ïîêîëåíèé ïðîöåâ è ACB îêàæåòñÿ ïðèåìëåìûì).
2) LZ77 õîðîø òîëüêî íà íåîäíîðîäíîé èíô-öèè, ìåä., òåõ., íàó÷íàÿ
îäíîðîäíû è ñ÷åò òàì èäåò íà ÃÁàéòû.
--- ifmail v.2.14dev2
* Origin: COMSTAR Telecommunications (2:5020/400@fidonet)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/61 10 Jan 99 21:37:37
To : Vadim Yoockin
Subj : Èòàê, êàêèì ÿ âèæó LZH ñëåäóþùåãî ïîêîëåíèÿ
*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).
* Crossposted in RU.COMPRESS
Hello Vadim!
Saturday January 09 1999, Vadim Yoockin writes to Bulat Ziganshin:
VY>> E9 ñëèøêîì ðåäîê â exe32.
BZ>> 1%. Ìîæåò, FAR 1.60 è íåòèïè÷åí, ÿ ìàññîâûõ òåñòîâ íå ïðîâîäèë.
VY> Òàì åñòü èíòåðåñíûå êóñî÷êè, êàê ðàç ïîä E9 (íàïðèìåð, ïî àäðåñó 0xF12).
Ëàäíî, äîìà ïîêðó÷ó äðóãèå EXE. À òàê - ÷åì far õóæå Calgary Corpus? :)
VY>> Î÷åíü õîðîøî MM ðàñïîçíàåò uharc. Ðåñóðñ îò Quake1 îí óïàêîâàë ëó÷øå
VY>> âñåõ.
BZ>> ß ÷òî òàì ðàñïîçíàâàòü, ïî÷òè òàê æå, êàê è òàáëèöû. Hà ìîé âçãëÿä -
BZ>> òîëüêî ðàçìåðû òàáëè÷åê áîëüøå è ïîðÿäêà â íèõ ìåíüøå.
VY> Ó RAR'a òàê íå ïîëó÷àåòñÿ (óâû, òî÷íîñòü 2kb + îøèáêè).
Âñå æå îí òðè ãîäà íàçàä ñäåëàí. Ñ âûñîòû íûíåøíåãî äíÿ ýòî êàæåòñÿ
äîñòàòî÷íî ïðîñòîé çàäà÷åé.
VY> Åñëè èñïîëüçîâàòü qsort3, òî ìîæíî íà êàæäîì óãëóáëåíèè ôîðìèðîâàòü
VY> ññûëêè. Âïðî÷åì, ýòî åùå íåèçâåäàííàÿ îáëàñòü è, ì.á. áóäóò ñâîè
VY> ïðîáëåìû.
ß âèæó ïîêà òîëüêî òàêîé ðàçðåç - ñîðòèðóåì ïî äâóì áóêâàì+ïîçèöèÿ (èëè
óñòîé÷èâàÿ ñîðòèðîâêà ïðîñòî ïî äâóì áóêâàì). Çàïîëíÿåì Offsets[2].
Äîñîðòèðîâûâàåì ïî òðåòüåé áóêâå. Çàïîëíÿåì Offsets[3]. Îäíàêî ñîðòèðîâêà ïî
îäíîé áóêâå çà ðàç áóäåò î÷åíü ìåäëåííîé, à õðàíèòü âñå ýòè Offsets äëÿ âñåõ
ïîçèöèé â ôàéëå - ñëèøêîì äîðîãî. Òàê ÷òî - íàäî äàëüøå äóìàòü.
BZ>> Ïîíÿë, à ìîæåøü íà òîì æå far 1.60 (èëè, ñêàæåì, cabarc) êèíóòü
BZ>> ñïèñîê íàéäåííûõ òàáëè÷åê? Òèïà òàêîãî:
VY> Áîþñü, íåïðîñòî áóäåò îòäåëèòü òàáëè÷êè îò âñåãî îñòàëüíîãî.
VY> Hî ÷óòü ïîçæå ïîñòàðàþñü (íàïîìíè, åñëè çàáóäó).
À ìíå êàçàëîñü, ÷òî íåñëîæíî. Hó ÷òî ïîäåëàåøü, æäåì-ñ.
BZ>> À âîò ýòîãî ÿ òàê è íå ñäåëàë, îáîøåëñÿ âû÷èòàíèåì "íà ìåñòå".
BZ>> Âîîáùå, åñëè ýòî îòäåëÿòü îò LZ - íåÿñíî, ïðîèãðàåøü èëè âûèãðàåøü. À
BZ>> åùå ÿ íå ñäåëàë ñîñòàâíîé ìóëüòèìåäèè, òèïà 4/8.
VY> À ÷òî òàêîå ñîñòàâíàÿ ìóëüòèìåäèÿ?
Hó âîò ïðèìåð:
00 ADD
01 ADC
02 SUB
03 SBB
Òî åñòü êîãäà âû÷èòàòü íóæíî ìåíüøåå ÷èñëî áàéòîâ, ÷åì øàã òàáëè÷êè.  äàííîì
ñëó÷àå (ïðè crl/lf) ýòî 2/8.
Äà, åñëè òû íå â êóðñå, ÿ íàçûâàþ ìóëüòèìåäèåé òî, ÷òî òû íàçûâàåøü
òàáëè÷êàìè :) Ýòî ñòàðàÿ ìîÿ òåðìèíîëîãèÿ, õîòÿ òâîÿ ëó÷øå - ÿ åùå íå ñêîðî îò
ñâîåé ïîëíîñòüþ èçáàâëþñü :)
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ: work 11849833, home 15872722
---
* Origin: Ó ýòîé ìàøèíû íåò ïðîáëåì ñ ãëþêàìè! (2:5093/61)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 10 Jan 99 22:45:26
To : Bulat Ziganshin
Subj : Èòàê, êàêèì ÿ âèæó LZH ñëåäóþùåãî ïîêîëåíèÿ
Ïpèâåòñòâóþ, Bulat!
10 Jan 99, Bulat Ziganshin ïèñàë ê All:
VY>> E9 ñëèøêîì ðåäîê â exe32.
BZ>> 1%. Ìîæåò, FAR 1.60 è íåòèïè÷åí, ÿ ìàññîâûõ òåñòîâ íå ïðîâîäèë.
VY> Òàì åñòü èíòåðåñíûå êóñî÷êè, êàê ðàç ïîä E9 (íàïðèìåð, ïî àäðåñó
VY> 0xF12).
Ýòî ÿ, ïðàâäà, â 1.40 ñìîòðåë. Áóäåì ñ÷èòàòü, íèêòî íå çàìåòèë ;)
BZ> Ëàäíî, äîìà ïîêðó÷ó äðóãèå EXE.
BZ> À òàê - ÷åì far õóæå Calgary Corpus? :)
Ìîé òåñòîâûé wcc386.exe - òîæå åùå òîò ýêçåìïëÿð ;)
VY>> Î÷åíü õîðîøî MM ðàñïîçíàåò uharc. Ðåñóðñ îò Quake1 îí óïàêîâàë
VY>> ëó÷øå âñåõ.
BZ>> ß ÷òî òàì ðàñïîçíàâàòü, ïî÷òè òàê æå, êàê è òàáëèöû. Hà ìîé âçãëÿä
BZ>> - òîëüêî ðàçìåðû òàáëè÷åê áîëüøå è ïîðÿäêà â íèõ ìåíüøå.
VY> Ó RAR'a òàê íå ïîëó÷àåòñÿ (óâû, òî÷íîñòü 2kb + îøèáêè).
BZ> Âñå æå îí òðè ãîäà íàçàä ñäåëàí. Ñ âûñîòû íûíåøíåãî äíÿ ýòî
BZ> êàæåòñÿ äîñòàòî÷íî ïðîñòîé çàäà÷åé.
À ÿ âîò ýòî äî ñèõ ïîð ïîäðîáíî íå ïðîðàáàòûâàë. Ïîìåðÿòü ýíòðîïèè
è ðåøèòü â ñðàâíåíèè? À òî÷íîñòü îïðåäåëåíèÿ ãðàíèöû?
VY> Åñëè èñïîëüçîâàòü qsort3, òî ìîæíî íà êàæäîì óãëóáëåíèè ôîðìèðîâàòü
VY> ññûëêè. Âïðî÷åì, ýòî åùå íåèçâåäàííàÿ îáëàñòü è, ì.á. áóäóò ñâîè
VY> ïðîáëåìû.
BZ> ß âèæó ïîêà òîëüêî òàêîé ðàçðåç - ñîðòèðóåì ïî äâóì áóêâàì+ïîçèöèÿ
BZ> (èëè óñòîé÷èâàÿ ñîðòèðîâêà ïðîñòî ïî äâóì áóêâàì). Çàïîëíÿåì
BZ> Offsets[2]. Äîñîðòèðîâûâàåì ïî òðåòüåé áóêâå. Çàïîëíÿåì Offsets[3].
BZ> Îäíàêî ñîðòèðîâêà ïî îäíîé áóêâå çà ðàç áóäåò î÷åíü ìåäëåííîé, à
BZ> õðàíèòü âñå ýòè Offsets äëÿ âñåõ ïîçèöèé â ôàéëå - ñëèøêîì äîðîãî.
BZ> Òàê ÷òî - íàäî äàëüøå äóìàòü.
À çà÷åì ñòîëüêî îôôñåòîâ? Hàëüçÿ îãðàíè÷èòüñÿ îäíèì íà áóêâó?
×òî êàñàåòñÿ ñêîðîñòè - òî êîëè÷åñòâî êîíòåêñòîâ
äëÿ äîñîðòèðîâêè óáûâàåò äîâîëüíî áûñòðî.
Ëàäíî, áóäåì äóìàòü.
BZ>> Ïîíÿë, à ìîæåøü íà òîì æå far 1.60 (èëè, ñêàæåì, cabarc) êèíóòü
BZ>> ñïèñîê íàéäåííûõ òàáëè÷åê? Òèïà òàêîãî:
VY> Áîþñü, íåïðîñòî áóäåò îòäåëèòü òàáëè÷êè îò âñåãî îñòàëüíîãî.
VY> Hî ÷óòü ïîçæå ïîñòàðàþñü (íàïîìíè, åñëè çàáóäó).
BZ> À ìíå êàçàëîñü, ÷òî íåñëîæíî. Hó ÷òî ïîäåëàåøü, æäåì-ñ.
Ïðîñòî âðåìÿ íàäî (ïàðó íåäåëü ÿ åùå íå ïèñàòåëü). Ñäåëàþ, êîíå÷íî.
Êñòàòè, ÷òî êàñàåòñÿ òàáëè÷åê, òî ÿ îáðàáàòûâàë òîëüêî 4-áàéòîâûå.
BZ>> À âîò ýòîãî ÿ òàê è íå ñäåëàë, îáîøåëñÿ âû÷èòàíèåì "íà ìåñòå".
BZ>> Âîîáùå, åñëè ýòî îòäåëÿòü îò LZ - íåÿñíî, ïðîèãðàåøü èëè âûèãðàåøü.
BZ>> À
BZ>> åùå ÿ íå ñäåëàë ñîñòàâíîé ìóëüòèìåäèè, òèïà 4/8.
VY> À ÷òî òàêîå ñîñòàâíàÿ ìóëüòèìåäèÿ?
BZ> Hó âîò ïðèìåð:
BZ> 00 ADD
BZ> 01 ADC
BZ> 02 SUB
BZ> 03 SBB
BZ> Òî åñòü êîãäà âû÷èòàòü íóæíî ìåíüøåå ÷èñëî áàéòîâ, ÷åì øàã
BZ> òàáëè÷êè.  äàííîì ñëó÷àå (ïðè crl/lf) ýòî 2/8.
À ýòî íå ðåøàåòñÿ ïîâòîðàìè distance, length?
Ñòîèò ëè èãðà ñâå÷?
Âñåãî äîáðîãî. Vadim Yoockin
... 2.000.000 Lemmings can't be wrong.
--- Ñòàpûé Äåä ñòîèìîñòüþ 3.00.Alpha4 äîïëàòà â ÑÊÂ UNREG
* Origin: yoockinv@mtu-net.ru (2:5020/1042.50)
— RU.COMPRESS
From : Igor Pavlov 2:5020/400 10 Jan 99 22:47:53
To : All
Subj : Re: Êàê ðóëèòü ïîòîêè ìåæäó êîäåðîì è äîæèìàëêîé ???!!!
From: "Igor Pavlov" <igor@znanie.ufanet.ru>
Bulat Ziganshin wrote in message <915897466@f26.n5093.z2.ftn>...
> IP> Êñòàòè, ïîïðîáóé íàòðàâè ýòîò àëãîðèòì íà îáû÷íûé hash lists search:
> IP> ñîáèðàé ïî äîðîãå âñå õîðîøèå ñîâïàäåíèÿ.
>
> ?
äèñòàíöèè äëÿ ñîâïàäåíèé ñ äëèííàìè îò 2 äî ìàêñèìàëüíîãî
> >> Òû ìîæåøü êàê-òî îáîçíà÷èòü êëàññ òàêèõ ôàéëîâ (êàê ÿ âûøå
> >> îáîçíà÷èë êëàññ ïëîõèõ äëÿ zip)?
>
> IP> ß çíàþ íåñêîëüêî ïðèìåðîâ.
> IP> êóñîê èç pdf ôàéëà:
>
> IP> 0000596023 00000 n
> IP> 0000596084 00000 n
> IP> 0000596145 00000 n
> IP> 0000596206 00000 n
> IP> 0000596267 00000 n
> IP> 0000596329 00000 n
> IP> 0000596390 00000 n
> IP> 0000596451 00000 n
> IP> ....
>
> ß áûë ïðàâ. Òèïè÷íåéøàÿ òàáëè÷êà. Âîò òåáå ïðîñòåíüêèé ðåöåïò - ëîâèøü åå ïî
>rep_both èëè áëèçêèì ñòðîêàì (ñ ìàëåíüêèì ñìåùåíèåì è äëèíîé ìåíüøå ñìåùåíèÿ).
>Âûñëåæèâàåøü åå îêîí÷àíèå ïî çàâåðøåíèþ ó÷àñòêà ìîíîòîííîñòè (ëó÷øå áóäåò,
>åñëè òû áóäåøü èãíîðèðîâàòü íåáîëüøèå îòêëîíåíèÿ, òèïà îäèí ðàç íå â òó
>ñòîðîíó, çàòî ïîòîì ïÿòü ìîíîòîííûõ èçìåíåíèé - êñòàòè, íàïðàâëåíèå
>ìîíîòîííîñòè â òàêèõ òàáëè÷êàõ ìîæåò è ìåíÿòüñÿ). Êîäèðîâàíèå - âûâîäèøü â
>âûõîäíîé ïîòîê ïðèçíàê "íà÷àëî òàáëè÷êè" (äàé åìó îòäåëüíûé êîä â õàôìåíîâñêîé
>òàáëèöå), ïàðàìåòðû ýòîé òàáëè÷êè (ðàçìåð ýëåìåíòà, êàê ìèíèìóì), äàëåå
>âû÷òåííûå äàííûå, çàòåì "êîíåö òàáëè÷êè". btw, ÿ ëè÷íî íå èñïîëüçóþ "êîíåö
>òàáëè÷êè", à êîäèðóþ ïîñëå "íà÷àëà òàáëè÷êè" ÷èñëî ýëåìåíòîâ â íåé.
> Âû÷òåííûå äàííûå ëó÷øå ïèñàòü íå íàïðÿìóþ (ñ êó÷åé íóëåâûõ áàéòîâ), à ïî
>áàçèñó ïåðâîãî ýëåìåíòà (òîãäà ëèøíèå íóëåâûå áàéòû ïîÿâëÿòüñÿ íå áóäóò).
>
> Åùå íåïëîõî áû äåëàòü èçáèðàòåëüíîå âû÷èòàíèå (åñëè ó íàñ åñòü äâà áàéòà
>ïîñòîÿííûõ, äâà ìîíîòîííûõ, äâà ñî ñëó÷àéíûìè äàííûìè); èíîãäà xor ëó÷øå
>âû÷èòàíèÿ (íà geo, êñòàòè). È òàáëè÷êè ñ êîðîòêèìè ýëåìåíòàìè íàäî ëîâèòü
>ïî-äðóãîìó - ïðîñòî ñðàâíåíèÿìè, ïðè íûíåøíèõ òîðìîçíûõ àëãîðèòìàõ ýòî íå òàê
>óæ ñòðàøíî. Ïîæàëóé ýòî âñå, ÷òî íóæíî äëÿ ôàêà. Êîãäà ïðèêàæåøü æäàòü íîâóþ
>âåðñèþ bix?
ß ïîêà íå õî÷ó ýòè ñëó÷àè îòëàâëèâàòü îòäåëüíî: íàäî ðàçîáðàòüñÿ ïîëó÷øå.
> Áåðåøü è ïðåðûâàåøü :) Ïðîñòî è íàãëî. Êàê òîëüêî òåáå íàäîåëî "ñïóñêàòüñÿ
>ïî äåðåâó, ïåðåñòðàèâàÿ åãî íà õîäó" - â ñìûñëå, êàê ñ÷åò÷èê ïåðåâàëèë çà
>íåêóþ îòìåòêó. Ìîæåò ñäåëàòü è òîíüøå - ïðè ñïóñêå âëåâî ïðîâåðÿòü, áûëà ëè
>ññûëêà âïðàâî, è ïîñëå íåñêîëüêòõ äåñÿòêîâ ñïóñêîâ ïî âûðîæäåííîìó ñåãìåíòó
>äåðåâà ïîñûëàòü âñåõ íàôèã. Håäîñòàòîê - çàìåäëÿåòñÿ ðàáîòà íà âñåõ ôàéëàõ.
Ïîæåðòâîâàòü 10-20% ñêîðîñòè íå æàëêî, ëèøü áû ïîìîãëî.
> >> 2) Èñïîëüçîâàòü âìåñòî ïî äâóì áàéòàì õåøèðîâàíèå ïî
> >> 4-5. Õîòÿ ýòî íåýôôåêòèâíî ïðè íîðìàëüíîì ïîâåäåíèè àëãîðèòìà, êîãäà
> >> ãëóáèíà äåðåâà ïðîïîðöèîíàëüíà ëîãàðèôìó ÷èñëà ýëåìåíòîâ â íåì, â
> >> âûðîæäåííûõ ñëó÷àÿõ ýòîò ïîäõîä äàñò ñóùåñòâåííîå óëó÷øåíèå
> >> ñêîðîñòè. Õîòÿ íåò, íå âñåãäà. Âûèãðûø áóäåò ïðîïîðöèîíàëåí êîë-âó
> >> äåðåâüåâ, ïî êîòîðûì óäàñòñÿ ðàñêèäàòü îðèãèíàëüíóþ öåïî÷êó.
>
> IP> Imho ìîæåò íå ïîìî÷ü (èëè ïîìî÷ü, íî íå âî âñåõ ñëó÷àÿõ), ÿ ïðîâåðþ.
Hà ìîåì PDF ïðè õåøèðîâàíèÿ ïî 5-6 áàéòàì ïîìîãàåò,
à äëÿ êånnedy íå ïîìàãàåò - òàì ðàçìåð ñòðóêòóð áîëüøå.
> IP> ïðîñòî ìîíîòîííàÿ ïîñëåäîâàòåëüíîñòü íå ñòðàøíà, ò.ê áóäåò
> IP> âñåãî îäíà èòåðàöèÿ.
>
> Håò. Âîò ìîå îïèñàíèå:
>
> ...
> Òåïåðü ñàì ñìîòðè - îäíîâðåìåííîå âûïîëíåíèå òðåáîâàíèé "äåðåâî ïîèñêà" è
>"ññûëêè òîëüêî íàçàä" æåñòêî ôèêñèðóåò äåðåâî, êîòîðîå ìîæíî ïîñòðîèòü ïî
>îïðåäåëåííûì âõîäíûì äàííûì; áàëàíñèðîâêà äåðåâà ñ öåëüþ óìåíüøèòü åãî ãëóáèíó
>çäåñü íåâîçìîæíà. Hà ìîíîòîííîé ïîñë-òè 0001,0002,...,0099 ìû ïîëó÷èì âîò
>òàêîå äåðåâî: 0099 ..... 0002 / 0001 Âûðîæäåííîå äåðåâî,
>êàê âèäèøü. È òàêèå äåðåâüÿ áóäóò ïîëó÷àòüñÿ âñÿêèé ðàç íà ìîíîòîííî
>èçìåíÿùèõñÿ äàííûõ.
Hó è ïëåâàòü, ÷òî âûðîæäåííîå, âñå ðàâíî íà ïîèñê/èçìåíåíèå íóæíà âñåãî îäíà
èòåðàöèÿ.
>Áîëåå òîãî, äàæå åñëè ýòè äàííûå ïåðåìåæàþòñÿ
>äðóãèìè (0001,..0050, 00ab, 00cd..., 0051, ..0099), äàæå "÷åðåçïîëîñèöåé"
>(00001, 001ab, ...0099, 001xy); äàæå â ýòèõ ñëó÷àÿõ íàøè ìîíîòîííûå äàííûå
>áóäóò îáðàçîâûâàòü ñâîè àâòîíîìèè - âûðîæäåííûå ïîääåðåâüÿ â îáû÷íîì äåðåâå.
>Ïðè÷åì ýòà âûðîæäåííîñòü áóäåò ñêàçûâàòüñÿ òîëüêî ïðè ïîèñêå òàêèõ æå äàííûõ -
>ïðè ïîèñêå îáû÷íûõ ñòðîê, íå çàìå÷åííûõ â òàáëè÷êàõ, ìû ïðîñòî íå áóäåì
>ïîïàäàòü â âûðîæäåííóþ ÷àñòü äåðåâà. Hàâåðíîå â ñëó÷àå ñ òåì pdf êàê ðàç
>êàêàÿ-òî ñïèðàëü, íî ÿ âñå ðàâíî ïëîõî ïîíèìàþ, ÷òî òàì ïðîèñõîäèò. Èìåííî
>ìîíîòîííàÿ ïîñëåäîâàòåëüíîñòü, ïîñìîòðè ñàì, ðàçâå åå ñëîæíî çàìåòèòü?
ß íàïèñàë ìàëåíüêóþ ïðîãðàììó äëÿ èñëåäîâàíèé:
#include <stdio.h>
#include <stdlib.h>
int main(int n, char *aStrings[])
{
if(n != 3)
return (1);
char aFormat[20];
sprintf(aFormat, "%%0%dd\n", atoi(aStrings[1]));
int aNum = atoi(aStrings[2]);
for(int i = 0; i < aNum; i++)
printf(aFormat, i);
return 0;
}
èñïîëüçîâàòü:
a.exe Êîëè÷åñòâîâî_çíàêîâ_â_îäíîì_÷èñëå Êîëè÷åñòâîâî_÷èñåë
îíà ñîçäàåò òàêóþ ïîñëåäîâàòåëüíîñòü
00000000
00000001
00000002
00000003
00000004
...
âîò ðåçóëüòàòû, äëÿ 10000 ÷èñåë:
Êîë-âî çíàêîâ / Âðåìÿ ñæàòèÿ â ñåêóíäàõ
6 2
7 5
8 24
9 44
Ò.å. äëÿ ïðîñòî ìîíîòîííîé ïîñë-òè âñå íîðìàëüíî.
À â äðóãèõ ñëó÷àÿõ ïðîèñõîäèò íåêîòîðîå ñïèðàëüíîå íàëîæåíèå:
(âñå äëÿ îäíîãî äåðåâà):
0000a
000b
00ñ
0d
e
0000(a+k)
000(b+k)
00(c+k)
0(d+k)
(e+k)
...
Êñòàòè, Áóëàò, ó òåáÿ â òâîåé ïðîöåäóðå longest_match for cabarc,
êàæåòñÿ, åñòü îøèáêà: òû ãäå-òî ïåðåïóòàë left è right.
> IP> Min(Compressed_Size / Modem_Speed + Extract_time).
>
> ß è çäåñü âñòàâëþ ñâîþ ïàðó ñëîâ. Âî-ïåðâûõ, ïðè÷åì çäåñü ìîäåìû? Ýòî ïðîñòî
>ïîïóëèçì. Ñêëàäûâàåì óòÿò ñ öûïëÿòàìè, èñïîëüçóÿ ïåðâûé ïîïàâøèéñÿ êîýôô.
>ïåðåñ÷åòà. Òîëüêî óìíîæåíèå! :) Âî-âòîðûõ, ÿñíî, ÷òî óìíîæàòü ðàçìåð ñæàòîãî
>ôàéëà íà ñêîðîñòü ðàáîòû òîæå íåõîðîøî - óâåëè÷åíèå ñæàòèÿ íà 10% è óñêîðåíèå
>ðàáîòû íà 10% ñîâñåì íå ðàâíîöåííûå âåùè. Òàêèì îáðàçîì, è çäåñü íóæíû
>êîýôôèöèåíòû, ïðåäñòàâëåííûå â âèäå ñòåïåíåé. Ðàçóìååòñÿ, îíè â íåêîòîðîé
>ñòåïåíè ïðîèçâîëüíû - îäíèì íóæíà ñêîðîñòü, äðóãèì ñæàòèå; â îäíèõ ñëó÷àÿõ
>íóæíî áûñòðî ñæàòü, â äðóãèõ - áûñòðî ðàñïàêîâàòü. Îäíàêî, ÿ ñ÷èòàþ, âñå òåñòû
>"øèðîêîãî ïðèìåíåíèÿ" äîëæíû èñïîëüçîâàòü èìåííî ìóëüòèïëèêàòèâíûå
>èíòåãðàëüíûå ôîðìóëû - ñ òåìè èëè èíûìè êîýôôèöèåíòàìè. ×òî êàñàåòñÿ ñàìèõ
>êîýôô-â, òî èìõî common sense áóäåò òàêîé - äàòü îäèíàêîâûå âåñà óïàêîâêå è
>ðàñïàêîâêå, òî åñòü ñ÷èòàòü, ÷òî óïàêîâêà â 1.5 ðàçà äîëüøå êîìïåíñèðóåòñÿ
>ðàñïàêîâêîé â 1.5 ðàçà áûñòðåå. ×òî êàñàåòñÿ ñòåïåíè ñæàòèÿ, òî ÿ áû ïîñ÷èòàë
>íîðìàëüíîé ðàñïëàòîé çà 10%-íîå åå óâåëè÷åíèå 5-êðàòíîå çàìåäëåíèå óïàêîâêè
>_è_ ðàñïàêîâêè. ln(5*5)/ln(1.1)=33. Òàê ÷òî ôîðìóëà ñ÷àñòüÿ âûãëÿäèò òàê:
>size*pow(add*extract,1/33). Ïðè ýòîì ðåçóëüòàò ìîæíî èçìåðÿòü â ïîïóãàÿõ, òî
>åñòü íîðìàëèçîâàòü ïî îòíîøåíèþ ê êàêîìó-íèáóäü zip.
Imho ñëîæíûå ìåõàíèçìû ïðèäóìâàòü íå ñòîèò. Ëó÷øå âûáðàòü íåñêîëüêî òèïè÷íûõ
çàäà÷ è çàäàòü äëÿ êàæäîé èç íèõ íåêîòîðóþ ïðîñòóþ ôîðìóëó.
Jeff âûáðàë òîëüêî îäíó èç âîçìîæíûõ çàäà÷.
> Òîãäà îñòàëñÿ òîëüêî îäèí âîïðîñ - à ýòîìó àëãîðèòìó îïòèìàëüíûõ ìàò÷åé
> âàæíî òî, ÷òî ìû íàøëè ñîâïàäåíèÿ äëÿ âñåõ ïîçèöèé â îêíå?
Imho íóæíû ñîâðàäåíèÿ èç äâóõ êëàññîâ: êîðîòêèå ïî äèñòàíöèè è áîëüøèå ïî
äëèíå.
Hàïðèìåð,
23 / 1mb
17/ 100kb
5/ 100
3/ 23
>Èëè, êàê è â îáû÷íîì lazy
>matching, íóæíû òîëüêî ìàò÷è ïîñëå âûâåäåííûõ ñòðîê +/- 1? Òî åñòü, äðóãèìè
>ñëîâàìè, âîçìîæíî ëè ñäåëàòü optimal matching áåç õåø-äåðåâüåâ?
Äà, íî íóæíî äåëàòü ïîèñê íà êàæäûé ñèìâîë.
>PS: Âìåñòî ïîñëåñëîâèÿ - íå õî÷åøü ñäåëàòü äëèííûå ñòðîêè? :)
Äëèííûå ñòðîêè?
> È ñëîâàðü çàîäíî
>åùå? :))
Imho ñëîâàðü ýòî ïîëóìåðà, êîòîðàÿ ñîçäàåò êó÷ó ïðîáëåì.
- ---
Èãîðü
--- ifmail v.2.14dev2
* Origin: Ufa State Aviation Technical University (2:5020/400@fidonet)
— RU.COMPRESS
From : Igor Pavlov 2:5020/400 10 Jan 99 22:47:54
To : All
Subj : Re: optimal lzh
From: "Igor Pavlov" <igor@znanie.ufanet.ru>
Bulat Ziganshin wrote in message <916012183@f61.n5093.z2.ftn>...
>* Crossposted in RU.COMPRESS
> Hàñêîëüêî ÿ âèæó, åäèíñòâåííîé ýìïèðè÷åñêîé ÷àñòüþ îñòàåòñÿ îöåíêà ÷èñëà
> áèò.
Ìîæíî äàæå íå ñìîòðåòü íà ïðåäûäóùèé huffman áëîê (à èñïîëüçîâàòü êîíñòàíòû):
ß ïîëó÷èë ãäå-òî 268 äëÿ book1 ïðîòèâ 264.
>Åñòü ïîâîä äëÿ îáñóæäåíèÿ :) Åùå âîïðîñ - êàêîé ïðîöåíò âðåìåíè óõîäèò íà
>ðàáîòó ñ äåðåâîì?
Çàâèñèò îò äàííûõ.
 õîðîøåì ñëó÷àå ãäå-òî 70 %.
>È êàêîé ðàçìåð áóôåðà îïòèìàëüíîãî êîäèðîâàíèÿ?
Ó íèõ â àëãîðèòìå åñòü óñëîâèå âûõîäà èç îñíîâíîãî öèêëà:
for(int i=0; i < Big_Value; i++)
{
åñëè íèêòî äàëüøå i íå ñòðåëÿë, òî âûõîä.
...
À Big_Value = ~2000;
Òàì åñòü åùå êó÷à âñÿêèõ ôè÷, íî ÿ íå îïèñàë òîëüêî ñóòü.
- ---
Èãîðü
--- ifmail v.2.14dev2
* Origin: Ufa State Aviation Technical University (2:5020/400@fidonet)