Run Length Encoding in Python
Given an input string, write a function that returns the Run Length Encoded string for the input string. For example, if the input string is ‘wwwwaaadexxxxxx’, then the function should return ‘w4a3d1e1x6’.
Examples:
Input : str = 'wwwwaaadexxxxxx' Output : 'w4a3d1e1x6'
This problem has existing solution please refer Run Length Encoding link. Here we will solve this problem quickly in python using OrderedDict. Approach is very simple, first we create a ordered dictionary which contains characters of input string as key and 0 as their default value, now we run a loop to count frequency of each character and will map it to it’s corresponding key.
Implementation:
Python3
<div id = "highlighter_850800" class = "syntaxhighlighter nogutter " ><table border = "0" cellpadding = "0" cellspacing = "0" ><tbody><tr><td class = "code" ><div class = "container" ><div class = "line number1 index0 alt2" ><code class = "comments" > # Python code for run length encoding</code></div><div class="line number2 index1 alt1"><code class="keyword">from</code> <code class="plain">collections </code><code class="keyword">import</code> <code class="plain">OrderedDict</code></div><div class="line number3 index2 alt2"><code class="keyword">def</code> <code class="plain">runLengthEncoding(</code><code class="functions">input</code><code class="plain">):</code></div><div class="line number4 index3 alt1"> </div><div class="line number5 index4 alt2"><code class="undefined spaces"> </code><code class="comments"># Generate ordered dictionary of all lower</code></div><div class="line number6 index5 alt1"><code class="undefined spaces"> </code><code class="comments"># case alphabets, its output will be</code></div><div class="line number7 index6 alt2"><code class="undefined spaces"> </code><code class="comments"># dict = {'w':0, 'a':0, 'd':0, 'e':0, 'x':0}</code></div><div class="line number8 index7 alt1"><code class="undefined spaces"> </code><code class="functions">dict</code><code class="keyword">=</code><code class="plain">OrderedDict.fromkeys(</code><code class="functions">input</code><code class="plain">, </code><code class="value">0</code><code class="plain">)</code></div><div class="line number9 index8 alt2"> </div><div class="line number10 index9 alt1"><code class="undefined spaces"> </code><code class="comments"># Now iterate through input string to calculate</code></div><div class="line number11 index10 alt2"><code class="undefined spaces"> </code><code class="comments"># frequency of each character, its output will be</code></div><div class="line number12 index11 alt1"><code class="undefined spaces"> </code><code class="comments"># dict = {'w':4,'a':3,'d':1,'e':1,'x':6}</code></div><div class="line number13 index12 alt2"><code class="undefined spaces"> </code><code class="keyword">for</code> <code class="plain">ch </code><code class="keyword">in</code> <code class="functions">input</code><code class="plain">:</code></div><div class="line number14 index13 alt1"><code class="undefined spaces"> </code><code class="functions">dict</code><code class="plain">[ch] </code><code class="keyword">+</code><code class="keyword">=</code> <code class="value">1</code></div><div class="line number15 index14 alt2"> </div><div class="line number16 index15 alt1"><code class="undefined spaces"> </code><code class="comments"># now iterate through dictionary to make</code></div><div class="line number17 index16 alt2"><code class="undefined spaces"> </code><code class="comments"># output string from (key,value) pairs</code></div><div class="line number18 index17 alt1"><code class="undefined spaces"> </code><code class="plain">output </code><code class="keyword">=</code> <code class="plain">''</code></div><div class="line number19 index18 alt2"><code class="undefined spaces"> </code><code class="keyword">for</code> <code class="plain">key,value </code><code class="keyword">in</code> <code class="functions">dict</code><code class="plain">.items():</code></div><div class="line number20 index19 alt1"><code class="undefined spaces"> </code><code class="plain">output </code><code class="keyword">=</code> <code class="plain">output </code><code class="keyword">+</code> <code class="plain">key </code><code class="keyword">+</code> <code class="functions">str</code><code class="plain">(value)</code></div><div class="line number21 index20 alt2"><code class="undefined spaces"> </code><code class="keyword">return</code> <code class="plain">output</code></div><div class="line number22 index21 alt1"> </div><div class="line number23 index22 alt2"><code class="comments"># Driver function</code></div><div class="line number24 index23 alt1"><code class="keyword">if</code> <code class="plain">__name__ </code><code class="keyword">=</code><code class="keyword">=</code> <code class="string">"__main__"</code><code class="plain">:</code></div><div class="line number25 index24 alt2"><code class="undefined spaces"> </code><code class="functions">input</code><code class="keyword">=</code><code class="string">"wwwwaaadexxxxxx"</code></div><div class="line number26 index25 alt1"><code class="undefined spaces"> </code><code class="functions">print</code> <code class="plain">(runLengthEncoding(</code><code class="functions">input</code><code class="plain">))</code></div></div></td></tr></tbody></table></div> |
Output
w4a3d1e1x6
Another code:
Python3
def encode(message): encoded_message = "" i = 0 while (i < = len (message) - 1 ): count = 1 ch = message[i] j = i while (j < len (message) - 1 ): if (message[j] = = message[j + 1 ]): count = count + 1 j = j + 1 else : break encoded_message = encoded_message + str (count) + ch i = j + 1 return encoded_message #Provide different values for message and test your program encoded_message = encode( "ABBBBCCCCCCCCAB" ) print (encoded_message) |
Output
1A4B8C1A1B