たくさん寝太郎の寝床

大阪在住大学生オタクのブログ

Pythonで考える基本情報の話

こんにちは、たくさん寝太郎です。

今日はH29秋の基本情報技術者試験の問8の話をしようと思います。


https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2017h29_2/2017h29a_fe_pm_qs.pdf
(以下の問題の画像はIPAのサイトにある過去問から引用しています)


H29秋の問8は「文字列の誤りの検出」がテーマでした。今日はPythonでこの問題を考えてみます。

アルファベット26文字と記号4つを次のように整数値と対応させます。

文字 . , ? a ... z
数値 0 1 2 3 4 ... 29

(以下、空白は見づらいので_で表すことにします)


プログラムの説明

これらの数値から検査文字を生成し、元となる文字列の末尾に検査文字を追加した検査文字付文字列を検証するプログラムを考えます。

検査文字の生成

f:id:kaworu_mk6:20180911113310p:plain
例として「ipa__」に検査文字を付与してみましょう。

文字 i p a _ _
数値 12 19 4 0 0

N=30
奇数番目について、
0*2/N=0 余り 0
4*2/N=0 余り 8
12*2/N=0 余り 24
0+0+0+8+0+24=32
偶数番目について、
0+19=19

よって32+19=51
51/Nの余りは21よりN-21=9
9/Nの余りは9なので検査文字はfとなり、検査文字付文字列はipa__fです。

関数calcCheckCharacterの仕様を次のように定めます。

引数/返り値 type I/O 説明
input[] char I 文字列が格納されている一次元配列
return char O 生成した検査文字を返す


まず文字と数値を対応させた辞書を作ります。
一々"_":0,".":1......と打っていくのも面倒なのでちょっと楽な方法を考えてみました。

char_list = "_.,?abcdefghijklmnopqrstuvwxyz"
value_dict = {}
for i in char_list:
	value_dict[i] = char_list.find(i)

作った後に気付きましたが対応付けた辞書を作成しなくてもchar_listだけで十分でした。(悲しみなせ...)


関数getValuegetCharを次のように定義しておきます。

def getValue(word):
	return char_list.find(word)

def getChar(num):
	return char_list[num]

これでcalcCheckCharacterが定義できます。

def calcCheckCharacter(words):
	N = 30
	length = len(words)
	sum = 0
	is_even = False #末尾から操作するので最初は奇数です

	for i in range(length)[::-1]:
		value = getValue(words[i])
		if is_even == True:
			sum += value
		else:
			sum += int(2*value/N)+2*value%N

		is_even = not(is_even)

	check_value = (N-sum%N)%N

	return getChar(check_value)
検査文字付文字列の検証

f:id:kaworu_mk6:20180911114936p:plain
関数validateCheckCharacterの仕様を次のように定めます。

引数/返り値 type I/O 説明
input[] char I 検査文字付文字列が格納されている一次元配列
return bool O 誤りが無い場合True,ある場合Falseを返す
def validateCheckCharacter(words):
	N = 30
	length = len(words)
	sum = 0
	is_odd = True
	ret_value = True

	for i in range(length)[::-1]:
		value = getValue(words[i])
		if is_odd == True:
			sum += value
		else:
			sum += int(2*value/N)+2*value%N

		is_odd = not(is_odd)

	if sum%N != 0:
		ret_value = False

	return ret_value

ではちゃんと動くか試してみましょう。

words = "minase_inori"+calcCheckCharacter("minase_inori")
print(words)
=>
"minase_inorik"

print(validateCheckCharacter(words))
=>
True

良さそうです。

注意点

以上で考えたコードは誤りが1文字であれば誤り検出が可能ですが、誤りが複数ある場合は誤りが無いと判定してしまうことがあります。

例:ipa__の検査文字はfですが、検査文字付文字列api__fをチェックしてみるとTrueが返ってきます。

検査文字付表

文字列長がnであるm個の文字列に対して、(m+1)行(n+1)列の検査文字付表を作成します。

i p a _ _
t e s t s
m a k e _
i t . _ _

各行各列を文字列とみなしcalcCheckCharacterで検査文字を生成し最右列と最下行に格納すると以下のようになります。

i p a _ _ f
t e s t s i
m a k e _ n
i t . _ _ h
r a v b l

各行各列を文字列とみなしvalidateCheckCharacterで検証した結果、全て誤りがなかった場合にのみ検査文字付表に誤りが無いことが分かります。



以上で解説は終了です。
最後の話は水平垂直パリティチェック*1みたいな話ですね。

このように文字列に検査文字を付けておくことで、送信途中に改竄がなかったかなどのセキュリティチェックができます。最初に考えた人は凄いですね〜。


長くなりましたが閲覧ありがとうございました。
よろしければ読者登録とスターお願いします。