字典序

字典序
术语名称	字典序
英语名称	lexicographic order

字典序(lexicographic order, lexicographical order, dictionary order)指在字符列比较时，按照从左到右逐个字母比较先后顺序，在遇到第一组不同字母或序列结束点时，判断拥有字母更靠前或结束时更短的序列先于字母更靠后或结束时更长的序列。字典和百科全书中往往使用这一顺序在特定语言的字母表上排列词条，称为字母序(alphabetical order)，字典序是字母序在任意给定字符集上的泛化。

定义

字典序
关系名称	字典序
关系符号
Latex
关系对象	字符列
关系元数	2
类型	全序

对语言 [math]\displaystyle{ L }[/math] ，记其字母表为 [math]\displaystyle{ A }[/math] ，其上有一个全序 [math]\displaystyle{ leq }[/math] ，可定义字母序列 [math]\displaystyle{ a = a_1 a_2 \cdots a_m }[/math] 和 [math]\displaystyle{ b = b_1 b_2 \cdots b_n }[/math] 上的关系 [math]\displaystyle{ leq }[/math] 满足：

• 若 [math]\displaystyle{ m=n=0 }[/math] ，即两个序列均为空，定义两序列相等，即 [math]\displaystyle{ a\leq b \land b \leq a }[/math] 。
• 若两序列均非空且 [math]\displaystyle{ a_1 \leq b_1 \land b_1 \leq a_1 }[/math] ，则定义序关系与后续部分序关系相同，即 [math]\displaystyle{ a\leq b \Leftrightarrow a_2 \cdots a_m \leq b_2 \cdots b_m }[/math] 。
• 否则，若 [math]\displaystyle{ m=0 }[/math] （即 [math]\displaystyle{ a }[/math] 为空序列）或 [math]\displaystyle{ a_1 \leq b_1 }[/math] ，则 [math]\displaystyle{ a \leq b }[/math] ；
• 否则，若 [math]\displaystyle{ n=0 }[/math] （即 [math]\displaystyle{ b }[/math] 为空序列）或 [math]\displaystyle{ b_1 \leq a_1 }[/math] ，则 [math]\displaystyle{ b \leq a }[/math] 。

根据字典序的使用，有时也允许序关系为偏序，几个变体字母互相先于对方，此时仍依此定义，不区分几个字母的顺序。

性质

如果字母表上的是一个全序，字典序一定也是一个全序。但是即使前者是良序，也不一定能推导出后者是良序，因为序列不限制长度时可能不存在最小。