n_base_number_system_with_prefix_encoding_decoding.py, Python 3

Language: Layout:

import random;	#for random.randrange()

print("\n\n\nСтарт программы...")

# Эта функция подсчитает количества комбинаций '0' и '1',
# а также количества комбинаций '00', '01', '10', '11' в двоичной строке,
# и вернёт эти количества в виде массива с двумя объектами.
def count_null_ones(binary_string):	#binary_string: "011010010...0010010..."

#	Подcчитаем количества комбинаций '0', '1':
	nulls	=	0;
	ones 	=	0;	
	if(len(binary_string)%2 == 1): binary_string = '0'+binary_string;
	for i in range(0, len(binary_string)):
		if(binary_string[i]=='1'):
			ones	+=	1;
		elif(binary_string[i]=='0'):
			nulls	+=	1;

#	Подсчитаем количества комбинаций '00', '01', '10', '11':
	null_null	=	0;
	null_one	=	0;
	one_null	=	0;
	one_one		=	0;
	for i in range(0, len(binary_string), 2):
		if		(	binary_string[i] == '0'	and	binary_string[i+1] == '0'	):
			null_null	+=	1;
		elif	(	binary_string[i] == '0'	and	binary_string[i+1] == '1'	):
			null_one	+=	1;
		elif	(	binary_string[i] == '1'	and	binary_string[i+1] == '0'	):
			one_null	+=	1;
		elif	(	binary_string[i] == '1'	and	binary_string[i+1] == '1'	):
			one_one		+=	1;
	return [	#	Вернуть массив с объектами.
				{
					'0': nulls,
					'1': ones
				},
				{
					'00': null_null,
					'01': null_one,
					'10': one_null,
					'11': one_one
				}
	];
#Конец функции

# Эта функция кодирует строку префиксным кодом по словарю Prefix_code_dictionary, и декодирует её назад (когда decode=True);
def Prefix_code(string, Prefix_code_dictionary, decode=False):
	"""
	#пример словаря:
	Prefix_code_dictionary = {
		#	encode ->
		#	decode <-
		#	index:	["value": "code"]
			0: ['0', '00'],
			1: ['1', '01'],
			2: ['2', '1']
	};
	#индексы размещены по порядку так, чтобы префиксный код был получен последовательными заменами в строке.
	"""
	if(decode == True):				#Prefix_code Decode
		keys	=	list(Prefix_code_dictionary.keys());			#in python 2, you'll need `Prefix_code_dictionary.keys()`
		values	=	list(Prefix_code_dictionary.values());

#Эти данные будут браться из словаря замены.
		min_code_length 	= 	0;		#длина минимального кода
		min_code 			= 	0;		#минимальный код
		min_value 			= 	0;		#значение минимального кода
		max_code_length 	= 	0;		#длина максимального кода

#Сохраним данные о наименьшем и наибольшем коде, из словаря Prefix_code_dictionary
		for i in range(0, len(keys)):							#Для всех кодов, определяе
			if(len(values[i][1]) < min_code_length):				#Определяем наименьший код, и знчение, которое ему соответствует.
				min_code_length = len(values[i][1]);					#сохраняем длину самого короткого кода
				min_code = values[i][1];									#сам код
				min_value = values[i][0];									#и значение, ему соответствующее.
			elif(len(values[i][1]) > max_code_length):				#Для наибольшего кода
				max_code_length = len(values[i][1]);					#сохраняем длину самого длинного кода
		
		bin_string_arr = [];									#определим масив с бинарными данными.
		skip = 0;												#определим переменную, содержащую количество бит для пропуска.

#Декодируем префиксный код по словарю Prefix_code_dictionary
		for j in range(0, len(string)):					#для каждого бита закодированной строки
			if(skip>0):												#если надо пропустить его
				skip -= 1;												#декрементировать skip
				continue;												#и пропустить бит
			if(string[j] == min_code):						#Самый короткий код - соответствует самому часто-встречающемуся значению. Если это он, то...
				bin_string_arr.append(str(min_value));					#добавляем значение ему соответствующее.
			else:												#иначе, в закодированной строке ожидается более длинный код.
				long_code = "";										#задать пустую строку long_code.
				for i in range(min_code_length, max_code_length):		#Для каждого последующего бита, от минимальной длины кода, до максимальной
					if(skip>0): break;										#выйти из цикла, если skip больше нуля
					if((j+i)>=len(string)): break;					#также, выйти из цикла, когда превышена длина строки.
					long_code += string[j+i];						#иначе прибавить следующий бит к long_code.
					for c in values:										#попытаться найти код в values
						if(skip>0): break;										#выйти из этого цикла, если skip больше нуля 
						if(len(long_code) == len(c[1]) and long_code == c[1]):		#если long_code найден
							bin_string_arr.append(c[0]);								#добавить значение, ему соответствующее в bin_string_arr
							skip = (skip + i)%(i+1);									#сказать программе, что надо пропустить i следующих бит.
							break;														#и выйти из этого цикла.
		#print("bin_string_arr", bin_string_arr);				#Теперь, должен быть получен массив значений, соответствующих кодам префиксного кода. Показать его.

#Из него, нужно создать бинарную строку.
		string = "";							#к пустой строке
		for k in range(0, len(bin_string_arr)):		#для всех значений массива
			string += bin_string_arr[k];			#прибавляем очередное значение
		#string будет возвращена из функции позже

elif(decode == False):				#Если не нужно декодировать, то кодировать.
		#все ключи и значения - в массивы
		keys	=	list(Prefix_code_dictionary.keys());			#в Python 2, надо будет исползовать 'Prefix_code_dictionary.keys()'
		values	=	list(Prefix_code_dictionary.values());
		for i in range(0, len(keys)):												#для каждого значения ключа ["value": "code"]
			string = string.replace(values[i][0], values[i][1]);			#произвести последовательные замены "value" на "code"

#print("string = ", string, "\nlen(string): ", len(string));		#покажем бинарну строку, которая будет возвращена, и её длину.
	return string;	#Теперь вернём либо закодированную, либо раскодированную бинарную строку.
#Конец функции.
"""
Как сгенерировать префиксный код?
	По условию Фано, все коды префиксного кода не должны быть началом предыдущих кодов.
	1. Генерируем все комбинации бит, длиной n. Пусть n = 2, в этом случае:
		00
		01
		10
		11
	2. Удаляем нули спереди, кроме нуля:
		0
		1
		10
		11
	3. Комментируем коды, являющиеся началом предыдущих кодов:
		0	<- оставить
	#	1	<- закомментировать, потому что является началом следующих кодов.
		10
		11
	4.		Берём незакомментированные коды:	[0, 10, 11] - это коды префиксного кода.
			Также, как и негации этих кодов:	[1, 01, 00] - это тоже коды префиксного кода.

#Как юзать функцию выше?
#	1. Определяем словарь в виде объекта, вот так:
Prefix_code_dictionary = {
	#	encode ->
	#	decode <-
	#	index:	["value": "code"]
		0: ['0', '00'],
		1: ['1', '01'],
		2: ['2', '1']
};
#	2. Кодируем:
encoded = Prefix_code	(012_ternary_number_system_string, 	Prefix_code_dictionary);	#encode
#	3. Декодируем:
decoded = Prefix_code	(encoded, Prefix_code_dictionary, True);						#decode
"""

#	Эта функция генерирует массив с цифрами [0, (base-1)], для основания (base>10) и (base < 75)
#	Массив содержит символы, а цифры являются индексами этих символов в массиве.
def gen_digits_array(base):
	digits_array = [];
	if(base<=10):
		return [[], False];
	if(base>=11):
		for i in range(0, base):
			if(i<10):
				digits_array.append(str(i));
			elif(i>=10 and i<16):
				digits_array.append(str(hex(i)[2::]));
			else:
				if(i<48):
					add = 0;			#value to shift symbols
				elif(i>=48 and i<49):
					add = 48;			#change
				elif(i>=49 and i<54):
					add = 54;			#change
				elif(i>=54 and i<74):
					add = 54;			#change
				else:
					print("base too big - over or equal 75: base =", base);
					return [[], False];

char = chr(i+add);				#shift symbol
				digits_array.append(char);
	return [digits_array, True];
#Конец функции

# Эта функция переводит число в b-ричную систему счисления, с основанием 'b'.
#	При основании b > 16, цифры представляют из себя буквы, сгенерированные функцией выше.
def baseb(n, b):
	e = n//b
	q = n%b
	if n == 0:
		return '0'
	elif e == 0:
		if(digits[1] == True):
			return digits[0][q];
		else:
			return str(q)
	else:
		if(digits[1] == True):
			return baseb(e, b) + digits[0][q];
		else:
			return baseb(e, b) + str(q)
#Конец функции.

# Эта функция переводит число из base-ричной системы счисления, с основанием base - в десятичную систему счисления.
def toDecimal(str, base):
	llen = len(str);
	power = 1;	#Инициализировать степень основания
	num = 0;	#инициализировать результат

# Десятичный эквивалент: str[len-1]*1 + str[len-1]*base + str[len-1]*(base^2) + ...  
	for i in range(llen - 1, -1, -1): 
		# Цифра во входном номере должна быть меньше основания.
		if(digits[1]==True):							#Если используются цифры из массива
			num += (digits[0]).index(str[i]) * power;		#индекс цифры в массиве умножить на степень основания и прибавить к предыдущему числу.
		else:											#Если не используются цифры из массива
			num += int(int(str[i])*int(power));				#i умножить на степень основания и прибавит к предыдущему числу.
		power = power * base;							#увеличить степень основания на основание.
	return num;										#и вернуть число, в конце.
#Конец функции.

#	Ввести число при запуске программы.
#x = int(input("Введите натуральное число ввод: _"));
#print(str("\n")+str("Было введено: x = "),x);

#	А лучше - сгенерировать его.
x = int(random.randrange(0, 1000000000000000000000000000000000000000000000000000000000000));
print(str("\n")+str("Было сгенерировано: x = "),x);

#	Или задать это число
#Пример - отсюда: https://arxiv.org/ftp/arxiv/papers/1201/1201.5603.pdf
#x = 1358; #11 бит - в двоичном представлении, 10 bits - в троичном, пожатом префиксным кодом.

#x = 2954312706550833698643;				#1000000000000000000000000000000000000000000000 (3)		#много нулей
#	Закодированная префиксным кодом строка троичного представления - намного длинее двоичного представления числа.

#x = 4431469059826250547964;				#1111111111111111111111111111111111111111111111 (3)		#много единиц
#	Закодированная префиксным кодом строка троичного представления - намного длинее двоичного представления числа.

#x = 8862938119652501095928;				#2222222222222222222222222222222222222222222222 (3)		#много двоек
#	Закодированная префиксным кодом срока троичного представления - короче двоичного представления числа.

#print(str("\n")+str("Было задано: x = "),x);

print(
	str("\n")+
	str("bin(x)[2::]:\n")+str(bin(x)[2::])+
	str(",\nlen(bin(x)[2::]): ")+str(len(bin(x)[2::]))
);

binary_not_encoded_string = bin(x)[2::];

print(	"nulls, ones:", count_null_ones(str(bin(x)[2::])), str("\n")	);

base = 3;				#Изберём троичную систему счисления.
#base = 74; 			#Или другую - максимумальным основанием 74 (тест)
print("base =", base);

digits = gen_digits_array(base);		#Сгенерируем массив с цифрами для системы счисления с основанием base.

#string = to_ternary(x);
base_encoded_string = baseb(x, base);		#Переведём число в систеу счисления, с основанием base.
print("base_encoded_string = ", base_encoded_string, "\nlen(base_encoded_string): ", len(base_encoded_string), str("\n"));

#	Теперь, сожмём base-ричное число - префиксным кодом.
#	Коды - отсюда: https://arxiv.org/ftp/arxiv/papers/1201/1201.5603.pdf

#Словарь для сжатия
Prefix_code_dictionary = {
	#	encode ->
	#	decode <-
	#	index:	["value": "code"]
		0: ['0', '00'],
		1: ['1', '01'],
		2: ['2', '1']
};

base_encoded_Prefix_code_string 	= 		Prefix_code	(base_encoded_string, 	Prefix_code_dictionary,						);		#закодировать строку с троичным представлением.
print("base_encoded_Prefix_code_string", base_encoded_Prefix_code_string, "\nlen(base_encoded_Prefix_code_string): ", len(base_encoded_Prefix_code_string));
print("nulls, ones:", count_null_ones(base_encoded_Prefix_code_string));	#подсчитать количества однобитных и двухбитных комбинаций.
print(
	str("\n")+str("Видно, что нулей больше, чем в изначальной двоичной строке...")+
	str("\n")+str("Иногда, закодированная префиксным кодом строка содержит нечётное число бит.")+
	str("\n")+str("Можно было бы добавить бит 1 или 00 (в зависимости от чётности длины строки), и попробовать сжать нули опять...")+
	str("\n")
);

#Раскодируем строку,  закодированную префиксным кодом - назад в base-ричное представление.
base_encoded_string 			= 		Prefix_code	(base_encoded_Prefix_code_string, 	Prefix_code_dictionary, 	True	);
print("base_encoded_string = ", base_encoded_string, "\nlen(base_encoded_string): ", len(base_encoded_string), str("\n"));

#Переведём её из base-ричного представления в десятичное.
x2 = toDecimal(base_encoded_string, base);

print("Число, декодированное из base-ричной системы счисления: x2 =", x2);				#	покажем восстановленное число
print("Сравним с изначальным числом: (x2 == x):", (x2 == x)); 	#	и сравним его - с изначальным

[ + ] Show input