いろんなアルゴリズム"00.00.00.16"

知恵の館の目次

立ち位置・仕様

• いろんなアルゴリズムをコピペできるように記録するのみ
• 最適化が目的でない
• たまにメモとして解説を残す
• 最低限でまとめる
• データを抽出しやすいように個別のIDを付与
• あるアルゴリズムにおいて、他のアルゴリズムが登場する際にはそのIDを付与
• IDは16進数表記
• なるべく最低限なパッケージで実装
• なるべく特殊なオブジェクト型は使用しない

TargetID

00.00.00.16

ReferenceID

swiched run length encoding

• "同じ数値が連続する場合"と"隣接する数値が異なることが連続する場合"とでモードを交互に切り替える方法
• AAAABBBBのような場合、4A04Bというようになる。4A04B内の0は、隣接する数値が異なることが連続する場合"がないため、"何も無い"という数値が0個あるというような解釈となる。
• 同じ数値が連続する場合：例 AAAAA
• 隣接する数値が異なることが連続する場合：例 ABCBA

def getPacBits(string, index):
	max_count = len(string) - index
	count = 0
	code = string[index]
	index += 1
	count += 1
	encodeMode = None

	if code == string[index]:
		encodeMode = 0
		while index < len(string) and code == string[index] and count < max_count:
			code = string[index]
			index += 1
			count += 1
	else:
		encodeMode = 1
		while index < len(string) and code != string[index] and count < max_count:
			code = string[index]
			index += 1
			count += 1

		if index != len(string):
			index -= 1
			count -= 1
	return (count, index, encodeMode)

def switchedRunLengthEncoding(string):
	encode_list = []
	index = 0
	mode = 1
	while index < len(string) - 1:
		baseIndex = index
		count, index, encodeMode = getPacBits(string,index)

		if mode == 0:
			mode = 1
			if encodeMode == 1:
				encode_list.append(0)
				index = baseIndex
			else:
				# 同じ数値が連続する方は、2以上であるはずだから、count-1で表現することがある
				# (count, 数値)となることや(数値, count)となることや，それぞれで異なることがある
				encode_list.append((count, string[baseIndex])) 
		else:
			mode = 0
			if encodeMode == 0:
				encode_list.append(0)
				index = baseIndex
			else:
				encode_list.append((count,string[baseIndex:index])) 
	
	encode_string = ""
	for d in encode_list:
		if type(d) == int and d == 0:
			encode_string += str(d)
		else:
			encode_string += str(d[0])+str(d[1])
	
	return encode_string

使用方法

string = "AAAABCCCCABCAAA"
l = switchedRunLengthEncoding(string)
print(l) # 04A1B4C3ABC3A