Python
iRidgeDay 6

逆引き辞書を作成できる条件

行きはよいよい 帰りはこわい

Pythonの辞書において、キーと値を逆にした辞書、つまり逆引きの辞書が欲しい場面がある。逆引き辞書は簡単に作成することができる。例えば、次のようにすればよい。

>>> d = {"a": 1, "b": 2, "c": 3}
>>> inv_d = dict((v, k) for k, v in d.items())  # {1: 'a', 2: 'b', 3: 'c'}

しかし、簡単に作成できる一方で気をつけるべき点が2点ほど存在する。逆引き辞書の作り方はGoogleで検索すればたくさんヒットするが、隠された罠に関する情報は中々出てこない。今回はその陥りやすい罠を2点紹介する。

辞書のキーはハッシュ可能な値に限る

Pythonの公式ドキュメントには次のようにある。

マッピング (mapping) オブジェクトは、ハッシュ可能 (hashable) な値を任意のオブジェクトに対応付けます。(中略)
辞書のキーはほぼ任意の値です。ハッシュ可能 (hashable) でない値、つまり、リストや辞書その他のミュータブルな型 (オブジェクトの同一性ではなく値で比較されるもの) はキーとして使用できません。

対応付けの制約におけるキーはハッシュ可能なオブジェクトに限り、値は任意のオブジェクトが使用可能という非対称性がある。例えば、対応付け先の値としてリストや辞書などのミュータブルなオブジェクトを使用している場合は逆引き辞書を作成できない。キーとしてミュータブル(ハッシュ可能ではない)なオブジェクトを使用できないからである。

>>> d = {"a": [1], "b": [2], "c": [3]}
>>> inv_d = dict((v, k) for k, v in d.items())
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

逆引き辞書が存在するための数学的な特徴付け

キーと値を両方ハッシュ可能なオブジェクトで構成しても、必ず逆引き辞書が存在するとは限らない。ここでPythonの辞書を別の視点から眺めることで逆引き辞書が存在するための特徴を数学を使って形式化する。

まずは写像に関する言葉を定義する。集合$X$から集合$Y$への写像$f$を考える。

  • 定義 写像$f$が全射であるとは、$\forall y \in Y$に対して$f(x) = y$なる$x \in X$が存在することである。

  • 定義 写像$f$が単射であるとは、$x_{1}, x_{2} \in X$において$f(x_{1}) = f(x_{2})$ならば$x_{1} = x_{2}$となることである。

  • 定義 写像$f$が全射かつ単射であるとき、写像$f$は全単射であるという。

ここで、写像$f$が全単射ならば、任意の$y \in Y$において$f(x) = y$なる$x \in X$が存在する。このような$y$から$x$を対応づける写像を$f$の逆写像といい、$f^{-1}$と表す。

ここまでの数学の話をPythonの辞書に当てはめると、$X$がハッシュ可能なオブジェクトの集合、$Y$が任意のオブジェクトの集合、写像$f$が辞書、そして逆引き辞書が$f^{-1}$となる。つまり、逆引き辞書が存在するためには辞書が全単射であることと同値である。

さて、実際にPythonで辞書を定義すると、次のような構造となる。

>>> d = {"a": 1, "b": 2, "c": 3}

Pythonで辞書を定義すると、必ず全射の条件を満たす。必ずキーと値の組を定義する必要があるので自然と全射となる。そのため、逆引き辞書が存在するためには単射であることが必要十分となる。また、Pythonの辞書の構造から$|X| \geq |Y|$となるが、単射であることと$|X| = |Y|$であることは必要十分である。

よって、「逆引き辞書が存在するための必要十分条件はlen(set(d.keys())) == len(set(d.values()))となる。

まとめ

逆引き辞書を作成する場合は言語的な仕様と構造的な仕様に気をつける必要がある。