[發明專利]一種基于反向索引的航程匹配優化及實現方法

有效

• 申請號: 201610069083.9
• 申請日: 2016-04-18
• 公開（公告）號: CN105740433B
• 公開（公告）日: 2019-05-24
• 發明（設計）人: 趙志剛;黃曉軍
• 申請（專利權）人: 深圳馬可孛羅科技有限公司
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/2453
• 代理公司: 唐山永和專利商標事務所 13103
• 代理人: 王永紅

本發明涉及一種基于反向索引的航程匹配優化及實現方法，其步驟：存儲航程區域與城市的對應關系種子數據，建立航程區域與城市的正向索引；建立航程區域與城市的反向索引；根據反向索引定位城市是否屬于航程區域；通過反向索引中的城市鍵值，以城市鍵值為偏移量，在反向索引數組中定位該城市鍵值是否已存在，若存在，則進入下一步；反之結束；根據通過反向索引數組中的指針獲取城市?航程區域列表數據，得到所有的城市所屬各級航程區域；直接根據目標航程區域級別將定位城市與得到的各級航程區域進行匹配；索引維護：新增或修改區域與城市對應關系種子數據時，直接替換相應鍵值對應的value值，時間復雜度O（1）。本發明實現了O(1)的查詢時間復雜度及O(n)的存儲空間復雜度。

技術領域

本發明涉及一種航程區域模糊匹配優化方法，特別是關于一種在計算機領域中應用的基于反向索引的航程匹配優化及實現方法。

背景技術

隨著互聯網行業的迅速發展，通過網絡預訂機票方式也逐漸普及，目前市場上許多航空公司都有自己的運價及優惠政策。這些政策一般是以國家或區域為單位進行劃分的（如中國到美國，亞洲到美洲等），體現在具體的地址時則是少則數十，多則數百甚至上千座城市的排列組合。

通常現有的航程匹配模式是通過關系型數據庫存儲相應的城市對后進行城市對的精確匹配或者存儲城市列表后進行模糊匹配，這兩種方法都有各自的弊端與不足：1、存儲城市對進行精確匹配的弊端在于，由于需要將區域進行排列組合，這將消耗大量的存儲空間——對于一個包含N座城市的出發區域及M座城市的抵達區域，需要存儲N乘M項的城市對組合。且隨著航程數目的增加，組合數量將會呈指數級別的增長。因此將會導致搜索性能的線性下降及越來越大的數據維護代價。2、儲城市列表進行模糊匹配的弊端在于，由于只能進行模糊匹配，每次查詢都需要讀取所有的數據后進行遍歷查找。這會導致巨大的IO讀取開銷，以致當并發查詢數達到某個臨界點時系統的整體吞吐量及響應時間呈指數級別的下降。

發明內容

針對上述問題，本發明的目的是提供一種基于反向索引的航程匹配優化及實現方法，其對于復雜區域的航程存儲與高性能匹配問題實現了O(1)的查詢時間復雜度及O(n)的存儲空間復雜度。

為實現上述目的，本發明采取以下技術方案：一種基于反向索引的航程匹配優化及實現方法，其特征在于包括以下步驟：1）存儲航程區域與城市的對應關系種子數據，建立航程區域與城市的正向索引；2）建立航程區域與城市的反向索引；3）根據反向索引定位城市是否屬于航程區域；（1）通過反向索引中的城市鍵值，以城市鍵值為偏移量，在反向索引數組中定位該城市鍵值是否已存在，若存在，則進入下一步；反之結束；（2）根據通過反向索引數組中的指針獲取城市-航程區域列表數據，得到所有的城市所屬各級航程區域：國家、地區、大區；直接根據目標航程區域級別將定位城市與得到的各級航程區域進行匹配，時間復雜度O（1）；4）索引維護：新增或修改區域與城市對應關系種子數據時，直接替換相應鍵值對應的value值，時間復雜度O（1）。

進一步，所述步驟1）中，建立航程區域與城市的正向索引方法為：（1）以航程區域為鍵，以城市列表為值，將存儲區域與城市列表的對應關系存儲到K-V數據庫作為種子數據；（2）建立區域列的hash索引。

進一步，所述步驟1）中，正向索引的結構如下：航程區域-城市正向數據：航程區域-城市對應關系的數據區是一個鍵值對組成的堆，其鍵為區域碼，值為城市列表；區域鍵通過指針指向城市進行關聯；航程區域-城市正向索引：航程區域-城市正向索引是以區域碼hash值為基礎建立的數據指針數組，當需要進行匹配時計算hash值后直接定位到數據指針從而獲取數據。

進一步，所述步驟2）中，反向索引建立方法為：（1）根據區域與城市列表的對應關系種子數據，將航程解析為出發城市列表與抵達城市列表；（2）以城市為鍵，所屬的航程區域列表為值，建立航程區域與城市的反向hash索引，并存儲至K-V數據庫。