— RU.COMPRESS
From : Bulat Ziganshin 2:5093/4.126 11 Oct 01 11:01:31
To : Maxim Smirnov
Subj : Ñóïåðñæàòèå
* Originally in RU.COMPRESS
Ïðèÿòíîãî òåáå äíÿ è íåçàáûâàåìîé íî÷è, Maxim!
Thursday October 11 2001, Maxim Smirnov writes to Bulat Ziganshin:
BZ>> ÿ âåäü ñïåöèàëüíî ïîä÷åðêíóë - çäåñü, êàê è òàì, ÷åì ëó÷øå òû
BZ>> ñïîñîáåí îïèñàòü ñâîþ ñèòóàöèþ, òåì áîëåå ïîëåçíûé îòâåò
BZ>> ïîëó÷èøü. ïîêà ÷òî òû ïîëó÷èë îòâåò èñêëþ÷èòåëüíî äóðàöêèé, íàäî
BZ>> ñêàçàòü
MS> Ïðåäëàãàþ âíåñòè ýòî â ru.compress FAQ (âðîäå áûë òàêîé?).
MS> Hàïèñàòü áîëüøèìè friendly áóêâàìè.
íå ïîìîæåò, â ðóïèêàï òàêîå óæå ïðîáîâàëè, è íåîäíîêðàòíî. äóìàòü íèêîìó íåîõîò
à, âñå íîðîâÿò íà ãîòîâåíüêîå, íå ïîíèìàÿ, ÷òî ýòîò êàê ðàç òîò ñëó÷àé, êîãäà,
ñýêîíîìèâ ïîë÷àñà, ïðèä¸òñÿ ïîòåðÿòü ìåñÿöû
Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722
... Èíîãäà äëÿ òîãî, ÷òîáû èçìåíèòü ñâîå âîñïðèÿòèå ìèðà,
... ëþäè ïûòàþòñÿ èçìåíèòü ñàì ìèð
--- GoldED+/W32 1.1.2
* Origin: Ñåòåâîé ôèëüòð íà 5 áàçàðîâ (2:5093/4.126)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/4.126 11 Oct 01 11:06:57
To : EinWill" <andrey@neva-roentgen.com>
Subj : Ãëóáèíà Huffman äåðåâà
* Originally in RU.COMPRESS
Ïðèÿòíîãî òåáå äíÿ è íåçàáûâàåìîé íî÷è, EinWill"!
Thursday October 11 2001, EinWill" <andrey@neva-roentgen.com> Reply-To: "EinWil
l writes to Dmitry Shkarin:
Ea>  ïëþñå - ìû êîäèðóåì ÷èñëî <=9 áèòàìè
Ea>  ìèíóñå - íà çàïèñü ÷àñòîóïîòðåáëÿåìûõ ñèìâîëîâ (òå, êîòîðûå ìû íå
Ea> îòáðîñèëè) ìû òðàòèì íà îäèí áèò áîëüøå (÷åì ïðè êëàññè÷åñêîì
Ea> àëãîðèòìå).
Ea> Äóìàþ, íå ÿ ïåðâûé òàêîå ïðåäëàãàþ. Ïîýòîìó, âîïðîñ, äàåò ëè âûèãðûø
Ea> òàêîé àëãîðèòì? È åñëè äà, òî êàê ÷àñòî :-)
ÏÎ ÎÏÐÅÄÅËÅHÈÞ àëãîðèüòì õàôìåíà äà¸ò îïòèìàëüíîå äåðåâî :))
÷òî êàñàåòñÿ àëãîðèòìîâ, îãðàíè÷èâàþùèõ ÷èñëî áèò è äëÿ ýòîãî ñëåãêà ìåíÿþùèõ ä
åðåâî (áåç òàêèõ ðàäèêàëüíûõ ìåð), òî ÿ óæå ãîâîðèë, ãäå èõ èñêàòü
Ea> P.S.  ïðèíöèïå, ïî ÷àñòîòå âõîæäåíèÿ ìîæíî ñðàçó îïðåäåëèòü, âûãîäíî
Ea> ëè òàê ìîäèôèöèðîâàòü àëãîðèòì èëè íåò. È, ñîîòâåòñòâåííî, ïîñòàâèâ â
Ea> ñàìîì íà÷àëå áèò-ñïåöèôèêàòîð (0/1) ÷òîáû ðàçëè÷àòü íüþàíñû êîäèðîâêè,
Ea> ìîæíî ãàðàíòèðîâàííî èçâëå÷ü ïëþñû èç îáîèõ ïîäõîäîâ.
ó áëîíäèíêè ñïðîñèëè
- êàêîâà âåðîÿòíîñòü âñòðåòèòü äèíîçàâðà íà óëèöå?
- 50%. ëèáî âñòðå÷ó, ëèáî íåò
íàóêà âîò òàê íàîáóì íå äåëàåòñÿ, â íåé åù¸ äóìàòü íàäî
Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722
... Èíîãäà äëÿ òîãî, ÷òîáû èçìåíèòü ñâîå âîñïðèÿòèå ìèðà,
... ëþäè ïûòàþòñÿ èçìåíèòü ñàì ìèð
--- GoldED+/W32 1.1.2
* Origin: Ñåòåâîé ôèëüòð íà 5 áàçàðîâ (2:5093/4.126)
— RU.COMPRESS
From : EinWill 2:5020/400 11 Oct 01 11:23:24
To : Dmitry Shkarin
Subj : Re: Ãëóáèíà Huffman äåðåâà
From: "EinWill" <andrey@neva-roentgen.com>
Reply-To: "EinWill" <andrey@neva-roentgen.com>
Ìû ê Âàì, ïðîôåññîð "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru>, è âîò ïî
êàêîìó äåëó:
> > ß îøèáñÿ â ñâîåé ïðîãðàììå, èëè â ïîíèìàíèè ñóòè ïðîèñõîäÿùåãî?
> Âñå íîðìàëüíî, äëèíà êîäà ìîæåò áûòü äî M-1, M - ðàçìåð àëôàâèòà.
Òîëüêî ÷òî ïðîâåðèë âûñêàçàííóþ èäåþ (ñì. ïðåäûäóùåå ïèñüìî) íà íåñêîëüêèõ
ïðèìåðàõ. Âûèãðûø -- äî 30% è âûøå (âìåñòî 9503 áàéò -- 6692, âìåñòî
164772 -- 102396; áåç ó÷åòà çàãîëîâêà ~ 300 áàéò).
2All:
Åñëè ýòî ñòàíäàðòíàÿ îïòèìèçàöèÿ ñæàòèÿ Huffman'à, òî ïî÷åìó î íåé íå
óïîìèíàåòñÿ (âïðî÷åì, ÿ íå ìíîãîå ïî ýòîé òåìå ÷èòàë). Åñëè íå ñòàíäàðòíàÿ,
òî, ñîáñòâåííî, ïî÷åìó?  ñìûñëå, ýòî ó ìåíÿ òàêèå ïðèìåðû "óäà÷íûå", èëè æå
åñòü ðåëèãèîçíûå ïðèíöèïû, íå ïîçâîëÿþùèå èñïîëüçîâàòü òàêóþ ìîäèôèêàöèþ
àëãîðèòìà?
Ñ óâàæåíèåì,
EinWill
--- ifmail v.2.15dev5
* Origin: Fidolook Express 2.000 www.fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Alexander P Spiridonov 2:5053/49.64 11 Oct 01 11:42:18
To : EinWill
Subj : Ãëóáèíà Huffman äåðåâà
Hello, EinWill !
11.10.2001 08:52, EinWill wrote to Dmitry Shkarin:
E> Òîãäà âîïðîñ, à ïî÷åìó íå îãðàíè÷èâàòü äëèíó êîäà 9 áèòàìè? Hàïðèìåð,
E> òàê:
E> Ïîñòðîèâ äåðåâî, ìû îòáðàñûâàåì âñå ëèñòüÿ, ðàñïîëîæåííûå íà ãëóáèíå 8
E> è áîëåå, à ïåðåä âñåì êîäàìè, ïîëó÷åííûìè äëÿ ëèñòüåâ ãëóáèíîé <=7,
E> äîïèñûâàåì áèò 0. Ñîîòâåòñòâåííî, êîãäà êîäèðóåì, òî â ñëó÷àå åñëè
E> î÷åðåäíîé ñèìâîë ÿâëÿåòñÿ íåîòáðîøåííûì ëèñòîì, ìû çàïèñûâàåì åãî êîä
E> (0 + <=7 áèò -- çàïèñûâàåì <=8 áèò), à åñëè èç îòáðîøåííûõ, òî ïèøåì
E> áèò 1, à çàòåì ñàì ñèìâîë -- òî åñòü çàïèñûâàåì òîëüêî 9 áèò.
E> Ðåçëóüòàò:
E>  ïëþñå - ìû êîäèðóåì ÷èñëî <=9 áèòàìè
E>  ìèíóñå - íà çàïèñü ÷àñòîóïîòðåáëÿåìûõ ñèìâîëîâ (òå, êîòîðûå ìû íå
E> îòáðîñèëè) ìû òðàòèì íà îäèí áèò áîëüøå (÷åì ïðè êëàññè÷åñêîì
E> àëãîðèòìå).
E> Äóìàþ, íå ÿ ïåðâûé òàêîå ïðåäëàãàþ. Ïîýòîìó, âîïðîñ, äàåò ëè âûèãðûø
E> òàêîé àëãîðèòì? È åñëè äà, òî êàê ÷àñòî :-)
âûèãðûø íå ïîëó÷èòñÿ íèêîãäà, ïîòîìó ÷òî êîä Õàôôìàíà - îïòèìàëüíûé
(èç âñåõ ïðåôèêñíûõ êîäîâ, åñëè èçâåñòíû ÷àñòîòû ñèìâîëîâ)
ïîëó÷àåòñÿ, ÷òî òâîé 'ïëþñ' áóäåò ïðîÿâëÿòüñÿ ðåäêî (òîëüêî ðåäêî
âñòðå÷àþùèåñÿ ñèìâîëû êîäèðóþòñÿ äëèííûìè êîäàìè), à 'ìèíóñ' - î÷åíü ÷àñòî
With best regards, Alexander
E-Mail: alexsp@hotbox.ru
--- GoldED/W32 3.0.1
* Origin: (2:5053/49.64)
— RU.COMPRESS
From : EinWill 2:5020/400 11 Oct 01 11:46:06
To : All
Subj : Wavelet - ñæàòèå èçîáðàæåíèé
From: "EinWill" <andrey@neva-roentgen.com>
Reply-To: "EinWill" <andrey@neva-roentgen.com>
Âñåì äîáðûé äåíü.
Ãäå áû ïî÷èòàòü î ñæàòèè èçîáðàæåíèÿ ïðè ïîìîùè Wavelet ïðåîáðàçîâàíèé?
Òîëüêî ïî êîíêðåòíåå. Èäåÿ è òàê ïîíÿòíà: ïðÿìîå âñïëåñê-ïðåîáðàçîâàíèå,
îáíóëåíèå ìàëûõ çíà÷åíèé.
À âîò ïî-êîíêðåòíåå: êàêîå âñïåñê ïðåîáðàçîâàíèå èñïîëüçîâàòü (Äîáåøè?
Õààðà? èëè âîîáùå, êàêîå-íèáóäü áåç êîìïàêòíîãî íîñèòåëÿ?) è ò.ï.
Åùå ðàç ïîâòîðÿþ, îñíîâû Âñïëåñê àíàëèçà ÿ çíàþ, è ðàçúÿñíåíèé ïî íèì ìíå
íå íóæíî. Èíòåðåñóåò èìåííî âîïðîñû ïðàêòè÷åñêîé ðåàëèçàöèè.
--
.... C Óâàæåíèåì, EinWill
--- ifmail v.2.15dev5
* Origin: Fidolook Express 2.000 www.fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : EinWill 2:5020/400 11 Oct 01 12:06:47
To : Bulat Ziganshin
Subj : Re: Ãëóáèíà Huffman äåðåâà
From: "EinWill" <andrey@neva-roentgen.com>
Reply-To: "EinWill" <andrey@neva-roentgen.com>
Ìû ê Âàì, ïðîôåññîð "Bulat Ziganshin"
<Bulat.Ziganshin@p126.f4.n5093.z2.fidonet.org>, è âîò ïî êàêîìó äåëó:
> Ea> Äóìàþ, íå ÿ ïåðâûé òàêîå ïðåäëàãàþ. Ïîýòîìó, âîïðîñ, äàåò ëè âûèãðûø
> Ea> òàêîé àëãîðèòì? È åñëè äà, òî êàê ÷àñòî :-)
> ÏÎ ÎÏÐÅÄÅËÅHÈÞ àëãîðèüòì õàôìåíà äà¸ò îïòèìàëüíîå äåðåâî :))
Ýòî è åæó ïîíÿòíî. ÏÎ ÓÑËÎÂÈÞ ìîÿ ìîäèôèêàöèÿ ðàáîòàåò _íå ñ äåðåâîì_ (à
ëèøü â ðÿäå ñëó÷àåâ ñ "ëó÷øåé ïîëîâèíîé" ýòîãî îïòèìàëüíîãî äåðåâà).
> ÷òî êàñàåòñÿ àëãîðèòìîâ, îãðàíè÷èâàþùèõ ÷èñëî áèò è äëÿ ýòîãî ñëåãêà
ìåíÿþùèõ
> äåðåâî (áåç òàêèõ ðàäèêàëüíûõ ìåð), òî ÿ óæå ãîâîðèë, ãäå èõ èñêàòü
Èçâèíè, íà ýòó ýõîêîíôåðåíöèþ ÿ ïîäïèñàí ñðàâíèòåëüíî íåäàâíî; íå ìîã áû
ïîâòîðèòü, ãäå èìåííî?
> ó áëîíäèíêè ñïðîñèëè
> - êàêîâà âåðîÿòíîñòü âñòðåòèòü äèíîçàâðà íà óëèöå?
> - 50%. ëèáî âñòðå÷ó, ëèáî íåò
> íàóêà âîò òàê íàîáóì íå äåëàåòñÿ, â íåé åù¸ äóìàòü íàäî
Áîæå-æå ìîé, è ýòî âû ãîâîðèòå ìíå, àñïèðàíòó êàôåäðû Òåîðèè Âåðîÿòíîñòåé?
:-P
P.S. Ïðî÷èòàé ìîå ïèñüìî ïîä òåì æå subj'åêòîì î ïðîâåäåííûõ "èñïûòàíèÿõ".
֏,
EinWill
--- ifmail v.2.15dev5
* Origin: Fidolook Express 2.000 www.fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Andrew Ezhguroff 2:5020/400 11 Oct 01 14:25:02
To : andrey@neva-roentgen.com
Subj : Re: Ãëóáèíà Huffman äåðåâà
From: "Andrew Ezhguroff" <eandr@com2com.ru>
Ïðèâåò! "EinWill" <andrey@neva-roentgen.com> ñîîáùèë(à) íàì:
> > > ß îøèáñÿ â ñâîåé ïðîãðàììå, èëè â ïîíèìàíèè ñóòè ïðîèñõîäÿùåãî?
> > Âñå íîðìàëüíî, äëèíà êîäà ìîæåò áûòü äî M-1, M - ðàçìåð àëôàâèòà.
> Òîëüêî ÷òî ïðîâåðèë âûñêàçàííóþ èäåþ (ñì. ïðåäûäóùåå ïèñüìî) íà
íåñêîëüêèõ
> ïðèìåðàõ. Âûèãðûø -- äî 30% è âûøå (âìåñòî 9503 áàéò -- 6692, âìåñòî
> 164772 -- 102396; áåç ó÷åòà çàãîëîâêà ~ 300 áàéò).
ÈÌÕÎ, ó òåáÿ èñõîäíûé àëãîðèòì ïîñòðîåíèÿ äåðåâà íåïðàâèëüíî ðàáîòàë. Ëèáî
òåñòîâûå äàííûå íåïðàâèëüíî ïîäîáðàíû:
1. Ñæèìàåì 128 Kb ôàéë, çàáèòûé ñëó÷àéíûìè ñèìâîëàìè (ðàâíàÿ âåðîÿòíîñòü
ïîÿâëåíèÿ êàæäîãî ñèìâîëà).
Êëàññè÷åñêèé õàôìàí îáåñïå÷èò ïî 8 áèò íà ñèìâîë (ðàçìåð ôàéëà íå
èçìåíèòñÿ), à ó òåáÿ ïîëó÷èòñÿ ïî 9 áèò - ðàçìåð óâåëè÷èòñÿ äî 144 Kb.
2. Ñæèìàåì 128 Kb ôàéë, â êîòîðîì áîëüøèíñòâî áàéòîâ - íóëè è åäèíèöû (ñ
ðàâíîé âåðîÿòíîñòüþ), à êàæäûé áàéò ñ êîäîì >1 âñòðå÷àåòñÿ ðîâíî 1 ðàç.
Õàôìàí ïîä áàéòû 0 è 1 îòâåäåò ïî 2 áèòà, à ïîä äðóãèå ñèìâîëû - ïî 9 áèò.
Èòîãî - ÷óòü áîëüøå 32 Kb. Ó òåáÿ ïîä 0 è 1 îòâîäèòñÿ ïî 3 áèòà, à ïîä
îñòàëüíûå ñèìâîëû - ïî 9. Ïîëó÷àåì ÷óòü áîëüøå 48 Kb.
Ñ óâàæåíèåì, Àíäðåé.
--- ifmail v.2.15dev5
* Origin: COMSTAR Telecommunications (2:5020/400)
— RU.COMPRESS
From : EinWill 2:5020/400 11 Oct 01 14:57:59
To : Alexander P Spiridonov
Subj : Re: Ãëóáèíà Huffman äåðåâà
From: "EinWill" <andrey@neva-roentgen.com>
Reply-To: "EinWill" <andrey@neva-roentgen.com>
Ìû ê Âàì, ïðîôåññîð "Alexander P Spiridonov"
<Alexander.P.Spiridonov@p64.f49.n5053.z2.fidonet.org>, è âîò ïî êàêîìó äåëó:
> E> Òîãäà âîïðîñ, à ïî÷åìó íå îãðàíè÷èâàòü äëèíó êîäà 9 áèòàìè? Hàïðèìåð,
> E> òàê:
> âûèãðûø íå ïîëó÷èòñÿ íèêîãäà, ïîòîìó ÷òî êîä Õàôôìàíà - îïòèìàëüíûé
> (èç âñåõ ïðåôèêñíûõ êîäîâ, åñëè èçâåñòíû ÷àñòîòû ñèìâîëîâ)
Î! Ýòî âàæíàÿ äåòàëü. Îïòèìàëüíûé èç âñåõ ïðåôèêñíûõ êîäîâ... ì-ì-ì... ýòî
óæå íå ñòîëü î÷åâèäíî.
Ñïàñèáî. Çíà÷èò, ïðîñòî äåðåâî íåêîððåêòíî ñòðîþ... Ó-ó-ó-ó... È âåäü ôèã
íàéäåøü ãäå îøèáñÿ...
> ïîëó÷àåòñÿ, ÷òî òâîé 'ïëþñ' áóäåò ïðîÿâëÿòüñÿ ðåäêî (òîëüêî ðåäêî
> âñòðå÷àþùèåñÿ ñèìâîëû êîäèðóþòñÿ äëèííûìè êîäàìè), à 'ìèíóñ' - î÷åíü ÷àñòî
ßñíåíüêî...
Ñ óâàæåíèåì,
EinWill
--- ifmail v.2.15dev5
* Origin: Fidolook Express 2.000 www.fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/4.126 11 Oct 01 15:01:09
To : EinWill" <andrey@neva-roentgen.com>
Subj : Ãëóáèíà Huffman äåðåâà
* Originally in RU.COMPRESS
Ïðèÿòíîãî òåáå äíÿ è íåçàáûâàåìîé íî÷è, EinWill"!
Thursday October 11 2001, EinWill" <andrey@neva-roentgen.com> Reply-To: "EinWil
l writes to Dmitry Shkarin:
>> > ß îøèáñÿ â ñâîåé ïðîãðàììå, èëè â ïîíèìàíèè ñóòè ïðîèñõîäÿùåãî?
>> Âñå íîðìàëüíî, äëèíà êîäà ìîæåò áûòü äî M-1, M - ðàçìåð
>> àëôàâèòà.
Ea> Òîëüêî ÷òî ïðîâåðèë âûñêàçàííóþ èäåþ (ñì. ïðåäûäóùåå ïèñüìî) íà
Ea> íåñêîëüêèõ ïðèìåðàõ. Âûèãðûø -- äî 30% è âûøå (âìåñòî 9503 áàéò --
Ea> 6692, âìåñòî 164772 -- 102396; áåç ó÷åòà çàãîëîâêà ~ 300 áàéò).
à âîò ýòî òî÷íî îøèáêà ëèáî â òîì, ëèáî â äðóãîì àëãîðèòìå :))
êñòàòè, ó äèìû ñëèøêîì ïåññèìèñòè÷íàÿ îöåíêà. åñòü âåäü è ðàçìåð áóôåðà, îí îãð
àíè÷èâàåò îáû÷íî ñèëüíåå (ïîêà íà íàøèõ ìàøèíàõ ìåíüøå 2^256 áàéò ïàìÿòè ;)
Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722
... Èíîãäà äëÿ òîãî, ÷òîáû èçìåíèòü ñâîå âîñïðèÿòèå ìèðà,
... ëþäè ïûòàþòñÿ èçìåíèòü ñàì ìèð
--- GoldED+/W32 1.1.2
* Origin: Ñåòåâîé ôèëüòð íà 5 áàçàðîâ (2:5093/4.126)
— RU.COMPRESS
From : Leonid Broukhis 2:5020/400 11 Oct 01 15:08:15
To : EinWill
Subj : Re: DCT
From: leob@mailcom.com (Leonid Broukhis)
EinWill wrote:
>> Ïîäêèíüòå ññûëîê íà ìàòåìàòè÷åñêîå îïèñàíèå Subj. Ýòî äèñêðåòíîå
>> ïðåîáðàçîâàíèå êîñèíóñîâ (Discrete Cosinus Transform), åñëè ìíå íå
>íàâðàëè.
>Hå íàâðàëè. Òîëüêî, òóò ëèáî "ìàòåìàòè÷åñêîå îïèñàíèå", ëèáî "_äèñêðåòíîå_
>ïðåîáðàçîâàíèå" :-)
Hàâðàëè. Îíî Discrete Cosine Tranform.
Leo
--- ifmail v.2.15dev5
* Origin: leob@at-mailcom.dot-com (2:5020/400)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/4.126 11 Oct 01 15:21:16
To : Andrew Ezhguroff
Subj : Ãëóáèíà Huffman äåðåâà
* Originally in RU.COMPRESS
Ïðèÿòíîãî òåáå äíÿ è íåçàáûâàåìîé íî÷è, Andrew!
Thursday October 11 2001, Andrew Ezhguroff writes to andrey@neva-roentgen.com:
AE> 2. Ñæèìàåì 128 Kb ôàéë, â êîòîðîì áîëüøèíñòâî áàéòîâ - íóëè è åäèíèöû
AE> (ñ ðàâíîé âåðîÿòíîñòüþ), à êàæäûé áàéò ñ êîäîì >1 âñòðå÷àåòñÿ ðîâíî
AE> 1 ðàç.
AE> Õàôìàí ïîä áàéòû 0 è 1 îòâåäåò ïî 2 áèòà, à ïîä äðóãèå ñèìâîëû - ïî 9
AE> áèò.
åñëè ýòîò õàôìàí - óìíûé ìóæèê, òî îí íàéä¸ò êîä ïîêîðî÷å ;)
Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722
... Èíîãäà äëÿ òîãî, ÷òîáû èçìåíèòü ñâîå âîñïðèÿòèå ìèðà,
... ëþäè ïûòàþòñÿ èçìåíèòü ñàì ìèð
--- GoldED+/W32 1.1.2
* Origin: Ñåòåâîé ôèëüòð íà 5 áàçàðîâ (2:5093/4.126)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/4.126 11 Oct 01 15:25:09
To : EinWill" <andrey@neva-roentgen.com>
Subj : Ãëóáèíà Huffman äåðåâà
* Originally in RU.COMPRESS
Ïðèÿòíîãî òåáå äíÿ è íåçàáûâàåìîé íî÷è, EinWill"!
Thursday October 11 2001, EinWill" <andrey@neva-roentgen.com> Reply-To: "EinWil
l writes to Bulat Ziganshin:
>> ÏÎ ÎÏÐÅÄÅËÅHÈÞ àëãîðèüòì õàôìåíà äà¸ò îïòèìàëüíîå äåðåâî :))
Ea> Ýòî è åæó ïîíÿòíî. ÏÎ ÓÑËÎÂÈÞ ìîÿ ìîäèôèêàöèÿ ðàáîòàåò _íå ñ äåðåâîì_
Ea> (à ëèøü â ðÿäå ñëó÷àåâ ñ "ëó÷øåé ïîëîâèíîé" ýòîãî îïòèìàëüíîãî
Ea> äåðåâà).
Ea> Áîæå-æå ìîé, è ýòî âû ãîâîðèòå ìíå, àñïèðàíòó êàôåäðû Òåîðèè
Ea> Âåðîÿòíîñòåé? :-P
íó ÷òî ÿ ìîëãó ñêàçàòü. íàçîâèòå ìíå âàø èíñòèòóò, áóäåì èì äåòåé ïóãàòü
Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722
... Èíîãäà äëÿ òîãî, ÷òîáû èçìåíèòü ñâîå âîñïðèÿòèå ìèðà,
... ëþäè ïûòàþòñÿ èçìåíèòü ñàì ìèð
--- GoldED+/W32 1.1.2
* Origin: Ñåòåâîé ôèëüòð íà 5 áàçàðîâ (2:5093/4.126)
— RU.COMPRESS
From : EinWill 2:5020/400 11 Oct 01 16:36:32
To : Bulat Ziganshin
Subj : Re: Ãëóáèíà Huffman äåðåâà
From: "EinWill" <andrey@neva-roentgen.com>
Reply-To: "EinWill" <andrey@neva-roentgen.com>
Ìû ê Âàì, ïðîôåññîð "Bulat Ziganshin"
<Bulat.Ziganshin@p126.f4.n5093.z2.fidonet.org>, è âîò ïî êàêîìó äåëó:
> >> ÏÎ ÎÏÐÅÄÅËÅHÈÞ àëãîðèüòì õàôìåíà äà¸ò îïòèìàëüíîå äåðåâî :))
> Ea> Ýòî è åæó ïîíÿòíî. ÏÎ ÓÑËÎÂÈÞ ìîÿ ìîäèôèêàöèÿ ðàáîòàåò _íå ñ äåðåâîì_
> Ea> (à ëèøü â ðÿäå ñëó÷àåâ ñ "ëó÷øåé ïîëîâèíîé" ýòîãî îïòèìàëüíîãî
> Ea> äåðåâà).
> Ea> Áîæå-æå ìîé, è ýòî âû ãîâîðèòå ìíå, àñïèðàíòó êàôåäðû Òåîðèè
> Ea> Âåðîÿòíîñòåé? :-P
>
> íó ÷òî ÿ ìîëãó ñêàçàòü. íàçîâèòå ìíå âàø èíñòèòóò, áóäåì èì äåòåé ïóãàòü
Ìàò-Ìåõ ÑÏáÃÓ, åñëè òàê èíòåðåñíî. Òîëüêî ÷åãî äåòåé ïóãàòü-òî?
Òû æå íå ñêàçàë, ÷òî _êîäû_ Õàôôìàíà îïòèìàëüíûå _èç âñåõ ïðåôèêñíûõ_. Â
ñìûñëå, íå ñêàçàë ýòî ìíå, ýòîãî íå çíàþùåãî (à ÷åãî ìíå çíàòü, åñëè ÿ ïðî
ýòîãî Õàôôìàíà òîëüêî â÷åðà óñëûøàë? :-) ). Ïîòîìó èç òâîèõ ñëîâ îòíþäü íå
ñëåäîâàëà àáñóðäíîñòü èëè æå çàâåäîìàÿ íåâåðíîñòü ìîèõ.
ßñíåå âûðàæàòüñÿ íàäî, ãîñïîäà ãóðó :-P
֏,
EinWill
--- ifmail v.2.15dev5
* Origin: Fidolook Express 2.000 www.fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Alex 'Agent' Smith 2:464/34.74 11 Oct 01 22:43:14
To : Bulat Ziganshin
Subj : Ñóïåðñæàòèå
>< >< >< Wake up, Bulat. Ìåíòû îêðóæàþò! >< >< ><
Òèïà, Bulat Ziganshin -+> Alex 'agent' Smith âòèðàëè ïðî "Ñóïåðñæàòèå":
AS>> À ïîäðîáíåå: åñòü ôèëåñ, ãäå êðîìå ñèìâîëîâ öèôð è ïðîáåëîâ -
AS>> íè÷åãî íåò. Êàê áû åãî ñàìîñòîÿòåëüíî ñæàòü?
BZ> õàôôìåíîì
AS>> ÇÛ: Òû íà âîïðîñ "êàê ñäåëàòü?" íå õîòåë äàâàòü ñòàíäàðòíûé
AS>> îòâåò? ;))))
BZ> ÿ âåäü ñïåöèàëüíî ïîä÷åðêíóë - çäåñü, êàê è òàì, ÷åì ëó÷øå òû ñïîñîáåí
BZ> îïèñàòü ñâîþ ñèòóàöèþ, òåì áîëåå ïîëåçíûé îòâåò ïîëó÷èøü. ïîêà ÷òî òû
BZ> ïîëó÷èë îòâåò èñêëþ÷èòåëüíî äóðàöêèé, íàäî ñêàçàòü
Òû ïîíèìàåøü â ÷åì áàãà: ÿ äàæå íå â ñîñòîÿíèè îöåíèòü äóðàöêîñòü îòâåòà, ïîñêî
ëüêó ðàíüøå æàòèåì âîîáùå íå çàíèìàëñÿ. Âîò ïî÷åìó è ñïîñèë ìåñòíûé ôàê èëè ÷òî
-òî âðîäå ýòîãî.
Good bye, mister Ziganshin _
/_| _ _ _/
Smith, ( | (/ (- /) / Smith...
_/
... Îò÷åãî, îò÷åãî, îò÷åãî Winamp ïîåò? Îòòîãî, ÷òî êòî-òî ëþáèò ïðîãðàììèñòà!
--- À ó òâîåãî ÃîëÄåäà ñòîèò... ôèëüòðàöèÿ ìåññàã???
* Origin: Äàéòå íàïèòüñÿ âîäû âîñïèòàííèêó óïàâøåé Âèíäû... (2:464/34.74)
— RU.COMPRESS
From : IP Robot 2:5093/4.126 12 Oct 01 01:08:57
To : All
Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/
ftp://ftp.elf.stuba.sk/pub/pc/pack/bioarc19.zip
BioArc v1.9 - Archive manager optimized for text/office documents, executable a
nd MP3 files (1,595,749 bytes)
ftp://ftp.elf.stuba.sk/pub/pc/pack/nbz20.exe
Brilliant Zip v2.01 - Compression tool for Win32 (1,291,304 bytes)
ftp://ftp.elf.stuba.sk/pub/pc/pack/rarisimo.zip
Rarissimo v1.0 - Companion tool for WinRAR that preserve NTFS alternate streams
(2,705,491 bytes)
--- PktMake.pl
* Origin: PktMake.pl (2:5093/4.126)
— RU.COMPRESS
From : Andrew Ezhguroff 2:5020/400 12 Oct 01 02:43:42
To : Bulat Ziganshin
Subj : Re: Ãëóáèíà Huffman äåðåâà
From: "Andrew Ezhguroff" <eandr@com2com.ru>
Ïðèâåò! "Bulat Ziganshin" <Bulat.Ziganshin@p126.f4.n5093.z2.fidonet.org>
ñîîáùèë(à) íàì:
> AE> Õàôìàí ïîä áàéòû 0 è 1 îòâåäåò ïî 2 áèòà, à ïîä äðóãèå ñèìâîëû - ïî 9
> AE> áèò.
> åñëè ýòîò õàôìàí - óìíûé ìóæèê, òî îí íàéä¸ò êîä ïîêîðî÷å ;)
Ñîãëàñåí, îøèáñÿ. Hî ñàì ïðèíöèï îïðîâåðæåíèÿ èäåè EinWill'à âåðåí? :-)
Ñ óâàæåíèåì, Àíäðåé.
--- ifmail v.2.15dev5
* Origin: COMSTAR Telecommunications (2:5020/400)
— RU.COMPRESS
From : Sasha Breger 2:5066/70.64 12 Oct 01 20:09:06
To : All
Subj : Ñæàòèå ñòðîê (äî 250 ñèìâîëîâ)
Ïðèâåò, All.
×åì/êàê ëó÷øå âñåãî ñæèìàòü íå î÷åíü áîëüøèå ñòðîêè? ×åì ìîæíî ïîëó÷èòü ìàêñèìà
ëüíîå ñæàòèå (ñ ó÷¸òîì çàãîëîâêîâ)?
Sasha, <no@e-mail.smth>
--- ÃîëÄåä+1.1.4.7
* Origin: Äîëã íîãèøîì ïëàòÿò (2:5066/70.64)
— RU.COMPRESS
From : IP Robot 2:5093/4.126 13 Oct 01 01:13:19
To : All
Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/
ftp://ftp.elf.stuba.sk/pub/pc/pack/wrar290d.exe
RAR v2.90 for Windows (32-bit) - German Edition (698,428 bytes)
ftp://ftp.elf.stuba.sk/pub/pc/pack/wrar29tc.exe
RAR v2.90 for Windows (32-bit) - Traditional Chinese Edition (760,508 bytes)
--- PktMake.pl
* Origin: PktMake.pl (2:5093/4.126)
— RU.COMPRESS
From : Andrew Gorbunow 2:5022/81.7 14 Oct 01 17:19:05
To : All
Subj : HA32
Hy çäpàâñòâyé, All!
Èìååòñÿ ëè â ïpèpîäå ñàáæåâûé àpõèâàòîp?
Åñëè äà, òî ãäå åãî ìîæíî âçÿòü, ypë?
Ñ yâàæåíèåì, Andy E-mail: AgSpider@Mail.ru
W e b: http://A-W-L.narod.ru
--- GOLDED 1.1.5 -·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-
* Origin: ::: Night Kingdom ::: (2:5022/81.7)
— RU.COMPRESS
From : Serg Tikhomirov 2:5020/122.166 14 Oct 01 21:17:06
To : Maxim Smirnov
Subj : Ñóïåpñæàòèå
Çäpàâñòâyé, Maxim!
09:48 of 11 Oct Maxim Smirnov wrote in a message to Bulat Ziganshin:
BZ> ÿ âåäü ñïåöèàëüíî ïîä÷åpêíóë - çäåñü, êàê è òàì, ÷åì ëó÷øå òû ñïîñîáåí
BZ> îïèñàòü ñâîþ ñèòóàöèþ, òåì áîëåå ïîëåçíûé îòâåò ïîëó÷èøü. ïîêà ÷òî òû
BZ> ïîëó÷èë îòâåò èñêëþ÷èòåëüíî äópàöêèé, íàäî ñêàçàòü
MS> Ïpåäëàãàþ âíåñòè ýòî â ru.compress FAQ (âpîäå áûë òàêîé?).
MS> Hàïèñàòü áîëüøèìè friendly áóêâàìè.
Áóäåò ñäåëàíî ;-).
Âñåãî íàèëó÷øåãî!
Jee
---
* Origin: Âåñü ìèp - áàíêåò, à ëþäè â í¸ì - îáæîpû. (2:5020/122.166)
— RU.COMPRESS
From : Serg Tikhomirov 2:5020/122.166 14 Oct 01 21:20:07
To : Bulat Ziganshin
Subj : Ñóïåpñæàòèå
Çäpàâñòâyé, Bulat!
11:01 of 11 Oct Bulat Ziganshin wrote in a message to Maxim Smirnov:
BZ> Thursday October 11 2001, Maxim Smirnov writes to Bulat Ziganshin:
BZ>> ÿ âåäü ñïåöèàëüíî ïîä÷åpêíóë - çäåñü, êàê è òàì, ÷åì ëó÷øå òû
BZ>> ñïîñîáåí îïèñàòü ñâîþ ñèòóàöèþ, òåì áîëåå ïîëåçíûé îòâåò
BZ>> ïîëó÷èøü. ïîêà ÷òî òû ïîëó÷èë îòâåò èñêëþ÷èòåëüíî äópàöêèé, íàäî
BZ>> ñêàçàòü
MS> Ïpåäëàãàþ âíåñòè ýòî â ru.compress FAQ (âpîäå áûë òàêîé?).
MS> Hàïèñàòü áîëüøèìè friendly áóêâàìè.
BZ> íå ïîìîæåò, â póïèêàï òàêîå óæå ïpîáîâàëè, è íåîäíîêpàòíî.
Àäíàçíà÷íà â FAQ! Åñëè íå äîõîäèò ÷åpåç ãîëîâó - áóäåì èñêàòü äpóãèå... ãì..
. ïóòè ;).
BZ> äóìàòü íèêîìó íåîõîòà, âñå íîpîâÿò íà ãîòîâåíüêîå, íå ïîíèìàÿ, ÷òî
BZ> ýòîò êàê pàç òîò ñëó÷àé, êîãäà, ñýêîíîìèâ ïîë÷àñà, ïpèä¸òñÿ
BZ> ïîòåpÿòü ìåñÿöû
È âåäü, ÷òî õàpàêòåpíî, è òàì, è òóò èñòîpèÿ ïîâòîpÿåòñÿ...
Âñåãî íàèëó÷øåãî!
Jee
---
* Origin: Âåñü ìèp - áàíêåò, à ëþäè â í¸ì - îáæîpû. (2:5020/122.166)
— RU.COMPRESS
From : Alexey Rojnov 2:5020/689.50 15 Oct 01 00:27:36
To : All
Subj : RANGECODER
Hello All!
Ëþäè, à ÷òî åñòü ñàáæ? Ýòî ÷òî, íîâûé òèï àðèôìåòè÷. êîäèðîâàíèÿ?
bye.
--- alexa2r@mail.ru, alexa2r.chat.ru
* Origin: -=< KABALAH >=- (2:5020/689.50)
— RU.COMPRESS
From : EinWill 2:5020/400 15 Oct 01 09:57:48
To : Bulat Ziganshin
Subj : Re: Ãëóáèíà Huffman äåðåâà
From: "EinWill" <andrey@neva-roentgen.com>
Reply-To: "EinWill" <andrey@neva-roentgen.com>
Ìû ê Âàì, ïðîôåññîð "Bulat Ziganshin"
<Bulat.Ziganshin@p126.f4.n5093.z2.fidonet.org>, è âîò ïî êàêîìó äåëó:
> >> ÏÎ ÎÏÐÅÄÅËÅHÈÞ àëãîðèüòì õàôìåíà äà¸ò îïòèìàëüíîå äåðåâî :))
> Ea> Ýòî è åæó ïîíÿòíî. ÏÎ ÓÑËÎÂÈÞ ìîÿ ìîäèôèêàöèÿ ðàáîòàåò _íå ñ äåðåâîì_
> Ea> (à ëèøü â ðÿäå ñëó÷àåâ ñ "ëó÷øåé ïîëîâèíîé" ýòîãî îïòèìàëüíîãî
> Ea> äåðåâà).
Ãëóïîñòü ñìîðîçèë. :-(
Ïðèçíàþ... Håâåñòü ñ ÷åãî ïîêàçàëîñü, ÷òî ìîè êîäû íå ïðåäñòàâèìû â âèäå
âåòâëåíèÿ äåðåâà :-( ). Hó ñ êåì ïðèñòóïîâ ãëóïîñòåé íå áûâàåò? :)
Ïðîùåíèÿ ïðîñèì-ñ. :-)
֏
--- ifmail v.2.15dev5
* Origin: Fidolook Express 2.000 www.fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : IP Robot 2:5093/4.126 16 Oct 01 01:07:43
To : All
Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/
ftp://ftp.elf.stuba.sk/pub/pc/pack/pcr157d.zip
PNGCRUSH v1.5.7 - PNG files packer (executable) (148,880 bytes)
ftp://ftp.elf.stuba.sk/pub/pc/pack/pcr157s.zip
PNGCRUSH v1.5.7 - PNG files packer (source code) (333,975 bytes)
ftp://ftp.elf.stuba.sk/pub/pc/pack/qzip201.exe
QuickZip v2.01 - Archiver for Win32 (2,836,122 bytes)
--- PktMake.pl
* Origin: PktMake.pl (2:5093/4.126)
— RU.COMPRESS
From : IP Robot 2:5093/4.126 17 Oct 01 01:05:01
To : All
Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/
ftp://ftp.elf.stuba.sk/pub/pc/pack/7z230b6.exe
7-ZIP Archiver v2.30 beta 6 - Command line file archiver (716,560 bytes)
--- PktMake.pl
* Origin: PktMake.pl (2:5093/4.126)
— RU.COMPRESS
From : EinWill 2:5020/400 17 Oct 01 11:35:25
To : All
Subj : È åùå ðàç, Huffman
From: "EinWill" <andrey@neva-roentgen.com>
Reply-To: "EinWill" <andrey@neva-roentgen.com>
Ïðèâåòñòâóþ âñåõ!
Òóò â Ru.Algorithm ðàçãîðåëàñü äèñêóññèÿ, îòíîñÿùàÿñÿ ê ñæàòèþ àëãîðèòìîì
Huffman'à.
Âîïðîñ òàêîé: êàêèì îáðàçîì ìîæíî îïòèìàëüíåå âñåãî õðàíèòü äåðåâî
Huffman'à? Hó, èëè òàáëèöó êîäîâ Huffman'à (ïî êîòîðîìó, ðàçóìååòñÿ, äåðåâî
âîñòàíàëâèâàåòñÿ).
Hàèáîëåå óäàíûé ñïîñîá ïðåäëîæèë "Dmitriy Guzenko"
<gudmal@viii.ntu-kpi.kiev.ua> åìó ñëîâî:
===
ß õðàíþ äåðåâî òàê:
Çàïèñûâàþ ëèñòüÿ â ïîðÿäêå îáõîäà.
Äëÿ êàæäîé âåðøèíû â ïîðÿäêå îáõîäà çàïèñûâàåì áèò-ïðèçíàê - èìååò âåðøèíà
îáîèõ äåòåé èëè íå îäíîãî, âñåãî 510 áèò.
Èòîãî ïîëó÷àåì 320 áàéò áåç 2-õ áèò äëÿ ëþáîãî äåðåâà - äàæå åñëè
ìàêñèìàëüíàÿ
äëèíà áèòîâîé ïîñëåäîâàòåëüíîñòè ðàâíà 255
===
À åñòü ëè ñïîñîáû ëó÷øå?
--
.... C Óâàæåíèåì, EinWill
--- ifmail v.2.15dev5
* Origin: Fidolook Express 2.000 www.fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Sergey Kovalev 2:5020/400 17 Oct 01 13:27:53
To : EinWill
Subj : Re: È åùå ðàç, Huffman
From: "Sergey Kovalev" <s-kovalev@nwgsm.ru>
Reply-To: "Sergey Kovalev" <s-kovalev@nwgsm.ru>
"EinWill" <andrey@neva-roentgen.com> wrote in message
news:Ntaz7.146$kY.167043@news.rt.ru...
> Ïðèâåòñòâóþ âñåõ!
>
> Òóò â Ru.Algorithm ðàçãîðåëàñü äèñêóññèÿ, îòíîñÿùàÿñÿ ê ñæàòèþ
àëãîðèòìîì
> Huffman'à.
> Âîïðîñ òàêîé: êàêèì îáðàçîì ìîæíî îïòèìàëüíåå âñåãî õðàíèòü äåðåâî
> Huffman'à? Hó, èëè òàáëèöó êîäîâ Huffman'à (ïî êîòîðîìó, ðàçóìååòñÿ,
äåðåâî
> âîñòàíàëâèâàåòñÿ).
> Hàèáîëåå óäàíûé ñïîñîá ïðåäëîæèë "Dmitriy Guzenko"
Òóò åñòü ïðîñòîé ïðèåì. Òû ôîðìèðóåøü ìàññèâ ÷àñòîò,
ïî êîòîðîìó ïîòîì ñòðîèøü êîä Õ.
Äàëåå ïîëó÷àåøü ìàññèâ äëèí ñëîâ êîäà Õ.
Çäåñü âûïîëíÿåøü ñëåäóþùåå æóëüíè÷åñòâî.
Hà ñàìîì äåëå ñóùåñòâóþåò ìíîãî äåðåâüåâ
ñ çàäàííûì íàáîðîì äëèí,
è ïóáëèêå ñîâåðøåííî âñå ðàâíî, êàêîå äåðåâî èñïîëüçîâàòü.
Ãëàâíîå, ÷òîáû èñïîëüçîâàòü ïðè äåêîäèðîâàíèè
òî æå äåðåâî, ÷òî è ïðè êîäèðîâàíèè.
Èòàê, ïîñëå ïîëó÷åíèÿ íàáîðà äëèí òû ñòðîèøü
äåðåâî çàíîâî ïî îïðåäåëåííîìó àëãîðèòìó.
(Ýòî ëåãêî ïðèäóìàòü - ÿ â äåòñòâå ýòèì çàíèìàëñÿ ;-)
Ïî òàêîìó æå àëãîðèòìó äåêîäåð áóäåò ñòðîèòü äåðåâî äëÿ äåêîäèðîâàíèÿ.
Òàêèì îáðàçîì, äîñòàòî÷íî îòäàòü äåêîäåðó ìàññèâ äëèí.
SK
SPb,2001
--- ifmail v.2.15dev5
* Origin: HOME (2:5020/400)
— RU.COMPRESS
From : EinWill 2:5020/400 17 Oct 01 14:34:33
To : Sergey Kovalev
Subj : Re: È åùå ðàç, Huffman
From: "EinWill" <andrey@neva-roentgen.com>
Reply-To: "EinWill" <andrey@neva-roentgen.com>
Ìû ê Âàì, ïðîôåññîð "Sergey Kovalev" <s-kovalev@nwgsm.ru>, è âîò ïî êàêîìó
äåëó:
> > Âîïðîñ òàêîé: êàêèì îáðàçîì ìîæíî îïòèìàëüíåå âñåãî õðàíèòü äåðåâî
> > Huffman'à?
[Skiped]
> Hà ñàìîì äåëå ñóùåñòâóþåò ìíîãî äåðåâüåâ
> ñ çàäàííûì íàáîðîì äëèí,
> è ïóáëèêå ñîâåðøåííî âñå ðàâíî, êàêîå äåðåâî èñïîëüçîâàòü.
> Ãëàâíîå, ÷òîáû èñïîëüçîâàòü ïðè äåêîäèðîâàíèè
> òî æå äåðåâî, ÷òî è ïðè êîäèðîâàíèè.
[Skiped]
> (Ýòî ëåãêî ïðèäóìàòü - ÿ â äåòñòâå ýòèì çàíèìàëñÿ ;-)
> Òàêèì îáðàçîì, äîñòàòî÷íî îòäàòü äåêîäåðó ìàññèâ äëèí.
Òîëüêî, òîãäà óæ, íå òîëüêî ìàññèâ äëèí, íî è ïåðå÷åíü ñèìâîëîâ â
îïðåäåëåííîì ïîðÿäêå (a'la ëèñòüÿ äåðåâà). Èëè âñå åùå õèòðåå? Åñëè åùå
õèòðåå, òî, ïîæàëóéñòà, íå ìîã áû òû âñïîíèòü äåòñòâî è ïîäåëèòüñÿ èäååé,
êàê êîäèðîâàòü òîëüêî ìàññèâîì äëèí?
:-)
Ñ óâàæåíèåì,
EinWill
--- ifmail v.2.15dev5
* Origin: Fidolook Express 2.000 www.fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Sergey Kovalev 2:5020/400 17 Oct 01 17:07:34
To : EinWill
Subj : Re: È åùå ðàç, Huffman
From: "Sergey Kovalev" <s-kovalev@nwgsm.ru>
Reply-To: "Sergey Kovalev" <s-kovalev@nwgsm.ru>
"EinWill" <andrey@neva-roentgen.com> wrote in message
news:S5dz7.165$kY.179780@news.rt.ru...
[]
> Òîëüêî, òîãäà óæ, íå òîëüêî ìàññèâ äëèí, íî è ïåðå÷åíü ñèìâîëîâ â
> îïðåäåëåííîì ïîðÿäêå (a'la ëèñòüÿ äåðåâà). Èëè âñå åùå õèòðåå? Åñëè åùå
> õèòðåå, òî, ïîæàëóéñòà, íå ìîã áû òû âñïîíèòü äåòñòâî è ïîäåëèòüñÿ èäååé,
> êàê êîäèðîâàòü òîëüêî ìàññèâîì äëèí?
> :-)
Äà íåò, âñå êàê ðàç î÷åíü ïðîñòî.
Ñîîòâåòñòâèå ìåæäó êîäèðóåìûìè ñèìâîëàìè è êîäîâûìè ñëîâàìè êîäà X
îñòàåòñÿ _òî_æå_ñàìîå_. Îíî çàäàþòñÿ ïîðÿäêîì
ñëåäîâàíèÿ äëèí â ìàññèâå äëèí. Âåäü äëèíû -òî ïðèâÿçàíû
ê êîíêðåòíûì ñèìâîëàì, ïîñêîëüêó áûëè ïîëó÷åíû ïî èõ ÷àñòîòàì.
Ãðóáî ãîâîðÿ, èíäåêñ ìàññèâà åñòü âõîäíîé ñèìâîë, êîòîðûé
áóäåò êîäèðîâàòüñÿ ñëîâîì, èìåþùåì äëèíó, ñòîÿùóþ â ýòîì ýëåìåíòå
ìàññèâà. Óõ.. ;)
Ïðîñòî êîäîâûå ñëîâà ìîãóò áûòü äðóãèìè. Hî òîé æå äëèíû.
È ýòî òîæå äåðåâî. ( Åñëè , êîíå÷íî, ýòîò íàáîð äëèí íå ïîïåðåê Êðàôòà ;))
È, ãëàâíîå, ÷òî ýòî òî÷íî òàêîå äåðåâî, êîòîðîå ïîñòðîèò
äåêîäåð. Ïî ìàññèâó äëèí. Áëèí! ;)
Æóëüíè÷åñòâî ñîñòîèò â òîì, ÷òî ýòî ñïîñîá îïèñàíèÿ íå ïðîèçâîëüíîãî
äåðåâà, à îäíîãî ïðåäñòàâèòåëÿ èç ìíîæåñòâà â íåêîòîðîì
ñìûñëå ýêâèâàëåíòíûõ äåðåâüåâ,
èìåþùèõ òðåáóåìûé (îäèíàêîâûé) íàáîð äëèí.
Hî, ïîñêîëüêó â äàííîì ñëó÷àå âàæåí èìåííî íàáîð äëèí,
à íå êîíêðåòíîå äåðåâî,
òî ñ òî÷êè çðåíèÿ ñæàòèÿ èíôîðìàöèè çäåñü âñå ÷åñòíî.
SK
SPB,2001
--- ifmail v.2.15dev5
* Origin: HOME (2:5020/400)
— RU.COMPRESS
From : EinWill 2:5020/400 17 Oct 01 18:27:01
To : Sergey Kovalev
Subj : Re: È åùå ðàç, Huffman
From: "EinWill" <andrey@neva-roentgen.com>
Reply-To: "EinWill" <andrey@neva-roentgen.com>
Ìû ê Âàì, ïðîôåññîð "Sergey Kovalev" <s-kovalev@nwgsm.ru>, è âîò ïî êàêîìó
äåëó:
> > Òîëüêî, òîãäà óæ, íå òîëüêî ìàññèâ äëèí, íî è ïåðå÷åíü ñèìâîëîâ â
> > îïðåäåëåííîì ïîðÿäêå (a'la ëèñòüÿ äåðåâà). Èëè âñå åùå õèòðåå? Åñëè åùå
> > õèòðåå, òî, ïîæàëóéñòà, íå ìîã áû òû âñïîíèòü äåòñòâî è ïîäåëèòüñÿ
èäååé,
> > êàê êîäèðîâàòü òîëüêî ìàññèâîì äëèí?
> > :-)
> Äà íåò, âñå êàê ðàç î÷åíü ïðîñòî.
Ïðî÷èòàâ òâîè ñëåäóþùèå ñëîâà ÿ â ýòîì çàñîìíåâàëñÿ :-)
[Skiped]
> Æóëüíè÷åñòâî ñîñòîèò â òîì, ÷òî ýòî ñïîñîá îïèñàíèÿ íå ïðîèçâîëüíîãî
> äåðåâà, à îäíîãî ïðåäñòàâèòåëÿ èç ìíîæåñòâà â íåêîòîðîì
> ñìûñëå ýêâèâàëåíòíûõ äåðåâüåâ,
> èìåþùèõ òðåáóåìûé (îäèíàêîâûé) íàáîð äëèí.
Âîò ýòî ÿ ïîíÿë. Hî ìíå íàäî ïîñòðîèòü íå òîëüêî êàðêàñ äåðåâà, íî åùå è
ñîõðàíèòü çíà÷åíèÿ åãî ëèñòüåâ (êîòîðûå õðàíÿò ñèìâîëû àëôàâèòà). Êàê ïî
ìàññèâó äëèí ïîñòðîèòü îäíó èç âîçìîæíûõ ñòðóêòóð äåðåâà -- ýòî ÿ ïîíèìàþ.
Hî çíà÷åíèÿ ëèñòüåâ êóäà äåâàòü??? Èëè òû õî÷åøü ñêàçàòü, ÷òî ìîæíî
ïîñòðîèòü òàêîé ïðåäñòàâèòåëü, â êîòîðîì, íàïðèìåð, ëåâîñòîðîííèé îáõîä
ëèñòüåâ áóäåò äîâàòü âñåãäà àëôàâèòíûé ïîðÿäîê???? (òî åñòü ñèìâîëû #0, #1,
#2 èò.ä.)
Åñëè äà -- òî îáúÿñíè êàê. Ýòîãî ÿ íå ïîíèìàþ. À åñëè íåò, òî òîãäà ÿ
äîëæåí åùå è ñîõðàíèòü âñå ñèìâîëû (íåêîòîðûé èõ ïîðÿäîê).
Ãäå ÿ íå ïðàâ? :-)
EinWill
--- ifmail v.2.15dev5
* Origin: Fidolook Express 2.000 www.fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Sergey Tchirco 2:5020/400 17 Oct 01 19:31:00
To : EinWill
Subj : Hà: È åùå ðàç, Huffman
From: "Sergey Tchirco" <tchsv@nbrt.kazan.su>
"EinWill" <andrey@neva-roentgen.com> ñîîáùèë/ñîîáùèëà â íîâîñòÿõ ñëåäóþùåå:
news:zvgz7.184$kY.196615@news.rt.ru...
Ïðèâåòñòâóþ!
Ýòî íè÷åãî ÷òî ÿ âìåøèâàþñü?
> > Æóëüíè÷åñòâî ñîñòîèò â òîì, ÷òî ýòî ñïîñîá îïèñàíèÿ íå ïðîèçâîëüíîãî
> > äåðåâà, à îäíîãî ïðåäñòàâèòåëÿ èç ìíîæåñòâà â íåêîòîðîì
> > ñìûñëå ýêâèâàëåíòíûõ äåðåâüåâ,
> > èìåþùèõ òðåáóåìûé (îäèíàêîâûé) íàáîð äëèí.
> Âîò ýòî ÿ ïîíÿë. Hî ìíå íàäî ïîñòðîèòü íå òîëüêî êàðêàñ äåðåâà, íî åùå è
> ñîõðàíèòü çíà÷åíèÿ åãî ëèñòüåâ (êîòîðûå õðàíÿò ñèìâîëû àëôàâèòà). Êàê ïî
> ìàññèâó äëèí ïîñòðîèòü îäíó èç âîçìîæíûõ ñòðóêòóð äåðåâà -- ýòî ÿ ïîíèìàþ.
> Hî çíà÷åíèÿ ëèñòüåâ êóäà äåâàòü??? Èëè òû õî÷åøü ñêàçàòü, ÷òî ìîæíî
> ïîñòðîèòü òàêîé ïðåäñòàâèòåëü, â êîòîðîì, íàïðèìåð, ëåâîñòîðîííèé îáõîä
> ëèñòüåâ áóäåò äîâàòü âñåãäà àëôàâèòíûé ïîðÿäîê???? (òî åñòü ñèìâîëû #0,
#1,
> #2 èò.ä.)
> Åñëè äà -- òî îáúÿñíè êàê. Ýòîãî ÿ íå ïîíèìàþ. À åñëè íåò, òî òîãäà ÿ
> äîëæåí åùå è ñîõðàíèòü âñå ñèìâîëû (íåêîòîðûé èõ ïîðÿäîê).
Âñå î÷åíü ïðîñòî çàïèñûâåì äëèíó ê ñèìâîëó ñ êîäîì 0, çàòåì ñ êîäîì 1, çàòåì
2 è ò.ä.
Ýòà çàïèñü HÅ çàäàåò îäíîçíà÷íîãî âèäà äåðåâà, íî çàäàåò ìíîæåñòâî äåðåâüåâ
ñ ÎÄÈHÀÊÎÂÎÉ ýôôåêòèâíîñòüþ ñæàòèÿ, êóäà â õîäèò è Õàôôìàíîâñêîå äåðåâî,
èìåþùåå ìàêñèìàëüíóþ ýôôåêòèâíîñòü, ñëåäîâàòåëüíî ëþáîå èç äåðåâüåâ ýòîãî
ìíîæåñòâà ìàêñèìàëüíî ýôôåêòèâíî. Òåïåðü çàäà÷à ïîñòðîèòü îäíî èç äåðåâüåâ,
âõîäÿùåå â ýòî ìíîæåñòâî è åñëè ó òåáÿ â êîäåðå è äåêîäåðå èñïîëüçóåòñÿ
îäèíàêîâûé àëãîðèòì ïîñòðîåíèÿ äåðåâà, òî ïîëó÷àåì îäèíàêîâûå äåðåâüÿ è âîò
èìè òî è ïîëüçûåìñÿ.
Hàäåþñü, ÿ ïîíÿòíî îáúÿñíèë
Ñ óâàæåíèåì, Ñåðãåé
--- ifmail v.2.15dev5
* Origin: IFC BanCorp (2:5020/400)
— RU.COMPRESS
From : EinWill 2:5020/400 18 Oct 01 09:50:18
To : Sergey Tchirco
Subj : Re: È åùå ðàç, Huffman
From: "EinWill" <andrey@neva-roentgen.com>
Reply-To: "EinWill" <andrey@neva-roentgen.com>
Ìû ê Âàì, ïðîôåññîð "Sergey Tchirco" <tchsv@nbrt.kazan.su>, è âîò ïî êàêîìó
äåëó:
> Ýòî íè÷åãî ÷òî ÿ âìåøèâàþñü?
Ñâåæèå èäåì âñåãäà êñòàòè :-)
> Âñå î÷åíü ïðîñòî çàïèñûâåì äëèíó ê ñèìâîëó ñ êîäîì 0, çàòåì ñ êîäîì 1,
çàòåì
> 2 è ò.ä.
> Ýòà çàïèñü HÅ çàäàåò îäíîçíà÷íîãî âèäà äåðåâà, íî çàäàåò ìíîæåñòâî
äåðåâüåâ
> ñ ÎÄÈHÀÊÎÂÎÉ ýôôåêòèâíîñòüþ ñæàòèÿ, êóäà â õîäèò è Õàôôìàíîâñêîå äåðåâî,
> èìåþùåå ìàêñèìàëüíóþ ýôôåêòèâíîñòü, ñëåäîâàòåëüíî ëþáîå èç äåðåâüåâ ýòîãî
> ìíîæåñòâà ìàêñèìàëüíî ýôôåêòèâíî. Òåïåðü çàäà÷à ïîñòðîèòü îäíî èç
äåðåâüåâ,
> âõîäÿùåå â ýòî ìíîæåñòâî è åñëè ó òåáÿ â êîäåðå è äåêîäåðå èñïîëüçóåòñÿ
> îäèíàêîâûé àëãîðèòì ïîñòðîåíèÿ äåðåâà, òî ïîëó÷àåì îäèíàêîâûå äåðåâüÿ è
âîò
> èìè òî è ïîëüçûåìñÿ.
Îõ. Ýòî ÿ ïîíÿë. ×åñòíîå ñëîâî. Òîëüêî ÿ íå ìîãó ïðèäóìàòü àëãîðèòì,
ïîñòðîåíèÿ òàêîãî äåðåâà, áåç èñïîëüçîâàíèÿ äîïîëíèòåëüíîé èíôîðìàöèè,
êîòîðóþ íàäî ïåðåäàâàòü äåêîäåðó (òàêîâîé èíôîðìàöèåé ÿâëÿåòñÿ, íàïðèìåð,
ïåðå÷åíü ñèìâîëîâ â ëåâîñòîðîííåì îáõîäå äåðåâà). Âîò.
EinWill.
--- ifmail v.2.15dev5
* Origin: Fidolook Express 2.000 www.fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Sergey Tchirco 2:5020/400 18 Oct 01 11:21:28
To : EinWill
Subj : Hà: È åùå ðàç, Huffman
From: "Sergey Tchirco" <tchsv@nbrt.kazan.su>
"EinWill" <andrey@neva-roentgen.com> ñîîáùèë/ñîîáùèëà â íîâîñòÿõ ñëåäóþùåå:
news:j1uz7.239$kY.261536@news.rt.ru...
>
> Ìû ê Âàì, ïðîôåññîð "Sergey Tchirco" <tchsv@nbrt.kazan.su>, è âîò ïî
êàêîìó
> äåëó:
[skip]
> Îõ. Ýòî ÿ ïîíÿë. ×åñòíîå ñëîâî. Òîëüêî ÿ íå ìîãó ïðèäóìàòü àëãîðèòì,
> ïîñòðîåíèÿ òàêîãî äåðåâà, áåç èñïîëüçîâàíèÿ äîïîëíèòåëüíîé èíôîðìàöèè,
> êîòîðóþ íàäî ïåðåäàâàòü äåêîäåðó (òàêîâîé èíôîðìàöèåé ÿâëÿåòñÿ, íàïðèìåð,
> ïåðå÷åíü ñèìâîëîâ â ëåâîñòîðîííåì îáõîäå äåðåâà). Âîò.
Õì. Hó òóò âîîáùå ýëåìåíòàðíî. Hàïðèìåð Huffman íà îáîðîò :)
Âûáèðàåì ýëåìåíòû ñ íàèáîëüøåé äëèíîé èõ èëè 1 - òîãäà ýòî åäèíñòâåííûé
êîðåíü, èëè ÷åòíîå ÷èñëî. Îáúåäèíÿåì èõ ïîïàðíî ãëàâíîå êàêîé èç íèõ ëåâûé
êàêîé ïðàâûé, ýòî âñå ðàâíî, íî äîëæíî ðåøàòüñÿ îäèíàêîâî è â . Ïîëó÷àåì
óçëû ñ äëèíîé íà 1 ìåíüøå è òàê ïîêà íå îñòàíåòñÿ îäèí óçåë. Äåðåâî ãîòîâî.
Êñòàòè, â äîãîíêó: ñàìè äëèíû, ìîæíî òîæå ïîæàòü õàôôìàíîì, òîëüêî èñïîëüçóÿ
ñòàòè÷åñêîå äåðåâî, à åãî ïîñòðîèòü íà îñíîâå êàêîé-íèáóäü áîëüøîé
ñòàòèñòèêè è çàøèòü åíêîäåð è äåêîäåð
>
> EinWill.
Ñ óâàæåíèåì, Ñåðãåé
--- ifmail v.2.15dev5
* Origin: IFC BanCorp (2:5020/400)
— RU.COMPRESS
From : EinWill 2:5020/400 18 Oct 01 16:51:13
To : Sergey Tchirco
Subj : Re: È åùå ðàç, Huffman
From: "EinWill" <andrey@neva-roentgen.com>
Reply-To: "EinWill" <andrey@neva-roentgen.com>
Ìû ê Âàì, ïðîôåññîð "Sergey Tchirco" <tchsv@nbrt.kazan.su>, è âîò ïî êàêîìó
äåëó:
> > Îõ. Ýòî ÿ ïîíÿë. ×åñòíîå ñëîâî. Òîëüêî ÿ íå ìîãó ïðèäóìàòü àëãîðèòì,
> > ïîñòðîåíèÿ òàêîãî äåðåâà, áåç èñïîëüçîâàíèÿ äîïîëíèòåëüíîé èíôîðìàöèè,
> Õì. Hó òóò âîîáùå ýëåìåíòàðíî. Hàïðèìåð Huffman íà îáîðîò :)
Òû íå óìíè÷àé, òû ïàëüöåì ïîêàæè :-)
Âîò ñìîòðè, òàêîå äåðåâî:
À Á Ã Ä Â
5 10 11 14 40
\ / \ / /
15 25 /
\ / /
40 /
\ /
80
Ìàññèâ âõîæäåíèé ñèìâîëîâ -- [1,0,4]
Òû óòâåðæäàåøü, ÷òî ìîæåøü ïîñòðîèòü ýêâèâàëåòíîå äåðåâî, òîëüêî ïî ýòîìó
ìàññèâó. ÊÀÊ? Âåäü â ýêâèâàëåòíòîì äåðåâå ñèìâîë B âñåãäà äîëæåí èìåòü
åäèíè÷íóþ äëèíó. Òàêèì îáðàçîì, òû _îáÿçàí_ ïåðåäàòü äåêîäåðó, ÷òî èäíè÷íóþ
äëèíó èìååò èìåííî ñèìâîë Â. Ïîýòîìó òû îáÿçàí åãî ïåðåäàòü. Åñëè áû äåðåâî
áûëî áîëåå âåòñâèñòûì, òî èç àíàëîãè÷íûõ ñîîáðàæåíèé òû äîëæåí áûë áû
âêëþ÷èòü è ñèìâîëû, ñîîòâåòñòâóþùèå ëèñòüÿì êîòîðûå ðàñïîëîæåííû íà ðàçíîé
ãëóáèíå äåðåâà. Hå âêëþ÷àòü â ïåðå÷åíü òû ìîæåøü òîëüêî ñèìâîëû îäíîãî
(íàïðèìåð, ïîñëåäíåãî) óðîâíÿ -- èõ ìîæíî âîñòàíîâèòü çíàÿ âåñü àëôàâèò. Â
ïðèìåðå, òû ìîæåøü íå ïåðåäàâàòü ñèìâîëû òðåòüåãî óðîâíÿ - ÀÁÃÄ.
Òàêèì îáðàçîì, òû îáÿçàí ïîìèìî ìàññèâà [1,0,4] ïåðåäàòü åùå è
äîï.èíôîðìàöèþ -- ñèìâîë B.
Ãäå ÿ íå ïðàâ?
EinWill.
--- ifmail v.2.15dev5
* Origin: Fidolook Express 2.000 www.fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Sergey Tchirco 2:5020/400 18 Oct 01 17:28:30
To : EinWill
Subj : Hà: È åùå ðàç, Huffman
From: "Sergey Tchirco" <tchsv@nbrt.kazan.su>
"EinWill" <andrey@neva-roentgen.com> ñîîáùèë/ñîîáùèëà â íîâîñòÿõ ñëåäóþùåå:
news:xbAz7.286$kY.290230@news.rt.ru...
>
> > > Îõ. Ýòî ÿ ïîíÿë. ×åñòíîå ñëîâî. Òîëüêî ÿ íå ìîãó ïðèäóìàòü àëãîðèòì,
> > > ïîñòðîåíèÿ òàêîãî äåðåâà, áåç èñïîëüçîâàíèÿ äîïîëíèòåëüíîé èíôîðìàöèè,
>
> > Õì. Hó òóò âîîáùå ýëåìåíòàðíî. Hàïðèìåð Huffman íà îáîðîò :)
> Òû íå óìíè÷àé, òû ïàëüöåì ïîêàæè :-)
>
> Âîò ñìîòðè, òàêîå äåðåâî:
> À Á Ã Ä Â
> 5 10 11 14 40
> \ / \ / /
> 15 25 /
> \ / /
> 40 /
> \ /
> 80
> Ìàññèâ âõîæäåíèé ñèìâîëîâ -- [1,0,4]
Hå ïîíÿë, ÷òî ýòî çà ìàññèâ.
Ðå÷ü èäåò î ìàññèâå äëèí - ìàññèâ [3,3,1,3,3] íó èëè [2,2,0,2,2]òåïåðü
ñ÷èòàåì ÷òî ÷òî 0 - ïîääåðåâó ñ âõîæäåíèåì íàèìåíüøåé áóêâû 1-ñ äðóãîìó.
Ïàðû âûáèðàåì òîæå ñ ìèíèìàëüíûìè áóêâàìè.
íà óðîâíå 3 - 4 óçëà À Á Ã Ä îáúåäèíÿåì â ÀÁ è ÃÄ
À 0
Á 1
Â
à 0
Ä 1
Òåïåðü íà óðîâíå 2 äâà óçëà ÀÁ è ÃÄ îáúåäèíÿì â ÀÁÃÄ
À 00
Á 01
Â
à 10
Ä 11
Òåïåðü íà óðîâíå 1 äâà óçëà ÀÁÃÄ è Â îáúåäèíÿåì â ÀÁÃÄÂ
À 000
Á 001
 1
à 010
Ä 011
Îñòàëñÿ îäèí óçåë îñòàíîâèëèñü (èëè ïîëó÷èëñÿ óçåë óðîâíÿ 0 - îñòàíîâèëèñü)
Ïîëó÷èëè âîò òàêèå ïðåôèêñíûå êîäû, íó èëè èõ ìîæíî â âèäå äåðåâà
íàðèñîâàòü.
È âîò ÈÕ óæå èñïîëüçûåì êàê â êîäåðå òàê è äåêîäåðå.
>
> Òû óòâåðæäàåøü, ÷òî ìîæåøü ïîñòðîèòü ýêâèâàëåòíîå äåðåâî, òîëüêî ïî
ýòîìó
> ìàññèâó. ÊÀÊ? Âåäü â ýêâèâàëåòíòîì äåðåâå ñèìâîë B âñåãäà äîëæåí èìåòü
> åäèíè÷íóþ äëèíó. Òàêèì îáðàçîì, òû _îáÿçàí_ ïåðåäàòü äåêîäåðó, ÷òî
èäíè÷íóþ
> äëèíó èìååò èìåííî ñèìâîë Â.
Èìåííî ýòà èíôîðìàöèÿ è ïåðåäàåòñÿ â ìàññèâå äëèí. Òóäà âêëþ÷àþòñÿ ÂÑÅ
ëèñòüÿ ò.å. ÂÅÑÜ àëôàâèò.
> Ïîýòîìó òû îáÿçàí åãî ïåðåäàòü. Åñëè áû äåðåâî
> áûëî áîëåå âåòñâèñòûì, òî èç àíàëîãè÷íûõ ñîîáðàæåíèé òû äîëæåí áûë áû
> âêëþ÷èòü è ñèìâîëû, ñîîòâåòñòâóþùèå ëèñòüÿì êîòîðûå ðàñïîëîæåííû íà ðàçíîé
> ãëóáèíå äåðåâà. Hå âêëþ÷àòü â ïåðå÷åíü òû ìîæåøü òîëüêî ñèìâîëû îäíîãî
> (íàïðèìåð, ïîñëåäíåãî) óðîâíÿ -- èõ ìîæíî âîñòàíîâèòü çíàÿ âåñü àëôàâèò. Â
> ïðèìåðå, òû ìîæåøü íå ïåðåäàâàòü ñèìâîëû òðåòüåãî óðîâíÿ - ÀÁÃÄ.
> Òàêèì îáðàçîì, òû îáÿçàí ïîìèìî ìàññèâà [1,0,4] ïåðåäàòü åùå è
> äîï.èíôîðìàöèþ -- ñèìâîë B.
>
> Ãäå ÿ íå ïðàâ?
>
> EinWill.
Ñ óâàæåíèåì, Ñåðãåé
>
--- ifmail v.2.15dev5
* Origin: IFC BanCorp (2:5020/400)
— RU.COMPRESS
From : EinWill 2:5020/400 18 Oct 01 17:43:02
To : Sergey Tchirco
Subj : Re: È åùå ðàç, Huffman
From: "EinWill" <andrey@neva-roentgen.com>
Reply-To: "EinWill" <andrey@neva-roentgen.com>
Ìû ê Âàì, ïðîôåññîð "Sergey Tchirco" <tchsv@nbrt.kazan.su>, è âîò ïî êàêîìó
äåëó:
Èçâèíÿþñü, åñëè ïèñüìî ïðîäóáëèðóåòñÿ -- ïðè îòïðàâêå Mail'åð "ñãëþ÷èë".
> > Îõ. Ýòî ÿ ïîíÿë. ×åñòíîå ñëîâî. Òîëüêî ÿ íå ìîãó ïðèäóìàòü àëãîðèòì,
> > ïîñòðîåíèÿ òàêîãî äåðåâà, áåç èñïîëüçîâàíèÿ äîïîëíèòåëüíîé èíôîðìàöèè,
> Õì. Hó òóò âîîáùå ýëåìåíòàðíî. Hàïðèìåð Huffman íà îáîðîò :)
Òû íå óìíè÷àé, òû ïàëüöåì ïîêàæè :-)
Âîò ñìîòðè, òàêîå äåðåâî:
À Á Ã Ä Â
5 10 11 14 40
\ / \ / /
15 25 /
\ / /
40 /
\ /
80
Ìàññèâ âõîæäåíèé ñèìâîëîâ -- [1,0,4]
Òû óòâåðæäàåøü, ÷òî ìîæåøü ïîñòðîèòü ýêâèâàëåòíîå äåðåâî, òîëüêî ïî ýòîìó
ìàññèâó. ÊÀÊ? Âåäü â ýêâèâàëåòíòîì äåðåâå ñèìâîë B âñåãäà äîëæåí èìåòü
åäèíè÷íóþ äëèíó. Òàêèì îáðàçîì, òû _îáÿçàí_ ïåðåäàòü äåêîäåðó, ÷òî èäíè÷íóþ
äëèíó èìååò èìåííî ñèìâîë Â. Ïîýòîìó òû îáÿçàí åãî ïåðåäàòü. Åñëè áû äåðåâî
áûëî áîëåå âåòñâèñòûì, òî èç àíàëîãè÷íûõ ñîîáðàæåíèé òû äîëæåí áûë áû
âêëþ÷èòü è ñèìâîëû, ñîîòâåòñòâóþùèå ëèñòüÿì êîòîðûå ðàñïîëîæåííû íà ðàçíîé
ãëóáèíå äåðåâà. Hå âêëþ÷àòü â ïåðå÷åíü òû ìîæåøü òîëüêî ñèìâîëû îäíîãî
(íàïðèìåð, ïîñëåäíåãî) óðîâíÿ -- èõ ìîæíî âîñòàíîâèòü çíàÿ âåñü àëôàâèò. Â
ïðèìåðå, òû ìîæåøü íå ïåðåäàâàòü ñèìâîëû òðåòüåãî óðîâíÿ - ÀÁÃÄ.
Òàêèì îáðàçîì, òû îáÿçàí ïîìèìî ìàññèâà [1,0,4] ïåðåäàòü åùå è
äîï.èíôîðìàöèþ -- ñèìâîë B.
Ãäå ÿ íå ïðàâ?
EinWill.
--- ifmail v.2.15dev5
* Origin: Fidolook Express 2.000 www.fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Maxim Smirnov 2:5020/400 18 Oct 01 17:53:17
To : All
Subj : Data Compression by D.Solomon
From: "Maxim Smirnov" <model@iac.spb.ru>
Hi All,
Hàðîä, êòî-íèáóäü ÷èòàë
Data Compression : The Complete Reference
by David Salomon. Second Edition (2000).
Êàê âïå÷àòëåíèÿ?
À òî ÿ âñå ñìîòðþ íà íåå è äóìàþ -- êóïèòü èëè
íå êóïèòü?
Maxim
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 18 Oct 01 17:55:21
To : Sergey Tchirco
Subj : Re: È åùå ðàç, Huffman
From: "Vadim Yoockin" <vy@thermosyn.com>
Reply-To: "Vadim Yoockin" <vy@thermosyn.com>
Hello, Sergey!
You wrote to EinWill on Thu, 18 Oct 2001 13:28:30 +0000 (UTC):
ST>> Âîò ñìîòðè, òàêîå äåðåâî:
ST>> À Á Ã Ä Â
ST>> 5 10 11 14 40
ST>> \ / \ / /
ST>> 15 25 /
ST>> \ / /
ST>> 40 /
ST>> \ /
ST>> 80
ST>> Ìàññèâ âõîæäåíèé ñèìâîëîâ -- [1,0,4]
ST> Hå ïîíÿë, ÷òî ýòî çà ìàññèâ.
Ïîëàãàþ, òîâàðèù EinWill èìåë â âèäó ìàññèâ êîëè÷åñòâà ðàçíûõ äëèí.
1 - îäíà íóëåâàÿ äëèíà, 0 - íîëü îäèíî÷íûõ, 4 - êîë-âî äâîéíûõ äëèí.
ST> Ðå÷ü èäåò î ìàññèâå äëèí - ìàññèâ [3,3,1,3,3] íó èëè [2,2,0,2,2]
Êñòàòè, äîïîëíþ. Ïîñëå óêàçàíèÿ ïåðâûõ ýëåìåíòîâ [2,2,0]
íàì íåò íåîáõîäèìîñòè óêàçûâàòü îñòàëüíûå [2,2], ò.ê. êðîìå íèõ
î÷åâèäíî íè÷åãî èíîãî áûòü íå ìîæåò, åñëè ìû çíàåì ÷èñëî ñèìâîëîâ
â àëôàâèòå. Âïðî÷åì, íà äëèííûõ àëôàâèòàõ ýòî äàåò êîïåå÷íûé âûèãðûø.
Âñåãî äîáðîãî,
Âàäèì.
--- ifmail v.2.15dev5
* Origin: vy@thermosyn.com yoockinv@mtu-net.ru 2:5020/1042.50 (2:5020/400)
— RU.COMPRESS
From : Sergey Kovalev 2:5020/400 18 Oct 01 19:01:32
To : EinWill
Subj : Re: È åùå ðàç, Huffman
From: "Sergey Kovalev" <s-kovalev@nwgsm.ru>
Reply-To: "Sergey Kovalev" <s-kovalev@nwgsm.ru>
[]
> Òû óòâåðæäàåøü, ÷òî ìîæåøü ïîñòðîèòü ýêâèâàëåòíîå äåðåâî, òîëüêî ïî
ýòîìó
> ìàññèâó. ÊÀÊ? Âåäü â ýêâèâàëåòíòîì äåðåâå ñèìâîë B âñåãäà äîëæåí èìåòü
> åäèíè÷íóþ äëèíó. Òàêèì îáðàçîì, òû _îáÿçàí_ ïåðåäàòü äåêîäåðó, ÷òî
èäíè÷íóþ
> äëèíó èìååò èìåííî ñèìâîë Â. Ïîýòîìó òû îáÿçàí åãî ïåðåäàòü. Åñëè áû
äåðåâî
È â êîäåðå è â äåêîäåðå ñîîòâåòñòâèå ìåæäó êîäèðóåìûìè
ñèìâîëàìè è äëèíàìè êîäîâ â òàáëèöå äëèí
ôèêñèðîâàíî è èçâåñòíî çàðàíåå.
Hó íàïðèìåð, òû êîäèðóåøü òåêñòîâûé ôàéë. Ïåðåäàåøü äåêîäåðó
â ìàññèâå äëèí äëèíû êîäîâûõ ñëîâ Õ
äëÿ âõîäíûõ ñèìâîëîâ â òîì ïîðÿäêå,
â êàêîì ýòè ñèìâîëû ñëåäóþò â òàáëèöå ASCII-êîäîâ.
Äåêîäåð áåðåò ASCII-òàáëèöó, ïðèñòàâëÿåò ê íåé ïîëó÷åííûé îò êîäåðà
ìàññèâ äëèí è ïîëó÷àåò ïàðû "êîäèðóåìûé ñèìâîë - äëèíà ñëîâà êîäà Õ".
Òåïåðü äåêîäåð ñòðîèò êîä Õ ñ çàäàííûì íàáîðîì äëèí
è ïðèïèñûâàåò ê êàæäîé ýòîé ïàðå òðåòèé
ýëåìåíò - ñîáñòâåííî ñëîâî êîäà Õ äëÿ êîäèðîâàíèÿ
äàííîãî ñèìâîëà ASCII-òàáëèöû. È êîäåð ïîñòóïàë òàê æå.
Ïîýòîìó âñå êîäèðóåòñÿ è äåêîäèðóåòñÿ åäèíîîáðàçíî.
SK
SPb,2001
--- ifmail v.2.15dev5
* Origin: HOME (2:5020/400)
— RU.COMPRESS
From : Maxime Zakharov 2:5020/400 18 Oct 01 23:32:27
To : Maxim Smirnov
Subj : Re: Data Compression by D.Solomon
From: Maxime Zakharov <maxime@sochi.com>
Ïðèâåò,
Êëþ÷åâîå ñëîâî â íàçâàíèè: Reference, ò.å. áåç îñîáûõ óãëóáëåíèé â òåîðèþ,
íî ïî-ìîåìó äàâîëüíî ïîëíî. ß íå ðàçî÷àðîâàí. Ó ìåíÿ íå Second Edition, íî
äóìàþ õóæå íå ñòàëà.
Maxim Smirnov wrote:
> Hàðîä, êòî-íèáóäü ÷èòàë
> Data Compression : The Complete Reference
> by David Salomon. Second Edition (2000).
> Êàê âïå÷àòëåíèÿ?
>
> À òî ÿ âñå ñìîòðþ íà íåå è äóìàþ -- êóïèòü èëè
> íå êóïèòü?
--
Maxime
http://sochi.net.ru/~maxime
--- ifmail v.2.15dev5
* Origin: Technology Communication Centre, Sochi, Russia (2:5020/400)
— RU.COMPRESS
From : IP Robot 2:5093/4.126 19 Oct 01 01:04:49
To : All
Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/
ftp://ftp.elf.stuba.sk/pub/pc/pack/as12.zip
Archive Searcher v1.2 for Win9x/Me/NT/2000 - Util for searching files in a ZIP,
RAR, ACE and CAB archives (630,139 bytes)
--- PktMake.pl
* Origin: PktMake.pl (2:5093/4.126)
— RU.COMPRESS
From : Lev Serebryakov 2:5030/661 19 Oct 01 03:18:36
To : Serg Tikhomirov
Subj : Huffman
What do you think about sharp blades, Serg?
[Answer on] [Serg Tikhomirov wrote to Lev Serebryakov at [05 Oct 01 13:55]]:
ST> È ïîä ýòî åñòü - íî ïîñêîëüêó ñàì ÿ ñ íèì íå pàáîòàþ, òî è íå çíàþ,
ST> ïîä êàêèå ïëàòôîpìû îí íàïèñàí (êñòàòè, ýòî íàâåpíÿêà îïèñàíî â äîêå â
ST> àpõèâå RAR29LNX.TGZ, æèâóùåì íà ftp://ftp.elf.stuba.sk/pub/pc/pack).
ST> Òàì æå æèâóò êàê ìèíèìóì UNRAR-û äëÿ ATARI, Solaris 7, AIX,... è
ST> èñõîäíèêè îíîãî.
_UN_rar.
LS>> MacOS 9.x
LS>> MacOS X
LS>> Äà, ïîä íåêîòîpîå èç ýòîãî åñòü. Hî ÿ ñòàëêèâàþñü íå òîëüêî ñ
LS>> ýòèì.
ST> Èçâèíè, íå ïîíÿë: ñòàëêèâàåøüñÿ íå òîëüêî ñ ÷åì?
Hå òîëüêî ñ ýòèìè ïëàòôîðìàìè.
LS>> P.S. InfoZIP êàê àëüòåpíàòèâó ÿ áû åùå ïîíÿë...
ST> ZIP â ïpèíöèïå íå ìîæåò áûòü àëüòåpíàòèâîé RAR-ó, êàê Ëåêñèêîí
ST> 6.51 íå ìîæåò áûòü àëüòåpíàòèâîé PAGEMAKER-ó ;-). Ñëèøêîì âåëèêà
ST> pàçíèöà â êëàññå ïpîäóêòîâ.
Âîò òîëüêî zip ëåãàëåí è ïåðåíîñèì, à rar íåò...
ST> Îäíàêî, äàáû íå óéòè â îôôòîïèê, ïîñìîòpèì ëèøü íà påçóëüòàòû
ST> _ñæàòèÿ_ òåñòîâûõ ïpèìåpîâ:
ST> TAR 3.21g -cve9f 20.73 5.39 1,576,960
÷òî âîò ýòî òàêîå, è ãäå bzip2?!
Âîò ðóññêèé òåêñò:
ORIGINAL: dird.txt 737463, 00.00 sec
rar32 -mdE -m5: dird.rar 284399, 20.01 sec
bzip2 -9 dird.txt.bz2 243874, 3.3 sec
ÀÃÀ?! È bzip2 åñòü _ïîäî_âñå_ ïëàòôîðìû, áåñïëàòåí è ëåãàëåí.
ST> Ïîìèìî ñîáñòâåííî ñòåïåíè ñæàòèÿ, ãäå âûèãpûø ñîñòàâëÿåò (íà
ST> ïpåäñòàâëåííûõ ïpèìåpàõ) ~10 - 30%, åñòü è äpóãèå àñïåêòû, èìåþùèå
ST> ìàëî îòíîøåíèÿ ê òåìàòèêå êîíôåpåíöèè. Hàïpèìåp, çàùèòà àpõèâîâ îò
ST> ïîâpåæäåíèé, êîþ îñóùåñòâëÿåò RAR, è íå îñóùåñòâëÿåò ZIP. Âîïpîñû
ST> ;). À Gzip âîîáùå íå óìååò pàçáèâàòü àpõèâû íà òîìà...
À ýòî -- òðåòüÿ ïðîãðàììà, split íàçûâàåòñÿ. Çà÷åì _êîìïðåññîðó_ óìåòü ðàçáèâ
àòü ÷òî-òî íà òîìà?! Ýòî äîëæåí óìåòü ðàçáèâàòåëü íà òîìà!
Êîãäà ó òåáÿ åñòü ìíîãî ìàëåíüêèõ ïðîãðàìì, êàæäàÿ èç êîòîðûõ óìååò ÷òî-òî îä
íî, òû ìîæåøü ïîñòðîèòü ËÞÁÓÞ êîíñòðóêöèþ. À âîò êîãäà ó òåáÿ åñòü îäíà ïðîãðàì
ìà, êîòîðàÿ ïûòàåòñÿ óìåòü âñå... ÓÂÛ, ÷àñòî ýòîãî ``ÂÑÅÃÎ'' íå õâàòàåò.
ST> PS. Ñóãóáî ÷åëîâå÷åñêîå ëþáîïûòñòâî: à êàê ýòî òû óñïåâàåøü pàáîòàòü
ST> ñî âñåìè ýòèìè
LS>> Win32
LS>> FreeBSD
LS>> SunOS
LS>> Linux (íà 3 pàçíûõ ïpîöåññîpàõ -- 80x86, PowerPC, MIPS)
LS>> MacOS 9.x
LS>> MacOS X
ST> äà åù¸ è íà pàçíûõ ïpîöåññîpàõ? Póê-òî õâàòàåò? ;-)
Ðàçðàáîò÷èê...
Remember, pain is part of pleasure, Serg.
... ß äåðæó çà îøåéíèê âðåìÿ, ÿ ñëåæó, ÷òîáû íå áûëî óòðà.
--- I try to be as sharp as I can
* Origin: Cave of Black Lion (2:5030/661)
— RU.COMPRESS
From : Andrew Plyako 2:5030/922.20 20 Oct 01 00:27:04
To : Sergey Tchirco
Subj : Hà: È åùå ðàç, Huffman
Hello Sergey.
18 Oct 01 17:28, you wrote to EinWill:
>> > Õì. Hó òóò âîîáùå ýëåìåíòàðíî. Hàïðèìåð Huffman íà îáîðîò :)
>> Òû íå óìíè÷àé, òû ïàëüöåì ïîêàæè :-)
>> Âîò ñìîòðè, òàêîå äåðåâî:
>> À Á Ã Ä Â
>> 5 10 11 14 40
>> \ / \ / /
>> 15 25 /
>> \ / /
>> 40 /
>> \ /
>> 80
>> Ìàññèâ âõîæäåíèé ñèìâîëîâ -- [1,0,4]
ST> Hå ïîíÿë, ÷òî ýòî çà ìàññèâ.
Óõ òû! À ìû î ðàçíûõ ìàññèâàõ ãîâîðèì, îêàçûâàåòñÿ... ß ñîâñåì äðóãîé àëãîðèòì
ïðèäóìàë... Äàæå ìèíè-ñòàòüþ â Ru.Algorithms ïî ýòîìó ïîâîäó íàïèñàë...
Ýòîò ìàññèâ îçíà÷àåò ñëåäóþùåå: Ó ìåíÿ 1 ñèìâîë êîäèðóåòñÿ îäíèì áèòîì, 0 ñèì
âîëîâ êîäèðóåòñÿ äâóìÿ áèòàìè è 4 ñèìâîëà êîäèðóþòñÿ òðåìÿ áèòàìè.
Ýòîãî ìàññèâà (òî÷íåå ìàññèâà [1,0]) è ñèìâîëà B äîñòàòî÷íî äëÿ ïîñòðîåíèÿ ýêâè
âàëåòíîãî äåðåâà...
ST> Ðå÷ü èäåò î ìàññèâå äëèí - ìàññèâ [3,3,1,3,3]
Î-î-î... ×åãò, ñ õîäó íå áåðóñü ñêàçàòü, êàêîé èç ñïîñîáîâ ëó÷øå... Hî, íàâåðíî
å, òâîé (èç ñîîáðàæåíèé, ÷òî åãî ïðîïàãàíäèðóþò è äðóãèå).
Ñïàñèáî, ÷òî íàïðàâèë íà ïóòü èñòèííûé =)
Andrew
---
* Origin: Äóìàòü áåçÎáðàçíî -- áåçîáðÀçíî!!! (2:5030/922.20)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/4.126 23 Oct 01 13:09:27
To : Andrew Ezhguroff
Subj : Ãëóáèíà Huffman äåðåâà
* Originally in RU.COMPRESS
Ïðèÿòíîãî òåáå äíÿ è íåçàáûâàåìîé íî÷è, Andrew!
Friday October 12 2001, Andrew Ezhguroff writes to Bulat Ziganshin:
>> AE> Õàôìàí ïîä áàéòû 0 è 1 îòâåäåò ïî 2 áèòà, à ïîä äðóãèå ñèìâîëû
>> AE> - ïî 9 áèò.
>> åñëè ýòîò õàôìàí - óìíûé ìóæèê, òî îí íàéä¸ò êîä ïîêîðî÷å ;)
AE> Ñîãëàñåí, îøèáñÿ. Hî ñàì ïðèíöèï îïðîâåðæåíèÿ èäåè EinWill'à âåðåí?
AE> :-)
:))) ýòî ãäå-òî èç æåíñêîé ëîãèêè - ëþáîå óòâåðæäåíèå òèïà "â áîëüøèíñòâå ñëó÷à
åâ" ìîæíî îïðîâåðãíóòü îäíèì, à ëó÷øå äâóìÿ ïðèìåðàìè
Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722
... Èíîãäà äëÿ òîãî, ÷òîáû èçìåíèòü ñâîå âîñïðèÿòèå ìèðà,
... ëþäè ïûòàþòñÿ èçìåíèòü ñàì ìèð
--- GoldED+/W32 1.1.2
* Origin: Ñåòåâîé ôèëüòð íà 5 áàçàðîâ (2:5093/4.126)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/4.126 23 Oct 01 13:24:32
To : Einwill
Subj : Ãëóáèíà Huffman äåðåâà
* Originally in RU.COMPRESS
Ïðèÿòíîãî òåáå äíÿ è íåçàáûâàåìîé íî÷è, Einwill!
Monday October 15 2001, EinWill writes to Bulat Ziganshin:
>> >> ÏÎ ÎÏÐÅÄÅËÅHÈÞ àëãîðèüòì õàôìåíà äà¸ò îïòèìàëüíîå äåðåâî :))
>> Ea> Ýòî è åæó ïîíÿòíî. ÏÎ ÓÑËÎÂÈÞ ìîÿ ìîäèôèêàöèÿ ðàáîòàåò _íå ñ
>> Ea> äåðåâîì_ (à ëèøü â ðÿäå ñëó÷àåâ ñ "ëó÷øåé ïîëîâèíîé" ýòîãî
>> Ea> îïòèìàëüíîãî äåðåâà).
E> Ãëóïîñòü ñìîðîçèë. :-(
E> Ïðèçíàþ... Håâåñòü ñ ÷åãî ïîêàçàëîñü, ÷òî ìîè êîäû íå ïðåäñòàâèìû â
E> âèäå âåòâëåíèÿ äåðåâà :-( ). Hó ñ êåì ïðèñòóïîâ ãëóïîñòåé íå áûâàåò?
E> :)
äà-äà, ôèøêà è áûëà â òîì, ÷òî ëþáîé ïðåôèêñíûé êîä ìîæíî ïðåäñòàâèòü äåðåâîì
Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722
... Èíîãäà äëÿ òîãî, ÷òîáû èçìåíèòü ñâîå âîñïðèÿòèå ìèðà,
... ëþäè ïûòàþòñÿ èçìåíèòü ñàì ìèð
--- GoldED+/W32 1.1.2
* Origin: Ñåòåâîé ôèëüòð íà 5 áàçàðîâ (2:5093/4.126)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/4.126 23 Oct 01 14:47:25
To : Sasha Breger
Subj : Ñæàòèå ñòðîê (äî 250 ñèìâîëîâ)
* Originally in RU.COMPRESS
Ïðèÿòíîãî òåáå äíÿ è íåçàáûâàåìîé íî÷è, Sasha!
Friday October 12 2001, Sasha Breger writes to All:
SB> ×åì/êàê ëó÷øå âñåãî ñæèìàòü íå î÷åíü áîëüøèå ñòðîêè? ×åì ìîæíî
SB> ïîëó÷èòü ìàêñèìàëüíîå ñæàòèå (ñ ó÷¸òîì çàãîëîâêîâ)?
îïèøè öåëèêîì ñèñòåìó. ïîêà îòâåò îòðèöàòåëüíûé, âåäü ïðîãðàììà òîæå ìåñòî çàíè
ìàåò ;)
Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722
... Èíîãäà äëÿ òîãî, ÷òîáû èçìåíèòü ñâîå âîñïðèÿòèå ìèðà,
... ëþäè ïûòàþòñÿ èçìåíèòü ñàì ìèð
--- GoldED+/W32 1.1.2
* Origin: Ñåòåâîé ôèëüòð íà 5 áàçàðîâ (2:5093/4.126)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/4.126 23 Oct 01 14:50:46
To : Einwill
Subj : È åùå ðàç, Huffman
* Originally in RU.COMPRESS
Ïðèÿòíîãî òåáå äíÿ è íåçàáûâàåìîé íî÷è, EinWill!
Wednesday October 17 2001, EinWill writes to All:
E> àëãîðèòìîì Huffman'à. Âîïðîñ òàêîé: êàêèì îáðàçîì ìîæíî îïòèìàëüíåå
E> âñåãî õðàíèòü äåðåâî Huffman'à? Hó, èëè òàáëèöó êîäîâ Huffman'à (ïî
ñìîòðåòü èñõîäíèêè zip/ar002. êëàññèêà. à åù¸ ïðîùå ñíà÷àëà ïðî÷åñòü appnote.tx
t èç pkzip 1.93 alpha èëè âûøå
Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722
... Èíîãäà äëÿ òîãî, ÷òîáû èçìåíèòü ñâîå âîñïðèÿòèå ìèðà,
... ëþäè ïûòàþòñÿ èçìåíèòü ñàì ìèð
--- GoldED+/W32 1.1.2
* Origin: Ñåòåâîé ôèëüòð íà 5 áàçàðîâ (2:5093/4.126)
— RU.COMPRESS
From : EinWill 2:5020/400 23 Oct 01 15:42:55
To : All
Subj : È ñíîâà Huffman. È íè÷åãî ñìåøíîãî :-(
From: "EinWill" <andrey@neva-roentgen.com>
Reply-To: "EinWill" <andrey@neva-roentgen.com>
Ïðèâåòñòâóþ âñåõ!
Äèñêóññèÿ â ýõîêîíôåðåíöèè íå î÷åíü îæèâëåííàÿ, òàê ÷òî, ïîëàãàþ, çà
åäèíîîðáàçèå ïîäíèìàåìûõ ìíîþ òåì, ñóäèòü íå ñòàíåòå...
Ðàññìîòðèì òàêóþ çàäà÷ó: ïóñòü Hist[i] - ÷àñòîòà âõîæäåíèÿ êàæäîãî èç
ñèìâîëîâ â êîäèðóåìûé òåêñò. Ñòàíäàðòíàÿ çàäà÷à -- ïîñòðîèòü ïðåôèêñíûå êîäû
ñ äëèíàìè C[i], êîòîðûå óäîâëåòâîðÿþò óñëîâèÿì:
\sum 2^(-C[i]) <=1, è \sum C[i]*Hist[i] -> ìèíèìàëüíà.
Ýòà çàäà÷à, ðåøàåòñÿ ñòàíäàðòíûì àëãîðèòìîì Huffman'à.
NB!
Óñèëèì íàøè òðåáîâàíèÿ: ïîòðåáóåì, ÷òîáû max(C[i]) áûë ìèíèìàëåí (äëÿ
òåõ C[i], êîòîðûå óäîâëåòâîðÿþò äâóì ñòàíäðàòíûì óñëîâèÿì). Ðåøåíèåì òàêîé
çàäà÷è áóäåò íåñêîëüêî âèäîèçìåíåííûé àëãîðèòì Huffman'à, â êîòîðîì ìû ïðè
êàæäîé èòåðàöèè áóäåì âûáèðàòü íå ëþáûå äâà ïîääåðåâà, ñ ìèíèìàëüíûìè
çíà÷åíèÿìè, à òîëüêî òå, ðàçíèöà ìåæäó óæå ïîñòðîåííûìè âûñîòàìè êîòîðûõ --
ìèíèìàëüíà; â ñëó÷àå æå, êîãäà ó íåñêîëüêèõ ïàð ïîääåðåâüåâ ðàçíèöà âûñîò
ìèíèìàëüíà, âûáèðàåì òó ïàðó, ó êîòîðîé âûñîòû ìåíüøå.
Ïðèìåð. Äëÿ Àëôàâèòà ABCDEFGH ñ ÷àñòîòîé âõîæäåíèÿ ðàâíîé,
Hist = [A=3,B=1,C=2,D=5,E=5,F=1,G=1,H=10] ìû, äëÿ íà÷àëà, ïîñòðîèì
ñòàíäàðòíîå äåðåâî Huffman'à:
B F G C A D E H
1 1 1 2 3 5 5 10
\ / / / / \ / /
2 / / / 10 /
\ / / / / /
3 / / / /
\ / / / /
5 / / /
\ / / /
8 / /
\ / /
\ / /
18 /
\ /
28
÷òî ñîîòâåòñòâóåò êîäàì:
A = 001
B = 000000
C = 0001
D = 010
E = 011
F = 000001
G = 00001
H = 1
Òî åñòü ìàññèâ äëèí êîäîâ C = [3,6,4,3,3,6,5,1] max(C[i]) = 6.
Òåïåðü ïðèìåíèì îïèñàííóþ âûøå ìîäèôèêàöèþ àëãîðèòìà (ïîýòàïíî):
B F G C A D E H
1 1 1 2 3 5 5 10
\ /
2
íà ñëåäóþùåì øàãå, ìû äîëæíû îáúåäåíèòü G è Ñ, à íå G è óçåë,
èáî óçåë èìååò âûñîòó 1, à G è Ñ -- íóëåâóþ, òî åñòü ðàçíèöà
ìåæäó âûñîòàìè G è C -- ìèíèìàëüíà:
B F G C A D E H
1 1 1 2 3 5 5 10
\ / \ /
2 3
Èç òåõ æå ñîîáðàæåíèé, òåïåðü ìû îáúåäèíÿåì äâà óçëà, à íå
óçåë è A:
B F G C A D E H
1 1 1 2 3 5 5 10
\ / \ /
2 3
\ /
\ /
5
Ðàçóìååòñÿ, íàäî îáúåäèíèòü A è D (èëè A è E):
B F G C A D E H
1 1 1 2 3 5 5 10
\ / \ / \ /
2 3 8
\ /
\ /
5
Hà ýòîé èòåðàöèè ó íàñ òîëüêî îäèí âîçìîæíûé âàðèàíò:
B F G C E A D H
1 1 1 2 5 3 5 10
\ / \ / / \ /
2 3 / 8
\ / /
\ / /
5 /
\ /
10
Hàêîíåö, òåïåðü ìû äîëæíû îáúåäèíèòü óçåë 8 ñ ëèñòîì H. Èõ
âûñîòû, õîòÿ è íå ðàâíû, íî âñå æå ðàçíèöà ìåæäó íèìè =1,
à ðàçíèöà ìåæäó âûñîòàìè óçëîâ =2. Çàìåòèì, ÷òî äàæå åñëè áû
óçåë 10 èìåë âûñîòó 2 (à íå 3), òî åñòü, äàæå åñëè áû ðàçíèöà
ìåæäó âûñîòàìè äâóõ óçëîâ ñîâïàäàëà, òî ìû (ïîñìîòðèòå íà
àëãîðèòì!) âñå ðàâíî äîëæíû áûëè áû âûáðàòü â ïàðó ê óçëó 8
ëèñò H, èáî âûñîòû ïðè òàêîì âûáîðå (2 è 1) ìåíüøå, ÷åì âûñîòû
ïðè âûáîðå äâóõ óçëîâ (3 è 2).
B F G C E A D H
1 1 1 2 5 3 5 10
\ / \ / / \ / /
2 3 / 8 /
\ / / \ /
\ / / 18
5 /
\ /
10
 èòîãå, ïîëó÷àåì âîò òàêîå äåðåâî:
B F G C E A D H
1 1 1 2 5 3 5 10
\ / \ / / \ / /
2 3 / 8 /
\ / / \ /
\ / / 18
5 / /
\ / /
10 /
\ /
\ /
28
÷òî ñîîòâåòñòâóåò êîäàì:
A = 100
B = 0000
C = 0011
D = 101
E = 01
F = 0001
G = 0010
H = 11
Çíà÷èò ìàññèâ äëèí êîäîâ C = [3,4,4,3,2,4,2], à max(C[i]) = 4
Ïî÷óâñòâóéòå ðàçíèöó.
Ðàçóìååòñÿ, îáà äåðåâà êîäèðóþò èíôîðìàöèþ îäèíàêîâî (â ñìûñëå ñæàòèÿ
èíôîðìàöèè). Hî çàòî ñòðóêòóðó âòîðîãî ìîæíî ïåðåäàòü áîëåå êîìïàêòíî. Çà
÷òî, ñîáñòâåííî, âñÿ áîðüáà è øëà...
À òåïåðü ñàì âîïðîñ. Ñåé÷àñ ó ìåíÿ ðåàëèçàöèÿ ïîñòðîåíèÿ ìàññèâà C
èìåííî òàêàÿ, êàê îïèñàíà âûøå: ÿ ñòðîþ äåðåâî óêàçàííûì àëãîðèòìîì, à ïîòîì
ïî íåìó óæå ñ÷èòàþ ìàññèâ äëèí. À õî÷åòñÿ èçáåæàòü ïðîìåæóòî÷íîãî ïîñòðîåíèÿ
äåðåâà.
Ýòî âîçìîæíî? Èäåè, ïðåäëîæåíèÿ?
--
.... C Óâàæåíèåì, EinWill
--- ifmail v.2.15dev5
* Origin: Fidolook Express 2.000 www.fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/4.126 23 Oct 01 17:42:44
To : Alexey Rojnov
Subj : RANGECODER
* Originally in RU.COMPRESS
Ïðèÿòíîãî òåáå äíÿ è íåçàáûâàåìîé íî÷è, Alexey!
Monday October 15 2001, Alexey Rojnov writes to All:
AR> Ëþäè, à ÷òî åñòü ñàáæ? Ýòî ÷òî, íîâûé òèï àðèôìåòè÷. êîäèðîâàíèÿ?
äà. áîëåå áûñòðûé è íå ïîäïàäàþùèé ïîä ïàòåíò ibm. âåðîÿòíî, åù¸ ëó÷øå êîäåð â
ppmd ïîñëåäíåé âåðñèè. íî ýòî ïóñòü äðóãèå âûñêàæóòñÿ
Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722
... Èíîãäà äëÿ òîãî, ÷òîáû èçìåíèòü ñâîå âîñïðèÿòèå ìèðà,
... ëþäè ïûòàþòñÿ èçìåíèòü ñàì ìèð
--- GoldED+/W32 1.1.2
* Origin: Ñåòåâîé ôèëüòð íà 5 áàçàðîâ (2:5093/4.126)
— RU.COMPRESS
From : Sergey Tchirco 2:5020/400 23 Oct 01 18:52:16
To : EinWill
Subj : Hà: È ñíîâà Huffman. È íè÷åãî ñìåøíîãî :-(
From: "Sergey Tchirco" <tchsv@nbrt.kazan.su>
"EinWill" <andrey@neva-roentgen.com> ñîîáùèë/ñîîáùèëà â íîâîñòÿõ ñëåäóþùåå:
news:nGcB7.732$kY.789990@news.rt.ru...
> Ïðèâåòñòâóþ âñåõ!
>
> Äèñêóññèÿ â ýõîêîíôåðåíöèè íå î÷åíü îæèâëåííàÿ, òàê ÷òî, ïîëàãàþ, çà
> åäèíîîðáàçèå ïîäíèìàåìûõ ìíîþ òåì, ñóäèòü íå ñòàíåòå...
>
> Ðàññìîòðèì òàêóþ çàäà÷ó: ïóñòü Hist[i] - ÷àñòîòà âõîæäåíèÿ êàæäîãî èç
> ñèìâîëîâ â êîäèðóåìûé òåêñò. Ñòàíäàðòíàÿ çàäà÷à -- ïîñòðîèòü ïðåôèêñíûå
êîäû
> ñ äëèíàìè C[i], êîòîðûå óäîâëåòâîðÿþò óñëîâèÿì:
> \sum 2^(-C[i]) <=1, è \sum C[i]*Hist[i] -> ìèíèìàëüíà.
>
> Ýòà çàäà÷à, ðåøàåòñÿ ñòàíäàðòíûì àëãîðèòìîì Huffman'à.
>
> NB!
> Óñèëèì íàøè òðåáîâàíèÿ: ïîòðåáóåì, ÷òîáû max(C[i]) áûë ìèíèìàëåí (äëÿ
> òåõ C[i], êîòîðûå óäîâëåòâîðÿþò äâóì ñòàíäðàòíûì óñëîâèÿì). Ðåøåíèåì òàêîé
> çàäà÷è áóäåò íåñêîëüêî âèäîèçìåíåííûé àëãîðèòì Huffman'à, â êîòîðîì ìû ïðè
> êàæäîé èòåðàöèè áóäåì âûáèðàòü íå ëþáûå äâà ïîääåðåâà, ñ ìèíèìàëüíûìè
> çíà÷åíèÿìè, à òîëüêî òå, ðàçíèöà ìåæäó óæå ïîñòðîåííûìè âûñîòàìè
êîòîðûõ --
> ìèíèìàëüíà; â ñëó÷àå æå, êîãäà ó íåñêîëüêèõ ïàð ïîääåðåâüåâ ðàçíèöà âûñîò
> ìèíèìàëüíà, âûáèðàåì òó ïàðó, ó êîòîðîé âûñîòû ìåíüøå.
Îäíî èç äâóõ èëè ýòî ÎÏÒÈÌÀËÜHÎÅ ÄÅÐÅÂÎ è â íåì ÄÎËÆHÀ áûòü äëèíà C[i]
ïîëó÷åííàÿ â àëãîðèòìå Huffman'a
[Ñîêðàùàþ ïðèìåð]
> Òî åñòü ìàññèâ äëèí êîäîâ C = [3,6,4,3,3,6,5,1] max(C[i]) = 6.
> Åñòü ÷àñòîòû [A=3,B=1,C=2,D=5,E=5,F=1,G=1,H=10]
Äëèíà êîäèðîâàííîãî ñîîáùåíèÿ â "åäèíèöàõ"
3*3+6*1+4*2+3*5+3*5+6*1+5*1+1*10=9+6+8+15+6+5+10=59
Ïðèìåíèâ àëãîðèòì ïîëó÷èëè
> Çíà÷èò ìàññèâ äëèí êîäîâ C = [3,4,4,3,2,4,2], à max(C[i]) = 4
òóò îøèáêà C = [3,4,4,3,2,4,4,2]
Äëèíà êîäèðîâàííîãî ñîîáùåíèÿ â "åäèíèöàõ"
3*3+6*4+4*4+3*3+3*2+6*4+5*4+2*10=9+24+16+9+6+24+20+20=128
> Ïî÷óâñòâóéòå ðàçíèöó.
Âîò âîò, ïî÷óâñòâóé! Îáðåçàÿ äåðåâî Õàôôìàíà ÑÎÇHÀÒÅËÜHÎ èäóò íà íåêîòîðîå
óõóäøåíèå ñæàòèÿ, æåðòâóÿ èì ðàäè ñêîðîñòè è êîìïàêòíîñòè òàáëèö. Hî â òâîåì
ñëó÷àå óæ î÷åíü áîëüøàÿ æåðòâà.
> À òåïåðü ñàì âîïðîñ. Ñåé÷àñ ó ìåíÿ ðåàëèçàöèÿ ïîñòðîåíèÿ ìàññèâà C
> èìåííî òàêàÿ, êàê îïèñàíà âûøå: ÿ ñòðîþ äåðåâî óêàçàííûì àëãîðèòìîì, à
ïîòîì
> ïî íåìó óæå ñ÷èòàþ ìàññèâ äëèí. À õî÷åòñÿ èçáåæàòü ïðîìåæóòî÷íîãî
ïîñòðîåíèÿ
> äåðåâà.
> Ýòî âîçìîæíî? Èäåè, ïðåäëîæåíèÿ?
 ëþáîì ñëó÷àå ïåðåñòðîéêà äåðåâà ïî ñðàâíåíèþ ñ ñàìîé
óïàêîâêîé/ðàñïàêîâêîé -ìèçåð
À âîîáùå ïîñìîòðè, ÷òî ðåêîìåíäóåò Áóëàò. Åùå ìîæíî ïîñìîòðåòü èñõîäíèêè
zlib, òàì ãäå-òî åñòü îáñóæäåíèå òàáëèö/äåðåâüåâ è èõ ýôôåêòèâíîñòè
>
> --
> .... C Óâàæåíèåì, EinWill
Ñ óâàæåíèåì, Ñåðãåé
--- ifmail v.2.15dev5
* Origin: IFC BanCorp (2:5020/400)
— RU.COMPRESS
From : Andrew Gorbunow 2:5022/81.7 23 Oct 01 22:23:25
To : All
Subj : PPMDH
Hy çäpàâñòâyé, All!
Äîïyñòèì ÿ ñæàë ôàéë file.txt PPMonstr-îì (ver.H):
*ppmonstr e -o16 -m108 file.txt*
Áyäåò ëè îí íîpìàëüíî èçâëå÷åí y þçåpà ñ 32Mb ÎÇÓ (ò.å. ìåíüøå ÷åì 108)???
Ñ yâàæåíèåì, Andy E-mail: AgSpider@Mail.ru
W e b: http://A-W-L.narod.ru
--- GOLDED 1.1.5 -·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-·-
* Origin: ::: Night Kingdom ::: (2:5022/81.7)
— RU.COMPRESS
From : AWS Vladimir 2:5020/400 24 Oct 01 09:06:07
To : All
Subj : test
From: "AWS Vladimir" <aws@asbest.ru>
Reply-To: "AWS Vladimir" <aws@asbest.ru>
ñîððè, ïðîâåðêà ãëþêîâ
--
Îòïðàâëåíî ÷åðåç ñåðâåð Talk.Ru - http://www.talk.ru
--- ifmail v.2.15dev5
* Origin: Talk.Ru (2:5020/400)
— RU.COMPRESS
From : EinWill 2:5020/400 24 Oct 01 10:01:06
To : Bulat Ziganshin
Subj : Re: RANGECODER
From: "EinWill" <andrey@neva-roentgen.com>
Reply-To: "EinWill" <andrey@neva-roentgen.com>
Ìû ê Âàì, ïðîôåññîð "Bulat Ziganshin"
<Bulat.Ziganshin@p126.f4.n5093.z2.fidonet.org>, è âîò ïî êàêîìó äåëó:
AR>> Ëþäè, à ÷òî åñòü ñàáæ? Ýòî ÷òî, íîâûé òèï àðèôìåòè÷. êîäèðîâàíèÿ?
BZ> äà. áîëåå áûñòðûé è íå ïîäïàäàþùèé ïîä ïàòåíò ibm.
À ãäå îá ýòîì RangeCoder'å ìîæíî ïî÷èòàòü?
Ñ óâàæåíèåì,
EinWill
--- ifmail v.2.15dev5
* Origin: Fidolook Express 2.000 www.fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : EinWill 2:5020/400 24 Oct 01 10:17:34
To : Sergey Tchirco
Subj : Re: È ñíîâà Huffman. È íè÷åãî ñìåøíîãî :-(
From: "EinWill" <andrey@neva-roentgen.com>
Reply-To: "EinWill" <andrey@neva-roentgen.com>
Ìû ê Âàì, ïðîôåññîð "Sergey Tchirco" <tchsv@nbrt.kazan.su>, è âîò ïî êàêîìó
äåëó:
Âî-ïåðâûõ, òû íå ïðàâ. Âî âñÿêîì ñëó÷àå, ìû ñåé÷àñ ýòî îáñóäèì.
Âî-âòîðûõ, 2 All: âîïðîñ îñòàåòñÿ îòêðûòûì :-)
> > Ðàññìîòðèì òàêóþ çàäà÷ó: ïóñòü Hist[i] - ÷àñòîòà âõîæäåíèÿ êàæäîãî
èç
> > ñèìâîëîâ â êîäèðóåìûé òåêñò. Ñòàíäàðòíàÿ çàäà÷à -- ïîñòðîèòü ïðåôèêñíûå
êîäû
> > ñ äëèíàìè C[i], êîòîðûå óäîâëåòâîðÿþò óñëîâèÿì:
> > \sum 2^(-C[i]) <=1, è \sum C[i]*Hist[i] -> ìèíèìàëüíà.
> > Ýòà çàäà÷à, ðåøàåòñÿ ñòàíäàðòíûì àëãîðèòìîì Huffman'à.
> > Óñèëèì íàøè òðåáîâàíèÿ: ïîòðåáóåì, ÷òîáû max(C[i]) áûë ìèíèìàëåí
(äëÿ
> > òåõ C[i], êîòîðûå óäîâëåòâîðÿþò äâóì ñòàíäðàòíûì óñëîâèÿì).
> Îäíî èç äâóõ èëè ýòî ÎÏÒÈÌÀËÜHÎÅ ÄÅÐÅÂÎ è â íåì ÄÎËÆHÀ áûòü äëèíà C[i]
Òû íåâíèìàòåëüíî ïðî÷èòàë ïðåäûäóùèå àáçàöû. Çàìåòü, ÿ õî÷ó âûáðàòü äåðåâî ñ
íàèìåíüøåé äëèíîé ó C[i] _ñðåäè âñåõ îïòèìàëüíûõ äåðåâüåâ_ (êîòîðûõ,
ðàçóìååòñÿ, íåñêîëüêî).
> [Ñîêðàùàþ ïðèìåð]
Åìó òû òîæå íå óäåëèë äîëæíîãî âíèìàíèÿ. ß òàì ÷åñòíî íàïèñàë, ÷òî ýòè äâà
äåðåâà ýêâèâàëåíòíû â ñìûñëå ñòåïåíè ñæàòèÿ èíôîðìàöèè.
> > Òî åñòü ìàññèâ äëèí êîäîâ C = [3,6,4,3,3,6,5,1] max(C[i]) = 6.
> > Åñòü ÷àñòîòû [A=3,B=1,C=2,D=5,E=5,F=1,G=1,H=10]
> Äëèíà êîäèðîâàííîãî ñîîáùåíèÿ â "åäèíèöàõ"
Hó ÷òî æå, äàâàé ñ÷èòàòü âìåñòå :-)
> 3*3+6*1+4*2+3*5+3*5+6*1+5*1+1*10 = 9+6+8+15+6+5+10=59
Ñìîòðè, â ëåâîé ÷àñòè ó òåáÿ 8 ñëàãàåìûõ, à â ïðàâîé 7. Ïîòîìó ÷òî òû
ïðîïóñòèë îäíè èç ñëàãàåìûõ, ðàâíîå 15 (òàì äâà ðàçà 3*5). Ïîýòîìó ïîóë÷àåì
59+15 = 74
> Ïðèìåíèâ àëãîðèòì ïîëó÷èëè
> > Çíà÷èò ìàññèâ äëèí êîäîâ C = [3,4,4,3,2,4,2], à max(C[i]) = 4
> òóò îøèáêà C = [3,4,4,3,2,4,4,2]
Äà, ñïàñèáî.
> Äëèíà êîäèðîâàííîãî ñîîáùåíèÿ â "åäèíèöàõ"
> 3*3+6*4+4*4+3*3+3*2+6*4+5*4+2*10 = 9+24+16+9+6+24+20+20=128
À òóò òû ìåñòàìè çà÷åì-òî óìíîæàåøü íîâûå C[i] íà ñòàðûå C[i]. À íàäî âñþäó
íîâûå C[i]*Hist[i]:
3*3 + 4*1 + 4*2 + 3*5+ 2*5 + 4*1 +4*1 + 2*10 = 9+4+8+15+10+4+4+20 = 74
> > Ïî÷óâñòâóéòå ðàçíèöó.
> Âîò âîò, ïî÷óâñòâóé!
Èçâèíè, íî òåáå íå óäàëîñü ñúåõèäíè÷àòü :-)
> Îáðåçàÿ äåðåâî Õàôôìàíà ÑÎÇHÀÒÅËÜHÎ èäóò íà íåêîòîðîå
> óõóäøåíèå ñæàòèÿ, æåðòâóÿ èì ðàäè ñêîðîñòè è êîìïàêòíîñòè òàáëèö. Hî â
òâîåì
> ñëó÷àå óæ î÷åíü áîëüøàÿ æåðòâà.
ß íè÷åì íå æåðòâóþ. ß ïðîñòî ñòðîþ íàèáîëåå âûãîäíîå (äëÿ ìîèõ ëè÷íûõ íóæä
õðàíåíèÿ çàãîëîâêà äàííûõ) äåðåâî èç âñåõ îïòèìàëüíûõ (â ïëàíå ñæàòèÿ)
äåðåâüåâ.
Èòàê, âîïðîñ îñòàåòñÿ â ñèëå:
> > À òåïåðü ñàì âîïðîñ. Ñåé÷àñ ó ìåíÿ ðåàëèçàöèÿ ïîñòðîåíèÿ ìàññèâà C
> > èìåííî òàêàÿ, êàê îïèñàíà âûøå: ÿ ñòðîþ äåðåâî óêàçàííûì àëãîðèòìîì, à
> > ïîòîì ïî íåìó óæå ñ÷èòàþ ìàññèâ äëèí. À õî÷åòñÿ èçáåæàòü ïðîìåæóòî÷íîãî
> > ïîñòðîåíèÿ äåðåâà.
> > Ýòî âîçìîæíî? Èäåè, ïðåäëîæåíèÿ?
>  ëþáîì ñëó÷àå ïåðåñòðîéêà äåðåâà ïî ñðàâíåíèþ ñ ñàìîé
> óïàêîâêîé/ðàñïàêîâêîé -ìèçåð
Ì-ì-ì. Òóò íå â ñêîðîñòè äåëî. ß æå íå êîäåð ïèøó. Ó ìåíÿ ýòè, ñæèìàåìûå
äàííûå ïðåäâàðèòåëüíî ñðàâíèòåëüíî äîëãî âû÷èñëÿþòñÿ... Äåëî èñêëþ÷èòåëüíî
â ýñòåòè÷åñêîé êðàñîòå êîäà :-) Hó è ïëþñ çäîðîâûé íàó÷íûé èíåòåðåñ.
> À âîîáùå ïîñìîòðè, ÷òî ðåêîìåíäóåò Áóëàò.
À ÷òî îí ðåêîìåíäóåò? ß íåäàâíî ïîäïèñàí íà ýòó ýõîêîíôåðåíöèþ...
> Åùå ìîæíî ïîñìîòðåòü èñõîäíèêè zlib
Ñìîòðåë. Ïî êîíêðåòíî ìîåìó âîïðîñó íè÷åãî íå íàøåë.
Ñ óâàæåíèåì,
EinWill
--- ifmail v.2.15dev5
* Origin: Fidolook Express 2.000 www.fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Sergey Tchirco 2:5020/400 24 Oct 01 11:56:29
To : EinWill
Subj : Hà: È ñíîâà Huffman. È íè÷åãî ñìåøíîãî :-(
From: "Sergey Tchirco" <tchsv@nbrt.kazan.su>
"EinWill" <andrey@neva-roentgen.com> ñîîáùèë/ñîîáùèëà â íîâîñòÿõ ñëåäóþùåå:
news:E_sB7.820$kY.877785@news.rt.ru...
> Âî-ïåðâûõ, òû íå ïðàâ. Âî âñÿêîì ñëó÷àå, ìû ñåé÷àñ ýòî îáñóäèì.
> Âî-âòîðûõ, 2 All: âîïðîñ îñòàåòñÿ îòêðûòûì :-)
Ñîãëàñåí íå ïðàâ. ïðèìåð òî ðàçîáðàë, à âîò åãî îïèñàíèå â íà÷àëå, ïðî÷èòàë
íå âíèìàòåëüíî.
Äà, òâîé âàðèàíò äàåò òåîðèòè÷åñêè íåñêîëüêî ëó÷øóþ êàðòèíó, ÷åì ñòàíäàðòíûé
Huffman, íî íà ïðàêòèêå - óâû ;( Âåðîÿòíîñòü òîãî, ÷òî ó íåñêîëüêèõ óçëîâ
áóäóò ðàâíûå âåðîÿòíîñòè, íà ñêîëüêî íèáóäü áîëüøèõ äàííûõ íè÷òîæíî ìàëà :(
èëè íàäî îïÿòü òàêè çàãðóáëÿòü êàðòèíó, è òåðÿòü òåæå áèòèêè íà ñæàòèè.
> Èçâèíè, íî òåáå íå óäàëîñü ñúåõèäíè÷àòü :-)
óâû :( Õîòÿ ÷èñòî èíòóèòèâíî ìíå íå âåðèòñÿ, íî òåîðèÿ ïîêàçûâàåò :((
> Ì-ì-ì. Òóò íå â ñêîðîñòè äåëî. ß æå íå êîäåð ïèøó. Ó ìåíÿ ýòè, ñæèìàåìûå
> äàííûå ïðåäâàðèòåëüíî ñðàâíèòåëüíî äîëãî âû÷èñëÿþòñÿ... Äåëî
èñêëþ÷èòåëüíî
> â ýñòåòè÷åñêîé êðàñîòå êîäà :-) Hó è ïëþñ çäîðîâûé íàó÷íûé èíåòåðåñ.
À ýñòåòè÷åñêàÿ êðàñîòà äîñòèãàåòñÿ âûçîâîì îäíîé, ìàêñèìóì äâóõ ôóíêöèé èç
ãîòîâîé(!) ïðîòåñòèðîâàííîé(!) è îïòèìèçèðîâàííîé(!) áèáëèîòåêè, óæå
íàïèñàííîé çà òåáÿ. Ïðîãðàììèñò äîëæåí áûòü ëåíèâûì! Äà è óæ áîëüíî ÷àñòíûé
âîïðîñ: âûèãðûøü íåñêîëüêèõ áèòîâ, åñëè âçÿòü òîòæå RangeCoder, ðåçóëüòàòü
ñêîðåå âñåãî ïîëó÷øå áóäåò.
>
>
> > À âîîáùå ïîñìîòðè, ÷òî ðåêîìåíäóåò Áóëàò.
> À ÷òî îí ðåêîìåíäóåò? ß íåäàâíî ïîäïèñàí íà ýòó ýõîêîíôåðåíöèþ..
Òàê â÷åðà ïðîëåòàëî: bzip2 è readme ê pkzip
>
> > Åùå ìîæíî ïîñìîòðåòü èñõîäíèêè zlib
> Ñìîòðåë. Ïî êîíêðåòíî ìîåìó âîïðîñó íè÷åãî íå íàøåë.
Ïî ñîõðàíåíèþ äåðåâà òàì íåò, òàì åñòü âîïðîñ òàáëèöà/äåðåâî
>
> Ñ óâàæåíèåì,
> EinWill
Ñ óâàæåíèåì, Ñåðãåé
--- ifmail v.2.15dev5
* Origin: IFC BanCorp (2:5020/400)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/4.126 24 Oct 01 12:36:50
To : Einwill
Subj : RANGECODER
* Originally in RU.COMPRESS
Ïðèÿòíîãî òåáå äíÿ è íåçàáûâàåìîé íî÷è, Einwill!
Wednesday October 24 2001, EinWill writes to Bulat Ziganshin:
E> À ãäå îá ýòîì RangeCoder'å ìîæíî ïî÷èòàòü?
íèãäå. íî ìîæíî âçÿòü åãî èñõîäíèêè :))
Bulat, mailto:bulatzATfort.tatarstan.ru, ICQ 15872722
... Èíîãäà äëÿ òîãî, ÷òîáû èçìåíèòü ñâîå âîñïðèÿòèå ìèðà,
... ëþäè ïûòàþòñÿ èçìåíèòü ñàì ìèð
--- GoldED+/W32 1.1.2
* Origin: Ñåòåâîé ôèëüòð íà 5 áàçàðîâ (2:5093/4.126)