短先字典序
| 短先字典序 | |
|---|---|
| 术语名称 | 短先字典序 |
| 英语名称 | 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] 。
性质
如果字母表上的是一个全序，短先字典序一定也是一个全序。
与字典序的区别
- 字典序：从左向右依次比较元素。若比较时遇到字符串结束还没遇到不同元素，短的字符串更小。
- 短先字典序：先比较序列长度，若不同，短的字符串更小。若长度相同，从左向右依次比较元素。