近来需要做一些从中文文本中提取关键字（关键字自定义）的操作，偶然间了解了AC自动机算法，而网上的算法大多是基于英文实现的，所以也只是适用于英文提取关键字，因此最近研究了一下中文AC自动机的实现，记录下自己的思路，以期与大家共勉。
关于AC自动机，网上也已经是有了许多非常详细的介绍，比较关键的两步就是trie树和fail指针的构建，在这里也不再赘述，不清楚的可以去https://bestsort.cn/2019/04/28/402/。下面综合代码讲解一下我个人的实现方法，我使用java语言实现。
首先呢，是自定义一些关键字，为了方便统一操作，我们将关键字存入以UTF-8编码的txt文本中，每一行存一个关键字。不同类型的关键字存入不同的txt文本中，这里主要是适应于我个人的需要，用于区分关键字的类型，方便以后当做某种类型的参数去处理。
第一步，我构建一种新的数据结构，对该数据结构，每一个数据都有关键字和类型两个属性。
public class TypeKey {
public String ikey;//关键字
public String itype;//类型
}第二步，我从不同的文本分别读出里面所有的关键字，并给同一文本里的关键字以相同的类型标记。
List<TypeKey> strings = new ArrayList<>();//储存关键字和类型的数组
String type1 = "time";//每一种type都对应着一种类型，同时对应一个txt文本
String type2 = "attr";
String type3 = "machine";
String type4 = "place";
String type5 = "order";
File timeKey = new File("D:\\dict\\time.txt");
File attrKey = new File("D:\\dict\\attr.txt");
File machineKey = new File("D:\\dict\\machine.txt");
File placeKey = new File("D:\\dict\\place.txt");
File orderKey = new File("D:\\dict\\order.txt");
String str = null;
BufferedReader brt = new BufferedReader(new InputStreamReader(new FileInputStream(timeKey), "UTF-8"));
while((str = brt.readLine())!=null){
String time = str;
TypeKey tk = new TypeKey();
tk.ikey = time;
tk.itype = type1;
strings.add(tk);
}
BufferedReader bra = new BufferedReader(new InputStreamReader(new FileInputStream(attrKey), "UTF-8"));
while((str = bra.readLine())!=null){
String attr = str;
TypeKey tk = new TypeKey();
tk.ikey = attr;
tk.itype = type2;
strings.add(tk);
}
BufferedReader brm = new BufferedReader(new InputStreamReader(new FileInputStream(machineKey), "UTF-8"));
while((str = brm.readLine())!=null){
String machine = str;
TypeKey tk = new TypeKey();
tk.ikey = machine;
tk.itype = type3;
strings.add(tk);
}
BufferedReader brp = new BufferedReader(new InputStreamReader(new FileInputStream(placeKey), "UTF-8"));
while((str = brp.readLine())!=null){
String place = str;
TypeKey tk = new TypeKey();
tk.ikey = place;
tk.itype = type4;
strings.add(tk);
}
BufferedReader bro = new BufferedReader(new InputStreamReader(new FileInputStream(orderKey), "UTF-8"));
while((str = bro.readLine())!=null){
String order = str;
TypeKey tk = new TypeKey();
tk.ikey = order;
tk.itype = type5;
strings.add(tk);
}这样，我成功把所有的关键字及其类型存入了strings数组里面，有了关键字之后，比较重要的一环就是利用这些关键字构造trie树了。trie树其实也就是一棵前缀树，在这里根据个人的需要，将trie树数据结构定义如下。
public class Trie {//构建前缀树的树形结构，并附带fail指针
List<Trie> child = new ArrayList<>();//孩子结点
private Trie fail;//fail指针
private char value;//该结点所代表的值
boolean isleaf = false;//代表该结点是否是叶结点,默认为非叶结点
public String itype;//存储该关键字的类型
public Trie(){
this.value = '0';
}
public Trie(char value){
this.value = value;
}
public void createChild(Trie newNode){//给当前结点创建孩子结点
Trie newChild = new Trie();
newChild = newNode;
child.add(newChild);
}
public char getValue() {
return value;
}
public void setValue(char value) {
this.value = value;
}
public Trie getFail() {
return fail;
}
public void setFail(Trie fail) {
this.fail = fail;
}
public boolean isIsleaf() {
return isleaf;
}
public void setIsleaf(boolean isleaf) {
this.isleaf = isleaf;
}
}
构建trie树。
//给定关键字，构造Trie树的树形结构
public void createTrie(List<TypeKey> dict, Trie root){//dict表示关键字的集合，root表示构造的Trie树
Trie curNode = new Trie();
curNode = root;
for(int i=0;i<dict.size();i++){
char[] chars = dict.get(i).ikey.toCharArray();//将单个字符串转化成字符数组
for(int j=0;j<chars.length;j++){
boolean pre = false;//用于判断当前结点在该树中是否已有前缀树
for(int k=0;k<curNode.child.size();k++){
if(chars[j] == curNode.child.get(k).getValue()){
curNode = curNode.child.get(k);
pre = true;
break;
}
}
if(!pre) {
Trie newChild = new Trie(chars[j]);
curNode.createChild(newChild);
curNode = newChild;
}
}
curNode.setIsleaf(true);
curNode.itype = dict.get(i).itype;
curNode = root;
}
}构建fail指针。
//对当前Trie树进行fail指针的建立
public void createFail(Trie root){
Queue<Trie> queue = new LinkedList<>();
queue.add(root);
root.setFail(root);
int index = 0;
while(!queue.isEmpty()){
Trie curNode = queue.remove();
if(index == 0){
for(int i=0;i<curNode.child.size();i++){
curNode.child.get(i).setFail(root);
}
}else {
for(int i=0;i<curNode.child.size();i++){
for(int j=0;j<curNode.getFail().child.size();j++){
Trie node1 = curNode.child.get(i);
Trie node2 = curNode.getFail().child.get(j);
if(node1.getValue() == node2.getValue()){
node1.setFail(node2);
break;
}
node1.setFail(root);
}
}
}
index++;
for(int i=0;i<curNode.child.size();i++){
queue.add(curNode.child.get(i));
}
}
}当trie树和fail指针建立完成后，我们的AC自动机的核心部分也就全部完成了，接下来只需要对给定文本，在trie树中进行一个搜索遍历关键字的过程即可。这里结合个人需要，我还单独写了一点提取了一下详细的日期的代码，并将其单独命名为另一个类型。
//给定文本，在文本中查找关键字
public List<TypeKey> keySearch(String sen, Trie root){//sen表示给定的文本，root表示关键字构建的Trie树
List<TypeKey> res = new ArrayList<>();//res表示查找之后的结果
char[] chars = sen.toCharArray();//将文本字符串转化成字符数组方便遍历
Trie curNode = root;
String key = "";//关键字
String detailedDate = "";//详细日期
Boolean isDate = false;//用于判断详细日期的布尔变量
for(int i=0;i<chars.length;i++){
//对具体日期进行单独处理，如：18年9月5号
if(isDate){
if(chars[i] == '年' || chars[i] == '月' || chars[i] == '日' || chars[i] == '号' || chars[i] == '点'){
detailedDate += chars[i];
if((i+1<chars.length) && (chars[i+1]<48 || chars[i+1]>57)){
TypeKey tk = new TypeKey();
tk.ikey = detailedDate;
tk.itype = "time0";//详细时间类型定义为time0
res.add(tk);
isDate = false;
}
}
}
if(chars[i] >= 48 && chars[i] <= 57){//char类型中的数字0-9对应int型中的48-57
isDate = true;
detailedDate += chars[i];
}
//对Trie树上的关键字进行查找
for(int j=0;j<curNode.child.size();j++){
if(chars[i] == curNode.child.get(j).getValue()){
key += chars[i];
curNode = curNode.child.get(j);
break;
}
if(j == curNode.child.size()-1){
curNode = curNode.getFail();
key = "";
}
}
if(curNode.isleaf){
TypeKey tk = new TypeKey();
tk.ikey = key;
tk.itype = curNode.itype;
res.add(tk);
curNode = curNode.getFail();
key = "";
}
}
return res;
}简单实现了一下广度优先搜索和深度优先搜索，用于更好的查看我们构建的树的结构。
//深度优先搜索遍历
public void DFS(Trie root){
System.out.println(root.getValue());
for(int i=0;i<root.child.size();i++){
DFS(root.child.get(i));
}
}
//广度优先搜索遍历
public void BFS(Trie root){
Queue<Trie> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
Trie curNode = queue.remove();
System.out.println(curNode.getValue() + " " + curNode.getFail().getValue());
for(int i=0;i<curNode.child.size();i++){
queue.add(curNode.child.get(i));
}
}
}到这里，全部函数也就完成了，我们简单测试一下抽取参数的效果。
String sen = "今年9月5号集团的总发电量是多少";//给定的文本
AutoAC autoAC = new AutoAC();
Trie root = new Trie();
autoAC.createTrie(strings, root);
autoAC.createFail(root);
//autoAC.DFS(root);
//System.out.println(new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS") .format(new Date()));
List<TypeKey> res = autoAC.keySearch(sen, root);
//System.out.println(new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS") .format(new Date()));
for(int i=0;i<res.size();i++){
System.out.println(res.get(i).ikey + " " + res.get(i).itype);
}运行结果如下。
可见成功的提取出了参数和类型。
以上呢，就是我个人对中文AC自动机构建的一些思路和具体代码的实现。个人能力还有诸多不足，有可以改进的地方也欢迎和我一起探讨~
版权声明：本文为qq_36676123原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。