algorithm – THE HYPERTEXT http://www.thehypertext.com Thu, 10 Dec 2015 06:10:15 +0000 en-US hourly 1 https://wordpress.org/?v=5.0.4 Run-length encoding algorithm http://www.thehypertext.com/2015/10/28/run-length-encoding-algorithm/ Wed, 28 Oct 2015 01:06:58 +0000 http://www.thehypertext.com/?p=769 For our first assignment in Learning Machines, Patrick asked us to implement run-length encoding in Python.

Read More...

]]>
For our first assignment in Learning Machines, Patrick asked us to implement run-length encoding in Python.

Below is my code, which includes encode and decode functions.

def encode(u):
	# init tracking vars
	enc = list()
	cur = list(u[0])
	# iterate through string
	for i in range(1, len(u)):
		if u[i] == u[i-1]:
			cur.append(u[i])
		else:
			enc.append((len(cur), u[i-1]))
			cur = list(u[i])
	# handle last character
	enc.append((len(cur), cur[0]))

	def rep(tup):
		# encode using backtick as delimeter
		count, char = tup
		if count == 1:
			return char
		else:
			return "%s`%i`" % (char, count)

	return ''.join(map(rep, enc))

def decode(e):
	# init tracking vars
	result = list()
	cur_num = list()
	# switch var
	on_num = False
	# iterate through encoded string
	for i, char in enumerate(e):
		# if delimeter found...
		if char == "`":
			# switch on/off
			on_num = not on_num
			# if closing delimeter
			if not on_num:
				result.append(
					rep_char*int(''.join(cur_num))
				)
				cur_num = list()
			# if opening delimeter
			elif on_num and i > 0:
				# repeated char is last
				# added to result
				rep_char = result.pop()
		# if not delimeter and not on number
		elif not on_num:
			result.append(char)
		# if not delimeter and on number
		else:
			cur_num.append(char)
	return ''.join(result)



if __name__ == '__main__':
	import sys
	to_encode = sys.argv[1]
	encoded = encode(to_encode)
	decoded = decode(encoded)
	print encoded
	print decoded
	assert to_encode == decoded

 

]]>