Files

lzw.src encoder.src libs/lst.src
lzw.src
  • import_code("/home/me/projects/lzw/libs/lst.src")
  • import_code("/home/me/projects/lzw/encoder.src")
  • generate_dict = function(length)
  • f = function(i)
  • return [char(i), char(i)]
  • end function
  • return range(length - 1).sort.map(@f).to_map
  • end function
  • compress = function(uncompressed)
  • dict_size = 256
  • dictionary = generate_dict(dict_size)
  • w = ""
  • result = []
  • for c in uncompressed.values
  • wc = w + c
  • if dictionary.hasIndex(wc) then
  • w = wc
  • else
  • result.push(dictionary[w])
  • dictionary[wc] = dict_size
  • dict_size = dict_size + 1
  • w = c
  • end if
  • end for
  • if w != "" then result.push(dictionary[w])
  • return result
  • end function
  • decompress = function(compressed)
  • dict_size = 256
  • dictionary = generate_dict(dict_size)
  • w = compressed[0]
  • result = compressed[0]
  • compressed = compressed[1:]
  • for k in compressed
  • if dictionary.hasIndex(k) then
  • entry = dictionary[k]
  • else if k == dict_size then
  • entry = w + w[0]
  • else
  • exit("Bad compressed k: " + k)
  • end if
  • result = result + entry
  • dictionary[dict_size] = w + entry[0]
  • dict_size = dict_size + 1
  • w = entry
  • end for
  • return result
  • end function
  • //compressed = compress("TOBEORNOTTOBEORTOBEORNOT")
  • user_in = user_input("in: ")
  • compressed = compress(user_in)
  • //print compressed
  • //print bin_to_lzw_table(string_to_stream(encode_lzw_table(compressed)))
  • //print(user_in.len)
  • //print(compressed.len)
  • //print "original"
  • //print user_in
  • //print "compressed"
  • //print encode_lzw_table(compressed)
  • print "original len: " + user_in.len
  • print "compressed len: " + encode_lzw_table(compressed).len
  • exit
  • f = function(c)
  • r = c
  • if c isa string then r = c.code
  • return "0" * (CELL_LEN - to_bin(r).len) + to_bin(r)
  • end function
  • compressed = compressed.map(@f)
  • print compressed
  • compressed = divide(compressed.join(""), 7)
  • print compressed
  • f = function(s)
  • return to_int(s)
  • end function
  • compressed = compressed.map(@f)
  • print compressed
  • //print char_set.len
  • //print to_bin(char_set.len)
  • f = function(n)
  • return char(char_set[n])
  • end function
  • compressed = compressed.map(@f)
  • print compressed.join("")
  • exit
  • decompressed = decompress(compressed)
  • print decompressed
encoder.src
  • CELL_LEN = 14
  • // UTILS ------------------------------------------------------
  • to_bin = function(n)
  • if n == 0 then return "0"
  • if n == 1 then return "1"
  • return to_bin(floor(n / 2)) + str(n % 2)
  • end function
  • to_int = function(n)
  • n = n.values
  • n.reverse
  • r = 0
  • for i in n.indexes
  • if n[i] == "1" then
  • r = r + 2 ^ i
  • end if
  • end for
  • return r
  • end function
  • divide = function(s, n)
  • if s.len == 0 then
  • return []
  • end if
  • if s.len < n then
  • //prepend = "0" * (n - s.len)
  • //s = prepend + s
  • return [s]
  • end if
  • return divide(s[n:], n).insert(0, s[0:n])
  • end function
  • char_set = []
  • char_set.push(range(48, 57)) // numbers
  • char_set.push(range(65, 90)) // capital_letters
  • char_set.push(range(97, 122)) // letters
  • char_set.push(range(128, 192)) // extended
  • char_set.push("@".code)
  • char_set = char_set.flat // <- 7 bit char set
  • // -------------------------------------------------------------
  • lzw_table_to_bin = function(table)
  • f = function(c)
  • r = c
  • if c isa string then r = c.code
  • return "0" * (CELL_LEN - to_bin(r).len) + to_bin(r)
  • end function
  • return table.map(@f).join("")
  • end function
  • bin_to_lzw_table = function(stream)
  • f = function(s)
  • n = to_int(s)
  • if n < 256 then return char(n)
  • return n
  • return
  • end function
  • return divide(stream, CELL_LEN).map(@f)
  • end function
  • stream_to_string = function(bits_stream)
  • f = function(s)
  • return char(char_set[to_int(s)])
  • end function
  • return divide(bits_stream, 7).map(@f).join("")
  • end function
  • string_to_stream = function(string)
  • f = function(s)
  • bin = to_bin(char_set.indexOf(s.code))
  • return "0" * (7 - bin.len) + bin
  • end function
  • return string.values.map(@f).join("")
  • end function
  • encode_lzw_table = function(table)
  • return stream_to_string(lzw_table_to_bin(table))
  • end function
  • decode_lzw_table = function(string)
  • end function
libs/lst.src
  • map.to_list = function(shallow = false)
  • list = []
  • for i in self.indexes
  • if typeof(self[i]) == "map" then
  • if shallow == true then
  • list.push([i, self[i]])
  • else
  • list.push([i, self[i].to_list])
  • end if
  • else
  • list.push([i, self[i]])
  • end if
  • end for
  • return list
  • end function
  • list.to_map = function()
  • l = self[0:]
  • map = {}
  • for i in indexes(l)
  • if typeof(l[i][1]) == "list" and l[i][1].len == 2 and typeof(l[i][1][0]) == "string" then
  • map[l[i][0]] = l[i][1].to_map
  • else
  • map[l[i][0]] = l[i][1]
  • end if
  • end for
  • return map
  • end function
  • list.each = function(func)
  • result = self[0:] //list copy.
  • for i in indexes(self)
  • func(result[i])
  • end for
  • end function
  • map.each = function(func)
  • list = self.to_list(true)
  • result = list[0:] //list copy.
  • for i in indexes(list)
  • func(result[i][0], result[i][1])
  • end for
  • end function
  • list.map = function(func)
  • result = self[0:] //list copy.
  • for i in indexes(self)
  • result[i] = func(result[i])
  • end for
  • return result
  • end function
  • list.reject = function(func)
  • result = self[0:] //list copy.
  • i = 0
  • while i < result.len
  • if func(result[i]) == true then
  • result.remove(i)
  • continue
  • end if
  • i = i + 1
  • end while
  • return result
  • end function
  • list.select = function(func)
  • f = function(o)
  • return not func(o)
  • end function
  • return self.reject(@f)
  • end function
  • // do not rename funcc to to func it will infinite loop
  • list.lsort = function(funcc)
  • f = function(i)
  • return {"sort_key": funcc(i), "obj": i}
  • end function
  • result = self.map(@f)
  • result = result.sort("sort_key")
  • f = function(i)
  • return i["obj"]
  • end function
  • return result.map(@f)
  • end function
  • list.flat = function()
  • result = []
  • for i in self
  • if typeof(i) == "list" then
  • result = result + i.flat
  • else
  • result.push(i)
  • end if
  • end for
  • return result
  • end function
  • list.uniq = function()
  • result = []
  • for i in self
  • if result.indexOf(i) == null then result.push(i)
  • end for
  • return result
  • end function
  • list.has_any = function(value)
  • for i in self
  • if i == value then return true
  • end for
  • return false
  • end function
  • list.min = function()
  • min = self[0]
  • for item in self
  • if item < min then
  • min = item
  • end if
  • end for
  • return min
  • end function
  • list.max = function()
  • max = self[0]
  • for item in self
  • if item > max then
  • max = item
  • end if
  • end for
  • return max
  • end function