CSS3 – color/background-color

2020-11-30 / tau / コメントする

概要

colorは前景色、background-colorは背景色を指定する。

書式

color: 色指定;

background-color: 色指定；

値

色指定にいくつかの方法がある。

カラーネーム: red, grayなど特定の色に対応したキーワードで設定。
16進コード(6桁): #RRGGBBの6桁で指定する。2桁1バイトごとにR, G, Bに対応。
16進コード(3桁): #RGBの3桁で指定する。#RGBという指定は#RRGGBBと各色を繰り返した値に相当する。
rgb(r, g, b)/rgb(r, g, b, a): 3つの引数はそれぞれ0～255の整数で、R, G, Bに対応。4つ目の引数がある場合は透過度を表し、実数で指定する。
hsl(h, s, l)/hsl(h, s, l, a): 色相(Hue)、彩度(Saturation)、輝度(Lightness)を実数で指定する。4つ目の引数がある場合は透過度を表し、実数で指定する。

CSS3 – 基本色

2020-11-29 / tau / コメントする

基本の16色とカラーネーム、カラーコードは以下の通り。

色	カラーネーム	カラーコード
	black	#000000
	aqua	#00FFFF
	blue	#0000FF
	fuchsia	#FF00FF
	gray	#808080
	green	#008000
	lime	#00FF00
	maroon	#800000
	navy	#000080
	olive	#808000
	purple	#800080
	red	#FF0000
	silver	#C0C0C0
	teal	#008080

HTML5 – a～アンカー

2020-11-29 / tau / コメントする

書式

<a href="href属性" target="target属性">...</a>

属性

href属性

リンク先のURL、アンカーリンク（ページ内リンク）を組み合わせて指定する。

target属性

_self	現在のページでリンク先を開く（デフォルト）
_blank	新しいページ／タブでリンク先を開く

Breast cancer wisconsinデータセットの俯瞰

2020-03-20 / tau / コメントする

概要

breast_cancerデータは、複数の乳癌患者に関する細胞診の結果と診断結果に関するデータセットで、569人について腫瘤の細胞診に関する30の特徴量と診断結果（悪性／良性）が格納されている。このデータセットについて、irisデータセットと同じ流れで、一般的なグラフによる可視化によって俯瞰してみる。

各特徴量と診断結果

30個の特徴量について悪性と良性に色分けしてヒストグラムを描いてみると、特徴量によって悪性と良性がある程度分かれているものと、重なりが大きいものがあることがわかる。

特徴量の数は多いが、低い次元で見る限りは明確に悪性／良性を分離できる特徴量はあまり多くなさそうである。

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import load_breast_cancer

cancer_ds = load_breast_cancer()

X = cancer_ds.data
y = cancer_ds.target
feature_names = cancer_ds.feature_names
target_names = cancer_ds.target_names

fig, axs = plt.subplots(6, 5, figsize=(10.0, 8))

plt.rcParams['font.size'] = 8
fig.subplots_adjust(hspace=0.4, wspace=0.4)
axs_1d = axs.reshape(1, -1)[0]

for ax, feature in zip(axs_1d, range(len(feature_names))):

    xf = X[:, feature]
    range_min = np.min(xf)
    range_max = np.max(xf)

    ax.set_title("{}({})".format(feature_names[feature], feature))
    ax.hist(xf[y==0], range=(range_min, range_max), bins=20,
        color='b', ec='k', alpha=0.5, label="b")
    ax.hist(xf[y==1], range=(range_min, range_max), bins=20,
        color='r', ec='k', alpha=0.5, label="m")
    ax.tick_params(left=False, bottom=False, labelleft=False, labelbottom=False)

handler, label = axs_1d[0].get_legend_handles_labels()
fig.legend(handler, label, ncol=2, loc='lower center')

plt.show()

import numpy as np

import matplotlib.pyplot as plt

from sklearn.datasets import load_breast_cancer

cancer_ds = load_breast_cancer()

X = cancer_ds.data

y = cancer_ds.target

feature_names = cancer_ds.feature_names

target_names = cancer_ds.target_names

fig, axs = plt.subplots(6, 5, figsize=(10.0, 8))

plt.rcParams['font.size'] = 8

fig.subplots_adjust(hspace=0.4, wspace=0.4)

axs_1d = axs.reshape(1, -1)[0]

for ax, feature in zip(axs_1d, range(len(feature_names))):

xf = X[:, feature]

range_min = np.min(xf)

range_max = np.max(xf)

ax.set_title("{}({})".format(feature_names[feature], feature))

ax.hist(xf[y==0], range=(range_min, range_max), bins=20,

color='b', ec='k', alpha=0.5, label="b")

ax.hist(xf[y==1], range=(range_min, range_max), bins=20,

color='r', ec='k', alpha=0.5, label="m")

ax.tick_params(left=False, bottom=False, labelleft=False, labelbottom=False)

handler, label = axs_1d[0].get_legend_handles_labels()

fig.legend(handler, label, ncol=2, loc='lower center')

plt.show()

2つの特徴量同士の関係

特徴量が30個あるので、scatter_matrixやpairplotで全ての特徴量の関係を見るのはあまり得策ではない。そこで、30個の特徴量の中から、悪性／良性が分かれているものを選んで相互の関係を見てみる。

ここでは、双方の分布の山ができるだけ離れており、重なっている部分が少ないものとして、平均凹度、最大半径、最大周囲長、最大凹点数を選んだ。

最大半径と最大周囲長はかなり相関が高く、双方を組み合わせてもあまり効果はなさそうだ。もともと半径と周囲長は円形なら比例関係にあるので当然の結果だろう。

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
from sklearn.datasets import load_breast_cancer
from mpl_toolkits.mplot3d import Axes3D

cancer_ds = load_breast_cancer()
X = cancer_ds.data
y = cancer_ds.target
feature_names = cancer_ds.feature_names
target_names = cancer_ds.target_names

X06 = X[:, 6].reshape(-1, 1)
X20 = X[:, 20].reshape(-1, 1)
X22 = X[:, 22].reshape(-1, 1)
X27 = X[:, 27].reshape(-1, 1)
X_new = np.hstack((X06, X20, X22, X27))
fname_new = np.array(
    [feature_names[6], feature_names[20], feature_names[22], feature_names[27]])

df = pd.DataFrame(X_new, columns=fname_new)

df['target'] = cancer_ds.target
df.loc[df['target']==0, 'target'] = "malignant"
df.loc[df['target']==1, 'target'] = "benign"

g = sns.pairplot(df, hue='target', plot_kws={'alpha':0.5})

fig = plt.figure()
ax = fig.add_subplot(111, projection='3d')
ax.scatter(X06[y==0], X20[y==0], X27[y==0], alpha=0.5, label="malignant")
ax.scatter(X06[y==1], X20[y==1], X27[y==1], alpha=0.5, label="benign")
ax.legend()

plt.show()

import numpy as np

import pandas as pd

import matplotlib.pyplot as plt

import seaborn as sns

from sklearn.datasets import load_breast_cancer

from mpl_toolkits.mplot3d import Axes3D

cancer_ds = load_breast_cancer()

X = cancer_ds.data

y = cancer_ds.target

feature_names = cancer_ds.feature_names

target_names = cancer_ds.target_names

X06 = X[:, 6].reshape(-1, 1)

X20 = X[:, 20].reshape(-1, 1)

X22 = X[:, 22].reshape(-1, 1)

X27 = X[:, 27].reshape(-1, 1)

X_new = np.hstack((X06, X20, X22, X27))

fname_new = np.array(

[feature_names[6], feature_names[20], feature_names[22], feature_names[27]])

df = pd.DataFrame(X_new, columns=fname_new)

df['target'] = cancer_ds.target

df.loc[df['target']==0, 'target'] = "malignant"

df.loc[df['target']==1, 'target'] = "benign"

g = sns.pairplot(df, hue='target', plot_kws={'alpha':0.5})

fig = plt.figure()

ax = fig.add_subplot(111, projection='3d')

ax.scatter(X06[y==0], X20[y==0], X27[y==0], alpha=0.5, label="malignant")

ax.scatter(X06[y==1], X20[y==1], X27[y==1], alpha=0.5, label="benign")

ax.legend()

plt.show()

3つの特徴量の関係

最後に、平均凹度、最大半径、最大凹点数の3つの特徴量の関係を3次元化してみた。結果の図を回転させて、できるだけ境界面に沿うような角度から見たのが以下の図である。個々の特徴量だけで見るよりはかなり分離の精度は高くなっている。

上記の3d可視化とその前のpairplotのコードは下記の通り。

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
from sklearn.datasets import load_breast_cancer
from mpl_toolkits.mplot3d import Axes3D

cancer_ds = load_breast_cancer()
X = cancer_ds.data
y = cancer_ds.target
feature_names = cancer_ds.feature_names
target_names = cancer_ds.target_names

X06 = X[:, 6].reshape(-1, 1)
X20 = X[:, 20].reshape(-1, 1)
X22 = X[:, 22].reshape(-1, 1)
X27 = X[:, 27].reshape(-1, 1)
X_new = np.hstack((X06, X20, X22, X27))
fname_new = np.array(
    [feature_names[6], feature_names[20], feature_names[22], feature_names[27]])

df = pd.DataFrame(X_new, columns=fname_new)

df['target'] = cancer_ds.target
df.loc[df['target']==0, 'target'] = "malignant"
df.loc[df['target']==1, 'target'] = "benign"

g = sns.pairplot(df, hue='target', plot_kws={'alpha':0.5})

fig = plt.figure()
ax = fig.add_subplot(111, projection='3d')
ax.scatter(X06[y==0], X20[y==0], X27[y==0], alpha=0.5, label="malignant")
ax.scatter(X06[y==1], X20[y==1], X27[y==1], alpha=0.5, label="benign")
ax.legend()

plt.show()

import numpy as np

import pandas as pd

import matplotlib.pyplot as plt

import seaborn as sns

from sklearn.datasets import load_breast_cancer

from mpl_toolkits.mplot3d import Axes3D

cancer_ds = load_breast_cancer()

X = cancer_ds.data

y = cancer_ds.target

feature_names = cancer_ds.feature_names

target_names = cancer_ds.target_names

X06 = X[:, 6].reshape(-1, 1)

X20 = X[:, 20].reshape(-1, 1)

X22 = X[:, 22].reshape(-1, 1)

X27 = X[:, 27].reshape(-1, 1)

X_new = np.hstack((X06, X20, X22, X27))

fname_new = np.array(

[feature_names[6], feature_names[20], feature_names[22], feature_names[27]])

df = pd.DataFrame(X_new, columns=fname_new)

df['target'] = cancer_ds.target

df.loc[df['target']==0, 'target'] = "malignant"

df.loc[df['target']==1, 'target'] = "benign"

g = sns.pairplot(df, hue='target', plot_kws={'alpha':0.5})

fig = plt.figure()

ax = fig.add_subplot(111, projection='3d')

ax.scatter(X06[y==0], X20[y==0], X27[y==0], alpha=0.5, label="malignant")

ax.scatter(X06[y==1], X20[y==1], X27[y==1], alpha=0.5, label="benign")

ax.legend()

plt.show()

Python3 – 浮動小数点の誤差

2019-09-28 / tau / コメントする

概要

Pythonで浮動小数点誤差に行き当たった。

コンソール上にはErrorが表示され計算結果はnanになるが、配列を使っていたので、問題がどこで生じているかわかるまでにちょっと手間取った。

解析上の考え

中心が(cx, cy)、半径がrの円を考え、x座標を与えてそれに対する円上のy座標を計算しようとしていたとき。

このような円の方程式は、陰関数では以下のようになる。

$\begin{equation*} (x - c_x)^2 + (y - c_y)^2 = r^2 \end{equation*}$

これをy ≥ 0で解くと、

$\begin{equation*} y = c_y + \sqrt{r^2 - (x - c_x)^2} \end{equation*}$

問題の発生

中心の座標が(0.5, 0.5)、半径が0.3となるような円が欲しかったので、xの定義域を0.3～0.8として次のようなコードをPythonで書いた。実際はy < 0の部分も必要で、円周上だけでなく内部の座標をランダムに計算し、それらの相関係数を計算するというものだったが、本質的には変わらない。

import numpy as np

r = 0.3
cx, cy = 0.5, 0.5

x = np.linspace(0.3, 0.8, 11)
y = np.array([cy + np.sqrt(r**2 - (x - cx)**2)])

cor = np.sum((x - x.mean()) * (y - y.mean()) / x.std() / y.std())
print(cor)

import numpy as np

r = 0.3

cx, cy = 0.5, 0.5

x = np.linspace(0.3, 0.8, 11)

y = np.array([cy + np.sqrt(r**2 - (x - cx)**2)])

cor = np.sum((x - x.mean()) * (y - y.mean()) / x.std() / y.std())

print(cor)

その結果、cor=nanとなってしまう。実行時にsqrtの計算で警告が出ている。

C:\Users\tomo\Google �h���C�u\IT_and_Mobile\dev\python\trouble\float.py:7: RuntimeWarning: invalid value encountered in sqrt
  y = np.array([cy + np.sqrt(r**2 - (x - cx)**2)])
nan

C:\Users\tomo\Google �h��C�u\IT_and_Mobile\dev\python\trouble\float.py:7: RuntimeWarning: invalid value encountered in sqrt

y = np.array([cy + np.sqrt(r**2 - (x - cx)**2)])

nan

そこで配列x、yを表示させてみると、yの最後の要素がnanになっている。

print(x)
print(y)

1 2	print(x) print(y)

[0.3  0.35 0.4  0.45 0.5  0.55 0.6  0.65 0.7  0.75 0.8 ]
[[0.7236068  0.75980762 0.78284271 0.79580399 0.8        0.79580399
  0.78284271 0.75980762 0.7236068  0.66583124        nan]]

[0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.7 0.75 0.8 ]

[[0.7236068 0.75980762 0.78284271 0.79580399 0.8 0.79580399

0.78284271 0.75980762 0.7236068 0.66583124 nan]]

さらに、sqrtの中を表示させてみる。

for xx in x: print(r**2, (xx - cx)**2)

1	for xx in x: print(r2, (xx - cx)2)

0.09 0.04000000000000001
0.09 0.022500000000000006
0.09 0.009999999999999995
0.09 0.0024999999999999988
0.09 0.0
0.09 0.0025000000000000044
0.09 0.010000000000000018
0.09 0.022500000000000006
0.09 0.03999999999999998
0.09 0.0625
0.09 0.09000000000000002

0.09 0.04000000000000001

0.09 0.022500000000000006

0.09 0.009999999999999995

0.09 0.0024999999999999988

0.09 0.0

0.09 0.0025000000000000044

0.09 0.010000000000000018

0.09 0.022500000000000006

0.09 0.03999999999999998

0.09 0.0625

0.09 0.09000000000000002

最後のところで差し引かれる方の値がごくわずかに大きくなっていて、その結果根号の中が負の値となってnanが発生したらしい。

解決策

linspaceの範囲を円周上の上限・下限から少し内側にすることも考えられるが、今回はnumpy.around()を使った。

numpy.around(a, decimals=0)

これは値aを小数点以下decimalsの桁数で丸めてくれるもので、今回は小数点以下10桁目で丸めてみた。

import numpy as np

r = 0.3
cx, cy = 0.5, 0.5

x = np.linspace(0.3, 0.8, 11)
y = np.array([cy + np.sqrt(r**2 - np.around(x - cx, 10)**2)])

cor = np.sum((x - x.mean()) * (y - y.mean()) / x.std() / y.std())
print(cor)

import numpy as np

r = 0.3

cx, cy = 0.5, 0.5

x = np.linspace(0.3, 0.8, 11)

y = np.array([cy + np.sqrt(r**2 - np.around(x - cx, 10)**2)])

cor = np.sum((x - x.mean()) * (y - y.mean()) / x.std() / y.std())

print(cor)

この結果、正常に計算。

-6.625370822144879

1	-6.625370822144879

注意点

解析上値が等しくなる（差し引きゼロになる）ような場合でも、浮動小数点ではごくわずかな誤差のため、エラーとなることがある
numpy.linspace()を使うと上限・下限の間を等分してくれるのでありがたいが、上限・下限自体が他の値と厳密に等しくなければならない場合には、浮動小数点の誤差が生じるため注意が必要

クイックソート

2019-09-08 / tau / コメントする

概要

クイックソートは、特定の値（ピボット）を基準にして、データの先頭と最後尾から1つずつ中央に近づけていきながら、ピボットより小さなデータが前に、大きなデータが後ろに配置されるように交換し、その処理を再帰的に行っていく。

考え方

以下2段階に分けて、与えられたデータ列をピボット以上・未満に振り分ける操作と、それらを再帰的に実行していく操作を示す。

ピボットの取り方にはいろいろあるようだが、ここでは与えられたデータの先頭と最後尾の値の平均値とする。

部分列に対する操作

以下の図で、4,6,2,…5のデータの部分列が与えられたとする。その際の操作は以下の通り。

⓪　部分列の先頭と最後尾のデータの平均を計算し、それをピボットとして設定(4.5)
①　左からピボット以上のデータを探索(6≥4.5)、右からピボット未満のデータを探索(1<4.5)
②　探索した左右のデータを交換
③　さらに左からピボット以上のデータを探索(7≥4.5)、右からピボット未満のデータを探索(0<4.5)
④　探索した左右のデータを交換
⑤　さらに探索を進めた結果、左右のポインターが交差
- このとき、境界より左にピボット未満、境界より右にピボット以上のデータが格納されている
- 3を境界とし、境界を含む左側とそれより右側の部分列に分けて、再帰的に探索を行う

再帰処理

部分列の操作を踏まえたうえで、それらの再帰的な処理の様子を下図に示す。図中、それぞれの線種や背景色の意味は以下の通り

二重枠囲みはピボットの値
赤はピボット以上のデータ
青はピボット未満のデータ
黄色は境界値
緑色は位置が確定したデータ

各段階の処理は以下の通り。

①　元の列からピボット以上／未満のデータを振り分け
②　左側の部分列に対する再帰1段目、ピボットによる振り分け
③　左側の部分列に対する再帰2段目、ピボットによる振り分け
④　左側の部分列に対する再帰3段目、ピボットによる振り分け
⑤⑥　左側・右側の再帰終了、0と1の位置確定
⑦　右側の部分列に対する再帰3段目
⑧⑨　左側・右側の再帰終了、2と3の位置確定
⑩　右側の再帰終了、4の位置確定（ここで再帰1段目の左側終了）
⑪　右側の部分列に対する再帰1段目、ピボットによる振り分け
⑫　左側の再帰終了、5の位置確定
⑬　右側の再帰2段目、ピボットによる振り分け
⑭⑮　左側・右側の再帰終了、6と7の位置確定

コード

以下はPythonによる実装。全体のデータ列に対して位置を指定して並べ替えを実行する再帰関数quick_sort_core()を定義し、全体列に対してこれを呼び出す入口の関数quick_sort()を定義。

def quick_sort(data):
    quick_sort_core(data, 0, len(data)-1)

def quick_sort_core(data, org_left, org_right):
    if org_left == org_right: return

    left = org_left
    right = org_right
    pivot = (data[org_left] + data[org_right]) / 2

    while True:
        while data[left] < pivot:
            left += 1
            if left > org_right: return
        while data[right] >= pivot:
            right -= 1
            if right < org_left: return
        if left >= right:
            border = right
            break
        data[left], data[right] = data[right], data[left]

    quick_sort_core(data, org_left, border)
    quick_sort_core(data, border+1, org_right)

def quick_sort(data):

quick_sort_core(data, 0, len(data)-1)

def quick_sort_core(data, org_left, org_right):

if org_left == org_right: return

left = org_left

right = org_right

pivot = (data[org_left] + data[org_right]) / 2

while True:

while data[left] < pivot:

left += 1

if left > org_right: return

while data[right] >= pivot:

right -= 1

if right < org_left: return

if left >= right:

border = right

break

data[left], data[right] = data[right], data[left]

quick_sort_core(data, org_left, border)

quick_sort_core(data, border+1, org_right)

例示したデータに対して実行。

data = [4, 6, 2, 7, 3, 0, 1, 5]
quick_sort(data)
print(data)

# [0, 1, 2, 3, 4, 5, 6, 7]

data = [4, 6, 2, 7, 3, 0, 1, 5]

quick_sort(data)

print(data)

# [0, 1, 2, 3, 4, 5, 6, 7]

要素がすべて同じで、要素数が偶数・奇数の場合も正常に動作。

data = [1, 1, 1, 1]
quick_sort(data)
print(data)

data = [1, 1, 1, 1, 1]
quick_sort(data)
print(data)

# [1, 1, 1, 1]
# [1, 1, 1, 1, 1]

data = [1, 1, 1, 1]

quick_sort(data)

print(data)

data = [1, 1, 1, 1, 1]

quick_sort(data)

print(data)

# [1, 1, 1, 1]

# [1, 1, 1, 1, 1]

同じ要素が複数含まれる場合も正常に動作。

data = [2, 1, 2, 1, 1]
print(data)
quick_sort(data)
print(data)

# [1, 1, 1, 2, 2]

data = [2, 1, 2, 1, 1]

print(data)

quick_sort(data)

print(data)

# [1, 1, 1, 2, 2]

動作状況の確認

並べ替えの動作中の状況を以下のコードで確認。各所にprint()関数をちりばめてみる。

import random

def quick_sort(data):
    quick_sort_core(data, 0, len(data)-1)

def quick_sort_core(data, org_left, org_right):
    print('function start')
    print(data[org_left:org_right+1], end=' ')
    if org_left == org_right:
        print('return')
        return

    left = org_left
    right = org_right
    pivot = (data[org_left] + data[org_right]) / 2
    print('pivot', pivot, '<-', data[org_left], data[org_right])

    while True:
        print(data[org_left:org_right+1], pivot, 'check', data[left], data[right])
        while data[left] < pivot:
            left += 1
            print(data[org_left:org_right+1], 'left+1 ->', data[left])
            if left > org_right:
                print(data[left], '>', data[org_right], 'return')
                return
        while data[right] >= pivot:
            right -= 1
            print(data[org_left:org_right+1], 'right-1 ->', data[right])
            if right < org_left:
                print(data[org_left], '>', data[right], 'return')
                return
        if left >= right:
            border = right
            print(data[left], '>=', data[right], 'border=', data[border])
            break
        data[left], data[right] = data[right], data[left]
        print(data[org_left:org_right+1], 'switched', data[left], data[right])

    quick_sort_core(data, org_left, border)
    quick_sort_core(data, border+1, org_right)

data = [4, 6, 2, 7, 3, 0, 1, 5]
quick_sort(data)
print(data)

import random

def quick_sort(data):

quick_sort_core(data, 0, len(data)-1)

def quick_sort_core(data, org_left, org_right):

print('function start')

print(data[org_left:org_right+1], end=' ')

if org_left == org_right:

print('return')

return

left = org_left

right = org_right

pivot = (data[org_left] + data[org_right]) / 2

print('pivot', pivot, '<-', data[org_left], data[org_right])

while True:

print(data[org_left:org_right+1], pivot, 'check', data[left], data[right])

while data[left] < pivot:

left += 1

print(data[org_left:org_right+1], 'left+1 ->', data[left])

if left > org_right:

print(data[left], '>', data[org_right], 'return')

return

while data[right] >= pivot:

right -= 1

print(data[org_left:org_right+1], 'right-1 ->', data[right])

if right < org_left:

print(data[org_left], '>', data[right], 'return')

return

if left >= right:

border = right

print(data[left], '>=', data[right], 'border=', data[border])

break

data[left], data[right] = data[right], data[left]

print(data[org_left:org_right+1], 'switched', data[left], data[right])

quick_sort_core(data, org_left, border)

quick_sort_core(data, border+1, org_right)

data = [4, 6, 2, 7, 3, 0, 1, 5]

quick_sort(data)

print(data)

動作結果は以下の通りで、再帰的に実行されているのがわかる。

function start
[4, 6, 2, 7, 3, 0, 1, 5] pivot 4.5 <- 4 5
[4, 6, 2, 7, 3, 0, 1, 5] 4.5 check 4 5
[4, 6, 2, 7, 3, 0, 1, 5] left+1 -> 6
[4, 6, 2, 7, 3, 0, 1, 5] right-1 -> 1
[4, 1, 2, 7, 3, 0, 6, 5] switched 1 6
[4, 1, 2, 7, 3, 0, 6, 5] 4.5 check 1 6
[4, 1, 2, 7, 3, 0, 6, 5] left+1 -> 2
[4, 1, 2, 7, 3, 0, 6, 5] left+1 -> 7
[4, 1, 2, 7, 3, 0, 6, 5] right-1 -> 0
[4, 1, 2, 0, 3, 7, 6, 5] switched 0 7
[4, 1, 2, 0, 3, 7, 6, 5] 4.5 check 0 7
[4, 1, 2, 0, 3, 7, 6, 5] left+1 -> 3
[4, 1, 2, 0, 3, 7, 6, 5] left+1 -> 7
[4, 1, 2, 0, 3, 7, 6, 5] right-1 -> 3
7 >= 3 border= 3
function start
[4, 1, 2, 0, 3] pivot 3.5 <- 4 3
[4, 1, 2, 0, 3] 3.5 check 4 3
[3, 1, 2, 0, 4] switched 3 4
[3, 1, 2, 0, 4] 3.5 check 3 4
[3, 1, 2, 0, 4] left+1 -> 1
[3, 1, 2, 0, 4] left+1 -> 2
[3, 1, 2, 0, 4] left+1 -> 0
[3, 1, 2, 0, 4] left+1 -> 4
[3, 1, 2, 0, 4] right-1 -> 0
4 >= 0 border= 0
function start
[3, 1, 2, 0] pivot 1.5 <- 3 0
[3, 1, 2, 0] 1.5 check 3 0
[0, 1, 2, 3] switched 0 3
[0, 1, 2, 3] 1.5 check 0 3
[0, 1, 2, 3] left+1 -> 1
[0, 1, 2, 3] left+1 -> 2
[0, 1, 2, 3] right-1 -> 2
[0, 1, 2, 3] right-1 -> 1
2 >= 1 border= 1
function start
[0, 1] pivot 0.5 <- 0 1
[0, 1] 0.5 check 0 1
[0, 1] left+1 -> 1
[0, 1] right-1 -> 0
1 >= 0 border= 0
function start
[0] return
function start
[1] return
function start
[2, 3] pivot 2.5 <- 2 3
[2, 3] 2.5 check 2 3
[2, 3] left+1 -> 3
[2, 3] right-1 -> 2
3 >= 2 border= 2
function start
[2] return
function start
[3] return
function start
[4] return
function start
[7, 6, 5] pivot 6.0 <- 7 5
[7, 6, 5] 6.0 check 7 5
[5, 6, 7] switched 5 7
[5, 6, 7] 6.0 check 5 7
[5, 6, 7] left+1 -> 6
[5, 6, 7] right-1 -> 6
[5, 6, 7] right-1 -> 5
6 >= 5 border= 5
function start
[5] return
function start
[6, 7] pivot 6.5 <- 6 7
[6, 7] 6.5 check 6 7
[6, 7] left+1 -> 7
[6, 7] right-1 -> 6
7 >= 6 border= 6
function start
[6] return
function start
[7] return
[0, 1, 2, 3, 4, 5, 6, 7]

function start

[4, 6, 2, 7, 3, 0, 1, 5] pivot 4.5 <- 4 5

[4, 6, 2, 7, 3, 0, 1, 5] 4.5 check 4 5

[4, 6, 2, 7, 3, 0, 1, 5] left+1 -> 6

[4, 6, 2, 7, 3, 0, 1, 5] right-1 -> 1

[4, 1, 2, 7, 3, 0, 6, 5] switched 1 6

[4, 1, 2, 7, 3, 0, 6, 5] 4.5 check 1 6

[4, 1, 2, 7, 3, 0, 6, 5] left+1 -> 2

[4, 1, 2, 7, 3, 0, 6, 5] left+1 -> 7

[4, 1, 2, 7, 3, 0, 6, 5] right-1 -> 0

[4, 1, 2, 0, 3, 7, 6, 5] switched 0 7

[4, 1, 2, 0, 3, 7, 6, 5] 4.5 check 0 7

[4, 1, 2, 0, 3, 7, 6, 5] left+1 -> 3

[4, 1, 2, 0, 3, 7, 6, 5] left+1 -> 7

[4, 1, 2, 0, 3, 7, 6, 5] right-1 -> 3

7 >= 3 border= 3

function start

[4, 1, 2, 0, 3] pivot 3.5 <- 4 3

[4, 1, 2, 0, 3] 3.5 check 4 3

[3, 1, 2, 0, 4] switched 3 4

[3, 1, 2, 0, 4] 3.5 check 3 4

[3, 1, 2, 0, 4] left+1 -> 1

[3, 1, 2, 0, 4] left+1 -> 2

[3, 1, 2, 0, 4] left+1 -> 0

[3, 1, 2, 0, 4] left+1 -> 4

[3, 1, 2, 0, 4] right-1 -> 0

4 >= 0 border= 0

function start

[3, 1, 2, 0] pivot 1.5 <- 3 0

[3, 1, 2, 0] 1.5 check 3 0

[0, 1, 2, 3] switched 0 3

[0, 1, 2, 3] 1.5 check 0 3

[0, 1, 2, 3] left+1 -> 1

[0, 1, 2, 3] left+1 -> 2

[0, 1, 2, 3] right-1 -> 2

[0, 1, 2, 3] right-1 -> 1

2 >= 1 border= 1

function start

[0, 1] pivot 0.5 <- 0 1

[0, 1] 0.5 check 0 1

[0, 1] left+1 -> 1

[0, 1] right-1 -> 0

1 >= 0 border= 0

function start

[0] return

function start

[1] return

function start

[2, 3] pivot 2.5 <- 2 3

[2, 3] 2.5 check 2 3

[2, 3] left+1 -> 3

[2, 3] right-1 -> 2

3 >= 2 border= 2

function start

[2] return

function start

[3] return

function start

[4] return

function start

[7, 6, 5] pivot 6.0 <- 7 5

[7, 6, 5] 6.0 check 7 5

[5, 6, 7] switched 5 7

[5, 6, 7] 6.0 check 5 7

[5, 6, 7] left+1 -> 6

[5, 6, 7] right-1 -> 6

[5, 6, 7] right-1 -> 5

6 >= 5 border= 5

function start

[5] return

function start

[6, 7] pivot 6.5 <- 6 7

[6, 7] 6.5 check 6 7

[6, 7] left+1 -> 7

[6, 7] right-1 -> 6

7 >= 6 border= 6

function start

[6] return

function start

[7] return

[0, 1, 2, 3, 4, 5, 6, 7]

バブルソート

2019-09-02 / tau / コメントする

概要

バブルソートは、すべてのデータを一つずつチェックしながら、（昇順の場合）最も大きいデータを後ろに押し出していく。

たとえば以下のような初期データ列があるとする。

3, 4, 1, 2, 0

最初のループでは、全データの中で最大のものが一番最後に来るようにする。

3, 4, 1, 2, 0
3, 4, 1, 2, 0　→　3, 1, 4, 2, 0
3, 1, 4, 2, 0　→　3, 1, 2, 4, 0
3, 1, 2, 4, 0　→　3, 1, 2, 0, 4

3, 1, 2, 0, 4　→　1, 3, 2, 0, 4
1, 3, 2, 0, 4　→　1, 2, 3, 0, 4
1, 2, 3, 0, 4　→　1, 2, 0, 3, 4

1, 2, 0, 3, 4
1, 2, 0, 3, 4　→　1, 0, 2, 3, 4

1, 0, 2, 3, 4　→　0, 1, 2, 3, 4

ループ回数は $(n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2}$

コード

Pythonによるバブルソートのコード例。

def bubble_sort(data):
    for m in reversed(range(0, len(data))):
        for n in range(0, m):
            print(data, end=' -> ')
            if data[n] > data[n+1]:
                data[n], data[n+1] = data[n+1], data[n]
            print(data)
        print()


data = [3, 4, 1, 2, 0]
bubble_sort(data)

# [0, 1, 2, 3, 4]

def bubble_sort(data):

for m in reversed(range(0, len(data))):

for n in range(0, m):

print(data, end=' -> ')

if data[n] > data[n+1]:

data[n], data[n+1] = data[n+1], data[n]

print(data)

print()

data = [3, 4, 1, 2, 0]

bubble_sort(data)

# [0, 1, 2, 3, 4]

安定ソート

バブルソートは安定ソートである。すなわち、同じソートキーのデータについて、ソート後も元の順序が保持される。

def bubble_sort_2d(data):
    for m in reversed(range(0, len(data))):
        for n in range(0, m):
            print(data, end=' -> ')
            if data[n][1] > data[n+1][1]:
                data[n], data[n+1] = data[n+1], data[n]
            print(data)
        print()


data = [
    [1, 50],
    [2, 40],
    [3, 30],
    [4, 30],
    [5, 40]]
bubble_sort_2d(data)

# [[3, 30], [4, 30], [2, 40], [5, 40], [1, 50]]

def bubble_sort_2d(data):

for m in reversed(range(0, len(data))):

for n in range(0, m):

print(data, end=' -> ')

if data[n][1] > data[n+1][1]:

data[n], data[n+1] = data[n+1], data[n]

print(data)

print()

data = [

[1, 50],

[2, 40],

[3, 30],

[4, 30],

[5, 40]]

bubble_sort_2d(data)

# [[3, 30], [4, 30], [2, 40], [5, 40], [1, 50]]

公開鍵と秘密鍵

2019-08-15 / tau / コメントする

暗号化

暗号化の流れ

公開鍵(public key)と秘密鍵(secret/private key)を使った暗号化の流れは以下のとおり。

受信側が公開鍵と秘密鍵を準備し、公開鍵を公開
送信側は公開鍵を使って平文を暗号化し、受信側に送信
受信側は秘密鍵を使って暗号文を平文に復号（秘密鍵を持っている受信側しか複合できない）

この手順を、もう少し詳しく見ると以下のとおり。

受信側が、公開鍵として $(p, n)$ 、秘密鍵として $(s, n)$ を準備し、公開鍵を公開する
送信側は、公開鍵を使って平文(plaintext)を暗号化し、暗号文(ciphertext)を生成、受信側に送信
- $T_c = T_p^p \mod n$
受信側は、受け取った暗号文を秘密鍵を使って複合
- $T_p = T_c^s \mod n$

公開鍵・秘密鍵の算出手順

素数の組の準備

まず、受信側で2つの素数 $q, r$ を準備する。例えば $q=5, r=11$ とする。

素数の積nの計算

次に、 $q, r$ の積を計算し、その値を $n$ とする。

(1) $\begin{equation*} n = qr \end{equation*}$

例えば $n=5 \times 11 = 55$ 。

計算準備

$q-1, r-1$ の最小公倍数を計算しておく。

(2) $\begin{equation*} L = LCM(p-1, q-1) \end{equation*}$

例えば、 $L = LCM(4, 10) = 20$ 。

公開鍵の計算

$p, L$ が互いに素であるような $p$ を選ぶ。ここで公開鍵は $(p, n)$ となる。

(3) $\begin{equation*} p \; : \; GCM(p, L) = 1 \end{equation*}$

例えば、 $p = 3$ とすると、公開鍵は $(3, 55)$

秘密鍵の計算

(4) $\begin{equation*} s \; : \; sp \mod L = 1 \end{equation*}$

例えば、 $e = 7$ とすると、 $3 \times 7 \mod 20 = 1$ となり、秘密鍵は $(7, 55)$ 。

簡略化した暗号化の例

鍵の準備

先の公開鍵・秘密鍵の算出で例示した値を使って、暗号化の流れを見てみる。

2つの素数の組 $p=5, q=11$ を準備し、 $n = pq = 5 \times 11 = 55$ を計算した。

さらに $LCM(q-1, r-1)$ の値から、公開鍵 $(p, n)$ 、秘密鍵 $(s, n)$ を以下の様に得た。

(5) $\begin{eqnarray*} (p, n) &=& (3, 55) \\ (s, n) &=& (7, 55) \end{eqnarray*}$

暗号化

平文として数列 $12, 26, 33$ を考え、送信側で公開鍵を使って、この平文を暗号化する。

(6) $\begin{eqnarray*} 12 &\rightarrow& 12^p \mod n = 12^3 \mod 55 = 1728 \mod 55 = 23\\ 26 &\rightarrow& 26^p \mod n = 26^3 \mod 55 = 17576 \mod 55 = 31 \\ 33 &\rightarrow& 33^p \mod n = 33^3 \mod 55 = 35937 \mod 55 = 22 \end{eqnarray*}$

復号

受信側は受け取った暗号文を、秘密鍵を使って複合する。

(7) $\begin{eqnarray*} 23 &\rightarrow& 23^s \mod n = 23^7 \mod 55 = 3404825447 \mod 55 = 12\\ 31 &\rightarrow& 31^s \mod n = 31^7 \mod 55 = 27512614111 \mod 55 = 26\\ 22 &\rightarrow& 22^s \mod n = 22^7 \mod 55 = 2494357888 \mod 55 = 33 \end{eqnarray*}$

電子証明

電子証明の流れ

公開鍵と秘密鍵を使う順序を逆にすると、電子証明に仕える。その流れは以下のとおり。

発信側が公開鍵と秘密鍵を準備し、公開鍵を公開
発信側は秘密鍵を使って平文を暗号化し、受信側に送信
受信側は公開鍵を使って暗号文を平文に復号し、証明を確認（秘密鍵を持っている発信側しか公開鍵で正しい平文に復号可能な暗号文を生成できない）

簡略化した電子証明の例

暗号化の例と同じ公開鍵・秘密鍵を使って、電子証明の例を確認する。

証明書の暗号化

発信側で証明書の平文 $12, 26, 33$ を準備し、これを秘密鍵を使って暗号化。

(8) $\begin{eqnarray*} 12 &\rightarrow& 12^s \mod n = 12^7 \mod 55 = 35831808 \mod 55 = 23\\ 26 &\rightarrow& 26^s \mod n = 26^7 \mod 55 = 8031810176 \mod 55 = 16 \\ 33 &\rightarrow& 33^s \mod n = 33^7 \mod 55 = 42618442977 \mod 55 = 22 \end{eqnarray*}$

受信側は、公開鍵を使って暗号文を復号し、平文を確認（秘密鍵で暗号化した文のみ、公開鍵で適正に複合できる）。

(9) $\begin{eqnarray*} 23 &\rightarrow& 23^p \mod n = 23^3 \mod 55 = 12167 \mod 55 = 12\\ 16 &\rightarrow& 16^p \mod n = 16^3 \mod 55 = 4096 \mod 55 = 26 \\ 22 &\rightarrow& 22^p \mod n = 22^3 \mod 55 = 10648 \mod 55 = 33 \end{eqnarray*}$

ハッシュ

2019-08-15 / tau / コメントする

ハッシュ関数のことを考えてみようと、自分なりにトライしてみた。

簡単すぎる例
文字列の文字コードを足し込んでいくという単純な方法。

剰余を使った例
剰余を使った例。文字列が短い場合はある程度の長さに拡張して、キーとなる数で割った余りをハッシュとしている。

ハッシュ – 剰余を使った例

2019-08-15 / tau / コメントする

考え方

以下のように考える。

文字列を文字コード化し、眺めのバッファーに先頭から収めていく
バッファーが余った場合は、終わりまで0x00で埋める
バッファー全体を一つの整数として、特定の値で割った余りを求める
余りの下位で適当なバイト数の値を取り出し、ハッシュ値とする

コード全体

上記の考え方を、クラスに実装してみる。テスト用なので、引数やオーバーフローなどのチェックはしていない。

class Hash1():
    """簡単なハッシュを生成するクラス"""

    def __init__(self, st):
        """
        コンストラクター
        引数
        - st：ハッシュ生成対象文字列
        内容
        - 作業用のバッファーを準備しバッファーとハッシュ値の長さ(バイト数)を設定
        - 文字列の各文字の文字コードをバッファーの背等から格納

        """
        self.buf = 0
        self.buf_length = 16  # バッファーは16バイト
        self.hash_length = 8  # ハッシュ値は8バイト

        # 文字列中の文字のコードをバッファーに加えていく
        for c in st:
            self.buf <<= 8
            self.buf += ord(c)

        # 文字コードを埋めた後のバッファーのバイト数
        nbytes = self.get_nbytes()

        # バッファーの残り領域を0で埋める
        for n in range(0, self.buf_length - nbytes):
            self.buf = (self.buf << 8) + 0x00

    def __str__(self):
        """インスタンスの文字列化メソッド"""
        return format(self.buf, '0x')

    def get_hash(self, mod_key):
        """
        ハッシュを生成するメソッド
        引数
        - 剰余計算の被除数
        内容
        - バッファーの内容を整数とみなして剰余を計算
        戻り値
        - 16進表示の文字列によるハッシュ値(バイト数を調整)
        """
        hash_value = (self.buf % mod_key)
        return format(hash_value, '0'+str(self.hash_length)+'X')

    def get_nbytes(self):
        """現在のバッファーのバイト数を返すメソッド"""
        bf = self.buf
        nbytes = 0
        while bf != 0:
            nbytes += 1
            bf >>= 8
        return nbytes

class Hash1():

"""簡単なハッシュを生成するクラス"""

def __init__(self, st):

"""

コンストラクター

引数

- st：ハッシュ生成対象文字列

内容

- 作業用のバッファーを準備しバッファーとハッシュ値の長さ(バイト数)を設定

- 文字列の各文字の文字コードをバッファーの背等から格納

"""

self.buf = 0

self.buf_length = 16 # バッファーは16バイト

self.hash_length = 8 # ハッシュ値は8バイト

# 文字列中の文字のコードをバッファーに加えていく

for c in st:

self.buf <<= 8

self.buf += ord(c)

# 文字コードを埋めた後のバッファーのバイト数

nbytes = self.get_nbytes()

# バッファーの残り領域を0で埋める

for n in range(0, self.buf_length - nbytes):

self.buf = (self.buf << 8) + 0x00

def __str__(self):

"""インスタンスの文字列化メソッド"""

return format(self.buf, '0x')

def get_hash(self, mod_key):

"""

ハッシュを生成するメソッド

引数

- 剰余計算の被除数

内容

- バッファーの内容を整数とみなして剰余を計算

戻り値

- 16進表示の文字列によるハッシュ値(バイト数を調整)

"""

hash_value = (self.buf % mod_key)

return format(hash_value, '0'+str(self.hash_length)+'X')

def get_nbytes(self):

"""現在のバッファーのバイト数を返すメソッド"""

bf = self.buf

nbytes = 0

while bf != 0:

nbytes += 1

bf >>= 8

return nbytes

この実装例では、バッファーの長さを16バイト、ハッシュのバイト数は下位8バイトとし、余りを計算するための除数は実行時に引数として与えるようにしている。

実行結果

除数で変わる結果

これに適当な文字列と除数を与えてみる。

h = Hash1("My fair lady")
print(h)
print(h.get_hash(0xfedcba98))

# 4d792066616972206c61647900000000
# 723C2FC8

h = Hash1("My fair lady")

print(h)

print(h.get_hash(0xfedcba98))

# 4d792066616972206c61647900000000

# 723C2FC8

1文字だけ変えると、値が大きく変わり、なんとか使えそう。

h = Hash1("my fair lady")
print(h)
print(h.get_hash(0xfedcba98))

# 6d792066616972206c61647900000000
# 5E674DF0

h = Hash1("my fair lady")

print(h)

print(h.get_hash(0xfedcba98))

# 6d792066616972206c61647900000000

# 5E674DF0

簡単な文字列で除数を変えて試してみると、除数を「ややこしそうな値」にするとハッシュはばらつくが、除数の設定によっては入力文字列そのままの値が出たりする。

除数→	0xfedcba98	0xffffffff
A	9ED40708	41000000
AA	24FECD68	41410000
AB	B81E0A58	41420000
AC	4C608CB0	41430000
BA	EB7C9820	42410000
BB	7FBF1A78	42420000
BC	14019CD0	42430000

除数の影響

被除数の値によって、なぜハッシュ値が単純になるのか。

たとえば10進数で以下の様な例を考える。

$\begin{array}{rcrcrcr} 0000 & = & 99 & \times & 0 & + & 0 \\ 0100 & = & 99 & \times & 10 & + & 10 \\ 0200 & = & 99 & \times & 20 & + & 20 \\ & \vdots \\ 9000 & = & 99 & \times & 90 & + & 90 \\ 9100 & = & 99 & \times & 91 & + & 91 \\ & \vdots \\ 9800 & = & 99 & \times & 98 & + & 98 \\ 9900 & = & 99 & \times & 100 & + & 0 \\ \end{array}$

除数未満の値が余りに出ているが、上位桁のパターンがそのまま順番に現れており、先の2進数と同じ結果となっている。

そこで、より簡単な例を考えてみる。

以下の表は、左の列が被除数で、それらに対して最上段の除数で割ったときの余りを示している。被除数の1/2の桁の除数では、7あたりが最も結果がばらつき、その他の値では単純な余りの値が繰り返される。

$\begin{array}{r|ccccccccc} & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 10 & 1 & 2 & 3 & 4 & 0 & 2 & 1 & 0 & 0 \\ 20 & 2 & 4 & 6 & 2 & 0 & 0 & 2 & 0 & 0 \\ 30 & 3 & 6 & 2 & 0 & 0 & 2 & 0 & 0 & 0 \\ 40 & 4 & 0 & 5 & 4 & 0 & 0 & 1 & 0 & 0 \\ 50 & 5 & 2 & 1 & 2 & 0 & 2 & 2 & 0 & 0 \\ 60 & 6 & 4 & 4 & 0 & 0 & 0 & 0 & 0 & 0 \\ 70 & 7 & 6 & 0 & 4 & 0 & 2 & 1 & 0 & 0 \\ 80 & 8 & 0 & 3 & 2 & 0 & 0 & 2 & 0 & 0 \\ 90 & 0 & 2 & 6 & 0 & 0 & 2 & 0 & 0 & 0 \\ \end{array}$

これを細分化すると、余りの値の繰り返しはより顕著であることがわかる。

$\begin{array}{r|ccccccccc} & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \\ 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 0 & 0 \\ 3 & 3 & 3 & 3 & 3 & 3 & 3 & 0 & 1 & 0 \\ 4 & 4 & 4 & 4 & 4 & 4 & 0 & 1 & 0 & 0 \\ 5 & 5 & 5 & 5 & 5 & 0 & 1 & 2 & 1 & 0 \\ 6 & 6 & 6 & 6 & 0 & 1 & 2 & 0 & 0 & 0 \\ 7 & 7 & 7 & 0 & 1 & 2 & 3 & 1 & 1 & 0 \\ 8 & 8 & 0 & 1 & 2 & 3 & 0 & 2 & 0 & 0 \\ 9 & 0 & 1 & 2 & 3 & 4 & 1 & 0 & 1 & 0 \\ \end{array}$

先のコードは、上記の例で言えば除数を9に設定した場合に、その結果がきれいにもとの値と同じとなることに相当する。

衝突状況のチェック

除数を変化させて、アルファベット大文字１～４文字の文字列でハッシュ値の衝突が出るか確認してみた。各文字数に対するバリエーションの数は以下の通り。

１文字→26通り
２文字→26*26=676通り
３文字→26*26*26=17,576通り
４文字→26*26*26*26=456,976通り
合計、475,254通り

import string

.....

hash_dict = {}

al = string.ascii_uppercase
modkey = 0xffffffff

for c1 in al:
    h1 = Hash1(c1).get_hash(modkey)
    if not(h1 in hash_dict): hash_dict[h1] = []
    hash_dict[h1].append(c1)
    for c2 in al:
        s2 = c1 + c2
        h2 = Hash1(s2).get_hash(modkey)
        if not(h2 in hash_dict): hash_dict[h2] = []
        hash_dict[h2].append(s2)
        for c3 in al:
            s3 = c1 + c2 + c3
            h3 = Hash1(s3).get_hash(modkey)
            if not(h3 in hash_dict): hash_dict[h3] = []
            hash_dict[h3].append(s3)
            for c4 in al:
                s4 = c1 + c2 + c3 + c4
                h4 = Hash1(s4).get_hash(modkey)
                if not(h4 in hash_dict): hash_dict[h4] = []
                hash_dict[h4].append(s4)

for itm in list(hash_dict.items()):
    if len(itm[1]) > 1:
        print('{} : {}'.format(itm[0], itm[1]))

import string

.....

hash_dict = {}

al = string.ascii_uppercase

modkey = 0xffffffff

for c1 in al:

h1 = Hash1(c1).get_hash(modkey)

if not(h1 in hash_dict): hash_dict[h1] = []

hash_dict[h1].append(c1)

for c2 in al:

s2 = c1 + c2

h2 = Hash1(s2).get_hash(modkey)

if not(h2 in hash_dict): hash_dict[h2] = []

hash_dict[h2].append(s2)

for c3 in al:

s3 = c1 + c2 + c3

h3 = Hash1(s3).get_hash(modkey)

if not(h3 in hash_dict): hash_dict[h3] = []

hash_dict[h3].append(s3)

for c4 in al:

s4 = c1 + c2 + c3 + c4

h4 = Hash1(s4).get_hash(modkey)

if not(h4 in hash_dict): hash_dict[h4] = []

hash_dict[h4].append(s4)

for itm in list(hash_dict.items()):

if len(itm[1]) > 1:

print('{} : {}'.format(itm[0], itm[1]))

その結果は次の通り。

0xFEDCBA98
アルファベット１～４文字で衝突なし。

0xFEDCBA9
まだ衝突なし。

0xFEDCBA
衝突が多数発生。みな2つの文字列で衝突。たとえば
0071BB5E : [‘SZQA’, ‘ZRZW’]
003C0D52 : [‘SZQB’, ‘ZRZX’]
00065F46 : [‘SZQC’, ‘ZRZY’]
00CF8DF4 : [‘SZQD’, ‘ZRZZ’]
除数の10進値は16,702,650と文字列のバリエーションより大きいが、衝突が出始めた。

0xFFFFFFFF
意外にも衝突なし。

0xFFFFFFF
衝突が多数発生。これも2つの文字列で重複。たとえば
05A5CA5A : [‘JZZX’, ‘ZZZW’]
05A5DA5A : [‘JZZY’, ‘ZZZX’]
05A5EA5A : [‘JZZZ’, ‘ZZZY’]
除数の10進値は268,435,455とかなり大きいが、単純なパターンの値ほど衝突が起こりやすいのかもしれない。

コード詳細

コンストラクタinit()

インスタンス生成時にハッシュを生成する文字列を受け取り、空のバッファーを準備
バッファーの長さを16バイト、ハッシュ値の長さを8バイトに設定
引数で与えられた文字列から1文字ずつ取り出し、文字コードを追加
バッファー長までの余った部分に0を追加

    def __init__(self, st):
        """
        コンストラクター
        引数
        - st：ハッシュ生成対象文字列
        内容
        - 作業用のバッファーを準備しバッファーとハッシュ値の長さ(バイト数)を設定
        - 文字列の各文字の文字コードをバッファーの背等から格納

        """
        self.buf = 0
        self.buf_length = 16  # バッファーは16バイト
        self.hash_length = 8  # ハッシュ値は8バイト

        # 文字列中の文字のコードをバッファーに加えていく
        for c in st:
            self.buf <<= 8
            self.buf += ord(c)

        # 文字コードを埋めた後のバッファーのバイト数
        nbytes = self.get_nbytes()

        # バッファーの残り領域を0で埋める
        for n in range(0, self.buf_length - nbytes):
            self.buf = (self.buf << 8) + 0x00

def __init__(self, st):

"""

コンストラクター

引数

- st：ハッシュ生成対象文字列

内容

- 作業用のバッファーを準備しバッファーとハッシュ値の長さ(バイト数)を設定

- 文字列の各文字の文字コードをバッファーの背等から格納

"""

self.buf = 0

self.buf_length = 16 # バッファーは16バイト

self.hash_length = 8 # ハッシュ値は8バイト

# 文字列中の文字のコードをバッファーに加えていく

for c in st:

self.buf <<= 8

self.buf += ord(c)

# 文字コードを埋めた後のバッファーのバイト数

nbytes = self.get_nbytes()

# バッファーの残り領域を0で埋める

for n in range(0, self.buf_length - nbytes):

self.buf = (self.buf << 8) + 0x00

内部用メソッドget_nbytes()

文字コードを追加し終わったときのバッファー長を計算する処理を独立させたメソッド。

    def get_nbytes(self):
        """現在のバッファーのバイト数を返すメソッド"""
        bf = self.buf
        nbytes = 0
        while bf != 0:
            nbytes += 1
            bf >>= 8
        return nbytes

def get_nbytes(self):

"""現在のバッファーのバイト数を返すメソッド"""

bf = self.buf

nbytes = 0

while bf != 0:

nbytes += 1

bf >>= 8

return nbytes

ハッシュ値計算get_hash()

バッファーの内容を整数として、引数で与えられた除数から剰余を計算する
計算結果の下位バイトを取り出して、ハッシュ値として返す

    def get_hash(self, mod_key):
        """
        ハッシュを生成するメソッド
        引数
        - 剰余計算の被除数
        内容
        - バッファーの内容を整数とみなして剰余を計算
        戻り値
        - 16進表示の文字列によるハッシュ値(バイト数を調整)
        """
        hash_value = (self.buf % mod_key)
        return format(hash_value, '0'+str(self.hash_length)+'X')

def get_hash(self, mod_key):

"""

ハッシュを生成するメソッド

引数

- 剰余計算の被除数

内容

- バッファーの内容を整数とみなして剰余を計算

戻り値

- 16進表示の文字列によるハッシュ値(バイト数を調整)

"""

hash_value = (self.buf % mod_key)

return format(hash_value, '0'+str(self.hash_length)+'X')

文字列化メソッドstr()

インスタンスの文字列化メソッド。

    def __str__(self):
        """インスタンスの文字列化メソッド"""
        return format(self.buf, '0x')

def __str__(self):

"""インスタンスの文字列化メソッド"""

return format(self.buf, '0x')

概要

書式

値

書式

属性

href属性

target属性

概要

各特徴量と診断結果

2つの特徴量同士の関係

3つの特徴量の関係

概要

解析上の考え

問題の発生

解決策

注意点

概要

考え方

部分列に対する操作

再帰処理

コード

動作状況の確認

概要

コード

安定ソート

暗号化

暗号化の流れ

公開鍵・秘密鍵の算出手順

素数の組の準備

素数の積nの計算

計算準備

公開鍵の計算

秘密鍵の計算

簡略化した暗号化の例

鍵の準備

暗号化

復号

電子証明

電子証明の流れ

簡略化した電子証明の例

証明書の暗号化

考え方

コード全体

実行結果

除数で変わる結果

除数の影響

衝突状況のチェック

コード詳細

コンストラクタ__init__()

内部用メソッドget_nbytes()

ハッシュ値計算get_hash()

文字列化メソッド__str()__

コンストラクタinit()

文字列化メソッドstr()