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

[[分类:序理论]]{{DEFAULTSORT:duan3xian1zi4dian3xu4}}
{{#seo:
|keywords=短先字典序
|description=本文介绍短先字典序的定义、性质和应用，包括在字符序列和数学结构上的短先字典序构造。
|modified_time={{REVISIONYEAR}}-{{REVISIONMONTH}}-{{REVISIONDAY2}}
|published_time=2025-01-04
}}
{{InfoBox
|name=短先字典序
|eng_name=shortlex order
|alaises=length-lexicographical order,redix order,military order
}}
{{非标准翻译}}
'''短先字典序'''('''shortlex order''', '''length-lexicographical order''')是[[字典序]]的一种变体：先比较字符串的长度，更短的序列先于更长的序列；如果长度相等，再在字符列比较时，按照从左到右逐个字母比较先后顺序，在遇到第一组不同字母时，判断拥有字母更靠前更短的序列先于字母更靠后的序列。

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

== 定义 ==

{{Relation
|name=短先字典序
|operand_relation=序列
|prototype=全序
}}
{{Relation
|name=短先字典序
|operand_relation=元组
|prototype=全序
}}
对[[语言]] <math>L</math> ，记其字母表为 <math>A</math> ，其上有一个[[全序]] <math>\leq</math> （或给定对应的[[严格全序]] <math><</math> ），
可定义序列（或有限的元组） <math>a = a_1 a_2 \cdots</math> 和 <math>b = b_1 b_2 \cdots</math> 上的关系 <math>\leq_\mathrm{shortlex}</math> 满足以下条件：
* 若 <math>a</math> 和 <math>b</math> 长度不同，则：
** 若 <math>a</math> 的长度短于 <math>b</math> ，则 <math>a <_\mathrm{shortlex} b</math> ；
** 若 <math>b</math> 的长度短于 <math>a</math> ，则 <math>b <_\mathrm{shortlex} a</math> 。
* 否则，若有 <math>i</math> 是满足 <math>a_i \neq b_i</math> 的最小下标，则：
** 若 <math>a_i < b_i</math> 则 <math>a <_\mathrm{shortlex} b</math> ；
** 若 <math>a_i > b_i</math> 则 <math>b <_\mathrm{shortlex} a</math> 。
* 否则，两序列长度相同且元素必对应相同，则 <math>a =_\mathrm{shortlex} b</math> 。

== 性质 ==

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

== 与字典序的区别 ==

* 字典序：从左向右依次比较元素。若比较时遇到字符串结束还没遇到不同元素，短的字符串更小。
* 短先字典序：先比较序列长度，若不同，短的字符串更小。若长度相同，从左向右依次比较元素。