Run-length encoding: Difference between revisions

{{Wikipedia|Run-length_encoding}}

{{task|Compression}}

 

 

 

: Input: <code>WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW</code>

: Output: <code>12W1B12W3B24W1B14W</code>

 

Note: the encoding step in the above example is the same as a step of the [[Look-and-say sequence]].

 

=={{header|Ada}}==

with Ada.Strings.Fixed; use Ada.Strings.Fixed;

procedure Test_Run_Length_Encoding is

Put_Line (Encode ("WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW"));

Put_Line (Decode ("12W1B12W3B24W1B14W"));

Sample output:

<pre>

 

Note: The following uses iterators, eliminating the need of declaring arbitrarily large CHAR arrays for caching.

STRING output := "12W1B12W3B24W1B14W";

 

print(c)

# OD # );

Output:

<pre>

Encode input: 12W1B12W3B24W1B14W

Decode output: WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

</pre>

 

=={{header|APL}}==

[1] count←∣2-/((1,(2≠/rll),1)×⍳1+⍴rll)~0

[2] ret←(⍕count,¨(1,2≠/rll)/rll)~' '

∇

Sample Output:

<pre>

12W1B12W3B24W1B14W

</pre>

 

=={{header|AutoHotkey}}==

MsgBox % rle_decode(key)

 

}

Return output

 

=={{header|AWK}}==

'''Encoding'''

 

FS=""

}

}

printf("%d%c", j, cp)

 

'''Decoding'''

 

RS="[0-9]+[^0-9]"

final = "";

END {

print final

 

=={{header|BASIC}}==

{{trans|PowerBASIC}}

 

DECLARE FUNCTION RLEncode$ (i AS STRING)

 

outP = outP + tmp2

RLEncode$ = outP

 

Sample output (last one shows errors from using numbers in input string):

111r

rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr

 

=={{header|BBC BASIC}}==

The run counts are indicated by means of character codes in the range 131 to 255.

PRINT "Input: " input$

rle$ = FNencodeRLE(input$)

ENDIF

ENDWHILE

 

=={{header|Bracmat}}==

= character otherCharacter acc begin end

. :?acc

)

& run-length$WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

<pre> 12W1B12W3B24W1B14W</pre>

 

=={{header|Burlesque}}==

"WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW"

=[{^^[~\/L[Sh}\m

 

=={{header|C}}==

Encoder that can deal with byte streams. Can encode/decode any byte values and any length with reasonable efficiency. Also showing OO and polymophism with structs.

#include <stdlib.h>

 

typedef struct stream_t stream_t, *stream;

struct stream_t {

or -1 to signify end of input */

int (*get)(stream);

 

return 0;

 

See [[Run-length encoding/C]]

 

 

 

 

 

 

 

This example only works if there are no digits in the string to be encoded and then decoded.

 

{

string input = "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW";

}

return sb.ToString();

Somewhat shorter, using Regex.Replace with MatchEvaluator (using C#2 syntax only):

using System.Text.RegularExpressions;

 

});

}

 

=={{header|Clojure}}==

(->> (partition-by identity s) (mapcat (juxt count first)) (apply str)))

 

(->> (re-seq #"(\d+)([A-Z])" s)

(mapcat (fn [[_ n ch]] (repeat (Integer/parseInt n) ch)))

 

=={{header|CoffeeScript}}==

 

str.replace /(.)\1*/g, (w) ->

w[0] + w.length

console.log s = "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW"

console.log encode s

 

<pre>

The following version encodes the number of ocurrences as an unicode character. You can change the way it looks by rotating the offset.

 

str.replace /(.)\1*/g, (w) ->

w[0] + String.fromCharCode(offset+w.length)

str.split('').map((w,i) ->

if not (i%2) then w else new Array(+w.charCodeAt(0)-offset).join(str[i-1])

 

<pre>

 

=={{header|Common Lisp}}==

(loop for x in (rest sequence)

with temp = (subseq sequence 0 1)

 

(run-length-encode "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW")

 

=={{header|D}}==

===Short Functional Version===

 

alias encode = group;

"WWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW";

assert(s.encode.decode.equal(s));

 

===Basic Imperative Version===

 

// Similar to the 'look and say' function.

char last = input[$ - 1];

string output;

int count;

 

if (c == last) {

count++;

} else {

count = 1;

last = c;

}

 

}

 

string i, result;

 

switch (c) {

case '0': .. case '9':

throw new Exception("Can not repeat a letter " ~

"without a number of repetitions");

i.length = 0;

break;

default:

}

 

"WWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW";

writeln("Input: ", txt);

writeln("Encoded: ", encoded);

{{out}}

<pre>Input: WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

Encoded: 12W1B12W3B24W1B14W</pre>

===UTF String Version===

D's native string is utf-encoded. This version works for utf string, and uses a [[Variable-length_quantity|Variable-length Quantity]] [[Variable-length_quantity#D|module]].

 

import vlq;

 

auto sEncoded = RLE.init.encode(s).encoded ;

assert(s == RLE(sEncoded).decode(), "Not work");

 

output from "display.txt":

 

The code looks more complex than the third Python version because this also handles digits by escaping them with #.

std.algorithm;

 

"11#222##333";

assert(s == reDecode(reEncode(s)));

 

=={{header|E}}==

 

var seen := null

var count := 0

}

return result

 

# value: [[12, 'W'], [1, 'B'], [12, 'W'], [3, 'B'], [24, 'W'], [1, 'B'], [14, 'W']]

 

? unrle(rle("WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW"))

 

=={{header|Erlang}}==

A single-threaded/process version with a simple set of unit test.

 

 

-export([encode/1,decode/1]).

?_assert(decode(Expected) =:= PreEncoded),

?_assert(decode(encode(PreEncoded)) =:= PreEncoded)

 

=={{header|Euphoria}}==

 

function encode(sequence s)

pretty_print(1,s,{3})

puts(1,'\n')

 

Output:

 

=={{header|F Sharp|F#}}==

open System

open System.Text.RegularExpressions

|> List.map (fun m -> Int32.Parse(m.Groups.[1].Value), m.Groups.[2].Value)

|> List.fold (fun acc (len, s) -> acc + String.replicate len s) ""

 

=={{header|FALSE}}==

 

=={{header|Fan}}==

** Generates a run-length encoding for a string

**

 

override Str toStr() { return "${count}${char.toChar}" }

 

=={{header|Forth}}==

: n>a (.) tuck a @ swap move a +! ;

: >a a @ c! 1 a +! ;

i c@ digit? if 10 * i c@ [char] 0 - + else

a @ over i c@ fill a +! 0 then

 

Example:

 

here 1000 + encode here 2000 + decode cr 3 spaces type

 

=={{header|Fortran}}==

{{works with|Fortran|95 and later}}

implicit none

 

integer, parameter :: bufsize = 100 ! Sets maximum size of coded and decoded strings, adjust as necessary

call Encode(teststr, codedstr)

end do

end subroutine

=={{header|Go}}==

Decoder kind of necessary to demonstrate task requirement that I can recreate the input.

 

import "fmt"

}

return string(d)

Output:

<pre>

 

=={{header|Groovy}}==

def encoded = new StringBuilder()

(text =~ /(([A-Z])\2*)/).each { matcher ->

}

decoded.toString()

Test code

def rleEncoded = rleEncode(text)

assert rleEncoded == '12W1B12W3B24W1B14W'

 

println "Original Text: $text"

Output:

<pre>Original Text: WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

 

=={{header|Haskell}}==

 

-- Datatypes

type Decoded = String

 

-- Takes a decoded string and returns an encoded list of tuples

rlencode :: Decoded -> Encoded

 

-- Takes an encoded list of tuples and returns the associated decoded String

rldecode :: Encoded -> Decoded

 

main :: IO ()

main = do

decoded = rldecode encoded

 

=={{header|Icon}} and {{header|Unicon}}==

 

s := "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW"

procedure Repl(n, c)

return repl(c,n)

 

Sample output:

=={{header|J}}==

'''Solution:'''

 

'''Example:'''

12W1B12W3B24W1B14W

 

rld '12W1B12W3B24W1B14W'

 

Note that this implementation fails for the empty case. Here's a version that fixes that:

 

 

Other approaches include using <nowiki>rle ::(''"_)</nowiki> or <nowiki>rle^:(*@#)</nowiki> or equivalent variations on the original sentence.

 

=={{header|Java}}==

import java.util.regex.Pattern;

public class RunLengthEncoding {

System.out.println(decode("1W1B1W1B1W1B1W1B1W1B1W1B1W1B"));

}

Tests:

 

{{libheader|JUnit}}

 

import org.junit.Test;

 

}

 

=={{header|JavaScript}}==

Here's an encoding method that walks the input string character by character

var encoding = [];

var prev, count, i;

encoding.push([count, prev]);

return encoding;

 

Here's an encoding method that uses a regular expression to grab the character runs ({{works with|JavaScript|1.6}} for the <code>forEach</code> method)

var encoding = [];

input.match(/(.)\1*/g).forEach(function(substr){ encoding.push([substr.length, substr[0]]) });

return encoding;

 

And to decode (see [[Repeating a string#JavaScript|Repeating a string]])

var output = "";

encoded.forEach(function(pair){ output += new Array(1+pair[0]).join(pair[1]) })

return output;

 

 

 

 

{{trans|J}}

 

 

'''Example:'''

 

"12W1B12W3B24W1B14W"

rld "12W1B12W3B24W1B14W"

 

=={{header|Liberty BASIC}}==

 

'In$ ="aaaaaaaaaaaaaaaaaccbbbbbbbbbbbbbbba" ' testing...

next i

Decoded$ =r$

 

=={{header|Logo}}==

if empty? :str [output (word :out :count :last)]

if equal? first :str :last [output (encode bf :str :out :count+1 :last)]

make "foo "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

make "rle encode :foo

 

=={{header|Lua}}==

 

astable = Ct(C(1)^0)

 

end

return ret

 

 

 

=={{header|Maxima}}==

[n: slength(a), b: "", c: charat(a, 1), k: 1],

for i from 2 thru n do

sconcat(b, k, c)

)$

 

rle("WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW");

 

=={{header|MMIX}}==

GREG @

Buf OCTA 0,0,0,0 integer print buffer

2H SET $4,#a print NL

GO $127,PChar

Example run encode --> decode:

<pre>~/MIX/MMIX/Rosetta> mmix rle

12W1B12W3B24W1B14W

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW</pre>

 

=={{header|Objective-C}}==

 

=={{header|OCaml}}==

let len = String.length str in

let rec aux i acc =

let decode lst =

let l = List.map (fun (c,n) -> String.make n c) lst in

 

let e = encode "aaaaahhhhhhmmmmmmmuiiiiiiiaaaaaa" in

List.iter (fun (c,n) ->

) e;

print_endline (decode [('a', 5); ('h', 6); ('m', 7); ('u', 1); ('i', 7); ('a', 6)]);

 

;Using regular expressions

 

open Str

let () =

print_endline (encode "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW");

 

=={{header|Oz}}==

fun {RLEncode Xs}

for G in {Group Xs} collect:C do

{System.showInfo Data}

{Show Enc}

=={{header|PARI/GP}}==

if(s=="", return(s));

my(v=Vec(s),cur=v[1],ct=1,out="");

};

rle("WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW")

Output:

<pre>%1 = "12W1B12W3B24W1B14W"

 

=={{header|Pascal}}==

procedure encode(s: string; var counts: array of integer; var letters: string);

decode(s, counts, letters);

writeln(s);

Output:

<pre>:> ./RunLengthEncoding

 

=={{header|Perl}}==

 

sub decode {

 

 

 

 

 

 

 

 

 

 

=={{header|PHP}}==

}

 

}

 

 

=={{header|PicoLisp}}==

(pack

(make

(prinl "Data: " "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW")

(prinl "Encoded: " (encode @))

Output:

<pre>Data: WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

 

=={{header|PL/I}}==

declare run_length fixed binary;

declare input file;

end;

put edit ((c do i = 1 to run_length)) (a);

 

=={{header|PowerBASIC}}==

This version can handle any arbitrary string that doesn't contain numbers (not just letters). (A flag value could be added which would allow the inclusion of ''any'' character, but such a flag isn't in this example.)

 

DIM Loop0 AS LONG, rCount AS STRING, outP AS STRING, m AS STRING

 

'in PB/Win, "?" = MSGBOX; in PB/DOS & PB/CC. "?" = PRINT

? initial & $CRLF & encoded & $CRLF & decoded

 

Outputs are similar to those in [[#BASIC|BASIC]], above.

 

=={{header|PowerShell}}==

$re = [regex] '(.)\1*'

$ret = ""

}

return $ret

Output:

<pre>PS> Compress-RLE "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW"

PS> Expand-RLE "12W1B12W3B24W1B14W"

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW</pre>

=={{header|Prolog}}==

Works with SWI-Prolog.<br>

This code is inspired from a code found here : http://groups.google.com/group/comp.lang.prolog/browse_thread/thread/b053ea2512e8b350 (author : Pascal J. Bourguignon).

run_length :-

L = "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW",

 

run(Var,[Other|RRest], [1,Var],[Other|RRest]):-

Output :

<pre> ?- run_length.

 

=={{header|Pure}}==

 

encode s = strcat $ map (sprintf "%d%s") $ encode $ chars s with

let s = "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW";

let r = encode s; // "12W1B12W3B24W1B14W"

 

=={{header|PureBasic}}==

{{trans|PowerBasic}} with some optimations to use pointers instead of string functions. According to the task description it works with uppercase A - Z. In this implementation it also functions with all characters that are non-digits and whose value is non-zero.

Protected.s repCount, output, currChar, tmp

Protected *c.Character = @toDecode

Input()

CloseConsole()

Sample output:

<pre>Type something: WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWW

 

=={{header|Python}}==

count = 1

lst = []

for character in input_string:

if character != prev:

if prev:

lst.append(entry)

count = 1

prev = character

count += 1

else:

def decode(lst):

for character, count in lst:

#Method call

 

Functional

{{works with|Python|2.4}}

def encode(input_string):

return [(len(list(g)), k) for k,g in groupby(input_string)]

 

encode("aaaaahhhhhhmmmmmmmuiiiiiiiaaaaaa")

 

<br>'''By regular expression'''<br>

The simplified input range of only uppercase characters allows a simple regular expression to be applied repeatedly for encoding, and another for decoding:

 

def encode(text):

 

textin = "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW"

 

=={{header|R}}==

R has a built-in function, rle, for run length encoding. This modification allows input and output in the forms specified above.

{

splitx <- unlist(strsplit(input, ""))

 

input <- "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW"

Similarly, inverse.rle provides decompression after a run length encoding.

{

lengths <- as.numeric(unlist(strsplit(output, "[[:alpha:]]")))

 

output <- "12W1B12W3B24W1B14W"

 

=={{header|Racket}}==

 

#lang racket

(define (encode str)

(define (decode str)

(regexp-replace* #px"([0-9]+)(.)" str (λ (m n c) (make-string (string->number n) (string-ref c 0)))))

 

=={{header|REXX}}==

 

 

 

</pre>

 

 

 

</pre>

 

=={{header|Ruby}}==

string.scan(/(.)(\1*)/).collect do |char, repeat|

[1 + repeat.length, char]

def decode(string)

string.scan(/(\d+)(\D)/).collect {|length, char| char * length.to_i}.join

 

This usage also seems to be idiomatic, and perhaps less cryptic:

string.scan(/(.)(\1*)/).inject("") do |encoding, (char, repeat)|

encoding << (1 + repeat.length).to_s << char

decoding << char * length.to_i

end

 

<br>'''By regular expression'''<br>

The simplified input range of only uppercase characters allows a simple regular expression to be applied repeatedly for encoding, and another for decoding:

str.gsub(/(.)\1*/) {$&.length.to_s + $1}

end

def decode(str)

str.gsub(/(\d+)(\D)/) {$2 * $1.to_i}

 

'''Test:'''

p enc = encode(orig)

p dec = decode(enc)

 

{{out}}

 

=={{header|Run BASIC}}==

beg = 1

i = 1

beg = i

if i < len(press$) then goto [expand]

<pre>Compressed:12W1B12W3B24W1B14W

Expanded:WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW</pre>

 

=={{header|Scala}}==

Care is taken to use StringBuilder for performance reasons.

 

case ((len, c, sb), index) if c != s(index) => sb.append(len); sb.append(c); (1, s(index), sb)

case ((len, c, sb), _) => (len + 1, c, sb)

for (Code(len, c) <- Code findAllIn s) sb.append(c * len.toInt)

sb.toString

 

A simpler (?) encoder:

s.foldLeft((0,s(0),""))( (t,c) => t match {case (i,p,s) => if (p==c) (i+1,p,s) else (1,c,s+i+p)})

match {case (i,p,s) => s+i+p}

 

To make it faster (it's also faster than the longer implementation above) just replace '''""''' with '''new StringBuilder''' and '''s+i+p''' with '''{s.append(i);s.append(p)}'''