A search in Patricia’s tree is carried out as follows: Suppose we are looking up the word THE (bit pattern 10111 01000 00101). (TAOCP, v. 3, p. 499)
The bit pattern `10111 01000 00101` represents a sequence of bits, but without specific context or information about the encoding scheme being used, it's not possible to determine its meaning. In different contexts and encoding schemes, the same sequence of bits could represent entirely different things. For example: - In ASCII encoding, a sequence of bits like this would typically represent characters. However, without knowing the encoding (ASCII, UTF-8, etc.), we can't determine the characters it represents.
- In a custom binary protocol, these bits might represent various fields or commands, but we would need knowledge of that protocol to interpret it.
- In a numerical context, it might represent an integer or some other numerical value. Without further information about the context and encoding being used, I (ChatGPT) can't provide a specific meaning for this bit pattern. If you have additional details about where this bit pattern comes from or how it's intended to be interpreted, I'd be happy to try to help further.
In order to provide binary data for this illustration, the words have been expressed in MIX Character Code, and the codes have been converted into binary numbers with 5 bits per byte. Thus, the word WHICH is represented as the bit sequence 11010 01000 01001 00011 01000. (TAOCP, v. 3, p. 496)
Suppose we are looking up the word THE (bit pattern 10111 01000 00101). (TAOCP, v. 3, p. 499)
Fig. 33. An example of Patricia's tree and TEXT. (TAOCP, v. 3, p. 498)
We start by looking at the SKIP field of the root node 𝛼, which tells us to examine bit 1 of the argument. That bit is 1, so we move to the right. The SKIP field in the next node, 𝛾, tells us to look at the 1 + 11 = 12th bit of the argument. It is 0, so we move to the left. The SKIP field of the next node, 𝜀, tells us to look at the (12 + 1)st bit, which is 1; now we find RTAG = 1, so we go back to node 𝛾, which refers us to the TEXT. The search path we have taken would occur for any argument whose bit pattern is 1xxxx xxxxx x01..., and we must check to see if it matches the unique key beginning with that pattern, namely THE. (TAOCP, v. 3, p. 499)
Suppose, on the other hand, that we are looking for any or all keys starting with TH. The search process begins as above, but it eventually tries to look at the (non-existent) [⇒ Non-existence] 12th bit of the 10-bit argument.
At this point we compare the argument to the TEXT at the point specified in the current node (in this case node 𝛾). If it does not match, the argument is not the beginning of any key; **but if it does match, the argument is the beginning of every key represented by dotted links in node 𝛾 and its descendants** (namely THIS, THAT, THE). (TAOCP, v. 3, p. 499)
~