Деревья хаффмана - как с ними работать

[alone]

alone, а как это делается в виде программы для Z80 есть?

Нет. Да и зачем оно отдельно? Потом всё равно урезать дерево до 15 ярусов, сортировать символы в ярусах, кодировать длины ярусов. Да и без LZ это не нужно. Проще переделать ZXRar под нужный формат, как сделано в mRIP.

[jerri]

alone, у меня уже есть данные которые надо както оптимизированно утоптать
есть данные 16 бит +16 бит которые желательно упихать в 2-16 бит

---------- Post added at 15:33 ---------- Previous post was at 15:09 ----------

есть 6 байт

1 2 3 4 5 5

и есть вот такой генератор таблиц

.MakeHuff:
	ld	a,5
	call	.GetBits

	ld	a,(rncdat)
	or	a
	ret	z

	ld	(temp1),a
	ld	b,a

	ld	hl,tmptab
.MakeHuff2:
	push	bc
	push	hl
	ld	a,4
	call	.GetBits
	pop	hl
	ld	a,(rncdat)
	ld	(hl),a
	inc	hl
	pop	bc
	djnz	.MakeHuff2

	xor	a
	ld	(regy),a
	inc	a
	ld	(bitlen),a
	ld	hl,0
	ld	(hufcde),hl
	ld	hl,#8000
	ld	(hufbse),hl
.MakeHuff3:
	ld	a,(temp1)
	ld	(temp2),a

	xor	a
	ld	(temp3),a

.MakeHuff4:
	ld	a,(temp3)
	ld	(regx),a

	ld	hl,tmptab
	call	hla
	
	ld	a,(bitlen)
	cp	(hl)
	jp	nz,.MakeHuff8

	ld	(regx),a
	add	a,a
	ld	hl,.msktab
	call	hla

	ld	a,(regy)
	ld	c,a
	add	a,2
	ld	(regy),a

	ld	de,(hufftab)
	ld	a,c
	call	dea

	ldi
	ldi

	ld	bc,(rncdat)
	ld	de,(hufcde)

	ld	a,(regx)

.MakeHuff5:
	sla	e
	rl	d
	rr	b
	rr	c

	dec	a
	jr	nz,.MakeHuff5

	ld	hl,rncdat+3
	ld	(hl),d
	dec	hl
	ld	(hl),e
	dec	hl

	ld	a,(bitlen)
	ld	e,a

	ld	a,16
	sub	e
	jr	z,.MakeHuff7

.MakeHuff6:
	srl	b
	rr	c

	dec	a
	jr	nz,.MakeHuff6

.MakeHuff7:
	ld	(hl),b
	dec	hl
	ld	(hl),c

	ld	a,(regy)
	ld	b,a
	add	2
	ld	(regy),a

	ld	hl,(hufftab)
	ld	a,b
	call	hla

	ld	de,(rncdat)
	ld	(hl),e
	inc	hl
	ld	(hl),d
	inc	hl

	ld	de,15*4
	add	hl,de

	ld	a,(temp3)
	ld	(hl),a

	inc	hl

	ld	a,(bitlen)
	ld	(hl),a

	ld	bc,(hufbse)

	ld	hl,(hufcde)
	add	hl,bc
	ld	(hufcde),hl

.MakeHuff8:
	ld	hl,temp3
	inc	(hl)

	ld	hl,temp2
	dec	(hl)
	jp	nz,.MakeHuff4

	ld	hl,hufbse+1
	srl	(hl)
	dec	hl
	rr	(hl)

	ld	a,(bitlen)
	inc	a
	ld	(bitlen),a

	cp	17
	jp	nz,.MakeHuff3

	ret
hla
	add	a,l
	ld	l,a
	ret	nc
	inc	h
	ret
dea
	add	a,e
	ld	e,a
	ret	nc
	inc	d
	ret

и потом оно
вот этой подпрограммой хрен пойми как что то там выколупывает

;**********************************

.GetVal:
	ld	hl,(hufftab)
	dec	hl
.GetVal2:

	inc	hl
.GetVal3:
	ld	bc,(bitbufl)
	ld	a,c
	and	(hl)
	ld	c,a
	inc	hl
	ld	a,b
	and	(hl)
	ld	b,a
	inc	hl
	ld	(rncdat),bc

	ld	a,c
	cp	(hl)
	inc	hl
	jr	nz,.GetVal2

	ld	a,b
	cp	(hl)
	inc	hl
	jr	nz,.GetVal3

	ld	de,15*4
	add	hl,de

	ld	a,(hl)
	inc	hl
	push	af
	ld	a,(hl)
	call	.GetBits
	pop	af
	cp	2
	jr	nc,.GetVal4

	ld	hl,rncdat
	ld	(hl),a
	inc	hl
	xor	a
	ld	(hl),a
	ret
.GetVal4:
	dec	a
	push	af
	call	.GetBits
	pop	af
	ld	b,a
	inc	b
	ld	hl,1
	jr	.GetVal5a
.GetVal5:
	add	hl,hl
.GetVal5a:
	djnz	.GetVal5

	ld	de,(rncdat)	
	ld	a,e
	or	l
	ld	e,a
	inc	hl
	ld	a,d
	or	h
	ld	d,a
	ld	(rncdat),de
	ret

[alone]

есть 6 байт

1 2 3 4 5 5

Это частоты? Нужны частоты для всех литералов.

[jerri]

alone, я не знаю что это
я надеялся ты расскажешь

[GriV]

Юра, ты в получаешь те же самые вопросы, что я тебе задавал.

Для каждого случая ты будешь получать свое дерево, если ты хочешь наиболее оптимальный хаффман.

Хранить деревья просто, достаточно указать группы бит, по которым группируются значения, по хаффману.

Я не знаю, есть ли пакеры, которые строят каждый раз своё дерево, лучше спроси АлКо.

[psb]

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

[Advertiser]

[jerri]

GriV, а я кого спрашиваю?

я разобрался как оно работает

[jerri]

вобщем так

есть набор чисел

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
есть повторяемость каждого числа

как мне из этих данных сделать дерево?
желательно в виде примера кодирования и использования

при этом может оказаться что каких то из чисел вообще нет

[jerri]

распаковщик для спектрума RNC_propack

переписан под спек

[jerri]

1 2 3 4 5 5

Это частоты? Нужны частоты для всех литералов.

нет это не частоты
это длина этой позиции в битах в дереве хаффмана

позиция же указывает сколько бит нужно взять из потока для получения ссылки
исключением являются позиции 0 и 1 - они считаются безусловными цифрами

т.е если меньше 2х то возвращаем число

если n больше или равно 2 то берем n-1 бит из потока и устанавливаем бит n-1