java - 电话号码前缀查询

Question

我必须实现基于 Java 的调用路由引擎，该引擎根据电话号码前缀将调用路由到适当的网关。

我的表 (postgres) 包含前缀:

CREATE TABLE call_routing (
  prefix character varying(20) PRIMARY KEY NOT NULL,
  carrier character varying(50) NOT NULL,
  dialstring character varying(50) NOT NULL
)

一些示例数据:

INSERT INTO call_routing values ('02','1','/sofia/gateway/gw1');
INSERT INTO call_routing values ('0221','1','/sofia/gateway/gw2');
INSERT INTO call_routing values ('0228','1','/sofia/gateway/gw3');

例如，电话号码 0221123456789 应该路由到网关“/sofia/gateway/gw2”，电话号码 0211123456789 应该路由到“/sofia/gateway/gw1”，等等。

问题:

1. 使用 java/jdbc 查询最佳匹配前缀的最快方法是什么。
2. 将应用程序启动时的表读入 java 对象并在 java 中执行所有操作而无需在每次调用时访问数据库是否是更好的方法？

Answer 1

获得更好的索引

直接按前缀排序，而不是长度(前缀):

SELECT dialstring FROM call_routing
WHERE number like prefix || '%'
ORDER BY prefix DESC
LIMIT 1

为什么？

因为选中的行为一个数字abcdef将是前缀。数字也是如此:

一个 ab 美国广播公司 abcd

因此，如果您按字母顺序对它们进行排序，就足以得到一个从最长到最短的列表，这就是您想要的。

您还可以使用以下方法获得更强的过滤器:

prefix between 'a' and 'abcde' .您所有的前缀都将按字母顺序排列 >=最短的前缀和字母顺序 <=最长的。

所以可以表示为:

SELECT dialstring FROM call_routing WHERE
prefix between substr(number, 1, 1) and number -- range filter (use index)
AND number like prefix || '%' -- only relevant data (normal filter)
ORDER BY prefix DESC -- index will work
LIMIT 1

当然，索引将位于列前缀上。

全部缓存？

是的，请。 :)

你有多少元素？如果列表不是很大，将其加载到内存中。

然后你可以有一个 TreeMap(如果你想按前缀排序)或 HashMap(如果你更喜欢先找到最长的前缀，然后每次尝试少一个字符)。哪一个会更好？取决于 a >> abcde 范围内的前缀数量并且不匹配 like条件(以 abbde 为例)。

如果条目不多

您可以使用一个数组，按前缀 desc 排序:

be
b
abcde
abbbc
abd
ab

要找到好的前缀，请执行 Arrays.binarySearch(T[], T key, Comparator<T>)查看您的手机是否在其中 ( abcde )。如果是……好吧。如果不是你继续前进，直到:

- you find a prefix (OK, this is the winner)
- it doesn't start with the same char (there are no prefix)

这样您将遍历范围 abcde >> a并找到第一个前缀(它是最长的前缀)。

好的

正在制作 T-R-E-E(我不确定名字)。制作一棵树，其中每个节点仅包含一个字母(在您的情况下为数字)。

0 // represents 0
 ->
   2  // represents 02
     -> 1 // represents 021
     -> 3 // represents 023
 ->
   4 // represents 04

因此，当您寻找最长的前缀时，您会尝试在树中尽可能深入:

Node n = root;
for (char c: number) {
    if ((child = n.hasChild(c)) != null)
    {
       prefix += c;
       n = child;
    }
    else
       break;
}

你只需要一个来创建一个

class Node
{
   int digit;
   Map<Integer, Node> childs = new HashMap<Integer, Node>(); // or a 10 bucket array :)
   YourInfo info;
}

创建结构:

findOrCreateNode(prefix).setInfo(info);

其中 findOrCreateNode 与以前相同，但当它找不到节点时...创建它 ( n.put(c, new Node(c)))。