Overleg:Huffmancodering

Bij het onderdeel "Een voorbeeld" op deze pagina is volgens mij een fout gebeurd. Volgens wat er staat zou de kortste code, die voor E, 11 zijn. Nochtans zou Huffman codering normaal gezien een codewoord van 1 bit, dus lengte 1 in plaats van 2, moeten toekennen aan het meest voorkomende symbool. Over het algemeen zijn er in de opgestelde lijst te weinig korte codewoorden aanwezig naar mijn gevoel. Op zijn minst zou elke lengte van codewoord 1 keer moeten voorkomen, als ik het algoritme goed begrepen heb. Sbleuz (overleg) 31 mei 2019 11:42 (CEST)

Het Engelstalige artikel biedt uitkomst. Hier is te vinden dat Huffman codes voldoen aan de eigenschap "the bit string representing some particular symbol is never a prefix of the bit string representing any other symbol". Bob.v.R (overleg) 31 mei 2019 17:24 (CEST)

Na het handmatig narekenen van de boom zie ik in dat mijn originele veronderstelling dat de kortste code lengte 1 zou moeten hebben inderdaad incorrect is. De lengtes van de codes kunnen inderdaad verschillen en niet alle lengtes komen per se voor. Ondanks dit alles denk ik toch nog steeds dat de boom die hier weergegeven is fout is, of toch de codes die eruit geproduceerd worden, want aan de boom zelf valt geen touw vast te knopen zoals hieronder al opgemerkt is. Ik ga de boom nog een tweede keer narekenen voor de zekerheid en dan een manier zoeken om deze op een deftige manier hier weer te geven. Sbleuz (overleg) 2 jun 2019 11:59 (CEST)

Narekenen met computer (Python scriptje: https://gist.github.com/sibebleuze/0345c47555eaeb248c22370783feb8a4) toont dat de codes, en dus ook de boom, dezelfde zijn als degene die in het voorbeeld staan. Het voorbeeld is dus wel juist, maar de grafische weergave is nog steeds niet optimaal. Sbleuz (overleg) 2 jun 2019 17:15 (CEST)

Boom

De boom in het voorbeeld is wel erg lastig te lezen. Madyno (overleg) 31 mei 2019 23:01 (CEST)

Inderdaad! Bob.v.R (overleg) 1 jun 2019 07:53 (CEST)

Ik zou de binaire boom zo weergeven

										code	letter	freq. (%)	lengte
0 58,92	0 32,73	0 18,10	0 10,03							0000	N	10,03	4
			1 8,07	0 4,34	0 2,21					000100	M	2,21	7
					1 2,13	0 1,24				0001010	C	1,24	8
						1 0,89	0 0,81			00010110	F	0,81	8
							1 0,08	0 0,04	0 0,03	0001011100	Y	0,03	10
									1 0,01	0001011101	Q	0,01	10
								1 0,04		000101111	X	0,04	9
				1 3,73						00011	S	3,73	5
		1 14,63	0 7,49							0010	A	7,49	4
			1 7,14	0 3,57	0 1,99					001100	U	1,99	6
					1 1,58					001101	B	1,58	6
				1 3,57						00111	L	3,57	5
	1 26,19	0 13,29	0 6,79							0100	T	6,79	4
			1 6,50							0101	I	6,50	4
		1 12,90	0 6,49	0 3,40						01100	G	3,40	5
				1 3,09	0 1,57					011010	P	1,57	6
					1 1,52					011011	W	1,52	6
			1 6,41							0111	R	6,41	4
1	0	0 11,99	0 6,06							1000	O	6,06	4
			1 5,93							1001	D	5,93	4
		1	0 5,70	0 2,85						10100	V	2,85	5
				1 2,85	0 1,46					101010	J	1,46	6
					1 1,39					101011	Z	1,39	6
			1	0						10110	H	2,38	5
				1						10111	K	2,25	5
	1 18,91									11	E	18,91	2

Zinnig? Madyno (overleg) 3 jun 2019 23:00 (CEST)

In de huidige tabel (in het artikel) wordt ook een poging gedaan om het construeerproces te illustreren, dat ontbreekt helaas in bovenstaande tabel, die er overigens wel netjes uitziet. Bob.v.R (overleg) 4 jun 2019 03:47 (CEST)

Dat kan eraan toegevoegd worden, maar daar begin ik pas aan, als men het over deze, of een soortgelijke vorm eens is.
Bovenstaande opmerking werd geplaatst door Madyno op 4 jun 2019 om 06:46 uur.

Dat weet ik ook wel, maar deze tabel is een directe weergave van de boom. Ik heb nog een beginnetje gemaakt met een meer op een boom lijkende weergave. Madyno (overleg) 5 jun 2019 19:23 (CEST)

Nu begint het al meer een boom te worden. De vraag is nu of we in de vakjes links ook percentages willen vermelden (zie pagina-geschiedenis). Bob.v.R (overleg) 6 jun 2019 07:42 (CEST)

Dat is ook mijn idee, en dan bevat deze boom dezelfde info als de huidige. Je had al een beginnetje gemaakt, ik heb er nog twee toegevoegd en in small gezet. Lijkt dat wat?Madyno (overleg) 6 jun 2019 22:15 (CEST)

Jawel, maar een volledig weergegeven boom wordt dan vermoedelijk te breed, lastig dus. Bob.v.R (overleg) 6 jun 2019 23:36 (CEST)

We kunnen nog op de haakjes sparen en de kolom met frequenties kan dan ook weg. Madyno (overleg) 7 jun 2019 00:02 (CEST)

Werk in uitvoering: de boom is nu 7 niveaus diep, maar zal tot 10 niveaus moeten gaan, de lengte van de twee langste codewoorden. Bob.v.R (overleg) 10 jun 2019 02:44 (CEST)

Ik vind de boom als tabel niet erg fraai. Ik heb een echte boom gemaakt. Wat vinden jullie hiervan? Ik kan no gemakkelijk veranderingen aanbrengen. Madyno (overleg) 11 jun 2019 11:27 (CEST)

(zie artikel)Madyno (overleg) 16 jun 2019 20:53 (CEST)

Hierbij wat overwegingen. In het ideale geval zou je een animatie hebben, waarin de boom stapje voor stapje wordt opgebouwd. In het geval zonder animatie zou het mooi zijn als duidelijker wordt dat de codewoorden de conclusie zijn van het proces dat wordt doorlopen. Een manier om dit te doen kan zijn om eerst een boom te laten zien zonder de codewoorden en vervolgens (na wat toelichtende tekst) een boom met de codewoorden. Daarnaast nog een praktische opmerking: het lijkt me netjes om niet overdreven veel witruimte boven en onder te hebben. Bob.v.R (overleg) 13 jun 2019 23:20 (CEST)

Variant: eindboom is nog steeds de huidige boom, en daarvoor hebben we een boom waarin de codewoorden zijn vervangen door de percentages. Bob.v.R (overleg) 14 jun 2019 02:36 (CEST)

Mooie boom, Madyno. Een animatie is een leuke gimmick, maar ik we schrijven hier een tekst, geen film. Die eindboom als plaatje moet dus in ieder geval opgenomen worden. Een of meer tussenstappen ook opnemen kan, maar vind ik niet nodig. Je moet het ook niet overdrijven. Hoopje (overleg) 14 jun 2019 07:10 (CEST)

"Tekst"

Mijn correctie ("tekst" vervangen door "woord", "letterreeks" zou ook kunnen) wegens het feit dat een tekst ook spaties bevat (en nog wat minder frequente tekens zoals punten) is zonder motivering teruggedraaid. Waarom? Als je "tekst" handhaaft moet er een opmerking bij over de andere tekens. - Patrick (overleg) 14 jun 2019 13:04 (CEST)

Sorry, het ging niet om terugdraaien, maar er was een bewerkingsconflict. Ik heb het aangepast. Madyno (overleg) 14 jun 2019 13:41 (CEST)

Het is wel wat onbevredigend dat een optimalisatie met praktisch belang gesuggereerd wordt, terwijl spaties buiten beschouwing worden gelaten. - Patrick (overleg) 14 jun 2019 22:26 (CEST)

Ik heb niet het idee dat praktisch belang gesuggereerd wordt. Het is maar een voorbeeld om te begrijpen hoe de codering werkt. Madyno (overleg) 14 jun 2019 22:31 (CEST)

Lijsten

Ik vind de lijsten onder de boom, met letters en codes, niet erg zinvol in het kader van het voorbeeld. Madyno (overleg) 16 jun 2019 20:53 (CEST)