反向字典序

反向字典序
术语名称	反向字典序
英语名称	colexicographic order
别名	colex order, reverse lexicographic order

本条目没有一致可信的中文译名。

反向字典序(colexicographic order, 简称 colex order)是字典序的一种变体，比较序列时从右向左逐个元素比较，而非传统的从左向右。

本文的内容是一种将序列逆序的字典序所构成的顺序，不是字典序的逆序。

定义

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

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

对语言 [math]\displaystyle{ L }[/math] ，记其字母表为 [math]\displaystyle{ A }[/math] ，其上有一个全序 [math]\displaystyle{ \leq }[/math] （或给定对应的严格全序 [math]\displaystyle{ \lt }[/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_\mathrm{colex} }[/math] 满足以下条件：

• 若 [math]\displaystyle{ a }[/math] 是 [math]\displaystyle{ b }[/math] 的后缀，则 [math]\displaystyle{ a \lt _\mathrm{colex} b }[/math] ；若 [math]\displaystyle{ b }[/math] 是 [math]\displaystyle{ a }[/math] 的后缀，则 [math]\displaystyle{ b \lt _\mathrm{colex} a }[/math] 。
• 否则，若有 [math]\displaystyle{ i }[/math] 是满足 [math]\displaystyle{ a_{m-i} \neq b_{n-i} }[/math] 的最小值，此时取得元素不同的最大下标，则：
  • 若 [math]\displaystyle{ a_{m-i} \lt b_{n-i} }[/math] 则 [math]\displaystyle{ a \lt _\mathrm{colex} b }[/math] ；
  • 若 [math]\displaystyle{ a_{m-i} \gt b_{n-i} }[/math] 则 [math]\displaystyle{ b \lt _\mathrm{colex} a }[/math] 。
• 否则，两字符串元素必对应相同，则 [math]\displaystyle{ a =_\mathrm{colex} b }[/math] 。

这一定义也可以用在笛卡尔积 [math]\displaystyle{ A_1\times A_2\times A_3\times\cdots\times A_n }[/math] 中的两个序列或元组间，要求其中每个集合上都有这样的全序。

有时也允许字母表中的序关系为弱序，类似于现实中几个变体字母在字母表中有同一顺序，此时仍依此定义。

实例

在字符集合 [math]\displaystyle{ \Sigma = \{a,b\} }[/math] 上，有全序满足 [math]\displaystyle{ a\leq b }[/math] ，则字符串集合 [math]\displaystyle{ \Sigma^* }[/math] 上的字典序，简写所有长度大于 3 的字符串，可列出如下：

ε（空字符串）
a
aa
aaa
（形如 ...aaa 的更长字符串）
baa
（形如 ...baa 的更长字符串）
ba
aba
（形如 ...aba 的更长字符串）
bba
（形如 ...bba 的更长字符串）
b
ab
aab
（形如 ...aab 的更长字符串）
bab
（形如 ...bab 的更长字符串）
bb
abb
（形如 ...abb 的更长字符串）
bbb
（形如 ...bbb 的更长字符串）

与字典序的联系与区别

• 字典序：从左向右比较，首元素权重最高。允许定义在无穷序列上。
• 反向字典序：从右向左比较，末元素权重最高。无法定义在无穷序列上。

反向字典序相当于原元组各分量反向排列后的字典序。