Описание метода Динамического сжатия Маркова.

cinfo, page 86 of 138, hit 000'290

rules=none>

name=L3>

name=L4>

name=L5>

name=L7>

name=L8>

name=L9>

name=L10>

name=L11>

name=L12>

name=L13>

name=L14>

name=L15>

name=L16>

name=L17>

name=L18>

name=L19>

name=L20>

name=L21>

name=L22>

name=L23>

name=L24>

name=L25>

name=L26>

name=L27>

name=L28>

name=L29>

name=L30>

name=L31>

name=L32>

name=L33>

name=L34>

name=L35>

name=L36>

name=L37>

name=L38>

name=L39>

name=L40>

name=L41>

name=L42>

name=L43>

name=L44>

name=L45>

name=L46>

name=L47>

name=L48>

name=L49>

name=L50>

name=L51>

name=L52>

name=L53>

name=L54>

name=L55>

name=L56>

name=L57>

name=L58>

name=L59>

name=L60>

name=L61>

name=L62>

name=L64>

name=L65>

name=L66>

name=L67>

name=L68>

name=L69>

name=L70>

name=L71>

name=L72>

name=L73>

name=L74>

name=L75>

name=L76>

name=L77>

name=L78>

name=L79>

name=L80>

name=L81>

name=L82>

name=L83>

name=L84>

name=L85>

name=L87>

name=L88>

name=L89>

name=L90>

name=L91> name=L92> name=L93> name=L94> name=L95> name=L96> name=L97> name=L98> name=L99>

name=L100>

name=L101>

name=L102>

name=L103>

name=L104>

name=L105>

name=L106>

name=L107>

name=L108>

name=L109>

name=L110>

name=L111>

name=L112>

name=L113>

name=L114>

name=L115>

name=L116>

name=L117>

name=L118>

name=L119>

name=L120>

name=L121>

name=L122>

name=L123>

name=L124>

name=L125>

name=L126>

name=L127>

name=L128>

name=L129>

name=L130>

name=L131>

name=L132>

name=L133>

name=L134>

name=L135>

name=L136>

name=L137>

name=L138>

name=L140>

name=L141>

name=L142>

name=L143>

name=L144>

name=L145>

name=L146>

name=L147>

name=L148>

name=L149>

name=L150>

name=L151>

name=L152>

name=L153>

name=L154>

name=L155>

name=L156>

name=L157>

name=L158>

name=L159>

name=L160>

name=L161>

name=L162>

name=L163>

name=L164>

name=L166>

name=L167>

name=L168>

name=L169>

name=L170>

name=L171>

name=L172>

name=L173>

name=L174>

name=L175>

name=L176>

name=L177>

name=L178>

name=L179>

name=L180>

name=L181>

name=L182>

name=L183>

name=L184>

name=L185>

name=L186>

name=L187>

name=L188>

name=L189>

name=L190>

name=L191>

name=L192>

name=L193>

name=L194>

name=L195>

name=L196>

name=L197>

name=L198>

name=L199>

name=L200>

name=L201>

name=L202>

name=L203>

name=L204>

name=L205>

name=L206>

name=L207>

name=L208>

name=L209>

name=L210>

name=L211>

name=L212>

name=L213>

name=L214>

name=L215>

name=L216>

name=L217>

name=L218>

name=L219>

name=L220>

name=L221>

name=L222>

name=L223>

name=L224>

name=L226>

name=L227>

name=L228>

name=L229>

name=L230>

name=L231>

name=L232>

name=L233>

name=L234>

name=L235>

name=L236>

name=L237>

name=L238>

name=L239>

name=L240>

name=L241>

name=L242>

name=L243>

name=L244>

name=L245>

name=L246>

name=L247>

name=L248>

name=L249>

name=L250>

name=L251>

name=L252>

name=L253>

name=L254>

name=L255>

name=L256>

name=L257>

name=L258>

name=L259>

name=L261>

name=L262>

name=L263>

name=L264>

name=L265>

name=L266>

name=L267>

name=L268>

name=L269>

name=L270>

name=L271>

name=L272>

name=L273>

name=L274>

name=L275>

name=L276>

name=L277>

name=L278>

name=L280>

name=L282>

name=L283>

name=L284>

name=L285>

name=L286>

name=L287>

name=L288>

name=L289>

name=L290>

name=L291>

name=L292>

name=L293>

name=L294>

name=L295>

name=L296>

name=L297>

name=L298>

name=L299>

name=L300>

name=L301>

name=L302>

name=L303>

name=L304>

name=L305>

name=L306>

name=L307>

name=L308>

name=L309>

name=L310>

name=L311>

name=L312>

name=L313>

name=L314>

name=L315>

name=L316>

name=L317>

name=L318>

name=L319>

name=L320>

name=L321>

name=L322>

name=L323>

name=L324>

name=L325>

name=L326>

name=L327>

name=L328>

name=L329>

name=L330>

name=L331>

name=L332>

name=L333>

name=L334>

name=L335>

name=L336>

name=L337>

name=L338>

name=L339>

name=L340>

name=L341>

name=L342>

name=L343>

name=L344>

name=L345>

name=L346>

name=L347>

name=L348>

name=L349>

name=L350>

name=L351>

name=L352>

name=L353>

name=L354>

name=L355>

name=L356>

name=L357>

name=L358>

name=L359>

name=L360>

name=L361>

name=L362>

name=L363>

name=L364>

name=L365>

name=L366>

name=L367>

name=L368>

name=L369>

name=L370>

name=L371>

name=L372>

name=L373>

name=L374>

name=L375>

name=L376>

name=L377>

name=L378>

name=L379>

name=L380>

name=L381>

name=L382>

name=L383>

name=L384>

name=L385>

name=L386>

name=L387>

name=L388>

name=L389>

name=L390>

name=L391>

name=L392>

name=L393>

name=L394>

name=L395>

name=L396>

name=L397>

name=L398>

name=L399>

name=L400>

name=L401>

name=L402>

name=L403>

name=L404>

name=L405>

name=L406>

name=L407>

name=L408>

name=L409>

name=L410>

name=L411>

name=L412>

name=L413>

name=L414>

name=L415>

name=L416>

name=L417>

name=L418>

name=L419>

name=L420>

name=L421>

name=L422>

name=L423>

name=L424>

name=L425>

name=L426>

name=L427>

name=L428>

name=L429>

name=L430>

name=L431>

name=L432>

name=L433>

name=L434>

name=L435>

name=L436>

name=L437>

name=L438>

name=L439>

name=L440>

name=L441>

name=L442>

name=L443>

name=L444>

name=L445>

name=L446>

name=L447>

name=L448>

name=L449>

name=L450>

name=L451>

name=L452>

name=L453>

name=L454>

name=L455>

name=L456>

name=L457>

name=L458>

name=L459>

name=L460>

name=L461>

name=L462>

name=L463>

name=L464>

name=L465>

name=L466>

name=L467>

name=L468>

name=L469>

name=L470>

name=L471>

name=L472>

name=L473>

name=L474>

name=L475>

name=L476>

name=L477>

name=L478>

name=L479>

name=L480>

name=L481>

name=L482>

name=L483>

name=L484>

name=L485>

name=L486>

name=L487>

name=L488>

name=L489>

name=L490>

name=L491>

name=L492>

name=L493>

name=L494>

name=L495>

name=L496>

name=L497>

name=L498>

name=L499>

name=L500>

name=L501>

name=L502>

name=L503>

name=L504>

name=L505>

name=L506>

name=L507>

name=L508>

name=L509>

name=L510>

name=L511>

name=L512>

name=L513>

name=L514>

name=L515>

name=L516>

name=L517>

name=L518>

name=L519>

name=L520>

name=L521>

name=L522>

name=L523>

name=L524>

name=L525>

name=L526>

name=L527>

name=L528>

name=L529>

name=L530>

name=L531>

name=L532>

name=L533>

name=L534>

name=L535>

name=L536>

name=L537>

name=L538>

name=L539>

6.11.97

Захаров Максим

30.03.1993

Данное документ составлен на основе первоначального описания алгоритма,

опубликованного в [1]. Кратко описывается алгоритм и приводятся результаты

сравнения этого алгоритма с другими методами сжатия. Более подробно о работе

алгоритма, в частности, о тонких местах в выборе параметров и совместном

использовании GUAZZO CODING ALGORITHM, можно прочитать в [1]. В работе [2]

показывается, что модель Динамического сжатия Маркова эквивалентна автомату с

конечным контекстом (Finite Context Automata, FCA). Т.к. класс FCA является

подмножеством класса автоматов с конечным числом состояний (Finite State

Automata, FSA), то делается предположение, что т.к. фрагменты текстов на

английском языке могут бытьгуаспознаны FSA, но не могут распознаваться

Марковской моделью переменного порядка (variable-order Markov model), то

использование модели FSA потенциально должно давать лучшие результаты сжатия.

1. G.V. Cormack, R.N. Horspool.

Data Compression Using Dynamic Markov Modelling.

// The Computer Journal, vol.30,No.6,1987, pp.541-550

2. T. Bell, A. Moffat.

A note on the DMC data compression scheme.

// The Computer Journal, vol.32,No.1,1989, pp.16-20

------------------------

На практике, сообщения почти всегда имеют некоторую степень зависимости

между соседними символами, что соответствует источнику сообщений с памятью. В

частности, таким источником может быть Марковская модель (в каждом состоянии

она помнит только об одном предыдущем своем состоянии).

Для примера используем простую Марковскую модель. Будем считать, что

источник порождает строки, состоящие из двоичных цифр такие, что:

за 0 следует 0 с вероятностью 2/3

за 0 следует 1 с вероятностью 1/3

за 1 следует 0 с вероятностью 2/5

за 1 следует 1 с вероятностью 3/5

и первая цифра может быть 0 или 1 равновероятно (1/2).

Сообщения, порождаемые этой моделью имеют общее свойство: за 0 следует чаще

другой 0, чем 1. Аналогично - за 1 чаще следует 1, чем 0. Марковская модель

может быть описана с помощью ориентированного графа, каждой дуге которого

приписываются соответствующие вероятности перехода. Диаграмма состояний для

этой модели выглядит следующим образом:

---

| А |

/ ---

0(50%) / 1(50%)

|/ / 0 (40%) |

--- --------- --- /

--- | B | | C | ----

| --- --------- --- |

0 (67%)| | 1 (33%) / | |1 (60%)

------ --------

При автоматическом создании такой модели возникает две проблемы: проблема

определения вероятностей перехода, приписываемых дугам графа, и проблема в

определении самой структуры графа. Эти проблемы рассматриваются по

отдельности.

Определение вероятностей перехода

Пусть уже известна структура графа. По мере прочитывания двоичных цифр

сообщения Марковская модель будет переходить из одного своего состояния в

другое в соответствии с прочитанными символами. Необходимо подсчитать сколько

раз модель будет переходить по каждой дуге (для каждой дуги заводятся счетчики

переходов по этой дуге). С помощью этих счетчиков можно получить оценки

вероятностей переходов. Если переход из состояния А по дуге для символа 0

проходил N0 раз, а по дуге для 1 - N1, то оценки вероятностей будут выглядеть

следующим образом:

Prob{digit=0 | current state=A} = N0/(N0 + N1)

Prob{digit=1 | current state=A} = N1/(N0 + N1)

Чем чаще мы будем попадать в состояние А, тем точнее будут эти оценки.

При адаптивном кодировании заранее определить значения N0 и N1 невозможно.

В этом случае эти оценки могут выглядеть следующим образом:

Prob{digit=0 | current state=A} = (N0 + c)/(N0 + N1 + 2c)

Prob{digit=1 | current state=A} = (N1 + c)/(N0 + N1 + 2c)

где с - положительная константа. Для файлов большого размера (на много больше

значения c) выбор конкретного значения c существенной роли не играет. Для

файлов малого размера при малом значении c модель быстрее 'выучит'

характеристики источника, однако, при этом увеличивается вероятность

неправильного прогноза. (Т.е. типичная проблема адаптивных алгоритмов).

Построение диаграммы состояний

Алгоритм динамического построения диаграммы состояний поясняется на простом

примере: пусть уже построена модель, содержащая состояния A,B,...,E:

--- 0 --- 0 ---
| A |-------- | C |-------- | D |
--- / --- ---
/|
/
1 / 1
/
/
--- / | ---
| B | /------------------ | E |
--- ---

Из диаграммы видно, что в состояние C ведут две дуги из A и B и выходит две

дуги: в D и E. Всякий раз, когда модель переходит в состояние C, теряется

некоторая информация о контексте, т.е. забывается откуда мы пришли - из A или

B. Однако вполне может быть, что выбор следующего состояния (D или E) зависит

от предыдущего состояния (A или B). Чтобы учесть эту зависимость прибегнем к

следующему приему: разделим состояние C на два состояния. Измененная модель

будет иметь вид:

--- 0 --- 0 ---

| A |-------- | C |-------- | D |

--- --- 1 /| ---

0 /

--- 1 --- / ---

| B |-------- | С'|------- | E |

--- --- 1 / ---

Значения счетчиков переходов из C в D или E делится между счетчиками C и C'

в новой модели пропорционально числу переходов из A в C и из B в C для старой

модели. Теперь модель отражает степень зависимости между состояниями A,B и

D,E. Для этой модели возможно выбор следующего состояния (D или E) не зависит

от предыдущего состояния (A или B), но зависит от непосредственного

предшественника A или B. В этом случае делим состояния A,B,C' и еще раз делим

состояние C. Т.е. модель теперь будет учитывать эти зависимости.

В основном, чем больше мы делим состояний, тем больше увеличивает размах

зависимостей, используемых моделью для прогноза. Само собой процесс деления

необходимо производить только в том случае, когда мы уверены в существовании

соответствующих зависимостей, иначе мы потеряем информацию о контексте.

Отсюда желательно, чтобы деление состояния C проходило тогда, когда оба

счетчика переходов AC и BC достаточно велики. На основе этого можно вывести

критерий деления состояния:

Выбранное состояние делится в том и только в том случае, если число переходов

из текущего состояния в выбранное состояние больше, чем MIN_CNT1, и число

переходов из всех других состояний, кроме текущего, в выбранное состояние

больше, чем MIN_CNT2.

Начальная модель

Для полного определения метода динамического сжатия Маркова осталось

определить стартовую модель. Самая простая модель выглядит следующим образом:

-----------------

|/ |

--- |

----------| |---------------

| ---

| |

-------------

Самая простая модель для байт-ориентированного варианта имеет 255 состояний,

представляется в виде двоичного дерева у которого переход из каждого листа

ведет в корень дерева.

В целом, древовидная начальная модель работает хорошо, но можно построить

модель, которая будет работать немного лучше. В общем случае, состояния на

k-м уровне дерева учитывает зависимость от предыдущих k-1 бит. Размер

контекста, от которого зависит текущее состояние увеличивается от 0 до 7 бит,

затем, при переходе к корню дерева, эта зависимость теряется. Лучшей по

сравнению с этой будет модель, сохраняющая постоянным размер контекста. Т.е.

такая модель должна учитывать зависимость между последними битами предыдущего

байта и первыми битами текущего бита. К сожалению, такую модель трудно

представить в виде диаграммы, но алгоритм построения этой модели приводится в

конце данной статьи.

Последний важный момент

Этим последним моментом является вопрос когда прекращать производить

деление состояния модели. Если этого не производить, то через некоторое время

модель может занять всю имеющуюся память и потребовать еще. Одно из возможных

решений - определить предел числа состояний модели по достижении которого

модель разрушается и начинает создаваться заново из начальной модели.

Последствия такой операции можно облегчить, если запомнить перед разрушением

модели предыдущие n байт текста и затем по этому фрагменту улучшить начальную

модель перед продолжением обработки текста.

Зависимость коэффициента сжатия от параметров деления

(MIN_CNT1, MIN_CNT2)

-----------+---------------------+-----------------------

Значение | Число вершин графа | Коэффициент сжатия

параметров | | (%)

-----------+---------------------+-----------------------

( 1,1 )* | > 194000 | 34.7

( 2,2 ) | 150901 | 33.8

( 4,4 ) | 84090 | 35.8

( 8,8 ) | 44296 | 38.9

(16,16) | 23889 | 42.7

(32,32) | 12089 | 46.5

(64,64) | 6347 | 50.6

(128,128) | 3211 | 54.6

(256,256) | 1711 | 58.6

-----------+---------------------+-----------------------

Файл, на котором проводились исследования, содержал 97393

символов ASCII текста.

* Сжав 90% исходного файла, программа исчерпала ресурс

памяти для узлов графа и была прервана.

Сравнительные результаты работы

------------+-------------------------------------------------+

| Исследуемые файлы |

+--------------+----------------+---------+-------+

------------+--------------+----------------+---------+-------+

Adaptive | 59.7 | 61.6 | 79.6 | 62.9 |

------------+--------------+----------------+---------+-------+

Ziv-Lempel | 38.2 | 42.9 | 98.4 | 40.8 |

(LZW) | | | | |

------------+--------------+----------------+---------+-------+

Bit-oriented| 74.2 | 83.6 | 91.3 | 86.7 |

(LZ-2) | | | | |

------------+--------------+----------------+---------+-------+

Witten | 26.5 | 30.2 | 69.4 | 26.3 |

(CW) | | | | |

------------+--------------+----------------+---------+-------+

Markov | 27.2 | 31.8 | 54.8 | 27.5 |

(DMC) | | | | |

------------+--------------+----------------+---------+-------+

File size | 74510 | 61536 | 68608 | 31479 |

------------+--------------+----------------+---------+-------+

Алгоритм деления состояния модели

{ NEXT_STATE[S,D] = state reached from S after trsnsition on digit D

TRANS_CNT[S,D] = number of observations of input D when in state S

STATE = number of current state

LAST_STATE = largest state number used so far

MIN_CNT1 = minimum number of transitions from the current

state to state S before S is eligible for cloning

MIN_CNT2 = minimum number of visits to a state S from all

predecessors of S other than the current state

before S is eligible for cloning }

while not eof do

begin

resd( B ); { read one input bit }

TRANS_CNT[STATE,B] := TRANS_CNT[STATE,B] + 1;

NXT := NEXT_STATE[STATE,B];

NXT_CNT := TRANS_CNT[NXT,0] + TRANS_CNT[NXT,1];

if (TRANS_CNT[STATE,B] > MIN_CNT1) and

((TRANS_CNT - TRANS_CNT[STATE,B]) > MIN_CNT2) then

begin

LAST_STATE := LAST_STATE + 1;

NEW := LAST_STATE; { Obtain new state number }

NEXT_STATE[STATE,B] := NEW;

RATIO := TRANS_CNT[STATE,B] / NXT_CNT;

for B:=0 to 1 do

begin

NEXT_STATE[NEW,B] := NEXT_STATE[NXT,B];

TRANS_CNT[NEW,B] := RATIO * TRANS_CNT[NXT,B];

TRABS_CNT[NXT,B] := TRANS_CNT[NXT,B] - TRANS_CNT[NEW,B]

end;

NXT := NEW

end;

STATE := NXT

end;

Алгоритм генерации начального состояния

const

NBITS = 8; { Number of bits per byte }

STRANDS = 256; { 2 ** NBITS }

for I := 0 to NBITS-1 do

for J :=0 to STRANDS-1 do

begin

STATE := I + NBITS * J;

K := (I + 1) mod NBITS;

NEXT_STATE[STATE,0] := K + ((2 * j) mod STRANDS) * NBITS;

NEXT_STATE[STATE,1] := K + ((2 * j + 1) mod STRANDS) * NBITS;

TRANS_CNT[STATE,0] := 1;

TRANS_CNT[STATE,0] := 1

end;

LAST_STATE := NBITS * STRANDS -1;

Учебный вариант алгоритма Динамического сжатия Маркова

Ниже приводится реализация алгоритма Динамического сжатия Маркова,

написанный автором алгоритма для учебных целей. Этот алгоритм уже публиковался

в этой конференции и приводится здесь для полноты.

/* Dynamic Markov Compression (DMC) Version 0.0.0

Gordon V. Cormack

University of Waterloo

cormack@uwaterloo.ca

This code and the algorithms herein are the property of Gordon V. Cormack.

Neither the code nor any algorithm herein may be included in any software,

device, or process which is sold, exchanged for profit, or for which a

licence or royalty fee is charged.

Permission is granted to use this code for educational, research, or

commercial purposes, provided this notice is included, and provided this

code is not used as described in the above paragraph.

/* This program implements DMC as described in

"Data Compression using Dynamic Markov Modelling",

by Gordon Cormack and Nigel Horspool

in Computer Journal 30:6 (December 1987)

It uses floating point so it isn't fast. Converting to fixed point

isn't too difficult.

comp() and exp() implement Guazzo's version of arithmetic coding.

pinit(), predict(), and pupdate() are the DMC predictor.

pflush() reinitializes the DMC table and reclaims space

preset() starts the DMC predictor at its start state, but doesn't

reinitialize the tables. This is used for packetized

communications, but not here.

#include <stdio.h>

float predict();

int pinit();

int pupdate();

int memsize = 0x1000000;

main(argc,argv)

int argc;

char *argv[];

{

if (argc == 3 && isdigit(*argv[2])) sscanf(argv[2],"%d",&memsize);

if (argc >= 2 && *argv[1] == 'c') comp();

else if (argc >= 2 && *argv[1] == 'e') exp();

else {

fprintf(stderr,"usage: dmc [ce] memsize <infile >outfilen");

exit(1);

}

return 0;

}

comp(){

int max = 0x1000000,

min = 0,

mid,

c,i,

inbytes = 0,

outbytes =3,

pout = 3,

bit;

pinit(memsize);

for(;;){

c = getchar();

if (c == EOF) {

min = max-1;

fprintf(stderr,"compress done: bytes in %d, bytes out %d, ratio %fn",

inbytes,outbytes,(float)outbytes/inbytes);

break;

}

for (i=0;i<8;i++){

bit = (c << i) & 0x80;

mid = min + (max-min-1) * predict();

pupdate(bit != 0);

if (mid == min) mid++;

if (mid == (max-1)) mid--;

if (bit) {

min = mid;

} else {

max = mid;

}

while ((max-min) < 256) {

if(bit)max--;

putchar(min >> 16);

outbytes++;

min = (min << 8) & 0xffff00;

max = ((max << 8) & 0xffff00 ) ;

if (min >= max) max = 0x1000000;

}

if(!(++inbytes & 0xff)){

if(!(inbytes & 0xffff)){

fprintf(stderr,

"compressing... bytes in %d, bytes out %d, ratio %fr",

inbytes,outbytes,(float)outbytes/inbytes);

}

if (outbytes - pout > 256) { /* compression failing */

pflush();

}

pout = outbytes;

}

putchar(min>>16);

putchar((min>>8) & 0xff);

putchar(min & 0x00ff);

}

exp(){

int max = 0x1000000,

min = 0,

mid,

val,

inbytes=3,

pin=3,

outbytes=0,

bit,

pinit(memsize);

val = getchar()<<16;

val += getchar()<<8;

val += getchar();

while(1) {

c = 0;

if (val == (max-1)) {

fprintf(stderr,"expand: input %d output %dn",inbytes,outbytes);

break;

}

for (i=0;i<8;i++){

mid = min + (max-min-1)*predict();

if (mid == min) mid++;

if (mid == (max-1)) mid--;

if (val >= mid) {

bit = 1;

min = mid;

} else {

bit = 0;

max = mid;

}

pupdate(bit != 0);

c = c + c + bit;

while ((max-min) < 256) {

if(bit)max--;

inbytes++;

val = (val << 8) & 0xffff00 | (getchar()& 0xff);

min = (min << 8) & 0xffff00;

max = ((max << 8) & 0xffff00 ) ;

if (min >= max) max = 0x1000000;

}

putchar(c);

if(!(++outbytes & 0xff)){

if (inbytes - pin > 256) { /* compression was failing */

pflush();

}

pin = inbytes;

}

typedef struct nnn {

float count[2];

struct nnn *next[2];

} node;

static int threshold = 2, bigthresh = 2;

static node *p, *new, nodes[256][256];

static node *nodebuf;

static node *nodemaxp;

static node *nodesptr;

#include <malloc.h>

pinit(memsize)

int memsize;

{

fprintf(stderr,"using %d bytes of predictor memoryn",memsize);

nodebuf = (node *) malloc (memsize);

if (nodebuf == (node *) NULL) {

fprintf(stderr,"memory alloc failed; try smaller predictor memoryn");

exit(1);

}

nodemaxp = nodebuf + (memsize/sizeof(node)) - 20;

pflush();

}

pflush(){

int i,j;

for (j=0;j<256;j++){

for (i=0;i<127;i++) {

nodes[j][i].count[0] = 0.2;

nodes[j][i].count[1] = 0.2;

nodes[j][i].next[0] = &nodes[j][2*i + 1];

nodes[j][i].next[1] = &nodes[j][2*i + 2];

}

for (i=127;i<255;i++) {

nodes[j][i].count[0] = 0.2;

nodes[j][i].count[1] = 0.2;

nodes[j][i].next[0] = &nodes[i+1][0];

nodes[j][i].next[1] = &nodes[i-127][0];

}

nodesptr = nodebuf;

preset();

}

preset(){

p = &nodes[0][0];

}

float predict(){

return p->count[0] / (p->count[0] + p->count[1]);

}

pupdate(b)

int b;

{

float r;

if (p->count[b] >= threshold &&

p->next[b]->count[0]+p->next[b]->count[1]

>= bigthresh + p->count[b]){

new = nodesptr++;

p->next[b]->count[0] -= new->count[0] =

p->next[b]->count[0] *

(r = p->count[b]/(p->next[b]->count[1]+p->next[b]->count[0]));

p->next[b]->count[1] -= new->count[1] =

p->next[b]->count[1] * r;

new->next[0] = p->next[b]->next[0];

new->next[1] = p->next[b]->next[1];

p->next[b] = new;

}

p->count[b]++;

p = p->next[b];

if (nodesptr > nodemaxp){

fprintf(stderr,"flushing ...n");

pflush();

}

Назад в раздел

Emanual.ru – это сайт, посвящённый всем значимым событиям в IT-индустрии: новейшие разработки, уникальные методы и горячие новости! Тонны информации, полезной как для обычных пользователей, так и для самых продвинутых программистов! Интересные обсуждения на актуальные темы и огромная аудитория, которая может быть интересна широкому кругу рекламодателей. У нас вы узнаете всё о компьютерах, базах данных, операционных системах, сетях, инфраструктурах, связях и программированию на популярных языках!