LZW compression: Difference between revisions
→{{header|Picat}}
Line 4,298:
TOBEORNOTTOBEORTOBEORNOT
</pre>
=={{header|Picat}}==
<lang Picat>go =>
S = "TOBEORNOTTOBEORTOBEORNOT",
println(s=S),
println(len=S.length),
Compressed = compress(S),
println(compressed=Compressed),
println(len=Compressed.length),
Uncompressed = uncompress(Compressed),
println(uncompressed=Uncompressed),
printf("compressed to %3.3f%%\n", 100*(Compressed.length / S.length)),
if S = Uncompressed then
println("Same!")
else
println("Error: S != Uncompressed!"),
printf("S.length: %d Uncompressed.length: %d\n", S.length, Uncompressed.length),
edit(S,Uncompressed,Distance,Diffs),
println(distance=Distance),
println(diffs=Diffs)
end,
nl.
compress(Uncompressed) = Compressed =>
DictSize = 256,
Dict = new_map([C=C : I in 1..DictSize-1, C=chr(I).to_string()]),
W = "",
Result = [],
foreach(C in Uncompressed)
C := C.to_string(),
WC = W ++ C,
if Dict.has_key(WC) then
W := WC
else
Result := Result ++ [Dict.get(W)],
Dict.put(WC, DictSize),
DictSize := DictSize + 1,
W := C
end
end,
if W.length > 0 then
Result := Result ++ [Dict.get(W)]
end,
Compressed = Result.
uncompress(Compressed) = Uncompressed =>
DictSize = 256,
Dict = new_map([ C=C : I in 1..DictSize-1, C=chr(I).to_string()]),
W = Compressed.first(),
Compressed := Compressed.tail(),
Result = W,
Entry = "",
foreach(K in Compressed)
if Dict.has_key(K) then
Entry := Dict.get(K)
elseif K == DictSize then
Entry := W ++ W[1].to_string()
else
printf("Bad compressed K: %w\n", K)
end,
Result := Result ++ Entry,
Dict.put(DictSize,(W ++ Entry[1].to_string())),
DictSize := DictSize + 1,
W := Entry
end,
Uncompressed = Result.flatten().
%
% Computing the minimal editing distance of two given lists
%
table(+,+,min,-)
edit([],[],D,Diffs) => D=0, Diffs=[].
edit([X|Xs],[X|Ys],D,Diffs) => % copy
edit(Xs,Ys,D,Diffs).
edit(Xs,[Y|Ys],D,Diffs) ?=> % insert
edit(Xs,Ys,D1,Diffs1),
D=D1+1,
Diffs = [insert=Y,xPos=Xs.length,yPos=Ys.length|Diffs1].
edit([X|Xs],Ys,D,Diffs) => % delete
edit(Xs,Ys,D1,Diffs1),
D=D1+1,
Diffs = [[delete=X,xPos=Xs.length,yPos=Ys.length]|Diffs1].</lang>
Output:
<pre>s = TOBEORNOTTOBEORTOBEORNOT
len = 24
compressed = [T,O,B,E,O,R,N,O,T,256,258,260,265,259,261,263]
len = 16
uncompressed = TOBEORNOTTOBEORTOBEORNOT
compressed to 66.667%
Same!</pre>
=={{header|PicoLisp}}==
| |||