短先字典序
| 短先字典序 | |
|---|---|
| 术语名称 | 短先字典序 |
| 英语名称 | shortlex order |
本条目没有一致可信的中文译名。
短先字典序(shortlex order, length-lexicographical 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|\neq|n| }[/math] ，定义序关系与长度大小关系相同，即 [math]\displaystyle{ a\leq b \Leftrightarrow |a| \leq |b| }[/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{ a_1 \leq b_1 }[/math] ，则 [math]\displaystyle{ a \leq b }[/math] ；
- 否则，若 [math]\displaystyle{ b_1 \leq a_1 }[/math] ，则 [math]\displaystyle{ b \leq a }[/math] 。
性质
如果字母表上的是一个全序，短先字典序一定也是一个全序。