algorithm - 树哈希:如何验证范围是否与树哈希对齐？

“tree hash”是一个类似于amazon glacier使用merkle tree/tiger hash tree来验证给定数据流子集的数据完整性的概念。
为了在检索数据时从Amazon Glacier接收树哈希，指定的字节范围必须是“树哈希对齐”。
The concept of "tree hash aligned" is described here.
引用开发人员文档：
范围[a，b]是相对于存档对齐的树哈希，如果且仅当在[a，b]上构建新的树哈希时，该范围的树哈希的根相当于整个存档的树哈希中的节点。[…]
把[P，Q]看作N兆字节（MB）存档的范围查询，P和Q是1兆字节的倍数注意，实际的包含范围是[pMB，qMB–1字节]，但为了简单起见，我们将其显示为[p，q]。考虑到这些因素
如果p是奇数，则只有一个可能的树哈希对齐范围，即[p，p+1 mb]。
如果p是偶数，k是最大数，其中p可以写成2k*x，那么最多有k树哈希对齐范围，从p x开始是大于0的整数。树哈希对齐范围分为以下类别：
对于每个i，其中（0p=0是a=2[lgn]*0的特例
现在的问题是：如果给定的范围[startByte，endByte]是树哈希对齐的，我如何通过编程验证编程语言无关紧要。
测试用例：

[0,0) => true
[0,1) => true
[0,2) => false
[0,3) => true
[1,2) => false
[4,5) => true

最佳答案

这里是python中is_treehash_aligned函数的基本实现：

import math

def max_k(x):
    return 1 + max_k(x/2) if x % 2 == 0 else 0

def is_treehash_aligned(P, Q):

    if (Q < P):
        return False
    elif (P % 2 == 1):
        return Q == P
    else:
        ilen = Q - P + 1    # size(interval)
        if  not (((ilen & (ilen - 1)) == 0) and ilen != 0):
            return False    # size(interval) ~ not power of two
        if P == 0:
            return True
        else:
            k = max_k(P)
            i = int(math.log(ilen, 2))
            return i <= k

if (__name__ == "__main__"):
    ranges = [(0, 0), (0, 1), (0, 2), (0, 3), (1, 2), \
              (4, 5), (6, 7), (2, 4), (6, 8), (5, 6), \
              (4, 4), (1, 1), (4194304, 5242879), \
              (4194304, 5242880), (4194304, 5242881)]

    for r in ranges:
        ret = is_treehash_aligned(*r)
        print("[" + str(r[0]) + ", " + str(r[1]) + ") => " + str(ret))

输出为：

[0, 0) => True
[0, 1) => True
[0, 2) => False
[0, 3) => True
[1, 2) => False
[4, 5) => True
[6, 7) => True
[2, 4) => False
[6, 8) => False
[5, 6) => False
[4, 4) => True
[1, 1) => True
[4194304, 5242879) => True
[4194304, 5242880) => False
[4194304, 5242881) => False

注意：
我采用了你的间隔符号，而不是说明书上的那种。因此，可以假设每个间隔是兆字节对齐的。
测试用例[4194304, 5242880)的结果与您在原始问题中输入的结果不同，尽管我再次检查了它，我有点确信它是正确的。
如果N是已知的（在您的测试用例中不是这样），那么当P == 0时，还应该接受任何范围的s.t.Q >= floor(N)，而不仅仅是具有两个幂的大小的范围对于右边没有其他子树的子树，也可以进行类似的论证这两种情况都与给定的树哈希对齐定义相匹配，但与标识它的指令不匹配。
注：问题和问题的here看起来都很混乱。
测试用例以符号[A, B)给出，其中A是起始块的索引，B是结束块（包括）的索引，假设整个归档文件由一个数组（从0开始索引）组成，每个数组有N个大小为1 MB的块（可能最后一个块除外）。例如。：

[0,0) => true
[0,1) => true
[0,2) => false
[0,3) => true
[1,2) => false
[4,5) => true

但是，这些指令假定范围是用符号[P MB, Q MB – 1 byte]给出的。
这些指示是误导性的。
例如，这里说：
如果p是偶数，k是最大数，其中p可以写成2k*x，那么最多有k树哈希对齐范围，从p开始。
电源符号似乎被省略了，可能是因为错误的HTML代码，因为句子应该是“最大的ks.t.P = (2^k)*X”。
另一个例子是：
对于每个i，其中（0例如，假设Q = P + 1、i > 0和k > 0那么间隔[P, Q + 2^i)的大小为= Q + 2^i - P = P + 1 + 2^i - P = 2^i + 1 > 1。然而，通过构造不存在这样的树散列对齐范围，其奇数大小大于一个。建议应该是：“[…]，那么[P, P + 2^i)是一个树哈希对齐的范围”。

关于algorithm - 树哈希:如何验证范围是否与树哈希对齐？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37629472/