Java---正向、逆向和双向最大匹配算法_3.(正向与逆向最长匹配算法)分别实现正向和逆向最长匹配算法的代码过程,并加载字

完成正向、逆向和双向最大匹配算法

import java.io.*;
import java.util.*;

/**
 * 正向最大匹配 
 * 逆向最大匹配 
 * 双向最大匹配
 */
public class TwoMaxMatch {
	private static final int MAX_LENGTH = 5;
	public static void main(String[] args) {
		//加载字典
		getDictionary();
		
		String string = "北京大学生前来应聘算法工程师岗位";
		System.out.println("正向最大匹配结果：" + leftMax(string));
		System.out.println("逆向最大匹配结果：" + rightMax(string));
		System.out.println("双向最大匹配结果：" + twoMax(string));
	}
	/**
	 * 正向最大匹配
	 */
	public static List<String> leftMax(String str) {

		List<String> results = new ArrayList<String>();
		String input = str;

		while (input.length() > 0) {

			String subSeq;
			// 每次取小于或者等于最大字典长度的子串进行匹配
			if (input.length() < MAX_LENGTH)
				subSeq = input;
			else
				subSeq = input.substring(0, MAX_LENGTH);

			while (subSeq.length() > 0) {
				// 如果字典中含有该子串或者子串颗粒度为1，子串匹配成功
				if (dictionary.contains(subSeq) || subSeq.length() == 1) {
					results.add(subSeq);
					// 输入中从前向后去掉已经匹配的子串
					input = input.substring(subSeq.length());
					break; // 退出循环，进行下一次匹配
				} else {
					// 去掉匹配字段最后面的一个字
					subSeq = subSeq.substring(0, subSeq.length() - 1);
				}
			}

		}
		return results;
	}

	/**
	 * 逆向最大匹配
	 */
	public static List<String> rightMax(String str) {
		// 采用堆栈处理结果，后进先出
		Stack<String> store = new Stack<String>();
		List<String> results = new ArrayList<String>();
		String input = str;

		while (input.length() > 0) {

			String subSeq;
			// 每次取小于或者等于最大字典长度的子串进行匹配
			if (input.length() < MAX_LENGTH)
				subSeq = input;
			else
				subSeq = input.substring(input.length() - MAX_LENGTH);

			while (subSeq.length() > 0) {
				// 如果字典中含有该子串或者子串颗粒度为1，子串匹配成功
				if (dictionary.contains(subSeq) || subSeq.length() == 1) {
					store.add(subSeq);
					// 输入中从后向前去掉已经匹配的子串
					input = input.substring(0, input.length() - subSeq.length());
					break;
				} else {
					// 去掉匹配字段最前面的一个字
					subSeq = subSeq.substring(1);
				}
			}
		}
		// 输出结果
		int size = store.size();
		for (int i = 0; i < size; i++) {
			results.add(store.pop());
		}

		return results;
	}

	/**
	 * 双向最大匹配
	 */
	public static List<String> twoMax(String str) {
		List<String> leftmax = leftMax(str);
		List<String> rightmax = rightMax(str);

		// 如果分词的数量结果不同，返回长度较小的
		if (leftmax.size() != rightmax.size()) {
			if (leftmax.size() > rightmax.size())
				return rightmax;
			else
				return leftmax;
		}
		// 如果分词的数量结果相同
		else {
			//计算各自的  单字数
			int leftSingle = 0, rightSingle = 0;
			boolean isEqual = true;
			for (int i = 0; i < rightmax.size(); i++) {
				if (!leftmax.get(i).equals(rightmax.get(i))) {
					isEqual = false;
				}
				//判断是否为 单字
				if (leftmax.get(i).length() == 1)
					leftSingle++;
				if (rightmax.get(i).length() == 1)
					rightSingle++;
			}
			// 如果正向、逆向匹配结果完全相等，返回任意结果
			if (isEqual) {
				return leftmax;
				// 否则，返回单字数少的匹配方式
			} else if (leftSingle > rightSingle)
				return rightmax;
			else
				return leftmax;
		}
	}
	/**
	 * 载入字典和自定义添加词
	 */
	private static Set<String> dictionary;

	// 初始化字典，采用 hashset 存储
	public static void getDictionary() {
		dictionary = new HashSet<String>();
		String dicpath = "XXXX/ChineseDic.txt";
		String line = null;
		BufferedReader br;
		try {
			// 按照 UTF-8 编码读入文件
			br = new BufferedReader(new InputStreamReader(new FileInputStream(dicpath), "UTF-8"));
			try {
				while (((line = br.readLine()) != null)) {
					// 按照空格切分，只读取第二部分
					String[] str = line.split("\\s+");
					line = str[1];
					dictionary.add(line);
				}
				br.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	// 自定义添加词汇
	public void addWord(String str) {
		dictionary.add(str);
	}
}
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

运行结果

正向最大匹配结果：[北京大学, 生前, 来, 应聘, 算法, 工程师, 岗位]
逆向最大匹配结果：[北京, 大学生, 前来, 应聘, 算法, 工程师, 岗位]
双向最大匹配结果：[北京, 大学生, 前来, 应聘, 算法, 工程师, 岗位]
1
2
3

完！