誕生日の問題とユニークな識別子

誕生日の問題

誕生日は $N = 365$ 通りあります。$n$ 人($n < N$)がパーティを開きました。誕生日が同じ人がいる確率は

\[ 1 - \frac{365}{365} \times \frac{364}{365} \times \frac{363}{365} \times \cdots \times \frac{365 - n + 1}{365} \]

です。次の近似式でも計算できます(証明は例えばWikipediaの Birthday problem 参照):

\[ 1 - e^{-n^2/(2N)} \]

接種券番号の問題

日本では2021年に新型コロナ感染症ワクチン接種券を配りました。ところが接種券を発行するのは各自治体だったため,10桁の接種券番号も自治体ごとに付番されました。仮に番号がランダムだったとして,番号の衝突(重複)はあるでしょうか。

接種券の枚数を1億枚 $n = 10^8$ とします。10桁の番号は $N = 10^{10}$ 通りです。計算してみれば,

\[ 1 - e^{-n^2/(2N)} \approx 1 \]

ですので,確実に衝突が起こります。

では,何桁の番号であれば,各自治体がばらばらに付番しても,衝突が起こらないといえるでしょうか。

うんと大きい数は10進法でない符号化をすることが多いので,ビット数で表すほうが便利です。$N$ が80ビットなら $1 - e^{-n^2/(2N)}$ はおよそ $4 \times 10^{-9}$,100ビットならおよそ $4 \times 10^{-15}$ ですので,衝突はまず起こらないといえます。

UUID

128ビットのランダムな値を表す UUID(Universally Unique Identifier)というものが RFC 4122 で定められています。LinuxやMacには uuidgen というコマンドがあります。Pythonには uuid という標準ライブラリがあります。

UUIDにはいくつかのバージョンがありますが,ここではまったくランダムなバージョン4のUUIDを試してみましょう。128ビットですが,6ビットは固定で,ランダムな部分は122ビットです。

import uuid

uuid.uuid4()
UUID('3585b7a9-e35a-433b-be8e-3916c75f6240')

ULID

ULID(Universally Unique Lexicographically Sortable Identifier)はUUIDを改良したもので,UUIDと同じ128ビットでありながら,UUIDは36文字ですが,ULIDは26文字で表されます。128ビットのうち,先頭の48ビットはタイムスタンプで,UNIX時刻をミリ秒の単位で表したものです。10889年まで桁あふれしません。残りの80ビットがランダムな部分です。文字列としてソートすると,時刻順に並びます(lexicographically sortable)。

Pythonではいくつかのライブラリがありますが,ここでは python-ulid を使ってみます。pip install python-ulid でインストールします(余分なものが入らないのでconda環境でもpipでインストールして大丈夫です)。

from ulid import ULID

ULID()
ULID(01F63ZWFQGSMGM3XGXBE8CTRDT)