Python 3: 93943 = 91,752 + 1990 + 1
This is my messy attempt at a compression. The information density of the file is not as great as it seems and there were several observable redundancies. Because of that I have doubts that there is a reasonable way to predict the data. I am prepared to be wrong though :-).
The code by itself is not golfed that much, since the main portion of the cost is the size of the compressed files. The decompressor is only 1990 bytes long.
The compression itself is done by Two separate huffman trees, implied ":" between them and two one-bit streams that act as a guides. Also there are few simple substitutions in place.
- First huffman tree codes the first letter
- Second huffman tree codes the portion that follows the ":"
- First bit file (a) codes whether the line before the ":" consists of 0-1 or 2 characters
- Second bit file (u) codes whether the second character before : is "b" or "#"
Lastly, all the files are compressed via zip since on my work computer we don't have anything else. Might try other compressors later on.
zip-input
This archive has to be in programs working directory.
The code itself is tied tightly to the file. It does not cover full format specifications listed by the author of the question. (Also, I have hard-coded the input file size into the decoder - after I missed the proper termination one times too many.)
There is definitely a room for improvements - for example few more substitutions tied to the numbers in brackets.
There might be a missing trailing newline in the output, that I somehow keep missing while trying to debug.
Huffman tree generator:
import heapq as h
import numpy as np
from bitarray import bitarray
class List:
def __init__(self, char, freq):
self.char = char
self.freq = freq
self.leftSon = None
self.rightSon = None
def __lt__(self, other):
return self.freq < other.freq
def check(self,arr, prefix):
if self.char is not None:
arr.append((self.char, prefix))
else:
self.leftSon.check(arr, prefix + "0")
self.rightSon.check(arr, prefix + "1")
def encode(self):
if self.char is None:
toRet = "0"
toRet += self.leftSon.encode()
toRet += self.rightSon.encode()
else:
toRet = "1" + np.binary_repr(ord(self.char), 8)
return toRet
class HuffmanTree:
def __init__(self, inputList):
a = []
for x in inputList:
h.heappush(a, List(x[0], x[1]))
while len(a) > 1:
first = h.heappop(a)
second = h.heappop(a)
new = List(None, first.freq + second.freq)
new.leftSon = first
new.rightSon = second
h.heappush(a, new)
self.root = a[0]
self.encodeArray = []
self.root.check(self.encodeArray, "")
encodeDict = {}
for x in self.encodeArray:
encodeDict[x[0]] = x[1]
self.encodeDict = encodeDict
print(self.encodeArray)
def encodeSelf(self):
head = self.root
bits = head.encode()
x = bitarray()
for b in bits:
if b == "0":
x.append(0b0)
else:
x.append(0b1)
return x
The code to generate the support files:
import huffman
from bitarray import bitarray
a = ""
with open("chords.txt") as chr:
a = chr.read()
def getCounts(l):
counts = {}
for x in l:
if x in counts.keys():
counts[x] += 1
else:
counts[x] = 1
res = []
for x in counts.keys():
res.append((x, counts[x]))
return res
def stringToBits(string):
ret = bitarray()
for x in string:
if x =="0":
ret.append(0b0)
else:
ret.append(0b1)
return ret
lines = a.split("\n")
firstPart = []
secondPart = []
for i in lines:
a = i.split(":")
firstPart.append(a[0])
if len(a) > 1:
secondPart.append(a[1] + "\n")
###First part
Afile = ""
huffFile = ""
sharpFile = ""
firstPartChars = ""
fChar = []
sChar = []
for x in firstPart:
firstPartChars += x
if len(x) == 0:
fChar.append("\n")
Afile += "0"
else:
fChar.append(x[0])
if len(x) == 1:
Afile += "0"
if len(x) == 2:
Afile += "1"
sChar.append(x[1])
print([x for x in set(fChar)])
print([x for x in set(sChar)])
fCharCount = getCounts(fChar)
sCharCount = getCounts(sChar)
firstHuff = huffman.HuffmanTree(fCharCount)
for char in fChar:
code = firstHuff.encodeDict[char]
huffFile += code
for char in sChar:
if char == "b":
sharpFile += "0"
elif char == "#":
sharpFile += "1"
else:
raise Exception("error in sharp file")
#######
#####Second part
sPartFile = ""
subs = {}
subs["maj"] = "~"
subs["min"] = "&"
subs["sus"] = "^"
subs["aug"] = "%"
subs["dim"] = "$"
subs["hdi"] = "@"
spPart = []
secSubPart = ""
for x in secondPart:
c = x.replace("maj", "~").replace("min", "&").replace("sus", "^").replace("aug", "%")\
.replace("dim", "$").replace("hdim", "@")
spPart.append(c)
secSubPart += c
secPartCounts = getCounts(secSubPart)
secondHuff = huffman.HuffmanTree(secPartCounts)
for x in secSubPart:
sPartFile += secondHuff.encodeDict[x]
aBits = stringToBits(Afile)
huffBits = stringToBits(huffFile)
sharpBits = stringToBits(sharpFile)
sPartBits = stringToBits(sPartFile)
print("test")
with open("a", "wb") as t:
aBits.tofile(t)
with open("h", "wb") as t:
huffBits.tofile(t)
with open("u", "wb") as t:
sharpBits.tofile(t)
with open("f", "wb") as t:
sPartBits.tofile(t)
with open("i", "wb") as t:
a = firstHuff.encodeSelf()
a.tofile(t)
with open("j", "wb") as t:
b = secondHuff.encodeSelf()
b.tofile(t)
Finally the code itself:
from bitarray import bitarray as b
import zipfile
with zipfile.ZipFile("h.zip", 'r') as z:
z.extractall(".")
class N:
def __init__(s):
s.c = None
s.l = None
s.r = None
def i(s):
return s.l == None
def d(s, r):
if s.i():
return s.c
else:
if r.b() == 0:
return s.l.d(r)
else:
return s.r.d(r)
class R:
def __init__(s, bits):
s.d = bits
s.i = 0
def b(s):
t = s.d[s.i]
s.i += 1
return t
def B(s):
toRet = s.d[s.i:s.i + 8]
s.i += 8
return toRet
def rn(r):
if r.b() == 1:
n = N()
n.c = r.B().tostring()
else:
left = rn(r)
right = rn(r)
n = N()
n.l = left
n.r = right
return n
def bff(i):
with open(i, "rb") as f:
c = b()
c.fromfile(f)
return c
def huffRead(a):
c = bff(a)
r = R(c)
n = rn(r)
return n
fh = huffRead("i")
fp = R(bff("h"))
sh = huffRead("j")
sp = R(bff("f"))
af = R(bff("a"))
bp = R(bff("u"))
ft = ""
test = open("test", "w")
i=0
while i < 125784:
i += 1
tp = ""
n = "\n"
s = "#"
b = "b"
t = fh.d(fp)
spr = True
if af.b() == 0:
if t == n:
tp += t
spr = False
elif t == "N" or t == "X":
tp += t + n
spr = False
else:
tp += t + ":"
else:
tp += t
if bp.b() == 1:
tp += s + ":"
else:
tp += b + ":"
if spr:
x = sh.d(sp)
while x != n:
tp += x
x = sh.d(sp)
tp += x
tp = tp.replace("~", "maj").replace("&", "min").replace("^", "sus")\
.replace("%", "aug").replace("$", "dim").replace("@", "hdim")
ft += tp
print(ft)
