Learn something new every day More Info... by email
A prefix code is the binary code structure that represents certain letters or characters. These code strings are used by computers to communicate. They consist of zeros and ones that translate into certain commands or words. For example, the letter "A" may contain a prefix code of 0 while the number 1010 represents the letter “D”.
Binary trees are used to represent how strings of numbers in prefix code translate to certain letters, characters or messages. Many software applications use a prefix code based on binary trees to compress their data. Several different combinations of binary code are merged into one "tree" that may contain one or more messages. There is usually a root that is represented by either a 0 or 1 that is equated with one of the characters.
From the root, an extension of numbers can be followed that translates into another letter. There may be several different branches stemming from the binary tree's main line that translate into separate characters. Letters or characters that are represented by one binary digit are called single bits, while those that are represented by more than one binary digit are called two, three or four bits.
The number of bits is directly related to the number of binary digits that represent a particular character in a prefix code. Single bits are typically used for characters that occur several times in a message, while strings of two or more bits are used for those letters and characters that occur infrequently. For example, if a prefix code is encoding the word "relentless," a single bit will most likely represent the letter “E”.
Words and messages are usually made by placing binary code together that reads from the left to the right of the prefix code's tree. For example, one binary tree may contain the letter "R" which is represented by the binary digit 0, the letter "E" which is represented by the binary string 011 and the letter "D" which is represented by the binary string 0110. In this case the word "red" would be strung together as 00110110.
By using prefix codes, computers and applications are able to save space. Since a number of commands and messages use the same letters and characters, each can be represented by certain binary code translations. Separately, these words might need additional storage space due to the amount of bits each of them contains. Binary trees reduce the amount of required bits, sometimes increasing storage space by up to 50 percent.