[erlang-questions] Longest prefix match

Dragan Zubac <>
Thu Nov 29 23:19:53 CET 2007


Hello

A couple of questions regarding 'lpm' algorithm if anyone has any 
experience with this.

What would be the most elegant and efficient way for LPM ? For 
example,we have some list of numbers:

- 889123456
- 44712345678
- 5550123456789
- 32112345
- 5501

and the desired number for example:

550123555666

I guess the most efficient way would be to use some sort of 'tree' and 
traverse each number from the beginning of destination number and check 
it in number's list and if we can't match N position to claim it to be 
the longest prefix match ? 

Second question is the same as question one,but implies that to have 
some additional data with prefix (route,price,user_id,etc.),what would 
be algorithm looks like in this situation ? For example:

- 889123456,100
- 44712345678,100
- 5550123456789,101
- 32112345,101
- 5501,100
- 5550123456789,100

number is 550123555666,100 ,the problem would be to find LPM for 
specific price (100),in this case there's no unique prefix,but there's 
unique prefix+price 'object'.

Anybody had any experience with this issues ?

Sincerely

Dragan Zubac





More information about the erlang-questions mailing list