查看“︁短先字典序”︁的源代码

[[分类:序理论]]
{{InfoBox
|name=短先字典序
|eng_name=shortlex order
|alaises=length-lexicographical order,redix order,military order
}}

{{非标准翻译}}

'''短先字典序'''('''shortlex order''', '''length-lexicographical order''')是[[字典序]]的一种变体：先比较字符串的长度，更短的序列先于更长的序列；如果长度相等，再在字符列比较时，按照从左到右逐个字母比较先后顺序，在遇到第一组不同字母时，判断拥有字母更靠前更短的序列先于字母更靠后的序列。

字典序中是从左到右比较时如果遇到结束才会将短的判定为优先，相当于短序列后续有着比所有字符都优先的占位字符，短字符串优先于以自己为前缀的长字符串；短先字典序中则是先比较长度，更短的字符串优先于一切更长的字符串。

== 定义 ==

{{Relation
|name=短先字典序
|operand_relation=字符串
|prototype=全序
}}
对[[语言]] <math>L</math> ，记其字母表为 <math>A</math> ，其上有一个[[全序]] <math>\leq</math> ，可定义字母串（有限字母序列） <math>a = a_1 a_2 \cdots a_m</math> 和 <math>b = b_1 b_2 \cdots b_n</math> 上的关系 <math>\leq</math> 满足：
* 若 <math>|m|\neq|n|</math> ，定义序关系与长度大小关系相同，即 <math>a\leq b \Leftrightarrow |a| \leq |b|</math> 。
* 若 <math>m=n=0</math> ，即两个序列均为空，两序列相等，即 <math>a\leq b \land b \leq a</math> 。
* 若两序列均非空且 <math>a_1 \leq b_1 \land b_1 \leq a_1</math> ，则定义序关系与后续部分序关系相同，即 <math>a\leq b \Leftrightarrow a_2 \cdots a_m \leq b_2 \cdots b_m</math> 。
* 否则，若 <math>a_1 \leq b_1</math> ，则 <math>a \leq b</math> ；
* 否则，若 <math>b_1 \leq a_1</math> ，则 <math>b \leq a</math> 。

== 性质 ==

如果字母表上的是一个全序，短先字典序一定也是一个全序。