Run-length encoding: Difference between revisions
Content added Content deleted
(Rescued TMG entry.) |
|||
Line 4,157: | Line 4,157: | ||
echo decode('12W1B12W3B24W1B14W'), PHP_EOL; |
echo decode('12W1B12W3B24W1B14W'), PHP_EOL; |
||
?></lang> |
?></lang> |
||
=={{header|Picat}}== |
|||
Three different approaches: |
|||
* plain while loop: rle/1 |
|||
* using positions of different chars: rle2/1 |
|||
* recursion: rle3/1 |
|||
Encode and decode (only using rle3/1): |
|||
<lang Picat> |
|||
go => |
|||
S = "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWWA", |
|||
println(S), |
|||
RLE = rle3(S), |
|||
println(rle=RLE), |
|||
D = rl_decode(RLE), |
|||
println(D), |
|||
if D == S then |
|||
println(ok) |
|||
else |
|||
println(not_ok) |
|||
end, |
|||
nl. |
|||
% |
|||
% While loop. Quite slow. |
|||
% |
|||
rle(S) = RLE => |
|||
RLE = "", |
|||
Char = S[1], |
|||
I = 2, |
|||
Count = 1, |
|||
while (I <= S.len) |
|||
if Char == S[I] then |
|||
Count := Count + 1 |
|||
else |
|||
RLE := RLE ++ Count.to_string() ++ Char.to_string(), |
|||
Count := 1, |
|||
Char := S[I] |
|||
end, |
|||
I := I + 1 |
|||
end, |
|||
RLE := RLE ++ Count.to_string() ++ Char.to_string(). |
|||
% |
|||
% Using positions of different chars. Much faster than rle/1. |
|||
% |
|||
rle2(S) = RLE => |
|||
Ix = [1] ++ [I : I in 2..S.len, S[I] != S[I-1]] ++ [S.len+1], |
|||
Diffs = diff(Ix), |
|||
RLE = [Diffs[I].to_string() ++ S[Ix[I]].to_string() : I in 1..Diffs.len].join(''). |
|||
% Recursive approach. The fastest version. |
|||
rle3(S) = RLE => |
|||
rle3(S.tail(),S[1],1,[],RLE). |
|||
rle3([],LastChar,Count,RLE1,RLE) => |
|||
RLE = (RLE1 ++ [Count.to_string(),LastChar.to_string()]).join(''). |
|||
rle3([C|T],LastChar,Count,RLE1,RLE) => |
|||
C == LastChar -> |
|||
rle3(T,C,Count+1,RLE1,RLE) |
|||
; |
|||
rle3(T,C,1,RLE1++[Count.to_string()++LastChar.to_string()],RLE).</lang> |
|||
{{out}} |
|||
<pre>WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWWA |
|||
rle = 12W1B12W3B24W1B14W1A |
|||
WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWWA |
|||
ok |
|||
</pre> |
|||
Benchmark on a larger string (30_000) clearly shows that rle3/1 is the fastest. |
|||
<lang Picat>% Benchmark on larger strings |
|||
go2 => |
|||
_ = random2(), |
|||
Alpha = "AB", |
|||
Len2 = Alpha.len, |
|||
_ = random2(), |
|||
S = [Alpha[random(1,Len2)] : _ in 1..30_000], |
|||
if S.len < 200 then println(s=S) end , |
|||
println("rle/1:"), |
|||
time(_=rle(S)), |
|||
println("rle2/1:"), |
|||
time(_=rle2(S)), |
|||
println("rle3/1:"), |
|||
time(_=rle3(S)), |
|||
nl.</lang> |
|||
{{out}} |
|||
<pre>rle/1: |
|||
CPU time 4.02 seconds. |
|||
rle3/1: |
|||
CPU time 2.422 seconds. |
|||
rle3/1: |
|||
CPU time 0.812 seconds.</pre> |
|||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |