Transformée de Burrows-Wheeler en python (Burrows-Wheeler Transform)

Voici une implémentation python de la transformée de burrows-wheeler en python qui est un pré-traitement utilisé en compression de donnée.

def encodage(inputStr):
	rotations = [inputStr[i:] + inputStr[:i] for i in range(len(inputStr))]
	rotations.sort()
	encodagedStr = [x[-1] for x in rotations]
	index = rotations.index(inputStr)
	return (''.join(encodagedStr), index)

def decodage(encodagedStr, index):
	rotations = [encodagedStr[i] for i in range(len(encodagedStr))]
	for i in range(len(encodagedStr) - 1):
		rotations.sort(key = lambda x : x[0])
		rotations = [encodagedStr[i] + x for i,x in enumerate(rotations)]
	rotations.sort(key = lambda x : x[0])
	return rotations[index]

print("encodage = " + str(encodage('128mots.com')))
print("decodage = " + str(decodage('sm12.o8cmto',1)))
print("decodage = " + str(decodage('sm12.o8cmto',2)))
print("decodage = " + str(decodage('sm12.o8cmto',3)))

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *