85 lines
2.1 KiB
Text
85 lines
2.1 KiB
Text
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].
|