电话号码前缀查找

我必须实现基于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/ggateway/gw2"，电话号码021112345678应路由到"/sofia/ggateway-gw1"，等等。

问题：

使用java/jdbc查询最佳匹配前缀的最快方法是什么
在应用程序启动时将表读取到java对象中，并在每次调用都不访问数据库的情况下用java执行所有操作，这是一种更好的方法吗

获得更好的索引

通过直接按前缀而非长度（前缀）排序：

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

为什么？

因为为数字abcdef选择的行将是前缀。像这样的数字也是如此

aababcabcd

所以，如果你按字母顺序排列，就足以得到一个从最长到最短的列表，这就是你想要的。

此外，你可以使用获得更强的过滤器

CCD_ 2。所有前缀按字母顺序排列，>=是最短的前缀，<=是最长的前缀。

因此可以表示为：

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))）。

我个人会缓存表，但您可以通过按长度排序来获得最佳匹配前缀（number是您正在搜索的）：

SELECT dialstring FROM call_routing WHERE strpos(number, prefix) = 1 ORDER BY length(prefix) DESC LIMIT 1;

我对此感到好奇。看起来最大的问题是您有陷阱（示例中的gw1）。

SELECT dialstring from call_routing where number like prefix || '%'
ORDER BY length(prefix) DESC
LIMIT 1

索引这将是困难的，但我想第一个问题是，你跟踪了多少呼叫前缀？

您还可以在github上查看PostgreSQL模块，该模块专门用于为电话号码提供快速前缀匹配：https://github.com/dimitri/prefix

相关内容

最新更新

热门标签：