如何实现二进制节点一次读取4位的二进制树呢? [英] How to implement a binary trie that has nodes that read 4 bits at a time?

问题描述

在某种意义上，我试图找到一种方法来对 inline 二进制特里进行排序.基本上，二进制特里在二进制数中的每个插槽都有一个节点，在0和1上分别向左分支.如何构造该结构，以便一次读取4位而不是1位?通过在每个trie节点中具有16个插槽，似乎可以实现这一点，但是我很难想象它的实际外观.如何使用这种方法一次读取4位的二进制输入(如 10101010 ).会是什么样?

I am trying to find a way to sort of inline a binary trie in some sense. Basically, a binary trie has a node for every slot in a binary number, branching left on 0 and right on 1. How would you structure this so you could read 4 bits at a time rather than 1? It seems this would be possible by having 16 slots in each trie node, but I'm having a hard time visualizing how this would actually look; how you would read the binary input like 10101010 4-bits at a time using this sort of approach. What would it look like?

[  left    , right   ,    left,  right  ,  left,   right   ...]
  (goto2)    (goto5)   (goto7)  (goto8)   (goto9), (goto10)

或者我不知道.什么算法可以对数组中的16个时隙检查4位?

Or I don't know. What is an algorithm that would check the 4 bits against 16 slots in an array?

似乎可以在16个插槽中表示4位，但我只是看不到算法如何能够在不手动详细显示每个步骤的情况下弄清楚如何读取这些位.必须有一些方程式或类似的东西.

It seems that 4 bits can be represented in 16 slots, but I just don't see how an algorithm can figure out how to read these without manually visualizing every step in detail. There must be some equation or something.

推荐答案

您描述的是基数特里 base 16.通过从密钥中提取4位，您将获得0到15(含)之间的数字.您可以使用该数字来索引您的节点:

What you describe is a radix trie base 16. By extracting 4 bits from your key, you get a number between 0 and 15 (inclusive). You can use that number to index into your node:

struct Node {
    Node *children[16];
    Value value;
};

Value *find(const char *key, int nkey, Node *node) {
    int i = 0;
    while(i < 2*nkey && node) {
        int digit = (key[i/2] >> (i%2==0 ? 0 : 4)) & 0xf;
        node = node->children[digit];
        ++i;
    }
    return node ? &node->value : 0;
}

这篇关于如何实现二进制节点一次读取4位的二进制树呢?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！