- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章多模字符串匹配算法原理及Java实现代码由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.
多模字符串匹配算法在这里指的是在一个字符串中寻找多个模式字符字串的问题。一般来说,给出一个长字符串和很多短模式字符串,如何最快最省的求出哪些模式字符串出现在长字符串中是我们所要思考的。该算法广泛应用于关键字过滤、入侵检测、病毒检测、分词等等问题中。多模问题一般有trie树,ac算法,wm算法等等.
背景 。
在做实际工作中,最简单也最常用的一种自然语言处理方法就是关键词匹配,例如我们要对n条文本进行过滤,那本身是一个过滤词表的,通常进行过滤的代码如下 。
1
2
3
4
5
6
7
|
for
(string document : documents) {
for
(string filterword : filterwords) {
if
(document.contains(filterword)) {
//process ...
}
}
}
|
如果文本的数量是n,过滤词的数量是k,那么复杂度为o(nk);如果关键词的数量较多,那么支行效率是非常低的.
计算机科学中,aho–corasick算法是由alfredv.aho和margaretj.corasick发明的字符串搜索算法,用于在输入的一串字符串中匹配有限组“字典”中的子串。它与普通字符串匹配的不同点在于同时与所有字典串进行匹配。算法均摊情况下具有近似于线性的时间复杂度,约为字符串的长度加所有匹配的数量。然而由于需要找到所有匹配数,如果每个子串互相匹配(如字典为a,aa,aaa,aaaa,输入的字符串为aaaa),算法的时间复杂度会近似于匹配的二次函数.
原理 。
在一般的情况下,针对一个文本进行关键词匹配,在匹配的过程中要与每个关键词一一进行计算。也就是说,每与一个关键词进行匹配,都要重新从文档的开始到结束进行扫描。ac自动机的思想是,在开始时先通过词表,对以下三种情况进行缓存:
按照字符转移成功进行跳转(success表) 。
按照字符转移失败进行跳转(fail表) 。
匹配成功输出表(output表) 。
因此在匹配的过程中,无需从新从文档的开始进行匹配,而是通过缓存直接进行跳转,从而实现近似于线性的时间复杂度.
构建 。
构建的过程分三个步骤,分别对success表,fail表,output表进行构建。其中output表在构建sucess和fail表进行都进行了补充。fail表是一对一的,output表是一对多的.
按照字符转移成功进行跳转(success表) 。
sucess表实际就是一棵trie树,构建的方式和trie树是一样的,这里就不赘述.
按照字符转移失败进行跳转(fail表) 。
设这个节点上的字母为c,沿着他父亲的失败指针走,直到走到一个节点,他的儿子中也有字母为c的节点。然后把当前节点的失败指针指向那个字母也为c的儿子。如果一直走到了root都没找到,那就把失败指针指向root。使用广度优先搜索bfs,层次遍历节点来处理,每一个节点的失败路径.
匹配成功输出表(output表) 。
匹配 。
举例说明,按顺序先后添加关键词he,she,,his,hers。在匹配ushers过程中。先构建三个表,如下图,实线是sucess表,虚线是fail表,结点后的单词是ourput表.
代码 。
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
|
import
java.util.*;
/**
*/
public
class
actrie {
private
boolean
failurestatesconstructed =
false
;
//是否建立了failure表
private
node root;
//根结点
public
actrie() {
this
.root =
new
node(
true
);
}
/**
* 添加一个模式串
* @param keyword
*/
public
void
addkeyword(string keyword) {
if
(keyword ==
null
|| keyword.length() ==
0
) {
return
;
}
node currentstate =
this
.root;
for
(character character : keyword.tochararray()) {
currentstate = currentstate.insert(character);
}
currentstate.addemit(keyword);
}
/**
* 模式匹配
*
* @param text 待匹配的文本
* @return 匹配到的模式串
*/
public
collection<emit> parsetext(string text) {
checkforconstructedfailurestates();
node currentstate =
this
.root;
list<emit> collectedemits =
new
arraylist<>();
for
(
int
position =
0
; position < text.length(); position++) {
character character = text.charat(position);
currentstate = currentstate.nextstate(character);
collection<string> emits = currentstate.emit();
if
(emits ==
null
|| emits.isempty()) {
continue
;
}
for
(string emit : emits) {
collectedemits.add(
new
emit(position - emit.length() +
1
, position, emit));
}
}
return
collectedemits;
}
/**
* 检查是否建立了failure表
*/
private
void
checkforconstructedfailurestates() {
if
(!
this
.failurestatesconstructed) {
constructfailurestates();
}
}
/**
* 建立failure表
*/
private
void
constructfailurestates() {
queue<node> queue =
new
linkedlist<>();
// 第一步,将深度为1的节点的failure设为根节点
//特殊处理:第二层要特殊处理,将这层中的节点的失败路径直接指向父节点(也就是根节点)。
for
(node depthonestate :
this
.root.children()) {
depthonestate.setfailure(
this
.root);
queue.add(depthonestate);
}
this
.failurestatesconstructed =
true
;
// 第二步,为深度 > 1 的节点建立failure表,这是一个bfs 广度优先遍历
/**
* 构造失败指针的过程概括起来就一句话:设这个节点上的字母为c,沿着他父亲的失败指针走,直到走到一个节点,他的儿子中也有字母为c的节点。
* 然后把当前节点的失败指针指向那个字母也为c的儿子。如果一直走到了root都没找到,那就把失败指针指向root。
* 使用广度优先搜索bfs,层次遍历节点来处理,每一个节点的失败路径。
*/
while
(!queue.isempty()) {
node parentnode = queue.poll();
for
(character transition : parentnode.gettransitions()) {
node childnode = parentnode.find(transition);
queue.add(childnode);
node failnode = parentnode.getfailure().nextstate(transition);
childnode.setfailure(failnode);
childnode.addemit(failnode.emit());
}
}
}
private
static
class
node{
private
map<character, node> map;
private
list<string> emits;
//输出
private
node failure;
//失败中转
private
boolean
isroot =
false
;
//是否为根结点
public
node(){
map =
new
hashmap<>();
emits =
new
arraylist<>();
}
public
node(
boolean
isroot) {
this
();
this
.isroot = isroot;
}
public
node insert(character character) {
node node =
this
.map.get(character);
if
(node ==
null
) {
node =
new
node();
map.put(character, node);
}
return
node;
}
public
void
addemit(string keyword) {
emits.add(keyword);
}
public
void
addemit(collection<string> keywords) {
emits.addall(keywords);
}
/**
* success跳转
* @param character
* @return
*/
public
node find(character character) {
return
map.get(character);
}
/**
* 跳转到下一个状态
* @param transition 接受字符
* @return 跳转结果
*/
private
node nextstate(character transition) {
node state =
this
.find(transition);
// 先按success跳转
if
(state !=
null
) {
return
state;
}
//如果跳转到根结点还是失败,则返回根结点
if
(
this
.isroot) {
return
this
;
}
// 跳转失败的话,按failure跳转
return
this
.failure.nextstate(transition);
}
public
collection<node> children() {
return
this
.map.values();
}
public
void
setfailure(node node) {
failure = node;
}
public
node getfailure() {
return
failure;
}
public
set<character> gettransitions() {
return
map.keyset();
}
public
collection<string> emit() {
return
this
.emits ==
null
? collections.<string>emptylist() :
this
.emits;
}
}
private
static
class
emit{
private
final
string keyword;
//匹配到的模式串
private
final
int
start;
private
final
int
end;
/**
* 构造一个模式串匹配结果
* @param start 起点
* @param end 重点
* @param keyword 模式串
*/
public
emit(
final
int
start,
final
int
end,
final
string keyword) {
this
.start = start;
this
.end = end;
this
.keyword = keyword;
}
/**
* 获取对应的模式串
* @return 模式串
*/
public
string getkeyword() {
return
this
.keyword;
}
@override
public
string tostring() {
return
super
.tostring() +
"="
+
this
.keyword;
}
}
public
static
void
main(string[] args) {
actrie trie =
new
actrie();
trie.addkeyword(
"hers"
);
trie.addkeyword(
"his"
);
trie.addkeyword(
"she"
);
trie.addkeyword(
"he"
);
collection<emit> emits = trie.parsetext(
"ushers"
);
for
(emit emit : emits) {
system.out.println(emit.start +
" "
+ emit.end +
"\t"
+ emit.getkeyword());
}
}
}
|
总结 。
以上就是本文关于多模字符串匹配算法原理及java实现代码的全部内容,希望对大家有所帮助。如有不足之处,欢迎留言指出。感谢朋友们对本站的支持.
原文链接:https://www.cnblogs.com/hwyang/p/6836438.html 。
最后此篇关于多模字符串匹配算法原理及Java实现代码的文章就讲到这里了,如果你想了解更多关于多模字符串匹配算法原理及Java实现代码的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
本文全面深入地探讨了Docker容器通信技术,从基础概念、网络模型、核心组件到实战应用。详细介绍了不同网络模式及其实现,提供了容器通信的技术细节和实用案例,旨在为专业从业者提供深入的技术洞见和实
📒博客首页:崇尚学技术的科班人 🍣今天给大家带来的文章是《Dubbo快速上手 -- 带你了解Dubbo使用、原理》🍣 🍣希望各位小伙伴们能够耐心的读完这篇文章🍣 🙏博主也在学习阶段,如若发
一、写在前面 我们经常使用npm install ,但是你是否思考过它内部的原理是什么? 1、执行npm install 它背后帮助我们完成了什么操作? 2、我们会发现还有一个成为package-lo
Base64 Base64 是什么?是将字节流转换成可打印字符、将可打印字符转换为字节流的一种算法。Base64 使用 64 个可打印字符来表示转换后的数据。 准确的来说,Base64 不算
目录 协程定义 生成器和yield语义 Future类 IOLoop类 coroutine函数装饰器 总结 tornado中的
切片,这是一个在go语言中引入的新的理念。它有一些特征如下: 对数组抽象 数组长度不固定 可追加元素 切片容量可增大 容量大小成片增加 我们先把上面的理念整理在这
文章来源:https://sourl.cn/HpZHvy 引 言 本文主要论述的是“RPC 实现原理”,那么首先明确一个问题什么是 RPC 呢?RPC 是 Remote Procedure Call
源码地址(包含所有与springmvc相关的,静态文件路径设置,request请求入参接受,返回值处理converter设置等等): spring-framework/WebMvcConfigurat
请通过简单的java类向我展示一个依赖注入(inject)原理的小例子虽然我已经了解了spring,但是如果我需要用简单的java类术语来解释它,那么你能通过一个简单的例子向我展示一下吗?提前致谢。
1、背景 我们平常使用手机和电脑上网,需要访问公网上的网络资源,如逛淘宝和刷视频,那么手机和电脑是怎么知道去哪里去拿到这个网络资源来下载到本地的呢? 就比如我去食堂拿吃的,我需要
大家好,我是飞哥! 现在 iptables 这个工具的应用似乎是越来越广了。不仅仅是在传统的防火墙、NAT 等功能出现,在今天流行的的 Docker、Kubernets、Istio 项目中也经
本篇涉及到的所有接口在公开文档中均无,需要下载 GitHub 上的源码,自己创建私有类的文档。 npm run generateDocumentation -- --private yarn gene
我最近在很多代码中注意到人们将硬编码的配置(如端口号等)值放在类/方法的深处,使其难以找到,也无法配置。 这是否违反了 SOLID 原则?如果不是,我是否可以向我的团队成员引用另一个“原则”来说明为什
我是 C#、WPF 和 MVVM 模式的新手。很抱歉这篇很长的帖子,我试图设定我所有的理解点(或不理解点)。 在研究了很多关于 WPF 提供的命令机制和 MVVM 模式的文本之后,我在弄清楚如何使用这
可比较的 jQuery 函数 $.post("/example/handler", {foo: 1, bar: 2}); 将创建一个带有 post 参数 foo=1&bar=2 的请求。鉴于 $htt
如果Django不使用“延迟查询执行”原则,主要问题是什么? q = Entry.objects.filter(headline__startswith="What") q = q.filter(
我今天发现.NET框架在做计算时遵循BODMAS操作顺序。即计算按以下顺序进行: 括号 订单 部门 乘法 添加 减法 但是我四处搜索并找不到任何文档确认 .NET 绝对 遵循此原则,是否有此类文档?如
已结束。此问题不符合 Stack Overflow guidelines .它目前不接受答案。 我们不允许提出有关书籍、工具、软件库等方面的建议的问题。您可以编辑问题,以便用事实和引用来回答它。 关闭
API 回顾 在创建 Viewer 时可以直接指定 影像供给器(ImageryProvider),官方提供了一个非常简单的例子,即离屏例子(搜 offline): new Cesium.Viewer(
As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be
我是一名优秀的程序员,十分优秀!