理解流压缩算法中的最终值

Question

流压缩算法中的最终独占扫描值应该发生什么？

这是一个挑选所有"A"字符的例子。

序列A:

Input:       A B B A A B B A
Selection:   1 0 0 1 1 0 0 1
Scan:        0 1 1 1 2 3 3 3
0 - A
1 - A
2 - A
3 - A

序列B（除最后一个值外相同）：

Input:       A B B A A B B B
Selection:   1 0 0 1 1 0 0 0
Scan:        0 1 1 1 2 3 3 3
0 - A
1 - A
2 - A
3 - B

显然，第二个例子给出了错误的最终结果，基于对写入这些地址的扫描值进行天真的循环。

我在这里错过了什么？

更新：

根据我对扫描算法的理解，我会做以下等效的操作：

for (int i = 0; i < scan.length(); i++)
{
    result[scan[i]] = input[i];
}

同时，这将涉及分散指令。

Answer 1

在一个A之后，你假设至少会有另一个A。因此，你假设序列以A结束。如果没有，你就选错了最后一个字母。

你只需要计算A。不要从1开始。从0开始。只有当你找到A.时才增加这个计数

或者更新：

Input:       A B B A A B B A
Selection:   1 0 0 1 1 0 0 1
Scan:        0 1 1 1 2 3 3 3 4
                             ^
0 - A                        |
1 - A                        Four elements
2 - A
3 - A

Input:       A B B A A B B B
Selection:   1 0 0 1 1 0 0 0
Scan:        0 1 1 1 2 3 3 3 3
                             ^
0 - A                        |
1 - A                        Three elements
2 - A