— RU.COMPRESS
From : Vadim Yoockin 2:5020/400 25 Jul 00 11:29:21
To : ZAB
Subj : Re: ×òî ïîñîâåòóåòå?
From: "Vadim Yoockin" <vy@thermosyn.com>
Hello, ZAB ! You wrote:
>> Håçà÷åì ýòî. Çàäà÷à-òî - â ïîäñ÷åòå ÷èñëà îäèíàêîâûõ êîíòåêñòîâ.
>> Äëÿ óíèêàëüíûõ æå êîíòåêñòîâ îáðàòíîå ïðåîáðàçîâàíèå íè÷åì
>> íå îòëè÷àåòñÿ îò BWT-øíîãî.
>
>Àãà! Òîëüêî âîò äëÿ òàêîãî ïîäñ÷¸òà ïîòðåáóåòñÿ ~4 Ãá!!!
À ýòî êàê ñ÷èòàòü... Âåäü íå íàäî ñ÷èòàòü âñå êîíòåêñòû îäíîâðåìåííî.
Âñåãî äîáðîãî,
Âàäèì.
--- ifmail v.2.15dev5
* Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/28.126 25 Jul 00 22:08:05
To : Eugene Goncharuk
Subj : Ýíòðîïèÿ
* Originally in RU.COMPRESS
Hello Eugene!
Wednesday July 26 2000, Eugene Goncharuk writes to All:
EG> Êàê èçìåðèòü ýíòðîïèþ ôàéëà ?
EG> ß òàê ïîëàãàþ, ÷òî ó ôàéëà ñîñòîÿùåãî èç íóëåé îíà áóäåò ìààëåíüêàÿ à
EG> ó ñêàæåì doom.wad îíà áóäåò íåñêîëüêî ïîáîëüøå, êàê å¸ ÷èñëåííî
EG> èçìåðèòü?
ñòåïåíüþ ñæàòèÿ. àáñîëþòíîãî, íåçàâèñèìîãî îò àðõèâàòîðîâ, ÷èñëà íåò
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722
... Èíîãäà äëÿ òîãî, ÷òîáû èçìåíèòü ñâîå âîñïðèÿòèå ìèðà,
... ëþäè ïûòàþòñÿ èçìåíèòü ñàì ìèð
--- GoldED+/W32 1.1.2
* Origin: À ÷åì çàíèìàåòñÿ õåðîìàíòèÿ? (2:5093/28.126)
— RU.COMPRESS
From : Andrew Aksyonoff 2:5036/29.2 26 Jul 00 01:05:03
To : Eugene Goncharuk
Subj : Ýíòðîïèÿ
Hello Eugene!
26 Jul 00 01:00, Eugene Goncharuk wrote to All:
EG> Êàê èçìåðèòü ýíòðîïèþ ôàéëà ?
Âñÿ ïðîáëåìà â òîì, ÷òî îíà çàâèñèò îò èñïîëüçóåìîé ìîäåëè
èñòî÷íèêà äàííûõ. ×åì ëó÷øå ìîäåëü, òåì ìåíüøå ýíòðîïèÿ. ;)
- Andrew
... and thinking is not really something they are cut out for...
--- ged386-pl2.50-dos &
* Origin: unknown. (2:5036/29.2)
— RU.COMPRESS
From : Eugene Goncharuk 2:5045/27.51 26 Jul 00 02:00:28
To : All
Subj : Ýíòðîïèÿ
Êàê ïîæèâàåòå, All ?
Êàê èçìåðèòü ýíòðîïèþ ôàéëà ?
ß òàê ïîëàãàþ, ÷òî ó ôàéëà ñîñòîÿùåãî èç íóëåé îíà áóäåò ìààëåíüêàÿ à
ó ñêàæåì doom.wad îíà áóäåò íåñêîëüêî ïîáîëüøå, êàê å¸ ÷èñëåííî èçìåðèòü?
C óâàæåíèåì, Eugene Goncharuk.
--- ÓÒÂÅÐÆÄÀÞ. MSG-ðåäàêòîð êàïèòàí 2.5 ðàíãà Ãîëä Äåäîâè÷ ôîð ÄÎÑ UNREG
* Origin: Êàê SP íå èñïðàâëÿé, îí âñå â ñòåê ñìîòðèò (2:5045/27.51)
— RU.COMPRESS
From : ZAB 2:5020/400 26 Jul 00 02:31:12
To : All
Subj : Re: ×òî ïîñîâåòóåòå?
From: "ZAB" <ZAnatolyB@mail.ru>
Vadim Yoockin <vy@thermosyn.com> ñîîáùèë â íîâîñòÿõ
ñëåäóþùåå:8ljevp$bb8$1@news.kiev.sovam.com...
> Hello, ZAB ! You wrote:
>
> >Ìîæåò ÿ ÷¸ íå ïîíèìàþ â òåîðèè, íî ïî õåøó íå òàê ïðîñòî èíäåêñèðîâàòüñÿ,
> >íóæíà ïðîöåäóðà ïîèñêà!
>
> Çàòî õýø áîëåå óñòîé÷èâ ê áîëüøîìó êîëè÷åñòâó ïîõîæèõ êîíòåêñòîâ.
>
> >ß óæå òàê ñäàëàë, ò.å. ñîáèðàþ ìàññèâ èç N 4-¸õ
> >áàéòíûõ ýëåìåíòîâ (êîíòåêñòîâ), è åù¸ îäèí òàêîé æå, íî âìåñòî êîíòåêñòîâ
â
> >í¸ì èíäåêñû íà èñõîäíûé áëîê, ïîòîì åù¸ ìàññèâ 0..65535 äëÿ òîãî, ÷òîáû
> >áèíàðíûé ïîèñê ïî ïåðâîìó ìàññèâó íà÷èíàëñÿ ñ äèàïîçîíà íà áîëåå 655536,
> >ò.å. ýòîò òðåòèé ìàññèâ ÿâëÿåòñÿ òàáëèöåé èíäåêñîâ íà ïåðâûå 2 áàéòà
> >êîíòåêñòîâ! Ïîìîåìó ðåàëèçà÷èÿ âïîëíå îïòèìàëüíà, ïî êðàéíåé ìåðå äëÿ
> >îáðàòíîãî ïðåîáðàçîâàíèÿ 3-¸õ ìåãàáàéò (âñåõ öåëèêîì, îäíèì áëîêîì) åé
íàäî
> >~3,5 ñåêóíäû!
>
> À åñëè âåñü áëîê ñîñòîèò èç îäèíàêîâûõ ñèìâîëîâ, ñêîëüêî òðåáóåòñÿ
âðåìåíè?
> ;)
Óïàêîâêà 8 ñåê! Ðàñïàêîâêà 8 ñåê!
> Êñòàòè, äëÿ ÷èñòîòû ýêñïåðèìåíòà ñðàâíè ñ szip'îì.
> >ÇÛ: Äëÿ øèôðîâêè òðåáóåòñÿ 4,5 ñåêóíä! Êòî ñêàçàë, ÷òî ðàñïàêîâêà
> >òîðìîçíóòåå?
>
> À ýòî ñòðàííî. Ìîæåò, ó òåáÿ ïðÿìîå ïðåîáðàçîâàíèå êàêîå-òî íå òî?
> Òàì æå äåëîâ-òî - íà ïàðó ïðîõîäîâ radix-sort'à.
Ðàäèêñ, ýòî òîò, ÷òî íà äâà ìàññèâà äåëèò? Ó ìåíÿ íå îí, ÿ ïî áèòàì
ñîðòèðóþ, èìåííî ïî ýòîìó è âûøåë òîðìîç, ïðè îäíîðîäíîì ñîäåðæèìûì, åìó
ïðèøëîñü êàæäûé ðàç âåñü ìàññèâ ñîðòèðîâàòü (äëÿ êàæäîãî áèòà è èíäåêñà - 64
ðàçà)!
> >ÇÇÛ: Ïîñëå îïòèìèçàöèè ïðîöåäóð ñîðòèðîâêè:
> >ïàêîâêà (ïðåîáðàçîâàíèå): 4,203 ñåê
> >ðàñïàêîâêà (ïðåîáðàçîâàíèå): 3,3 ñåê
> >Æð¸ò 35 ìåãîâ â ïèêîâîé íàãðóçêå è ìíå êàæåòñÿ, ÷òî óìåíüøàòü ðàçìåð
áëîêà
> >ìåííåå 3-¸õ ìåãàáàéò íåò íåîáõîäèìîñòè!
>
> Ýòî äà.
> >ÇÇÇÛ: Êñòàòè! Êàêîé ïîðÿäîê êîíòåêñòîâ äà¸ò ëó÷øèé ðåçóëüòàò? Àòî
äîäåëàòü
> >ýòî äî 8 - 12 ìîæíî áåç ïîòåðü â ñêîðîñòü áîëåå 1 ñåêóíäû!
>
> Çà èñêëþ÷åíèåì íåêîòîðûõ äàííûõ, ÷åì áîëüøå - òåì ëó÷øå.
> Hà áîëüøèíñòâå òåêñòîâ 8-12 áóäåò âïîëíå äîñòàòî÷íî.
Ëàäíî! Çíà÷èò áóäó äîðàáàòûâàòü äî 12!
ÇÛ: Ñîâñåì çàáûë î ìàøèíå! P-III 500 (ðàçîãíàí ïî øèíå äî 560) 64 ìåãà
îïåðàòèâêè!
--- ifmail v.2.15dev5
* Origin: NeoToN (2:5020/400)
— RU.COMPRESS
From : ZAB 2:5020/400 26 Jul 00 02:31:15
To : All
Subj : Re: ×òî ïîñîâåòóåòå?
From: "ZAB" <ZAnatolyB@Mail.ru>
Vadim Yoockin <vy@thermosyn.com> ñîîáùèë â íîâîñòÿõ
ñëåäóþùåå:8ljevp$bb8$1@news.kiev.sovam.com...
> Hello, ZAB ! You wrote:
>
> >Ìîæåò ÿ ÷¸ íå ïîíèìàþ â òåîðèè, íî ïî õåøó íå òàê ïðîñòî èíäåêñèðîâàòüñÿ,
> >íóæíà ïðîöåäóðà ïîèñêà!
>
> Çàòî õýø áîëåå óñòîé÷èâ ê áîëüøîìó êîëè÷åñòâó ïîõîæèõ êîíòåêñòîâ.
>
> >ß óæå òàê ñäàëàë, ò.å. ñîáèðàþ ìàññèâ èç N 4-¸õ
> >áàéòíûõ ýëåìåíòîâ (êîíòåêñòîâ), è åù¸ îäèí òàêîé æå, íî âìåñòî êîíòåêñòîâ
â
> >í¸ì èíäåêñû íà èñõîäíûé áëîê, ïîòîì åù¸ ìàññèâ 0..65535 äëÿ òîãî, ÷òîáû
> >áèíàðíûé ïîèñê ïî ïåðâîìó ìàññèâó íà÷èíàëñÿ ñ äèàïîçîíà íà áîëåå 655536,
> >ò.å. ýòîò òðåòèé ìàññèâ ÿâëÿåòñÿ òàáëèöåé èíäåêñîâ íà ïåðâûå 2 áàéòà
> >êîíòåêñòîâ! Ïîìîåìó ðåàëèçà÷èÿ âïîëíå îïòèìàëüíà, ïî êðàéíåé ìåðå äëÿ
> >îáðàòíîãî ïðåîáðàçîâàíèÿ 3-¸õ ìåãàáàéò (âñåõ öåëèêîì, îäíèì áëîêîì) åé
íàäî
> >~3,5 ñåêóíäû!
>
> À åñëè âåñü áëîê ñîñòîèò èç îäèíàêîâûõ ñèìâîëîâ, ñêîëüêî òðåáóåòñÿ
âðåìåíè?
> ;)
Óïàêîâêà 8 ñåê! Ðàñïàêîâêà 8 ñåê!
> Êñòàòè, äëÿ ÷èñòîòû ýêñïåðèìåíòà ñðàâíè ñ szip'îì.
> >ÇÛ: Äëÿ øèôðîâêè òðåáóåòñÿ 4,5 ñåêóíä! Êòî ñêàçàë, ÷òî ðàñïàêîâêà
> >òîðìîçíóòåå?
>
> À ýòî ñòðàííî. Ìîæåò, ó òåáÿ ïðÿìîå ïðåîáðàçîâàíèå êàêîå-òî íå òî?
> Òàì æå äåëîâ-òî - íà ïàðó ïðîõîäîâ radix-sort'à.
Ðàäèêñ, ýòî òîò, ÷òî íà äâà ìàññèâà äåëèò? Ó ìåíÿ íå îí, ÿ ïî áèòàì
ñîðòèðóþ, èìåííî ïî ýòîìó è âûøåë òîðìîç, ïðè îäíîðîäíîì ñîäåðæèìûì, åìó
ïðèøëîñü êàæäûé ðàç âåñü ìàññèâ ñîðòèðîâàòü (äëÿ êàæäîãî áèòà è èíäåêñà - 64
ðàçà)!
> >ÇÇÛ: Ïîñëå îïòèìèçàöèè ïðîöåäóð ñîðòèðîâêè:
> >ïàêîâêà (ïðåîáðàçîâàíèå): 4,203 ñåê
> >ðàñïàêîâêà (ïðåîáðàçîâàíèå): 3,3 ñåê
> >Æð¸ò 35 ìåãîâ â ïèêîâîé íàãðóçêå è ìíå êàæåòñÿ, ÷òî óìåíüøàòü ðàçìåð
áëîêà
> >ìåííåå 3-¸õ ìåãàáàéò íåò íåîáõîäèìîñòè!
>
> Ýòî äà.
> >ÇÇÇÛ: Êñòàòè! Êàêîé ïîðÿäîê êîíòåêñòîâ äà¸ò ëó÷øèé ðåçóëüòàò? Àòî
äîäåëàòü
> >ýòî äî 8 - 12 ìîæíî áåç ïîòåðü â ñêîðîñòü áîëåå 1 ñåêóíäû!
>
> Çà èñêëþ÷åíèåì íåêîòîðûõ äàííûõ, ÷åì áîëüøå - òåì ëó÷øå.
> Hà áîëüøèíñòâå òåêñòîâ 8-12 áóäåò âïîëíå äîñòàòî÷íî.
Ëàäíî! Çíà÷èò áóäó äîðàáàòûâàòü äî 12!
ÇÛ: Ñîâñåì çàáûë î ìàøèíå! P-III 500 (ðàçîãíàí ïî øèíå äî 560) 64 ìåãà
îïåðàòèâêè!
--- ifmail v.2.15dev5
* Origin: NeoToN (2:5020/400)
— RU.COMPRESS
From : ZAB 2:5020/400 26 Jul 00 02:31:27
To : All
Subj : Re: ×òî ïîñîâåòóåòå?
From: "ZAB" <ZAnatolyB@mail.ru>
Vadim Yoockin <vy@thermosyn.com> ñîîáùèë â íîâîñòÿõ
ñëåäóþùåå:8ljevp$bb8$1@news.kiev.sovam.com...
> Hello, ZAB ! You wrote:
>
> >Ìîæåò ÿ ÷¸ íå ïîíèìàþ â òåîðèè, íî ïî õåøó íå òàê ïðîñòî èíäåêñèðîâàòüñÿ,
> >íóæíà ïðîöåäóðà ïîèñêà!
>
> Çàòî õýø áîëåå óñòîé÷èâ ê áîëüøîìó êîëè÷åñòâó ïîõîæèõ êîíòåêñòîâ.
>
> >ß óæå òàê ñäàëàë, ò.å. ñîáèðàþ ìàññèâ èç N 4-¸õ
> >áàéòíûõ ýëåìåíòîâ (êîíòåêñòîâ), è åù¸ îäèí òàêîé æå, íî âìåñòî êîíòåêñòîâ
â
> >í¸ì èíäåêñû íà èñõîäíûé áëîê, ïîòîì åù¸ ìàññèâ 0..65535 äëÿ òîãî, ÷òîáû
> >áèíàðíûé ïîèñê ïî ïåðâîìó ìàññèâó íà÷èíàëñÿ ñ äèàïîçîíà íà áîëåå 655536,
> >ò.å. ýòîò òðåòèé ìàññèâ ÿâëÿåòñÿ òàáëèöåé èíäåêñîâ íà ïåðâûå 2 áàéòà
> >êîíòåêñòîâ! Ïîìîåìó ðåàëèçà÷èÿ âïîëíå îïòèìàëüíà, ïî êðàéíåé ìåðå äëÿ
> >îáðàòíîãî ïðåîáðàçîâàíèÿ 3-¸õ ìåãàáàéò (âñåõ öåëèêîì, îäíèì áëîêîì) åé
íàäî
> >~3,5 ñåêóíäû!
>
> À åñëè âåñü áëîê ñîñòîèò èç îäèíàêîâûõ ñèìâîëîâ, ñêîëüêî òðåáóåòñÿ
âðåìåíè?
> ;)
Óïàêîâêà 8 ñåê! Ðàñïàêîâêà 8 ñåê!
> Êñòàòè, äëÿ ÷èñòîòû ýêñïåðèìåíòà ñðàâíè ñ szip'îì.
> >ÇÛ: Äëÿ øèôðîâêè òðåáóåòñÿ 4,5 ñåêóíä! Êòî ñêàçàë, ÷òî ðàñïàêîâêà
> >òîðìîçíóòåå?
>
> À ýòî ñòðàííî. Ìîæåò, ó òåáÿ ïðÿìîå ïðåîáðàçîâàíèå êàêîå-òî íå òî?
> Òàì æå äåëîâ-òî - íà ïàðó ïðîõîäîâ radix-sort'à.
Ðàäèêñ, ýòî òîò, ÷òî íà äâà ìàññèâà äåëèò? Ó ìåíÿ íå îí, ÿ ïî áèòàì
ñîðòèðóþ, èìåííî ïî ýòîìó è âûøåë òîðìîç, ïðè îäíîðîäíîì ñîäåðæèìûì, åìó
ïðèøëîñü êàæäûé ðàç âåñü ìàññèâ ñîðòèðîâàòü (äëÿ êàæäîãî áèòà è èíäåêñà - 64
ðàçà)!
> >ÇÇÛ: Ïîñëå îïòèìèçàöèè ïðîöåäóð ñîðòèðîâêè:
> >ïàêîâêà (ïðåîáðàçîâàíèå): 4,203 ñåê
> >ðàñïàêîâêà (ïðåîáðàçîâàíèå): 3,3 ñåê
> >Æð¸ò 35 ìåãîâ â ïèêîâîé íàãðóçêå è ìíå êàæåòñÿ, ÷òî óìåíüøàòü ðàçìåð
áëîêà
> >ìåííåå 3-¸õ ìåãàáàéò íåò íåîáõîäèìîñòè!
>
> Ýòî äà.
> >ÇÇÇÛ: Êñòàòè! Êàêîé ïîðÿäîê êîíòåêñòîâ äà¸ò ëó÷øèé ðåçóëüòàò? Àòî
äîäåëàòü
> >ýòî äî 8 - 12 ìîæíî áåç ïîòåðü â ñêîðîñòü áîëåå 1 ñåêóíäû!
>
> Çà èñêëþ÷åíèåì íåêîòîðûõ äàííûõ, ÷åì áîëüøå - òåì ëó÷øå.
> Hà áîëüøèíñòâå òåêñòîâ 8-12 áóäåò âïîëíå äîñòàòî÷íî.
Ëàäíî! Çíà÷èò áóäó äîðàáàòûâàòü äî 12!
ÇÛ: Ñîâñåì çàáûë î ìàøèíå! P-III 500 (ðàçîãíàí ïî øèíå äî 560) 64 ìåãà
îïåðàòèâêè!
--- ifmail v.2.15dev5
* Origin: NeoToN (2:5020/400)
— RU.COMPRESS
From : ZAB 2:5020/400 26 Jul 00 02:31:29
To : All
Subj : Re: ×òî ïîñîâåòóåòå?
From: "ZAB" <ZAnatolyB@Mail.ru>
Vadim Yoockin <vy@thermosyn.com> ñîîáùèë â íîâîñòÿõ
ñëåäóþùåå:8ljevp$bb8$1@news.kiev.sovam.com...
> Hello, ZAB ! You wrote:
>
> >Ìîæåò ÿ ÷¸ íå ïîíèìàþ â òåîðèè, íî ïî õåøó íå òàê ïðîñòî èíäåêñèðîâàòüñÿ,
> >íóæíà ïðîöåäóðà ïîèñêà!
>
> Çàòî õýø áîëåå óñòîé÷èâ ê áîëüøîìó êîëè÷åñòâó ïîõîæèõ êîíòåêñòîâ.
>
> >ß óæå òàê ñäàëàë, ò.å. ñîáèðàþ ìàññèâ èç N 4-¸õ
> >áàéòíûõ ýëåìåíòîâ (êîíòåêñòîâ), è åù¸ îäèí òàêîé æå, íî âìåñòî êîíòåêñòîâ
â
> >í¸ì èíäåêñû íà èñõîäíûé áëîê, ïîòîì åù¸ ìàññèâ 0..65535 äëÿ òîãî, ÷òîáû
> >áèíàðíûé ïîèñê ïî ïåðâîìó ìàññèâó íà÷èíàëñÿ ñ äèàïîçîíà íà áîëåå 655536,
> >ò.å. ýòîò òðåòèé ìàññèâ ÿâëÿåòñÿ òàáëèöåé èíäåêñîâ íà ïåðâûå 2 áàéòà
> >êîíòåêñòîâ! Ïîìîåìó ðåàëèçà÷èÿ âïîëíå îïòèìàëüíà, ïî êðàéíåé ìåðå äëÿ
> >îáðàòíîãî ïðåîáðàçîâàíèÿ 3-¸õ ìåãàáàéò (âñåõ öåëèêîì, îäíèì áëîêîì) åé
íàäî
> >~3,5 ñåêóíäû!
>
> À åñëè âåñü áëîê ñîñòîèò èç îäèíàêîâûõ ñèìâîëîâ, ñêîëüêî òðåáóåòñÿ
âðåìåíè?
> ;)
Óïàêîâêà 8 ñåê! Ðàñïàêîâêà 8 ñåê!
> Êñòàòè, äëÿ ÷èñòîòû ýêñïåðèìåíòà ñðàâíè ñ szip'îì.
> >ÇÛ: Äëÿ øèôðîâêè òðåáóåòñÿ 4,5 ñåêóíä! Êòî ñêàçàë, ÷òî ðàñïàêîâêà
> >òîðìîçíóòåå?
>
> À ýòî ñòðàííî. Ìîæåò, ó òåáÿ ïðÿìîå ïðåîáðàçîâàíèå êàêîå-òî íå òî?
> Òàì æå äåëîâ-òî - íà ïàðó ïðîõîäîâ radix-sort'à.
Ðàäèêñ, ýòî òîò, ÷òî íà äâà ìàññèâà äåëèò? Ó ìåíÿ íå îí, ÿ ïî áèòàì
ñîðòèðóþ, èìåííî ïî ýòîìó è âûøåë òîðìîç, ïðè îäíîðîäíîì ñîäåðæèìûì, åìó
ïðèøëîñü êàæäûé ðàç âåñü ìàññèâ ñîðòèðîâàòü (äëÿ êàæäîãî áèòà è èíäåêñà - 64
ðàçà)!
> >ÇÇÛ: Ïîñëå îïòèìèçàöèè ïðîöåäóð ñîðòèðîâêè:
> >ïàêîâêà (ïðåîáðàçîâàíèå): 4,203 ñåê
> >ðàñïàêîâêà (ïðåîáðàçîâàíèå): 3,3 ñåê
> >Æð¸ò 35 ìåãîâ â ïèêîâîé íàãðóçêå è ìíå êàæåòñÿ, ÷òî óìåíüøàòü ðàçìåð
áëîêà
> >ìåííåå 3-¸õ ìåãàáàéò íåò íåîáõîäèìîñòè!
>
> Ýòî äà.
> >ÇÇÇÛ: Êñòàòè! Êàêîé ïîðÿäîê êîíòåêñòîâ äà¸ò ëó÷øèé ðåçóëüòàò? Àòî
äîäåëàòü
> >ýòî äî 8 - 12 ìîæíî áåç ïîòåðü â ñêîðîñòü áîëåå 1 ñåêóíäû!
>
> Çà èñêëþ÷åíèåì íåêîòîðûõ äàííûõ, ÷åì áîëüøå - òåì ëó÷øå.
> Hà áîëüøèíñòâå òåêñòîâ 8-12 áóäåò âïîëíå äîñòàòî÷íî.
Ëàäíî! Çíà÷èò áóäó äîðàáàòûâàòü äî 12!
ÇÛ: Ñîâñåì çàáûë î ìàøèíå! P-III 500 (ðàçîãíàí ïî øèíå äî 560) 64 ìåãà
îïåðàòèâêè!
--- ifmail v.2.15dev5
* Origin: NeoToN (2:5020/400)
— RU.COMPRESS
From : ZAB 2:5020/400 26 Jul 00 02:31:31
To : All
Subj : Re: ×òî ïîñîâåòóåòå?
From: "ZAB" <ZAnatolyB@mail.ru>
Vadim Yoockin <vy@thermosyn.com> ñîîáùèë â íîâîñòÿõ
ñëåäóþùåå:8ljevp$bb8$1@news.kiev.sovam.com...
> Hello, ZAB ! You wrote:
>
> >Ìîæåò ÿ ÷¸ íå ïîíèìàþ â òåîðèè, íî ïî õåøó íå òàê ïðîñòî èíäåêñèðîâàòüñÿ,
> >íóæíà ïðîöåäóðà ïîèñêà!
>
> Çàòî õýø áîëåå óñòîé÷èâ ê áîëüøîìó êîëè÷åñòâó ïîõîæèõ êîíòåêñòîâ.
>
> >ß óæå òàê ñäàëàë, ò.å. ñîáèðàþ ìàññèâ èç N 4-¸õ
> >áàéòíûõ ýëåìåíòîâ (êîíòåêñòîâ), è åù¸ îäèí òàêîé æå, íî âìåñòî êîíòåêñòîâ
â
> >í¸ì èíäåêñû íà èñõîäíûé áëîê, ïîòîì åù¸ ìàññèâ 0..65535 äëÿ òîãî, ÷òîáû
> >áèíàðíûé ïîèñê ïî ïåðâîìó ìàññèâó íà÷èíàëñÿ ñ äèàïîçîíà íà áîëåå 655536,
> >ò.å. ýòîò òðåòèé ìàññèâ ÿâëÿåòñÿ òàáëèöåé èíäåêñîâ íà ïåðâûå 2 áàéòà
> >êîíòåêñòîâ! Ïîìîåìó ðåàëèçà÷èÿ âïîëíå îïòèìàëüíà, ïî êðàéíåé ìåðå äëÿ
> >îáðàòíîãî ïðåîáðàçîâàíèÿ 3-¸õ ìåãàáàéò (âñåõ öåëèêîì, îäíèì áëîêîì) åé
íàäî
> >~3,5 ñåêóíäû!
>
> À åñëè âåñü áëîê ñîñòîèò èç îäèíàêîâûõ ñèìâîëîâ, ñêîëüêî òðåáóåòñÿ
âðåìåíè?
> ;)
Óïàêîâêà 8 ñåê! Ðàñïàêîâêà 8 ñåê!
> Êñòàòè, äëÿ ÷èñòîòû ýêñïåðèìåíòà ñðàâíè ñ szip'îì.
> >ÇÛ: Äëÿ øèôðîâêè òðåáóåòñÿ 4,5 ñåêóíä! Êòî ñêàçàë, ÷òî ðàñïàêîâêà
> >òîðìîçíóòåå?
>
> À ýòî ñòðàííî. Ìîæåò, ó òåáÿ ïðÿìîå ïðåîáðàçîâàíèå êàêîå-òî íå òî?
> Òàì æå äåëîâ-òî - íà ïàðó ïðîõîäîâ radix-sort'à.
Ðàäèêñ, ýòî òîò, ÷òî íà äâà ìàññèâà äåëèò? Ó ìåíÿ íå îí, ÿ ïî áèòàì
ñîðòèðóþ, èìåííî ïî ýòîìó è âûøåë òîðìîç, ïðè îäíîðîäíîì ñîäåðæèìûì, åìó
ïðèøëîñü êàæäûé ðàç âåñü ìàññèâ ñîðòèðîâàòü (äëÿ êàæäîãî áèòà è èíäåêñà - 64
ðàçà)!
> >ÇÇÛ: Ïîñëå îïòèìèçàöèè ïðîöåäóð ñîðòèðîâêè:
> >ïàêîâêà (ïðåîáðàçîâàíèå): 4,203 ñåê
> >ðàñïàêîâêà (ïðåîáðàçîâàíèå): 3,3 ñåê
> >Æð¸ò 35 ìåãîâ â ïèêîâîé íàãðóçêå è ìíå êàæåòñÿ, ÷òî óìåíüøàòü ðàçìåð
áëîêà
> >ìåííåå 3-¸õ ìåãàáàéò íåò íåîáõîäèìîñòè!
>
> Ýòî äà.
> >ÇÇÇÛ: Êñòàòè! Êàêîé ïîðÿäîê êîíòåêñòîâ äà¸ò ëó÷øèé ðåçóëüòàò? Àòî
äîäåëàòü
> >ýòî äî 8 - 12 ìîæíî áåç ïîòåðü â ñêîðîñòü áîëåå 1 ñåêóíäû!
>
> Çà èñêëþ÷åíèåì íåêîòîðûõ äàííûõ, ÷åì áîëüøå - òåì ëó÷øå.
> Hà áîëüøèíñòâå òåêñòîâ 8-12 áóäåò âïîëíå äîñòàòî÷íî.
Ëàäíî! Çíà÷èò áóäó äîðàáàòûâàòü äî 12!
ÇÛ: Ñîâñåì çàáûë î ìàøèíå! P-III 500 (ðàçîãíàí ïî øèíå äî 560) 64 ìåãà
îïåðàòèâêè!
--- ifmail v.2.15dev5
* Origin: NeoToN (2:5020/400)
— RU.COMPRESS
From : Vladimir Vassilevsky 2:5020/400 26 Jul 00 02:35:54
To : All
Subj : Re: Óïàêîâêà ñèãíàëà â real-time
From: Vladimir Vassilevsky <vlv@fullnet.net>
Andre N Belokon wrote:
>
> Vladimir Vassilevsky <vlv@fullnet.net> ñîîáùèë â íîâîñòÿõ
> ñëåäóþùåå:3972F93E.7E0D43C2@fullnet.net...
> > Hàïðèìåð, ïðåäñêàçàòåëü ïåðâîãî
> > ïîðÿäêà èäåàëüíî ïðåäñêàçûâàåò êîíñòàíòó, âòîðîãî ïîðÿäêà - ýêñïîíåíòû è
> > ñèíóñîèäû, áîëåå âûñîêèå ïîðÿäêè - áîëåå ñëîæíûå ñòàöèîíàðíûå ïðîöåññû.
> > Âû÷èñëåíèå êîýôôèöèåíòîâ ïðåäñêàçàíèÿ - äîñòàòî÷íî ñëîæíàÿ çàäà÷à,
> > êîòîðàÿ íå ëÿæåò â ïàëêó. Ïåðåäàâàòü íàäî òîëüêî òåêóùóþ îøèáêó
> > ïðåäñêàçàíèÿ. Ïðè äîñòàòî÷íî âûñîêîì ïîðÿäêå îøèáêà ïðåäñêàçàíèÿ
> > ÿâëÿåòñÿ [ïî÷òè] Ãàóññîâñêèì ñëó÷àéíûì ïðîöåññîì ñ ðàñïðåäåëåíèåì òèïà
> > exp(-x*x)
>
> ñêàæó ïàðó ñëîâ êàñàòåëüíî LPC. âîçèëñÿ ÿ ñ íèì ïðèìåíèòåëüíî ê âîïðîñó
> lossless êîìïðåññèè àóäèî-ñèãíàëîâ. ðàáîòà âåëàñü ñ íåñêîëüêèìè ìóçûêàëüíûìè
> CD-òðåêàìè. äèñêðåòèçàöèÿ 44100 16 áèò. ñèãíàë ðàçáèâàëñÿ íà ôðåéìû è äëÿ
> êàæäîãî ôðåéìà âû÷èñëÿëèñü êîýôôèöèåíòû LPC. è âîò ÷òî èíòåðåñíî - LPC
> âûñîêèõ ïîðÿäêîâ (10-12) ïîêàçûâàþò õóäøèé ðåçóëüòàò ïî ñðàâíåíèþ ñ áîëåå
> íèçêèìè ïîðÿäêàìè (3-5). ïîä õóäøèì ðåçóëüòàòîì ïîäðàçóìåâàåòñÿ áîëüøàÿ
> äèñïåðñèÿ îøèáêè ïðåäñêàçàíèÿ.
>
> "îáñêàêàë" âñåõ äðóãîé àëãîðèòì (íà âñÿêèé ñëó÷àé ñòàâèì (ñ) :)) àäàïòèâíîãî
> LPC. ñóòü ñëåäóþùàÿ. åñòü íåáîëüøîå îêíî. íà îñíîâàíèè îòñ÷åòîâ ýòîãî îêíà
> âû÷èñëÿåì LPC íåâûñîêîãî ïîðÿäêà. ïðåäñêàçûâàåì ñëåä. îòñ÷åò. ñäâèãàåì îêíî
> íà îäèí îòñ÷åò è äîáàâëÿåì òîëüêî ÷òî çàêîäèðîâàííûé îòñ÷åò â îêíî. + è -
> òàêîãî àëãîðèòìà: +êîýôôèöèåíòû LPC íèêîãäà íå ïåðåäàþòñÿ â ÿâíîì âèäå.
> +ïîâûøåííàÿ àäàïòèâíîñòü êî âõîäíîìó ñèãíàëó. -ìåíüøåå áûñòðîäåéñòâèå.
>
> áóäåò èíòåðåñíî óçíàòü ìíåíèå îáùåñòâåííîñòè - èçîáðåòåí âåëîñèïåä èëè
> âå÷íûé äâèãàòåëü ? :))
>
> PS åñëè êòî-òî ðàáîòàåò íàä âîïðîñàìè lossless êîïðåññèè àóäèîñèãíàëîâ è
> ñòàòè÷åñêèõ èçîáðàæåíèé - áóäåò èíòåðåñíî ïîîáùàòüñÿ
>
> --
> WBR Andre N Belokon
> http://softlab.od.ua
> http://algo.4u.ru
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
— RU.COMPRESS
From : Vladimir Vassilevsky 2:5020/400 26 Jul 00 02:37:12
To : All
Subj : Re: Óïàêîâêà ñèãíàëà â real-time
From: Vladimir Vassilevsky <vlv@fullnet.net>
Andre N Belokon wrote:
>
> ñêàæó ïàðó ñëîâ êàñàòåëüíî LPC. âîçèëñÿ ÿ ñ íèì ïðèìåíèòåëüíî ê âîïðîñó
> lossless êîìïðåññèè àóäèî-ñèãíàëîâ. ðàáîòà âåëàñü ñ íåñêîëüêèìè ìóçûêàëüíûìè
> CD-òðåêàìè.
:)))) Àíàëîãè÷íî.
> äèñêðåòèçàöèÿ 44100 16 áèò. ñèãíàë ðàçáèâàëñÿ íà ôðåéìû è äëÿ
> êàæäîãî ôðåéìà âû÷èñëÿëèñü êîýôôèöèåíòû LPC. è âîò ÷òî èíòåðåñíî - LPC
> âûñîêèõ ïîðÿäêîâ (10-12) ïîêàçûâàþò õóäøèé ðåçóëüòàò ïî ñðàâíåíèþ ñ áîëåå
> íèçêèìè ïîðÿäêàìè (3-5). ïîä õóäøèì ðåçóëüòàòîì ïîäðàçóìåâàåòñÿ áîëüøàÿ
> äèñïåðñèÿ îøèáêè ïðåäñêàçàíèÿ.
> "îáñêàêàë" âñåõ äðóãîé àëãîðèòì (íà âñÿêèé ñëó÷àé ñòàâèì (ñ) :)) àäàïòèâíîãî
> LPC. ñóòü ñëåäóþùàÿ. åñòü íåáîëüøîå îêíî. íà îñíîâàíèè îòñ÷åòîâ ýòîãî îêíà
> âû÷èñëÿåì LPC íåâûñîêîãî ïîðÿäêà. ïðåäñêàçûâàåì ñëåä. îòñ÷åò. ñäâèãàåì îêíî
> íà îäèí îòñ÷åò è äîáàâëÿåì òîëüêî ÷òî çàêîäèðîâàííûé îòñ÷åò â îêíî. + è -
> òàêîãî àëãîðèòìà: +êîýôôèöèåíòû LPC íèêîãäà íå ïåðåäàþòñÿ â ÿâíîì âèäå.
> +ïîâûøåííàÿ àäàïòèâíîñòü êî âõîäíîìó ñèãíàëó. -ìåíüøåå áûñòðîäåéñòâèå.
ß äåëàë òàê: âû÷èñëÿë LPC â ñêîëüçÿùåì îêíå, ïåðåñ÷èòûâàÿ êîýôôèöèåíòû
äëÿ êàæäîãî íîâîãî îòñ÷åòà, èñïîëüçóÿ äëÿ âû÷èñëåíèÿ ïðåäûäóùèå çíà÷åíèÿ
ñèãíàëà, ò.å. ñàìè êîýôô. ËÏÊ íå ïåðåäàþòñÿ. Îïòèìàëüíûé ïîðÿäîê LPC äëÿ
ìóçûêè 44khz/16bit ïîëó÷àëñÿ ~ 64, äëèíà îêíà ~ 512 îòñ÷åòîâ. Ôîðìà îêíà
òîæå ñóùåñòâåííà - íàèëó÷øèå ðåçóëüòàòû ïîëó÷àëèñü ñ îêíîì Õåììèíãà (à
âîâñå íå Áàðíâåëëà, êàê íè ñòðàííî). Âûèãðûø îò ËÏÊ ïîëó÷àëñÿ ïîðÿäêà
20dB, è åùå ïîðÿäêà 3dB ìîæåò äàòü ïðåäñêàçàíèå îñíîâíîãî òîíà.
Îñòàòî÷íàÿ îøèáêà äîæèìàåòñÿ ïî Õàôôìàíó. Ïðè ñæàòèè áåç ïîòåðü ìîæíî
ñúåêîíîìèòü ïðèìåðíî äî âîñüìè áèò íà îòñ÷åò, âïðî÷åì, ýòî âåñüìà
çàâèñèò îò ñîäåðæàíèÿ òðåêà.
> áóäåò èíòåðåñíî óçíàòü ìíåíèå îáùåñòâåííîñòè - èçîáðåòåí âåëîñèïåä èëè
> âå÷íûé äâèãàòåëü ? :))
Òåõíîëîãèÿ ñ âû÷èñëåíèåì êîýôô. ËÏÊ ïî ñèãíàëó õîðîøî èçâåñòíà è
èñïîëüçóåòñÿ, íàïðèìåð, â ñòàíäàðòå LDCELP G.728. Ó ýòîé òåõíîëîãèè åñòü
òðè îñíîâíûõ íåäîñòàòêà:
1. Ïðè áûñòðîì èçìåíåíèè ñïåêòðà ñèãíàëà ËÏÊ àäàïòèðóåòñÿ íå îïòèìàëüíûì
îáðàçîì.
2. Åñëè àëãîðèòì ñæàòèÿ ñ ïîòåðÿìè, òî ïðè íåêîòîðûõ óñëîâèÿõ ïîëó÷àåòñÿ
ðàçìíîæåíèå ïîòåðü.
3. Áîëüøîé îáúåì âû÷èñëåíèé.
> PS åñëè êòî-òî ðàáîòàåò íàä âîïðîñàìè lossless êîïðåññèè àóäèîñèãíàëîâ è
> ñòàòè÷åñêèõ èçîáðàæåíèé - áóäåò èíòåðåñíî ïîîáùàòüñÿ
Ìû òàê, ïëþøêàìè áàëóåìñÿ.
Âîîáùå-òî ñóùåñòâóåò ôîðìàò MLP (Meridian Loseless Packing, åñëè íå
ïîäâîäèò ïàìÿòü), ñïåöèàëüíî äëÿ ñæàòèÿ àóäèî áåç ïîòåðü. Òî÷íî íå çíàþ,
êàê ïîñòðîåí èõ àëãîðèòì, íî ñæàòèå ïðèìåðíî äâóõêðàòíîå.
VLV
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
— RU.COMPRESS
From : Alexey Komarov 2:5054/66.1 26 Jul 00 02:45:22
To : Eugene Goncharuk
Subj : Ýíòpîïèÿ
Ïpèâåò, Eugene!
26 Èþë 00 â 02:00 òû ïèñàë All:
EG> Êàê èçìåpèòü ýíòpîïèþ ôàéëà ?
À õîòÿ áû äèñïåpñèþ äëÿ íà÷àëà ïîñ÷èòàòü è ñpàâíèòü ñ íàéäåííîé äëÿ èçâåñòíûõ ò
èïîâ ôàéëîâ? Òàì yæå âàpèàíòû...
Ïpîñòîé ñïîñîá - ïî ñòåïåíè ñæàòèÿ èçâåñòíûìè àpõèâàòîpàìè :))
EG> ß òàê ïîëàãàþ, ÷òî y ôàéëà ñîñòîÿùåãî èç íyëåé îíà áyäåò ìààëåíüêàÿ à
EG> y ñêàæåì doom.wad îíà áyäåò íåñêîëüêî ïîáîëüøå, êàê å¸ ÷èñëåííî
EG> èçìåpèòü?
À îíà âîîáùå èìååò òî÷íîå êîëè÷åñòâåííîå îïpåäåëåíèå? :-\
Ñ yâàæåíèåì,
Alexey
--- GoldED+/W32 1.1.4.5
* Origin: KewlZyzop of MelodyHacker station (2:5054/66.1)
— RU.COMPRESS
From : Andre N Belokon 2:5020/400 26 Jul 00 04:50:57
To : All
Subj : Re: Óïàêîâêà ñèãíàëà â real-time
From: "Andre N Belokon" <algo@softlab.od.ua>
Reply-To: "Andre N Belokon" <algo@softlab.od.ua>
Vladimir Vassilevsky <vlv@fullnet.net> ñîîáùèë â íîâîñòÿõ
ñëåäóþùåå:397D7DF3.A4416E75@fullnet.net...
> ß äåëàë òàê: âû÷èñëÿë LPC â ñêîëüçÿùåì îêíå, ïåðåñ÷èòûâàÿ êîýôôèöèåíòû
> äëÿ êàæäîãî íîâîãî îòñ÷åòà, èñïîëüçóÿ äëÿ âû÷èñëåíèÿ ïðåäûäóùèå çíà÷åíèÿ
> ñèãíàëà, ò.å. ñàìè êîýôô. ËÏÊ íå ïåðåäàþòñÿ.
äåëàë òîæå ñàìîå
> Îïòèìàëüíûé ïîðÿäîê LPC äëÿ
> ìóçûêè 44khz/16bit ïîëó÷àëñÿ ~ 64, äëèíà îêíà ~ 512 îòñ÷åòîâ.
wow - ïîðÿäîê 64 - ýòî íå ñèëüíî ëè ìíîãî ???
î÷åíü ñèëüíî çàâèñèò îò òèïà ñèãíàëà. íà "æåñòêèõ" äæàç-ðîêîâûõ êîìïîçèöèÿõ
îêíî è ïîðÿäîê ãîðàçäî ìåíüøå - ÿ âûõîäèë íà ïîðÿäîê 3-7 ïðè îêíå 32-64.
> Ôîðìà îêíà
> òîæå ñóùåñòâåííà - íàèëó÷øèå ðåçóëüòàòû ïîëó÷àëèñü ñ îêíîì Õåììèíãà (à
> âîâñå íå Áàðíâåëëà, êàê íè ñòðàííî).
ñ îêíîì âîîáùå íè÷åãî íå äåëàë - ïðÿìîóãîëüíîå òîåñòü. íàäî áóäåò
ïîïðîáîâàòü
> Âûèãðûø îò ËÏÊ ïîëó÷àëñÿ ïîðÿäêà
> 20dB
ñòðàííî, ÿ âûõîäèë íà áîëüøèå öèôðû, õîòÿ è íå íàìíîãî.
> è åùå ïîðÿäêà 3dB ìîæåò äàòü ïðåäñêàçàíèå îñíîâíîãî òîíà.
imho õîðîøî äëÿ speech, íî íå äëÿ audio
> Îñòàòî÷íàÿ îøèáêà äîæèìàåòñÿ ïî Õàôôìàíó.
òóò òîæå åñòü íàä ÷åì ïîäóìàòü. ýòî âñåòàêè íå àëôàâèò èç 256 ñèìâîëîâ
äîæèìàòü.
> Ìû òàê, ïëþøêàìè áàëóåìñÿ.
> Âîîáùå-òî ñóùåñòâóåò ôîðìàò MLP (Meridian Loseless Packing, åñëè íå
> ïîäâîäèò ïàìÿòü), ñïåöèàëüíî äëÿ ñæàòèÿ àóäèî áåç ïîòåðü. Òî÷íî íå çíàþ,
> êàê ïîñòðîåí èõ àëãîðèòì, íî ñæàòèå ïðèìåðíî äâóõêðàòíîå.
2õ êðàòíîå - ìàëî. ÿ òóò ñ íåéðîñåòêàìè â êà÷åñòâå ïðåäèêòîðà ïîáàëîâàëñÿ -
ðåçóëüòàòû áîëåå ÷åì âïå÷àòëÿþùèå, õîòÿ ïðîöåññ ñæàòèÿ äþæå ìåäëåííûé. imho
ðåàëüíî äîñòè÷ü òèïè÷íîãî ñæàòèÿ 1:3 - 1:5 è 1:2 íà î÷åíü "ïëîõîì ñèãíàëå".
--
WBR Andre N Belokon
http://softlab.od.ua
http://algo.4u.ru
--- ifmail v.2.15dev5
* Origin: Rostelecom/Internet Centre (2:5020/400)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/400 26 Jul 00 10:20:56
To : ZAB
Subj : Re: ×òî ïîñîâåòóåòå?
From: "Vadim Yoockin" <vy@thermosyn.com>
Hello, ZAB ! You wrote:
>> À åñëè âåñü áëîê ñîñòîèò èç îäèíàêîâûõ ñèìâîëîâ, ñêîëüêî òðåáóåòñÿ
>âðåìåíè?
>> ;)
>
>Óïàêîâêà 8 ñåê! Ðàñïàêîâêà 8 ñåê!
Ìîëîäåö, ýòî âïîëíå õîðîøàÿ óñòîé÷èâîñòü ê âûðîæäåííûì äàííûì.
>> >ÇÛ: Äëÿ øèôðîâêè òðåáóåòñÿ 4,5 ñåêóíä! Êòî ñêàçàë, ÷òî ðàñïàêîâêà
>> >òîðìîçíóòåå?
>>
>> À ýòî ñòðàííî. Ìîæåò, ó òåáÿ ïðÿìîå ïðåîáðàçîâàíèå êàêîå-òî íå òî?
>> Òàì æå äåëîâ-òî - íà ïàðó ïðîõîäîâ radix-sort'à.
>
>Ðàäèêñ, ýòî òîò, ÷òî íà äâà ìàññèâà äåëèò? Ó ìåíÿ íå îí, ÿ ïî áèòàì
>ñîðòèðóþ, èìåííî ïî ýòîìó è âûøåë òîðìîç, ïðè îäíîðîäíîì ñîäåðæèìûì, åìó
>ïðèøëîñü êàæäûé ðàç âåñü ìàññèâ ñîðòèðîâàòü (äëÿ êàæäîãî áèòà è èíäåêñà -
64
>ðàçà)!
64 ïðîõîäà ïî ôàéëó - ýòî ìíîãîâàòî. Ëó÷øå ñäåëàé ñîðòèðîâêó ïî ñëîâàì.
Äëÿ áîëüøîãî áëîêà ýòî äîëæíî îêóïèòüñÿ.
>ÇÛ: Ñîâñåì çàáûë î ìàøèíå! P-III 500 (ðàçîãíàí ïî øèíå äî 560) 64 ìåãà
>îïåðàòèâêè!
×òîáû íå ïðèâÿçûâàòüñÿ â èçìåðåíèÿõ ê ìàøèíå, âñå æ ñðàâíè ñ szip'îì.
Ïðàâäà, òàì îêîëî ïîëîâèíû âðåìåíè îòæèðàåò êîäåð...
Âñåãî äîáðîãî,
Âàäèì.
--- ifmail v.2.15dev5
* Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Andrew Filinsky 2:452/4.11 26 Jul 00 14:18:43
To : All
Subj : Êàê áûñòpî îòñîpòèpîâàòü ñòpîêè â BWT?
-++++++++¬ Ñ ãîpÿ÷èì ýëåêòpîííûì ïpèâåòîì!
LTTTTTTTT-
Êàê áûñòpî îòñîpòèpîâàòü ñòpîêè â BWT?
ß âèæó íåñêîëüêî âàpèàíòîâ:
1. /QuickSort/.
2. /HeapSort/.
Îäíàêî îáà âàpèàíòà ñòpàäàþò òåì íåäîñòàòêîì, ÷òî êîëè÷åñòâî ñpàâíåíèé ñòpîê
èìååò ñëîæíîñòü O(n*log(n)), ÷òî ñàìî ïî ñåáå íåïëîõî, íî âîò ïpè ñpàâíåíèè
ìíîæåñòâà ïî÷òè îäèíàêîâûõ ñòpîê ïpèâîäèò ê êàòàñòpîôè÷åñêèì påçóëüòàòàì.
3. /Äåpåâî êîíòåêñòîâ/. Âîçìîæíî, ýòî íàçûâàåòñÿ êàê-òî èíà÷å, íî ïî ñòpóêòópå
íàïîìèíàåò Äåpåâî êîíòåêñòîâ äëÿ PPM.
 îáùåì-òî, ïpîáëåìà òà æå. Ïpè âíåñåíèè ïî÷òè îäèíàêîâûõ ñòpîê äëèíà âåòâåé (è
âpåìÿ âíåñåíèÿ ñòpîêè) íåäîïóñòèìî âåëèêà.
_Âîïpîñ_: Êàê ãpàìîòíî îòñîpòèpîâàòü ñòpîêè â BWT, ÷òîáû íàëè÷èå ìíîæåñòâà
ïî÷òè îäèíàêîâûõ ñòpîê íå ñêàçûâàëîñü íà âpåìåíè ñîpòèpîâêè êàòàñòpîôè÷åñêèì
îápàçîì?
Ñ ìîèõ ñëîâ çàïèñàíî âåpíî. Andrew Filinsky.
--- No tears GoldED+/W32
* Origin: Òåpïåíèå... (2:452/4.11)
— RU.COMPRESS
From : Vladimir Vassilevsky 2:5020/400 26 Jul 00 16:02:56
To : All
Subj : Re: Óïàêîâêà ñèãíàëà â real-time
From: Vladimir Vassilevsky <vlv@fullnet.net>
Andre N Belokon wrote:
>
> > ß äåëàë òàê: âû÷èñëÿë LPC â ñêîëüçÿùåì îêíå, ïåðåñ÷èòûâàÿ êîýôôèöèåíòû
> > äëÿ êàæäîãî íîâîãî îòñ÷åòà, èñïîëüçóÿ äëÿ âû÷èñëåíèÿ ïðåäûäóùèå çíà÷åíèÿ
> > ñèãíàëà, ò.å. ñàìè êîýôô. ËÏÊ íå ïåðåäàþòñÿ.
>
> äåëàë òîæå ñàìîå
Êñòàòè, íå îáÿçàòåëüíî ïåðåñ÷èòûâàòü êîýôôèöèåíòû íà êàæäûé íîâûé
îòñ÷åò. Âïîëíå äîñòàòî÷íî äåëàòü ýòî ðàç íà äåñÿòîê îòñ÷åòîâ.
> > Îïòèìàëüíûé ïîðÿäîê LPC äëÿ
> > ìóçûêè 44khz/16bit ïîëó÷àëñÿ ~ 64, äëèíà îêíà ~ 512 îòñ÷åòîâ.
>
> wow - ïîðÿäîê 64 - ýòî íå ñèëüíî ëè ìíîãî ???
IMHO 32...64 - â ñàìûé ðàç.
> î÷åíü ñèëüíî çàâèñèò îò òèïà ñèãíàëà. íà "æåñòêèõ" äæàç-ðîêîâûõ êîìïîçèöèÿõ
> îêíî è ïîðÿäîê ãîðàçäî ìåíüøå - ÿ âûõîäèë íà ïîðÿäîê 3-7 ïðè îêíå 32-64.
>
> > Ôîðìà îêíà
> > òîæå ñóùåñòâåííà - íàèëó÷øèå ðåçóëüòàòû ïîëó÷àëèñü ñ îêíîì Õåììèíãà (à
> > âîâñå íå Áàðíâåëëà, êàê íè ñòðàííî).
>
> ñ îêíîì âîîáùå íè÷åãî íå äåëàë - ïðÿìîóãîëüíîå òîåñòü. íàäî áóäåò
> ïîïðîáîâàòü
IMHO, ó òåáÿ ñëèøêîì êîðîòêîå îêíî, è ê òîìó æå ïðÿìîóãîëüíîå. Ïîýòîìó è
ðàçíèöà.
> > Âûèãðûø îò ËÏÊ ïîëó÷àëñÿ ïîðÿäêà
> > 20dB
>
> ñòðàííî, ÿ âûõîäèë íà áîëüøèå öèôðû, õîòÿ è íå íàìíîãî.
Î÷åíü çàâèñèò îò ñîäåðæàíèÿ òðåêà. Â× øóìîâûå çâóêè ñèëüíî óõóäøàþò
ñæàòèå.
> > è åùå ïîðÿäêà 3dB ìîæåò äàòü ïðåäñêàçàíèå îñíîâíîãî òîíà.
>
> imho õîðîøî äëÿ speech, íî íå äëÿ audio
Ðàáîòàåò è äëÿ audio, íî íàäî èìåòü áîëüøóþ ãëóáèíó ïðåäñêàçàíèÿ (îò
íåñêîëüêèõ òûñÿ÷). Âû÷èñëèòåëüíî íàêëàäíî. È ýòîò ïàðàìåòð ïðèäåòñÿ
ïåðåäàâàòü.
> > Îñòàòî÷íàÿ îøèáêà äîæèìàåòñÿ ïî Õàôôìàíó.
>
> òóò òîæå åñòü íàä ÷åì ïîäóìàòü. ýòî âñåòàêè íå àëôàâèò èç 256 ñèìâîëîâ
> äîæèìàòü.
Âïîëíå Ãàóññîâñêàÿ ñòàòèñòèêà.
> 2õ êðàòíîå - ìàëî. ÿ òóò ñ íåéðîñåòêàìè â êà÷åñòâå ïðåäèêòîðà ïîáàëîâàëñÿ -
> ðåçóëüòàòû áîëåå ÷åì âïå÷àòëÿþùèå, õîòÿ ïðîöåññ ñæàòèÿ äþæå ìåäëåííûé. imho
> ðåàëüíî äîñòè÷ü òèïè÷íîãî ñæàòèÿ 1:3 - 1:5 è 1:2 íà î÷åíü "ïëîõîì ñèãíàëå".
Ìîæíî óçíàòü ïîäðîáíîñòè?
VLV
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
— RU.COMPRESS
From : Dmitry Shkarin 2:5020/400 26 Jul 00 19:20:31
To : All
Subj : Re: Óïàêîâêà ñèãíàëà â real-time
From: "Dmitry Shkarin" <dmitry.shkarin@mtu-net.ru>
Hi, Andre!
>> Ãëÿíü â ñòîðîíó HBB, TMW, coder by Guang Deng etc.
>ìîæíî áîëåå òî÷íûå URL-èêè ?
TMW: www.cs.monash.edu.au/~bmeyer
HBB: ãäå-òî òàì æå íà monash.edu
Ñòàòüÿ G.Deng íà
ftp://ftp.ee.latrobe.edu.au/pub/dennis/lossless/dpcm.ps.gz
>> Âîîáùå, ëó÷øå ðàññìàòðèâàòü ïðåäèêòîð êàê âñïîìîãàòåëüíûé øàã äëÿ
>> ïîñëåäóåùåãî êîíòåêñòíîãî ìîäåëèðîâàíèÿ, òîãäà àäàïòèâíîñòü ïðåäèêòîðà
>áóäåò
>> òîëüêî ñáèâàòü ñ òîëêó êîíòåêñòíûé ìîäåëåð.
>ýòî ïîíÿòíî âñå, íî î êîíòåêñòíîì ìîäåëèðîâàíèè ðå÷ü íå øëà.
Ýòî ÿ ê òîìó, ÷òî óëó÷øàÿ è óñëîæíÿÿ ïðåäèêòîð òû ìîæåøü óõóäøèòü îáùþþ
ïðîèçâîäèòåëüíîñòü êîäåêà.
--- ifmail v.2.15dev5
* Origin: home (2:5020/400)
— RU.COMPRESS
From : IP Robot 2:5093/28.126 27 Jul 00 01:09:13
To : All
Subj : News at ftp://ftp.elf.stuba.sk/pub/pc/pack/
ftp://ftp.elf.stuba.sk/pub/pc/pack/easyzip.zip
EASYZIP v1.2 by Dirk Paehl - Win32 packer (345,403 bytes)
ftp://ftp.elf.stuba.sk/pub/pc/pack/unz542c.zip
Info-ZIP's portable UnZip v5.42c beta - Source code (1,190,584 bytes)
--- PktMake.pl
* Origin: PktMake.pl (2:5093/28.126)
— RU.COMPRESS
From : Dima Petukhov 2:5020/1517.12 27 Jul 00 03:07:54
To : Helgy Green
Subj : Óïàêîâêà ñèãíàëà â real-time
Hello Helgy.
Monday July 24 2000 02:22, Helgy Green íàïèñàë(à) ê All:
HG> Ðåáÿòà, à ÷òî çà îñöèëîãðàô òàêîé?
Îáû÷íûé. 8 áèò, 100 ÌÃö, ìíîãî êàíàëîâ (ñèíõpîííûõ).
HG> 16 áèò ðåàëüíî ïîëó÷èòü ïðîñòî íåëüçÿ. Ìàêñèìóì 14 áèò. Øóìû ìåøàþò.
Ñ ýòèì ñïîpèòü íå áóäó, âåpþ.
HG> Â èíñòèòóòå ìåòðîëîãèè íàä ýòèì äîëãî òðóäèëèñü. Âñÿêàÿ ðåêëàìà, ãäå
HG> ãîâîðèòñÿ áîëüøå, ëæåò. Â ñîóíä-áëàñòåðå 12 áèò. 4 áèòà âñåãäà íóëè.
À âîò "íóëè" - ñëèøêîì ãpîìêî ñêàçàíî. Øóì, à íå íóëè.
Äà è âåëè÷èíà ýòîãî øóìà (â áèòàõ) îïpåäåëÿåòñÿ àïïàpàòópîé. À âîâñå íå ïpèíöèï
èàëüíûìè îãpàíè÷åíèÿìè, êàê òû õî÷åøü íàñ óâåpèòü. ß òàê äóìàþ ïpè èñïîëüçîâàíè
è påçèñòîpîâ ñ îòêëîíåíèåì 0.001% è ñîîòâåòñòâóþùèõ êîìïàpàòîpîâ (âñå íà îäíîì
êpèñòàëëå) âïîëíå ìîæíî ïîëó÷èòü 16-17 áèò ÀÖÏ. Äàæå åñëè íå âñïîìèíàòü ïpî âñÿ
êèå òàì "ñèãìà-äåëüòà ÀÖÏ" .... :)
Äèìà
ß íå ïðîùàþñü - åùå óâèäèìñÿ...
... ß íèêîãî íå óáèâàë ...
--- GoldED 3.00+ Alpha 5
* Origin: /dev/null (FidoNet 2:5020/1517.12)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/400 27 Jul 00 11:15:50
To : All
Subj : Re: Êàê áûñòpî îòñîpòèpîâàòü ñòpîêè â BWT?
From: "Vadim Yoockin" <vy@thermosyn.com>
Hello, Andrew Filinsky ! You wrote:
>Êàê áûñòpî îòñîpòèpîâàòü ñòpîêè â BWT?
Ïîìèëóéòå, Ïàíèêîâñêèé, âåäü âàøà ñïåöèàëüíîñòü - ãóñü?
(ñ) Çîëîòîé òåëåíîê. Â ñìûñëå, PPM ;)
>ß âèæó íåñêîëüêî âàpèàíòîâ:
>
>1. /QuickSort/.
>2. /HeapSort/.
Î, ïî ïîâîäó ñîðòèðîâêè äëÿ BWT óæå ñòîëüêî âñåãî
íàäóìàíî-ïðèäóìàíî...
>Îäíàêî îáà âàpèàíòà ñòpàäàþò òåì íåäîñòàòêîì, ÷òî êîëè÷åñòâî ñpàâíåíèé
ñòpîê
>èìååò ñëîæíîñòü O(n*log(n)), ÷òî ñàìî ïî ñåáå íåïëîõî, íî âîò ïpè ñpàâíåíèè
>ìíîæåñòâà ïî÷òè îäèíàêîâûõ ñòpîê ïpèâîäèò ê êàòàñòpîôè÷åñêèì påçóëüòàòàì.
Hà÷èíàÿ ñ bzip2, à òî÷íåå, ñ êàêîãî-òî èç Óèëåðîâñêèõ bred'îâ, èäåò ëèíåéêà
êîìïðåññîðîâ, èñïîëüçóþùèõ ïðåäâàðèòåëüíóþ radix-ñîðòèðîâêó ïî ïàðå
áàéò. Ïîëó÷åííûå ïàêåòû ñîðòèðóþòñÿ ïî î÷åðåäè, íà÷èíàÿ ñ íàèìåíüøåããî
èç íèõ. À ðåçóëüòàò ñîðòèðîâêè ìåëêèõ ïàêåòîâ èñïîëüçóåòñÿ äëÿ ñîðòèðîâêè
êðóïíûõ, êîãäà óêàçàòåëè íà ñðàâíèâàåìûõ ïîäñòðîêàõ äîáèðàþòñÿ íà
òå ìåñòà, êîòîðûå óæå ñðàâíèâàëèñü. Òàêîé ìåòîä èñïîëüçóåò è ìîé,
âå÷íî íåäîäåëàííûé ybs, íàâåðíîå, ñàìûé áûñòðûé èç èñïîâåäóþùèõ ïîäîáíûé
ïîäõîä.
 õóäøåì ñëó÷àå âñå ðàâíî äîëæíî áû ïîëó÷àòüñÿ n*logn, íî ìíå òàêèå ñëó÷àè
íå ïîïàäàëèñü. Äàæå ñïåöèàëüíî :) À íà áîëüøèíñòâå ôàéëîâ çàâèñèìîñòü
ïîëó÷àåòñÿ ïðàêòè÷åñêè ëèíåéíîé.
Ýòîò ìåòîä íå âñåãäà îêàçûâàåòñÿ ñàìûì áûñòðûì èç-çà çàìåòíûõ íàêëàäíûõ
ðàñõîäîâ íà ïîâûøåííóþ óñòîé÷èâîñòü. Ê ïðèìåðó, íà áîëüøèíñòâå òåêñòîâ
áîëåå áûñòðû imp è, îñîáåííî, dc (èäåþ ñîðòèðîâêè, êîòîðóþ èñïîëüçóåò dc,
ÿ ðàññêàæó ïîçæå). Hî ïîñëåäíèå õîðîøî çàäóìûâàþòñÿ íà äëèííûõ êîíòåêñòàõ.
>3. /Äåpåâî êîíòåêñòîâ/. Âîçìîæíî, ýòî íàçûâàåòñÿ êàê-òî èíà÷å, íî ïî
ñòpóêòópå
>íàïîìèíàåò Äåpåâî êîíòåêñòîâ äëÿ PPM.
>
>Â îáùåì-òî, ïpîáëåìà òà æå. Ïpè âíåñåíèè ïî÷òè îäèíàêîâûõ ñòpîê äëèíà
âåòâåé (è
>âpåìÿ âíåñåíèÿ ñòpîêè) íåäîïóñòèìî âåëèêà.
Hà ñàìîì äåëå, ýòî êàê ñòðîèòü äåðåâî. Ãëàâíàÿ-òî çàäà÷à â òîì, ÷òîáû
äëèííûå êîíòåêñòû ñðàâíèâàëèñü ëèøü îäíàæäû. Ñàäàêàíå, Êóðòö, Áàëêåíõîë,
Ëàðññîí ïðèäóìûâàëè ÷òî-òî ïî÷òè ñîâñåì ëèíåéíîå. Hî ëè÷íî ÿ ñêåïòè÷åñêè
îòíîøóñü ê òàêèì óõèùðåíèÿì èç-çà ñëèøêîì áîëüøèõ ðàñõîäîâ íà
ïîñòðîåíèÿ äåðåâüåâ èëè ñëîæíûõ êîâûðÿíèé ñ ñóôôèêñàìè, ïîñêîëüêó
íà áîëüøèíñòâå ôàéëîâ ýòè ìåòîäû ïðîèãðûâàþò â ñêîðîñòè.
>_Âîïpîñ_: Êàê ãpàìîòíî îòñîpòèpîâàòü ñòpîêè â BWT, ÷òîáû íàëè÷èå ìíîæåñòâà
>ïî÷òè îäèíàêîâûõ ñòpîê íå ñêàçûâàëîñü íà âpåìåíè ñîpòèpîâêè
êàòàñòpîôè÷åñêèì
>îápàçîì?
Ìîæíî, êàê â bzip'e, èõ ïðîðåäèòü ñëó÷àéíûìè xor'àìè.
Âñåãî äîáðîãî,
Âàäèì.
P.S. À âåäü ÷òî-òî äàæå äëÿ BWT FAQ'a ïîëó÷èëîñü...
Âíåñó, ïîæàëóé, òóäà.
--- ifmail v.2.15dev5
* Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : ZAB 2:5020/400 27 Jul 00 12:23:23
To : All
Subj : Re: ×òî ïîñîâåòóåòå?
From: "ZAB" <ZAnatolyB@Mail.ru>
Vadim Yoockin <vy@thermosyn.com> ñîîáùèë â íîâîñòÿõ
ñëåäóþùåå:8ljevp$bb8$1@news.kiev.sovam.com...
> Hello, ZAB ! You wrote:
>
> >Ìîæåò ÿ ÷¸ íå ïîíèìàþ â òåîðèè, íî ïî õåøó íå òàê ïðîñòî èíäåêñèðîâàòüñÿ,
> >íóæíà ïðîöåäóðà ïîèñêà!
>
> Çàòî õýø áîëåå óñòîé÷èâ ê áîëüøîìó êîëè÷åñòâó ïîõîæèõ êîíòåêñòîâ.
>
> >ß óæå òàê ñäàëàë, ò.å. ñîáèðàþ ìàññèâ èç N 4-¸õ
> >áàéòíûõ ýëåìåíòîâ (êîíòåêñòîâ), è åù¸ îäèí òàêîé æå, íî âìåñòî êîíòåêñòîâ
â
> >í¸ì èíäåêñû íà èñõîäíûé áëîê, ïîòîì åù¸ ìàññèâ 0..65535 äëÿ òîãî, ÷òîáû
> >áèíàðíûé ïîèñê ïî ïåðâîìó ìàññèâó íà÷èíàëñÿ ñ äèàïîçîíà íà áîëåå 655536,
> >ò.å. ýòîò òðåòèé ìàññèâ ÿâëÿåòñÿ òàáëèöåé èíäåêñîâ íà ïåðâûå 2 áàéòà
> >êîíòåêñòîâ! Ïîìîåìó ðåàëèçà÷èÿ âïîëíå îïòèìàëüíà, ïî êðàéíåé ìåðå äëÿ
> >îáðàòíîãî ïðåîáðàçîâàíèÿ 3-¸õ ìåãàáàéò (âñåõ öåëèêîì, îäíèì áëîêîì) åé
íàäî
> >~3,5 ñåêóíäû!
>
> À åñëè âåñü áëîê ñîñòîèò èç îäèíàêîâûõ ñèìâîëîâ, ñêîëüêî òðåáóåòñÿ
âðåìåíè?
> ;)
Óïàêîâêà 8 ñåê! Ðàñïàêîâêà 8 ñåê!
> Êñòàòè, äëÿ ÷èñòîòû ýêñïåðèìåíòà ñðàâíè ñ szip'îì.
> >ÇÛ: Äëÿ øèôðîâêè òðåáóåòñÿ 4,5 ñåêóíä! Êòî ñêàçàë, ÷òî ðàñïàêîâêà
> >òîðìîçíóòåå?
>
> À ýòî ñòðàííî. Ìîæåò, ó òåáÿ ïðÿìîå ïðåîáðàçîâàíèå êàêîå-òî íå òî?
> Òàì æå äåëîâ-òî - íà ïàðó ïðîõîäîâ radix-sort'à.
Ðàäèêñ, ýòî òîò, ÷òî íà äâà ìàññèâà äåëèò? Ó ìåíÿ íå îí, ÿ ïî áèòàì
ñîðòèðóþ, èìåííî ïî ýòîìó è âûøåë òîðìîç, ïðè îäíîðîäíîì ñîäåðæèìûì, åìó
ïðèøëîñü êàæäûé ðàç âåñü ìàññèâ ñîðòèðîâàòü (äëÿ êàæäîãî áèòà è èíäåêñà - 64
ðàçà)!
> >ÇÇÛ: Ïîñëå îïòèìèçàöèè ïðîöåäóð ñîðòèðîâêè:
> >ïàêîâêà (ïðåîáðàçîâàíèå): 4,203 ñåê
> >ðàñïàêîâêà (ïðåîáðàçîâàíèå): 3,3 ñåê
> >Æð¸ò 35 ìåãîâ â ïèêîâîé íàãðóçêå è ìíå êàæåòñÿ, ÷òî óìåíüøàòü ðàçìåð
áëîêà
> >ìåííåå 3-¸õ ìåãàáàéò íåò íåîáõîäèìîñòè!
>
> Ýòî äà.
> >ÇÇÇÛ: Êñòàòè! Êàêîé ïîðÿäîê êîíòåêñòîâ äà¸ò ëó÷øèé ðåçóëüòàò? Àòî
äîäåëàòü
> >ýòî äî 8 - 12 ìîæíî áåç ïîòåðü â ñêîðîñòü áîëåå 1 ñåêóíäû!
>
> Çà èñêëþ÷åíèåì íåêîòîðûõ äàííûõ, ÷åì áîëüøå - òåì ëó÷øå.
> Hà áîëüøèíñòâå òåêñòîâ 8-12 áóäåò âïîëíå äîñòàòî÷íî.
Ëàäíî! Çíà÷èò áóäó äîðàáàòûâàòü äî 12!
ÇÛ: Ñîâñåì çàáûë î ìàøèíå! P-III 500 (ðàçîãíàí ïî øèíå äî 560) 64 ìåãà
îïåðàòèâêè!
--- ifmail v.2.15dev5
* Origin: NeoToN (2:5020/400)
— RU.COMPRESS
From : ZAB 2:5020/400 27 Jul 00 12:23:26
To : All
Subj : Re: ×òî ïîñîâåòóåòå?
From: "ZAB" <ZAnatolyB@Mail.ru>
Vadim Yoockin <vy@thermosyn.com> ñîîáùèë â íîâîñòÿõ
ñëåäóþùåå:8ljevp$bb8$1@news.kiev.sovam.com...
> Hello, ZAB ! You wrote:
>
> >Ìîæåò ÿ ÷¸ íå ïîíèìàþ â òåîðèè, íî ïî õåøó íå òàê ïðîñòî èíäåêñèðîâàòüñÿ,
> >íóæíà ïðîöåäóðà ïîèñêà!
>
> Çàòî õýø áîëåå óñòîé÷èâ ê áîëüøîìó êîëè÷åñòâó ïîõîæèõ êîíòåêñòîâ.
>
> >ß óæå òàê ñäàëàë, ò.å. ñîáèðàþ ìàññèâ èç N 4-¸õ
> >áàéòíûõ ýëåìåíòîâ (êîíòåêñòîâ), è åù¸ îäèí òàêîé æå, íî âìåñòî êîíòåêñòîâ
â
> >í¸ì èíäåêñû íà èñõîäíûé áëîê, ïîòîì åù¸ ìàññèâ 0..65535 äëÿ òîãî, ÷òîáû
> >áèíàðíûé ïîèñê ïî ïåðâîìó ìàññèâó íà÷èíàëñÿ ñ äèàïîçîíà íà áîëåå 655536,
> >ò.å. ýòîò òðåòèé ìàññèâ ÿâëÿåòñÿ òàáëèöåé èíäåêñîâ íà ïåðâûå 2 áàéòà
> >êîíòåêñòîâ! Ïîìîåìó ðåàëèçà÷èÿ âïîëíå îïòèìàëüíà, ïî êðàéíåé ìåðå äëÿ
> >îáðàòíîãî ïðåîáðàçîâàíèÿ 3-¸õ ìåãàáàéò (âñåõ öåëèêîì, îäíèì áëîêîì) åé
íàäî
> >~3,5 ñåêóíäû!
>
> À åñëè âåñü áëîê ñîñòîèò èç îäèíàêîâûõ ñèìâîëîâ, ñêîëüêî òðåáóåòñÿ
âðåìåíè?
> ;)
> Êñòàòè, äëÿ ÷èñòîòû ýêñïåðèìåíòà ñðàâíè ñ szip'îì.
SZip'ó ïîòðåáîâàëîñü ïî 2 ñåêóíäû íà ðàñïàêîâêó è óïàêîâêó (íà îäíîðîäíîì 1
ñåêóíäà íà òî è íà òî!!! Êàê ñèå âûøëî íå ÿñíî, âåäü åìó íàäî áûëî åø¸ è ñ
àðèôìåòèêîé ìó÷àòüñÿ!!! Ñêîðåå âñåãî èç-çà ðàçìåðà áëîêà!
--- ifmail v.2.15dev5
* Origin: NeoToN (2:5020/400)
— RU.COMPRESS
From : ZAB 2:5020/400 27 Jul 00 12:23:39
To : All
Subj : Re: ×òî ïîñîâåòóåòå?
From: "ZAB" <ZAnatolyB@Mail.ru>
ZAB <ZAnatolyB@mail.ru> ñîîáùèë â íîâîñòÿõ
ñëåäóþùåå:8lk25h$2ua1$1@ddt.demos.su...
> Vadim Yoockin <vy@thermosyn.com> ñîîáùèë â íîâîñòÿõ
> ñëåäóþùåå:8ljevp$bb8$1@news.kiev.sovam.com...
> > Hello, ZAB ! You wrote:
> >
> > >Ìîæåò ÿ ÷¸ íå ïîíèìàþ â òåîðèè, íî ïî õåøó íå òàê ïðîñòî
èíäåêñèðîâàòüñÿ,
> > >íóæíà ïðîöåäóðà ïîèñêà!
> >
> > Çàòî õýø áîëåå óñòîé÷èâ ê áîëüøîìó êîëè÷åñòâó ïîõîæèõ êîíòåêñòîâ.
> >
> > >ß óæå òàê ñäàëàë, ò.å. ñîáèðàþ ìàññèâ èç N 4-¸õ
> > >áàéòíûõ ýëåìåíòîâ (êîíòåêñòîâ), è åù¸ îäèí òàêîé æå, íî âìåñòî
êîíòåêñòîâ
> â
> > >í¸ì èíäåêñû íà èñõîäíûé áëîê, ïîòîì åù¸ ìàññèâ 0..65535 äëÿ òîãî, ÷òîáû
> > >áèíàðíûé ïîèñê ïî ïåðâîìó ìàññèâó íà÷èíàëñÿ ñ äèàïîçîíà íà áîëåå
655536,
> > >ò.å. ýòîò òðåòèé ìàññèâ ÿâëÿåòñÿ òàáëèöåé èíäåêñîâ íà ïåðâûå 2 áàéòà
> > >êîíòåêñòîâ! Ïîìîåìó ðåàëèçà÷èÿ âïîëíå îïòèìàëüíà, ïî êðàéíåé ìåðå äëÿ
> > >îáðàòíîãî ïðåîáðàçîâàíèÿ 3-¸õ ìåãàáàéò (âñåõ öåëèêîì, îäíèì áëîêîì) åé
> íàäî
> > >~3,5 ñåêóíäû!
> >
> > À åñëè âåñü áëîê ñîñòîèò èç îäèíàêîâûõ ñèìâîëîâ, ñêîëüêî òðåáóåòñÿ
> âðåìåíè?
> > ;)
>
> Óïàêîâêà 8 ñåê! Ðàñïàêîâêà 8 ñåê!
>
> > Êñòàòè, äëÿ ÷èñòîòû ýêñïåðèìåíòà ñðàâíè ñ szip'îì.
> > >ÇÛ: Äëÿ øèôðîâêè òðåáóåòñÿ 4,5 ñåêóíä! Êòî ñêàçàë, ÷òî ðàñïàêîâêà
> > >òîðìîçíóòåå?
> >
> > À ýòî ñòðàííî. Ìîæåò, ó òåáÿ ïðÿìîå ïðåîáðàçîâàíèå êàêîå-òî íå òî?
> > Òàì æå äåëîâ-òî - íà ïàðó ïðîõîäîâ radix-sort'à.
>
> Ðàäèêñ, ýòî òîò, ÷òî íà äâà ìàññèâà äåëèò? Ó ìåíÿ íå îí, ÿ ïî áèòàì
> ñîðòèðóþ, èìåííî ïî ýòîìó è âûøåë òîðìîç, ïðè îäíîðîäíîì ñîäåðæèìûì, åìó
> ïðèøëîñü êàæäûé ðàç âåñü ìàññèâ ñîðòèðîâàòü (äëÿ êàæäîãî áèòà è èíäåêñà -
64
> ðàçà)!
>
> > >ÇÇÛ: Ïîñëå îïòèìèçàöèè ïðîöåäóð ñîðòèðîâêè:
> > >ïàêîâêà (ïðåîáðàçîâàíèå): 4,203 ñåê
> > >ðàñïàêîâêà (ïðåîáðàçîâàíèå): 3,3 ñåê
> > >Æð¸ò 35 ìåãîâ â ïèêîâîé íàãðóçêå è ìíå êàæåòñÿ, ÷òî óìåíüøàòü ðàçìåð
> áëîêà
> > >ìåííåå 3-¸õ ìåãàáàéò íåò íåîáõîäèìîñòè!
> >
> > Ýòî äà.
> > >ÇÇÇÛ: Êñòàòè! Êàêîé ïîðÿäîê êîíòåêñòîâ äà¸ò ëó÷øèé ðåçóëüòàò? Àòî
> äîäåëàòü
> > >ýòî äî 8 - 12 ìîæíî áåç ïîòåðü â ñêîðîñòü áîëåå 1 ñåêóíäû!
> >
> > Çà èñêëþ÷åíèåì íåêîòîðûõ äàííûõ, ÷åì áîëüøå - òåì ëó÷øå.
> > Hà áîëüøèíñòâå òåêñòîâ 8-12 áóäåò âïîëíå äîñòàòî÷íî.
>
> Ëàäíî! Çíà÷èò áóäó äîðàáàòûâàòü äî 12!
>
> ÇÛ: Ñîâñåì çàáûë î ìàøèíå! P-III 500 (ðàçîãíàí ïî øèíå äî 560) 64 ìåãà
> îïåðàòèâêè!
×òî çà ÷åðòîâùèíà? Åñëè â ýõó è âïðÿìü ïîïàëî ñòîëüêî îäèíàêîâûõ ïèñåì, òî
ýòî íå ìîÿ âèíà! Hî ÿ âñ¸ æå ïðîøó ïðîùåíèÿ!!!
×òî ñ fido7 ñëó÷èëîñü? Òî ñîåäèíåíèÿ íåò, à òî âäðóã...!!!!!!!
--- ifmail v.2.15dev5
* Origin: NeoToN (2:5020/400)
— RU.COMPRESS
From : ZAB 2:5020/400 27 Jul 00 12:32:09
To : All
Subj : Re: ×òî ïîñîâåòóåòå?
From: "ZAB" <ZAnatolyB@Mail.ru>
Vadim Yoockin <vy@thermosyn.com> ñîîáùèë â íîâîñòÿõ
ñëåäóþùåå:8llvtn$m2h$1@news.kiev.sovam.com...
> Hello, ZAB ! You wrote:
>
> >> À åñëè âåñü áëîê ñîñòîèò èç îäèíàêîâûõ ñèìâîëîâ, ñêîëüêî òðåáóåòñÿ
> >âðåìåíè?
> >> ;)
> >
> >Óïàêîâêà 8 ñåê! Ðàñïàêîâêà 8 ñåê!
>
> Ìîëîäåö, ýòî âïîëíå õîðîøàÿ óñòîé÷èâîñòü ê âûðîæäåííûì äàííûì.
Äà íåò! SZip'ó ïîòðåáîâàëàñü 1 ñåêóíäà!
> >> >ÇÛ: Äëÿ øèôðîâêè òðåáóåòñÿ 4,5 ñåêóíä! Êòî ñêàçàë, ÷òî ðàñïàêîâêà
> >> >òîðìîçíóòåå?
> >>
> >> À ýòî ñòðàííî. Ìîæåò, ó òåáÿ ïðÿìîå ïðåîáðàçîâàíèå êàêîå-òî íå òî?
> >> Òàì æå äåëîâ-òî - íà ïàðó ïðîõîäîâ radix-sort'à.
> >
> >Ðàäèêñ, ýòî òîò, ÷òî íà äâà ìàññèâà äåëèò? Ó ìåíÿ íå îí, ÿ ïî áèòàì
> >ñîðòèðóþ, èìåííî ïî ýòîìó è âûøåë òîðìîç, ïðè îäíîðîäíîì ñîäåðæèìûì, åìó
> >ïðèøëîñü êàæäûé ðàç âåñü ìàññèâ ñîðòèðîâàòü (äëÿ êàæäîãî áèòà è èíäåêñà -
> 64
> >ðàçà)!
>
> 64 ïðîõîäà ïî ôàéëó - ýòî ìíîãîâàòî. Ëó÷øå ñäåëàé ñîðòèðîâêó ïî ñëîâàì.
> Äëÿ áîëüøîãî áëîêà ýòî äîëæíî îêóïèòüñÿ.
64 ïðîõîäà íå âñåãäà, ýòî òîëüêî íà îäíîðîäíîì ôàéëå, íà ñàìîì äåëå ãäåòî
îêîëî 48, ò.å. 32 îáÿçàòåëüíî, à äàëüøå èä¸ò ïðîâåðêà è åñëè äèàïîçîí
ñóçèëñÿ äî 60, òî ïåðåõîäèò íà ìåíèå ñëîæíóþ ñîðòèðîâêó! À ýòî êàê, ïî
ñëîâàì, ïî 2 áàéòà? Äà! È ðàäèêñ ýòî âñ¸æå ÷òî?
> >ÇÛ: Ñîâñåì çàáûë î ìàøèíå! P-III 500 (ðàçîãíàí ïî øèíå äî 560) 64 ìåãà
> >îïåðàòèâêè!
>
> ×òîáû íå ïðèâÿçûâàòüñÿ â èçìåðåíèÿõ ê ìàøèíå, âñå æ ñðàâíè ñ szip'îì.
> Ïðàâäà, òàì îêîëî ïîëîâèíû âðåìåíè îòæèðàåò êîäåð...
Ïðîâåðÿë! Æì¸ò è ðàçæèìàåò çà 1 ñåêóíäó! ×óäåñà!
ÇÛ: Ïðîøó ïðîùåíèÿ çà îãðîìíûé ïîñòèíã! Ñàì íå çíàþ ÷òî ïðîèçîøëî!
--- ifmail v.2.15dev5
* Origin: NeoToN (2:5020/400)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/400 27 Jul 00 14:39:26
To : ZAB
Subj : Re: ×òî ïîñîâåòóåòå?
From: "Vadim Yoockin" <vy@thermosyn.com>
Hello, ZAB ! You wrote:
>> Ìîëîäåö, ýòî âïîëíå õîðîøàÿ óñòîé÷èâîñòü ê âûðîæäåííûì äàííûì.
>
>Äà íåò! SZip'ó ïîòðåáîâàëàñü 1 ñåêóíäà!
Âîçìîæíî, ñêîðîñòü I/O îïåðàöèé òîæå âëèÿåò.
Ïîïðîáóé ñðàâíèòü íà ðàìäðàéâå.
>> 64 ïðîõîäà ïî ôàéëó - ýòî ìíîãîâàòî. Ëó÷øå ñäåëàé ñîðòèðîâêó ïî ñëîâàì.
>> Äëÿ áîëüøîãî áëîêà ýòî äîëæíî îêóïèòüñÿ.
>
>64 ïðîõîäà íå âñåãäà, ýòî òîëüêî íà îäíîðîäíîì ôàéëå, íà ñàìîì äåëå ãäåòî
>îêîëî 48, ò.å. 32 îáÿçàòåëüíî, à äàëüøå èä¸ò ïðîâåðêà è åñëè äèàïîçîí
>ñóçèëñÿ äî 60, òî ïåðåõîäèò íà ìåíèå ñëîæíóþ ñîðòèðîâêó! À ýòî êàê, ïî
>ñëîâàì, ïî 2 áàéòà? Äà! È ðàäèêñ ýòî âñ¸æå ÷òî?
Ðàäèêñ, ãðóáî ãîâîðÿ, - ýòî êîãäà äåëèøü âñå ñòðîêè ïî îäíîìó
èç ñèìâîëîâ àëôàâèòà. Àëôàâèò ìîäåò áûòü äâîè÷íûì,
à ìîæåò - 65536-è÷íûì.
>> >ÇÛ: Ñîâñåì çàáûë î ìàøèíå! P-III 500 (ðàçîãíàí ïî øèíå äî 560) 64 ìåãà
>> >îïåðàòèâêè!
>>
>> ×òîáû íå ïðèâÿçûâàòüñÿ â èçìåðåíèÿõ ê ìàøèíå, âñå æ ñðàâíè ñ szip'îì.
>> Ïðàâäà, òàì îêîëî ïîëîâèíû âðåìåíè îòæèðàåò êîäåð...
>
>Ïðîâåðÿë! Æì¸ò è ðàçæèìàåò çà 1 ñåêóíäó! ×óäåñà!
Òîãäà òåáå åñòü, çà ÷òî áîðîòüñÿ :)
Hî ýòî âðÿä ëè èç-çà ðàçìåðà áëîêà - âåäü â szip'e åãî ìîæíî
óêàçàòü äîñòàòî÷íî áîëüøîé.
>ÇÛ: Ïðîøó ïðîùåíèÿ çà îãðîìíûé ïîñòèíã! Ñàì íå çíàþ ÷òî ïðîèçîøëî!
Ïðîâàéäåð, âîçìîæíî. Ñ êåì íå áûâàåò.
Çàòî òðàôèê ïîäíÿëñÿ :)
Âñåãî äîáðîãî,
Âàäèì.
--- ifmail v.2.15dev5
* Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/28.126 27 Jul 00 22:55:06
To : All
Subj : SoftNews
* Originally in RU.COMPRESS
=============================================================================
* Forwarded by Bulat Ziganshin (2:5093/28.126)
* Area : 1072.COMPNEWS (1072.COMPNEWS)
* From : Andrew Worobyew, 2:5020/1072 (Thursday July 27 2000 20:25)
* To : All
* Subj : SoftNews
=============================================================================
·--------·==¦• •¦==·--------·
¦ Ìîå ïî÷òåíèå, Âàì, óâàæàåìûé(àÿ) All !
¦
Hàéäåí íîâûé àëãîpèòì êîìïpåññèè...
17:10
Êîìïüþòåpíûå èññëåäîâàòåëè èç Bell Labs, ÿâëÿþùåéñÿ ïîäpàçäåëåíèåì Lucent Techn
ologies è Êàëèôîpíèéñêîãî Òåõíîëîãè÷åñêîãî Èíñòèòóòà, pàçpàáîòàëè ïåpâóþ òåõíîë
îãèþ, ïîçâîëÿþùóþ ïpàêòè÷åñêè ïåpåäàâàòü äåòàëèçèpîâàííûå òp¸õìåpíûå
èíôîpìàöèîííûå îáúåêòû, è pàáîòàòü ñ ýòèì òèïîì äàííûõ íà ïåpñîíàëüíûõ êîìïüþòå
pàõ.
Àíîíñ áûë ïpîèçâåä¸í íà âûñòàâêå SIGGRAPH 2000. Ðåâîëþöèîííûé àëãîpèòì íàçûâàþò
_digital geometry compression_. Ãåîìåòpè÷åñêîå ïpåäñòàâëåíèå âàpüèpóåòñÿ îò ÷å
pòåæåé àâèàëàéíåpà äî ïåpñîíàæåé êîìèêñîâ. Äåòàëüíàÿ èíôîpìàöèÿ î pàçìåpàõ è
ãpàíÿõ òp¸õìåpíûõ îáúåêòîâ ìîæåò áûòü îòîápàæåíà, èçìåpåíà è åé ìîæíî óïpàâëÿòü
. Öèôpîâàÿ èíôîpìàöèÿ îá îáúåêòå ìîæåò áûòü ïîëó÷åíà ñ ïîìîùüþ ëàçåpíîãî 3D ñêà
íåpà è ñîñòîÿòü èç ìèëëèîíîâ è äàæå ìèëëèàpäîâ òpåóãîëüíèêîâ
(ïîëèãîíîâ-ïpèìèòèâîâ).
Òåõíîëîãèÿ â äâåíàäöàòü pàç ïpåâîñõîäèò âîçìîæíîñòè êîìïpåññèè ãåîìåòpè÷åñêèõ î
áúåêòîâ, ÷åì ñòàíäàpò MPEG-4, è â øåñòü pàç áîëåå ýôôåêòèâíà ïpåäûäóùèõ pàçpàáî
òîê â ýòîé îáëàñòè. Âñ¸ ýòî íåèçìåííî ïpèâåä¸ò ê âíåäpåíèþ ïîëíîé påàëèçàöèè 3D
â
Internet.
Îáñóäèòü
Àëåêñåé Ïåpåâåpòàéëîâ
(C) 2000, Ô-Öåíòð
http://www.fcenter.ru
¦ Ñ íàèëó÷øàéøèìè ïîæåëàíèÿìè! /Àíäðåé Âîðîáüåâ, e-mail: anvakams@ixbt.com
¦ ICQ: 16998590
L¦--------· ·---------¦=
-+- ×òî ó òåáÿ òàì? Windows? Òî-òî äóåò...
+ Origin: Îí â Èíòåðíåò âîøåë. È íå âåðíóëñÿ. (2:5020/1072)
=============================================================================
Hello All!
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722
... Èíîãäà äëÿ òîãî, ÷òîáû èçìåíèòü ñâîå âîñïðèÿòèå ìèðà,
... ëþäè ïûòàþòñÿ èçìåíèòü ñàì ìèð
--- GoldED+/W32 1.1.2
* Origin: À ÷åì çàíèìàåòñÿ õåðîìàíòèÿ? (2:5093/28.126)
— RU.COMPRESS
From : ZAB 2:5020/400 28 Jul 00 13:01:17
To : All
Subj : Re: ×òî ïîñîâåòóåòå?
From: "ZAB" <ZAnatolyB@Mail.ru>
Vadim Yoockin <vy@thermosyn.com> ñîîáùèë â íîâîñòÿõ
ñëåäóþùåå:8lp3g3$1344$1@news.kiev.sovam.com...
> Hello, ZAB ! You wrote:
>
> >> Ìîëîäåö, ýòî âïîëíå õîðîøàÿ óñòîé÷èâîñòü ê âûðîæäåííûì äàííûì.
> >
> >Äà íåò! SZip'ó ïîòðåáîâàëàñü 1 ñåêóíäà!
>
> Âîçìîæíî, ñêîðîñòü I/O îïåðàöèé òîæå âëèÿåò.
> Ïîïðîáóé ñðàâíèòü íà ðàìäðàéâå.
Hå âëèÿåò, ïðîâåðÿë!
> Ðàäèêñ, ãðóáî ãîâîðÿ, - ýòî êîãäà äåëèøü âñå ñòðîêè ïî îäíîìó
> èç ñèìâîëîâ àëôàâèòà. Àëôàâèò ìîäåò áûòü äâîè÷íûì,
> à ìîæåò - 65536-è÷íûì.
>
> >> ×òîáû íå ïðèâÿçûâàòüñÿ â èçìåðåíèÿõ ê ìàøèíå, âñå æ ñðàâíè ñ szip'îì.
> >> Ïðàâäà, òàì îêîëî ïîëîâèíû âðåìåíè îòæèðàåò êîäåð...
> >
> >Ïðîâåðÿë! Æì¸ò è ðàçæèìàåò çà 1 ñåêóíäó! ×óäåñà!
>
> Òîãäà òåáå åñòü, çà ÷òî áîðîòüñÿ :)
> Hî ýòî âðÿä ëè èç-çà ðàçìåðà áëîêà - âåäü â szip'e åãî ìîæíî
> óêàçàòü äîñòàòî÷íî áîëüøîé.
Hî íå íà 3 ìåãà! Hó ÷òî æ áóäó ìó÷àòü ðàäèêñ!
--- ifmail v.2.15dev5
* Origin: NeoToN (2:5020/400)
— RU.COMPRESS
From : Andrew Belov 2:5020/181.2 28 Jul 00 13:17:03
To : Anatoly Popov
Subj : Èñòîðèÿ ñ ãåîãðàôèåé ;)
Hello Anatoly!
24 Jul 00 10:48, Anatoly Popov wrote to Andrew Belov:
AP>>> Êðîìå òîãî, ó íåãî åñòü àññîðòèìåíò îïöèé äëÿ ðàáîòû ñî
AP>>> ñòàðûìè/ìîëîäûìè ôàéëàìè, íî òàì íåò îáðàáîòêè ôàéëîâ, ñîçäàííûõ
AP>>> áîëåå N äíåé íàçàä. Ìåíåå - åñòü, áîëåå - íåò :(((
AB>> À ýòî åñòü: -odb<N>.
AP> À ñ êàêîé âåðñèè?  õåëïå ê ARJ 2.62ñ îá ýòîì óìàë÷èâàåòñÿ, õîòÿ îïöèÿ
AP> ðàáîòàåò ;)
 ARJ 2.62 è âûøå. À õåëï y íàñ påàëüíîñòè íå ñîîòâåòñòâyåò yæå äàâíî.
Åùå èç pÿäà íåäîêyìåíòèpîâàííûõ êëþ÷åé: ARJ a <filename> -hdd32750. Îápàòíî pàñ
ïàêîâàòü ïîëy÷èòñÿ òîëüêî ARJZ'îì, íî çàòî ýêîíîìèÿ êàêàÿ. ;)
Sincerely yours - Andrew
---
* Origin: ARJ Software Russia (2:5020/181.2)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/400 28 Jul 00 14:02:31
To : ZAB
Subj : Re: ×òî ïîñîâåòóåòå?
From: "Vadim Yoockin" <vy@thermosyn.com>
Hello, ZAB ! You wrote:
>> Òîãäà òåáå åñòü, çà ÷òî áîðîòüñÿ :)
>> Hî ýòî âðÿä ëè èç-çà ðàçìåðà áëîêà - âåäü â szip'e åãî ìîæíî
>> óêàçàòü äîñòàòî÷íî áîëüøîé.
>
>Hî íå íà 3 ìåãà!
Ïî÷åìó? Òîëüêî ÷òî ïîñìîòðåë: îò 100k äî 4.1Mb.
>Hó ÷òî æ áóäó ìó÷àòü ðàäèêñ!
Âñåãî äîáðîãî,
Âàäèì.
P.S. À ó òåáÿ íà êëàâèòàòóðå êíîïêà '.' ðàáîòàåò? ;)
--- ifmail v.2.15dev5
* Origin: Fidolook Express http://fidolook.da.ru (2:5020/400)
— RU.COMPRESS
From : Dmitry Ilyin 2:5020/400 28 Jul 00 19:01:59
To : All
Subj : Àðõèâ ýõè ru.compress ïåðååõàë
From: "Dmitry Ilyin" <w@thg.org>
Ñàáæ íà http://www.bigarh.com/compress/
--
WBR, Dmitry Ilyin
http://www.bigarh.com/
--- ifmail v.2.15dev5
* Origin: Network Information Center (2:5020/400)
— RU.COMPRESS
From : Vadim Yoockin 2:5020/1042.50 28 Jul 00 20:09:24
To : All
Subj : For information
Ïpèâåòñòâóþ, All!
Îçíàêîìèòüñÿ ñî ñæàòèåì êàðòèíîê ñ òåêñòàìè DJVU îò AT&T ìîæíî íà
http://djvu.research.att.com/home_mstr.html
Ñòàòüè îäíîãî èç àâòîðîâ åñòü íà
http://www.research.att.com/~leonb/biblio.html
Êðîìå òîãî, íà êîìïðåññêîíñàëòèíãîâîì ñàéòå Øèíäëåðà ïîÿâèëàñü
àëüôà SZIP 1.10. Hîâàÿ âåðñèÿ çàìåòíî áûñòðåå ïðåäûäóùèõ. Êñòàòè,
êàê è ïîäîçðåâàëîñü, äëÿ äîæàòèÿ èñïîëüçóåòñÿ rangecoder - îá ýòîì
ÿâíî ñêàçàíî â techinfo.txt.
Âñåãî äîáðîãî. Vadim Yoockin
... 2.000.000 Lemmings can't be wrong.
--- Ñòàpûé Äåä ñòîèìîñòüþ 3.00.Alpha4 äîïëàòà â ÑÊÂ UNREG
* Origin: mail to yoockinv@aha.ru (2:5020/1042.50)
— RU.COMPRESS
From : Serg Tikhomirov 2:5020/122.166 28 Jul 00 23:07:19
To : All
Subj : Short FAQ v.0.001 ;)
Çäpàâñòâyé, All!
Ïåpâàÿ âåpñèÿ FAQ-à ïî ïpîñòûì âîïpîñàì, òpåáóþùèì îòíîñèòåëüíî êîpîòêèõ îòâ
åòîâ. Åñëè ó âàñ åñòü ïîïpàâêè è äîïîëíåíèÿ - ïpèñûëàéòå.
--------------------------------
Q: A ôaê y âac òyò ecòü?
A: Òåïåpü - åñòü ;).
--------------------------------
Q: À ÷òî ýòî âîîáùå òàêîå - ñæàòèå? Êàê âîîáùå ìîæíî ÷òî-òî ñæàòü?
A: Ïpîöåññ óñòpàíåíèÿ èçáûòî÷íîñòè. Âîçüì¸ì äëÿ ïpèìåpà ïóñòóþ êàpòîííóþ êîpîáê
ó îò ìîíèòîpà pàçìåpîì 50*50*50 ñì (êñòàòè, â òàêóþ êîpîáêó ìîæíî óïàêîâàòü ñpå
äíåñòàòèñòè÷åñêîãî ãpàæäàíèíà, ñêàæåì, Âàñþ Ïóïêèíà, pîñòîì 175-180 ñì è ìàññîé
75-80 êã; ìû ê íåìó åù¸ âåpí¸ìñÿ ;).  pàçëîæåííîì âèäå êîpîáêà èìååò îáú¸ì 0.
125 êóáîìåòpà, íî åñëè å¸ ñëîæèòü ïî ñãèáàì, òî ìû ïîëó÷èì ïëîñêèé ïàêåò pàçìåp
îì 1*1ì. Ïîíÿòíî, ÷òî õpàíèòü êîpîáêó â òàêîì âèäå óäîáíåå (à åñëè ïåpåãíóòü å¸
è ïî îñòàëüíûì ñãèáàì, òî ïëîùàäü ïîëó÷åííîãî ïàêåòà áóäåò åù¸ ìåíüøå), çàòî è
ñïîëüçîâàòü ïî ïpÿìîìó íàçíà÷åíèþ áåç íåêèõ ïpåäâàpèòåëüíûõ äåéñòâèé íåâîçìîæíî
. Òî æå ñàìîå è ñ äàííûìè - ïpîñòî ïpîöåññ óñòpàíåíèÿ èçáûòî÷íîñòè íå âñåãäà ñò
îëü æå î÷åâèäåí.
Ñàìûì, íàâåpíîå, î÷åâèäíûì ñïîñîáîì óñòpàíåíèÿ èçáûòî÷íîñòè ÿâëÿåòñÿ RLE (Ru
n Length Encoding) - çàìåíà öåïî÷êè ïîâòîpÿþùèõñÿ ñèìâîëîâ íà äëèíó ïîâòîpåíèÿ
(ñàì ñèìâîë òîæå íàäî ñîõpàíèòü). Òàê, öåïî÷êà âèäà "ÀÀÀÀÀÀÀÀÀ" áóäåò çàìåíåíà
íà {'À', 9}, ãäå 'À' - ïîâòîpÿþùèéñÿ áàéò, à 9 - ñ÷¸ò÷èê ïîâòîpåíèé. Åñëè ñ÷¸ò÷
èê ïîâòîpåíèé áóäåò îäíîáàéòíûì, òî ìîæíî çàêîäèpîâàòü äâóìÿ áàéòàìè äî 255 îäè
íàêîâûõ áàéò! Hî è ýòî íå ïpåäåë. Ìîæíî ó÷åñòü, ÷òî äëèíà ïîâòîpåíèÿ íå ìîæåò á
ûòü ìåíüøå 2 - è òîãäà çíà÷åíèå ñ÷¸ò÷èêà pàâíîå 0 áóäåò îçíà÷àòü, ÷òî äëèíà öåï
î÷êè ïîâòîpåíèé - 2 áàéòà. Ñîîòâåòñòâåííî, ìàêñèìàëüíîå çíà÷åíèå äëèíû ñîñòàâèò
257 áàéò. Ïpèìåíÿþòñÿ è äpóãèå óõèùpåíèÿ.
Âòîpûì ïî î÷åâèäíîñòè, âèäèìî, ÿâëÿåòñÿ îpãàíèçàöèÿ ñëîâàpÿ è çàìåíà ñëîâ â
èñõîäíîì òåêñòå íà èõ ïîpÿäêîâûå íîìåpà â ñëîâàpå. ×åì äëèííåå çàìåíÿåìûå ñëîâà
è êîpî÷å íîìåpà, òåì âûøå ñòåïåíü ñæàòèÿ.
Ýòè ñïîñîáû (è èõ ìîäèôèêàöèè) èìåþò ïpàâî íà ñóùåñòâîâàíèå, íî ïîêàçûâàþò â
îáùåì ñëó÷àå íåâûñîêèå påçóëüòàòû. Ãîpàçäî ëó÷øèõ ïîêàçàòåëåé ìîæíî äîáèòüñÿ,
èñïîëüçóÿ àëãîpèòìû ñåìåéñòâà LZ* è äpóãèå, áîëåå ìîùíûå.
--------------------------------
Q: À ÷òî ýòî çà LZ* àëãîpèòìû?
A: (VS) Â 1977 ãîäó Ëåìïåë (Lempel) è Çèâ (Ziv) îïóáëèêîâàëè ñòàòüþ â "Òpóäàõ
ïî òåîpèè èíôîpìàöèè" (æópíàë) ïîä íàçâàíèåì "A universal algorithm for
sequential data compression". Òàì áûë îïèñàí àëãîpèòì, êîòîpûé ïpèíÿòî
íàçûâàòü LZ77 (ZL77 - äàííîå íàçâàíèå påäêî óïîòpåáëÿåòñÿ). Äàííûé àëãîpèòì
ñòàë ïåpâûì â öåëîì pÿäó ñëîâàpíûõ àëãîpèòìîâ ñæàòèÿ, îáúåäèíÿåìûõ â åäèíîå
ñåìåéñòâî LZ77. Ê äàííîìó ñåìåéñòâó îòíîñÿòñÿ: LZ77 (Lempel, Ziv; 1977), LZR
(Roden; 1981), LZSS (Storer, Szymanski, Bell; 1982 - 86), LZB (Bell;1987),
LZH (Brent; 1987), LZRW1 - LZRW3 ñ âàpèàöèÿìè (Williams; 1990-91 (LZRW1
âïåpâûå áûë ïpåäëîæåí íå Óèëüÿìñîì)). Ñþäà ìîæíî òàêæå îòíåñòè äâóõópîâíåâûå
ñëîâàpíûå àëãîpèòìû òèïà LZHUF, LZARI (Okumura; 1988), êîòîpûå ëåæàò â
îñíîâå LHA, ZIP, GZIP, ARJ, HA "a1", RAR, ACE, JAR, IMP "-1" è ò. ä. Èäåÿ
âñåõ àëãîpèòìîâ ãpóïïû ñîñòîèò â ñëåäóþùåì: â êà÷åñòâå ñëîâàpÿ ïîèñêà
âûñòóïàåò íåêîòîpàÿ ÷àñòü óæå îápàáîòàííîé èíôîpìàöèè (ôèêñèpîâàííîé èëè
íåôèêñèpîâàííîé äëèíû), íåïîñpåäñòâåííî ïpåäøåñòâóþùàÿ òåêóùåé
îápàáàòûâàåìîé ïîçèöèè. Ïîèñê ïpåñëåäóåò ñâîé öåëüþ íàõîæäåíèå ìàêñèìàëüíîãî
(èëè íå ñîâñåì ìàêñèìàëüíîãî :) ), ñîâïàäåíèÿ òåêóùåé îápàáàòûâàåìîé
ïîñëåäîâàòåëüíîñòè ñ êàêîé-òî óæå îápàáîòàííîé ïîñëåäîâàòåëüíîñòüþ.
Hàéäåííîå ñîâïàäåíèå êîäèpóåòñÿ ïóòåì óêàçàíèÿ ñìåùåíèÿ íà÷àëüíîé ïîçèöèè
ñîâïàäàþùåé ïîñëåäîâàòåëüíîñòè â ñëîâàpå ïîèñêà (÷àùå âñåãî ñìåùåíèå áåpåòñÿ
îòíîñèòåëüíî òåêóùåé ïîçèöèè) è äëèíû ñîâïàäåíèÿ. Ïîñëåäíåå ÿâëÿåòñÿ îäíèì
èç îñíîâíûõ àòpèáóòîâ ñåìåéñòâà. (Çàìåòèì íà äàííîì ýòàïå, ÷òî ïpî
êîíêpåòíûé ñïîñîá êîäèpîâàíèÿ çäåñü íè÷åãî íå ãîâîpèòñÿ. )
Pàññìîòpèì äâà ïpîñòåéøèõ àëãîpèòìà ñåìåéñòâà LZ77: LZ77 è LZSS. Áóäåì
êîäèpîâàòü ñëîâî "îáîpîíîñïîñîáíîñòü", èñïîëüçóÿ ñëîâàpü ïîèñêà ñ
ôèêñèpîâàííûì pàçìåpîì, pàâíûì 7 ñèìâîëàì (äëÿ çàïèñè ñìåùåíèÿ òpåáóåòñÿ 3
áèòà (îäíî çíà÷åíèå çàpåçåpâèpîâàíî ïîä óêàçàíèå îòñóòñòâèÿ ñîâïàäåíèÿ)), è
áóôåpîì ïîèñêà ñ ôèêñèpîâàííûì pàçìåpîì, pàâíûì 2 ñèìâîëàì (òàêèì îápàçîì,
äëÿ óêàçàíèÿ äëèíû òpåáóåòñÿ 1 áèò). Êîä äëÿ ñëîâà, ïîëó÷åííûé ñ ïpèìåíåíèåì
àëãîpèòìà LZ77, áóäåò âûãëÿäåòü ñëåäóþùèì îápàçîì:
<0,0,"î"><0,0,"á"><2,1,"p"><2,1,"í"><2,1,"ñ"><0,0,"ï"><3,2,"î"><0,0,"á">
<0,0,"í"><4,2,"ò"><0,0,"ü">.
Äëèíà êàæäîé êîäîâîé òpèàäû pàâíà 12 áèòàì, åñëè èñõîäíûé àëôàâèò ñîñòîèò èç
256 ñèìâîëîâ (12 = 3 + 1 +8). Ïpè pàññìîòpåíèè àëãîpèòìà LZSS óâåëè÷èì
ñëîâàpü ïîèñêà íà 1 ñèìâîë, òàê êàê â äàííîì ñëó÷àå íåò íåîáõîäèìîñòè
påçåpâèpîâàòü íóëåâîå ñìåùåíèå äëÿ óêàçàíèÿ îòñóòñòâèÿ ñîâïàäåíèÿ.
Àëãîpèòìîì LZSS çàêîäèpóåò pàññìàòpèâàåìîå ñëîâî òàê:
0<"î">0<"á">1<2,1>0<"p">1<2,1>0<"í">1<2,1>0<"ñ">0<"ï">1<3,2>1<2,1>0<"á">1
<8,3>0<"ò">0<"ü">.
Äëÿ çàïèñè ñëóæåáíûõ áèòîâ òpåáóåòñÿ îäèí áèò, äëÿ çàïèñè êîäîâîé ïàpû - 3 +
1 = 4 áèòà, à äëÿ çàïèñè íåçàêîäèpîâàííîãî ñèìâîëà - 8 áèò. Ââåäåíèå
ñëóæåáíîãî áèòà, êîòîpûé pàçëè÷àåò íåçàêîäèpîâàííûå ñèìâîëû è êîäîâûå ïàpû,
ïîçâîëÿåò ïîâûñèòü ýôôåêòèâíîñòü ñæàòèÿ. ( ïåpâîì ñëó÷àå êîýôôèöèåíò ñæàòèÿ
pàâåí 92%, à âî âòîpîì - 77%.)
Êpîìå pàçëè÷èÿ â ñïîñîáå êîäèpîâàíèÿ ìåæäó äàííûìè àëãîpèòìàìè ñóùåñòâóåò
òàêæå è íåêîòîpûå äpóãèå pàçëè÷èÿ, íà êîòîpûõ ÿ îñòàíàâëèâàòüñÿ íå áóäó.
Àëãîpèòì LZSS ÿâëÿåòñÿ òàêæå î÷åíü íåýôôåêòèâíûì.  öåëÿõ ïîâûøåíèÿ êà÷åñòâà
ñæàòèÿ íåîáõîäèìî ó÷èòûâàòü ñòàòèñòè÷åñêèå îñîáåííîñòè pàñïpåäåëåíèÿ
ñëóæåáíûõ áèòîâ, çíà÷åíèé ñìåùåíèé, äëèí ñîâïàäåíèé è íåçàêîäèpîâàííûõ
ñèìâîëîâ. Äëÿ ýòîãî ïpèìåíÿþòñÿ êîäû ïåpåìåííîé äëèíû, ïpè ïîñòpîåíèè
êîòîpûõ îáû÷íî èñïîëüçóåòñÿ îäíà èëè äâå ñòàòèñòè÷åñêèå ìîäåëè (ñì.
àëãîpèòìû LZHUF, LZARI è äp.). Â àëãîpèòìàõ LZB è LZH èñïîëüçóåòñÿ
óïpîùåííûé ïîäõîä, êîòîpûé ÿ òàêæå îñòàâëÿþ çà pàìêàìè äàííîãî îáúÿñíåíèÿ.
×òî æå êàñàåòñÿ íåýôôåêòèâíîñòè àëãîpèòìà LZ77, ñâÿçàííîé ñ îáÿçàòåëüíîñòüþ
ñëåäîâàíèÿ íåçàêîäèpîâàííîãî ñèìâîëà ïîñëå êîäîâîé ïàpû, îïèñûâàþùåé
ñîâïàäåíèå, òî çäåñü íå âñå òàê ïëîõî. Â îñíîâå äàííîãî ïîäõîäà ëåæèò òîò
ôàêò, ÷òî ñîâïàäåíèÿ íå ÷àñòî ñëåäóþò äpóã çà äpóãîì (ÈHÎÃÄÀ îíè îêàçûâàþòñÿ
ñîñòàâëÿþùèìè îäíîãî áîëåå äëèííîãî ñîâïàäåíèÿ). Hî ó÷åò âåpîÿòíîñòíîãî
pàñïpåäåëåíèÿ ñëóæåáíûõ áèòîâ â LZSS ÿâëÿåòñÿ, áåçóñëîâíî, áîëåå ýôôåêòèâíûì
ïîäõîäîì. Êñòàòè, â LZP3 òàêæå èñïîëüçóåòñÿ ïîäõîä èç LZ77, íî òàì îí, êàê
ìíå êàæåòñÿ, áîëåå îïpàâäàí.
--------------------------------
Q: Pàçúÿñíèòå ïëèç LZW íà ïàëüöàõ. ß ÷òî-òî íå ñîâñåì ïîíèìàþ êàê
îí pàáîòàåò.
A: (BZ) íà ïàëüöàõ - çàìåíÿåì ñëîâà èõ íîìåpàìè â äèíàìè÷åñêè êîíñòpóèpóåìîì ñë
îâàpå. ïåpâîíà÷àëüíî ñëîâàpü ñîñòîèò òîëüêî èç îäèíî÷íûõ áóêâ. åñëè ñëîâî, êîòî
pîå åñòü â ñëîâàpå, âñòpå÷àåòñÿ â òåêñòå, òî â ñëîâàpü äîáàâëÿåòñÿ ñëîâî íà îäí
ó áóêâó áîëüøå
--------------------------------
Q: À êàêèå åù¸ åñòü ýôôåêòèâíûå àëãîpèòìû?
A: Ñòàòèñòè÷åñêèå. Hàïpèìåp, àëãîpèòì Õàôôìàíà, àpèôìåòè÷åñêèé, PPM, ìàpêîâñêèé
...  îòëè÷èå îò âûøåpàññìîòpåííûõ ñëîâàpíûõ (ãäå êîäèpóåòñÿ ñîâïàäåíèå öåïî÷êè
ñèìâîëîâ ñ óæå îápàáîòàííûìè äàííûìè), ýòè àëãîpèòìû îïåpèpóþò âåpîÿòíîñòÿìè â
ñòpå÷àþùèõñÿ ñèìâîëîâ (êàê ñàìèõ ïî ñåáå - Õàôôìàí, àpèôìåòèêà), òàê è â çàâèñè
ìîñòè îò êîíòåêñòà (ïpåäûäóùèõ ñèìâîëîâ - PPM, ìàpêîâñêîå êîäèpîâàíèå) è ìîãóò
èñïîëüçîâàòüñÿ â ñîñòàâå äâóõópîâíåâûõ ñõåì òèïà LZHUF (Lempel-Ziv + Huffman),
ò.å. ïî Õàôôìàíó ñæèìàåòñÿ íå èñõîäíûé òåêñò, à påçóëüòàò pàáîòû LZ-øíîãî àëãîp
èòìà. Ýòî ãîpàçäî ýôôåêòèâíåå, ÷åì èñïîëüçîâàíèå êàæäîãî èç ýòèõ ìåòîäîâ ïî îòä
åëüíîñòè. Åñòü åù¸ àëãîpèòì ACB, pàçpàáîòàííûé Ãåîpãèåì Áóÿíîâñêèì è îïóáëèê
îâàííûé â æópíàëå "Ìîíèòîp" #8'94. Êëàññèôèöèpîâàòü åãî (àëãîpèòì ;) çàòpóäíÿþò
ñÿ äàæå ãpàíäû RU.COMPRESS ;).
--------------------------------
Q: À ÷òî òàêîå ñæàòèå ñ ïîòåpÿìè?
A: Âåpí¸ìñÿ ê óïîìÿíóòîìó Âàñå Ïóïêèíó ;). Åñëè îí - îïûòíûé éîã (ò.å. ïîäãîòîâ
ëåí îñîáûì îápàçîì), òî íå ñîñòàâèò îñîáîãî òpóäà çàñóíóòü åãî â óïîìÿíóòóþ êîp
îáêó. Åñëè æå îí îáû÷íûé ïpîãpàìì¸p, ñ ápþøêîì, øåéíûì îñòåîõîíäpîçîì è íåãíóùè
ìèñÿ ñóñòàâàìè, òî ïîìåñòèòñÿ îí â êîpîáêó òîëüêî ïî ÷àñòÿì ;). Ïpàâäà, ïîñëå è
çâëå÷åíèÿ èç îíîé êîpîáêè åãî íåëüçÿ áóäåò âîññòàíîâèòü â èñõîäíîì âèäå. Âîò ýò
î îíî è åñòü - ñæàòèå ñ ïîòåpÿìè ;).
À åñëè ñåpü¸çíî - ýòî àëãîpèòìû âûáîpà òîãî, ÷åì ìîæíî ïîæåpòâîâàòü pàäè óìå
íüøåíèÿ îáú¸ìà äàííûõ.  ÷àñòíîñòè, GIF æåpòâóåò êîëè÷åñòâîì öâåòîâ íà êàpòèíêå
(íå áîëåå 256), JPEG - ìåëêèìè äåòàëÿìè èçîápàæåíèÿ (è ÷åì êpóïíåå ýòè ïîòåpÿí
íûå äåòàëè, òåì ñèëüíåå ñòåïåíü ñæàòèÿ) è ò.ä.  JPEG (â îáùèõ ÷åpòàõ) âûáèpàåò
ñÿ pàçìåp ýëåìåíòà èçîápàæåíèÿ, äëÿ êîòîpîãî óñpåäíÿåòñÿ çíà÷åíèå öâåòà, à ïîòî
ì ïîëó÷åííûé íàáîp öâåòîâ äëÿ ýëåìåíòîâ èçîápàæåíèÿ äîæèìàåòñÿ Õàôôìàíîì.  çâó
êîâûõ ôîpìàòàõ æåpòâóþò êà÷åñòâîì çâóêà (ñíèæàÿ ÷àñòîòó äèñêpåòèçàöèè, íàïpèìåp
).
--------------------------------
Q: E8 - ýòî ÷òî?
A(BZ): Ýòî êîãäà _ÑÌÅÙÅHÈÅ_, çàïèñûâàåìîå â àññåìáëåpíîì êîäå ïîñëå êîìàíäû E8
(relative near call), çàìåíÿåòñÿ íà _ÀÁÑÎËÞÒHÛÉ_ÀÄPÅÑ_. Ïîñêîëüêó åñòü êàêîé-òî
íå î÷åíü áîëüøîé íàáîp àäpåñîâ ïîäïpîãpàìì, ñòåïåíü èçáûòî÷íîñòè ôàéëà óâåëè÷è
âàåòñÿ.
--------------------------------
Q: À ïî÷åìó ïàêîâàíàÿ win32 ïpîãpàììà â ïàìÿòè ìåñòà áîëüøå çàíèìàåò, ÷åì
íåïàêîâàííàÿ?
A(RT): Ñ îáû÷íîé ïpîãpàììîé ìåíåäæåp ïàìÿòè ìîæåò à) íå ÷èòàòü íóæíûé êóñîê
êîäà ñ äèñêà, ïîêà èñïîëíåíèå íå äîéäåò äî ýòîãî ìåñòà; á) ïpè íåõâàòêå
ïàìÿòè íå çàñîâûâàòü ñòpàíèöó â ñâîï, à ïpîñòî âûêèíóòü -- åå ñîäåpæèìîå íåèçìå
ííî è âñåãäà ì.á. ïåpå÷èòàíî èç èñõîäíîãî ôàéëà; â) äëÿ íåñêîëüêèõ êîïèé çàïóùå
ííîé ïpîãpàììû èëè DLL èñïîëüçîâàòü îäèí è òîò æå êóñîê ôèçè÷åñêîé ïàìÿòè äëÿ õ
pàíåíèé êîäà -- ñîäåpæèìîå æå îäèíàêîâîå. Âñå ýòî ýêîíîìèò ôèçè÷åñêóþ ïàìÿòü è
âpåìÿ.
Ïàêîâàííàÿ ïpîãpàììà äîëæíà pàñïàêîâàòüñÿ öåëèêîì -- ìåíåäæåp ïàìÿòè äîëæåí
âûäåëèòü ôèçè÷åñêîé ïàìÿòè ïîä _ïîëíûé_ îáúåì ïpîãpàììû; ñòpàíèöû, êóäà pàñïàêî
âàëîñü, óæå íå ìîãóò áûòü ïpîñòî òàê âûêèíóòû èç ïàìÿòè -- â íèõ æå _ïèñàëîñü_,
ìåíåäæåp òåïåpü îáÿçàí ñëèâàòü èõ ñâîï. Ïóíêò (â) âîîáùå îòïàäàåò -- pàç â ñòp
àíèöû ïèñàëîñü, áóäåì äåpæàòü ñâîþ êîïèþ äëÿ êàæäîãî ýêçåìïëÿpà ïpîãpàììû/DLL.
Ïîýòîìó ïàêîâàòü áîëüøèå ïàêåòû òèïà îôèñà èëè ñèñòåìíûå DLL -- ñàìîóáèéñòâî
. Òpåáîâàíèÿ ê ôèçè÷åñêîé ïàìÿòè âîçpàñòàþò â íåñêîëüêî pàç.
Ýòèõ îãpàíè÷åíèé íåò, íàñêîëüêî ÿ çíàþ, òîëüêî â OS/2, ãäå pàñïàêîâêà ñòpàíè
ö âñòpîåíà â ñàìî ÿäpî, â ìåíåäæåp ïàìÿòè.
--------------------------------
Q: Êàê âçëîìàòü ïàpîëü íà...
A: ZIP: (SB) ápóòýôîpñ ;)
(SZ) Äëÿ ZIP åñòü ìåòîä äëÿ èçâåñòíîãî íåçàøèôpîâàíîãî òåêñòà (íå íåçàï
àêîâàííîãî, à èìåííî çàïàêîâàííîãî è íåçàøèôpîâàíîãî;).
RAR: Îí æå, BruteForce.
--------------------------------
Q: À-à-à! À ÷òî òàêîå ápóòýôîpñ?
A: Ïåpåáîp. Âîçìîæíû âàpèàíòû:
à) ïåpåáîp _âîîáùå_âñåõ_ âîçìîæíûõ ïàpîëåé (a, b, ... aab, aac, ...);
á) ïåpåáîp "îãpàíè÷åííûé" - êîãäà ñíà÷àëà òùàòåëüíî ñîñòàâëÿåòñÿ íàáîp âîçìîæíû
õ ñèìâîëîâ ïàpîëÿ, à ïîòîì ñì à);
â) ïåpåáîp "ñëîâàpíûé" - ÷àñòî ïàpîëÿìè ñëóæàò îñìûñëåííûå ñëîâà, òóò ìîæåò îêà
çàòüñÿ äîñòàòî÷íûì è íåáîëüøîé ñëîâàpèê èç pàñïpîñòpàí¸ííûõ èì¸í, ÷åòûp¸õçíà÷íû
õ ÷èñåë (ãîä pîæäåíèÿ è ïp.) è, ïàpäîí, ìàòåpíûõ ñëîâ;
ã) ïåpåáîp îòäåëüíûõ ñèìâîëîâ ïàpîëÿ - íàïpèìåp, ìû çíàåì ïÿòü èç äåñÿòè áóêâ ï
àpîëÿ è âèäåëè, êóäà ïpèìåpíî äîòÿãèâàëèñü ïàëüöû åãî àâòîpà. Òóò íå íàäî ïåpåá
èpàòü âñ¸ - äîñòàòî÷íî çàäàòü íåêèå íàáîpû ñèìâîëîâ äëÿ êîíêpåòíûõ ïîçèöèé ïàpî
ëÿ. Ê ñëîâó - ïîèñê ïåpåáîpîì òèïà à) äåñÿòèñèìâîëüíîãî ïàpîëÿ íà àpõèâ RAR ìîæ
åò íå çàêîí÷èòüñÿ ïpè æèçíè íûíåøíåãî ïîêîëåíèÿ ;(.
--------------------------------
Q: À ãäå îáî âñ¸ì ýòîì ìîæíî ïî÷èòàòü ïîäpîáíåå?
A:  ÷àñòíîñòè, çäåñü.  ýõó RU.COMPRESS áóäóò ïåpèîäè÷åñêè ïîñòèòüñÿ îïèñàíèÿ
àëãîpèòìîâ (âpîäå BWT FAQ Âàäèìà Þêèíà). Î÷åíü ïîìîãàåò èçó÷åíèå pàçíûõ ñòàòåé
è èñõîäíèêîâ (ãîâîpÿò, èõ åñòü â ôàéë-ýõàõ ADEVCOMP è AUTLCOMP). Hó è íåêîòîpîå
êîëè÷åñòâî ññûëîê â èíåòå:
ftp.elf.stuba.sk/pub/pc/pack - àpõèâàòîpû, èñõîäíèêè, ÅÕÅïàêåpû, îáîëî÷êè, óíïà
êåpû, óòèëèòû, ...
Ñòàòüè îá ýõîòàãå:
http://sochi.net.ru/~maxime/compression.shtml
http://www.compression-pointers.com
http://www.hn.is.uec.ac.jp/~arimura/compression_links.html
http://algo.4u.ru/ - Pàçäåë "Êîìïpåññèÿ".
Hîâûé ACE (íå ñòèpàëüíûé ïîpîøîê, à ìîùíûé àpõèâàòîp ;) :
http://www.winace.com/ftp/ace20b1.exe
ftp://fido.urc.ac.ru/pub/fileecho/os2/gfd.app.arc/ace20b1.exe
ftp://ftp.mikon.ru/FILEECHO/GFD/APP/ARC/ace20b1.exe
ftp://ddt.demos.su/pub/fileecho/GFD.APP.ARC/ace20b1.exe
Cabarc SDK:
http://download.microsoft.com /download/platformsdk/Update/1/WIN98/EN-US/
CAB-16.cab
--------------------------------
Èíèöèàëû â ñêîáêàõ:
BZ - Bulat Ziganshin (2:5093/28.126)
RT - Roman Trunov (2:5022/2)
SB - Sergey Borodachev
SZ - Serguey Zefirov (2:5020/313.9)
VS - Vladimir Semenjuk
Âñåãî íàèëó÷øåãî!
Jee
---
* Origin: Åñëè êòî-òî êîå-ãäå ó íàñ ïîpîé - òàê åìó è íàäî! (2:5020/122.166)
— RU.COMPRESS
From : Sergey Borodachev 2:5048/7.6 29 Jul 00 12:22:00
To : All
Subj : Äåðåâî :_)
Hello, All
Îáúÿñíèòå ïëèç êàê ëó÷øå õðàíèòü äåðåâî, ÷òîáû äîñòóï ê åãî ýëåìåíòàì îñóùå
ñòâëÿëñÿ ñ ìàêñèìàëüíîé ñêîðîñòüþ. È êàê âîîáùå ïðàâèëüíî ñòðîèòü ýòî äåðåâî, å
ñëè èçâåñòíà ÷àñòîòà âñòðå÷àåìîñòè ñèìâîëîâ(ïîäêèíüòå ïðèìåð÷èê íà C/C++/PAS/AS
M)? Êàê áûñòðî ïåðåñòðîèòü ýòî äåðåâî(äëÿ äèíàì. õàôôìàíà, ê ïðèìåðó)? ;-) Ñïàñ
èáî çàðàíåå.
With respect, Sergey.
--- GoldED+/386 1.1.3.2
* Origin: (2:5048/7.6)
— RU.COMPRESS
From : Helgy Green 2:5020/400 29 Jul 00 14:04:30
To : All
Subj : Re: Ýíòpîïèÿ
From: "Helgy Green" <helgy@mf.stu.ru>
Ðàçäåë ìàòåìàòèêè "ñòàòèñòèêà. íîðìàëüíîå ðàñïðåäåëåíèå".
ß äåëàë ïðîñòî - ïîäñ÷èòàâàë, ñêîëüêî êàêèõ áàéò â ôàéëå, à ïîòîì îòîáðàæàë
ãðàôè÷åñêè. Êàðòèíêà 200õ256 ïèêñåëîâ. Ëóòøå ïîáîëå. Êîëè÷åñòâî îäèíàêîâûõ
áàéò îòîáðàæàòü ñòîëáèêàìè, ÷òîáû íå ïðîïóñòèòü òî÷êó. Åñëè åñòü
ñïåêòðàëüíûå ëèíèè - íåëàåø âûâîä.
Helgy
Alexey Komarov <Alexey.Komarov@p1.f66.n5054.z2.fidonet.org> wrote in message
news:964561689@p1.f66.n5054.z2.ftn...
> Ïpèâåò, Eugene!
>
> 26 Èþë 00 â 02:00 òû ïèñàë All:
>
> EG> Êàê èçìåpèòü ýíòpîïèþ ôàéëà ?
>
> À õîòÿ áû äèñïåpñèþ äëÿ íà÷àëà ïîñ÷èòàòü è ñpàâíèòü ñ íàéäåííîé äëÿ
èçâåñòíûõ
> òèïîâ ôàéëîâ? Òàì yæå âàpèàíòû...
>
> Ïpîñòîé ñïîñîá - ïî ñòåïåíè ñæàòèÿ èçâåñòíûìè àpõèâàòîpàìè :))
>
> EG> ß òàê ïîëàãàþ, ÷òî y ôàéëà ñîñòîÿùåãî èç íyëåé îíà áyäåò ìààëåíüêàÿ à
> EG> y ñêàæåì doom.wad îíà áyäåò íåñêîëüêî ïîáîëüøå, êàê å¸ ÷èñëåííî
> EG> èçìåpèòü?
>
> À îíà âîîáùå èìååò òî÷íîå êîëè÷åñòâåííîå îïpåäåëåíèå? :-\
>
>
> Ñ yâàæåíèåì,
> Alexey
>
--- ifmail v.2.15dev5
* Origin: Siberian state transport university (2:5020/400)
— RU.COMPRESS
From : Andrey Romanov 2:5052/13.10 30 Jul 00 03:20:00
To : Bulat Ziganshin
Subj : SoftNews
Hello Bulat.
27 Jul 00 22:55, Bulat Ziganshin wrote to All:
BZ> Hàéäåí íîâûé àëãîpèòì êîìïpåññèè...
BZ> 17:10
BZ> Êîìïüþòåpíûå èññëåäîâàòåëè èç Bell Labs, ÿâëÿþùåéñÿ ïîäpàçäåëåíèåì
BZ> Lucent Technologies è Êàëèôîpíèéñêîãî Òåõíîëîãè÷åñêîãî Èíñòèòóòà,
BZ> pàçpàáîòàëè ïåpâóþ òåõíîëîãèþ, ïîçâîëÿþùóþ ïpàêòè÷åñêè ïåpåäàâàòü
BZ> äåòàëèçèpîâàííûå òp¸õìåpíûå èíôîpìàöèîííûå îáúåêòû, è pàáîòàòü ñ ýòèì
BZ> òèïîì äàííûõ íà ïåpñîíàëüíûõ êîìïüþòåpàõ. Àíîíñ áûë ïpîèçâåä¸í íà
BZ> âûñòàâêå SIGGRAPH 2000. Ðåâîëþöèîííûé àëãîpèòì íàçûâàþò _digital
BZ> geometry compression_. Ãåîìåòpè÷åñêîå ïpåäñòàâëåíèå âàpüèpóåòñÿ îò
BZ> ÷åpòåæåé àâèàëàéíåpà äî ïåpñîíàæåé êîìèêñîâ. Äåòàëüíàÿ èíôîpìàöèÿ î
Ñæàòèå ãåîìåòðèè äîñòàòî÷íî äàâíî è õîðîøî èçy÷åíî.  ðàìêàõ 2õ øêîë ñyùåñòâyþ
ò äåñÿòêè îòëè÷íûõ àëãîðèòìîâ ñæàòèÿ ãåîìåòðèè ñ ïîòåðÿìè è áåç, .
Hàïðèìåð ìåòîä 1é øêîëû 'Progressive Meshes' 1997 ãîäà
ñæèìàåò áåç ïîòåðü òåñòîâyþ ñòàòyþ Áyääû ðàçìåðîì 33 Mb äî 2mb è âäîáàâîê
îáëàäàåò ñâîéñòâîì 'Progressive transmission'.  äàííîì ñëy÷àå yæå ïåðâûå
78k äàäyò îòëè÷íîå êà÷åñòâî ìîäåëè.
Àëãîðèòìû 2é øêîëû ñæàòèÿ ñ ïîòåðÿìè îñíîâàíûå íà ïàðàìåòðèçàöèè ìîäåëè ñ ïîìî
ùüþ wavelets, harmonic maps, splines etc äàþò íåñðàâíèìî ëy÷øèå ðåçyëüòàòû.
È åùå...
Àíàëîãèè ñæàòèÿ ãåîìåòðèè ñ JPEG-4 ãîâîðÿò î íåêîòîðîé íåêîìïåòåíòíîñòè
àâòîðà.
Andrey
--- GoldED 3.00.Beta1+
* Origin: (2:5052/13.10)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/28.126 30 Jul 00 04:58:53
To : Sergey Borodachev
Subj : Äåðåâî :_)
* Originally in RU.COMPRESS
Hello Sergey!
Saturday July 29 2000, Sergey Borodachev writes to All:
SB> Îáúÿñíèòå ïëèç êàê ëó÷øå õðàíèòü äåðåâî, ÷òîáû äîñòóï ê åãî
SB> ýëåìåíòàì îñóùåñòâëÿëñÿ ñ ìàêñèìàëüíîé ñêîðîñòüþ. È êàê âîîáùå
SB> ïðàâèëüíî ñòðîèòü ýòî äåðåâî, åñëè èçâåñòíà ÷àñòîòà âñòðå÷àåìîñòè
SB> ñèìâîëîâ(ïîäêèíüòå ïðèìåð÷èê íà C/C++/PAS/ASM)? Êàê áûñòðî ïåðåñòðîèòü
SB> ýòî äåðåâî(äëÿ äèíàì. õàôôìàíà, ê ïðèìåðó)? ;-) Ñïàñèáî çàðàíåå.
òû äîñòàòî÷íî íàèâíî ñåáå âñå ýòî ïðåäñòàâëÿåøü. ÷òî òû êîíêðåòíî õî÷åøü ñäåëàò
ü?
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722
... Èíîãäà äëÿ òîãî, ÷òîáû èçìåíèòü ñâîå âîñïðèÿòèå ìèðà,
... ëþäè ïûòàþòñÿ èçìåíèòü ñàì ìèð
--- GoldED+/W32 1.1.2
* Origin: À ÷åì çàíèìàåòñÿ õåðîìàíòèÿ? (2:5093/28.126)
— RU.COMPRESS
From : Bulat Ziganshin 2:5093/28.126 31 Jul 00 13:01:46
To : Andrey Romanov
Subj : SoftNews
*** Answering a msg posted in area CARBON_COPIES (CARBON_COPIES).
* Originally in RU.COMPRESS
Hello Andrey!
Sunday July 30 2000, Andrey Romanov writes to Bulat Ziganshin:
AR> Ñæàòèå ãåîìåòðèè äîñòàòî÷íî äàâíî è õîðîøî èçy÷åíî.  ðàìêàõ 2õ øêîë
AR> ñyùåñòâyþò äåñÿòêè îòëè÷íûõ àëãîðèòìîâ ñæàòèÿ ãåîìåòðèè ñ ïîòåðÿìè è
AR> áåç, . Hàïðèìåð ìåòîä 1é øêîëû 'Progressive Meshes' 1997 ãîäà ñæèìàåò
AR> áåç ïîòåðü òåñòîâyþ ñòàòyþ Áyääû ðàçìåðîì 33 Mb äî 2mb è
AR> âäîáàâîê îáëàäàåò ñâîéñòâîì 'Progressive transmission'. Â äàííîì
AR> ñëy÷àå yæå ïåðâûå 78k äàäyò îòëè÷íîå êà÷åñòâî ìîäåëè. Àëãîðèòìû 2é
AR> øêîëû ñæàòèÿ ñ ïîòåðÿìè îñíîâàíûå íà ïàðàìåòðèçàöèè ìîäåëè ñ ïîìîùüþ
AR> wavelets, harmonic maps, splines etc äàþò íåñðàâíèìî ëy÷øèå
AR> ðåçyëüòàòû.
âñå ÿñíî, òîëüêî ÷òî çà øêîëû? îäíàêî, ïðèÿòíî, ÷òî â ýõå åñòü ñïåöèàëèñòû ñàìû
õ íåîæèäàííûõ íàïðàâëåíèé.
AR> È åùå...
AR> Àíàëîãèè ñæàòèÿ ãåîìåòðèè ñ JPEG-4 ãîâîðÿò î íåêîòîðîé
AR> íåêîìïåòåíòíîñòè àâòîðà.
â íîâîñòÿõ? ÷òî æ òû õî÷åøü :)
Bulat, mailto:bulatz@fort.tatarstan.ru, ICQ 15872722
... Èíîãäà äëÿ òîãî, ÷òîáû èçìåíèòü ñâîå âîñïðèÿòèå ìèðà,
... ëþäè ïûòàþòñÿ èçìåíèòü ñàì ìèð
--- GoldED+/W32 1.1.2
* Origin: À ÷åì çàíèìàåòñÿ õåðîìàíòèÿ? (2:5093/28.126)
— RU.COMPRESS
From : ZAB 2:5020/400 31 Jul 00 19:29:48
To : All
Subj : Re: Óïàêîâêà ñèãíàëà â real-time
From: "ZAB" <ZAnatolyB@Mail.ru>
Helgy Green <helgy@mf.stu.ru> ñîîáùèë â íîâîñòÿõ
ñëåäóþùåå:8l8oph$scg$1@leia.stu.ru...
> Ðåáÿòà, à ÷òî çà îñöèëîãðàô òàêîé?
> 16 áèò ðåàëüíî ïîëó÷èòü ïðîñòî íåëüçÿ. Ìàêñèìóì 14 áèò. Øóìû ìåøàþò. Â
> èíñòèòóòå ìåòðîëîãèè íàä ýòèì äîëãî òðóäèëèñü. Âñÿêàÿ ðåêëàìà, ãäå
ãîâîðèòñÿ
> áîëüøå, ëæåò. Â ñîóíä-áëàñòåðå 12 áèò.
> 4 áèòà âñåãäà íóëè.
Ñòîï! Èçâèíèòå, ÷òî âìåøèâàþñü! ß òóò ðåøèë ýòî âûñêàçûâàíèå ïðîâåðèòü!
Âðóáèë CoolEdit -> Record ñîçäàë íåáîëüøîé íîéç ïðè ïîìîùè âäóâàíèÿ â
ìèêðîôîí! Ñîõðàíèë â PCM è çàëåç òóäû.... Hè÷åãî ïîäîáíîãî! Âñå 16
èñïîëüçóþòñÿ! Äðóãîå äåëî, ÷òî îíè ìîæåò íå íåñóò íèêàêîé îñìûñëåííîé
èíôîðìàöèè, íî íå íóëè, ýòî òî÷íî!
ÇÛ: Ñ÷èòàéòå ìî¸ äîáàâëåíèå ïðîñòî ïîïðàâêîé! Ðàññóæäàéòå äàëüøå!
--- ifmail v.2.15dev5
* Origin: NeoToN (2:5020/400)
— RU.COMPRESS
From : Dima Kirnocenskij 2:5020/1129.11 31 Jul 00 20:25:02
To : All
Subj : ðóññêèå òåêñòû
Hello All.
Ñòðîèì ìîäåëè ðóññêîãî òåêñòà. Êà÷åñòâî ìîäåëè ïðåëàãàåòñÿ ïðîâåðÿòü ãåíåðàöèåé
ïî äàííîé ìîäåëè íîâîãî òåêñòà. Âîò ÷òî ïîëó÷àåòñÿ:
ñòàâèëñÿ ñëåäóþùèé ýêñïåðåìåíò - ñîáèðàëèñü êîíòåêñòû ñëåâà äëèíîé 5 ñèìâîëîâ,
çàïîìèíàëèñü âåðîÿòíîñòè, ïîòîì ïî ïîëó÷åííîé ìîäåëè ãåíåðèëñÿ òåêñò - íà÷àëüíà
ÿ èíèöèàëèçàöèÿ áåðåòñÿ îò ôîíàðÿ, à ïîòîì êèäàåòñÿ êóáèê ñ ðàñïðåäåëåíèåì âåðî
ÿòíîñòåé â ñîîòâåòñòâèè ñ òåêóùèì êîíòåêñòîì è âûäàåòñÿ ïîïàâøàÿñÿ áóêâà íà âûõ
îä. Âîò ðåçóëüòàò ðàáîòû íàä òåêñòîì Ïåëåâèíà
=== Begin RES ===
ÊÓËÈÑÜ ÎÒÊÓÄÀ ÏÎËÓ×ÈËÀ ÒÓÌÀH ÂÇÌÛË ÂÑÅ ÝÒÎ ÌÎÅÌÓ ÂÇÎÐÓ È ÒÜÌÅ ÄËÈHHÛÉ ÕÈÒÈHÎÊ ×
ÈÒÀÅÒ È ÂÛÊÈÄÛÂÀÒÜÑß ×ÒÎ ÒÎ ÂÛØËÀ ÇÀÂÒÐÀ ÒÅHÜÞ ÎÄHÎ ÂÛÑÒÓÏÀËÈ HÅÎÁÛ×ÀÉ ÄÛÌ ÄÂÈÃ
ΠÊÎÒÎÐÎÉ ÅÅ HÅ ÓÂÈÄÅHHÛÉ ÏÅHÜ ÒÈÕÈÉ ÏËÀH ÃÎÐÁÀ×ÅÂÓ HÎÃÓ ÏÎØËÈ ß HÅÒ ÏÎÄÀÒËÈÂÎ
É HÀ ÃÐÀÖÈÞ Â ÌÎÐÅ ÊÎÃÎ ÒÎËÜÊÎ ÏÅÐÅÄ ØÀÐ ÐÛÂÊÎÌ À ÒÅËÅ HÅ ÎÁÅÙÀÂØÈÅ ÎÒ ÏÅÐÂÀHÓË
Ñß
HÎ ÑÏÈHÅ ÁÛË ÁÅÇ ÂÑß Î ÑHÎÂÀß ÊÓÄÀ HÅÒ HÀ ËÞÁÎÉ ÁÛÂÀÅÒ ÑÏÐÎÑÒÎÄÓØHÀß
ËÓÏÓ
È HÀÄÎËÃÈÉ ÂÎÄÊÀ ×ÒÎ ÏÎÄHÅÅ ÊÎ ÌÈÐ
ÂÎÏÐÎÑÒÓÏÀÒÜÑß ÎÒ ÌÈHÓÒ
ÇÀ ÂÏÅ×ÀÒÜ ÑÏÐÀØÈÂÀËÈËÀÑÜ HÀ ÓÄÈÂÈÒÅËßÌ ×ÒÎ ÒÛ ÊÀÇÀËÎÑÜ ×ÒÎÁÛ ÎHÀ ÅÃÎ
È ×ÒÎ
ÂÑÅÌ ÁÓÌÀÃÅ ÊÐÛËÜÅÂ È ÁÛË ÄËÈHHÀß ÈÇ ÊÎÒÎÐÀß ÄÅÂßÒÊÀ ØÅÅ
ÎH HÅÑÊÎËÜÊÎ Ó ÒÅÁß
ÏÎÌÎ×È ÐÀÇ Â ÆÈÂÎÉ HÀ ÏÎÊÀÇÀË ÌÈÒÈ ÌÀËÜ×ÈÊÀ ÏÐÀÂÓ È ÑÊÀÇÀË ÎH ÏÐÀÂËÅHÈÂØÅÉÑß Á
Û Ê ÊÎÌÀHÄÎÂÀËÈÑÜ ÑÂÈÑÒÎÌ ÑÈÄÅHÜß ÇÀÒßÆÅËÎ ÑÎÂÅÐHÎÉ
ÏÎØËÎ ÎÒÂÅÒÈË ÑÊÀÐÀÁÅÈ ÇHÀÞ ÄÀÆÅ HÅ
ÎÒÂÅÒÈË ×ÒÎ ÁÓÄÅÌ ÎH ÁÛËÎ ÏÐÈÊΠÂÛÕËÎÏÀË ÂÇÃËßÄÅË ÏÐÈÄÀÒÜ ËÎÁ ÎÊÐÀØÅHHÎ
ÑÏÐÎÑÈË
ÄÈÌÛ ÏÎÃËßÄÅËÀ ÊÀÊ
ÃÐÓÄÈ ÔÀÊÒ ×ÒÎ ÁÛËÎ ÒÅÌHÓÞ ÓËÛÁÀ ÌÀÐÈHÀ ÊÎÒÎÐÎÃÈ Â ÏÅÒÅÐ ÑÎÐÂÀË ÎÒ ÓÄÀÐ ÒÀÊÎÅ Î
×ÅHÛÕ È ÇËÛÌ ÏÑÅÂÄÎÑËÀÂÀËÎÌ
ÈÇ ÅÅ
ÃËÓÁÎÉ Ñ ÊÐÎÂÈH === End RES ===
ò.å. âïîëíå ðóññêèå ñëîâà.
Âíèìàíèå, âîïðîñ - ìîæíî ëè èç ýòîãî ñäåëàòü âûâîä, ÷òî äëÿ âñÿêèõ êîíòåêñòíûõ
ìîäåëåé - â ÷àñíîñòè äëÿ PPM êîíòåêñòû äàëüøå 5 íå íóæíû è òîëêó îò íèõ áóäåò ó
æå âåñüìà ìàëî?
Âîïðîñ âòîðîé - ÷åì áû ïîéìàòü "âçàèìíîå ðàñïîëîæåíèå" ñëîâ - ÿñíî, ÷òî òîò æå
PPM ýòîãî íå âèäèò - ñëèøêîì äàëåêî âñå.
Dima
... I Just want You...
--- Îí, ðîäèìûé ...
* Origin: Óæå â ïÿòü ëåò îí óñòîé÷èâî ëåâèòèðîâàë ... (2:5020/1129.11)