2

我正在尝试用 java 重写一个 c++ patricia trie。C++ 代码来自这里

完整的源代码

我有点卡住了。

所以这是我的理解：

#define ZEROTAB_SIZE 256
head->key = (char*)calloc(ZEROTAB_SIZE, 1);

我们为密钥创建了一个 256 位的数组，因此我们可以有一个最大长度为 32 个字符的字符串，每个字符用 8 位表示。我可以用java中的char数组来实现它吗？

template <class T>
int PatriciaTrie<T>::bit_get(PatriciaTrieKey bit_stream, int n) {
  if (n < 0) return 2; // "pseudo-bit" with a value of 2.
  int k = (n & 0x7);
  return ( (*(bit_stream + (n >> 3))) >> k) & 0x1;
}

k 获取 n 的最后 7 位，我们移动到字符串的 n/8 字符（不完全是 n/8，因为向右移动会将任何低于 8 的内容删除为零）然后我们移动 bit_stream[n> 的值>3] 由 k 然后我们得到最后一位。如果我在 java 中使用数组，我可以将其重写为

return (bit_stream[n>>3] >> k) & 0x1;

?

template <class T>
int PatriciaTrie<T>::bit_first_different(PatriciaTrieKey k1, PatriciaTrieKey k2) {
    if (!k1 || !k2)
        return 0; // First bit is different!
    int n = 0;
    int d = 0;
    while ( (k1[n] == k2[n]) &&
            (k1[n] != 0) &&
            (k2[n] != 0) )
        n++;
    while (bit_get(&k1[n], d) == bit_get(&k2[n], d))
        d++;
    return ((n << 3) + d);
}

现在这是令人困惑的地方，直到第二个while循环的第一部分看起来足够清晰，循环并检查有多少位相等且非零，但是我不确定第二个循环在做什么，我们获取地址两个键中的第一个位是否相等，如果它们相等，我们再次检查直到我们发现不相等的位？

主要是我不确定这里如何使用密钥的地址，但我也可能对 bit_get 类中的位移感到困惑。

我想对我的 java 类的 c++ 和 java 中的 trie 进行比较，并且我希望使实现尽可能相似。

4

2 回答 2

2

我对这个数据结构不熟悉，但是你对这段代码的理解存在一些问题。

首先，calloc分配 256 个字节，而不是位。 new byte[256]在java中可以比较。

其次，n & 0x7得到 3 位n，而不是 7 位。更清晰的编写方法是n/8andn%8而不是n>>3and n & 7，但是如果您的编译器很愚蠢，则按位运算可能会稍微快一些。

你是对的那(bit_stream[n>>3]>>k) & 1是一样的。

现在，第一个循环bit_first_different循环的是字节，而不是位。检查 0 是为了防止超出键的末端。一旦该循环终止，n指的是第一个不同的字节。然后第二个循环寻找不同的位。

请注意，如果两个键不同，则第二个循环可能会在键的末尾运行，从而可能导致分段错误。

现在， & 正在获取地址，k1[n]因为bit_get函数需要一个指向字符的指针……这会传入n位流的第 th 个元素。循环之后，d是 的第一个不同位的偏移量k[n]。

最后，代码将n（哪个字节？）与d（那个字节中的哪个位？）结合起来给出位。我再次主张8*n+d清晰，但这是一个品味问题。

于 2012-10-28T18:51:19.587 回答
0

我可以用java中的char数组来实现它吗？

我的 java 有点生疏，但我相信char它是用 java 签名的，这意味着它>>不会像你期望的那样做。那是因为移动有符号数不会移动符号位，所以你真正想要的是>>>运算符或只使用byte无符号的类型。我有一种感觉，这是各种错误，所以请仔细检查。

返回 (bit_stream[n>>3] >> k) & 0x1;

在 C 或 C++ 中，*(array + k)这只是另一种编写方式，array[k]因此您的翻译看起来正确。至于解释，bit_stream[n>>3]本质上是获取所需位所在的字节。>> k将所需位移动到最低有效位位置。最后，我们通过用 屏蔽掉所有我们不感兴趣的位& 0x1。根据该位是否设置，这给我们留下了 0 或 1 的值。

最后一个函数所做的是比较 2 个位字符串并返回 2 个字符串首先不同的位位置。第一个循环本质上是第二个循环的优化版本，它不是逐位比较，而是检查整个字节。

换句话说，它首先遍历每个字节并找到前 2 个不同的字节。然后它获取这 2 个不同的字节并遍历它们，直到找到不同的前 2 位。请注意，bit_get在这种情况下，函数永远不会收到大于 7 的 n，因为我们知道字节中的某处存在差异。然后根据两个循环的结果构造最终位位置，如下所示(number_of_equal_bytes * 8) + number_of_equal_bits)：

于 2012-10-28T18:43:39.460 回答