Java實(shí)現(xiàn)AC自動(dòng)機(jī)全文檢索示例
更新時(shí)間：2017年02月08日 16:53:55 作者：Acce1erator
本篇文章主要介紹了Java實(shí)現(xiàn)AC自動(dòng)機(jī)全文檢索示例，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧
第一步，構(gòu)建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();
}
第二步，實(shí)現(xiàn)兩種Node，如果詞匯全是可打印的ASCII字符，就采用AsciiNode，否則（比如包含漢字），使用基于hash表的MapNode；這兩種Node均集成自AbstractNode:
/**
* Created by zhaoyy on 2017/2/8.
*/
abstract class AbstractNode implements Node {
private static final char EMPTY = '\0';
private final char value;
private final Node parent;
private boolean exists;
private Node fail;
public AbstractNode(Node parent, char value) {
this.parent = parent;
this.value = value;
this.exists = false;
this.fail = null;
}
public AbstractNode() {
this(null, EMPTY);
}
private static String tab(int n) {
StringBuilder builder = new StringBuilder();
for (int i = 0; i < n; i++) {
builder.append('\t');
}
return builder.toString();
}
private static String toString(Node node, int depth) {
StringBuilder builder = new StringBuilder();
String tab = tab(depth);
Node fail = node.fail();
Node parent = node.parent();
builder
.append(tab)
.append('<')
.append(node.value())
.append(" exists=\"")
.append(node.exists())
.append('"')
.append(" parent=\"")
.append(parent == null ? "null" : parent.value())
.append('"')
.append(" fail=\"")
.append(fail == null ? "null" : fail.value())
.append("\">\r\n");
for (Node child : node.children())
builder.append(toString(child, depth + 1));
builder
.append(tab)
.append("</")
.append(node.value())
.append(">\r\n");
return builder.toString();
}
@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) {
this.fail = node;
}
@Override
public void setExists(boolean exists) {
this.exists = 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();
this.children = new Node[TO - FROM + 1];
}
public AsciiNode(Node parent, char value) {
super(parent, value);
this.children = 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) child.value();
children[index - FROM] = child;
}
@Override
public List<Node> children() {
List<Node> nodes = new ArrayList<Node>();
for (Node child : children)
if (child != null)
nodes.add(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();
this.children = new HashMap<Character, Node>();
}
public MapNode(Node parent, char value) {
super(parent, value);
this.children = new HashMap<Character, Node>();
}
@Override
public Node childOf(char c) {
return children.get(c);
}
@Override
public void add(Node child) {
children.put(child.value(), child);
}
@Override
public List<Node> children() {
List<Node> nodes = new ArrayList<Node>();
nodes.addAll(children.values());
return nodes;
}
}
第三步，
首先定義一個(gè)Node構(gòu)造器：
/**
* Created by zhaoyy on 2017/2/8.
*/
public interface NodeMaker {
Node make(Node parent, char value);
Node makeRoot();
}
然后構(gòu)建AC自動(dòng)機(jī)，實(shí)現(xiàn)創(chuàng)建及查找方法：
/**
* 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);
this.root = root;
}
public static WordTable compile(Collection<? extends CharSequence> words) {
if (words == null || words.isEmpty())
throw new IllegalArgumentException();
final NodeMaker maker;
if (isAscii(words))
maker = new NodeMaker() {
@Override
public Node make(Node parent, char value) {
return new AsciiNode(parent, value);
}
@Override
public Node makeRoot() {
return new AsciiNode();
}
};
else maker = new NodeMaker() {
@Override
public Node make(Node parent, char value) {
return new MapNode(parent, value);
}
@Override
public Node makeRoot() {
return new MapNode();
}
};
return new WordTable(words, maker);
}
private static boolean isAscii(Collection<? extends CharSequence> words) {
for (CharSequence word : words) {
int len = word.length();
for (int i = 0; i < len; i++) {
int c = (int) word.charAt(i);
if (c < 32 || c > 126)
return false;
}
}
return true;
}
private static Node buildTrie(Collection<? extends CharSequence> sequences, NodeMaker maker) {
Node root = maker.makeRoot();
for (CharSequence sequence : sequences) {
int len = sequence.length();
Node current = root;
for (int i = 0; i < len; i++) {
char c = sequence.charAt(i);
Node node = current.childOf(c);
if (node == null) {
node = maker.make(current, c);
current.add(node);
}
current = node;
if (i == len - 1)
node.setExists(true);
}
}
return root;
}
private static void setFailNode(final Node root) {
root.setFail(null);
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
while (!queue.isEmpty()) {
Node parent = queue.poll();
Node temp;
for (Node child : parent.children()) {
if (parent.isRoot())
child.setFail(root);
else {
temp = parent.fail();
while (temp != null) {
Node node = temp.childOf(child.value());
if (node != null) {
child.setFail(node);
break;
}
temp = temp.fail();
}
if (temp == null)
child.setFail(root);
}
queue.add(child);
}
}
}
public boolean findAnyIn(CharSequence cs) {
int len = cs.length();
Node node = root;
for (int i = 0; i < len; i++) {
Node next = node.childOf(cs.charAt(i));
if (next == null) {
next = node.fail();
if (next == null) {
node = root;
continue;
}
}
if (next.exists())
return true;
}
return false;
}
public List<MatchInfo> search(CharSequence cs) {
if (cs == null || cs.length() == 0)
return Collections.emptyList();
List<MatchInfo> result = new ArrayList<MatchInfo>();
int len = cs.length();
Node node = root;
for (int i = 0; i < len; i++) {
Node next = node.childOf(cs.charAt(i));
if (next == null) {
next = node.fail();
if (next == null) {
node = root;
continue;
}
}
if (next.exists()) {
MatchInfo info = new MatchInfo(i, next);
result.add(info);
node = root;
continue;
}
node = next;
}
return result;
}
@Override
public String toString() {
return root.toString();
}
}
定義一個(gè)保存查找結(jié)果的實(shí)體：
/**
* Created by zhaoyy on 2017/2/7.
*/
public final class MatchInfo {
private final int index;
private final String word;
public MatchInfo(int index, String word) {
this.index = index;
this.word = word;
}
public MatchInfo(int index, Node node) {
StringBuilder builder = new StringBuilder();
while (node != null) {
if (!node.isRoot())
builder.append(node.value());
node = node.parent();
}
String word = builder.reverse().toString();
this.index = index + 1 - word.length();
this.word = word;
}
public int getIndex() {
return index;
}
public String getWord() {
return word;
}
@Override
public String toString() {
return index + ":" + word;
}
}
第四步，調(diào)用Demo：
public static void main(String[] args) {
List<String> list = Arrays.asList("say", "her", "he", "she", "shr", "alone");
WordTable table = WordTable.compile(list);
System.out.println(table);
System.out.println(table.search("1shesaynothingabouthislivinghimalone"));
}
以下是輸出結(jié)果：
< exists="false" parent="null" fail="null"> <s exists="false" parent=" " fail=" "> <a exists="false" parent="s" fail="a"> <y exists="true" parent="a" fail=" "> </y> </a> <h exists="false" parent="s" fail="h"> <e exists="true" parent="h" fail="e"> </e> <r exists="true" parent="h" fail=" "> </r> </h> </s> <h exists="false" parent=" " fail=" "> <e exists="true" parent="h" fail=" "> <r exists="true" parent="e" fail=" "> </r> </e> </h> <a exists="false" parent=" " fail=" "> <l exists="false" parent="a" fail=" "> <o exists="false" parent="l" fail=" "> <n exists="false" parent="o" fail=" "> <e exists="true" parent="n" fail=" "> </e> </n> </o> </l> </a> </ > [1:she, 4:say, 31:alone]
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
使用ClassFinal實(shí)現(xiàn)SpringBoot項(xiàng)目jar包加密的操作指南
在實(shí)際開發(fā)中,保護(hù)項(xiàng)目的安全性和保密性是至關(guān)重要的,針對(duì)于 Spring Boot 項(xiàng)目,我們需要將 JAR 包進(jìn)行加密從而有效地防止未經(jīng)授權(quán)的訪問和修改,本文將介紹如何使用ClassFinal在 Spring Boot 項(xiàng)目中實(shí)現(xiàn) JAR 包加密,需要的朋友可以參考下2024-06-06
這篇文章主要為大家詳細(xì)介紹了java利用SMB讀取遠(yuǎn)程文件的方法，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-05-05
java性能調(diào)優(yōu)System的gc垃圾回收方法
這篇文章主要為大家介紹了java性能調(diào)優(yōu)System的gc垃圾回收方法示例解析有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步2022-03-03
這篇文章主要為大家詳細(xì)介紹了java多線程下載文件原理，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-04-04
有的項(xiàng)目可能需要用到直接外部調(diào)用阿里通義千問的接口,下面這篇文章主要介紹了java對(duì)接阿里通義千問的簡(jiǎn)單教程,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下2025-03-03
本文主要介紹了一文詳解JavaWeb過濾器(Filter)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-05-05
這篇文章介紹了Java匿名內(nèi)部類的實(shí)現(xiàn)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-12-12
idea項(xiàng)目文件夾橫向顯示,縱向顯示的解決方法
這篇文章主要介紹了idea項(xiàng)目文件夾橫向顯示,縱向顯示的解決方法,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-08-08
Java中判斷對(duì)象是否相等的equals()方法使用教程
與==運(yùn)算符響應(yīng),equals()方法也是Java中對(duì)對(duì)象進(jìn)行比較的一大方式,要特別注意二者的不同點(diǎn),這個(gè)我們?cè)谙挛闹屑磳⒅v到,接下來我們就來看一下Java中判斷對(duì)象是否相等的equals()方法使用教程2016-05-05
SpringBoot實(shí)現(xiàn)PPT格式文件上傳并在線預(yù)覽功能
本文介紹SpringBoot實(shí)現(xiàn)PPT格式文件上傳并在線預(yù)覽功能，通過上傳接口，可在C盤的tempfile目錄下找到上傳的文件，預(yù)覽時(shí)會(huì)在同級(jí)目錄下創(chuàng)建一個(gè)相同文件名后綴為pdf的文件，每次預(yù)覽會(huì)先查找文件是否存在，存在則直接預(yù)覽，不存在則會(huì)走上面的處理,需要的朋友可以參考下2022-02-02