Geek asks and answers

Keyword Search Tables in Existing Tables

I have doubts about one of my book statements.

Speaking of searching by keywords in the symbol table, at some point he says: “If there are no records (but only keys), we can use the bit table. In this case, the symbol table is called the existence table, since we can consider the kth bit as an indicator of whether the key is k or not in the table. For example, using a 313-word table on a 32-bit computer, we can use this to quickly determine if this 4-digit internal phone number has been assigned. "

Well, I know what a word is, so in this case the existence table should be a 10.016-bit table. But what does this mean? What is the reason for this 4-digit phone number? So, how can you implement a character search table with keywords when records match keys?

+3
source share
2 answers

There are 9,000 four-digit numbers (in base 10, decimal) and 10,000 (non-negative) numbers with no more than four digits, so a table with more than 10,000 bits is sufficient to indicate for each of these numbers whether it is present (bit bit nset or no?). For five-digit numbers - 90,000 of them - you will need a larger table.

- ", " ", ", , - , . , , () , . .

+2

10000 ( , ), 313 (10000/32 = 312,5 ~ = 313)

+2

More articles:


All Articles