Java後綴數組之求sa數組的實例代碼

後綴數組的一些基本概念請自行百度,簡單來說後綴數組就是一個字符串所有後綴大小排序後的一個集合，然後我們根據後綴數組的一些性質就可以實現各種需求。

 public class MySuffixArrayTest { public char[] suffix;//原始字符串public int n;//字符串長度public int[] rank;// Suffix[i]在所有後綴中的排名public int[] sa;// 滿足Suffix[SA[1]] < Suffix[SA[2]] …… < Suffix[SA[Len]],即排名為i的後綴為Suffix[SA[i]] // (與Rank是互逆運算) public int[] height;// 表示Suffix[SA[i]]和Suffix[SA[i - 1]]的最長公共前綴，也就是排名相鄰的兩個後綴的最長公共前綴public int[] h;// 等於Height[Rank[i]]，也就是後綴Suffix[i]和它前一名的後綴的最長公共前綴public int[] ws;// 計數排序輔助數組public int[] y;// 第二關鍵字rank數組public int[] x;// rank的輔助數組｝

以下的講解都以"aabaaaab"這個字符串為例，先展示一下結果，請參考這個結果進行理解分析（這個結果圖我複制別人的，請各位默認下標減1，因為我的數組從下標0開始的）

suffix：原始字符串數組假設原始字符串是"aabaaaab" 那這個數組對應的值應該是{'a','a','b','a','a','a','a','b'}
n：字符串長度這裡n是8
rank: 後綴數組的名次數組相當於存的是第i個後綴對應的名次是多少比如rank[0]就是指"aabaaaab"這個後綴的名次rank[1]指"abaaaab"這個後綴的名次
sa: 這個是和rank數組互逆的一個數組存的是第x名的是哪個後綴還是舉例子來說明sa[0]指的是排名第一的後綴數組即為3 也就是"aaaab"這個數組他對應的rank[3]就是0。 sa[rank[i]]=i 這個式子請務必理解，理解了這個sa和rank的關係你應該也搞懂了
height: height[i]就是sa[i]後綴數組和sa[i-1]後綴數組的最大公共前綴的長度height[1]指的是排名第2和排名第1的最大公共前綴sa[1]與sa[0]即"aaab"與"aaaab"的最大公共前綴自然一眼看出height[1]=3
h: h[i]指的是第i個後綴與他前一名的最大公共前綴h[0]指的就是第一個後綴數組即"aabaaaab"與他前一名即"aab"的最大公共前綴也就是height[rank[0]]=height[3]=3 這個有點不好理解可以暫時不理解繼續往下看
ws: 沒什麼好說的，計數排序的輔助數組
y: 存的是第二關鍵字排序相當於第二關鍵字的sa數組
x: 你可以理解為rank數組的備份，他最開始是rank數組備份，之後記錄每次循環後的rank數組

首先來看下求sa數組的代碼，我會一段一段的說明代碼作用並在後面附上總代碼

rank = new int[n]; sa = new int[n]; ws = new int[255]; y = new int[n]; x = new int[n]; // 循環原字符串轉換int值放入rank數組for (int i = 0; i < n; i++) { rank[i] = (int) suffix[i]; }

上面這段代碼的作用就是初始化數組以及進行第一次計數排序，第一次循環是對rank數組賦初值，執行完後rank數組對應值為{97,97,98,97,97,97,97,98},大家應該看得出來rank數組的初值就是字母對應的ascii碼。

接下來的三段循環就是第一次計數排序了，不理解計數排序的請百度。我說下這三段循環運行的過程

for (int i = 0; i < n; i++) { ws[rank[i]]++; x[i] = rank[i]; }for (int i = 1; i < ws.length; i++) { ws[i] += ws[i - 1]; }

這兩段循環做的是對所有出現值計數，並備份rank數組至x數組，第一個循環運行完後ws[97]=6,ws[98]=2，第二個循環運行完後ws[97]=6,ws[98]=8

 for (int i = n - 1; i >= 0; i--) { sa[--ws[rank[i]]] = i; }

上面這段就是具體的計數排序求sa數組的代碼，大家第一次看的時候肯定是蒙的，這怎麼就求出了sa呢。我第一次也是蒙的，但請保持耐心，仔細理解這段代碼。還記得前面說的公式嗎sa[rank[i]]=i 舉個例子對於後綴"b"我們求他的sa 即sa[rank[7]]=sa[98]=7 顯然sa[98]不存在但我們將98出現的次數已經記錄在ws數組了那麼ws[98]應該就是"b"對應的名次了注意不要忘記計數減1 就變成了sa[--ws[rank[i]]] = i。至於為什麼要從後向前遍歷，這裡你需要仔細理解一下，否則後面根據第二關鍵字進行排序的方式你肯定會完全蒙蔽。如果有兩個rank值相同的你怎麼排序呢？肯定是先出現的在sa數組的前面，仔細思考這個循環以及ws數組值的變化，你會明白，for循環的順序實際上代表了rank值相同時的排列順序。從後向前遍歷代表了rank值相同時靠後的後綴排名也靠後。

以上只是第一次計數排序，相當於只比較每個後綴數組的首字母求出了一個sa,對應的結果如下圖

// 循環組合排序for (int j = 1, p = 0; j <= n; j = j << 1) { // 需要補位的先加入排序數組yp = 0; for (int i = n - j; i < n; i++) { y[p++] = i; } // 根據第一關鍵字sa排出第二關鍵字for (int i = 0; i < n; i++) { if (sa[i] >= j) { y[p++] = sa[i] - j; } } // 合併兩個關鍵字的排序for (int i = 0; i < ws.length; i++) { ws[i] = 0; } for (int i : x) { ws[i]++; } for (int i = 1; i < ws.length; i++) { ws[i] += ws[i - 1]; } for (int i = n - 1; i >= 0; i--) { sa[--ws[x[y[i]]]] = y[i]; y[i] = 0; } // 根據sa算出rank數組int xb[] = new int[n];// x數組備份for (int i = 0; i < n; i++) { xb[i] = x[i]; } int number = 1; x[sa[0]] = 1; for (int i = 1; i < n; i++) { if (xb[sa[i]] != xb[sa[i - 1]]) { x[sa[i]] = ++number; } else if (sa[i] + j >= n && sa[i - 1] + j >= n) { x[sa[i]] = number; } else if (sa[i] + j < n && sa[i - 1] + j >= n) { x[sa[i]] = ++number; } else if (xb[sa[i] + j] != xb[sa[i - 1] + j]) { x[sa[i]] = ++number; } else { x[sa[i]] = number; } if (number >= n) break; } }

這是求sa數組最難以理解的一段代碼，首先大家需要理解一下倍增算法的思路。第一次計數排序後我們是不是已經知道了所有後綴數組第一個首字母的排序，既然我們知道了第一個首字母的排序那是不是相當於我們也知道了他第二個字母的順序(注意排序和順序的區別，排序是我們知道他固定的排在第幾名，順序是我們只知道他出現的次序，但並不知道他具體排第幾名)，這是當然的,因為他們本來就是出自一個字符串，對於每個後綴他同時也可以作為他之前後綴的後綴。說起來繞口，舉個例子，比如對於"baaaab"他首字母的順序是不是對應"abaaaab"的第二關鍵字順序。我們有了第一關鍵字的排序和第二關鍵字的排序就能求出兩個關鍵字的組合排序，跟據組合排序的結果我們還是可以延用之前的想法，對於"baaaab"第一次組合排序後我們排出來他頭兩個字母"ba"的排序，那麼他同時他也可以作為"aabaaaab"的第二關鍵字的順序。整個排序的邏輯參考下圖

然後我們來分段的分析代碼

for (int i = n - j; i < n; i++) { y[p++] = i; } // 根據第一關鍵字sa排出第二關鍵字for (int i = 0; i < n; i++) { if (sa[i] >= j) { y[p++] = sa[i] - j; } }

以上代碼就是求第二關鍵字的sa也就是y數組，p初始值為0，第一段循環是將需要補位的後綴排在數組最前面。

第二個循環的邏輯你需要結合前面的邏輯圖進行理解了，我們對第一關鍵字的排序結果sa進行遍歷，if(sa[i] >=j )判斷該後綴能否作為其他後綴的第二關鍵字，以第一次循環j=1為例，當sa[i]=0時代表後綴數組"aabaaaab"，顯然它無法作為其他後綴的第二關鍵字。對於可以作為其他後綴第二關鍵字的，他sa的順序就是對應的第二關鍵字的順序，sa[i] - j 求出他作為第二關鍵字的後綴放在y數組下，並且p++。這裡你需要慢慢理解。

 // 合併兩個關鍵字的排序for (int i = 0; i < ws.length; i++) { ws[i] = 0; } for (int i : x) { ws[i]++; } for (int i = 1; i < ws.length; i++) { ws[i] += ws[i - 1]; } for (int i = n - 1; i >= 0; i--) { sa[--ws[x[y[i]]]] = y[i]; y[i] = 0; }

以上是根據第一關鍵字排序sa和第二關鍵字排序y求出其組合排序，這段代碼相當的晦澀難懂。我們可以先不理解代碼，先理解一個思路，對於兩個關鍵字排序，實際規則和兩個數字排序差不多，比如11和12比較大小，10位就是第一關鍵字，個位就是第二關鍵字，比較完10位我們求得11=12，再比較個位我們知道11<12，10位相同的話其個位的順序就是大小順序。我上面第一次計數排序時說過，計數排序for循環的順序實際上代表了rank值相同時的排列順序，那麼這裡我們怎麼一次計數排序就求出兩個關鍵字合併後的順序呢？我說下我的理解，一次計數排序實際上包含了兩次排序，一次是數值的排序，一次是出現次序的排序，其規則就相當於前面11和12比較的例子，數值的排序是10位，出現次序的排序是個位。到這裡我們就有思路了，數值的排序用第一關鍵字的排序，出現次序的排序用第二關鍵字的排序，這樣就能一次計數排序求得兩個關鍵字合併後的排序。上面的代碼就是這個思路的實現。 x數組就是第一關鍵字的rank數組，我們對他進行計數。

 for (int i = n - 1; i >= 0; i--) { sa[--ws[x[y[i]]]] = y[i]; y[i] = 0; }

這段循環就是上面所有思路的實現，我們對第二關鍵字數組y從後進行遍歷，對於y[i]我們求出他第一關鍵字的計數排名，這個計數排名就是y[i]的排名，最後計數減1。合併關鍵字的排序成功求出。

相信你如果理解了上面所有的代碼後肯定會拍案叫絕，我本人在一遍遍琢磨這段代碼時也是熱血澎湃，簡直拜服了。這就是算法的魅力吧。

有了sa數組我們就可以求rank數組，這並不難，也就不講解了。下面附上求sa的所有代碼。

 public static void main(String[] args) { String str = "aabaaaab"; MySuffixArrayTest arrayTest = new MySuffixArrayTest(str.toString()); arrayTest.initSa();// 求sa數組} public void initSa() { rank = new int[n]; sa = new int[n]; ws = new int[255]; y = new int[n]; x = new int[n]; // 循環原字符串轉換int值放入rank數組for (int i = 0; i < n; i++) { rank[i] = (int) suffix[i]; } // 第一次計數排序for (int i = 0; i < n; i++) { ws[rank[i]]++; x[i] = rank[i]; } for (int i = 1; i < ws.length; i++) { ws[i] += ws[i - 1]; } for (int i = n - 1; i >= 0; i--) { sa[--ws[rank[i]]] = i; } // 循環組合排序for (int j = 1, p = 0; j <= n; j = j << 1) { // 需要補位的先加入排序數組yp = 0; for (int i = n - j; i < n; i++) { y[p++] = i; } // 根據第一關鍵字sa排出第二關鍵字for (int i = 0; i < n; i++) { if (sa[i] >= j) { y[p++] = sa[i] - j; } } // 合併兩個關鍵字的排序for (int i = 0; i < ws.length; i++) { ws[i] = 0; } for (int i : x) { ws[i]++; } for (int i = 1; i < ws.length; i++) { ws[i] += ws[i - 1]; } for (int i = n - 1; i >= 0; i--) { sa[--ws[x[y[i]]]] = y[i]; y[i] = 0; } // 根據sa算出rank數組int xb[] = new int[n];// x數組備份for (int i = 0; i < n; i++) { xb[i] = x[i]; } int number = 1; x[sa[0]] = 1; for (int i = 1; i < n; i++) { if (xb[sa[i]] != xb[sa[i - 1]]) { x[sa[i]] = ++number; } else if (sa[i] + j >= n && sa[i - 1] + j >= n) { x[sa[i]] = number; } else if (sa[i] + j < n && sa[i - 1] + j >= n) { x[sa[i]] = ++number; } else if (xb[sa[i] + j] != xb[sa[i - 1] + j]) { x[sa[i]] = ++number; } else { x[sa[i]] = number; } if (number >= n) break; } } }

總結

以上所述是小編給大家介紹的Java後綴數組之求sa數組的實例代碼，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時回復大家的。在此也非常感謝大家對武林網網站的支持！