競馬の血統表における2分探索木

競馬の血統表、例えばドゥラメンテ (Duramente)の血統表 | 競走馬データ - netkeiba.com *1 においてどのようにデータを保持しておくのが便利かという話。
正直一旦読み込んでラベルさえ振ってしまえばもうどうでもいいんだが、それは言わない約束。

netkeibaのデータをそのまま読んだ場合（nk_index）

シンプルにそのまま5世代血統表を読み込んだ場合を考える。具体的にはtdタグを上から順に読むわけだがそうするとFig.1 (左)のようになる。*2各ノードの数字は5世代血統表でのナンバリング（読み込み順）でFig.1 (左)の数字をnk_index*3と呼ぶことにする。また、'父母母父'のような文字列をped_stringと呼ぶことにする。

この方法のナンバリングは2分木探索の深さ優先探索行きがけ順になっている。実装方法にはpop-pushによる方法と回帰による方法があるが前者を採用。
nk_index→ped_stringに変換する方法はpop-pushで行うが、ped_string→nk_indexはX世代血統表のもとで
${\rm nk\_index} = {\rm generation}-1+\sum_{\rm Gen\ is \ mother} (2^{X+1-{\rm Gen}}-1)$
と簡単に計算できるため、PedTree()._ped_index2nk_indexではこの式を使用している。*4

Fig1. (左) nk_indexの5世代血統表　(右) ped_indexの5世代血統表*5

ped_index

nk_indexではped_stringが同じでも3世代血統表か5世代血統表か…でindexが変わってしまう、かつそのときのindexとped_stringの対応付けに少し手間がかかる。
この2点を解決するため幅優先探索順でindexをふる。これをped_indexと呼ぶことにする。ped_indexはFig.1 (右)の通り。

ped_index→ped_string

実装はコード参照だが例として16を考える。これが何世代かを計算する。n世代血統表の馬の数は $2^1+2^2+\cdots+2^n = 2^{n+1}-2$ 頭。よって $2^{3+1}-2=14\leq {\rm ped\_index}< 2^{4+1}-2=30$ から4世代。3世代までの頭数は2^{3+1}-2=14頭なのでそれをped_indexから引く。ped_index-14=2。これを4bit分の2進数表示にして0010となる。0→父、1→母に読み替えて'父父母父'となる。

ped_string→ped_index

実装はコード参照だが例として'父母母父'を考える。父→0、母→1と読み替えて2進数0110となり10進数に直して6。このped_stringは4世代なので3世代までの頭数2^{3+1}-2=14頭を足してped_indexは6+14=20となる。

使用例

ptree = PedTree(max_generation=5) # 5世代血統表の作成。max_generation=5の場合は引数省略可。
ptree.nk_index2ped_index(5) # max_generation=5の場合のnk_index=5に対応するped_index
# 出力: 31

pdi = PedIndex(16)  # ped_index=16を入力
pdi.get_dict()
# 出力:  {'ped_index': 16, 'ped': '父父母父', 'ped_num_in_generation': 2}

pdi.set_ped_index(48) # ped_index=48で上書き
pdi.ped() # ped_stringだけ欲しい場合
# 出力: '母父父母父'
pdi.get_father_index() # その父のped_indexを取得。同じくget_mother_index()もある。
# 出力: 98

# 本当にやりたかったこと。もっと高速化できそうだがこれ以上の用途で使用しないのでこの程度で。
import pandas as pd

max_gen = 5 # 5世代血統表
ptree = PedTree(max_generation=max_gen)
pdi = PedIndex()
ped_string_list = [] # ped_string_list[nk_index] -> nk_indexに対応するped_string
for nk_index in range(2**(max_gen+1)-2):
    ped_index = PedTree().nk_index2ped_index(nk_index)
    pdi.set_ped_index(ped_index) # ped_indexを設定
    ped_string_list.append(pdi.ped())

df_nk_index = pd.DataFrame(ped_string_list, index=list(range(len(ped_string_list))), columns=['ped_string']) 
df_nk_index # 出力は下の画像

ソース

参考文献

qiita.com
2分探索木深さ優先探索行きがけ順をpop-pushで実装していたので参考にした。
ちなみに回帰による実装はうさぎでもわかる2分探索木後編 2分探索木における4つの走査方法 | 工業大学生ももやまのうさぎ塾などがある。

hdl.handle.net
今回のビット演算部分のアイデアはこれを元にしている。物性物理におけるスピン系の厳密対角化（ED）では状態 $|\uparrow\downarrow\uparrow\uparrow\uparrow\rangle$ を大きさ5の配列[1, 0, 1, 1, 1]に格納して状態として扱うのではなく $|10111\rangle$ の2進数に読みかえる。その2進数を10進数表示した23を「（全格子点のスピン）状態」として扱うことがある。こうするとわざわざ状態の配列を用意する必要がなく、かつスピン系のハミルトニアンに作用させたときの行列成分の計算をビット演算で処理できる。詳細はP.538参照。もちろんS=1/2だけでなくS=1（3進数に読みかえる）等にも拡張は可能。*6

*1:血統にはさっぱりの自分でもドゥラメンテの血統表は感嘆する。ディープが日本近代競馬の結晶とよく言われるが血としての縮図はこっちだと思ってる。早世が惜しい。

*2:青矢印先のノードは元ノードの父親、赤矢印は母親です。

*3:ゼロスタートに注意。

*4:例えば5世代血統表のもとでの'父母母父'の場合を考える。4世代の親なのでgeneration=4。母となっている世代は2、3世代。Σの2世代分の項は2^{5+1-2}-1=15、3世代分は2^{5+1-3}-1=7。よってnk_index=4-1+(15+7)=25。Fig.1(右)で確認しても'父母母父'のnk_indexが25となっていることが確認できる。

*5: (左)は PedTree().graph_nk_index() 、(右)は PedTree().graph() で表示可能。

*6:S=1の場合は例えば S=1 スピン鎖のランチョス対角化 : Kobe Pack 。量子スピン系の計算物理については計算物理〈3〉数値磁性体物性入門基礎物理学シリーズ―15 がわかりやすかったと思います。

potass' blog

ポタシウムのことが書いてないブログ。