August 8, 2019

Information, Entropy and Malayalam

This was originally written by Kavya Manohar and published at kavyamanohar.com.

It was during my undergraduate course, I was awestruck by the idea that Information is quantifiable. Until then information for me was an abstract term. It still would have been, if not in the realm of information storage, transmission and retreival.

As a layman we associate the term information to various  contexts - text content of books and newspapers, videos from news rooms,  speech from telephonic conversations, audio podcasts etc- all contains  information. I should not forget to mention that we exchange information in our daily chit-chats too.

What attracts us to a source of information - a new book, a conversation or a video? It is either the novelty of the content or the way of presentation. The former is what I call the information content of the source. It surprises you with new ideas. The latter is an  element of art that charms you to read a book, listen to a conversation  or watch a video. But my concern in this writeup would of course be the  first aspect, that helps you quantify or measure information. A news  room debate may be heavily engaging and tempting to listen, but every  participant would be just stating the obvious. Would you consider that  debate informative? The answer is a big NO!!

What is Information?

So far I have used the term information in a very loose sense. But  when it comes to mathematical quantification, it has to be very binding.   Even in the loose sense, it is meaningful to think a source is highly informative if it is giving out less probable or surprising outputs.

The text content of a newspaper article would just be a sequence of  alphabets. But just imagine what diverse realms of knowledge can be  depicted in English with just the permutations of the 26 alphabets!! The  entire information content of that article can be considered to be  built up of the information contributed by each alphabet. If that idea  did surprise you, I am happy that I just transferred a hell lot of information to you.

A Simple Information Source

But it is difficult to explain how to measure the information  contained in an abstract idea. So let me redefine the scope of the term source of information. Suppose there is a coin tossing machine. It tosses a fair coin in secret and lets you know the result by writing out a H and T for a Head and Tail respectively. This machine is a source of information. The result of  the toss is unknown beforehand and there is an absolute uncertainity.  The message  written out H or T does carry  some information to the outside world. If the machine continuously  tosses and reports the result, there would be a sequence of Hs and Ts  flowing out. Machine reporting an output is equivalent to someone  reporting the result of a cricket match in a news article. The entire  sequence of Hs and Ts contain information  about the result of all tosses. On repeating the experiment many times  you can expect approximately and equal number of Hs and Ts in your sequence. The information present in the sequence is equally distributed among the alphabets H and T.

Now let us expand the secret experiment of coin toss. Our new  information source is a machine that randomly picks up a button in  secret from a group of eight buttons - 4 blue, 2 green, 1 yellow and 1  red - and reports the colour. As in the previous case, instead of  stating the color explicitly just share an agreed symbols B-blue, G-green, Y-yellow, R-red. If the secret pick experiment is repeated many number of times and the results are reported, we get a sequence, say BBYGBBRGGBBGYRBGBB.

In this particular case I can expect a half of the sequence would be Bs, a quarter would be Gs and one-eighth each would be Ys and Rs. That would hardly need any explanation. This is indicated in the folowing probability table.

P(B) = 1⁄2 =0.5

P(G) = 1⁄4 = 0.25

P(Y) = 1⁄8 = 0.125

P(R) = 1⁄8 = 0.125

Since B is a highly probable outcome, its occurance would not induce much surprise in you. In other words, among the symbols B, G, Y and R - B has the least information content in it. Y and R being the least probable outcomes, their occurance would be more surprising and hence contain more information. The information content in a source symbol is infact inversely realted to its probability of occurance.

But what is Entropy?

Before quantifying this information let us agree on some unit to represent it. Let us choose binary digits (0 and 1) as the symbols to represent the outcome of any information source. That is instead of H and T use 0 and 1. To convey the outcome of the coin tossing machine, you need one bit. If you repeat the coin tossing experiment 32 times, you will need 32 x 1 = 32 bits to represent the sequence of outcomes.

Instead of B, G, Y and R let us use the binary words 00, 01, 10 and 11 respectively. That is to tell the outcome of the button picking machine you need two bits.  Repeating the button picking experiment 32 times would require 32 x 2 = 64 bits to indicate the sequence of outcomes.

Now the question is, can it be represented in a more compact way? What if I use 1 for B, 01 for G, 000 for Y and 001 for R? So now I need 1 bit to say Blue was chosen while 3 bits to say Yellow. The sequence of 7 outcomes BBYGBBR can be now written as 1 1 000 01 1 1 001, using just 12 bits. If it were the earlier scheme we would have needed 14 bits.

That sounds cool!! But what did we just do?

Instead of assigning equal length binary word to each symbol B, G, Y and R , we assigned shortest word of 1 bit length to the symbol B which contains the least amount of information and the longest word of 3 bits to the the symbols Y and R with the highest quantity of information. When you represent a large sequence of outcomes like BBYGBBRGGBBGYRBGBB in bits, this would reduce the total number of bits as we have exemplified above.

Why does it reduce the total number of bits?

It is because you have used the shortest word for the most frequently occuring symbol B and the longest word for the least occuring symbols Y and R.

If you have not noticed already, the length of word assigned to each  symbol was infact the base 2 logarithm of the inverse of probability of  occurance of each symbol. This number(the base 2 logarithm of the  inverse of probability) is the information content of that particular  symbol in bits. You can read that once again!!

Probaility of each symbol

P(B) = 1⁄2 =0.5

P(G) = 1⁄4 = 0.25

P(Y) = 1⁄8 = 0.125

P(R) = 1⁄8 = 0.125

Code word and Information content of each symbol. Information is Quantified in this step!!

Code for B = 1. The Information content of B is given by:

I(B)=log210.5=1 bit

Code for G = 01. The Information content of G is given by:

I(G)=log210.25=2 bits

Code for Y = 000. The Information content of Y is given by:

I(Y)=log210.125=3 bits

Code for R = 001. The Information content of R is given by:

I(R)=log210.125=3 bits

Initially we had used equal length code for each symbol. So the  average code word length was 2 bits. Now our code word is variable  length, the length corresponding to the information contained in each  symbol.

The average information content per source symbol is H(X)=∑ni=1P(xi)I(xi)=0.5×1bit+0.25×2bits+0.125×3bits+0.125×3bits=1.75bits

The term H(X)

is the entropy of the source.

On an average you need only 1.75 bits (unlike 2 bits we assumed  initially) per source symbol to represent the information emitted by the  source. The colours are predictable to some extend and that reduces the  uncertainty and thus the information contained in it. If all the four  colours were equally likely, you would have needed same number of bits  to represent each letter and that number would have been 2, ie. (log210.25)

Higher the entropy of a source, on an average we need more number of  bits to represent a source symbol. In the example above the codeword  length was same as the information content of that symbol. This is  possible because the information defined by log2(1P(xi)

,  happened to be integers. It need not always be the case. If it is not  an integer, choose a code word length that is the next higher integer.  Then the average codeword length would be higher than the entropy. A

Assigning a binary codeword to a symbol, that has a length (approximately) equal to the information contained in it is called entropy coding. A popular type of entropy coding is Huffman coding algorithm. Replacing every occurrence of a symbol by its huffman code  would essentially compress the content than it were represented by equal  length codes.

This is infact an idea first proposed by Claude E.Shannon and the foundation for the theory of compression and communication. If you have observed the Morse code used in telegraphy, the same idea of assigning shortest code to most frequently occurring symbol can be seen.

Further, if you are really interested in the equation of entropy, check out the video in speech zone.

But the source need not always be the tossing machine!! Then how would I find the best code word length?

The source of information and its structure need not be known  beforehand. You can always observe a large sequence of symbols emitted  by a source and just count the number of times a particular symbol is  repeated. Find the probability of occurrence of the symbol. Once you know  the probability, you can find the information content associated with that symbol in bits. Averaging it over all symbols and their probabilities, would give you the entropy.

Shannon himself has tried to determine, the entropy of English language. If all the alphabets were equally likely, the entropy would have been log2(1126)=4.7bits/letter

. But on analysing English language, e is the most and q the least popular letters. Analysing the relative frequencies, he has reached the answer that the entropy is 4.14 bits/letter.  The more we know about the statistical structure of a language, it  becomes easily predictable and thus reduces the information content and  thus the entropy.

The redundancy in a langauge can be further explored by considering  the probability of a particular letter to follow another letter, and the  entropy can be found to be still lower. From Shannon’s paper on Prediction  and  Entropy  of Printed  English

The redundancy,on the other hand,  measures the amount of constraint  imposed on a  text in the  language  due  to  its  statistical   structure,  e.g. in   English  the  high  frequency  of  the  letter E,   the strong  tendency  of H  to  follow  T  or of  U  to  follow Q.  It   was  estimated  that  when  statistical  effects  extending  over  not   more than  eight  letters  are  considered  the  entropy  is  roughly   2.3  bits  per  letter, the  redundancy  about  50  per  cent

Entropy of Malayalam Script

Every scripted language has an inherent structure that makes certain  character sequences valid words. A probability modelling of the  alphabets of the language with respect to the relative frequency of  occurance of the alphabets can be done by analysing huge text corpora of  that language. An experiment to determine the entropy of Malayalam  script is elaborated next.

I extracted a subset of Malayalam sentence corpora maintained by Swathanthra Malayalam Computing. Regular Malayalam text content has English alphabets occurring occasionally.

Then the following python script was used to filter out English and  retain only those characters relevant to Malayalam. The relevant list of  alphabets consist of all the Malayalam vowels(അ, ആ ..), consonants(ക, ച,  ട…), vowel signs(ാ, ി…), Arabic numerals (0-9) and basic punctuations  including space and newline characters .

A part of the sentance corpora consisting of curated content extracted from newspaper articles, blogposts etc. in textcorpus directory was filtered and the resulting content was placed in result directory as a single textfile malayalam.txt using the following shell script.

cat ./textcorpus/*.txt | python malayalam-filter.py > result/malayalam.txt

Now it is time for relative frequency analysis on malayalam.txt. Python libraries numpy, scipy and huffman helps in the statistical analysis and the code below is self explanatory.

On analysing 543865 characters, the resulting entropy is 4.944 bits/character. The result as given by the above script is as below:

The number of characters parsed 543865
Total number of unique characters: 82
writing content to character frequency table
The entropy is: 4.9443809924853666
writing content to huffman codebook

If you are curious to see the relative frequency of each characters, have a look at the character frequency table:

You can see for yourself ് is the most frequent character in Malayalam script and ഋ is the least occuring one.

Now if you apply Huffman encoding, the most frequent character will  get the binary code-word of least length. See for yourself the huffman  code for each of the above characters.

് has a 3 bit code word while ഋ has a 17  bit code word. You can experiment for youself by changing the corpora,  and find out the corresponding entropies and binary codewords. On  expanding the corpora by including the Malayalam wikipedia articles, I  got an entropy of 5.024 bits/characters.

Infact there has been prior attempts in this regard for Malayalam and the details can be found in the following academic papers.

It reports an entropy of 4.8 bits per character. The difference might have been caused by the choice of corpora.

  • “Malayalam text Compression”, Sajilal Divakaran, Biji C. L., Anjali C., Achuthsankar S. Nair, International Journal of Information System and Engineering, 2013

It reports an entropy of 5.47 bit per character. But the characters  chosen are not the atomic characters, but mostly consonant conjuncts and  that has made a difference.

What does that mean, if Malayalam has an entropy of 4.944 bits/letter?

In the simplest terms it indicate the limit to which you can compress  Malayalam text content. If you have a text of 1000 characters in  Malayalam, it would follow a probability distribution as indicated by  the character frequency table. You can replace every character by the  huffman code we derived above and the total number of bits you need to  represent those 1000 characters would be approximately 4.944 bits/letter x 1000 = 4944 bits. But inorder to recover the original text you will have to look-up a huffman code table.

Representing a 1000 character text in Malayalam in Unicode encoding would have costed you 1000 x 24 bits = 24000 bits !! Remember every Malayalam unicode character takes 3 bytes of memory.

To wind up, there are still more possibilities to explore towards  the statistical nature of the Malayalam text. There are restrictions  like a vowel can never occur in a valid Malayalam word, unless it is at  the start of the word. Such properties can be extracted from the N-gram  character probability modelling of Malayalam and the corresponding  entropy would be smaller and can help you reach better compression.