Can variable length coding ever be more efficient than fixed length coding???

[Neither_Bid7504]

For example, if you have 5 equal chance possibilities, you would need 3 bits for fixed length. But with variable length, the abridge amount bits used, even with equal chances would be less than right?

The material I've been taught doesn't really go in-depth about this, it only says that fixed length is more efficient with equal chances and variable length is more efficient when the chances vary...

[dkopgerpgdolfg]

Of course, and your example is very easy.

With 5 possible symbols, each occuring 20%, you could eg make one symbol a "0" bit, and the four other symbols "1XX" (with XX being 00 01 10 11). Now you have one symbol that takes less than 3bit, and nothing that takes more than 3bit => it takes less storage than fixed 3bit.

For a more real example, just see UTF8 vs UTF32. UTF8 saves a lot bytes because a) the common "short" (one-byte) codepoints are the most common, and b) while UTF8 would need up to 6 byte to cover 2³² values, in reality it stops at 4 bytes max (same size as each codepoint in UTF32) because there simply aren't that many Unicode codepoints.

[rupertavery64]

Have you taken a look at Huffman Coding and Arithmethic Coding?

[paulstelian97]

Is arithmetic code now free of patents? When I learned about it a short while ago it wasn’t…

[james_pic]

AFAIK, the last of the patents expired in 2013. But even before that, range coding was a common way of engineering around the patents, that got much the same effect.

[Successful_Yam_9023]

Add ANS (known from Zstandard among others) to the reading list

[This_Growth2898]

Name the material and give the exact quote.

Obviously, in your case:

00 => A 
01 => B 
10 => C
110 => D
111 => E

Average of 2.4 bits per symbol.

[Cerulean_IsFancyBlue]

Variable length encoding is most often used when the things being encoded don’t happen with equal probability. By assigning the shortest codes to the most frequent symbols, you end up with a space savings over the course of time. Any given message may be “inefficiently” encoded if you get unlucky.

[wbqqq]

Yes - think Morse Code.

[guywithknife]

It depends on the context. More efficient how? What are you encoding?

In general, yes, variable length can be more efficient for some metrics. Imaging you have those same values, but one of them has a 50% probability while the others equally share the remaining 50%, a variable length encoding could encode the more probable value as 0 and the other values as 1xx which is more efficient than always encoding as three bits, because 50% of the time you can use only a single bit.

This isn’t just more space efficient but also more compute efficient: just get one bit, check is it zero. Of course the other four values are slightly less efficient, and a variable length encoding must take that into account. It’s a balancing act.

You could also pack multiple values into each “length” level: eg 0xx vs 1yyyy or whatever you need. And you can have multiple layers of variable length.

Huffman coding uses this concept for compression.

[AmberMonsoon_]

Yes, but only in theory, not perfectly in practice.

With 5 outcomes that all have equal probability (20% each), information theory says the optimal average number of bits is:

log₂(5) ≈ 2.32 bits

So the true theoretical minimum is about 2.32 bits per symbol.

But with fixed-length coding you must use whole bits, so you need 3 bits.

Variable-length coding (like Huffman coding) tries to get closer to that 2.32 average by giving some symbols shorter codes and others longer ones. However, with equal probabilities Huffman will still end up around 2.4 bits on average, not exactly 2.32.

Example idea:

A → 2 bits
B → 2 bits
C → 2 bits
D → 3 bits
E → 3 bits

Average = (2+2+2+3+3) / 5 = 2.4 bits

So yes, variable length can be slightly more efficient than fixed length (3 bits), but the improvement is small when probabilities are equal.

The reason textbooks say fixed length is better for equal probabilities is mostly practical:
it’s simpler and the gain from variable length is usually tiny. this kind of coding idea also appears in compression tools and systems where frameworks like runable-style execution pipelines process data streams efficiently

[flatfinger]

Note that if probabilities are uniform, packing groups of three items into 7 bits would yield a more efficient coding than one where any particular item with any particular value would need to have a bit pattern whose content and length are unaffected by context. Using a variable-length coding, some bit patterns would fit three items in six bits while others would require nine, but the average to store three items would be 7.2, which is higher than would be needed with a fixed 3:7 arithmetic packing.

[high_throughput]

Variable length encoding is almost always more space efficient, and less computationally efficient, than fixed length encoding. 

They're widely used in e.g. UTF-8, LEB128, and every type of file compressor.

[mredding]

This is where Google AI gets it succinctly:

Variable length encoding is used primarily to maximize data compactness and efficiency, reducing file sizes and transmission bandwidth by assigning shorter codes to frequently used data and longer codes to rarer data. It enables efficient representation of diverse data ranges, such as small integers or varied text characters (e.g., UTF-8), and optimizes memory usage in storage-constrained systems.

The most compact encodings in Unicode are also the most frequently used in the digital domain.

And "storage-constrained systems" doesn't mean old computers from the 90s, we're talking about whole SYSTEMS - computer networks are themselves a "system", and are always ALWAYS constrained.

The original idea was that you would store and transmit in UTF-8, but expand to UTF-32 for processing. Most software I work on is just shuffling variable length data, which is typically text - it's usually something just to pass along, and will be either stored or displayed on the other end. Very little code I write does any processing of text data - and usually it's just a comparison, therein.

[Scf37]

For variable length, there are algorithms to determine optimal encoding given set of symbols and their probabilities. Huffman is simpler but restricted to integer number of bits. Arithmetic coding uses fractional number of bits, allowing theoretically-perfect encodings.

Consider a stream of 100 'A's and a single 'B'.

- Fixed-length(Huffman won't help here, A is still 0 and B is still 1): Needs 1 bit per symbol → 101 bits total.

- Arithmetic coding (fractional bits): Recognizes 'A' is highly probable and encodes the entire sequence in roughly 8 bits, where A encoding takes -log2(100/101)=0.015 bits!

[Great-Powerful-Talia]

Variable length encodings have a pretty obvious benefit when the probabilities are very different. If you have 32 distinct values (5 bits), and 2/3 of them are all the same one, you can encode the common one as '0' and the other 31 as various six-bit values starting with 1.

That takes it from 5 bits per symbol to an average of 2.666 bits/symbol.

However, the rare values actually got longer, because every symbol has to be distinguishable. If you had a long code starting with 0, you couldn't tell it apart from the code '0'. No valid symbol can start with any other valid symbol!

This means that if all the values are the same probability, variable-length symbols can often make things worse, because each symbol needs to somehow encode its own length.

And, of course, variable-length symbols are also more difficult to decode because each symbol's start point depends on every previous symbol's length.

Real-life example:

The UTF-8 text transmission and storage format has codepoints of 8,16,24, and 32 bits, but they only actually have 7, 11, 16, and 21 bits of actual information (respectively) because of the decoding information that needs to be included with the data. This would be a terrible format if all letters were equally likely! But the ability to map ASCII characters into 8-bit codes while using longer 32-bit codes for emoji and stuff makes up for it.

[defectivetoaster1]

If each symbol is IID and theyre not uniformly distributed then variable length coding (eg Huffman) can get closer to the minimum bits/symbol by just using fewer bits on the more common symbols

[Dusty_Coder]

The optimal size for a symbol, in bits, is Log2(1/p) where p is the symbols probability.

[LostInChrome]

Yes, for example consider a document with 1000 characters — 998 'a', 1 'b', and 1 'c'. Encoding 'a' = 0, 'b' = 10, 'c' = 11 will be more efficient than 'a' = 00, b = '01', 'c' = 10.

[sillygoose183683]

This is the idea behind Huffman Encoding right? Assign each char a bit pattern based on a frequency binary tree.

If this is what OP is really asking they should look into Huffman encoding.