如何使用Java实现AC自动机全文检索实例

导语：如何使用Java实现AC自动机全文检索，下面是小编给大家推荐的代码实现过程，大家可以参考阅读，更多详情请关注应届毕业生考试网。

　　第一步，构建Trie树，定义Node类型：

/**

* Created by zhaoyy on 2017/2/7.

*/

interface Node {

char value();

boolean exists();

boolean isRoot();

Node parent();

Node childOf(char c);

Node fail();

void setFail(Node node);

void setExists(boolean exists);

void add(Node child);

List<Node> children();

}

　　第二步，实现两种Node，如果词汇全是可打印的ASCII字符，就采用AsciiNode，否则（比如包含汉字），使用基于hash表的ode；这两种Node均集成自AbstractNode:

/**

* Created by zhaoyy on 2017/2/8.

*/

abstract class AbstractNode implements Node {

private static final char EMPTY = '';

private final char value;

private final Node parent;

private boolean exists;

private Node fail;

public AbstractNode(Node parent, char value) {

nt = parent;

e = value;

ts = false;

= null;

}

public AbstractNode() {

this(null, EMPTY);

}

private static String tab(int n) {

StringBuilder builder = new StringBuilder();

for (int i = 0; i < n; i++) {

nd('t');

}

return ring();

}

private static String toString(Node node, int depth) {

StringBuilder builder = new StringBuilder();

String tab = tab(depth);

Node fail = ();

Node parent = nt();

builder

nd(tab)

nd('<')

nd(e())

nd(" exists="")

nd(ts())

nd('"')

nd(" parent="")

nd(parent == null ? "null" : e())

nd('"')

nd(" fail="")

nd(fail == null ? "null" : e())

nd("">rn");

for (Node child : dren())

nd(toString(child, depth + 1));

builder

nd(tab)

nd("</")

nd(e())

nd(">rn");

return ring();

}

@Override

public char value() {

return value;

}

@Override

public boolean exists() {

return exists;

}

@Override

public boolean isRoot() {

return value == EMPTY;

}

@Override

public Node parent() {

return parent;

}

@Override

public Node fail() {

return fail;

}

@Override

public void setFail(Node node) {

= node;

}

@Override

public void setExists(boolean exists) {

ts = exists;

}

@Override

public String toString() {

return toString(this, 0);

}

}

/////////////////////////////////////////////////////////////////////////////////////////////

/**

* Created by zhaoyy on 2017/2/8.

*/

final class AsciiNode extends AbstractNode implements Node {

private static final char FROM = 32;

private static final char TO = 126;

private final Node[] children;

public AsciiNode() {

super();

dren = new Node[TO - FROM + 1];

}

public AsciiNode(Node parent, char value) {

super(parent, value);

dren = new Node[TO - FROM + 1];

}

@Override

public Node childOf(char c) {

if (c >= FROM && c <= TO)

return children[(int) c - FROM];

else return null;

}

@Override

public void add(Node child) {

int index = (int) e();

children[index - FROM] = child;

}

@Override

public List<Node> children() {

List<Node> nodes = new ArrayList<Node>();

for (Node child : children)

if (child != null)

(child);

return nodes;

}

}

//////////////////////////////////////////////////////////////////////////////////////////////

/**

* Created by zhaoyy on 2017/2/8.

*/

final class MapNode extends AbstractNode implements Node {

private final Map<Character, Node> children;

public MapNode() {

super();

dren = new HashMap<Character, Node>();

}

public MapNode(Node parent, char value) {

super(parent, value);

dren = new HashMap<Character, Node>();

}

@Override

public Node childOf(char c) {

return (c);

}

@Override

public void add(Node child) {

(e(), child);

}

@Override

public List<Node> children() {

List<Node> nodes = new ArrayList<Node>();

ll(es());

return nodes;

}

}

　　第三步，

首先定义一个Node构造器：

/**

* Created by zhaoyy on 2017/2/8.

*/

public interface NodeMaker {

Node make(Node parent, char value);

Node makeRoot();

}

然后构建AC自动机，实现创建及查找方法：

/**

* Created by zhaoyy on 2017/2/7.

*/

public final class WordTable {

private final Node root;

private WordTable(Collection<? extends CharSequence> words, NodeMaker maker) {

Node root = buildTrie(words, maker);

setFailNode(root);

= root;

}

public static WordTable compile(Collection<? extends CharSequence> words) {

if (words == null || pty())

throw new IllegalArgumentException();

final NodeMaker maker;

if (isAscii(words))

maker = new NodeMaker() {

@Override

public Node make(Node parent, char value) {