huffman encoding reviews

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

Andrew Davie

I currently have a candidate pool of 147 reviews. These are heavily culled from literally thousands. My current thinking is that I'll have 100 levels, consisting of 10 planets and 10 continents on each. Each of those will have a 'review', hopefully oddball with a bit of humour.

So, that's a lot of text. I do have "ample" ROM space, of course, but it tends to disappear quickly. The 147 reviews take about 15 KB of space. So, just for a bit of fun/interest I decided to encode these strings (i.e., compress them) using Huffman encoding - which experience tells me is a suitable method for this scenario.

It's all working, and I can switch between normal/compressed with a simple #define.

It's saved about 6 KB (reduced to about 60% of original size), which isn't to be sneezed at.

Other things:  I have tweaked and tweaked and tweaked the proportional, justified, string drawing routines. It's rather nice now.
=   center the string
<   left-justify the string
>   right-justify the string
_   turn on/off underlining
|   start a new line
.|  if a sentence ends at end of line, a long pause is inserted
~   pause dramatically (don't print the ~)
,   print a comma followed by a short pause
%   a single open-quote
&   a single close-quote
"   double open-quote
#   double close-quote
\   escape the next character and draw it instead of processing it
    so the above will all print as the expected shapes instead of the control shapes

So, a typical string is encoded (before Huffman compression) like this...

"=\"The|planet hums a|note not|quite any|note I know,|and my|species has a|word for that|note, and the|word means|_leave_.#

To start a string drawing, just...

            drawString(FONT_COMPACT, 0x8, 3, _BUF_GLOBE_GRP, _BUF_GLOBE_COLUP0,    //
                       "=_Planet@Visor", 0, pa_lines - 20);

Parameters:
1. which font to use. All fonts are of variable width, height.
2. colour
3. typing speed/delay. In this case one letter every 3 frames
4. Which sprite buffer to draw
5. Which colour buffer to draw to
6. string to draw
7. x coordinate. i gotta remove that - no longer used
8. y coordinate

All of the centering/justification is calculated automatically at runtime.  The screenshot shows how the above example displays. The video shows it in action Sound might be out of sync because I used Gopher video capture and it's still in development/slightly buggy. One interesting addition was to NOT include the opening/closing quote for the review as part of the centering calculation. That is, the TEXT on those first/last lines is centered, but the quote is not a part of that.  The quote is placed to the left/right of the centered text. That took quite some time to get right, as the centering calculation has to cater for TWICE the width of the quotes to get things right. Took me a while to figure that one out. But it's really nice now -- quite some space between those quotes and the text. It's the little things that matter.


Justification is on a global basis - all fonts are justified the same way. I have a neato table that has  'modifiers' for each of the printable characters.

1. If it's actually a printable - some are control characters as described above
2. If it can be underlined
3. If it is left-justified (shifted left one pixel when drawn)
4. If it is right-justified (next character is shifted closer - left - when drawn)

With the recent discovery of being able to use emojis in the source code, it's really easy to eyeball which flags are set/clear.

const unsigned char justifyChar['~' - ' ' + 1] = {

//   🟨 = visible
//  ⎧        🟨 = underline
//  ⎮       ⎧  🟨 = left-justify
//  ⎮       ⎮ ⎧  🟨 = right-justify
//  ⎮       ⎮ ⎮ ⎮
    🟨🟦🟦🟦🟦🟦🟦🟦 ,    //   ' '         32
    🟨🟦🟦🟦🟦🟦🟦🟦 ,    //   '!'         33
    🟨🟦🟦🟦🟦🟦🟦🟦 ,    //   '"'         34
    🟨🟦🟦🟦🟦🟦🟦🟦 ,    //   '#'         35
    🟨🟦🟦🟦🟦🟦🟦🟦 ,    //   '$'         36       replacement '.' without a delay (for numbers0
    🟨🟦🟦🟦🟦🟦🟦🟦 ,    //   '%'         37
    🟨🟦🟦🟦🟦🟦🟦🟦 ,    //   '&'         38
    🟨🟦🟦🟦🟦🟨🟦🟦 ,    //   '''         39
    🟨🟦🟦🟦🟦🟦🟦🟨 ,    //   '('         40
    🟨🟦🟦🟦🟦🟦🟨🟦 ,    //   ')'         41
    🟨🟦🟦🟦🟦🟦🟨🟦 ,    //   '*'         42
    🟨🟦🟦🟦🟦🟦🟨🟦 ,    //   '+'         43
    🟨🟦🟦🟦🟦🟦🟨🟦 ,    //   ','         44       + short pause
    🟨🟦🟦🟦🟦🟨🟦🟦 ,    //   '-'         45
    🟨🟦🟦🟦🟦🟦🟦🟦 ,    //   '.'         46       + long pause if '|' follows
// ... etc

Well, it looks MUCH nicer in my IDE. See attached screenshot.


The attached binary has a (low-volume) background tune that every now and then changes volume. It also has the typing sound effects installed. In fact, it's pretty much polished. I'm going to move on to creating that progress/status grid to show which planets and continents you've completed. It will be pretty much identical to the grid thing I used in GridLock (see image).

Binary tests working OK on Stella and Gopher. For me!

OK, finally -- here are the 147 candidate reviews.

QuoteThe currency is based on something I will not name, but I had more of it after a long trip. That felt unfair.
QuoteChecked in to what I thought was my room. It was a lift, and I unpacked before the lift explained itself.
QuoteEach room runs at a different speed. I was somehow early and late for the same meal.
QuoteA kind word here causes mild pain. I was polite from day one. Did not connect these facts until day two.
QuoteThe tourist board slogan is... WE ARE HERE. That is the full extent of the pitch.
QuoteA human laughed at me, and I read this as a threat display. I responded in kind. The crowd that formed did not help.
QuoteAssumed the atmosphere was decorative. Removed my suit. Second mistake, after booking.
QuoteJoined what I thought was a guided walk. It was a funeral. By the end I was a pallbearer.
QuoteI asked a local what they did for fun. They stared long enough that I felt I had said something in very poor taste.
QuoteEveryone here has three shadows, one of them cold. Mine kept touching theirs, and this was rude.
QuoteA human told me to have a nice day, and I said I would try. It looked at me as though trying was not the expected response.
QuoteBeautiful planet, would return. Can't return for legal reasons.
QuoteMade an amazing discovery on this planet. The box provided is too small to detail it here.
QuotePaid for the premium tour. It was the same as the standard tour, but with an angry guide.
QuoteStepped off the ship and joined the local ecosystem. Took effort to reverse. Left me feeling implicated in something.
QuoteThe exit sign pointed at the ocean, and the ocean had no exit. Very poor planning.
QuoteThe locals can see sound and asked me to keep it down. I said I was not making any. They showed me.
QuoteThe gravity reverses briefly at noon. This is in a footnote. The footnote is at the bottom of the page.
QuoteThe handshake has a part where you pretend not to know each other. I skipped that part, and things went wrong.
QuoteThe nightlife starts at dusk, ends shortly after dusk, and everyone goes home and sighs.
QuoteThe welcome pack included a breathing guide, which I assumed was a joke. It was not a joke.
QuoteThere is no word for stranger, and I was given a family on arrival. They had views on how I spent my days.
QuoteThey keep a room clean and ready for guests, sit in a worse room on all other days, and call this having a lounge.
QuoteThey pay for water in a bottle when it falls free from the sky, complain when it falls. Both are considered normal.
QuoteThey removed the stimulant from their stimulant drink, still drink it, and call this a choice they made freely.
QuoteTime here is measured in moods. My shuttle was due at after the sadness, and I waited at the wrong feeling.
QuoteTravel insurance listed this planet by name in the exclusions, and I booked anyway, my mistake.
QuoteTried to explain to a human that their planet is unusual, and she said "we like to think we are special". I said "know".
QuoteWas handed a leaflet of things to do here. The leaflet had one page, and one of the things listed was leaving.
QuoteWas told the piles were 'historical' and I said 'historical what?'. Nobody finished the sentence.
QuoteThe year is three days long. I booked a week. Five new-year celebrations. A gift was expected each time.
QuoteThe slow part of the day is called rush hour, a naming decision that has clearly never been reviewed.
QuoteThe local cemetery is peaceful and well-kept. The dates on the stones are all in the future.
QuoteA local told me to take care when I left. I asked of what. She said just in general. I said that is a lot to take care of.
QuoteDid not realise breathing was compulsory here. Had to be reminded twice. Signage is inadequate.
QuoteHeld my umbrella the wrong way for two days before learning the rain falls down here.
QuoteI asked a local how long they had lived here. It said longer than it meant to, and stared at the horizon.
QuoteI asked a local what time it was, and he told me in a unit I do not have the organs to perceive. Useless.
QuoteI asked a ranger which trail was best. He said "It depends". I said "scenery". He said "then not this planet".
QuoteI asked if the air was safe. "For some definitions of safe", they said. My species reads this as yes. It is not.
QuoteI asked if the haze ever clears. "Clears of what?", they asked. I realised they had never seen their planet.
QuoteI asked where all the valuable minerals had gone, and was told "away".
QuoteMistook the warning siren for a welcome song, and sang for twenty minutes before someone intervened.
QuoteMoisture stuck to my outer layer. I took this as territorial and panicked. Better labelling would help.
QuotePhotos came out entirely grey, and the locals said that was the best the planet had looked.
QuoteMy ship's navigation refused to save this location to favourites. I now understand it was trying to help me.
QuoteThe air here is edible. I had too much on day one and had to lie down. For reasons I could not convey to anyone.
QuoteThe beach looked perfect in photos. Photos were the right way to experience it.
QuoteThe guide pointed at something, said "there it is", and walked on before I could see what it was.
QuoteThe locals change colour to speak, and I have no such ability. I spent the trip mute in a way I have not been before.
QuoteLocals exhale what I breathe. I exhale what they breathe. For one afternoon we were very close.
QuoteThe locals shed their skin each morning and leave it in the hall. I greeted my neighbour's "shed" for two days.
QuoteThe ocean here is technically swimmable, in the sense that you can enter it and exit it. The question is what you exit as.
QuoteThe wildlife ignored me until it did not. The transition was not announced.
QuoteThe local drink was an "acquired taste". I acquired it. I would like to return it.
QuoteThe locals have a greeting of twelve gestures. I learned eleven. The twelfth is apparently the important one.
QuoteI left a review on arrival as is my custom. The locals found it. It affected the rest of the stay.
QuoteLovely from orbit. The tourism board recommends orbit. This is on page nine.
QuoteThere was a festival. I was not told what it was for. I was told to stand here. I stood here. Nobody explained.
QuoteSaid goodbye on leaving. The local said see you soon. I have not returned. I think about that.
QuoteThe local told me to enjoy my stay. I asked how. He said however I liked. I did. He later told me that was not what he meant.
QuoteI make a sound when I breathe. This species associates that sound with grief. The staff were very kind.
QuotePointing is considered rude here. The guidebook has pictures you point at to order food. This is not addressed.
QuoteThe local children ask how many times you have died. I said none. They conferred and moved away.
QuoteOn day five my translator became philosophical. It rendered everything as "but why?" I have not found good answers.
QuoteThere are no shadows here. The light comes from everywhere. After three days I missed somewhere to hide.
QuoteThe locals do not finish sentences. They stop where the important part begins. My translator was not built for this.
QuoteThere is no word for yesterday here. All complaints must be about the future. I filed seven.
QuoteI was warned the locals read thoughts. I was very careful. I would prefer not to say about what.
QuoteThe guidebook says locals value directness. One told me the guidebook was not written here.
QuoteThe locals sleep in shifts. The shifts are unlabelled. I got into someone else's bed on day two. They were polite.
QuoteThe guidebook says locals are friendly to visitors. A second guidebook clarifies which visitors. I had the first.
QuoteI glow slightly in cold. It was cold here. By day three several people had begun following me at night.
QuoteThe planet rotates the wrong way. I cannot explain why this bothers me. I have felt slightly wrong all week.
QuoteThe locals use descriptions, not names. I arrived tired and confused. This is now my name.
QuoteA local ritual. Six hours. Nothing happened. The locals were very pleased. I asked. They said "everything".
QuoteThe smell here is called "distinctive" in the brochure. Calling a fire warm is also not wrong.
QuoteThe locals have perfect recall. I had forgotten what I said on day one. They had not. Day three was difficult.
QuoteThe locals point with their attention, not their fingers. I spent three days not knowing where anything was.
QuoteBy day four a plant near my window had moved. I mentioned this to the staff. They said yes.
QuoteThe planet hums a note not quite any note I know, and my species has a word for that note, and the word means leave.
QuoteThe planet smells of something I cannot name but have smelled once before, in a situation I do not wish to revisit.
QuoteThe scenic flyby is good if you like gas, which I did not know I did not like until I was inside it.
QuoteHello and an explicit proposal differ here only by tone. I have poor tone in this language. I was very popular.
QuoteThe tourism office gave me a list of things to do. One of them was the tourism office. I was already there.
QuoteThe two moons orbit at a distance that suggests they are trying to stay out of things.
QuoteI was measured on arrival. My dimensions were noted. Several locals came to look.
QuoteThe attendant said the wildlife was friendly, and when I asked how friendly, she paused in a way that answered.
QuoteI asked a local if the smell was natural or man-made. She said "yes". I have thought about this every day since.
QuoteI asked what grows here. I was told "resentment". Booked the cultural tour. It was about resentment.
QuoteLanded, explored, ate something, left. Three of those four I would not do again.
QuoteMisread the entry form, and declared myself as luggage. I spent day one in a storage bay nicer than my hotel.
QuoteMy suit's air monitor skipped numbers and went straight to a small picture of something dying.
QuoteThe cold here has texture. I was not warned about this. I do not have the right organs for it.
QuoteThe gas here is sentient in patches. One of the patches was in my cabin and had strong views about the lighting.
QuoteThe heat here sits in the range my species uses for food storage. I kept reflexively trying to put things in the locals.
QuoteThe local dish arrived alive and looking at me. I did not know the correct response.
QuoteThe ocean laps the shore in a way that sounds like it is sighing at you, personally.
QuoteThe oceans are warm and the things in them are also warm and "friendly", in a way that means you cannot swim.
QuoteThe locals keep a small animal in their dwelling. The animal has no duties. The animal knows this.
QuoteA local said "have a good one" as I left. I did not know what one. I have been thinking about the one.
QuoteAsked if there was anything I should not do. He listed seven things. I had done four of them before he finished.
QuoteI smiled at a local. It stopped. I stopped smiling. It resumed. I have thought about this every day since.
QuoteI do not sleep the way this species does. I stood in a corner each night. The cleaner stopped coming in on day two.
QuoteThe entry form asked what I was willing to lose. I did not read this carefully. I have since checked. Something is missing.
QuoteThe locals reproduce by arguing. I made several points at dinner. I am told there are now nine more locals. I apologise.
QuoteThis planet smells like something I recognise but cannot name. On day four I placed it. I cut the trip short.
QuoteThe sky has no colour name. My translator called it "the colour before something stops being true".
QuoteThis planet has a return policy on experiences. I tried to use it. There is a lot of paperwork.
QuoteI asked what the smell was. A local said it was the planet thinking. I asked what about. She said "us".
QuoteThe locals measure distance in feelings. The hotel was "not far" and "worth it". It took me three days.
QuoteThere is a saying here: "the second time is always worse". My translator offered this unprompted. Several times.
QuoteThe scenery is "once seen, not forgotten", says the brochure. This is accurate. I wish it were not.
QuoteThe pool had a sign I could not read. The staff said it was advice. I asked what advice. They said not swimming.
QuoteThe reviews all said "you will see". They were all five stars. I have seen. I understand.
QuoteThe wake-up call came at seven. A voice said "it is seven". Then "we are sorry". Then nothing.
QuoteThe guest book entries were all addressed to the next visitor. They all said the same thing. I added mine.
QuoteThe guidebook said the locals value intimacy with visitors. I thought this meant being open. I was half right.
QuoteThe planet hums at a pitch my species reads as grief. I cried for five days.
QuoteThe upgrade was to a larger pile, and I said thank you because I did not know what else to say.
QuoteThe volcano tour was cancelled due to the volcano, a sentence I could not have predicted needing.
QuoteI asked about the length of the tour. The guide said it depended on interest. She said I seemed very interested.
QuoteMy translator rendered the local language as 'medium length sighs' all visit. I'm not entirely sure that was wrong.
QuoteStepped off the ship and became part of the local food chain within minutes.
QuoteThe compost bin in my room was sentient and began making requests on day two. I did not know how to refuse.
QuoteThe days are eighteen minutes. I booked three nights and was there for under an hour.
QuoteThe festival was described as "lively". It involved twelve people standing near a thing.
QuoteThey exchange information by vibrating their face-holes. Impressive, but needless given that telepathy exists.
QuoteThe kids here have a look in their eyes that I have thought about every day since I left.
QuoteThe locals are made of sound, and I kept walking through them. They kept saying sorry, which made the problem louder.
QuoteThe locals have no word for "no" and express it by doing the thing anyway. Sadly, I missed this for three days.
QuoteThe locals leave gaps in speech for you to fill. By day one, I had agreed to several things I had not planned on.
QuoteThe locals said the smell was part of the culture. I said which part, and they said "all of it".
QuoteMy room had a card explaining local etiquette. I read it after day three. This explains days one through three.
QuotePaid extra for the room with a view. The view was of the room with the better view.
QuoteThe planet has one season. The locals have twelve words for it and argue about which word applies.
QuoteThe signs use a language I do not read. The locals also do not read it. This was not in the brochure.
QuoteThere was a gift shop at the exit. The gifts were images of the entrance. I bought one. I do not know why.
QuoteMy translator gave up on day four and began summarising. "They are speaking", it would say. "It is about you."
QuoteThe currency here is apologies. I had several to spend. I ran out on day three.
QuoteThe mountain is said to watch visitors. I dismissed this. On day four it was closer. I did not check on day five.
QuoteThe local greeting is something I will not describe. I thought it was a handshake. We are married now.
QuoteThe gesture for thank you here is very intimate. I thanked everyone I met. I have been invited back.
QuoteThe planet leans, and every local I told looked genuinely unsure if that was true.
QuoteThe shadow followed me the whole time. When I complained, I was told it was mine. This only raised more questions.
QuoteI asked about the noise. She said "relaxing". I asked if always this loud. Only when it goes well.
QuoteThe currency is smell-based. I arrived with nothing of value, and left owing a scent debt I am still repaying.

If you've read this far, let me know which ones you like.

Andrew Davie

My brain 'programs' overnight, and I woke up thinking maybe the Huffman encoding could be improved if I had a word dictionary along with the character encoding. I was right. The new encoder has a 60 word dictionary (built from the input text) and the improvement is significant.

Phrases       : 156
Word dict     : 60 words
  top words   : and, the, was, The, said, not, planet, for, that, what
Token set     : 112 tokens  (11723 total vs 15776 chars)
Max code len  : 14 bits
Verification  : all 156 phrases OK
Original      : 15776 bytes
Compressed    : 7599 bytes (48.2% of original)
Baseline      : 9020 bytes (57.2%) — chars-only Huffman
Word saving   : +1421 bytes vs baseline
Avg bits/char : 3.85
Written       : ../main/planetHuffman.h, ../main/planetHuffman.c

Essentially, reduced the text from 15.5 KB to 7.5 KB, a 1.5 KB improment on the previous encoder.
All working OK. Thanks, dreaming brain.

Andrew Davie

More refinement. I've switched to a scheme called BPE (Byte Pair Encoding) which, instead of using a word dictionary, uses a dictionary of arbitrary characters. I parse the remarks set to find the optimal 'dictionary' of BPEs -- and also pre-parse to figure the optimal dictionary size (by exhaustive search of 0-100).  It takes a few seconds at most.

With all this, I save another 58 bytes (including code overhead) on the last pass. Total savings 905 bytes from the original Huffman encode.

Best          : 72 merges → net saving +905 B
Token set     : 121 unique  (9513 total vs 15776 chars)
BPE tokens    : 72  e.g. ['t|', 't ', 'e ', 'ha', 's ', 'and ', 'e|', 's|']
Max code len  : 13 bits
Verification  : all 156 phrases OK
Original      : 15776 bytes
Compressed    : 7575 bytes (48.0%)
Token table   : 540 bytes overhead
Net saving    : +905 bytes vs baseline
Avg bits/char : 3.84
Written       : ../main/planetHuffman.h, ../main/planetHuffman.c

I know it's probably pointless, but I've enjoyed the challenge.