辞書式順序
数学における辞書式順序(じしょしきじゅんじょ、英: lexicographical order. lexicographic-, dictionary-)とはいくつかの順序集合の直積集合上に順序を定める方法の一つである。順序集合 A と B が与えられた際の直積集合 A × B 上の辞書式順序は
{ ( a , b ) ≤ ( a ′ , b ′ ) ∣ ( a < a ′ ) ∪ ( a = a ′ ∩ b ≤ b ′ ) } {\displaystyle \{(a,b)\leq (a',b')\mid (a<a')\cup (a=a'\cap b\leq b')\}}
として定められる。辞書式順序という名前は、この順序の定め方が辞書における項目の並べ方を一般化したものと見なせることに由来する。つまり、単語(文字の並び)a1a2...ak が別の単語 b1b2...bk の前に現れるのは ai が bi と異なるような最初の i について、文字の順番の中で ai が bi より前に現れる場合である。このとき2つの単語は同じ長さ(文字数)であるものと仮定されているが、実際の辞書では普通短い単語の方を後ろにどんな文字よりも先の順番にある空白を付け加えることで単語の長さが揃っているものとして考える、という操作が行われる。
辞書式順序の実社会における応用として日付の書式に関するISO 8601規格が挙げられる。この規格では日付は YYYYMMDD(Yは年、Mは月、Dは日を表す)という書式によって表され、単純に文字の並びとして並べ替えるだけの整列アルゴリズムで時系列順の並べ替えが得られる。ここで、このアルゴリズムが機能するためには年は4つの数字で表され、月や日は2つの数字で表されていなければならないので、たとえば数字1つの日付には0を付け足して '01' などと表すことになる。