algorithm - 了解流压缩算法中的最终值

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 结尾。如果不是，则您选择了错误的最后一个字母。

你只需要数As。不要从 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