Ñìîòðèòå òàêæå ìàòåðèàëû:
- Ïðåäñêàçàíèå ïî ÷àñòè÷íîìó ñîâïàäåíèþ (PPM)
- Àðèôìåòè÷åñêîå ñæàòèå
- Ñæàòèå ñ ïîìîùüþ ãðàììàòè÷åñêèõ ìîäåëåé
- Îáçîðû óíèâåðñàëüíûõ àëãîðèòìîâ ñæàòèÿ äàííûõ
- Êíèãà "Ìåòîäû ñæàòèÿ äàííûõ". Ðàçäåë 1 "Ìåòîäû ñæàòèÿ áåç ïîòåðü"
Ýêñïåðèìåíòàëüíûé
îäíîôàéëîâûé êîìïðåññîð hipp
v0.5819 (19/08/2005)
Áîãàòîâ Ðîìàí, Îìñêèé ãîñóäàðñòâåííûé òåõíè÷åñêèé óíèâåðñèòåòHipp v0.5819 ñ èñõîäíèêàìè 59 Êá (Visual C++ 7.0)
Îñíîâíûå îñîáåííîñòè (â íàïðàâëåíèè êîòîðûõ è ñòàâèòñÿ ýêñïåðèìåíò):
- äâîéíîå îãðàíè÷åíèå ãëóáèíû ñóôôèêñíîãî äåðåâà ïðè èñïîëüçîâàíèè îáúåäèíåíèÿ öåïî÷åê äåòåðìèíèðîâàííûõ óçëîâ;
- èñïîëüçîâàíèå ôèêñèðîâàíî-óäàë¸ííûõ êîíòåêñòîâ.
Ôèêñèðîâàíî-óäàë¸ííûå êîíòåêñòû (äàëåå – fd-êîíòåêñòû, îò fixed distance contexts) èìåþò âèä x*, x**, xx*, x***, xx**, xxx*, x**** è ò.ä. (ãäå õ – êîíêðåòíûå îïîðíûå ñèìâîëû, * – ïîçèöèè, çàíèìàåìûå ëþáûìè ñèìâîëàìè), ò.å. ÿâëÿþòñÿ ÷àñòíûì ñëó÷àåì ðàçðåæåííûõ êîíòåêñòîâ (sparse contexts), êîãäà âñå îïîðíûå ñèìâîëû ñãðóïïèðîâàíû ñëåâà è îòäåëåíû îò êîäèðóåìîãî ñèìâîëà ñ ïðîïóñêîì íåêîòîðîãî ôèêñèðîâàííîãî ÷èñëà ñèìâîëîâ. Ðàñïðîñòðàí¸ííîé ïðàêòèêîé èñïîëüçîâàíèÿ ðàçðåæåííûõ êîíòåêñòîâ ÿâëÿåòñÿ çàïîìèíàíèå òîëüêî îäíîãî – ïîñëåäíåãî âñòðåòèâøåãîñÿ – ñèìâîëà. Ýêñïåðèìåíò ñ fd-êîíòåêñòàìè çàêëþ÷àåòñÿ â ó÷¸òå ïîëíîé ñòàòèñòèêè ïî âñòðå÷àåìîñòè ñèìâîëîâ â ýòèõ êîíòåêñòàõ è óâåëè÷åíèè ñòåïåíè ñæàòèÿ äàííûõ ñ èñïîëüçîâàíèåì ýòîé ñòàòèñòèêè. (Ñì. ðåçóëüòàòû ýêñïåðèìåíòîâ íèæå.)
Hipp èñïîëüçóåò ïîëíîå ñìåøèâàíèå ïî ñëåäóþùåé ñõåìå. Âåñà ïðîãíîçîâ ïî ñïëîøíûì êîíòåêñòàì (ò.å. "îáû÷íûì", íå ðàçðåæåííûì êîíòåêñòàì) ðàññ÷èòûâàþòñÿ ïî ìåòîäó PPMY Åâãåíèÿ Øåëâèíà ñ èñïîëüçîâàíèåì çàèìñòâîâàííûõ èç PPMY òàáëèö êîýôôèöèåíòîâ; âåñà fd-êîíòåñòîâ – ïî òåì æå ôîðìóëàì, íî ñ ïîñòîÿííûìè êîýôôèöèåíòàìè; äåòåðìèíèðîâàííûå êîíòåêñòû, âûõîäÿùèå çà ïðåäåëû ïåðâîãî îãðàíè÷åíèÿ ãëóáèíû, îáðàáàòûâàþòñÿ îñîáî. Êîäèðîâàíèå ñèìâîëà ïðîèñõîäèò äèõîòîìè÷åñêè (aka "óíàðíî") c ïîýòàïíîé îöåíêîé êàæäîãî âîçìîæíîãî çíà÷åíèÿ ñèìâîëà è êîäèðîâàíèÿ ðåçóëüòàòà. Óíàðíûå âåðîÿòíîñòè ìîäåëåé ñïëîøíûõ è fd-êîíòåêñòîâ ïðîõîäÿò äâóìåðíóþ âòîðè÷íóþ îöåíêó ñ èíòåðïîëÿöèåé (aka SSE2), ðåàëèçîâàííóþ Å. Øåëâèíûì, è ñìåøèâàþòñÿ ñ ïîìîùüþ òàêæå âòîðè÷íî îöåíèâàåìîãî êîýôôèöèåíòà.
Äëÿ âòîðè÷íîãî îöåíèâàíèÿ èñïîëüçóþòñÿ óïðîù¸ííûå SSE-êîíòåêñòû. Äëÿ ñïëîøíûõ êîíòåêñòîâ - íè÷åãî íîâîãî. Äëÿ fd-êîíòåêñòîâ è êîýôôèöèåíòà ñìåøèâàíèÿ ìîäåëåé íàèáîëåå ñóùåñòâåííûì êîìïîíåíòîì ÿâëÿåòñÿ óíèêàëüíûé èíäåêñ øàáëîíà fd-êîíòåêñòà, âí¸ñøåãî íàèáîëüøèé âêëàä â ñîâîêóïíóþ îöåíêó.  êà÷åñòâå äâóõ èíòåðïîëèðóåìûõ àðãóìåíòîâ èñïîëüçóþòñÿ íåñìåøàííûå óíàðíûå âåðîÿòíîñòè ìîäåëåé.
Íàèáîëåå ñóùåñòâåííûå íåäîðàáîòêè:
- îòñóòñòâóåò êàêîå-ëèáî ìàñøòàáèðîâàíèå ñ÷¸ò÷èêîâ ÷àñòîò (recency scaling, rescaling);
- ðåàëèçîâàí ñàìûé ïðîñòåéøèé ìåòîä âûæèâàíèÿ ïðè äîñòèæåíèè îãðàíè÷åíèÿ ïî ïàìÿòè, ñâîäÿùèé íà íåò âåñü äîñòèãíóòûé ê òîìó ìîìåíòó âûèãðûø â ñæàòèè;
- ïðèìèòèâíàÿ ñõåìà ñìåøèâàíèÿ ïðîãíîçîâ ìîäåëåé ñïëîøíûõ è fd-êîíòåêñòîâ è íåïðîðàáîòàííûå SSE-êîíòåêñòû;
- ïðè èñïîëüçîâàíèè fd-êîíòåêñòîâ íå ìîæåò áûòü èñïîëüçîâàíî ÎÄÓ (ïîäðóæèòü èõ ìîæíî, íî íå òàê áûñòðî, êàê ïðåäïîëàãàëîñü);
- â ñëó÷àå fd-êîíòåêñòîâ òðåáóåòñÿ äèôôåðåíöèàöèÿ ñ÷¸ò÷èêîâ "îïòèìàëüíîñòè" (èñïîëüçóåìûõ Å. Øåëâèíûì äëÿ ðàñ÷¸òà âåñîâ ïîëíîãî ñìåøèâàíèÿ) â çàâèñèìîñòè îò ãëóáèíû è øàáëîíà fd-êîíòåêñòà;
- ïðèëàãàåìûé èñõîäíûé êîä âîîáùå-òî íå ïëàíèðîâàëñÿ ê îïóáëèêîâàíèþ è ñîâåðøåííî íå ïðè÷¸ñàí :î)
(Èçîáðàæåíû ðåçóëüòàòû ïðîãîíà 18 ôàéëîâ òåñòîâîãî íàáîðà Calgary Corpus ïðè îãðàíè÷åíèè ãëóáèíû MaxOrder=1706.  Calgary Corpus åñòü òîëüêî îäèí ôàéë, ñîäåðæàùèé ïîâòîðÿþùèéñÿ áëîê äëèíû áîëüøå 1706, pic, êîòîðîìó ñîîòâåòñòâóåò ïèê íà ãðàôèêå â 300 Ìá. Äëÿ pic ïîëíîå ñóôôèêñíîå äåðåâî (MaxOrder=36313) ñ ÎÄÓ çàíèìàåò âñåãî 15,4 Ìá; áåç ÎÄÓ óæå ïðè MaxOrder=8000 çàíèìàåò 926 Ìá. Òîò ôàêò, ÷òî â hipp èñïîëüçîâàíû 32-áèòíûå ñ÷¸ò÷èêè ÷àñòîò (~1/6 îáú¸ìà äåðåâà áåç ÎÄÓ) è 18-áàéòîâàÿ ñòðóêòóðà óçëà (ñîäåðæàùàÿ äîïîëíèòåëüíûå ïàðàìåòðû, âìåñòî ìèíèìàëüíîé 5-áàéòîâîé; ~1/3 îáú¸ìà äåðåâà), íå èñêàæàåò êà÷åñòâà ãðàôèêà. Çäåñü æå ñëåäóåò îòìåòèòü, ÷òî äëÿ ïîñòðîåíèÿ äåðåâà ñ ÎÄÓ òðåáóåòñÿ ìåíüøå âðåìåíè (ãëàâíûì îáðàçîì, èç-çà ýêîíîìèè ïàìÿòè), à â öåëîì ñæàòèå ñ ÎÄÓ çàíèìàåò ïðèáëèçèòåëüíî ñòîëüêî æå âðåìåíè, êàê áåç ÎÄÓ.)
Ïðè ðåàëèçàöèè ÎÄÓ èñïîëüçîâàëñÿ áîëåå ñëîæíûé ïîäõîä, ÷åì çàìåíà symbol-transition íà string-transition (ñì., íàïðèìåð, äèññåðòàöèþ S. Bunton), íà îñíîâå ñîáñòâåííûõ ñòðóêòóð (ñì. ôàéë NodeStruct.inl). Ñàìàÿ áîëüøàÿ ïðîáëåìà, ñ êîòîðîé ïðèøëîñü ñòîëêíóòüñÿ, – ýòî ýìóëÿöèÿ äîëæíûõ çíà÷åíèé ñ÷¸ò÷èêîâ "îïòèìàëüíîñòè" îáúåäèí¸ííûõ óçëîâ (÷òîáû íå õðàíèòü èõ ÿâíî; èíà÷å áû âñÿ êðàñîòà ÎÄÓ ñîøëà íà íåò). Ðåàëèçîâàííûé ìåòîä òðåáóåò äâà äîïîëíèòåëüíûõ ñòàòè÷åñêèõ ìàññèâà – äëÿ ñ÷¸ò÷èêîâ âñòðå÷àåìîñòè óçëîâ è ñ÷¸ò÷èêîâ îïòèìàëüíîñòè – ïî (MaxOrder+1) ýëåìåíòîâ êàæäûé.
Èñïîëüçîâàíèå âòîðîãî îãðàíè÷åíèÿ ãëóáèíû ñóôôèêñíîãî äåðåâà (MaxOrder2, MaxOrder1<=MaxOrder2) ïîçâîëÿåò êà÷åñòâåííî îáðàáàòûâàòü ôàéëû, ñîäåðæàùèå áîëüøèå ïîâòîðÿþùèåñÿ áëîêè, ïðè òåõ æå ðàñõîäàõ ïàìÿòè è íåáîëüøèõ äîïîëíèòåëüíûõ çàòðàòàõ âðåìåíè. Ïðèìåð:
Èñõîäíûå ôàéëû:
book1 768771
book1_x10 7687710 (10 ñêëååííûõ book1)
Îáîðóäîâàíèå: Pentium 4 2400MHz, 1Gb DDR400, Seagate 60Gb, Windows XP Pro + SP2.
Ïàðàìåòðû Ïàìÿòü, Âðåìÿ, Àðõèâ,
çàïóñêà Hipp 0.5819 Ìá ñ Êá
book1_x10/o4/do4 32,8 50 1758
book1_x10/o4/do256 32,8 53 314
book1_x10/o4/do1024 32,8 62 212
Äëÿ ñðàâíåíèÿ – ñæàòèå îäíîãî book1:
book1/o4/do4 25,6 5 209
(ò.å. ïî÷òè äîñòèãíóò ðàçìåð îäíîêðàòíîãî book1)
Ïðî÷èå àðõèâàòîðû
(ñæàòèå book1_x10: ïàìÿòü, âðåìÿ, ðàçìåð):
PAsQDa v3.9 -8 930Mb 6344 176
PAsQDa v3.9 -2 32Mb 1324 1741
Durilca v.0.4b –o64 -t1 940Mb 22 179
Durilca v.0.4b –o64 940Mb 22 199
PAQAR v4.0 -7 ~900Mb 1891 192
PAQAR v4.0 -3 ~55Mb 2054 1752
WinRK 2.0 PWCM 900Mb 870 200
PPMonstr var.I –o32 225Mb 12 201
PPMonstr var.I –o16 32Mb 23 991
PPMonstr var.I –o32 32Mb 26 1295
ash /o33 /s255 480Mb 85 203
ash /o17 /s255 186Mb 66 222
ash /o65 /s255 >1Gb 94 364
PPMd var I. –o16 89Mb 2 224
PPMd var I. –o9 26Mb 2 569
RAR 3.40 -m5 3 212
RAR 3.40 -m5 –mc63:128t+ 4 212
RAR 3.40 -m5 –mc16:32t+ 4 534
Slim! v0.016 –w22 18 216
Slim! v0.23d –o32 240Mb 52 218
Slim! v0.23d –o16 140Mb 51 230
Slim! v0.23d –o16 70Mb 81 915
EPM r9 –c128 71 1960
EPM r9 –c064 70 1963
EPM r9 -c999 101 1963
Êàê âèäíî èç ïåðâîé òàáëèöû, áëàãîäàðÿ ÎÄÓ hipp èñïîëüçîâàë âñåãî 32,8 Ìá ïàìÿòè äëÿ êîíòåêñòíîãî ìîäåëèðîâàíèÿ 4-ãî ïîðÿäêà (èç êîòîðûõ ñóôôèêñíîå äåðåâî çàíèìàåò òîëüêî 2,7 Ìá; îñòàëüíîå – íåâîñòðåáîâàííûå SSE-ìàññèâû, êýøèðîâàíèå âñåãî ôàéëà öåëèêîì è ïð.) è áëàãîäàðÿ óâåëè÷åíèþ MaxOrder2 äî 1024 "ó÷¸ë" äåñÿòèêðàòíîñòü âõîäíûõ äàííûõ, çàòðàòèâ íà 25% áîëüøå âðåìåíè (õîòÿ ïîðÿäîê ìîäåëè óâåëè÷èëñÿ â 256 ðàç).
Íà îáû÷íûõ ôàéëàõ (íå ÿâëÿþùèõñÿ ñêëåéêîé îäèíàêîâûõ áëîêîâ :î) ñèòóàöèÿ äâîÿêàÿ. Òèïè÷íûå áëàãîïðèÿòíûé è íåáëàãîïðèÿòíûé ñëó÷àè íà ïðèìåðå ôàéëîâ news èç Calgary Corpus è fp.log ñ www.maximumcompression.com:
Ôèêñèðîâàíî-óäàë¸ííûå êîíòåêñòû îáåñïå÷èâàþò ñóùåñòâåííîå óâåëè÷åíèå ñòåïåíè ñæàòèÿ íà ôàéëàõ ñ òàáëè÷íîé ñòðóêòóðîé (xls, dbf è ò.ï.), à òàêæå èñïîëíÿåìûõ ôàéëàõ, è â òî æå âðåìÿ íåçíà÷èòåëüíî óõóäøàþò ñòåïåíü ñæàòèÿ ïðè ïðèìåíåíèè ê "íåáëàãîïðèÿòíûì" äàííûì (íàïðèìåð, òåêñòàì). Çàâèñèìîñòü ðàñõîäîâ âðåìåíè è ïàìÿòè îò îáú¸ìà âõîäíûõ äàííûõ ïðè ýòîì îñòà¸òñÿ ëèíåéíîé (õîòÿ ýòî íè î ÷¸ì íå ãîâîðèò – çàâèñèìîñòü îñòà¸òñÿ ëèíåéíîé äàæå ïðè ïðèâëå÷åíèè âñåõ âîçìîæíûõ ðàçðåæåííûõ êîíòåêñòîâ îãðàíè÷åííîé ãëóáèíû :î). Ñìîòðèì çàâèñèìîñòè ñòåïåíè ñæàòèÿ (ratio), âðåìåíè (time) è èñïîëüçîâàííîé ïàìÿòè (used memory) îò ãëóáèíû ñïëîøíûõ êîíòåêñòîâ (MaxOrder) è ãëóáèíû fd-êîíòåêñòîâ (fd-MaxOrder) ïðè ñæàòèè ôàéëîâ kennedy.xls èç Canterbury Corpus, obj2 è pic èç Calgary Corpus:
Ðåçóëüòàòû áîëüøîãî òåñòà. Èñõîäíûå äàííûå: ãîäîâàÿ 1Ñ-áàçà îäíîãî èç ïðåäïðèÿòèé (207 Ìá) + íåñêîëüêî ãîäîâûõ xls-îò÷¸òîâ (17 Ìá), âñåãî 730 ôàéëîâ 21 òèïà. Ò.ê. hipp íå èñïîëüçóåò íèêàêèõ ôèëüòðîâ, íå ðàçáèâàåò âõîäíûå äàííûå íà îáëàñòè, íå ìàñøòàáèðóåò ñòàòèñòèêó, íåâàæíî ñåáÿ âåä¸ò ïðè äåôèöèòå ïàìÿòè, íå ñîõðàíÿåò íè èìåíè ôàéëà, íè ïóòè... :î), ïðèõîäèòñÿ äåëàòü ñëåäóþùèé ìàí¸âð. Èñõîäíûå äàííûå êîíñîëèäèðóþòñÿ â rar-àðõèâû áåç ñæàòèÿ, ðàçäåëüíî ïî ðàñøèðåíèÿì, ñ ìàêñèìàëüíûì ðàçìåðîì òîìà 1 Ìá (íàïðèìåð, rar a -ds -m0 -r -v1m -vn _dbf *.dbf); ìåëêèå è îäèíî÷íûå ôàéëû (ñ ðàñøèðåíèÿìè txt, rtf, xml, als, tls, cfg, st, tip, spl, log, efd, lst, id; ñóììàðíûé ðàçìåð 700 Êá) – â îäèí àðõèâ.  ðåçóëüòàòå èñõîäíûå äàííûå ïðåäñòàâëÿþò ñîáîé 230 ôàéëîâ (225 Ìá), ðàçìåðîì íå áîëåå 1 Ìá êàæäûé, óäîáíûõ ê îáðàáîòêå îäíîôàéëîâûì êîìïðåññîðîì. Îáðàòíîå ïðåîáðàçîâàíèå îñóùåñòâëÿåòñÿ êîìàíäîé rar x *.rar.
Ñîâîêóïíàÿ ñòåïåíü ñæàòèÿ ïîëó÷åííûõ òîìîâ ïî îòäåëüíîñòè ïðåäñòàâëåíà â òàáëèöàõ:
(Ëó÷øåå çíà÷åíèå ñòåïåíè ñæàòèÿ â ïåðâûõ äâóõ ñòîëáöàõ âûäåëåíî ïîëóæèðíûì; ëó÷øåå ïî ñòðîêå - êðàñíûì. Çäåñü, âî-ïåðâûõ, âèäíî, ÷òî èñïîëüçîâàíèå äâîéíîãî îãðàíè÷åíèÿ ãëóáèíû ñóôôèêñíîãî äåðåâà â ñðåäíåì ñïîñîáñòâóåò óâåëè÷åíèþ ñòåïåíè ñæàòèÿ (âòîðîé ñòîëáåö). Çíà÷åíèÿ ãëóáèíû fd-êîíòåêñòîâ ñî øòðèõîì – ýêñïåðèìåíò ïî èñêëþ÷åíèþ fd-êîíòåêñòîâ ñ îäíèì îïîðíûì ñèìâîëîì, ò.å. âèäà x*, x**, x***, x**** è ò.ä., ÿâëÿþùèõñÿ ñàìûìè ðåñóðñî¸ìêèìè è, êàê ìîæåò ïîêàçàòüñÿ, íàèìåíåå âàæíûìè. Íî íåáîëüøîé âûèãðûø â ðåñóðñàõ ïðè ýòîì îêàçàëñÿ íåñîîòâåòñòâåííûì ïîòåðå â ñòåïåíè ñæàòèÿ: ñîâîêóïíûå ðåçóëüòàòû çàïóñêà ñ ïàðàìåòðîì /so16' , íàïðèìåð, ïî âñåì ïîêàçàòåëÿì ïðîèãðûâàþò áîëåå ñèëüíîìó è ýêîíîìè÷íîìó ñæàòèþ ñ ïàðàìåòðîì /so10.)
Äâà ñòîëáöà ñ ëó÷øèìè ïîêàçàòåëÿìè hipp (áåç è ñ èñïîëüçîâàíèåì fd-êîíòåêñòîâ) ïðåäñòàâëåíû â ñðàâíåíèè ñ äðóãèìè èçâåñòíûìè àðõèâàòîðàìè:
(Òÿæåëîâåñû òèïà PAQAR, PAsQDa è WinRK íå òåñòèðîâàëèñü :î( Ëó÷øåå çíà÷åíèå ñòåïåíè ñæàòèÿ ïî ñòðîêå âûäåëåíî ïîëóæèðíûì. Èòîãîâûå ñòåïåíè ñæàòèÿ òàêæå îòîáðàæåíû íà äèàãðàììå íèæå. Êàê âèäíî, ðåéòèíã hipp ñ fd-êîíòåêñòàìè â òàáëèöå îáóñëîâëåí õîðîøèì ñæàòèåì cdx è xls-ôàéëîâ, ñîñòàâëÿþùèõ ïî÷òè ÷åòâåðòü âõîäíûõ äàííûõ. Î êà÷åñòâå ýòîãî ðåçóëüòàòà ãîâîðèò òàêæå òîò ôàêò, ÷òî ïî ñæàòèþ dbf-ôàéëîâ, ñîñòàâëÿþùèõ 46,6%, hipp çàíèìàåò àæ ïÿòîå ìåñòî, ÷òî íå ìåøàåò åìó îñòàâàòüñÿ íà òðåòüåì ìåñòå ïî ñîâîêóïíîé ñòåïåíè ñæàòèÿ.)
Îñíîâíûå âûâîäû. Åù¸ ðàç ïîâòîðþñü, ÷òî ýêñïåðèìåíò ñòàâèëñÿ â äâóõ íàïðàâëåíèÿõ: ïîâûøåíèå ñòåïåíè ñæàòèÿ ïðè èñïîëüçîâàíèè ÎÄÓ + äâîéíîãî îãðàíè÷åíèÿ ãëóáèíû äåðåâà è fd-êîíòåêñòîâ.
ÎÄÓ, ñàìî ïî ñåáå, ñóùåñòâåííî ýêîíîìèò ïàìÿòü, íî ïðèìåíèìî òîëüêî äëÿ "ïðîñòûõ" ñóôôèêñíûõ äåðåâüåâ, óçëû êîòîðûõ íå ñîäåðæàò ñïåöèôè÷åñêèõ ïàðàìåòðîâ. ÎÄÓ ðåàëèçóåìî, íàïðèìåð, äëÿ óçëîâ ñ îáû÷íûìè ñ÷¸ò÷èêàìè âñòðå÷àåìîñòè è îïòèìàëüíîñòè óçëà, à òàêæå ïðè èñïîëüçîâàíèè ïðîñòîãî áåçóñëîâíîãî ìàñøòàáèðîâàíèÿ ýòèõ ñ÷¸ò÷èêîâ.
Åñëè ÎÄÓ ðåàëèçîâàíî, òî äâîéíîå îãðàíè÷åíèå ãëóáèíû ñóôôèêñíîãî äåðåâà ÿâëÿåòñÿ ãîòîâîé è óäîáíîé àëüòåðíàòèâîé LZ-ñóáìîäåëÿì, ïðåäíàçíà÷åííûì äëÿ îáðàáîòêè áîëüøèõ ïîâòîðÿþùèõñÿ áëîêîâ äàííûõ. Äàæå òàêîå ãðóáîå èñïîëüçîâàíèå äâîéíîãî îãðàíè÷åíèÿ, êàê â íàñòîÿùåé âåðñèè hipp, ÿâëÿåòñÿ ñåðü¸çíûì ïîäñïîðüåì, îñîáåííî ïðè ìàëûõ çíà÷åíèÿõ MaxOrder1.
Ó÷¸ò ïîëíîé ñòàòèñòèêè ïî âñòðå÷àåìîñòè ñèìâîëîâ â fd-êîíòåêñòàõ íà îïðåäåë¸ííûõ òèïàõ äàííûõ ïîçâîëÿåò hipp ïðè âñåé åãî íåäîðàáîòàííîñòè äîñòèãàòü óðîâíÿ ñæàòèÿ õîðîøî ïðîðàáîòàííûõ ëèäèðóþùèõ àðõèâàòîðîâ. Âñêîëüçü óïîìÿíóòûé ýêñïåðèìåíò ñ çàïðåùåíèåì fd-êîíòåêñòîâ ñ îäíèì îïîðíûì ñèìâîëîì ãîâîðèò î öåííîñòè èìåííî ïîëíîé ñòàòèñòèêè ïî âñåì âñòðå÷àþùèìñÿ ñèìâîëàì â fd-êîíòåêñòàõ êîíòåêñòàõ. Õîòåëîñü áû îáðàòèòü îáùåñòâåííîå âíèìàíèå íà òî, ÷òî òåìà èñïîëüçîâàíèÿ ðàçðåæåííûõ êîíòåêñòîâ äëÿ óíèâåðñàëüíîãî ñæàòèÿ ìàëî èññëåäîâàíà è åù¸ ìåíüøå îñâåùåíà â êàêèõ-ëèáî ïóáëèêàöèÿõ.
Áëàãîäàðþ Áîãà (òàêîãî çàáîòëèâîãî Îòöà), êàôåäðó ÀÑÎÈÓ ÎìÃÒÓ (ñòàâøóþ ìîåé ðîäèíîé) è Åâãåíèÿ Øåëâèíà (çà ùåäðîå êîíñóëüòèðîâàíèå è äðóæáó)!
Èìýéë àâòîðà äëÿ îòçûâîâ: fwd2bogatov íà ßíäåêñ.ðó.
íàâåðõ
Ñìîòðèòå òàêæå ìàòåðèàëû:
- Ïðåäñêàçàíèå ïî ÷àñòè÷íîìó ñîâïàäåíèþ (PPM)
- Àðèôìåòè÷åñêîå ñæàòèå
- Ñæàòèå ñ ïîìîùüþ ãðàììàòè÷åñêèõ ìîäåëåé
- Îáçîðû óíèâåðñàëüíûõ àëãîðèòìîâ ñæàòèÿ äàííûõ
- Êíèãà "Ìåòîäû ñæàòèÿ äàííûõ". Ðàçäåë 1 "Ìåòîäû ñæàòèÿ áåç ïîòåðü"