[發(fā)明專利]一種基于反向索引的航程匹配優(yōu)化及實現(xiàn)方法

有效

• 申請?zhí)枺?/td>: 201610069083.9
• 申請日: 2016-04-18
• 公開（公告）號: CN105740433B
• 公開（公告）日: 2019-05-24
• 發(fā)明（設(shè)計）人: 趙志剛;黃曉軍
• 申請（專利權(quán)）人: 深圳馬可孛羅科技有限公司
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/2453
• 代理公司: 唐山永和專利商標(biāo)事務(wù)所 13103
• 代理人: 王永紅

1.一種基于反向索引的航程匹配優(yōu)化及實現(xiàn)方法，其特征在于包括以下步驟：

1）存儲航程區(qū)域與城市的對應(yīng)關(guān)系種子數(shù)據(jù)，建立航程區(qū)域與城市的正向索引；

建立航程區(qū)域與城市的正向索引方法為：

（1）以航程區(qū)域為鍵，以城市列表為值，將存儲區(qū)域與城市列表的對應(yīng)關(guān)系存儲到K-V數(shù)據(jù)庫作為種子數(shù)據(jù)；

（2）建立區(qū)域列的hash索引；

正向索引的結(jié)構(gòu)如下：

航程區(qū)域-城市正向數(shù)據(jù)：航程區(qū)域-城市對應(yīng)關(guān)系的數(shù)據(jù)區(qū)是一個鍵值對組成的堆，其鍵為區(qū)域碼，值為城市列表；區(qū)域鍵通過指針指向城市進(jìn)行關(guān)聯(lián)；

航程區(qū)域-城市正向索引：航程區(qū)域-城市正向索引是以區(qū)域碼hash值為基礎(chǔ)建立的數(shù)據(jù)指針數(shù)組，當(dāng)需要進(jìn)行匹配時計算hash值后直接定位到數(shù)據(jù)指針從而獲取數(shù)據(jù)；

2）建立航程區(qū)域與城市的反向索引；

反向索引建立方法為：

（1）根據(jù)區(qū)域與城市列表的對應(yīng)關(guān)系種子數(shù)據(jù)，將航程解析為出發(fā)城市列表與抵達(dá)城市列表；

（2）以城市為鍵，所屬的航程區(qū)域列表為值，建立航程區(qū)域與城市的反向hash索引，并存儲至K-V數(shù)據(jù)庫；

反向索引的結(jié)構(gòu)如下：

城市-航程區(qū)域反向數(shù)據(jù)：城市-航程區(qū)域?qū)?yīng)關(guān)系的數(shù)據(jù)區(qū)同樣是一個鍵值對組成的堆，鍵是城市碼，值是城市所屬的區(qū)域列表；

城市-航程區(qū)域反向索引：城市-航程區(qū)域反向索引是以城市碼hash值為基礎(chǔ)建立的數(shù)據(jù)指針數(shù)組，當(dāng)需要進(jìn)行匹配時計算hash值后直接定位到數(shù)據(jù)指針從而獲取數(shù)據(jù)；

3）根據(jù)反向索引定位城市是否屬于航程區(qū)域；

（1）通過反向索引中的城市鍵值，以城市鍵值為偏移量，在反向索引數(shù)組中定位該城市鍵值是否已存在，若存在，則進(jìn)入下一步；反之結(jié)束；

（2）根據(jù)通過反向索引數(shù)組中的指針獲取城市-航程區(qū)域列表數(shù)據(jù)，得到所有的城市所屬各級航程區(qū)域：國家、地區(qū)、大區(qū)；直接根據(jù)目標(biāo)航程區(qū)域級別將定位城市與得到的各級航程區(qū)域進(jìn)行匹配，時間復(fù)雜度O（1）；

4）索引維護(hù)：新增或修改區(qū)域與城市對應(yīng)關(guān)系種子數(shù)據(jù)時，直接替換相應(yīng)鍵值對應(yīng)的value值，時間復(fù)雜度O（1）。

2.如權(quán)利要求1所述的一種基于反向索引的航程匹配優(yōu)化及實現(xiàn)方法，其特征在于：所述步驟4）中，索引維護(hù)方法如下：

（1）計算新航程區(qū)域碼的hash值；

（2）以hash值為偏移量，在正向hash索引數(shù)組中判斷該hash值是否已存在，若已存在則進(jìn)入步驟（3），反之進(jìn)入步驟（5）；

（3）根據(jù)hash索引指針定位航程區(qū)域-城市數(shù)據(jù)及其反向數(shù)據(jù)，移除航程區(qū)域hash索引值；

（4）移除對應(yīng)的航程區(qū)域-城市數(shù)據(jù)，從反向數(shù)據(jù)中刪除各城市所屬航程區(qū)域列表中的對應(yīng)航程區(qū)域；

（5）插入新的航程區(qū)域及其城市列表數(shù)據(jù)，通過城市列表定位對應(yīng)的城市-航程區(qū)域數(shù)據(jù)，并將新航程區(qū)域附加到航程區(qū)域數(shù)據(jù)尾部，若不存在對應(yīng)的城市-航程區(qū)域數(shù)據(jù)，則新建城市-航程區(qū)域數(shù)據(jù)接口；

（6）通過hash值將數(shù)據(jù)指針插入hash索引數(shù)組，生成新索引。