短先字典序：修订间差异

2025年10月26日 (日) 15:47的最新版本

短先字典序
术语名称	短先字典序
英语名称	shortlex order

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

短先字典序(shortlex order, length-lexicographical 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 }[/math] 和 [math]\displaystyle{ b = b_1 b_2 \cdots }[/math] 上的关系 [math]\displaystyle{ \leq_\mathrm{shortlex} }[/math] 满足以下条件：

若 [math]\displaystyle{ a }[/math] 和 [math]\displaystyle{ b }[/math] 长度不同，则：
- 若 [math]\displaystyle{ a }[/math] 的长度短于 [math]\displaystyle{ b }[/math] ，则 [math]\displaystyle{ a \lt _\mathrm{shortlex} b }[/math] ；
- 若 [math]\displaystyle{ b }[/math] 的长度短于 [math]\displaystyle{ a }[/math] ，则 [math]\displaystyle{ b \lt _\mathrm{shortlex} a }[/math] 。
否则，若有 [math]\displaystyle{ i }[/math] 是满足 [math]\displaystyle{ a_i \neq b_i }[/math] 的最小下标，则：
- 若 [math]\displaystyle{ a_i \lt b_i }[/math] 则 [math]\displaystyle{ a \lt _\mathrm{shortlex} b }[/math] ；
- 若 [math]\displaystyle{ a_i \gt b_i }[/math] 则 [math]\displaystyle{ b \lt _\mathrm{shortlex} a }[/math] 。
否则，两序列长度相同且元素必对应相同，则 [math]\displaystyle{ a =_\mathrm{shortlex} b }[/math] 。

性质

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

与字典序的区别

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

@@ 第1行： / 第1行： @@
-[[分类:序理论]]
+[[分类:序理论]]{{DEFAULTSORT:duan3xian1zi4dian3xu4}}
+{{#seo:
+|keywords=短先字典序
+|description=本文介绍短先字典序的定义、性质和应用，包括在字符序列和数学结构上的短先字典序构造。
+|modified_time={{REVISIONYEAR}}-{{REVISIONMONTH}}-{{REVISIONDAY2}}
+|published_time=2025-01-04
+}}
 {{InfoBox
 |name=短先字典序
@@ 第5行： / 第11行： @@
 |alaises=length-lexicographical order,redix order,military order
 }}
 {{非标准翻译}}
 '''短先字典序'''('''shortlex order''', '''length-lexicographical order''')是[[字典序]]的一种变体：先比较字符串的长度，更短的序列先于更长的序列；如果长度相等，再在字符列比较时，按照从左到右逐个字母比较先后顺序，在遇到第一组不同字母时，判断拥有字母更靠前更短的序列先于字母更靠后的序列。
@@ 第16行： / 第20行： @@
 {{Relation
 |name=短先字典序
-|operand_relation=字符串
+|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> 满足：
+{{Relation
-* 若 <math>|m|\neq|n|</math> ，定义序关系与长度大小关系相同，即 <math>a\leq b \Leftrightarrow |a| \leq |b|</math> 。
+|name=短先字典序
-* 若 <math>m=n=0</math> ，即两个序列均为空，两序列相等，即 <math>a\leq b \land b \leq a</math> 。
+|operand_relation=元组
-* 若两序列均非空且 <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> 。
+|prototype=全序
-* 否则，若 <math>a_1 \leq b_1</math> ，则 <math>a \leq b</math> ；
+}}
-* 否则，若 <math>b_1 \leq a_1</math> ，则 <math>b \leq a</math> 。
+对[[语言]] <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> 。
 == 性质 ==
 如果字母表上的是一个全序，短先字典序一定也是一个全序。
+== 与字典序的区别 ==
+* 字典序：从左向右依次比较元素。若比较时遇到字符串结束还没遇到不同元素，短的字符串更小。
+* 短先字典序：先比较序列长度，若不同，短的字符串更小。若长度相同，从左向右依次比较元素。