<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Hemalatha M on Medium]]></title>
        <description><![CDATA[Stories by Hemalatha M on Medium]]></description>
        <link>https://medium.com/@hemalatha.psna?source=rss-5347d02b36e5------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/2*z-7x3dx3uc6ocBz11PZrEA.jpeg</url>
            <title>Stories by Hemalatha M on Medium</title>
            <link>https://medium.com/@hemalatha.psna?source=rss-5347d02b36e5------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 02:44:36 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@hemalatha.psna/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Getting started with Node and npm]]></title>
            <link>https://javascript.plainenglish.io/node-package-manager-e9e5ba45da72?source=rss-5347d02b36e5------2</link>
            <guid isPermaLink="false">https://medium.com/p/e9e5ba45da72</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[web-development]]></category>
            <category><![CDATA[javascript]]></category>
            <category><![CDATA[nodejs]]></category>
            <category><![CDATA[software-development]]></category>
            <dc:creator><![CDATA[Hemalatha M]]></dc:creator>
            <pubDate>Thu, 10 Oct 2019 04:31:30 GMT</pubDate>
            <atom:updated>2019-12-09T09:37:04.900Z</atom:updated>
            <content:encoded><![CDATA[<p>For years, there have been so many developers around. Each of them contributing to many portions of JavaScript development. But how about duplicate code. Over and over if many developers write the codes over and over again, there will be a lot of duplicate code. To avoid this problem, they invented something called as node package manager.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*y5YLuOKO5XM7MOzve6XsDQ.png" /></figure><p>We would have heard about JavaScript packages. A package is a file or a set of files full of existing, <em>reusable</em> code. They are designed to be shared, allowing many web developers to use the same code in their own projects. Npm(node package manager) helps to keep these packages organized.</p><p>There are developers around the world and have resolved many problems with perfect solutions. When we try to resolve similar problems, we need not reinvent the whole solution again while excellent working solutions already exist. We can reuse the code written by other developers which are made available as packages. And npm is a tool used for this purpose. The value of existing code is incredible.</p><h3>How to set up</h3><p>If you have installed Node.js in your computer, npm would have already been installed in your system. If you want to confirm that you have npm in your computer, enter the following command.</p><pre>node -v</pre><p>A version should appear in your terminal, if you already have one. You can also double check by using the following command as well.</p><pre>npm -v</pre><p>If a version number does not appear, you can install it using <a href="https://nodesource.com/blog/installing-node-js-tutorial-using-nvm-on-mac-os-x-and-ubuntu/">Node version manager</a>(nvm). The npm version you have can also be updated to the latest version, using the following command.</p><pre>npm install --global npm<br>//npm install -g npm <br>//the above line will also work;just a short form</pre><p>As the name indicates npm is a package manager and npm works with your JavaScript project directories via the command line, allowing you to install packages of preexisting code. You can install and use packages of varying size right from the smallest packages like <em>isNumber </em>to huge libraries and frameworks like <em>React</em> and <em>Express</em>.</p><h3>package.json</h3><p>The package.json file will tell us about all the packages required to run the JavaScript application listing out each package name. If you enter the following command inside a directory which has a file named package.json, it will install all the packages required to run that JavaScript application.</p><pre>npm install</pre><p>The package.json file is a key part of sharing JS code repositories on sites like GitHub. Instead of having to include all the dependencies&#39; code with every project, we just include a small file, listing out what npm needs to get for the project.The file also typically includes information about the project, such as the name, version, author and license.The package.json file is written in JSON, so like an object in JavaScript, it is always wrapped in curly braces, and includes keys and values.</p><p>Since npm relies on a package.json file, it has a built in command to <em>build</em> package.json files. Running the following command will begin a series of prompts, asking about specific content to include in the file. At the end, it will create a file or edit an existing package.json file.</p><pre>npm init</pre><p>That will be very useful if you are building a project from scratch. So far, npm has been the most useful tool for a beginner like me. Hope I have given my understanding of npm as short as possible. Happy coding!</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=e9e5ba45da72" width="1" height="1" alt=""><hr><p><a href="https://javascript.plainenglish.io/node-package-manager-e9e5ba45da72">Getting started with Node and npm</a> was originally published in <a href="https://javascript.plainenglish.io/">JavaScript in Plain English</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Collision Detection in Javascript]]></title>
            <link>https://medium.com/@hemalatha.psna/collision-detection-in-javascript-efafe8bba2c0?source=rss-5347d02b36e5------2</link>
            <guid isPermaLink="false">https://medium.com/p/efafe8bba2c0</guid>
            <category><![CDATA[2d-side-scroller]]></category>
            <category><![CDATA[collision-detection]]></category>
            <category><![CDATA[javascript]]></category>
            <dc:creator><![CDATA[Hemalatha M]]></dc:creator>
            <pubDate>Tue, 23 Apr 2019 06:05:44 GMT</pubDate>
            <atom:updated>2022-04-06T03:45:02.921Z</atom:updated>
            <content:encoded><![CDATA[<p>Collision detection also known as<em> </em><strong><em>hit testing </em></strong>is one of the most commonly and widely used terminology in web development to detect or sense tow hitting or colliding objects on screen. It is a broad topic and there is no single technique or theorem to include or render all types of collisions. The term collision detection is widely used in game programming, whereas hit testing is a terminology used in UI programming.</p><p>Remember the famous Mario or Castlevania game?!?!! The animated characters scroll on the screen and they pick up the items or they walk on the platform, jump and escape from the enemy.What must be happening behind the scenes?! Some event is triggered as a result of hitting or colliding of one object with another object on the screen. I have wondered, what is going on, under the hood, when I was a kid. While playing games those days , I never knew something called game development exists. The science behind that trigger is based on the Collision detection. Formulating the events and after effects of colliding objects play behind the scenes of such games. Sometimes this colliding not only implies when two objects on the screen collide, but also when an onscreen object collides with the edges or walls (like boundaries on the game window). And sometimes both the objects would be moving or one of them would be static and the other one would be a moving object.</p><p>There are some algorithms to detect collision in 2D games depending on the type of shapes that can collide (e.g. Rectangle to Rectangle, Rectangle to Circle, Circle to Circle). If the shape is not regular, then an entity like a rectangular box is considered as a hit box and the algorithm for rectangle to rectangle can be applied in such cases. Let us see an overview of the algorithms for all the three cases. I am going to walk through the steps that my team (Mark Pothecary , Cory Harper) and I used when we were working on a classroom project - 2D- side scroller game using pure Javascript. I had spent most of the time on Collision detection, which is the part that I was responsible for. It took almost two days for me integrate my file ‘<em>Collision.js’</em> with the file that had the canvas. The reason for that long time was because that the canvas coordinates were not conventional. Getting to the point, here are the general collision detection techniques followed in two dimensional game development and the one which which I used, in our game.</p><p><strong>Collision detection theorems :</strong></p><p>1. Axis Aligned Bounding Box (detects collision between two rectangles)</p><p>2. Separating Axis theorem (detects collision between two convex polygons)</p><p>3.Circle Collision( technique that detects collision between two circles)</p><p><strong>Axis-Aligned Bounding Box(AABB):</strong></p><p>This is the one that I used in our app. When objects are moving on the same plane without any rotation, then they are said to be <em>axis-aligned. </em>This algorithm is applied when two rectangular objects are colliding while they are axis aligned (no rotation). This algorithm is based on the gap between the moving objects. If there is a gap between the objects, then they are considered to be non-colliding, otherwise (no gap between the four sides of a rectangle) collision is said to occur. This is one of the simplest collision detection in game programming, since the rectangles are axis aligned. I used this technique to detect collision in our game because it was a 2D side scroller game with animated objects (of irregular geometry) moving across the screen.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*gy87mfYt11v1IXo5.jpg" /><figcaption>AABB algorithm for collision detection</figcaption></figure><p>If all of following are true than our first rectangle (A) is colliding with our second rectangle (B).</p><ul><li>A.X &lt; B.X + B.Width</li><li>A.X + A.Width &gt; B.X</li><li>A.Y &lt; B.Y + B.Height</li><li>A.Y + A.Height &gt; B.Y</li></ul><p>In the playableCharacter.js , I had let the character to save its position in an array, which was initialized as one of its properties in the class constructor. And rendered an update statement for that array in each and every movement function invoked inside of another function where we defined the event Listeners to make object move according to the user’s input. We had a class called staticObject which had two subclasses called the platform and items . If the object is an item, the characters health and points were calculated depending which item did it pick. If you notice the conditional statement, the conditions are slightly modified in accordance with the canvas’ coordinates. To incorporate the coordinates with the algorithm steps was a little tricky.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*rE1A8lCwPMfB-_Q6CbJDdA.png" /><figcaption>Collision detection function (using AABB theorem)</figcaption></figure><p><strong>Canvas Coordinate System:</strong></p><p>Let’s take a look at the canvas basics used in game programming. The canvas is a grid of pixels. When we use the canvas to draw 2d pictures, each pixel has a x and a y location that describes where it is on the canvas.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/534/0*0NZbbZd_zEPcB5zN.png" /><figcaption>Coordinate system of a canvas(HTML game element)</figcaption></figure><p>And finally, I could derive the conditions based on the canvas coordinate system , which has an inversing y axis to that of the conventional x-y coordinate system. The function shown in the code block above detects the collision perfectly as expected.</p><pre>if(((pleft &lt; pcright) &amp;&amp; (pright &gt; pcleft) &amp;&amp; (pbottom &gt; pctop) &amp;&amp; (ptop &lt; pcbottom)))<br>     {      <br>        collision = true; <br>      }</pre><p>I have used <em>pcleft, pcright, pctop, pctop</em> to represent the bounding box of the playable character. And <em>pleft, pright, ptop, pbottom</em> to represent the bounding box of the object. When called on an item (instance of Item class), it checks for the charcater’s collision with the item . When called on a platform, it checks for the character’s collision with the platform.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*h9uRshF-PR1r9HExQ4868g.png" /><figcaption>Invoking the collision detection function on platform and item</figcaption></figure><p>And finally, the collisionTestMethod was called on all of the platforms and all of the items generated so as to check for collision of the playableCharacter with all of the platforms and all of the items which were generated randomly on the canvas with the animation frame scrolling. This is done to check for collision with all if the platforms and all of the items appearing on the screen.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/926/1*08oO4WcPG97-9TjG2i6Yzg.png" /></figure><p>Working on collision detection was a real exploration. Once the techniques are known, it is so easy to detect the collision. Happy Game Coding!</p><p>References:</p><ul><li><a href="https://developer.mozilla.org/en-US/docs/Games/Techniques/2D_collision_detection">2D collision detection</a></li><li><a href="https://www.tandfonline.com/doi/abs/10.1080/10867651.1997.10487480">Efficient Collision Detection of Complex Deformable Models using AABB Trees</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=efafe8bba2c0" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Implementation of Poisson Disc Sampling in Javascript]]></title>
            <link>https://medium.com/@hemalatha.psna/implementation-of-poisson-disc-sampling-in-javascript-17665e406ce1?source=rss-5347d02b36e5------2</link>
            <guid isPermaLink="false">https://medium.com/p/17665e406ce1</guid>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Hemalatha M]]></dc:creator>
            <pubDate>Tue, 09 Apr 2019 18:03:31 GMT</pubDate>
            <atom:updated>2020-02-17T17:38:52.129Z</atom:updated>
            <content:encoded><![CDATA[<h3>Poisson Disc Sampling</h3><p>Imagine that you are playing a game and you are flying on a chopper across the amazon jungle. What would be your view? Or if you are playing age of empires. How are those trees uniformly spaced? When you see an animated furry animal, the hairs are uniformly spaced for your vision. How do they animate those trees or uniformly spaced objects using code? The most widely used solution is the “Poisson Disc Sampling” technique. Algorithms are a fascinating use case for visualization; And Visualization is more than a tool for finding patterns in data. It leverages the human visual system to augment human intellect! Light — electromagnetic radiation — the light emanating from this screen, traveling through the air, focused by your lens and projected onto the retina — is a continuous signal. To be perceived, we must reduce light to discrete impulses by measuring its intensity and frequency distribution at different points in space. This reduction process is called <em>sampling</em>, and it is essential to vision. It has recently been suggested that dyslexia may manifest as a deficit in the neural synchrony underlying language-based codes such that the phonological deficits apparent in dyslexia occur as a consequence of poor synchronization of oscillatory brain signals to the sounds of language. Visual coding of text requires large populations of neurons to be synchronizing and synthesizing information extremely quickly, over disparate cortical areas to form coherent percepts, in order for the eyes to recognize an object. Sampling is further a core concern of computer graphics; for example, to rasterize a 3D scene by raytracing, we must determine where to shoot rays. Even resizing an image requires sampling. The samples should be evenly distributed without any aliasing.</p><p>The human retina has a beautiful solution to sampling in its placement of photoreceptor cells. The cells cover the retina densely and evenly (with the exception of the blind spot over the optic nerve), and yet the cells’ relative positions are irregular. This is called a <strong>Poisson-disc distribution</strong> because it maintains a minimum distance between cells, avoiding occlusion and thus wasted photoreceptors. Nature is miraculous! To think of whats going inside our body and their functionalities is way complex than to add functionalities to our code.</p><p><strong>Poisson disc Sampling:</strong></p><p>In a Poisson disk sample set, no two samples are too close together. The closeness is defined by the Poisson disk <em>radius</em>, which is the half distance between the two closest samples. As compared to regular random sampling, Poisson disk sample sets provide a much more uniform sample distribution over the sampling domain. Beyond providing a nice distribution of sample points, Poisson disk sample sets also provide superior convergence properties with Monte Carlo sampling. The same number of Poisson disk samples typically produces lower noise, as compared to random sampling.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/870/1*V42bF9jHRbAaYm6OZAbBlw.png" /></figure><p><strong>Bridson’s algorithm for Poisson-disc sampling:</strong></p><p>Using <em>Pythagora’s theorem,</em><strong><em> s=r</em>/√2</strong>; where <strong>s</strong> is the side of the small pink colored square that you see on the picture and <strong>r</strong> is the radius of the circle. Our aim is to generate samples of the circle that we have, such that they don’t overlap with each other and are uniformly spaced. The distance and the dependency of each sample can be figured out. The following is the algorithm proposed by<em> Robert Bridson</em><strong>, </strong>called <strong>Fast Poisson Disk Sampling in Arbitrary Dimensions</strong>.The algorithm takes as input the extent of the sample domain in Rn, the minimum distance r between samples, and a constant k.</p><p><strong>Step 0</strong>. Initialize an n-dimensional background grid for storing samples and accelerating spatial searches. We pick the cell size to be bounded by r/√n, so that each grid cell will contain at most one sample, and thus the grid can be implemented as a simple n-dimensional array of integers: the default−1 indicates no sample, a non-negative integer gives the index of the sample located in a cell.</p><p><strong>Step 1</strong>. Select the initial sample, x0, randomly chosen uniformly from the domain. Insert it into the background grid, and initialize the “active list” (an array of sample indices) with this index (zero).</p><p><strong>Step 2</strong>. While the active list is not empty, choose a random index from it (say i). Generate up to k points chosen uniformly from the spherical annulus between radius r and 2r around xi.</p><p>For each point in turn, check if it is within distance r of existing samples (using the background grid to only test nearby samples). If a point is adequately far from existing samples, emit it as the next sample and add it to the active list. If after k attempts no such point is found, instead remove i from the active list.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*93EtzInFnl4hZNCeYoTEVg.png" /><figcaption>Comparison of Random samples Vs Poisson Disk Samples, generated using Bridson’s algorithm.</figcaption></figure><p><strong><em>Weighted Sample Elimination:</em></strong></p><p>Generating Poisson samples has been a real tough task because each sample is dependent on the position of other samples and hence the samples cannot be generated independently. Simple, yet computationally expensive algorithm to produce Poisson disc samples are available, like dart- throwing. On the other hand, computationally efficient algorithms are complex and limited to certain sampling domains. When I was looking upon the solutions and algorithms proposed by people. One of the efficient solutions available is <strong>Sample Elimination for Generating Poisson Disk Sample Sets algorithm </strong>by<strong> </strong>Cem Yuksel.</p><p>Weighted sample elimination is a simple algorithm for generating Poisson disk sample sets. One additional advantage of it is that it does not require specifying a Poisson disk radius property. It’s input is a collection of (randomly generated) samples and it <strong>eliminates</strong> a portion of these samples such that the resulting sample set has<em> Poisson disk property</em>. In other words, the weighted sample elimination algorithm receives a large set of input samples and it returns a smaller set of output samples. It does not generate new samples. It merely selects a subset from a given input set.</p><p>The input samples can be generated for any sampling domain in any dimensions. The more input samples you provide, the better quality Poisson disk sample set you get, though beyond a certain percentage you get diminishing returns. It is not a good idea to use a very small input sample set, regardless of the output sample set size. For example, if you would merely generate 10 samples, using 50 input samples may not provide a good input sample distribution. In this case, it would be a good idea to start with a much larger input sample set size.</p><p>The <em>Sample Elimination for Generating Poisson Disk Sample Sets algorithm </em>allows us to perform weighted sample elimination as a simple greedy algorithm for picking a subset with a reasonably large Poisson disk radius from a given set of input samples. We begin with assigning a weight to each sample based on its distance to its neighbors. At each step we eliminate the sample with the highest weight and adjust the weights of the remaining samples around it. Therefore, an efficient implementation of this algorithm merely needs two relatively common data structures: a spatial partitioning structure for quickly finding the neighboring samples and a priority queue for picking the sample with the highest weight. A kd- tree(an acronym used for k dimensional tree) is used and then a heap and with these two steps elimination of discs that do not have Poisson disc properties, result in the samples that we wanted. The following pseudocode proposed by Cem Yuksel can be used in any programming language of our choice to have Poisson samples. The following picture shows the differences between the Bridon’s algorithm and Cem’s algorithm, which shows the Poisson samples generated using them respectively. The results evident that the samples generated from the latter one are more gorgeous and more evenly distributed.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/468/0*jQTa0EyCldjQZlJ9" /><figcaption>The first bunny of both the above sets used Bridson’s algorithm and the others used Cem Yuksel’s algorithm.</figcaption></figure><p><strong>Psuedocode:</strong></p><pre>function WeightedSampleElim( samples )<br>     Build a kd-tree for samples <br>     Assign weights wi to each sample si <br>     Build a heap for si using weights wi <br>     while number of samples &gt; desired <br>         sj ← pull the top sample from heap <br>            for each sample si around sj <br>                 Remove wi j from wi <br>                 update the heap position of si</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/982/1*rKqoW3orFR8JiqdmnOnLAw.png" /><figcaption>A Sequence of tree leaves placed on the surfaces of the branches using weighted sample elimination by Cem Yuksel.</figcaption></figure><p><strong>References:</strong></p><ul><li><a href="http://www.cemyuksel.com/">Cem Yuksel</a></li><li><a href="https://www.jasondavies.com/poisson-disc/">Poisson-Disc Sampling</a></li></ul><p><a href="https://www.researchgate.net/publication/242093366_Fast_Poisson_disk_sampling_in_arbitrary_dimensions">https://www.researchgate.net/publication/242093366_Fast_Poisson_disk_sampling_in_arbitrary_dimensions</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=17665e406ce1" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Implementation of Huffman encoding]]></title>
            <link>https://medium.com/@hemalatha.psna/implementation-of-huffman-encoding-b19aa344cb65?source=rss-5347d02b36e5------2</link>
            <guid isPermaLink="false">https://medium.com/p/b19aa344cb65</guid>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Hemalatha M]]></dc:creator>
            <pubDate>Tue, 26 Mar 2019 16:06:07 GMT</pubDate>
            <atom:updated>2019-09-19T05:00:32.485Z</atom:updated>
            <content:encoded><![CDATA[<p>In olden days, reducing the size of the data during data transmission was a need to reduce the memory consumption. The hard disks were not greater than ten megabytes, a few decades back. These days the tiniest chips have giga bytes of memory. As the size of the hard disks started to grow, the memory required for the data we wanted to transmit kept increasing eventually! One technique to use our storage more optimally, is to compress the files. By taking advantage of redundancy or patterns, we may be able to “abbreviate” the contents in such a way to take up less space yet maintain the ability to reconstruct a full version of the original when needed. Such compression could be useful when trying to cram more things on a disk or to shorten the time needed to copy or send a file over a network.</p><p><strong>Data Compression:</strong></p><p><strong>Data compression</strong> is a reduction in the number of bits needed to represent <strong>data</strong>. <strong>Compressing data</strong> can save the storage capacity, speed up file transfer, and decrease costs for storage hardware and network bandwidth.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/577/0*K8Djji6NWXMR8IQF.png" /></figure><p>The most common compressed data forms that we would have come across include JPEG, MPEG or MP3, which are used for particular data file types. They tend to take advantage of known features of that type of data (such as the propensity for pixels in an image to be same or similar colors to their neighbors) to compress it. Other tools such as compress, zip, or pack and programs like StuffIt or ZipIt can be used to compress any sort of file. These algorithms have no a priori expectations and usually rely on studying the particular data file contents to find redundancy and patterns that allow for compression.Some of those techniques are lossy i.e., the decompressed data does not reproduce the data that we transmitted. the general structure would be maintained, while the minute details would be lost. For audio and video transmission such a loss is acceptable to a tiny extent. Whereas for text transmission, such a loss cannot be ignored or tolerated. We would be highly in need of a lossless compression during transmission.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/300/0*2KyAXXhdrjAvCbdc.jpg" /><figcaption>Looks smaller when compressed!</figcaption></figure><p><strong>Encoding:</strong></p><p>Encoding is the process of converting the data or a given sequence of characters, symbols, alphabets etc., into a specified format, for the secured transmission of data. In the receiver side, decoding is done to extract the information from the converted format. Various patterns of voltage or current levels to represent 1s and 0s of the digital signals on the transmission link.</p><p>Binary numbers can be readily encoded into numbers with a number base. For example: 2 in base 10 (the regular numbers we use) is 10 in binary. Encoding the characters into binary numbers takes an extra mile. The solution to represent characters using numbers is mapping a binary number to a character.</p><p>One could do it in an infinite number of ways. You could assign each letter, digit, and symbol to a number. You could decide to assign only the common letters, digit, and symbol to numbers and leave out the others. ASCII, UNICODE, EBCDIC, etc., are products of such mappings.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/636/0*BwWADiWcVG-20pWB.jpg" /><figcaption>Data encoded!</figcaption></figure><p>The encoding techniques are of two categories: Fixed length encoding and variable length encoding.</p><p><strong>Fixed-length encoding:</strong></p><p>In a <strong>fixed</strong>-length<strong> encoding</strong> scheme, each character is given a binary code with the same number of bits. — Example: Standard <strong>ASCII</strong> is a <strong>fixed length encoding</strong> scheme, where each character is <strong>encoded</strong> with 7 bits. This gives us 27 = 128 different codes for characters.</p><p><strong>ASCII encoding:</strong></p><p>It is one of the data encoding techniques. The standard ASCII character encoding uses the same amount of space (one byte or eight bits, where each bit is either a 0 or a 1) to store each character. A file of 1000 characters encoded using the ASCII scheme will take 1000 bytes (8000 bits); no more, no less, whether it be a file of 1000 spaces to a file containing 4 instances each of 250 different characters. A fixed-length encoding like ASCII is convenient because the boundaries between characters are easily determined and the pattern used for each character is completely fixed.</p><p><strong>Variable- length encoding:</strong></p><p>The variable encoding involves mapping the source symbols to a variable number of bits, allowing the sources to be compressed and decompressed with zero error (lossless data compression). Huffman encoding is one of the popular variable length encoding techniques , widely used.</p><p><strong>The Huffman Encoding :</strong></p><p>The Huffman encoding algorithm is an optimal compression algorithm when only the frequency of individual letters are used to compress the data. (There are better algorithms that can use more structure of the file than just letter frequencies.) The idea behind the algorithm is that if you have some letters that are more frequent than others, it makes sense to use fewer bits to encode those letters than to encode the less frequent letters. In addition, modern encoding schemes need to have a bit pattern for every possible letter. In order to account for foreign letters, some encoding schemes (i.e. Unicode, used by Java), uses 16 bits per character. Any given file or set of files is likely to use only a small subset of this set of 2¹⁶ characters. There are only 52 characters in the alphabet (counting lowercase and capital), 10 numbers (digits 0–9), and some small set of punctuation that is likely to be used. So the real number of characters used in a typical plain text file is closer to 75 than 256 (for 8-bit encoding) or 2¹⁶ (for 16-bit encoding).</p><p>Unlike <a href="https://www.webopedia.com/TERM/A/ASCII.html">ASCII</a> code, it assigns smaller codes for more frequently used characters and larger codes for less frequently used characters in order to reduce the size of files being compressed and transferred.</p><p>For example, in a file with the following data:</p><p>XXXXXXYYYYZZ</p><p>the frequency of “X” is 6, the frequency of “Y” is 4, and the frequency of “Z” is 2. If each character is represented using a fixed-length code of two bits, then the number of bits required to store this file would be 24, i.e., (2 x 6) + (2x 4) + (2x 2) = 24.</p><p>If the above data were compressed using Huffman compression, the more frequently occurring numbers would be represented by smaller bits, such as:</p><p>X by the code 0 (1 bit)<br>Y by the code 10 (2 bits)<br>Z by the code 11 (2 bits)</p><p>therefore the size of the file becomes 18, i.e., (1x 6) + (2 x 4) + (2 x 2) = 18.</p><p>In the above example, more frequently occurring characters are assigned smaller codes, resulting in a smaller number of bits in the final compressed file.</p><p><strong>Greedy Algorithms:</strong></p><p>In general, greedy algorithms use small-grained, or local minimal/maximal choices to result in a global minimum/maximum. Making change using U.S. money is another example of a greedy algorithm.</p><ul><li>Problem: give change in U.S. coins for any amount (say under $1.00) using the minimal number of coins.</li><li>Solution (assuming coin denominations of $0.25, $0.10, $0.05, and $0.01, called quarters, dimes, nickels, and pennies, respectively): use the highest-value coin that you can, and give as many of these as you can. Repeat the process until the correct change is given.</li><li>Example: make change for $0.91. Use 3 quarters (the highest coin we can use, and as many as we can use). This leaves $0.16. To make change use a dime (leaving $0.06), a nickel (leaving $0.01), and a penny. The total change for $0.91 is three quarters, a dime, a nickel, and a penny. This is a total of six coins, it is not possible to make change for $0.91 using fewer coins.</li></ul><p>The solution/algorithm is greedy because the largest denomination coin is chosen to use at each step, and as many are used as possible. This locally optimal step leads to a globally optimal solution. Note that the algorithm <strong>does not work with different denominations</strong>. For example, if there are no nickels, the algorithm will make change for $0.31 using one quarter and six pennies, a total of seven coins. However, it’s possible to use three dimes and one penny, a total of four coins. This shows that greedy algorithms are not always optimal algorithms.</p><p><strong>Why Huffman’s algorithm is considered greedy?</strong></p><p>Huffman’s algorithm is an example of a greedy algorithm. In general, greedy algorithms use small-grained, or local minimal/maximal choices in attempt to result in a global minimum/maximum. At each step, the algorithm makes the near choice that appears to lead toward the goal in the long-term. In Huffman’s case, the insight for its strategy is that combining the two smallest nodes makes both of those character encodings one bit longer (because of the added parent node above them) but given these are the most rare characters, it is a better choice to assign them longer bit patterns than the more frequent characters. The Huffman strategy does, in fact, lead to an overall optimal character encoding. Even when a greedy strategy may not result in the overall best result, it still can be used to approximate when the optimal solution requires an exhaustive or expensive traversal. In a time or space-constrained situation, we might be willing to accept the quick and easy-to-find greedy solution as an approximation.</p><p>In this algorithm, a variable-length code is assigned to input different characters. The code length is related to how frequently characters are used. Most frequent characters have the smallest codes and longer codes for least frequent characters.</p><p><strong>The Huffman Encoding Process:</strong></p><p><em>What’s the smallest number of bits (hence the minimum size of file) we can use to store an arbitrary piece of text?</em></p><p>Huffman’s scheme uses a table of frequency of occurrence for each symbol (or character) in the input. This table may be derived from the input itself or from data which is representative of the input. For instance, the frequency of occurrence of letters in normal English might be derived from processing a large number of text documents and then used for encoding all text documents. We then need to assign a variable-length bit string to each character that unambiguously represents that character. This means that the encoding for each character must have a unique prefix. If the characters to be encoded are arranged in a binary tree:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/231/0*eG96S6uvEZgPGewI.gif" /></figure><p>Encoding tree for ETASNOAn encoding for each character is found by following the tree from the route to the character in the leaf: the encoding is the string of symbols on each branch followed.</p><p>For example:</p><pre>String   Encoding<br>    TEA    10 00 010<br>    SEA    011 00 010<br>    TEN    10 00 110</pre><ul><li>As desired, the highest frequency letters — E and T — have two digit encodings, whereas all the others have three digit encodings.</li><li>Encoding would be done with a lookup table.</li></ul><p>A divide-and-conquer approach might have us asking which characters should appear in the left and right subtrees and trying to build the tree from the top down. As with the optimal binary search tree, this will lead to to an exponential time algorithm.</p><p>A greedy approach places our <strong>n</strong> characters in <strong>n</strong> sub-trees and starts by combining the two least weight nodes into a tree which is assigned the sum of the two leaf node weights as the weight for its root node.</p><p>The time complexity of the Huffman algorithm is <strong>O(nlogn)</strong>. Using a heap to store the weight of each tree, each iteration requires <strong>O(logn)</strong> time to determine the cheapest weight and insert the new weight. There are <strong>O(n)</strong>iterations, one for each item.</p><p><strong>Decoding Huffman Encoded data:</strong></p><p>Curious readers are, of course, now asking <em>“How do we </em><strong>decode</strong><em> a Huffman-encoded bit string? With these variable length strings, it’s not possible to break up an encoded string of bits into characters!”</em></p><p>The decoding procedure is deceptively simple. Starting with the first bit in the stream, one then uses successive bits from the stream to determine whether to go left or right in the decoding tree. When we reach a leaf of the tree, we’ve decoded a character, so we place that character onto the (uncompressed) output stream. The next bit in the input stream is the first bit of the next character.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/301/0*gmS7JVJOH16HNNZh.gif" /></figure><p><strong>Transmission and storage of Huffman encoded data:</strong></p><p>If your system is continually dealing with data in which the symbols have similar frequencies of occurrence, then both encoders and decoders can use a standard encoding table/decoding tree. However, even text data from various sources will have quite different characteristics. For example, ordinary English text will have generally have ‘e’ at the root of the tree, with short encodings for ‘a’ and ‘t’, whereas C programs would generally have ‘;’ at the root, with short encodings for other punctuation marks such as ‘(‘ and ‘)’ (depending on the number and length of comments!). If the data has variable frequencies, then, for optimal encoding, we have to generate an encoding tree for each data set and store or transmit the encoding with the data. The extra cost of transmitting the encoding tree means that we will not gain an overall benefit unless the data stream to be encoded is quite long — so that the savings through compression more than compensate for the cost of the transmitting the encoding tree also.</p><p><strong>Example of Huffman encoding with the tree:</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/746/1*nrt8NVY9NXoMuLKAYDTPaw.png" /></figure><p>Thus using Huffman encoding technique , we can achieve a lossless data compression of nearly 80% . In the above example, the 11 bytes input data is compressed into just 3 bytes.</p><p><strong>Implementation/Programming of Huffman coding:</strong></p><p>The Huffman encoding can be implemented in the same way in any programming language using the two main steps. A compression program and a decompression program. You need both to have a useful compression utility. We’ll assume these are separate programs, but they share many classes, functions, modules, code or whatever unit-of-programming you’re using. We’ll call the program that reads a regular file and produces a compressed file the <em>compression</em> or <em>huffing</em> program. The program that does the reverse, producing a regular file from a compressed file, will be called the de<em>compression</em> or <em>unhuffing</em> program. .The pseudocode for the implementation is as follows.</p><p><strong>Pseudocode:</strong></p><p>0. Determine the count of each symbol in the input message.</p><p>1. Create a forest of single-node trees. Each node in the initial forest represents a symbol from the set of possible symbols, and contains the count of that symbol in the message to be coded. Symbols with a count of zero are ignored (consider them to be impossible).</p><p>2. Loop while there is more than 1 tree in the forest:</p><p>2a. Remove the two trees from the forest that have the lowest count contained in their roots.</p><p>2b. Create a new node that will be the root of a new tree. This new tree will have those two trees just removed in step 2a as left and right subtrees. The count in the root of this new tree will be the sum of the counts in the roots of its subtrees. Label the edge from this new root to its left subtree “1”, and label the edge to its right subtree “0”.</p><p>2c. Insert this new tree in the forest, and go to 2.</p><p>3. Return the one tree in the forest as the Huffman code tree.</p><p><strong>References:</strong></p><ul><li><a href="https://web.stanford.edu/class/archive/cs/cs106b/cs106b.1126/handouts/220%20Huffman%20Encoding.pdf">https://web.stanford.edu/class/archive/cs/cs106b/cs106b.1126/handouts/220%20Huffman%20Encoding.pdf</a></li><li><a href="https://www.geeksforgeeks.org/huffman-coding-greedy-algo-3/">https://www.geeksforgeeks.org/huffman-coding-greedy-algo-3/</a></li><li><a href="https://www.dspguide.com/ch27/3.htm">https://www.dspguide.com/ch27/3.htm</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b19aa344cb65" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>