Difference between revisions of "Binary traversal"
(Add Wikipedia:Trie) |
(Remove obsolete comment) |
||
| Line 46: | Line 46: | ||
</table> | </table> | ||
Both the decimal and the binary numbers really have an infinite number of leading zeros before them, but we can still maintain a unique sequence of digits to represent every integer even if we omit all leading zeros as we have in this table. The point is that this rule means that every single number except for 0 always ends (when reading from right to left) with a non-zero digit. While this may not be of much interest for most number systems, you will notice that with binary it means that every number except zero ends with a 1 - and if we forget about the two first items in the list, then we could drop the last bit altogether. As can be seen from the ''Nodal Path'' column in the list, that's exactly what we do in path traversal. This can't usually work with normal numeric data types because ''0'' and ''00'' evaluate to the same, but a ''sequence'' of binary digits is more like a string comparison of ''"0"'' and ''"00"''. | Both the decimal and the binary numbers really have an infinite number of leading zeros before them, but we can still maintain a unique sequence of digits to represent every integer even if we omit all leading zeros as we have in this table. The point is that this rule means that every single number except for 0 always ends (when reading from right to left) with a non-zero digit. While this may not be of much interest for most number systems, you will notice that with binary it means that every number except zero ends with a 1 - and if we forget about the two first items in the list, then we could drop the last bit altogether. As can be seen from the ''Nodal Path'' column in the list, that's exactly what we do in path traversal. This can't usually work with normal numeric data types because ''0'' and ''00'' evaluate to the same, but a ''sequence'' of binary digits is more like a string comparison of ''"0"'' and ''"00"''. | ||
| − | |||
| − | |||
So that's how the binary conversion from a decimal index goes, but there's one more inefficiency to remove; every item in list-space is composed of three list-item-keys (which are each integer indexes of other items) and each index points to the middle of the three. So the index of the root item is 1, the next item is 4, then 7, 10, 13... so as you can see, a division by three can be done to ensure that we're not missing out any binary paths. Actually we subtract one, then divide by three giving us a proper zero-based integer range of binary paths. | So that's how the binary conversion from a decimal index goes, but there's one more inefficiency to remove; every item in list-space is composed of three list-item-keys (which are each integer indexes of other items) and each index points to the middle of the three. So the index of the root item is 1, the next item is 4, then 7, 10, 13... so as you can see, a division by three can be done to ensure that we're not missing out any binary paths. Actually we subtract one, then divide by three giving us a proper zero-based integer range of binary paths. | ||
*'''See Also:''' [[Wikipedia:Trie]] | *'''See Also:''' [[Wikipedia:Trie]] | ||
Revision as of 21:57, 31 January 2006
The array elements of the @space are all identified by an integer index which starts at 0 for the first element created, and one for the next and so on. All integers can be represented as a unique binary sequence as in the decimal and binary columns of the following list of example index numbers:
| Decimal | Binary | Nodal Path |
|---|---|---|
| 0 | 0 | never traversed |
| 1 | 1 | never traversed |
| 2 | 10 | 0 |
| 3 | 11 | 1 |
| 4 | 100 | 0-0 |
| 100 | 1100100 | 0-0-1-0-0-1 |
| 1000 | 1111101000 | 0-0-0-1-0-1-1-1-1 |
| 1023 | 1111111111 | 1-1-1-1-1-1-1-1-1 |
| 1024 | 10000000000 | 0-0-0-0-0-0-0-0-0-0 |
| 1025 | 10000000001 | 1-0-0-0-0-0-0-0-0-0 |
Both the decimal and the binary numbers really have an infinite number of leading zeros before them, but we can still maintain a unique sequence of digits to represent every integer even if we omit all leading zeros as we have in this table. The point is that this rule means that every single number except for 0 always ends (when reading from right to left) with a non-zero digit. While this may not be of much interest for most number systems, you will notice that with binary it means that every number except zero ends with a 1 - and if we forget about the two first items in the list, then we could drop the last bit altogether. As can be seen from the Nodal Path column in the list, that's exactly what we do in path traversal. This can't usually work with normal numeric data types because 0 and 00 evaluate to the same, but a sequence of binary digits is more like a string comparison of "0" and "00".
So that's how the binary conversion from a decimal index goes, but there's one more inefficiency to remove; every item in list-space is composed of three list-item-keys (which are each integer indexes of other items) and each index points to the middle of the three. So the index of the root item is 1, the next item is 4, then 7, 10, 13... so as you can see, a division by three can be done to ensure that we're not missing out any binary paths. Actually we subtract one, then divide by three giving us a proper zero-based integer range of binary paths.
- See Also: Wikipedia:Trie
