查看“︁UPS”︁的源代码

UPS（Upper Projection Sequence, 向上投影序列）是由 Optimism 最初创作，Alice 完善的记号，旨在以序列形式模拟向上投影。

== 定义 ==

=== 基础定义 ===
一个 UPS 表达式由一组有序排列的项组成。

项：一个自然数与一个星号标记 <math>\alpha_i = (v_i, s_i)</math> 。

父项：一个索引的父项 <math>p(i)</math> 为最大的 <math>j < i</math>, 满足 <math>v_j < v_i</math> 。

正规化序列：一个序列 <math>S = [\alpha_0, \alpha_1, ..., \alpha_{L-1}]</math> 的正规化序列为 <math>\mathrm{norm}(S) = [\alpha'_0, \alpha'_1, ..., \alpha'_{L-1}]</math>, 其中 <math>\alpha'_i = (v_i - v_0, s_i)</math> 。

=== 直接集与直接段 ===
一个索引 <math>i</math> 的直接集定义为：

# <math>i \in D(i)</math>;
# 若 <math>p(j) \in D(i), s_{p(j)} = 1</math>, 则 <math>j \in D(i)</math> 。
定义直接段结尾：令 <math>M(i) = \max(t | t \in D(i))</math> 。若存在 <math>k</math> 使得 <math>v_k = \min (v_j | j > M(i), p(j) \in D(i))</math>, 找到其中索引最小的 <math>k_0</math> , 定义 <math>\mathrm{ed}(i) = k_0</math>; 否则，定义 <math>\mathrm{ed}(i) = M(i)</math> 。

定义索引 <math>i</math> 的直接段为 <math>\mathrm{seg}(i) = [\alpha_i, ..., \alpha_{\mathrm{ed}(i)}]</math> 。

=== 字典序比较与投影比较 ===
在进行字典序比较与投影比较之前，首先要将待比较序列的 <math>\alpha_{L-1}</math> 替换为 <math>\alpha^{*}_{L-1} = (v_{L-1}, 1)</math> ，并进行正规化。

字典序比较为逐项首先比较数值（数值大者更大），其次比较星号（有星号者更大）。若前缀完全相同，则更长者更大。

投影比较的流程如下：

首先定义 <math>S = [\alpha_0, \alpha_1, ..., \alpha_{L-1}]</math>的投影深度 <math>\mathrm{dep}(S) = v_{L-1}</math> 。投影深度更大者更大。

若投影深度相等且等于 <math>0</math>，则直接返回相等，否则进行进一步比较。

令 <math>t = p(L-1)</math> , 则定义 <math>S</math> 的投影子序列为 <math>\mathrm{proj}(S) = \mathrm{norm}([\alpha'_{t}, \alpha_{t+1}, ..., \alpha_{L-1}])</math> , 其中 <math>\alpha'_t = (v_t, 0)</math> 。比较两个序列的投影子序列的字典序，更大者更大。