先读我,一分钟了解算法原理

这是一个文本中同时查找多个字符串的项目

先读我,一分钟了解算法原理

帖子Normangen » 2015-05-13 11:42

有限状态机是从单词表中构建来的。怎么构建的先不管,先看怎么搜索:
图片
待搜索的文本是:a white fox,共有三个单词:a, white, fox
而单词表中:
有单词 aid, all,没有单词 a
有单词 what,没有单词 white
有单词 fox
GTalkabout 写道:Click to open by GTalkabout: 13a237c0-f922-11e4-942b-1aee658114e8
头像
Normangen
 
帖子: 20
注册: 2015-04-05 20:49

讨论代码在第292行(文件StringSet.cpp中)

帖子Normangen » 2015-05-13 11:43

当前状态从0开始
GTalkabout 写道:Click to open by GTalkabout: 3e6ef19e-f922-11e4-b2da-1aee658114e8
图片
头像
Normangen
 
帖子: 20
注册: 2015-04-05 20:49

讨论代码在第323行(文件StringSet.cpp中)

帖子Normangen » 2015-05-13 11:47

在有限状态机中找当前状态下(初始状态0),输入字符a的entry
GTalkabout 写道:Click to open by GTalkabout: c9f9c0b0-f922-11e4-b22d-1aee658114e8
图片
头像
Normangen
 
帖子: 20
注册: 2015-04-05 20:49

讨论代码在第340行(文件StringSet.cpp中)

帖子Normangen » 2015-05-13 11:56

因为单词表中有以a开头的单词aid和all,所以状态0收到a后会进入新状态,在这个状态下等待接收字符 i 或者字符 l , 如果碰巧后面是这两个字符,那么状态机会很高兴的继续进入新状态……看上去可以找到一个单词。
前面说了,会进入一个新状态,这个状态值是50,这个50并没有任何意义,而是在构建状态机时分配的这么一个数。
GTalkabout 写道:Click to open by GTalkabout: 07ec19cf-f924-11e4-9ffa-1aee658114e8
图片
头像
Normangen
 
帖子: 20
注册: 2015-04-05 20:49

讨论代码在第301行(文件StringSet.cpp中)

帖子Normangen » 2015-05-13 12:01

这个时候意外发生了,a后面的是空格,nIdx是这个空格的序号,而nNextIdx是“字符串中下一个非空格、符号的序号”,也就是空格后面的 w 字符的序号,造成这里不相等。
GTalkabout 写道:Click to open by GTalkabout: b0b5544f-f924-11e4-ba17-1aee658114e8
图片
头像
Normangen
 
帖子: 20
注册: 2015-04-05 20:49

讨论代码在第309行(文件StringSet.cpp中)

帖子Normangen » 2015-05-13 12:03

当前状态从50又重置回 0,这就意味着状态机不要再想着能收到 i 或者 l 了,也不会找到 aid 或者 all了,从 0 开始。
GTalkabout 写道:Click to open by GTalkabout: 12651c80-f925-11e4-b4e5-1aee658114e8
图片
头像
Normangen
 
帖子: 20
注册: 2015-04-05 20:49

讨论代码在第310行(文件StringSet.cpp中)

帖子Normangen » 2015-05-13 12:06

单词序号也从字符 w 的序号开始,意味着和上一次相比,在状态 0 下输入的不是字符a而是字符w了。
GTalkabout 写道:Click to open by GTalkabout: 619e2da1-f925-11e4-b110-1aee658114e8
图片
头像
Normangen
 
帖子: 20
注册: 2015-04-05 20:49

讨论代码在第323行(文件StringSet.cpp中)

帖子Normangen » 2015-05-13 12:07

在有限状态机中找当前状态下(初始状态0),输入字符w的entry
GTalkabout 写道:Click to open by GTalkabout: 952c92b0-f925-11e4-bd84-1aee658114e8
图片
头像
Normangen
 
帖子: 20
注册: 2015-04-05 20:49

讨论代码在第340行(文件StringSet.cpp中)

帖子Normangen » 2015-05-13 14:21

w开头的单词有what,所以进入新状态,状态值是86。同样,86也没有意义,仅是构建状态机时分配的状态值。
GTalkabout 写道:Click to open by GTalkabout: 3f4d41ae-f938-11e4-9ea9-1aee658114e8
图片
头像
Normangen
 
帖子: 20
注册: 2015-04-05 20:49

讨论代码在第323行(文件StringSet.cpp中)

帖子Normangen » 2015-05-13 14:23

在有限状态机中找当前状态下(86),输入字符h的entry
GTalkabout 写道:Click to open by GTalkabout: 86a1e840-f938-11e4-9783-1aee658114e8
图片
头像
Normangen
 
帖子: 20
注册: 2015-04-05 20:49

下一页

回到 Normangen 的项目

在线用户

正在浏览此版面的用户:没有注册用户 和 2 位游客