リー距離
リー距離(英: Lee distance)とは符号理論における距離の一種。q 文字からなるアルファベット {0, 1, ..., q − 1}(但しq ≥ 2)上の長さ n の文字列 x 1 x 2 ⋯ x n {\displaystyle x_{1}x_{2}\dotsb x_{n}} と y 1 y 2 ⋯ y n {\displaystyle y_{1}y_{2}\dotsb y_{n}} に対して
∑ i = 1 n min ( | x i − y i | , q − | x i − y i | ) {\displaystyle \sum _{i=1}^{n}\min(|x_{i}-y_{i}|,q-|x_{i}-y_{i}|)}
により定義される。アルファベットを加法群 Zq と見做すと、長さ1の文字列である x {\displaystyle x} と y {\displaystyle y} に対するリー距離は、ケイリーグラフにおける最短経路の長さである 。
もし q = 2 {\displaystyle q=2} か q = 3 {\displaystyle q=3} であれば、リー距離はハミング距離と一致する。これは、それぞれの文字に対して一致していれば0を、一致していなければ1を出力する関数の和となるからである。 q > 3 {\displaystyle q>3} においては、異なる文字に対して2以上を出力しうるため、ハミング距離と一致するとは限らない。
リー距離から導かれる距離空間は、離散化した楕円空間である 。