resortVideoRle.py

#Суть алгоритма: 
# 1. Находим для всех массивов, какой длины у него есть "торчащие" голова и хвост из одинаковых элементов. Получаем массив из туплов - голова, хвост, индекс элемента.
# 2. Выбираем самую лучшую пару для соединения - ищем, какие голова и хвост могут образовать самую длинную цепочку
# 3. Соединяем два элемента массива в один - склеиваем голову и хвост, получаем элемент с новыми концами. Запоминаем также, какая пара элементов была склеена - храним список того, какие именно элементы были соединены.
# 4. Повторяем шаг 2 до тех пор, пока это возможно - пока будут находится пары элементов, у которых значение головы первого элемента пары совпадает со значением хвоста второго элемента.
# 5. Когда таких пар не нашлось - список невозможно дальше склеивать, теперь проходим по нему слева направо и восстанавливаем все списки индексов элементов - это лучшая последовательность для сжатия её алгоритмом RLE.
#------------------------------------------------------------
def calcEnds(arr):
	repeatBegin = 0
	for x in arr:
		if x == arr[0]:
			repeatBegin+=1
		else:
			break
	repeatEnd = 0
	lastVal = arr[len(arr)-1]
	for ind in xrange(len(arr)-1, 0, -1):
		if arr[ind] == lastVal:
			repeatEnd+=1
		else:
			break
	return ((repeatBegin, arr[0]), (repeatEnd, lastVal))
  
def prepareEndPairs(nesData):
	index = 0
	result = []
	while len(nesData) >= 16:
		arr = nesData[:16]
		nesData = nesData[16:]
		ends = calcEnds(arr)
		result.append( (ends, [index]) )
		index+=1
	return result

#------------------------------------------------------------
  
def findBestMatch(endPairs):
	curMax = 0
	curBestPair = (-1,-1)
	for i in xrange(len(endPairs)):
		for j in xrange(len(endPairs)):
			if i == j:
				continue
			r1, v1 = endPairs[i][0][0]
			r2, v2 = endPairs[j][0][1]
			if v1 == v2 and (r1+r2) > curMax:
				curMax = r1+r2
				curBestPair = (i,j)
	return curBestPair, curMax
  
def foldEndPairs(endPairs):
	while True:
		bestPair = findBestMatch(endPairs)
		if bestPair[0] == (-1,-1):
			break
		endPairs = reconstruct(endPairs, bestPair)
	return endPairs
  
def reconstruct(endPairs, bestPair):
	b,e = bestPair[0]
	bdel = endPairs[b]
	edel = endPairs[e]
	endPairs.remove(bdel)
	endPairs.remove(edel)
	edel[1].extend(bdel[1])
	endPairs.append(((edel[0][0],bdel[0][1]), edel[1]))
	return endPairs
  
def remakeArray(data, endPairs):
	result = []
	for _,inds in endPairs:
		for ind in inds:
			result.extend(data[index*16 : (index+1)*16])
	return result
  
###
#endPairs = [(((3,1),(2,3)),[0]), (((3,8),(4,9)),[1]), (((3,1),(4,3)),[2]), (((8,3),(1,1)),[3]) ]
#>>> fn = r"Duck Tales (U) [!].nes"
#>>> f = open(fn, "rb")
#>>> d = f.read()
#>>> f.close()
#>>> vd = d[0x4010:0x4010+4096]
endPairs = prepareEndPairs(vd)
shortPairs = foldEndPairs(endPairs)
#((2, 1), 12)
###