Longest Prefix Match for Phone Numbers

[c0reM]

Hi all,

This is a problem I've been grapping with for a few months on and off and I can't seem to crack it...

I have a CSV list of call detail records and a list of long distance rates and I need to be able to match the rate to the phone number based on the longest prefix match.

Here is sample of what the rate table looks like:

[TABLE="width: 400"]
<colgroup><col><col><col></colgroup><tbody>[TR]
[TD]destination
[/TD]
[TD="align: right"]prefix
[/TD]
[TD="align: right"]rate
[/TD]
[/TR]
[TR]
[TD]Finland - Mobile
[/TD]
[TD="align: right"]3584571[/TD]
[TD="align: right"]0.34[/TD]
[/TR]
[TR]
[TD]Finland - NGN - personal[/TD]
[TD="align: right"]35871[/TD]
[TD="align: right"]0.1[/TD]
[/TR]
[TR]
[TD]Finland - Other
[/TD]
[TD="align: right"]3589315980[/TD]
[TD="align: right"]0.1[/TD]
[/TR]
[TR]
[TD]Finland - Sonera Mobile[/TD]
[TD="align: right"]35840[/TD]
[TD="align: right"]0.34[/TD]
[/TR]
[TR]
[TD]Finland - Sonera Mobile[/TD]
[TD="align: right"]35842[/TD]
[TD="align: right"]0.34[/TD]
[/TR]
[TR]
[TD]Finland[/TD]
[TD="align: right"]358[/TD]
[TD="align: right"]0.1[/TD]
[/TR]
[TR]
[TD]Finland[/TD]
[TD="align: right"]35819[/TD]
[TD="align: right"]0.1[/TD]
[/TR]
[TR]
[TD]Finland[/TD]
[TD="align: right"]35829[/TD]
[TD="align: right"]0.1[/TD]
[/TR]
[TR]
[TD]Finland[/TD]
[TD="align: right"]3587[/TD]
[TD="align: right"]0.1[/TD]
[/TR]
[TR]
[TD]Finland[/TD]
[TD="align: right"]35870[/TD]
[TD="align: right"]0.1[/TD]
[/TR]
[TR]
[TD]Finland[/TD]
[TD="align: right"]3589[/TD]
[TD="align: right"]0.1[/TD]
[/TR]
[TR]
[TD]France - Mobile Bouygues
[/TD]
[TD="align: right"]336003[/TD]
[TD="align: right"]0.47[/TD]
[/TR]
</tbody>[/TABLE]


The other table I have looks like this:

[TABLE="width: 178"]
<colgroup><col><col></colgroup><tbody>[TR]
[TD]To
[/TD]
[TD]Duration[/TD]
[/TR]
[TR]
[TD="align: right"]14734334000
[/TD]
[TD="align: right"]0:19:47[/TD]
[/TR]
[TR]
[TD="align: right"]3222735856
[/TD]
[TD="align: right"]0:02:09[/TD]
[/TR]
[TR]
[TD="align: right"]35622458106
[/TD]
[TD="align: right"]0:06:47[/TD]
[/TR]
[TR]
[TD="align: right"]35622458130
[/TD]
[TD="align: right"]0:03:41
[/TD]
[/TR]
</tbody>[/TABLE]

The first table has about 150,000 rows worth of prefixes.

My ultimate goal would be to generate a third table that would append the rate to a new column like this (not real data):

[TABLE="width: 178"]
<tbody>[TR]
[TD]To
[/TD]
[TD]Duration
[/TD]
[TD] Cost
[/TD]
[/TR]
[TR]
[TD="align: right"]14734334000
[/TD]
[TD="align: right"]0:19:47
[/TD]
[TD="align: right"]2.54
[/TD]
[/TR]
[TR]
[TD="align: right"]3222735856
[/TD]
[TD="align: right"]0:02:09[/TD]
[TD="align: right"]0.54
[/TD]
[/TR]
[TR]
[TD="align: right"]35622458106
[/TD]
[TD="align: right"]0:06:47[/TD]
[TD="align: right"]...
[/TD]
[/TR]
[TR]
[TD="align: right"]35622458130
[/TD]
[TD="align: right"]0:03:41
[/TD]
[TD="align: right"]...
[/TD]
[/TR]
</tbody>[/TABLE]

My biggest sticking point is finding a formula or set of formulas that will allow a longest prefix match in Excel. The closest I came was to make an insanely large spreadsheet with multiple columns with prefix length 1, 2, 3,4, 5, 6 and so on and then grabbing the largest value but it was insanely messy and incredibly inefficient (and didn't work properly).

Hopefully some guru here can help with this one!

 

[RobertSF]

What do you mean by "longest prefix match?" Although I see the prefixes are of different lengths, are there non-exact matches? For example, in your example rate table I see a 3587 and a 35870 prefix. Will there be calls to a 35871 prefix that, although not on the rate table, must still be matched, and the correct prefix to match it with is 35870 and not 3587?

The VLOOKUP function can find exact or non-exact matches. Have you played around with it?

 

[c0reM]

Hey RobertSF,

What I mean by "longest prefix match" is this:

Suppose we take the number 35622458106 as an example.

If the rate table has the following prefix entries:

35
356
35622

Even though the prefixes 35 and 356 match the number being checked against, these matches should be disregarded because there exists a better (longer) prefix match, in this case 35622. Note when I say "prefix" I mean what I'm trying to match against is the longest possible exact match from left to right.

The VLOOKUP function can get me part of the way but what it seems to do is take (if I remember correctly) the first match and not the longest one. I made many attempts trying to mix VLOOKUP with something like =LEFT(A1,LEN(A1)-1) to truncate characters to the right successively but I also need to be able to iterate it and choose the longest match which is where I get totally lost.

Will there be calls to a 35871 prefix that, although not on the rate table, must still be matched, and the correct prefix to match it with is 35870 and not 3587?

The rate table has ~150,000 rows and contains all possible prefixes for a minimum 2 digit prefix match. The matches must be exact and there shouldn't be any "fuzzy matching".

I'm usually pretty handy with Excel but this one has really left me struggling

 

[Eric W]

Here's one way:

	A	B	C	D	E	F	G	H	I
destination	prefix	rate	To	Duration	Rate	Cost
Finland - Mobile
Finland - NGN - personal
Finland - Other	3589315980	3584571999
Finland - Sonera Mobile
Finland - Sonera Mobile
Finland
Finland
Finland
Finland
Finland
Finland
France - Mobile Bouygues

<colgroup><col style="width: 25pxpx"><col><col><col><col><col><col><col><col><col></colgroup><thead>
</thead><tbody>
[TD="align: center"]1[/TD]

[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]2[/TD]

[TD="align: right"]3584571[/TD]
[TD="align: right"]0.23[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"]358111111[/TD]
[TD="align: right"]0:19:47[/TD]
[TD="align: right"]0.1[/TD]
[TD="align: right"] $ 1.98 [/TD]

[TD="align: center"]3[/TD]

[TD="align: right"]35871[/TD]
[TD="align: right"]0.1[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"]358421111[/TD]
[TD="align: right"]0:02:09[/TD]
[TD="align: right"]0.34[/TD]
[TD="align: right"] $ 0.73 [/TD]

[TD="align: center"]4[/TD]

[TD="align: right"]0.1[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: right"]0:06:47[/TD]
[TD="align: right"]0.23[/TD]
[TD="align: right"] $ 1.56 [/TD]

[TD="align: center"]5[/TD]

[TD="align: right"]35840[/TD]
[TD="align: right"]0.34[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"]3799999[/TD]
[TD="align: right"]0:03:41[/TD]
[TD="align: right"]0[/TD]
[TD="align: right"] $ - [/TD]

[TD="align: center"]6[/TD]

[TD="align: right"]35842[/TD]
[TD="align: right"]0.34[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]7[/TD]

[TD="align: right"]358[/TD]
[TD="align: right"]0.1[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]8[/TD]

[TD="align: right"]35819[/TD]
[TD="align: right"]0.1[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]9[/TD]

[TD="align: right"]35829[/TD]
[TD="align: right"]0.1[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]10[/TD]

[TD="align: right"]3587[/TD]
[TD="align: right"]0.1[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]11[/TD]

[TD="align: right"]35870[/TD]
[TD="align: right"]0.1[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]12[/TD]

[TD="align: right"]3589[/TD]
[TD="align: right"]0.1[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]13[/TD]

[TD="align: right"]336003[/TD]
[TD="align: right"]0.47[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

</tbody>

Sheet2​

[TABLE="width: 85%"]
<tbody>[TR]
[TD]Worksheet Formulas[TABLE="width: 100%"]
<thead>[TR="bgcolor: [URL=https://www.mrexcel.com/forum/usertag.php?do=list&action=hash&hash=DAE7F5]#DAE7F5[/URL] "]
[TH="width: 10px"]Cell[/TH]
[TH="align: left"]Formula[/TH]
[/TR]
</thead><tbody>[TR]
[TH="width: 10px, bgcolor: [URL=https://www.mrexcel.com/forum/usertag.php?do=list&action=hash&hash=DAE7F5]#DAE7F5[/URL] "]I2[/TH]
[TD="align: left"]=G2*24*H2*60[/TD]
[/TR]
</tbody>[/TABLE]
[/TD]
[/TR]
</tbody>[/TABLE]

[TABLE="width: 85%"]
<tbody>[TR]
[TD]Array Formulas[TABLE="width: 100%"]
<thead>[TR="bgcolor: [URL=https://www.mrexcel.com/forum/usertag.php?do=list&action=hash&hash=DAE7F5]#DAE7F5[/URL] "]
[TH="width: 10px"]Cell[/TH]
[TH="align: left"]Formula[/TH]
[/TR]
</thead><tbody>[TR]
[TH="width: 10px, bgcolor: [URL=https://www.mrexcel.com/forum/usertag.php?do=list&action=hash&hash=DAE7F5]#DAE7F5[/URL] "]H2[/TH]
[TD="align: left"]{=MOD(MAX(IF(LEFT(F2,LEN($B$2:$B$13))=$B$2:$B$13&"",LEN($B$2:$B$13)+$C$2:$C$13/100)),1)*100}[/TD]
[/TR]
</tbody>[/TABLE]
Entered with Ctrl+Shift+Enter. If entered correctly, Excel will surround with curly braces {}.
Note: Do not try and enter the {} manually yourself[/TD]
[/TR]
</tbody>[/TABLE]



I tweaked the tables a bit to illustrate how it works. The rate lookup is an array formula, enter it, update the ranges to match your sheet, and confirm with Control+Shift+Enter.

I'm worried a bit about performance. If you have 150,000 prefixes in your table, and you have a lot of these formulas, it could slow down your sheet noticeably. You might want a macro that you run on-demand, which would probably run much faster. But try this out and let us know.

 

[c0reM]

Hi Eric,

Not going to lie, I'm blown away at how fast you were able to find a function to make this work! I've tested it on the real datasets and it does what it says on the tin. The processing time is noticeable as you said but it's more than reasonable on a quick computer (seems to be about 1 second per 200 rows in the "destination" table).

I would never have thought to use the MOD function and it will probably take me about an hour to figure out how this actually works but thanks a million. Longest prefix match in Excel has been asked tons of times online based on my research and you are the first to have cracked it in my travels

Cheers!

 

[Eric W]

I'm glad it works for you!

To see how it works, run it through the Evaluate Formula tool on the Formulas tab. (Preferably on the small sample size.) In short, it finds the length of all the prefixes in column B, does a LEFT of F2 for all those lengths, and compares those with the associated prefix. If they match, then we save the length of the prefix + the rate divided by 100. So on the F3 cell, we'd match on 3584571 and 358, giving 7.0023 and 3.001. The MAX of those is 7.0023. Then the MOD(7.0023, 1) takes off the 7 giving .0023, and multiply by 100 to get .23 back again.

I've seen something similar before, but it's always fun to apply old tricks to new problems! Good luck!