木のナンバリング

それぞれの木に一意な番号をふります。

方法

以下のような表を考えます。

x \ y	0	1	2	3	4	. .
0	1	4	9	16	25	. .
1	2	3	8	15	24	. .
2	5	6	7	14	23	. .
3	10	11	12	13	22	. .
4	17	18	19	20	21	. .
:	:	:	:	:	:

木から自然数への変換は以下の定義によって一意に定まります。

• 空の番号は $0$ である。
• 左の子の番号が $x$、右の子の番号が $y$ である木の番号は上の表の $(x, y)$ を見る。

逆に、自然数から木への変換も一意に定まります。

• $0$ は空である。
• $z$ は上の表の $(x, y)$ にあるとき、左の子の番号が $x$、右の子の番号が $y$ であるような木である。

計算は以下の擬似コードでできます。

def pair(x, y):

m = max(x, y)

return m * (m + 1) + y - x + 1

def unpair(z):

m = floor(sqrt(z - 1))

h = m * (m + 1) + 1

if z < h:

return ( m, m - h + z )

if z == h:

return ( m, m )

if z > h:

return ( m - z + h, m )

他の方法

割り当て方は色々考えられます。現在は四角埋めに落ち着いていますが、過去に挙がった方法一覧と現在の方法が選ばれた理由を紹介しておきます。

数学的には自然数が自由マグマをなすような二項演算 $N \times N \to N$ を考えればいい？

2べき

https://twitter.com/kepeken/status/1029774623787765760

$$\mathrm{pair}(x, y) = 2^x (2y + 1)$$

インフレが激しいため不採用です。

三角埋め

x \ y	0	1	2	3	4
0	1	3	6	10	15
1	2	5	9	14
2	4	8	13
3	7	12
4	11

後述の四角埋めのほうが都合が良かったので廃止しました。

四角埋め

https://twitter.com/kepeken/status/1031492656528941059

x \ y	0	1	2	3	4
0	1	4	9	16	25
1	2	3	8	15	24
2	5	6	7	14	23
3	10	11	12	13	22
4	17	18	19	20	21

現在採用している案です。特徴として番号順がそのまま高さ順になっているため、例えば木の高さによって品詞を決定すれば、

• 造語するとき自然数の範囲から選ぶだけで良い
• 単語が他の単語を部分木として含まないようにできる（一意分解できる）

などの利点があることから採用しました。

往復埋め

x \ y	0	1	2	3	4
0	1	4	5	16	17
1	2	3	6	15	18
2	9	8	7	14	19
3	10	11	12	13	20
4	25	24	23	22	21

四角埋めに加わる特徴として、自然数の差が１である木同士の編集距離も１になっています。それによる利点が特に思いつかない割に計算が面倒なので、採用を見送っています。

Z階数曲線

Z階数曲線 - Wikipedia

x \ y	0	1	2	3	4
0	1	3	9	11
1	2	4	10	12
2	5	7	13	15
3	6	8	14	16
4	17

へだるさんの提案 によるものです。

ビット演算で高速に処理ができることが利点です。

文法を考えるにあたって四角埋めの性質が面白そうなのでZ階数曲線の採用は見送っていますが、Z階数曲線にも文法に利用できそうな性質があったら採用するかもしれません。