一种基于状态机的 DOM 树生成技术(1)


声明:本文转载自https://my.oschina.net/gschen/blog/1618549,转载目的在于传递更多信息,仅供学习交流之用。如有侵权行为,请联系我,我会及时删除。

本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列博客。

DOM(Document Object Model)即文档对象模型,是一种非常重要的数据结构,用途非常广泛。

对于浏览器的渲染引擎来说,需要将html 字符串转换成 DOM 树,再转换成渲染树,最后才进行渲染。

对于数据采集来说,经常需要做的是解析已经下载的 html 文档,而这种解析工作的前提是要生成 html 文档的 DOM 树,然后才能解析。

本系列博客将为大家介绍一种基于状态机的 DOM树生成技术,从最初的 html 文档如何一步步生成最终的 DOM 树。

 本讲我们将为大家介绍状态机的基本知识。

1 状态机介绍

 

图1- 1 状态机示例图

我们从上述一个简单的示例来介绍什么是状态机,图中四个圆圈分别表示四个状态即状态0,状态1,状态2,状态3。其中状态0表示起始状态,状态2、状态3表示终止状态。起始状态表示任务开始的地方,终止状态将不再接受任何输入。

状态0:当用户输入字符'a'的时候,将进入状态1,其他字符将进入状态3。

状态1:用户可以不停的输入字符'b',但是会一直处于状态1,当用户输入字符'a'的时候,将进入状态2,其他字符进入状态3。

状态2:终止状态,不再接受任何输入。

状态3:终止状态,不再接受任何输入。

上面给大家介绍的就是状态机,在状态机中有多个状态,一般情况下,有一个起始状态,多个中间状态和终止状态。对于每一个状态可以接受不同的输入,或维持在当前状态,或进入下一个状态。

上面给大家介绍的这个状态机,其实功能很简单,这个状态机可以接受任何abbbb*a模式的字符串如:aba, abba, abbba等。

状态机的用途非常的广泛,不仅在正则表达式,编译器等众多领域发挥重要作用。

2 状态机实现

有了上述的状态机基本知识后,本节将为大家介绍如何用 Java 语言实现状态机。

要想实现上述状态机,我们有以下三个任务需要完成:

(1)对字符串输入的控制。

我们需要定义一个类能够实现非常方便的控制整个输入的字符串,每次移动一个字符。

这个类非常的简单,如下所示:

public class CharacterReader {     private String content;     private int pos;      public CharacterReader(String content) {         this.content = content;         pos = 0;     }      public char consume() {          return content.charAt(pos++);     } }

对于给定的任意一个字符串如"abbba",我们保存在 content 属性中,再定义一个 pos 属性,标记当前正在处理的是哪一个字符位置,处理完一个字符后,位置后移一位,初始位置为0。

CharacterReader reader = new CharacterReader("abbba");

 

(2)各种状态的定义。

在本例中,我们有四个状态,所以需要定义四个状态类StateZero, StateOne, StateTwo, StateThree。

每一个状态类的处理逻辑都是类似的,基本的业务处理逻辑为:

接受一个字符,然后判断是否进行状态转移。

所以我们可以抽象一个状态基类 State,在基类中可以定义一个共同的抽象方法,如下:

public enum State {     abstract void read(StateController controller, CharacterReader reader); }

 

这里面我们使用是枚举类型来定义基类 State,并且定义了一个抽象方法 read,该方法有两个参数:

第一个是状态控制逻辑controller,通过 controller我们可以快速的转移状态;

第二个是输入字符串的一个封装,通过consume方法可以快速的得到当前字符。

接下来我们介绍 StateZero 的实现:

StateZero {     @Override     void read(StateController controller, CharacterReader reader) {          char ch = reader.consume();          switch (ch) {              case 'a':                 controller.transition(StateOne);                 break;              default:                 controller.transition(StateThree);                 break;          }     } }  

上述代码非常容易理解,根据第一节的状态转换图,我们知道,在状态0的时候,当输入字符'a'就转移到状态1,其他字符则转移到状态3。所以大家看到上述代码非常的简单易懂。

StateOne和 StateZero 类似,不再赘述。接下来介绍终止状态的实现。

 StateTwo {     @Override     void read(StateController controller, CharacterReader reader) {          controller.setTerminated(true);         System.out.println("Match!");     } }, StateThree {     @Override     void read(StateController controller, CharacterReader reader) {          controller.setTerminated(true);         System.out.println("UnMatch!");     } };

 

状态2和3都是终止状态,不再接受任何的输入,因此直接将 controller 的 terminated 设置为true 即可。

(3)状态控制逻辑。

这个任务是我们状态机实现的核心部分,也是最精彩的部分。我们通过定义一个状态控制逻辑类 StateController 来控制所有的流程。

public class StateController {      private CharacterReader reader;     private State state = State.StateZero;       private boolean isTerminated = false;      public StateController(CharacterReader reader) {         this.reader = reader;     }       // 将当前状态转移到新的状态     public void transition(State state){          this.state = state;     }      public void run() {          while (!isTerminated) {             state.read(this, reader);         }     }      public void setTerminated(boolean terminated) {         isTerminated = terminated;     } }

state属性持有当前状态机的状态,初始状态为 StateZero,isTerminated 属性表示当前状态机是否已经进入终止状态。

核心代码是:

while (!isTerminated) {       state.read(this, reader);  }

不停的检测状态机当前的状态是否处于终止状态,如果不是则不停的从 reader 接受输入字符,进入状态机。

最后是测试代码了:

public class StateTest {     public static void main(String[] args) {          CharacterReader reader = new CharacterReader("abbba");          StateController controller = new StateController(reader);         controller.run();     } }

综上,已经完成了一个状态机的设计,简单总结就是三个:输入控制,各种状态类定义,状态控制逻辑。

3 总结

本文通过一个简单的案例向大家介绍了状态机的基本知识,并给出了设计状态机的基本思路和相关代码,为后续讲解基于状态机的DOM 树的生成打好基础。

本文所有代码可在以下 git 库中 day01模块中找到,git 地址为:

https://gitee.com/gschen/sctu-treebuilder.git

欢迎持续关注“算法与编程之美”微信公众号,了解更多。

本文发表于2018年02月05日 14:39
(c)注:本文转载自https://my.oschina.net/gschen/blog/1618549,转载目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责。如有侵权行为,请联系我们,我们会及时删除.

阅读 1557 讨论 0 喜欢 0

抢先体验

扫码体验
趣味小程序
文字表情生成器

闪念胶囊

你要过得好哇,这样我才能恨你啊,你要是过得不好,我都不知道该恨你还是拥抱你啊。

直抵黄龙府,与诸君痛饮尔。

那时陪伴我的人啊,你们如今在何方。

不出意外的话,我们再也不会见了,祝你前程似锦。

这世界真好,吃野东西也要留出这条命来看看

快捷链接
网站地图
提交友链
Copyright © 2016 - 2021 Cion.
All Rights Reserved.
京ICP备2021004668号-1