電話號碼前綴查找

我必須實現基於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應該被路由到網關「/索菲亞/網關/ GW2」，電話號碼0211123456789應該被路由到「/ sofia/gateway/gw1」等。

問題：

用java/jdbc查詢最佳匹配前綴的最快方法是什麼？
這是一個更好的方法來讀取應用程序啓動時的表到java對象，並在每次調用沒有數據庫訪問java中做所有的事情？

來源

2012-08-31 markus

數據庫只包含2位或4位前綴號碼？或者更多，更少？ – chris

前綴可以從2到7位數 – markus

得到一個更好的索引

通過對前綴直接訂貨，而不是長度（前綴）：

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

爲什麼？

因爲數字abcdef的選定行將作爲前綴。所以會像數字：

一個 AB ABC 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

當然和索引將在列前綴。

Cache all？

是的，請。 :)

你有多少物品？如果它不是一個巨大的列表，請將其加載到內存中。

然後你可以有一個TreeMap（如果你想要通過前綴命令）或一個HashMap（如果你希望首先找到最長的前綴，並繼續嘗試每次少用一個字符）。哪一個會更好？取決於a >> abcde範圍內的前綴數量，並且不符合like條件（例如，abbde）。

如果沒有很多條目

你可以使用一個數組，由前綴降序排序：

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

來源

2012-08-31 11:53:02 helios

我將您的查詢與David的查詢進行了比較，兩者均在我的環境中在44ms內執行，並在call_routing表中包含1538個條目。只有1538個條目，我認爲在內存緩存是更好的方法，但是當有更改時，我必須重新加載表。 – markus

是的。肯定它值得緩存。 – helios

如果你想緩存看：http://www.java2s.com/Code/Java/Collections-Data-Structure/CharPrefixTree。htm它具有我提到的樹形結構。 – helios

我個人緩存表，但你可以通過長下令獲得最佳匹配前綴（number是你要搜索的內容）：

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

來源

2012-08-31 10:36:17

我認爲它應該是：SELECT dialstring FROM call_routing WHERE strpos（number，prefix）= 1 ORDER BY length（prefix）DESC LIMIT 1; – markus

@markus：是的，這就是我的意思:) –

你有沒有建議如何索引表，以獲得該查詢的最佳性能？ – markus

我想知道這一點。看起來最大的問題是你有catchalls（在你的例子中是gw1）。

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

索引這將是困難的，但我想第一個問題是，有多少個呼叫前綴你跟蹤？

來源

2012-08-31 11:43:25

你也可以看在github上這個PostgreSQL的模塊，特別是指爲電話號碼提供快速前綴匹配： https://github.com/dimitri/prefix

來源

2012-08-31 13:35:58

是的，我已經看到它。你知道它是否穩定？ – markus

電話號碼前綴查找

回答

相關問題