ARTS-第14周

发表于

ARTS （第14周）

现在是真正明白了那句话，算法和数据结构是不可分离，二者是相辅相成的。

本周：

BM算法、KMP算法、堆排序。

Algorithm 算法

BM算法

BM算法全名Boyer-Moore字符串搜索算法，是一种非常高效的[字符串搜索算法]。它由Bob Boyer和J Strother Moore设计于1977年。

此算法首先对模式串进行预处理，构建各类字典，减少后期不必要的匹配，在匹配失败的时候根据不同的原则，进行大幅度的跳跃。减少匹配次数。

匹配原则分为好字符原则和坏字符原则，构建字典，匹配到了坏字符或者好字符，就可以根据这二种规则进行一个较长长度的跳跃。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
package pack;

import java.util.Random;

/**
 * BM算法
 * 
 * @author lfy
 */
public class BMSearch {

	////////////////////////////////////////
	// 这部分为测试部分，70行往下才是BM算法
	////////////////////////////////////////

	public static void main(String[] args) {
		// System.out.println(2<<15);
		int max = 10000;
		int err = 0;
		BMSearch bms = new BMSearch();
		String text = "01411254141351540514";
		String pattern = "35121";
		char[] t = text.toCharArray();
		char[] p = pattern.toCharArray();
		System.out.println(text + ":" + pattern + "-->" + bms.bm(t, p));
		System.out.println("========test=========");
		for (int i = 0; i < max; i++) {
			pattern = generateString(5);
			text = generateString(20);
			t = text.toCharArray();
			p = pattern.toCharArray();
			// 创建随机字符串
			// 用BM算法和string类的indexof得出的结果进行比对
			int bm = bms.bm(t, p);
			int io = text.indexOf(pattern);
			if (bm != io) {
				System.err.println(i + ":" + text + ":" + pattern + ":fail:-->" + bm + ":" + io);
				// System.exit(0);
				err++;
			} else {
				System.out.println(i + ":" + text + ":" + pattern + ":ok:-->" + bm + ":" + io);
			}
		}
		System.out.println("err:" + err);
	}

	// "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
	private static final String CHARS = "012345";//// 随机字符串池

	/**
	 * 随机字符串
	 * 
	 * @author lfy
	 * @param length
	 * @return
	 */
	public static String generateString(int length) {
		StringBuffer sb = new StringBuffer();
		Random random = new Random();
		for (int i = 0; i < length; i++) {
			sb.append(CHARS.charAt(random.nextInt(CHARS.length())));
		}
		return sb.toString();
	}

	////////////////////////////////////////
	// 上面为测试用例部分，下面才是BM算法本身
	////////////////////////////////////////

	// private static final int MAXSIZE = 65536;// 所支持的最大ASCII码 0~MAXSIZE
	private static final int MAXSIZE = 256;// 所支持的最大ASCII码 0~MAXSIZE

	/**
	 * bm算法
	 * 
	 * @author lfy
	 * @param a
	 * @param b
	 * @return
	 */
	public int bm(char[] a, char[] b) {
		int n = a.length;
		int m = b.length;
		int[] bc = buildBc(b, m);// 坏字符字典
		int pos = 0;// 偏移量
		boolean[] prefix = new boolean[b.length];// 好前缀字典
		int[] suffix = new int[b.length];// 好字符字典
		buildGc(b, m, suffix, prefix);// 号支付构建
		while (pos <= n - m) {// 偏移量未到底的时候
			int idx = m - 1;// 当前模式串的最后坐标
			for (; idx >= 0; idx--) {
				// 模式串和主串的末尾部分相不匹配的时候
				if (b[idx] != a[idx + pos]) {
					break;
				}
			}
			if (idx < 0) {// 匹配
				return pos;
			}

			char bad = a[pos + idx];// 坏字符
			int badIndex = bad;// 坏字符字典索引
			// 查找坏字符所在的最后一个位置
			// 比如:模式串是 abac, 正在匹配的idx是最后一个,即idx = 3
			// 如果是坏字符是并且是a ,那么坏字符的最后index就是2
			// 那么就会进行偏移 -> idx - 坏字符indx
			int badIdx = bc[badIndex];
			// 坏字符偏移量
			int badPos = idx - badIdx;
			// 坏字符偏移存在负数的情况 如：
			// 01411254141351540514
			// 35121 其中1字符，在bc索引为49，值为4
			// 第一次进行匹配的时候 坏字符为1 主串的第四个字符（索引3）
			// 在这里badPos = idx - badIdx ==> 3-4 ==> -1;
			// 所以会得出-1的情况
			// 但是这种情况不用担心，
			// 因为有好字典
			// 因为出现坏字符偏移量为-1的时候 ,必定有好字符,而好字符必定不会返回小于0的值
			// 所以最终一定会有偏移
			int goodPos = 0;
			if (idx < m - 1) {// 有好字符
				goodPos = getGoodPos(idx, m, suffix, prefix);
			}
			// 得出更大的偏移量进行偏移
			int max = Math.max(badPos, goodPos);
			pos = pos + max;
		}

		return -1;
	}

	/**
	 * 获得好字符的偏移量
	 * 
	 * @author lfy
	 * @param j
	 * @param m
	 * @param suffix
	 * @param prefix
	 * @return
	 */
	private int getGoodPos(int j, int m, int[] suffix, boolean[] prefix) {
		int l = m - 1 - j;// 好字符长度
		if (suffix[l] != -1) {// 匹配到的时候
			// 如 好字符长度为2 总长度为5 应该偏移长度为 3
			// 因为suffix保存的是下标 所以 应该计算长度时候应该加1
			int len = j - suffix[l] + 1;
			return len;
		}
		// 后缀无法匹配则匹配前缀
		for (int i = l; i > 0; i--) {
			// 前缀长度会进行递减 直到匹配为止
			// 如好字符长度为2，总长度5 也是正确的前缀
			// 即i=2: 5+1-2 = 4
			if (prefix[i]) {
				return j - suffix[l] + 1;

			}
		}
		// 完全不匹配 直接跳跃整个字符长度
		return m;
	}

	/**
	 * 构建坏字典
	 * 
	 * @author lfy
	 * @param a
	 * @param l
	 * @return
	 */
	private int[] buildBc(char[] a, int l) {
		int[] bc = new int[MAXSIZE];// ASCII码和坐标对应的字典
		// 重置为-1
		for (int i = 0; i < MAXSIZE; i++) {
			bc[i] = -1;

		}
		// 设置坐标
		for (int i = 0; i < l; i++) {
			int ac = a[i];// ASCII码
			bc[ac] = i;
		}
		return bc;
	}

	/**
	 * 构建好字典
	 * 
	 * @author lfy
	 * @param b
	 * @param m
	 * @param suffix
	 * @param prefix
	 */
	private void buildGc(char[] b, int m, int[] suffix, boolean[] prefix) {
		// a b c a b m=5
		// 0 1 2 3 4 ==
		// [-1, 1, 0, -1, -1]
		// [false, false, true, false, false]

		// 初始化
		for (int i = 0; i < m; i++) {
			suffix[i] = -1;
			prefix[i] = false;
		}
		for (int i = 0; i < m; i++) {
			int p = i;// 前坐标
			int s = m - 1;// 后坐标
			while (p >= 0 && s > p && b[p] == b[s]) {
				// m为总长度 s是当前后坐标
				// m-s就为后缀长度
				// 例如 总长度 5 最大坐标为4 当前后座标为3 那么就是说 成功匹配了 坐标3开始的字符 即为2个
				suffix[m - s] = p;
				s--;
				p--;
			}
			if (p == -1) {
				// m为总长度 s是当前后坐标
				// m-s就为后缀长度
				// 例如 总长度 5 最大坐标为4 当前后座标为3 那么就是说 成功匹配了 坐标3开始的字符 即为2个
				// 之所以要多减一 是因为 在上一个循环里 有s-- 所以这里数值要补上
				// 上面是减 这里也是减 是因为计算的是后缀长度 而后缀长度的计算为 总长度-坐标 所以这里应该额外多减
				prefix[m - 1 - s] = true;
			}
		}

	}

}

KMP搜索算法

KMP算法是由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此取名KMP。

KMP算法和BM算法类似，也是发现无法匹配的时候进行大幅度的跳跃。

具体实现就是实现一个next()函数（有的地方称之为失效函数），函数本身包含了模式串的局部匹配信息。

匹配失败就根据失效函数进行跳跃。

代码如下：

在后面我还写了一个变种写法，大体思路不变，仅仅是坐标有所改变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
package pack;

import java.util.Random;

/**
 * @description
 * 
 * @author lfy
 */
public class KMPSearch {
	///////////////////
	// kmp算法测试 算法部分70行开始
	////////////////////
	public static void main(String[] args) {
		int max = 100000;
		int err = 0;
		//KMPSearch kmps = new KMPSearch();
		String text = "abaababsdzcxasdzxaabababcabasdzsdzz";
		String pattern = "sdzz";
		char[] t = text.toCharArray();
		char[] p = pattern.toCharArray();
		System.out.println(text + ":" + pattern + "-->" + kmp(t, p));
		System.out.println(text + ":" + pattern + "-->" + kmp2(t, p));
		System.out.println("========test=========");
		for (int i = 0; i < max; i++) {
			pattern = generateString(2);
			text = generateString(20);
			t = text.toCharArray();
			p = pattern.toCharArray();
			// 创建随机字符串
			// 用BM算法和string类的indexof得出的结果进行比对
			int bm = kmp(t, p);
			int bm2 = kmp2(t, p);
			int io = text.indexOf(pattern);
			if (bm != io || bm2 != io) {
				System.err.println("========================================");
				System.err.println(i + ":" + text + ":" + pattern + ":fail:-->" + bm + ":" + bm2 + ":" + io);
				System.err.println("========================================");
				// System.exit(0);
				err++;
			} else {// 这里bm == bm2 == io
				System.out.println(i + ":" + text + ":" + pattern + ":ok:-->" + bm + ":" + io);
			}
		}
		System.out.println("err:" + err);
	}

	// "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
	private static final String CHARS = "012345";//// 随机字符串池

	/**
	 * 随机字符串
	 * 
	 * @author lfy
	 * @param length
	 * @return
	 */
	public static String generateString(int length) {
		StringBuffer sb = new StringBuffer();
		Random random = new Random();
		for (int i = 0; i < length; i++) {
			sb.append(CHARS.charAt(random.nextInt(CHARS.length())));
		}
		return sb.toString();
	}

	///////////////////////
	// kmp查找
	//////////////////////
	/**
	 * kmp查找
	 * 
	 * @author lfy
	 * @param a
	 * @param b
	 * @return
	 */
	public static int kmp(char[] a, char[] b) {
		int n = a.length;
		int m = b.length;
		int[] next = getNexts(b, m);
		int j = 0;
		for (int i = 0; i < n; i++) {
			// 不匹配的时候 就去next数组里找
			while (j > 0 && a[i] != b[j]) {
				// 去next数组里找前一个字符所在的下标 进行匹配
				// 进行+1 是因为next数组里的 位置的转换
				j = next[j - 1] + 1;
			}
			// 当前字符匹配
			if (a[i] == b[j]) {
				j++;
			}
			// 完全匹配
			if (j == m) {
				// 当前坐标减模式串最大长度 即为首个字符出现的位置
				// 坐标从0开始 所以补个1
				return i - m + 1;

			}
		}

		return -1;// 不匹配
	}

	/**
	 * 获取失效函数
	 * 
	 * @author lfy
	 * @param b
	 * @param m
	 * @return
	 */
	private static int[] getNexts(char[] b, int m) {
		int[] n = new int[m];
		n[0] = -1;// 下标0 直接赋值 不需要计算
		int k = -1;// 下标 
		for (int i = 1; i < m; i++) {
			// 不匹配
			while (k > -1 && b[k + 1] != b[i]) {
				// 不匹配的时候 k取数组前一个最长前缀的下标
				// 再继续用k+1下标进行继续匹配
				// 直到匹配或者 k=-1的时候跳出
				// k=-1的时候就代表着没有任何数值匹配
				// 如： aaab 进行匹配
				// 首次计算的时候，是用下标0和下标1进行匹配 能成功匹配 所以不进入循环 ，k值累加
				// 所以不进入循环 ，k值累加 ，这时候n = [-1,0, 尚未计算,尚未计算 ]
				// 第二次的时候 是 i = 2, k = 0
				// 即用下标2和下标1进行匹配,能匹配，那么k的值就会进行累加
				// 所以不进入循环 ，k值累加 ，因此n = [-1,0, 1,尚未计算 ]
				// 第三次进行匹配的时候 i = 3, k = 1
				// 无法匹配 所以 k值会重新计算 所以k = n[k] = n[1] = 0;
				// 这时候就会用下标3 和下标0进行匹配 发现依旧无法匹配
				// 重新计算k值，得出k值为-1；因此跳出循环 进行下面的判断
				// 因此最后得出n = [-1,0, 1,-1 ]
				k = n[k];
			}
			// 匹配
			if (b[k + 1] == b[i]) {
				k++;// 相同 则i和k都累加
			}

			n[i] = k;

		}

		return n;
	}

	/**
	 * 获取失效函数 坐标值一样 方法返回值和getNexts()一样
	 * 
	 * @author lfy
	 * @param b
	 * @param m
	 * @return
	 */
	private static int[] ___getNexts(char[] b, int m) {
		int[] n = new int[m];
		n[0] = -1;// 下标0 直接赋值 这种情况不需要计算
		int k = 0;
		for (int i = 1; i < m; i++) {
			// 不匹配
			while (k > 0 && b[k] != b[i]) {
				k = n[k - 1];
			}
			// 匹配
			if (b[k] == b[i]) {
				k++;// 相同 则i和k都累加
			}

			n[i] = k - 1;

		}

		return n;
	}

	////////////////////////////
	// 思路一致 和极客时间不一样的变种写法
	////////////////////////////
	/**
	 * kmp查找
	 * 
	 * @author lfy
	 * @param a
	 * @param b
	 * @return
	 */
	public static int kmp2(char[] a, char[] b) {
		int n = a.length;
		int m = b.length;
		int[] next = getNexts2(b, m);
		int j = 0;
		for (int i = 0; i < n; i++) {
			// 不匹配的时候 就去next数组里找
			while (j > 0 && a[i] != b[j]) {
				// 去next数组里找前一个字符所在的下标 进行匹配
				// 进行是因为next数组里的 位置的转换
				j = next[j - 1];
			}
			// 当前字符匹配
			if (a[i] == b[j]) {
				j++;
			}
			// 完全匹配
			if (j == m) {
				// 当前坐标减模式串最大长度 即为首个字符出现的位置
				// 坐标从0开始 所以补个1
				return i - m + 1;

			}
		}

		return -1;// 不匹配
	}

	private static int[] getNexts2(char[] b, int m) {
		int[] n = new int[m];
		int k = 0;
		for (int i = 1; i < m; i++) {
			// 不匹配
			while (k > 1 && b[k] != b[i]) {
				k = n[k - 1];
			}
			// 匹配
			if (b[k + 1] == b[i]) {
				k++;// 相同 则i和k都累加
			}
			n[i] = k;
		}
		return n;
	}

}

堆排序

堆排序就是利用堆结构，首先建堆，再删除堆顶，以此进行排序的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
package pack;

import java.util.Arrays;

import jdk8test.Sort;

/**
 * @description
 * 
 * @author lfy
 */
public class HeapSort {
	public static void main(String[] args) {
		int[] arr = { 100, 1, 5, 10, 55, 2, 3, 6 };
		heapSortAll(arr, arr.length - 1);
		System.out.println("HeapSort:" + Arrays.toString(arr));
		System.out.println("======test========");
		int max = 10;
		int err = 0;//错误次数
		int repeat = 100000;
		Sort sort = new Sort();
		//验证
		for (int q = 0; q < repeat; q++) {
			int[] a = new int[max];
			int[] b = new int[max];
			for (int i = 0; i < max; i++) {
				int r = (int) (Math.random() *888 )+100;
				a[i] = r;
				b[i] = r;
			}
			System.out.println(q + "=========\nbefore:" + Arrays.toString(a));
			sort.bucketSort3_1(b,3);
			System.out.println("ElseSort:" + Arrays.toString(b));
			heapSortAll(a, a.length);
			System.out.println("HeapSort:" + Arrays.toString(a));
			for (int i = 0; i < max; i++) {
				if (a[i] != b[i]) {
					System.out.println("err1");
					err++;
					//System.exit(0);//出现错误结束
					break;
				} else if (i > 0 && b[i] < b[i - 1]) {
					System.out.println("err2");
					err++;
					//System.exit(0);//出现错误结束
					break;
				}
			}

		}

		System.out.println("err:" + err);
	}

	// n 表示数据的个数，数组 a 中的数据从下标 1 到 n 的位置。
	public static void heapSortAll(int[] a, int n) {
		// 把最小值放到数组最前面
		// 因为堆排序是不排首个值的
		int min = 0;
		for (int i = 0; i < n; i++) {
			if (a[min] > a[i]) {
				min = i;
			}
		}
		swap(a, min, 0);
		for (int i = n / 2; i > 0; i--) {
			heapify(a, n, i);// 建堆 (大顶堆
		}
		int k = n;
		while (k > 1) {
			swap(a, 1, --k);// 交换 把最大的放到最末尾
			heapify(a, k, 1);// 重新建堆 (从根节点开始
		}
	}

	// n 表示数据的个数，数组 a 中的数据从下标 1 到 n 的位置。
	public static void heapSort(int[] a, int n) {
		for (int i = n / 2; i > 0; i--) {
			heapify(a, n, i);// 建堆 (大顶堆
		}
		int k = n;
		while (k > 1) {
			swap(a, 1, k);// 交换 把最大的放到最末尾
			heapify(a, --k, 1);// 重新建堆 (从根节点开始
		}
	}

	/**
	 * 堆排序-建堆
	 * 
	 * @author lfy
	 * @param a
	 * @param n
	 * @param i
	 */
	private static void heapify(int[] a, int n, int i) {
		int max = i;
		// 判断子节点和当前节点的大小 用最大的数值 替代当前节点
		if (2 * i < n && a[2 * i] > a[i]) {
			max = 2 * i;
		}
		if (2 * i + 1 < n && a[2 * i + 1] > a[max]) {
			max = 2 * i + 1;
		}
		if (max != i) {
			swap(a, i, max);
			// 将替换后的子节点递归（即原本的i节点）
			heapify(a, n, max);
		}

	}

	private static void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

}

Review 英文文章

https://lucene.apache.org/solr/news.html

solr的各个版本信息。

Tip 技巧

极客时间的专栏《数据结构与算法之美》

本周学习了该专栏中的33-34篇

其中33篇是再次重新理解的。之前看完33篇以为理解了BM算法，在后面写代码的时候，发现很多地方尚未理解，本周就重新学习了一遍。

这两篇的核心内容就是BM算法和KMP算法。

BM算法：

分此算法首先对模式串进行预处理，构建各类字典，减少后期不必要的匹配，在匹配失败的时候根据不同的原则，进行大幅度的跳跃。减少匹配次数。

匹配原则分为好字符原则和坏字符原则，构建字典，匹配到了坏字符或者好字符，就可以根据这二种规则进行一个较长长度的跳跃。

KMP算法：

KMP算法和BM算法类似，也是发现无法匹配的时候进行大幅度的跳跃。

具体实现就是实现一个next()函数（有的地方称之为失效函数），函数本身包含了模式串的局部匹配信息。

匹配失败就根据失效函数进行跳跃。

Share 分享

https://www.zhihu.com/question/21923021

如何更好的理解和掌握 KMP 算法? （看其中逍遥行的回答）

https://www.zhihu.com/question/33776070/answer/722984174

算法数据结构中有哪些奇技淫巧