數據庫專題訓練

任務

實現近似串查詢，近似串有兩種度量方式：Levenshtein edit distance和Jaccard index。需要實現SimSeacher類的createIndex、searchED、searchJaccard三個方法。

代碼中實現了brute-force、tournament sort、MergeSkip@LLL08和DivideSkip@LLL08四種查詢算法。

BruteForce

枚舉所有字符串，和查詢字符串一一進行Levenshtein edit distance或Jaccard index的計算， 若滿足閾值條件則添加到存放結果的向量。

Tournament sort

採用filter-and-verification framework，代碼中實現了索引、Filter和Verification三個部分。

索引

索引的數據結構是若干倒排索引，另外有一個hash table爲Q-gram到倒排索引的映射。

執行createIndex構建索引時， 對於每個輸入的字串，使用類似Rabin-Karp string search算法的方式，獲取當前長爲的窗口中的Q-gram，計算出散列值，找到對應的倒排索引，並在該索引末端加入當前行號。如果輸入字串有重複的Q-gram，那麼當前行號可能會在倒排索引中插入多次。然後窗口向右移動一格，把之前的散列值通過rolling hash計算出下一時刻的值。

輸入文件讀入完畢後，對於hash table中的每個倒排索引(必然是非空的)，在末端加入作爲哨兵元素的無窮大。

Filter

對於一個查詢，使用類似構建索引時的Rabin-Karp string search algorithm，對於每個長爲的窗口中的Q-gram，找到對應的倒排索引，把指向首元素的指針放入列表中。設查詢字串長度位，那麼中將會有個指針(可能重複)。

建立binary heap

列表的元素是指向倒排索引的指針，以指針指向的值爲關鍵字使用Floyd’s algorithm 在時間內建立binary heap 。

Tournament sort進行N-way merge

  1. 堆頂指針指向的值爲，若old爲無窮大則返回

  2. 計算堆頂元素指向的值的出現次數，若大於等於閾值則添加到候選集中

  3. 把堆頂元素指針向前移動一格(即指向對應的倒排索引的下一項)，若下一項仍等於原來指向的值則繼續移動

  4. 上述操作後堆頂指針指向的值變大了，對它進行下濾操作

  5. 若新的堆頂指向的值等於則跳轉到步驟3

之後對候選集的每個元素進行檢驗，是否滿足Jaccard index或Levenshtein編輯距離的閾值要求， 輸出篩選後的。

Verification

Levenshtein edit distance

對於searchED操作，需要對每個候選字串和查詢字串計算編輯距離。

兩個字符串的Levenshtein edit distance可以使用的Needleman–Wunsch algorithm計算。

注意到代碼中使用到編輯距離的地方都有閾值限制，如果編輯距離超過閾值，那麼它的實際值無關緊要。因此我們可以只計算動態規劃矩陣中對角線帶狀區域的狀態。

另外當其中某個字符串的長度小於等於128時，還可以採用bit vector的算法@edit03加速到。

Jaccard index

採用scan count的方式。 先用rolling hash計算查詢串所有Q-gram的標號，在計數容器中增加一。然後對於候選串的所有Q-gram，若計數容器中的值大於零則減去零並加到答案中。再便利候選串的所有Q-gram，把減去的值再加回來。

MergeSkip

和tournament sort基本結構相同，對Filter部分做了優化，即優化了統計每個字串的出現次數，過程如下：

  1. 堆頂指針指向的值爲，若old爲無窮大則返回

  2. 計算堆頂元素指向的值的出現次數，若大於等於閾值則添加到候選集中

  3. 把堆頂元素指針向前移動一格(即指向對應的倒排索引的下一項)，若下一項仍等於原來指向的值則繼續移動

  4. 上述操作後堆頂指針指向的值變大了，對它進行下濾操作

  5. 若新的堆頂指向的值等於則跳轉到步驟3

  6. 從堆中彈出個元素，使用二分檢索把這些倒排索引指針移動至大於當前堆頂指向的值，再重新插入堆中

DivideSkip

結合了MergeSkip和MergeOut。

  1. 使用啓發函數把倒排索引劃分爲長索引和短索引兩類，長索引有個，其中爲索引個數

  2. 對短索引採用MergeSkip算法，對於短索引中所有出現次數不少於的元素，在所有長索引中二分檢索

  3. 將出現次數不少於的元素添加到候選集中

  4. 把堆頂元素指針向前移動一格(即指向對應的倒排索引的下一項)，若下一項仍等於原來指向的值則繼續移動

  5. 上述操作後堆頂指針指向的值變大了，對它進行下濾操作

  6. 若新的堆頂指向的值等於則跳轉到步驟4

  7. 從堆中彈出個元素，使用二分檢索把這些倒排索引指針移動至大於當前堆頂指向的值，再重新插入堆中

其他

Tournament類使用了curiously recurring template pattern。

Similarity join

任務

實現similarity join，近似串有兩種度量方式：Levenshtein edit distance和Jaccard index。需要實現SimJoiner類的joinED、joinJaccard兩個方法。

BruteForce

枚舉集合的所有字符串，和集合的所有字符串一一進行Levenshtein edit distance或Jaccard index的計算，若滿足閾值條件則添加到存放結果的向量，實現複雜度爲，其中爲串的最大長度。

DivideSkip

執行次similarity search。 採用filter-and-verification framework，代碼中實現了索引、Filter和Verification三個部分。

索引

索引的數據結構是若干倒排索引，另外有一個hash table爲Q-gram到倒排索引的映射。

執行createIndex構建索引時， 對於每個輸入的字串，使用類似Rabin-Karp string search算法的方式，獲取當前長爲的窗口中的Q-gram，計算出散列值，找到對應的倒排索引，並在該索引末端加入當前行號。如果輸入字串有重複的Q-gram，那麼當前行號可能會在倒排索引中插入多次。然後窗口向右移動一格，把之前的散列值通過rolling hash計算出下一時刻的值。

輸入文件讀入完畢後，對於hash table中的每個倒排索引(必然是非空的)，在末端加入作爲哨兵元素的無窮大。

Filter

對於一個查詢，使用類似構建索引時的Rabin-Karp string search algorithm，對於每個長爲的窗口中的Q-gram，找到對應的倒排索引，把指向首元素的指針放入列表中。設查詢字串長度位，那麼中將會有個指針(可能重複)。

建立binary heap

列表的元素是指向倒排索引的指針，以指針指向的值爲關鍵字使用Floyd’s algorithm 在時間內建立binary heap 。

Tournament sort進行N-way merge

  1. 堆頂指針指向的值爲，若old爲無窮大則返回

  2. 計算堆頂元素指向的值的出現次數，若大於等於閾值則添加到候選集中

  3. 把堆頂元素指針向前移動一格(即指向對應的倒排索引的下一項)，若下一項仍等於原來指向的值則繼續移動

  4. 上述操作後堆頂指針指向的值變大了，對它進行下濾操作

  5. 若新的堆頂指向的值等於則跳轉到步驟3

之後對候選集的每個元素進行檢驗，是否滿足Jaccard index或Levenshtein編輯距離的閾值要求， 輸出篩選後的。

  1. 使用啓發函數把倒排索引劃分爲長索引和短索引兩類，長索引有個，其中爲索引個數

  2. 對短索引採用MergeSkip算法，對於短索引中所有出現次數不少於的元素，在所有長索引中二分檢索

  3. 將出現次數不少於的元素添加到候選集中

  4. 把堆頂元素指針向前移動一格(即指向對應的倒排索引的下一項)，若下一項仍等於原來指向的值則繼續移動

  5. 上述操作後堆頂指針指向的值變大了，對它進行下濾操作

  6. 若新的堆頂指向的值等於則跳轉到步驟4

  7. 從堆中彈出個元素，使用二分檢索把這些倒排索引指針移動至大於當前堆頂指向的值，再重新插入堆中

Verification

Levenshtein edit distance

需要對每個候選字串和查詢字串計算編輯距離。

兩個字符串的Levenshtein edit distance可以使用的Needleman–Wunsch algorithm計算。

注意到代碼中使用到編輯距離的地方都有閾值限制，如果編輯距離超過閾值，那麼它的實際值無關緊要。因此我們可以只計算動態規劃矩陣中對角線帶狀區域的狀態。

另外當其中某個字符串的長度小於等於128時，還可以採用bit vector的算法@edit03加速到。

兩個字符串的Levenshtein edit distance的下界是字符集所有字符出現頻數差的絕對值的和的一半，當該下界小於等於閾值時再進行實際計算。可以用_mm_sad_epu8來估算頻數差的絕對值的和。當某個字符頻數差大於等於256時會低估實際值，但對結果沒有影響。

Jaccard index

採用scan count的方式。 先用rolling hash計算查詢串所有Q-gram的標號，在計數容器中增加一。然後對於候選串的所有Q-gram，若計數容器中的值大於零則減去零並加到答案中。再便利候選串的所有Q-gram，把減去的值再加回來。

ppjoin@ppjoin

之前一個疑惑是沒理解similarity join和執行若干次similarity search有什麼區別。 原來是similarity search構建的索引能支持閾值不同的查詢，而similarity join直接指定了固定閾值， 因此構建的索引可以利用這個性質。

Prefix filtering

按照一個全序排序entity包含的gram，那麼若兩個串的overlap滿足：，則的前個q-gram必然與的前個gram有交集。

Jaccard index轉化爲overlap

由可得。

另由$ J(x,y) t 得|x| t |y|$

如果需要能所探尋到所有overlap超過的的串，取前綴長度爲即可。

論文中沒有提及某gram被同一個entity包含多次的情況。這時的前綴和的前綴的交集大小似乎不能有效地精確計算出來。

ppjoin

對於查詢串，計算，探測前個gram的倒排索引後得到一些候選entity，並且知道每個候選entity 的前個gram和前個gram的交集大小，如果加上後不到下界，則可以剔除。

需要一種類似數組的數據結構支持三種操作：清零、訪問某一項、列出上次清零以來所有訪問過的項。可以用三個數組和一個計數器實現。

Positional filtering

根據overlap計算hamming distance上界後根據和的某幾個對應的相等字符估算hamming distance下界，判斷是否可行。

當gram有重複時比較麻煩，SuffixFilterWeighted中不能直接用mid作爲的樞軸，需要取 中第一個取值和mid相同的字符。

對於可能重複的gram，另一種處理方式是讓各gram取不同的值。

Approximate entity extraction

任務

實現近似抽取，近似串有兩種度量方式：Levenshtein edit distance和Jaccard index。 需要實現AEE類的createIndex、aeeED、aeeJaccard三個方法。

Faerie algorithm

實現採用@faerie中提到的Faerie algorithm。

索引

讀入描述entity的文件採用mmap：

1
2
3
struct stat s;
int fd = open(filename, O_RDONLY); fstat(fd, &s);
mmap(0, s.st_size, PROT_READ, MAP_PRIVATE | MAP_POPULATE, fd, 0);

其中的MAP_POPULATE是爲了讓產生read-ahead的效果，加速文件讀入。

索引的數據結構包含：

  • entity向量e

  • 把Q-gram映射爲entity編號的若干倒排索引s2gid。

  • 若干倒排索引gid2e，爲每個entity中出現的Q-gram保存包含該Q-gram的entity向量。

對於每個輸入的字串，使用類似Rabin-Karp string search算法的方式，獲取當前長爲的窗口中的Q-gram，計算出散列值，找到對應的倒排索引，並在該索引末端加入當前行號。如果輸入字串有重複的Q-gram，那麼當前行號可能會在倒排索引中插入多次。然後窗口向右移動一格，把之前的散列值通過rolling hash計算出下一時刻的值。

s2gid的每個倒排索引末尾添加哨兵元素INT_MAX。

近似抽取

Levenshtein edit distance和Jaccard index均可用Faerie算法處理。對於每個文檔執行一次single-heap based algorithm。

建立binary heap

首先把長度爲的doc劃分爲的Q-gram，經s2gid映射後得到個指向倒排索引的指針。以指針指向的值(entity編號)爲第一關鍵字，位置爲第二關鍵字使用Floyd’s algorithm在時間內建立binary heap L。

Tournament sort進行N-way merge得到候選子串

令表示entity 的長度(和論文中定義不同)。

如果是Levenshtein edit distance查詢，則設置， ，； 如果是Jaccard index查詢，則設置， ，。

  1. 記堆頂元素爲eeid，彈出所有等於eeid的元素得到@faerie中的。

  2. 由於位置爲第二關鍵字，得到的以及有序了。

  3. 使用尺取法尋找包含中至少個元素，且包含的Q-gram數在區間內的所有窗口。

  4. 每個窗口可以產生若干候選子串。

代碼使用了batch-count pruning，使用尺取法時可以用@faerie中提到的二分檢索方法，一次把指針移動若干步。

Verification

之後對每個候選子串進行檢驗，是否滿足Jaccard index或Levenshtein編輯距離的閾值要求。

Levenshtein edit distance

兩個字符串的Levenshtein edit distance可以使用的Needleman–Wunsch algorithm計算。

注意到代碼中使用到編輯距離的地方都有閾值的限制，如果編輯距離超過閾值，那麼它的實際值無關緊要。因此我們可以只計算動態規劃矩陣中對角線帶狀區域的狀態。

另外當其中某個字符串的長度小於等於128時，可以使用內置類型__int128採用bit vector的算法@edit03加速到。

兩個字符串的Levenshtein edit distance的下界是字符集所有字符出現頻數差的絕對值的和的一半，當該下界小於等於閾值時再進行實際計算。可以用_mm_sad_epu8來估算頻數差的絕對值的和。當某個字符頻數差大於等於256時會低估實際值，但對結果沒有影響。

Jaccard index

計算兩個串和的Jaccard index時使用公式。

採用scan count的方式計算。根據s2gid計算查詢串所有Q-gram的編號，在計數容器中增加一。然後對於候選串的所有Q-gram，若計數容器中的值大於零則減去零並加到答案中。再遍歷候選串的所有Q-gram，把減去的值再加回來。

Trie-based@taste

令Levenshtein編輯距離閾值爲，對於每個entity ，劃分爲個片段存入trie。

若文檔和某個相似，則文檔必然以的某個片段爲子串。檢索trie即可得到所有候選entity。

當探測到文檔的某子串對應的trie節點包含某個entity ，則就是一個候選entity，且可以知道 的某個已經出現在中了，包含的某個更長子串和的編輯距離是：

即需要把前面的部分和匹配，後面的部分和匹配，兩部分可以分開考慮。總的編輯距離就是兩部分匹配結果編輯距離的和。如果左側的，則右側的最大可以是。

可以用帶閾值限制的編輯距離算法計算。

多個串共同包含時複用計算結果

多個串共同包含時，它們的右側部分可能也有公共前綴，這部分串的編輯距離結果可以複用。

把trie節點中檢索到的entity按組織爲下層trie(原trie爲上層trie)。求出下層trie的最左葉節點和的編輯距離後，要切換到次左葉節點，它們的longest common prefix和的編輯距離動態規劃值可以複用。

構建下層trie比較耗空間，可以借鑑suffix array的思路，把索引到的entity的右側部分排序，先計算字典需最小和的編輯距離，再計算字典序次小的和的編輯距離，如此處理其他所有。

另外如果發現計算到時發現所有都超過了，那麼可以立刻停止計算。

生成結果

把匹配某個左側部分的和匹配對應右側部分的求cartesian product，如果兩部分編輯距離和小於，拼接兩部分以及可以得到一個結果子串。

文檔的某個子串和某個的公共部分可能較長，導致的多個片段都在trie中被檢索到。產生的結果可能會重複，另外編輯距離的計算各片段間也會有很大的重疊。我沒想到怎麼利用。

Aho-Corasick automaton

目前的方式是對於文檔的每個位置都對上層trie探測得到候選entity，可以Aho-Corasick automaton改進。 注意Aho-Corasick automaton和Aho-Corasick algorithm的區別，前者會把trie改造爲圖(一些網絡資料稱之爲trie圖)。探測的文檔子串的右邊界在不斷增加，左邊界要根據Aho-Corasick狀態的轉移選擇性變化。

1
2
3
4
5
6
7
8
9
10
11
12
13
TrieNode *p = trie_root, *q; for (int i, j = 0; j < m; ) {
  u8 c = doc[j++];
  i += p->dep+1-p->ch[c]->dep;
  p = p->ch[c];
  for (ii = i, q = p; ; ) {
    // 考慮文檔d[ii,j)和節點q表示的e_m的下層trie q->inferior
    if (p->pi) {
      ii += p->depth-p->pi->depth;
      p = p->pi;
    } else
      break;
  }
}

對於每個匹配的p都要沿着p->pi->pi->…鍊上溯到根。可以對於每個trie節點記錄其最長的表示一個的後綴(即pi的若干次冪)。這樣可以被多串匹配部分的複雜度從優化到，其中爲文檔長度，爲出現次數和，爲單個的長度。

演化

Faerie 7.263 Faerie+ED共用 4.197 Trie-based初版 2.4s 使用Aho-Corasick automaton後2.264s 利用公共前綴後 2.133s

實現空間數據庫的即敲即得式檢索系統

實驗要求

  • 實現空間數據庫的即敲即得式檢索系統

  • 給定100w個POI，以及一個查詢，找到所有的相關結果

  • 基於位置的檢索和即敲即得式檢索

運行方式

項目由兩部分組成，實現檢索算法的部分爲後端，由C++11編寫； Web展示部分由網頁前端和Ruby Sinatra寫的web服務器組成。

運行後端：

1
2
g++ -std=c++11 -O3 src/a.cc -ljsoncpp -o a
./a

將會讀取當前目錄下的zipcode.json並監聽TCP 1337端口。

運行web服務器：

1
ruby web/web.rb

將會監聽0.0.0.0:4567。

使用說明

瀏覽器打開，在輸入框中填寫字串，點擊地圖上某處作爲起點，就會用marker的方式顯示最近10個地點，且name 字段包含字串。

點擊marker或者代表候選地點的右側按鈕， 即可顯示起點到該地點的路徑。

項目實現

JSON輸入文件處理

輸入文件爲JSON格式的zipcode-address.json，後端程序使用C++庫JsonCpp進行JSON的解析和渲染。

位置檢索

根據實驗要求，location-aware instant search的方法直觀上是最適合的。但考慮到數據規模和prefix-region tree的描述，及想要實現任意子串而非單單前綴的查詢，我在項目中分別實現了位置檢索和地名檢索。

位置檢索屬於multidimensional spatial data structure的應用。考慮到我們需要處理的詢問：求出矩形區域內的地點和與給定點最近的k個地點，解決這類問題最常用的數據結構是R-tree家族。

R-tree

R-tree是派生於B+-tree的層次化數據結構，存儲d維點或矩形，一般的物體可以轉化爲最小包圍盒後用矩形的方式存儲。 R-tree除根以外的節點度限製爲，其中，葉節點存儲若干物體，以及這些物體的最小包圍盒，內部節點存儲其包含的所有節點的包圍盒的最小包圍盒。

R-tree的操作通常用自頂向下遍歷，根據查詢和包圍盒的相關性來剪枝。 R-tree的缺點是分解是數據相關的，很難進行集合論操作比如交集。

Bulk loading

很多應用數據是靜態的，或者修改不頻繁，即使是動態的也很有可能很多數據可以提前知道。這時一次插入一項會帶來較大的加載代價，空間利用也不充分，結構不夠好。此時進行根據輸入數據特點進行bulk loading即建立初始數據結構是比較好的選擇。

R-tree bulk loading的通用的算法是：

  1. 把矩形劃分爲個分組，每個分組爲一個葉節點。最後一個分組分配到的矩形可能不到個。

  2. 遞歸地把若干個節點合併爲一個上一層的大節點，直到根節點被創建。

一種比較好的啓發式合併算法是Sort-Tile-Recursive。

Priority R-tree

@prtree是一種R-tree變體，window query的時間複雜度爲，是第一個達到該最壞情況下漸進最優複雜度的R-tree變體。

PR tree的起源，其中Priority R-tree誕生年份應爲2004年

Priority R-tree算法實際上指的是R-tree的一種bulk loading算法。 Priority R-tree的構建爲若干次pseudo priority R-tree構建過程。

Pseudo priority R-tree的構建方式如下：

Extract B left-extreme points. Store them in a leaf-node.
Extract B bottom-extreme points. Store them in a leaf-node.
Extract B right-extreme points. Store them in a leaf-node.
Extract B top-extreme points. Store them in a leaf-node.
Partition the remaining n - 4B nodes into two halves based on our current tree depth, using the same scheme as found in the kd-tree data structure:
If ((depth % 4) == 0) partition by the x-coordinate (left-extreme).
If ((depth % 4) == 1) partition by the y-coordinate (bottom-extreme).
If ((depth % 4) == 2) partition by the x-coordinate in reverse (right-extreme).
If ((depth % 4) == 3) partition by the y-coordinate in reverse (top-extreme).
Recursivly apply this algorithm to create two sub-trees on the partitioned halves.
Stop when no points remain to be indexed (e.g. stop when n - 4B ≤ 0).

去除pseudo priority R-tree的內部節點，把葉節點看作物體繼續調用pseudo priority R-tree進行下一輪構建，得到的內部節點再進行構建，如此反覆直到葉節點數，之後創建一個根節點包含所有葉節點。

我的實現參考了一個Java版的priority R-tree實現：https://github.com/dshanley/prtree。

K-nearest neighbors

採用best-first search實現k-nearest neighbors問題，以距離的下界作爲估價函數。

地名檢索

C++後端實現了給出一個字串，輸出所有包含該字串的地點的功能。這個需求可以轉化爲string search問題。

Suffix array構建

Suffix array是解決string search問題的一個工具，它是一個字串所有後綴的排序。

線性時間的構建算法主要有Kärkkäinen-Sanders(@dc3)、Ko-Aluru(@ka)、KSP三種，其中KSP算法使用了類似suffix tree的構建方式， Kärkkäinen-Sanders算法時間複雜度的遞推式爲，通常認爲性能不如的Ko-Aluru。

項目中我實現了Ko-Aluru算法，並按照@yangzhe的註記，借鑑@nzc對LMS substring遞歸排序使用的方法，對原始的Ko-Aluru算法進行改動以簡化內存使用和提升性能。我的實現在字串和suffix array外僅使用兩個數組：計數排序使用的桶和一個表示L/S類型的數組，反映了Ko-Aluru算法能達到和@nzc同等的精簡內存佔用。

Ka-Aluru suffix array construction algorithm

規定爲哨兵字符，且小於字符集中任意一個字符。對於字串個每個後綴，根據和的大小關係得到後綴的類型，然後根據把所有後綴分爲兩類：

令字符集爲，再根據後綴首字母分類：

並結合以上兩種分類定義：

對於，中的後綴排在中後綴的前面，因爲如果兩個後綴和的第一個字符、不同，那麼和的大小關係可以直接確定。另外中的後綴排在中後綴的前面，因爲中後綴均小於，而中後綴均大於。

Suffix array即爲。

根據@ka的induced sorting，只要確定了的大小順序，那麼的順序也可以確定。同樣地，只要確定了的大小順序，那麼的順序也可以確定。根據抽屜原理或有一個，不妨設，只要求出中所有後綴的大小順序，那麼使用induced sorting即可得到的大小順序。再根據中的後綴排在中後綴的前面，即可得到所有後綴的大小順序。

下面考慮如何遞歸求出的大小順序。@ka使用了一個複雜的方法，根據-distance計算。借鑑@nzc對LMS substring遞歸排序使用的方法，我在實現中使用了一個簡單的方法。定義--substring爲夾在相鄰兩個-類型字符間的子串。定義一個--substring 小於另一個--substring 當且僅當字典序小於，其中兩種取值規定-小於+。

對於兩個長度不同的--substring 和，它們不會相等，且根據--substring的大小關係可以得到和的大小關係。如果兩--substring相等，找到在原串後的--substring ，兩者共用一個字符。再找到在原串後的--substring ， 和的大小關係即爲和的大小關係。如果這兩個子串也相同了，那麼可以繼續找緊接着的下一對--substring。

根據以上比較方式可以發現如果取出中所有--substring，並把這些--substring看作字符，就可以得到子問題遞歸調用算法解決。現在考慮如何確定所有--substring的大小關係，使得長度不同的可以區分大小，而長度相同的允許相等(所以才需要遞歸確定大小)。

先用桶排序求出所有-類型字符的大小，使用一次induced sorting根據-計算 +，這樣便得到了所有形如子串的大小。再用一次induced sorting根據+計算-，便得到了所有形如類型子串的大小，而這些串就是我們需要的--substring。

對--substring計算新字符集大小，若小於--substring數目則說明所有 --substring的順序已經確定，否則取出-字符遞歸計算suffix array。得到這些--substring的順序即的順序後使用induced sorting即可得到整個suffix array。

實現技巧

爲原串，爲類型數組，爲桶排序使用的桶。

整個實現分爲幾個階段，仍然設：

  1. 計算數組，需要使用

  2. 使用兩次induced sorting計算--substring的大小，需要使用

  3. 根據--substring構建新字串遞歸計算子suffix array

  4. 根據子suffix array計算部分的suffix array

  5. 使用induced sorting根據部分的suffix array得到整體suffix array

其中第2、3步需要特別使用了很多技巧節省空間佔用。

注意到，因此新字串和子suffix array的空間佔用和，可以讓它們共用 原始的suffix array的空間。這樣根據子suffix array計算部分的suffix array的過程變成了把suffix array擴張的過程，而擴張時需要根據新字串和的字符對應關係的映射進行，因爲映射的性質可以共用一個數組實現，擴張中suffix array儲存了三部分的內容：映射、子suffix array、部分的suffix array， 其中部分的suffix array漸漸變大，子suffix array漸漸變小。 求得部分的suffix array後，原地桶排序得到原始下標的。

遞歸也需要使用數組，因爲計算是線性的，可以讓遞歸時繼續使用該數組，遞歸函數返回時重新計算被覆蓋的部分。這樣可以省去數組在遞歸中不斷被創建的開銷。

多數文獻都在末尾添加哨兵元素以方便講解，但個人感覺實現中哨兵元素通常會導致更複雜的判斷，弊大於利。不使用哨兵元素只需要在三個地方注意，

  • 爲-，因爲把哨兵字符看作字典序最小。

  • 根據+-substring計算--substring的induced sorting過程提前把放入桶中。 否則因爲它是最後一個字符，無法被放入桶中，當該字符的桶包含兩個或更多元素時可能會導致它的位置被覆蓋而出錯。

  • 計算新字符集時，需要注意比較過程中到達邊界的情況。

使用suffix array檢索字串

把所有地點的名字拼接爲一個字串後檢索字串的問題就轉化爲找到所有包含該字串的位置。在suffix array中檢索所有長爲的可以使用二分檢索在時間內得到：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def search(P):
    l = 0; r = n
    while l < r:
        mid = (l+r) / 2
        if P > A[mid]:
            l = mid + 1
        else:
            r = mid
    s = l; r = n
    while l < r:
        mid = (l+r) / 2
        if P < A[mid]:
            r = mid
        else:
            l = mid + 1
    return (s, r)

String search可以用suffix tree的top-down traversal輕易實現。 @sa04提出了使用lcp表增強suffix array的功能，從而實現時間檢索。給suffix array擴充lcp表後suffix array即能實現suffix tree的top-down traversal功能。

childtab

-interval 定義爲：

其性質是後綴的LCP爲。

滿足的稱爲-interval 的-index。這些-index把劃分爲若乾子區間，每個子區間可能是單元素區間，或者是LCP更大的-interval()。

根據這些-interval的包含關係構建一棵以-interval爲節點的樹，就得到了沒有葉節點的suffix tree。

\begin{aligned}
  \text{up}[i] &=& \min{\{ q \in [0,i) | \text{lcp}[q] > \text{lcp}[i] \text{ and } \forall k\in [q+1,i): \text{lcp}[k]\geq \text{lcp}[q]\}} \\
  \text{down}[i] &=& \min{\{ q \in [i+1,n) | \text{lcp}[q] > \text{lcp}[i] \text{ and } \forall k\in [i+1,q): \text{lcp}[k] > \text{lcp}[q]\}} \\
  \text{next}[i] &=& \min{\{ q \in [i+1,n) | \text{lcp}[q] = \text{lcp}[i] \text{ and } \forall k\in [i+1,q): \text{lcp}[k] > \text{lcp}[i]\}} \\\end{aligned}

可以這樣計算：

last = -1
push(0)
for i = [1,n)
  while lcp[i] < lcp[top]
    last = pop
    if lcp[i] <= lcp[top] && lcp[st] != lcp[last]
      down[top] = last
  if last != -1
    up[i] = last
    last = -1
  push(i)
while 0 < lcp[top]
  last = pop
  if lcp[top] != lcp[last]
    down[top] = last
if last != -1
  up[n] = last

push(0)
for i = [1,n)
  while lcp[i] < lcp[top]
    pop
  if lcp[i] == lcp[top]
    next[top] = i
    pop
  push(i)

有些項沒有值，不妨設爲無效值。

用一個數組child表示

如果有效，則，推出和都無效。

對於一個可分割的-interval ，，令，則爲各個子區間的分割點。因此可以記錄在和數組中。

進一步，有多個區間終點相同，它們計算子區間要用到。令該值爲最大的區間的值，則其他較小區間的分割點都必須用左邊界的值計算，而這些較小區間都是其父區間的最後一個子區間，所以它們的左邊界的值都爲，剛好可以用來存儲。這樣，三個數組可以只用一個數組存儲。

其中、和可以這樣區分：

  • 表示：-1 < child[i] && child[i] <= i

  • 表示：child[i] > i && lcp[child[i]] > lcp[i]

  • 表示：child[i] > i && lcp[child[i]] == lcp[i]

比如要在suffix array中搜索needle，@sa04中的僞代碼沒有考慮越界，修正如下：

found = true
(l, h) = get_interval(0, n, s[0])
i = 1
while found && i < m
  if l < h-1
    j = min(get_lcp(l, h), m)
    found = a[sa[l]+i...sa[l]+j] == needle[i...j]
    i = j
    if i < m
      (l,h) = get_interval(l, h, s[i])
  else
    found = a[sa[l]+i...sa[l]+m] == needle[i...m]
    i = m
return found ? (l, h) : (-1, -1)

如果要輸出方案，那麼複雜度變爲，其中是出現的次數。

得到包含needle的區間後，根據rank得到原字符串中的位置，即可知道哪些地點包含該字串。

結果呈現

前端

前端使用Slim作爲HTML的模板引擎，Sass爲CSS預處理器，CoffeeScript爲JavaScript預處理器，使用Semantic-UI CSS框架。Model和view的綁定採用了Model View ViewModel設計模式的 knockout.js。

Web服務器

項目中實現了基於Ruby的Sinatra實現了一個web server：web/web.rb。

對於地圖點擊，前端將用ajax向web服務器提交請求，web/web.rb收到查詢請求後會使用TCP socket向後端的C++服務器發送請求， C++服務器進行位置檢索，web服務器得到應答後以JSON格式發送給前端，前端再進行處理。

自動補全的實現方式類似。前端的jquery-autocomplete發現輸入框內容改變後向web服務器提交ajax請求，web/web.rb收到查詢請求後使用TCP socket向後端的C++服務器發送請求，C++服務器使用suffix array進行地名檢索。

結果展示

搜索框的自動補全是用jquery-autocomplete發送ajax請求由後臺返回的
使用Google Directions API計算路線