Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Given the standard North American phone number format: (Area Code) Exchange - Subscriber, the set of possible numbers is about 6 billion. However, efficiently breaking down the nodes into the sections listed above would yield less than 12000 distinct nodes that can be arranged in groupings to get all the possible numbers.

This seems like a problem already solved.

Would it done via a graph or tree?

share|improve this question
6  
Prefix trees / tries might be what you're looking for. –  birryree Apr 14 '12 at 21:59
1  
@birryree You should answer it in an answer instead of a comment, cause I think this is exactly it. –  Spencer Kormos Apr 14 '12 at 22:10
    
If you are storing all possible numbers, why do you need to search them? On the otherhand, If you are storing only actual numbers, then searching makes sense to me in that case. –  Emmad Kareem Apr 14 '12 at 22:41
    
@EmmadKareem It was an easier question to ask, instead of qualifying. Let's just say that there are much more than 5, but still less than 6 billion. :-) –  Spencer Kormos Apr 15 '12 at 1:10
1  
You want to store it efficently... for what? For searching speed? Minimum memory usage? Define what the goals are here. –  GrandmasterB Apr 15 '12 at 3:43
show 2 more comments

4 Answers 4

up vote 6 down vote accepted

A comment you placed on the question:

It was an easier question to ask, instead of qualifying. Let's just say that there are much more than 5, but still less than 6 billion. :-)

So it sounds like you intend to store all current valid phone numbers, in the range of (000) 000-0000 through (999) 999-9999. So the set of possible numbers is 10,000,000,000, or, 10 billion.

This number can immediately be reduced to less than 8 billion, since the first digit in an area code cannot be a 0 or 1, area code cannot end in "11", and 555 numbers are reserved, as well as a few other rules.

Since only a maximum of 8 billion are available, and you mention storing 5-6 billion, I propose the much more space-efficient storage of the 2-3 billion unused numbers.

To generate a list of valid numbers, you would then numerically loop through all combinations, and skip numbers in the list of invalid numbers. Or, simply check to see that a number is not in the store invalid numbers, to know if it is valid.

A Trie tree or a Radix tree are most likely going to be the most space efficient while still having fast lookup/insert/remove speeds.

share|improve this answer
    
The reason I said 6 billion is that for the same reason that you reduce the "permutable" set from 10 down to 8 billion based on illegal area codes, you would do the same exact thing for exchanges, thus dropping it down another 2 billion (roughly). This then makes storing unused numbers almost as bad as used numbers. I do like the idea though. –  Spencer Kormos Apr 16 '12 at 13:53
    
@SpencerK The idea is that the search/lookup knows about the invalid patterns as well, so that numbers that match it don't need to be stored at all. If the 8 billion can be dropped to ~6 billion by the same reason, then you only have to store, what, less than 1 billion for the unused valid numbers? –  Izkata Apr 16 '12 at 14:32
    
Right. After rereading, that makes sense (fuzzy morning brain). Thanks. –  Spencer Kormos Apr 16 '12 at 14:35
add comment

If my calculations are correct, a bit array for each phone number should take about 1.2 GB of memory. Simply set the bit for each phone number that is valid.

share|improve this answer
1  
Or for each phone that is invalid as Izkata suggested. Whichever set is smaller. If there are n possible numbers, at most n/2 + 1 bits will be needed (one is for telling if we are storing the valid or the invalid numbers). –  Remo.D Apr 15 '12 at 8:10
add comment

If you were doing this for ultimate memory efficency you could do better.

Start with the area code - I don't know how many are actually used but assuming you need to store all 3 digit values.

Presumably exchange codes are filled in order, so you would expect the lower ones to be used in more areas than the higher ones. So you could use a run-length coding to flag the sequences that are in use.

Finally actual phone numbers will be used or not at random so I would use a bit field to flag which of the 9999 possible last numbers are on. At one bit/number you need only 1K to store each set.

share|improve this answer
    
Why would you assume that anything is filled in order? Why would you also assume that the lower exchange codes are used in more areas than higher ones? Unless you know some internal phone company algorithm, I don't think either of these are valid assumptions. –  Spencer Kormos Apr 16 '12 at 13:50
    
For the most efficent storage - and the only way to beat something like 'gzip' is to have knowledge of the specifics of the system. So you know that only certain area codes are used, you know that exchanges (at least in US) are generally numbered in order as the area grew. So in a big city with many area codes they will be filled - but in a rural location all numbers may start with a limited range. –  Martin Beckett Apr 16 '12 at 15:22
add comment

Graph isn't suitable for this, the implementation requires more memory than tree and it doesn't provide any additional features in this case.

Prefix trees? These are very efficient for search but memory representation isn't optimized for size. They're in fact very memory inefficient. They can also be used to compress data and write it to disk but memory representation takes much more memory than the data itself.

If you arrange by groups so only 3 last digits would be stored in the tree-like struct it'd be 3x4 + 1 bytes for each number anyway (3x4 byte pointer + 1 byte for data). ~78 GB just for 3 last digits of each number (if i remember the implementation details correctly). Which will require 64 bit pointers instead of 32b... so ~140GB of ram.

So the problem (in my opinion) is that for tree for each suffix in each group you still need at least one 32 bit pointer (which will probably turn out to be 64 bits because you'd need to allocate > 4GB for the data).

In my opinion most efficient way will be an array or 12000 pointers to structure like

char[x] prefix;
DWORD* suffixes;
int n_count;

so prefix, eg. 43333 suffix eg. 19821982 => number is 4333319821982 (n_count -> count of numbers)

You store the numbers without separators to save space, one suffix after the other (eg. number 1 is suffixes+0, number 2 is suffixes+1) and you can search efficiently too, if you have it sorted.

This way it'd take just 4(DWORD)*6 billion suffixes = 24GB of memory + size of 12k pointers + prefixes which is irrelevant

So instead of (at least!) 6 billion 64 bit pointers you'd just have (at most!) 6b of 32 bit suffixes.

But probably the numbers are continuous, so you can try array of (start_suffix, end_suffix) instead of just storing all suffixes should take much less.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.