澳门新葡亰娱乐官网高性能Java解析器实现过程详解

澳门新葡亰娱乐官网 19

如果你没有指定数据或语言标准的或开源的Java解析器,
可能经常要用Java实现你自己的数据或语言解析器。或者,可能有很多解析器可选,但是要么太慢,要么太耗内存,或者没有你需要的特定功能。或者开源解析器存在缺陷,或者开源解析器项目被取消诸如此类原因。上述原因都没有你将需要实现你自己的解析器的事实重要。

在某些情况下,你可能需要在Java中实现你自己的数据或语言解析器,也许是这种数据格式或语言缺乏标准的Java或开源解析器可以使用。或者虽然有现成的解析器实现,但它们要么太慢,要么太占内存,要么就是没有符合你所需要的特性。又或者是某个开源的解析器存在缺陷,要么是某个开源解析器的项目中止了,原因不一而足。不过无论原因是什么,总之事实就是你必须要自己去实现这个解析器。

XML和JSON解析

   在网络上传输数据时最常用的格式有两种:XML和JSON。本文主要就是学习如何对这两种常用的数据格式进行解析。

当你必需实现自己的解析器时,你会希望它有良好表现,灵活,功能丰富,易于使用,最后但更重要是易于实现,毕竟你的名字会出现在代码中。本文中,我将介绍一种用Java实现高性能解析器的方式。该方法不具排他性,它是简约的,并实现了高性能和合理的模块化设计。该设计灵感来源于VTD-XML
,我所见到的最快的java XML解析器,比StAX和SAX Java标准XML解析器更快。

当你必须自己实现一个解析器时,你对它的期望会有很多,包括性能良好、灵活、特性丰富、方便使用,以及便于维护等等。说到底,这也是你自己的代码。在本文中,我将为你介绍在Java中实现高性能解析器的一种方式,这种方法并且独一无二,但难度适中,不仅实现了高性能,而且它的模块化设计方式也比较合理。这种设计是受到了VTD-XML的设计方式的启发,后者是我所见过的最快的Java
XML解析器,比起StAX和SAX这两种标准的Java XML解析器都要快上许多。

1、XML和JSON的定义

  • XML扩展标记语言
    (Extensible Markup Language, XML)

    ,用于标记电子文件使其具有结构性的标记语言,可以用来标记数据、定义数据类型,是一种允许用户对自己的标记语言进行定义的源语言。
    XML使用DTD(document type
    definition)文档类型定义来组织数据
    ;格式统一,跨平台和语言,早已成为业界公认的标准。XML是标准通用标记语言
    (SGML) 的子集,非常适合 Web 传输。XML
    提供统一的方法来描述和交换独立于应用程序或供应商的结构化数据。

     1 <apps>
     2     <app>
     3         <id>1</id>
     4         <name>matlab</name>
     5         <version>12.5</version>
     6     </app>
     7     <app>
     8         <id>2</id>
     9         <name>chorme</name>
    10         <version>9.986</version>
    11     </app>
    12     <app>
    13         <id>3</id>
    14         <name>Google Maps</name>
    15         <version>10.4</version>
    16     </app>
    17 </apps>
    
  • JSONJavaScript Object
    Notation
    ,一种轻量级的数据交换格式,具有良好的可读和便于快速编写的特性。可在不同平台之间进行数据交换。JSON采用兼容性很高的、完全独立于语言文本格式,同时也具备类似于C语言的习惯(包括C,
    C++, C#, Java, JavaScript, Perl,
    Python等)体系的行为。这些特性使JSON成为理想的数据交换语言。JSON基于JavaScript
    Programming Language , Standard ECMA-262 3rd Edition – December 1999
    的一个子集。

    JSON就是一串字符串,只不过元素会使用特定的符号标注。

      {} 双括号表示对象

      [] 中括号表示数组

      ”” 双引号内是属性或值

      :
    冒号表示后者是前者的值(这个值可以是字符串、数字、也可以是另一个数组或对象)

    1 [{"id":"1","name":"matlab","version","12.5"}
    2 {"id":"2","name":"chorme","version","9.986"}
    3 {"id":"3","name":"Google Maps","version","10.4"}]    
    

两个基本解析器类型

解析器有多种分类方式。在这里,我只比较两个基本解析器类型的区别:

  • 顺序访问解析器(Sequential access parser)
  • 随机访问解析器(Random access parser)

顺序访问意思是解析器解析数据,解析完毕后将解析数据移交给数据处理器。数据处理器只访问当前已解析过的数据;它不能回头处理先前的数据和处理前面的数据。顺序访问解析器已经很常见,甚至作为基准解析器,SAX和StAX解析器就是最知名的例子。

随机访问解析器是可以在已解析的数据上或让数据处理代码向前和向后(随机访问)。随机访问解析器例子见XML
DOM解析器。

澳门新葡亰娱乐官网 1

顺序访问解析器只能让你在文档流中访问刚解析过的“窗口”或“事件”,而随机访问解析器允许你按照想要的方式访问遍历。

两种基本的解析器类型

为解析器进行分类的方式有好几种,在这里我将解析器分为两种基础类型:

  • 顺序访问解析器
  • 随机访问解析器

顺序访问是指解析器对进行数据进行解析,在数据解析完成后将其转交给数据处理器(processor)的过程。数据处理器只能访问当前正在进行解析的数据,它既不能访问已解析过的数据,也不能访问等待解析的数据。这种解析器也被称为基于事件的解析器,例如SAX和StAX解析器。

而随机访问解析器是指解析器允许数据处理代码可以随意访问正在进行解析的数据之前和之后的任意数据(随机访问)。这种解析器的例子有XML
DOM解析器。

下图展示了顺序访问解析器与随机访问解析器的不同之处:

澳门新葡亰娱乐官网 2

顺序访问解析器只能让你访问当前正在解析的“视窗”或“事件”,而随机访问解析器允许你任意地浏览所有已解析数据。

2、XML和JSON的优缺点

  • XML的优缺点

    • XML的优点
      1. 格式统一,符合标准;
      2. 容易与其他系统进行远程交互,数据共享比较方便。

    • XML的缺点
      1. XML文件庞大,文件格式复杂,传输占带宽;
      2. 服务器端和客户端解析XML花费较多的资源和时间。
      3. 服务器端和客户端都需要花费大量代码来解析XML,导致服务器端和客户端代码变得异常复杂且不易维护;
      4. 客户端不同浏览器之间解析XML的方式不一致,需要重复编写很多代码;
  • 两者对比:

    • 相同点
      1. 两者的数据可读性基本相同
      2. 两者拥有同样丰富的解析手段
    • 异同点
      1. json的数据体积更小
      2. json与JS的交互更加方便
      3. json的解析速度更快
      4. xml对数据的描述性更好

 

设计概要

我这里介绍的解析器设计属于随机访问变种。

随机访问解析器实现总是比顺序访问解析器慢一些,这是因为它们一般建立在某种已解析数据对象树上,数据处理器能访问上述数据。创建对象树实际上在CPU时钟上是慢的,并且耗费大量内存。

代替在解析数据上构建对象树,更高性能的方式是建立指向原始数据缓存的索引缓存。索引指向已解析数据的元素起始点和终点。代替通过对象树访问数据,数据处理代码直接在含有原始数据的缓存中访问已解析数据。如下是两种方法的示意图:

澳门新葡亰娱乐官网 3

因为没找到更好的名字,我就叫该解析器为“索引叠加解析器”。该解析器在原始数据上新建了一个索引叠加层。这个让人想起数据库构建存储在硬盘上的数据索引的方式。它在原始未处理的数据上创建了指针,让浏览和搜索数据更快。

如前所说,该设计受VTD-XML的启发, VTD是虚拟令牌描述符(Virtual Token
Descriptor)的英文缩写。因此,你可以叫它虚拟令牌描述符解析器。不过,我更喜欢索引叠加的命名,因为这是虚拟令牌描述符代表,在原始数据上的索引。

设计概况

我在这里所介绍的解析器设计属于随机访问解析器。

随机访问解析器的实现通常会慢于顺序访问解析器,因为它们一般都会为已解析数据创建某种对象树,数据处理代码将通过这棵树对数据进行访问。创建这种对象树不仅要花费较长的CPU时间,消耗的内存也很大。

相对于从已解析数据中创建一棵对象树的方式,另一种性能更佳的方式是为原来的数据缓冲区建立一个对应的索引缓冲区,这些索引会指向在已解析数据中找到的元素的起点与终点。数据处理代码此时不再通过对象树访问数据,而是直接在包括了原始数据的缓冲区中访问已解析数据。以下是对这两种处理方式的图示:

澳门新葡亰娱乐官网 4

由于我找不到一个更好的名字,因此我将这种方式简单地命名为“索引覆盖解析器”(Index
Overlay
Parser)。该解析器为原始数据创建了一个覆盖于其上的索引。这种方式让人联想起数据库索引将数据保存在磁盘的方式,它为原始的、未处理的数据创建了一个索引,以实现更快地浏览和搜索数据的目的。

如同我之前所说的,这种设计方式是受到了VTD-XML(VTD是指虚拟令牌描述符)的启发,因此你也可以把这种解析器称为虚拟令牌描述符解析器。但我还是倾向于索引覆盖这个名字,因为它表现了虚拟令牌描述符的本质,即对原始数据建立的索引。

3、XML和JSON的解析

  我们先整体上列一个思路,对于这两种数据格式的解析,每一种数据都有多种解析方法,本文对每一种数据都提供两种经常用到的两种方式:

  • XML格式解析Pull解析方式、SAX解析方式、DOM解析方式
    1. Pull解析方式:Pull解析器的运行方式与 SAX
      解析器相似。它提供了类似的事件,如:开始元素和结束元素事件,使用parser.next()可以进入下一个元素并触发相应事件。事件将作为数值代码被发送,因此可以使用一个switch对感兴趣的事件进行处理。当元素开始解析时,调用parser.nextText()方法可以获取下一个Text类型元素的值。

       1 private void parseXMLWithPull(String xmlData){
       2     try {
       3         //创建一个xml解析的工厂
       4         XmlPullParserFactory factory = XmlPullParserFactory.newInstance();
       5         //获得xml解析类的引用
       6         XmlPullParser xmlPullParser = factory.newPullParser();
       7         //以流的方式传入需要解析的xml数据
       8         xmlPullParser.setInput(new StringReader(xmlData));
       9         //获得事件的类型
      10         int eventType = xmlPullParser.getEventType();
      11         String id = "" ;
      12         String name = "" ;
      13         String version = "" ;
      14         //判断是否到了文档结束位置
      15         while(eventType != XmlPullParser.END_DOCUMENT){
      16             String nodeName = xmlPullParser.getName() ;
      17            switch(eventType){
      18              
      19               //遇到标签元素
      20               case XmlPullParser.START_TAG:
      21                  if("id".equals(nodeName)){
      22                     //取出属性值,0是代表第0个属性
      23                     id = xmlPullParser.nextText();
      24                  } else if("name".equals(nodeName)){
      25                     //获取该节点的内容 
      26                     name = xmlPullParser.nextText();
      27                  }else if("version".equals(nodeName)){
      28                     //获取该节点的内容 
      29                     version = xmlPullParser.nextText();
      30                  }
      31                  break; 
      32               //标签结束
      33               case XmlPullParser.END_TAG:
      34                   if("app".equals(xmlPullParser.getName())){
      35                      //这里可以做一些初始化,或者log记录
      36                       Log.d("MainAvtivity", "id is" + id) ;
      37                       Log.d("MainAvtivity", "name is" + name) ;
      38                       Log.d("MainAvtivity", "version is" + version) ;
      39                   }
      40                  break;
      41               default:
      42                   break ;
      43            }
      44             //循环
      45             eventType = xmlPullParser.next();
      46         } 
      47     } catch (Exception e) {
      48         // TODO Auto-generated catch block
      49         e.printStackTrace();
      50     }
      51 }
      
    2. SAX解析方式:Simple API
      for
      XML,SAX是一个解析速度快并且占用内存少的xml解析器,非常适合用于
      Android等移动设备。 SAX解析XML文件采用的是事件驱动,也就是说,它并不需要解析完整个文档,在按内容顺序解析文档的过程中,SAX会判断当前读到的字符是否合法XML
      语法中的某部分,如果符合就会触发事件。所谓事件,其实就是一些回调(callback)方法,这些方法(事件)定义在ContentHandler接口。

       1 private void parseXMLWithSAX(String xmlData){
       2     try {
       3         //第一步:新建一个工厂类SAXParserFactory,并获取其实例
       4         SAXParserFactory factory = SAXParserFactory.newInstance();
       5         //第二步:让工厂类产生一个SAX的解析类SAXParser的对象
       6         SAXParser parser = factory.newSAXParser();
       7         //第三步:从SAXPsrser中得到一个XMLReader实例
       8         XMLReader xmlReader = parser.getXMLReader();
       9         //第四步:把自己写的handler注册到XMLReader中,一般最重要的就是ContentHandler
      10         MySaxHandler handler = new MySaxHandler() ;
      11         xmlReader.setContentHandler(handler);
      12         //第五步:将一个xml文档或者资源变成一个java可以处理的InputStream流后,解析正式开始
      13         xmlReader.parse(new InputSource(new StringReader(xmlData)));
      14     } catch (Exception e) {
      15         // TODO Auto-generated catch block
      16         e.printStackTrace();
      17     }
      18 }
      

       最重要、最关键的就是第四步,handler的实现。下面是其实现的代码:

       1 /*
       2  * 实现一个ContentHandler一般要一下几个步骤:
       3  * 
       4  * 1、声明一个类,继承DefaultHandler。DefaultHandler是一个基类,这个类里面简单实现了
       5  *    一个ContentHandler。我们只需要重写里面的方法即可。
       6  * 2、重写 startDocument() 和 endDocument(),一般解析将正式解析之前的一些初始化工资放
       7  *    到startDocument()里面,收尾的工作放到endDocument()里面。
       8  * 3、重写startElement(),XML解析器遇到XML里面的tag时就会调用这个函数。经常在这个函数内是
       9  *    通过localName俩进行判断而操作一些数据。
      10  * 4、重写characters()方法,这是一个回调方法。解析器执行完startElement()后,解析完节点的内
      11  *    容后就会执行这个方法,并且参数ch[]就是节点的内容。这个例子里我们根据currentstate的不同,来
      12  *    判断当前那个tag的内容,并放到合适的实体类中。
      13  * 5、重写endElement()方法,这个方法与startElement()相对应,解析完一个tag节点后,执行这个方法。
      14  *    再找个例子中,如果解析一个item结束,就将RSSIiem添加到RSSFeed中。
      15  *    
      16  */
      17 class MySaxHandler extends DefaultHandler{
      18     
      19     private String nodeName ;
      20     private StringBuilder id ;
      21     private StringBuilder name ;
      22     private StringBuilder version ;
      23     
      24     /**
      25      * 当SAX解析器解析到XML文档开始时,会调用的方法
      26      */
      27     @Override
      28     public void startDocument() throws SAXException {
      29         id = new StringBuilder() ;
      30         name = new StringBuilder() ;
      31         version = new StringBuilder() ;
      32     }
      33     
      34     /**
      35      * 当SAX解析器解析到XML文档结束时,会调用的方法
      36      */
      37     @Override
      38     public void endDocument() throws SAXException {
      39         super.endDocument();
      40     }
      41     
      42     /**
      43      * 当SAX解析器解析到某个属性值时,会调用的方法
      44      * 其中参数ch记录了这个属性值的内容
      45      */
      46     @Override
      47     public void characters(char[] ch, int start, int length)throws SAXException {
      48         //根据当前的节点名判断将内容添加到哪一个StringBuilder上
      49         if("id".equals(nodeName)){
      50             id.append(ch, start, length) ;
      51         }else if("name".equals(nodeName)){
      52             name.append(ch, start, length) ;
      53         }else if("version".equals(nodeName)){
      54             version.append(ch, start, length) ;
      55         }
      56     }
      57     
      58     /**
      59      * 当SAX解析器解析到某个元素开始时,会调用的方法
      60      * 其中localName记录的是元素属性名
      61      */
      62     @Override
      63     public void startElement(String uri, String localName, String qName,
      64             Attributes attributes) throws SAXException {
      65         nodeName = localName ;
      66     }
      67     
      68     /**
      69      * 当SAX解析器解析到某个元素结束时,会调用的方法
      70      * 其中localName记录的是元素属性名
      71      */
      72     @Override
      73     public void endElement(String uri, String localName, String qName)
      74             throws SAXException {
      75         if("app".equals(localName)){
      76             //这里可以做一些初始化,或者log记录
      77              Log.d("MainAvtivity", "id is" + id) ;
      78              Log.d("MainAvtivity", "name is" + name) ;
      79              Log.d("MainAvtivity", "version is" + version) ;
      80          }
      81     }
      82 }
      

       

    3. DOM解析方式: DOM解析XML文件时,会将XML文件的所有内容读取到内存中,然后允许您使用DOM
      API遍历XML树、检索所需的数据。使用DOM操作XML的代码看起来比较直观,并且,在某些方面比基于SAX的实现更加简单。但是,因为DOM需要将
      XML文件的所有内容读取到内存中,所以内存的消耗比较大,特别对于运行Android的移动设备来说,因为设备的资源比较宝贵,所以建议还是采用SAX
      来解析XML文件,当然,如果XML文件的内容比较小采用DOM是可行的。(不适合Android移动设备)

  • JSON格式解析:使用JsonObject解析和使用GSON解析。可以参考:Android学习笔记45:JSON数据解析(GSON方式)
    1. 使用JsonObject解析:可以看作是一个json对象,这是系统中有关JSON定义的基本单元,其包含一对(Key/Value)数值。它对外部(External:应用toString()方法输出的数值)调用的响应体现为一个标准的字符串(例如:{“JSON”:
      “Hello,
      World”},最外被大括号包裹,其中的Key和Value被冒号”:”分隔)。其对于内部(Internal)行为的操作格式略微,例如:初始化一个JSONObject实例,引用内部的put()方法添加数值:new
      JSONObject().put(“JSON”, “Hello,
      World!”),在Key和Value之间是以逗号”,”分隔。Value的类型包括:Boolean、JSONArray、JSONObject、Number、String或者默认值JSONObject.NULL
      object。

       1 private void parseJSONWithJSONObject(String jsonData){
       2     try {
       3         JSONArray jsonArray = new JSONArray(jsonData);
       4         for (int i = 0; i < jsonArray.length(); i++) {
       5             JSONObject jsonObject = jsonArray.getJSONObject(i);
       6             String id = jsonObject.getString("id");
       7             String name = jsonObject.getString("name");
       8             String version = jsonObject.getString("version");
       9 
      10             // 解析完之后对这些数据进行处理,这里我们只是Log输出
      11             Log.d("MainAvtivity", "id is" + id);
      12             Log.d("MainAvtivity", "name is" + name);
      13             Log.d("MainAvtivity", "version is" + version);
      14         }
      15     } catch (Exception e) {
      16         e.printStackTrace();
      17     }
      18 }
      
    2. 使用GSON解析:要创建和解析JSON数据,也可以使用GSON来完成。GSON是Google提供的用来在Java对象和JSON数据之间进行映射的Java类库。使用GSON,可以很容易的将一串JSON数据转换为一个Java对象,或是将一个Java对象转换为相应的JSON数据。之一,GSON是谷歌的开源库,并没有被添加到Android官方的API中,因此要使用这个功能,我们需要在项目中添加一个GSON的jar包。
      在GSON的API中,提供了两个重要的方法:String toJson()和<T>
      fromJson()方法。其中,toJson()方法用来实现将Java对象转换为相应的JSON数据,以字符串形式返回,fromJson()方法则用来实现将JSON数据转换为相应的Java对象。所以,我们在解析JSON数据时,可以直接通过使用前面提到的fromJson()方法将JSON数据(实际上是字符串类型)转化为我们所想要的一种类型,因此,我们一般需要自定义一个相关的类来将我们需要的数据进行封装,方面我们通过fromJson()方法返回获得。这里我们将一个对象的数据封装成App类。

       1 private void parseJSONWithGson(String jsonData){
       2     Gson gson= new Gson() ;
       3     //我们借助TypeTolen将期望解析成的数据类型传入到fromJson()方法中
       4     List<App> appList = gson.fromJson(jsonData, new TypeToken<List<App>>(){}.getType()) ;
       5     for(App app:appList){
       6         // 解析完之后对这些数据进行处理,这里我们只是Log输出
       7         Log.d("MainAvtivity", "id is" + app.getId());
       8         Log.d("MainAvtivity", "name is" +app.getName());
       9         Log.d("MainAvtivity", "version is" + app.getVersion());
      10     }
      11 }
      
       1 /*
       2  * 我们将一个JSON对象({}之间表示一个对象)封装成App类
       3  */
       4 class App{
       5     String id ;
       6     String name ;
       7     String version ;
       8     public String getId() {
       9         return id;
      10     }
      11     public void setId(String id) {
      12         this.id = id;
      13     }
      14     public String getName() {
      15         return name;
      16     }
      17     public void setName(String name) {
      18         this.name = name;
      19     }
      20     public String getVersion() {
      21         return version;
      22     }
      23     public void setVersion(String version) {
      24         this.version = version;
      25     }    
      26 }
      
    3. FastJSON:不详细解释。 

       

常规解析器设计

一般解析器设计会将解析过程分为两步。第一步将数据分解为内聚的令牌,令牌是一个或多个已解析数据的字节或字符。第二步解释这些令牌并基于这些令牌构建更大的元素。两步示意图如下:

澳门新葡亰娱乐官网 5

图中元素并不是指XML元素(尽管XML元素也解析元素),而更大“数据元素”构造了已解析数据。在我XML文档中表示XML元素,而在JSON
文档中则表示JSON对象,诸如此类。

举例说明,字符串将被分解为如下令牌:

<
myelement
>

一旦数据分解为多个令牌,解析器更容易理解它们和判断这些令牌构造的大元素。解析器将会识别XML元素以
‘<’令牌开头后面是字符串令牌(元素名称),然后是一系列可选的属性,最后是‘>’令牌。

解析器设计概要

一种常规的解析器设计方式将解析过程分为两步。第一步是将数据分解为内聚的令牌,一个令牌是已解析数据中的一个或多个字节或字符。第二步是对令牌进行解释,并根据这些令牌构建更大的元素。以下是这两个步骤的图示:

澳门新葡亰娱乐官网 6

这里的元素并不一定是指XML元素(虽然XML元素也是解析器元素),而是指构成解析数据的更大的“数据元素”。比如说,在一个XML文档中元素代表了XML元素,而在一个JSON文档中元素则代表了JSON对象,等等。

举例来说,<myelement>这个字符串可以被分解为以下几个令牌:

  • <
  • myelement
  • >

一旦数据被分解为令牌,解析器就能够相对容易地了解它的意义,并且决定这些令牌构成的更大的元素。解析器就能够理解一个XML元素是由一个’<’令牌开始,随后是一个字符串(即元素名称),随后有可能是一些属性,最后以一个’>’令牌结尾。

索引叠加解析器设计

两步方法也将用于我们的解析器设计。输入数据首先由分析器组件分解为多个令牌。
然后解析器解析这些令牌识别输入数据的大元素边界。

你也可以增加可选的第三步骤—“元素导航步骤”到解析过程中。
若解析器从已解析数据中构造对象树,那么对象树一般会包含对象树导航的链接。当我们构建元素索引缓存代替对象树时,我们需要一个独立组件帮助数据处理代码导航元素索引缓存。

我们解析器设计概览参见如下示意图:

澳门新葡亰娱乐官网 7

我们首先将所有数据读到数据缓存内。为了保证可以通过解析中创建的索引随机访问原始数据,所有原始数据必需放到内存中。

接着,分析器将数据分解为多个令牌。开始索引,结束索引和令牌类型都会保存于分析器中一个内部令牌缓存。使用令牌缓存使其向前和向后访问成为可能,上述情况下解析器需要令牌缓存。

第三步,解析器查找从分析器获取的令牌,在上下文中校验它们,并判断它们表示的元素。然后,解析器基于分析器获取的令牌构造元素索引(索引叠加)。解析器逐一获得来自分析器的令牌。因此,分析器实际上不需要马上将所有数据分解成令牌。而仅仅是在特定时间点找到一个令牌。

数据处理代码能访问元素缓存,并用它访问原始数据。或者,你可能会将数据缓存封装到元素访问组件中,让访问元素缓存更容易。

该设计基于已解析数据构建对象树,但它需建立访问结构—元素缓存,由索引(整型数组)指向含有原始数据的数据缓存。我们能使用这些索引访问存于原始数据缓存的数据。

下面小节将从设计的不同方面更详细地进行介绍。

索引覆盖解析器设计

在这种解析器的设计方式中也包含了两个步骤:输入数据首先被一个令牌生成器(tokenizer)组件分解为令牌,解析器随后将对令牌进行解析,以决定输入数据的一个更大的元素边界。

你也可以为解析过程加入一个可选的“元素浏览步骤”。如果解析器从解析数据中构建出一棵对象树,它通常会包含在整棵树中进行浏览的链接。如果我们不选择对象树,而是构建出一个元素索引缓冲区,我们也许需要另一个组件以帮助数据处理代码在元素索引缓冲区中进行浏览。

以下是我们的解析器设计的概要:

澳门新葡亰娱乐官网 8

我们首先将所有数据读入一个数据缓冲区中,为了能够通过在解析过程中创建的索引对原始数据进行随机访问,所有的原始数据必须已经存在于内存中。

第二步,令牌生成器会将数据分解为令牌。令牌生成器内部的某个令牌缓冲区会将该令牌的起点索引、终点索引和令牌类型都保留下来。使用令牌缓冲区使你能够查找之前或之后的令牌,在这种设计中解析器会利用到这一项特性。

第三步,解析器获取了令牌生成器所产生的令牌,根据上下文对其进行验证,并决定它所表示的元素。随后解析器会根据从令牌生成器处获取的令牌构建一个元素索引(即索引覆盖)。解析器会从令牌生成器中一个接一个地获取令牌。因此令牌生成器不必立即将所有数据都分解为令牌,它只需要每次找到一个令牌就行了。

数据处理代码将浏览整个元素缓冲区,利用它访问原始数据。你也可以选择用一个元素浏览组件将元素缓冲区包装起来,使浏览元素缓冲区的工作更加简单。

这种设计不会从解析数据中生成一棵对象树,但它确实生成了一个可浏览的结构,即元素缓冲区,索引(即整数数组)将指向包含了原始数据的数据缓冲区。你可以使用这些索引浏览原始数据缓冲区中的所有数据。

本文的以下部分将分析这种设计的各方面细节。

数据缓存

数据缓存是含有原始数据的一种字节或字符缓存。令牌缓存和元素缓存持有数据缓存的索引。

为了随机访问解析过了的数据,内存表示上述信息的机制是必要的。我们不使用对象树而是用包含原始数据的数据缓存。

将所有数据放在内存中需消耗大块的内存。若数据含有的元素是相互独立的,如日志记录,将整个日志文件放在内存中将是矫枉过正了。相反,你可以拉大块的日志文件,该文件存有完整的日志记录。因为每个日志记录可完全解析,并且独立于其它日志记录的处理,所以我们不需要在同一时间将整个日志文件放到内存中。在我的文章—“使用缓存迭代访问数据流”中,我已经描述了如何遍历块中的数据流。

数据缓冲区

数据缓冲区是一个包括了原始数据的字节字符缓冲区,而令牌缓冲区和元素缓冲区则包含了指向数据缓冲区的索引。

为了实现对解析数据的随机访问,必须以某种形式将它保留在内存中。我们在这里没有选择对象树,而是选择了包含未处理数据本身的数据缓冲区。

将所有数据全部保留在内存中可能会导致对内存的大量消耗。如果你的数据包含了互相独立的元素,例如日志记录,那么将整个日志文件导入内存很可能会造成崩溃。你应该采取的方式是只导入日志文件的一部分,其中至少包含一条完整的日志记录。由于每一条日志记录都可以不依赖于其它日志记录进行解析和处理,你就不需要将整个日志文件在同一时刻加载到内存里了。我在我的文章《使用缓冲区对流进行迭代处理》中描述了如何对一块数据流进行迭代的方式。

标记分析器和标记缓存

分析器将数据缓分解为多个令牌。令牌信息存储在令牌缓存中,包含如下内容:

  • 令牌定位(起始索引)
  • 令牌长度
  • 令牌类型 (可选)

上述信息放在数组中。如下实例说明处理逻辑:

public class IndexBuffer {
    public int[] position = null;
    public int[] length = null;
    public byte[] type = null; 
/* assuming a max of 256 types (1 byte / type) */
}

当分析器找到数据缓存中令牌时,它将构建位置数组的起始索引位置,长度数组的令牌长度和类型数组的令牌类型。

若不使用可选的令牌类型数组,你仍能通过查看令牌数据来区分令牌类型。这是性能和内存消耗的权衡。

令牌生成器与令牌缓冲区

令牌生成器将数据缓冲区分解为令牌,令牌的信息会保存在令牌缓冲区中,包括以下信息:

  • 令牌的位置(起始位置的索引)
  • 令牌长度
  • 令牌类型(可选信息)

以上信息都保存在数组中,这里是一段示例代码:

   public class IndexBuffer {
       public int[]  position = null;
       public int[]  length   = null;
       public byte[] type     = null; 
     /* assuming a max of 256 types (1 byte / type) */
   }

当令牌生成器在数据缓冲区中找到令牌之后,它会将该位置(起始位置的索引)插入position数组、将令牌长度插入length数组,并将令牌类型插入type数组。

如果你不使用这个可选的令牌类型数组,你也可以在需要的时候通过令牌中的数据得出令牌的类型。这是一种性能与内存占用之间的权衡。

解析器

解析器是在性质上与分析器类似,只不过它采用令牌作为输入和输出的元素索引。如同使用令牌,一个元素由它的位置(起始索引),长度,以及可选的元素类型来决定。这些数字存储在与存储令牌相同的结构中。

再者,类型数组是可选的。若你很容易基于元素的第一个字节或字符确定元素类型,你不必存储元素类型。

元素缓存中标记的要素精确粒度取决于数据被解析,以及需要后面数据处理的代码。例如,如果你实现一个XML解析器,你可能会标记为每个“解析器元素”的开始标签,
属性和结束标签。

解析器

解析器本质上与令牌生成器非常类似,不同的是它将令牌作为输入,而将元素索引作为输出。和令牌类似,每个元素由它的位置(起始位置的索引)、长度和可选的元素类型几部分组成。用以保存这些数字的结构与保存令牌的结构是完全一样的。

在这里type数组仍然是可选的。如果你能够从元素的首个字节或字符中很容易地判断元素的类型,那就无需特意保存元素的类型信息。

在元素缓冲区中所包含的元素的精确粒度取决于被解析的数据,以及之后将对数据进行处理的代码段。举例来说,如果你要实现一个XML解析器,你可能会选择将每个开始标签、属性和结束标签作为独立的“解析元素”。

元素缓存(索引)

解析器生成带有指向元数据的索引的元素缓存。该索引标记解析器从数据中获取的元素的位置(起始索引),长度和类型。你可以使用这些索引来访问原始数据。

看一看上文的IndexBuffer代码,你就知道元素缓存每个元素使用9字节;四个字节标记位置,四个自己是令牌长度,一个字节是令牌类型。

你可以减少IndexBuffer
的内存消耗。例如,如果你知道元素从不会超过65,536字节,那么你可以用短整型数组代替整型来存令牌长度。这将每个元素节省两个字节,使内存消耗降低为每个元素7个字节。

此外,如果知道将解析这些文件长度从不会超过16,777,216字节,你只需要三个字节标识位置(起始索引)。在位置数组中,每一整型第四字节可以保存元素类型,省去了一个类型数组。如果您有少于128的令牌类型,您可以使用7位的令牌类型而不是八个。这使您可以花25位在位置上,这增加了位置范围最大到33,554,432。如果您令牌类型少于64,您可以安排另一个位给位置,诸如此类。

VTD-XML实际上会将所有这些信息压缩成一个Long型,以节省空间。处理速度会有损失,因为额外的位操作收拾单独字段到单个整型或long型中,不过你可以节省一些内存。总而言之,这是一个权衡。

元素缓冲区(索引)

解析器所生成的元素缓冲区包含了引向原始数据的索引。这些索引会记录解析器在数据中所找到的元素的位置(起始位置的索引)、长度和类型信息。你可以利用这些索引实现在原始数据的任意浏览。

从之前的IndexBuffer代码段中,你可以看到元素缓冲区为每个元素保留了9个字节的缓冲区,4个字节用于保存位置、另4个字节用于保存令牌长度,最后1个字节用于保存令牌类型。

你或许能够通过某些手段来减少IndexBuffer的内存占用。举例来说,如果你确认其中的元素不超过65535个字节,你就可以选择使用short短整数,而不是常规的int整数来保存令牌长度信息,这样每个元素都可以节省两个字节,将整个内存占用减少至每个元素七个字节。

此外,如果你确认被解析文件的大小不会超过16,777,216个字节,那你只需要三个字节来保存位置信息(起始位置的索引)。那么在position数组中的每个整数的第四个字节就可以用来保存元素类型,这样就可以完全不用使用单独的type数组了。如果你的令牌类型不超过128种,你就可以使用七个字节、而不是八个字节来保存令牌类型,这样一来你就可以使用25个比特来保存位置,使得最大的位置可以达到33,554,432。如果你的令牌类型少于64种,你还可以空出一个比特以保存位置信息。

VTD-XML实际上将所有这些信息都保存在一个长整数类型中,以达到节省空间的目的。为了将几个分离的字段加载成为一个单独的整数或者长整数,需要进行一些比特操作,也因此会降低一些速度,但好处是节省了部分内存,这就是一种资源的权衡。

元素导航组件

元素导航组件帮助正在处理数据的代码访问元素缓存。务必记住,一个语义对象或元素(如XML元素)可能包括多个解析器元素。为了方便访问,您可以创建一个元素导航器对象,可以在语义对象级别访问解析器元素。例如,一个XML元素导航器组件可以通过在起始标记和到起始标记来访问元素缓存。

使用元素导航组件是你的自由。如果要实现一个解析器在单个项目中的使用,你可以要跳过它。但是,如果你正在跨项目中重用它,或作为开源项目发布它,你可能需要添加一个元素导航组件,这取决于如何访问已解析数据的复杂度。

元素Navigator

元素navigator可以帮助处理数据的代码在元素缓冲区中对数据任意浏览。请记住一个语义化的对象或元素(例如一个XML元素)或许会包含多个解析器元素。为了简化浏览的实现,你可以创建一个元素navigator对象,让它负责在语义化对象级别对解析器元素进行浏览的操作。举例来说,XML元素navigator可以通过在开始标签之间跳转的方式实现对元素缓冲区的浏览。

是否使用元素navigator组件由你自行选择,如果你只需要为某个单一的项目的某一个功能实现解析器,你也可以选择不使用这种方式。但如果你希望实现的解析器能够在多个项目中重用,或者是将它发布为开源代码,你或许需要添加一个元素navigator组件,这取决于对解析数据的浏览的复杂度有多高。

案例学习:一个JSON解析器

为了让索引叠加解析器设计更清晰,我基于索引叠加解析器设计用Java实现了一个小的JSON解析器。你可以在GitHub上找到完整的代码。

JSON是JavaScript Object
Notation的简写。JSON是一种流行的数据格式,基于AJAX来交换Web服务器和浏览器之间的数据,Web浏览器已经内置了JSON解析为JavaScript对象的原生支持。后文,我将假定您熟悉JSON。

如下是一个JSON简单示例:

{ "key1" : "value1" , "key2" : "value2" , [ "valueA" , "valueB" , "valueC" ] }

JSON分析器将JSON字符串分解为如下令牌:

澳门新葡亰娱乐官网 9

这里下划线用于强调每个令牌的长度。

分析器也能判断每个令牌的基本类型。如下是同一个JSON示例,只是增加了令牌类型:

澳门新葡亰娱乐官网 10

注意令牌类型不是语义化的。它们只是说明基本令牌类型,而不是它们代表什么。

解析器解释基本令牌类型,并使用语义化类型来替换它们。如下示例是同一个JSON示例,只是由语义化类型(解析器元素)代替:

澳门新葡亰娱乐官网 11

一旦解析器完成了上述JSON解析,你将有一个索引,包含上面打标记元素的位置,长度和元素类型。你可以访问索引从JSON抽取你需要的数据。

在GitHub库中的实现包含两个JSON解析器。其中一个分割解析过程为JsonTokenizer和JsonParser(如本文前面所述),以及一个为JsonParser2结合分析和解析过程为一个阶段,一个类。JsonParser2速度更快,但更难理解。因此,我会在下面的章节快速介绍一下在JsonTokenizer和JsonParser类,但会跳过JsonParser2。

(本文第一个版本有读者指出,从该指数叠加分析器的输出是不是难于从原始数据缓冲区中提取数据。正如前面提到的,这就是添加一个元素导航组件的原因。为了说明这样的元素导航组件的原理,我已经添加了JsonNavigator类。稍后,我们也将快速浏览一下这个类。)

案例学习:一个JSON解析器

为了让索引覆盖解析器的设计更为直观,我自己实现了一个基于Java的小型JSON解析器,它遵循了索引覆盖解析器设计的方式,你可以在GitHub上找到它的完整代码。

JSON是JavaScript对象表示法的简称,它是在web服务端和客户端浏览器之间通过AJAX进行数据交换的一种常见数据格式,这是因为web浏览器内置了将JSON转换为JavaScript对象的原生支持。以下篇章中我会假设你已经熟悉JSON格式了。

这里有一个简单的JSON示例:

  {"key1":"value1","key2":"value2",["valueA":"valueB":"valueC"]}

JSON令牌生成器将JSON字符串分别为以下令牌:

澳门新葡亰娱乐官网 12

这里的下划线强调了每个令牌的长度。

令牌生成器还将决定每个令牌的基本类型,以下的JSON示例与之前的相同,只是加入了令牌的类型信息:

澳门新葡亰娱乐官网 13

请注意这里的令牌类型并非语义化,它只是说明了令牌的基本类型是什么,而并没有体现出这些令牌包含了什么内容。

解析器会分析出基本的令牌类型,并将它们替换为语义化的类型。这里是一个相同的JSON示例,但使用了语义化的类型(即解析器元素):

澳门新葡亰娱乐官网 14

当解析器完成了对该JSON对象的解析之后,你将获得一个索引(即元素缓冲区),它由图中所标注的元素的位置、长度和元素类型信息所组成。接下来你就可以对该索引进行浏览,以找出该JSON对象中你所需的数据。

JsonTokenizer.parseToken()方法

为了介绍分析和解析过程实现原理,我们看一下JsonTokenizer 和JsonParser
类的核心代码部分。提醒,完整代码可以在GitHub 访问 。

如下是JsonTokenizer.parseToken()方法,解析数据缓存的下一个索引:

public void parseToken() {
       skipWhiteSpace();
       this.tokenBuffer.position[this.tokenIndex] = this.dataPosition;
       switch (this.dataBuffer.data[this.dataPosition]) {
         case '{': {
           this.tokenBuffer.type[this.tokenIndex] = TokenTypes.JSON_CURLY_BRACKET_LEFT;
         }
         break;
         case '}': {
           this.tokenBuffer.type[this.tokenIndex] = TokenTypes.JSON_CURLY_BRACKET_RIGHT;
         }
         break;
         case '[': {
           this.tokenBuffer.type[this.tokenIndex] = TokenTypes.JSON_SQUARE_BRACKET_LEFT;
         }
         break;
         case ']': {
           this.tokenBuffer.type[this.tokenIndex] = TokenTypes.JSON_SQUARE_BRACKET_RIGHT;
         }
         break;
         case ',': {
           this.tokenBuffer.type[this.tokenIndex] = TokenTypes.JSON_COMMA;
         }
         break;
         case ':': {
           this.tokenBuffer.type[this.tokenIndex] = TokenTypes.JSON_COLON;
         }
         break;
         case '"': { parseStringToken(); } break;
         case '0':
         case '1':
         case '2':
         case '3':
         case '4':
         case '5':
         case '6':
         case '7':
         case '8':
         case '9': {
           parseNumberToken();
           this.tokenBuffer.type[this.tokenIndex] = TokenTypes.JSON_NUMBER_TOKEN;
         }
         break;
         case 'f': {
           if (parseFalse()) {
             this.tokenBuffer.type[this.tokenIndex] = TokenTypes.JSON_BOOLEAN_TOKEN;
           }
         }
         break;
         case 't': {
           if (parseTrue()) {
               this.tokenBuffer.type[this.tokenIndex] = TokenTypes.JSON_BOOLEAN_TOKEN;
           }
         }
         break;
         case 'n': {
           if (parseNull()) {
             this.tokenBuffer.type[this.tokenIndex] = TokenTypes.JSON_NULL_TOKEN;
           }
         }
         break;
        }
        this.tokenBuffer.length[this.tokenIndex] = this.tokenLength;
     }

如你所见,代码相当简洁。首先,skipWhiteSpace()调用跳过存在于当前位置的数据中的空格。接着,当前令牌(数据缓存的索引)的位置存于tokenBuffer
。第三,检查下一个字符,并根据字符是什么(它是什么样令牌)来执行switch-case
结构。最后,保存当前令牌的令牌长度。

这的确是分析一个数据缓冲区的完整过程。请注意,一旦一个字符串索引开始被发现,该分析器调用parseStringToken()方法,通过扫描的数据,直到字符串令牌结尾。这比试图处理parseToken()方法内所有逻辑执行更快,也更容易实现。

JsonTokenizer
内方法的其余部分只是辅助parseToken()方法,或者移动数据位置(索引)到下一个令牌(当前令牌的第一个位置),诸如此类。

JsonTokenizer.parseToken()

为了让你了解令牌生成器和解析工作是如何实现的,我会为你展示JsonTokenizer和JsonParser中的核心代码。请记得去Github下载完整的代码。

以下是JsonTokenizer.parseToken()方法的实现,它将负责解析数据缓冲区中的下一个令牌:

public void parseToken() {
     skipWhiteSpace();
     this.tokenLength = 0;

     this.tokenBuffer.position[this.tokenIndex] = this.dataPosition;
     char nextChar = this.dataBuffer.data[this.dataPosition];

     switch(nextChar) {
     case '{'   :
           this.tokenLength = 1;
           this.tokenBuffer.type[this.tokenIndex] = 
TokenTypes.JSON_CURLY_BRACKET_LEFT;
           break;
     case '}'   :  
           this.tokenLength = 1;
           this.tokenBuffer.type[this.tokenIndex] = 
TokenTypes.JSON_CURLY_BRACKET_RIGHT;
           break;
     case '['   :
           this.tokenLength = 1;
           this.tokenBuffer.type[this.tokenIndex] = 
TokenTypes.JSON_SQUARE_BRACKET_LEFT ;
           break;
     case ']'   : 
           this.tokenLength = 1;
           this.tokenBuffer.type[this.tokenIndex] = 
TokenTypes.JSON_SQUARE_BRACKET_RIGHT;
           break;
     case ','   :
           this.tokenLength = 1;
           this.tokenBuffer.type[this.tokenIndex] = TokenTypes.JSON_COMMA;
           break;
     case ':'   :  
           this.tokenLength = 1;
           this.tokenBuffer.type[this.tokenIndex] = TokenTypes.JSON_COLON;
           break;
     case '"'   :
           parseStringToken();
           this.tokenBuffer.type[this.tokenIndex] = TokenTypes.JSON_STRING_TOKEN;
           break;
     default    : 
           parseStringToken();
           this.tokenBuffer.type[this.tokenIndex] = TokenTypes.JSON_STRING_TOKEN;
     }
     this.tokenBuffer.length[this.tokenIndex] = this.tokenLength;
  }

如你所见,这部分代码非常简单。我们第一步首先调用skipWhiteSpace()方法,它将忽略当前位置的数据中的空格字符。第二步是将令牌长度设为0。第三步,将当前令牌的位置(数据缓冲区中的相对位置)保存在TokenBuffer中。第四步,对下一个字符进行分析,根据字符种类(即令牌种类)的不同,将执行switch—case结构中的某条语句。最后,将当前令牌的长度保存起来。

以上就是为数据缓冲区生成令牌的全部工作了,请注意,当找到了某个字符串令牌的开头部分之后,令牌生成器就会调用parseStringToken()方法,它会对数据进行完整的扫描,直到找到了该字符串令牌的结束为止。这种方式比起在parseToken()方法中进行各种条件判断并处理各种不同情况执行得会更快,而且实现也更加容易。

JsonTokenizer中其余的方法都是parseToken()的辅助方法,或者是将数据的位置移至下一个令牌(即当前令牌之后的第一个位置),等等。

JsonParser.parseObject()方法

JsonParser类主要的方法是parseObject()方法,它主要处理从JsonTokenizer得到令牌的类型,并试图根据上述类型的输入数据找到JSON对象中。

如下是parseObject() 方法:

private void parseObject(JsonTokenizer tokenizer) {
       assertHasMoreTokens(tokenizer);
       tokenizer.parseToken();
       assertThisTokenType(tokenizer.tokenType(), TokenTypes.JSON_CURLY_BRACKET_LEFT);
       setElementData(tokenizer, ElementTypes.JSON_OBJECT_START);
       tokenizer.nextToken();
       tokenizer.parseToken();
       byte tokenType = tokenizer.tokenType();
       while (tokenType != TokenTypes.JSON_CURLY_BRACKET_RIGHT) {
          assertThisTokenType(tokenType, TokenTypes.JSON_STRING_TOKEN);
          setElementData(tokenizer, ElementTypes.JSON_PROPERTY_NAME);
          tokenizer.nextToken();
          tokenizer.parseToken();
          tokenType = tokenizer.tokenType();
          assertThisTokenType(tokenType, TokenTypes.JSON_COLON);
          tokenizer.nextToken();
          tokenizer.parseToken();
          tokenType = tokenizer.tokenType();
          switch (tokenType) {
             case TokenTypes.JSON_STRING_TOKEN: {
               setElementData(tokenizer, ElementTypes.JSON_PROPERTY_VALUE_STRING);
             }
             break;
             case TokenTypes.JSON_STRING_ENC_TOKEN: {
               setElementData(tokenizer, ElementTypes.JSON_PROPERTY_VALUE_STRING_ENC);
             }
             break;
             case TokenTypes.JSON_NUMBER_TOKEN: {
               setElementData(tokenizer, ElementTypes.JSON_PROPERTY_VALUE_NUMBER);
             }
             break;
             case TokenTypes.JSON_BOOLEAN_TOKEN: {
               setElementData(tokenizer, ElementTypes.JSON_PROPERTY_VALUE_BOOLEAN);
             }
             break;
             case TokenTypes.JSON_NULL_TOKEN: {
               setElementData(tokenizer, ElementTypes.JSON_PROPERTY_VALUE_NULL);
             }
             break;
             case TokenTypes.JSON_CURLY_BRACKET_LEFT: {
               parseObject(tokenizer);
             }
             break;
             case TokenTypes.JSON_SQUARE_BRACKET_LEFT: {
               parseArray(tokenizer);
             }
             break;
          }
          tokenizer.nextToken();
          tokenizer.parseToken();
          tokenType = tokenizer.tokenType();
          if (tokenType == TokenTypes.JSON_COMMA) {
             tokenizer.nextToken(); //skip , tokens if found here.
             tokenizer.parseToken();
             tokenType = tokenizer.tokenType();
          }
       }
       setElementData(tokenizer, ElementTypes.JSON_OBJECT_END); } 
     }

parseObject()方法希望看到一个左花括号({),后跟一个字符串标记,一个冒号和另一个字符串令牌或数组的开头([])或另一个JSON对象。当JsonParser从JsonTokenizer获取这些令牌时,它存储开始,长度和这些令牌在自己elementBuffer中的语义。然后,数据处理代码可以浏览这个elementBuffer后,从输入数据中提取任何需要的数据。

看过JsonTokenizer和JsonParser类的核心部分后能让我们理解分析和解析的工作方式。为了充分理解代码是如何运作的,你可以看看完整的JsonTokenizer和JsonParser实现。他们每个都不到200行,所以它们应该是易于理解的。

JsonParser.parseObject()

JsonParser类的主要方法是parseObject(),它会检查JsonTokenizer中令牌的类型,并尝试在输入数据中查找该类型的JSON对象。

以下是parseObject()方法的实现:

private void parseObject(JsonTokenizer tokenizer) {
     assertHasMoreTokens(tokenizer);
     tokenizer.parseToken();
     assertThisTokenType(tokenizer, TokenTypes.JSON_CURLY_BRACKET_LEFT);
     setElementData     (tokenizer, ElementTypes.JSON_OBJECT_START);
     tokenizer.nextToken();
     tokenizer.parseToken();
     while( tokenizer.tokenType() != TokenTypes.JSON_CURLY_BRACKET_RIGHT) {                 
         assertThisTokenType(tokenizer, TokenTypes.JSON_STRING_TOKEN);
     setElementData(tokenizer, ElementTypes.JSON_PROPERTY_NAME);          
         tokenizer.nextToken();
     tokenizer.parseToken();
     assertThisTokenType(tokenizer, TokenTypes.JSON_COLON);
     tokenizer.nextToken();
     tokenizer.parseToken();
     if(tokenizer.tokenType() == TokenTypes.JSON_STRING_TOKEN) {             
             setElementData(tokenizer, ElementTypes.JSON_PROPERTY_VALUE);
     } else if(tokenizer.tokenType() == TokenTypes.JSON_SQUARE_BRACKET_LEFT) {
         parseArray(tokenizer);
     }
         tokenizer.nextToken();
     tokenizer.parseToken();
     if(tokenizer.tokenType() == TokenTypes.JSON_COMMA) {
         tokenizer.nextToken();  //skip , tokens if found here.             
             tokenizer.parseToken();
     }
      }
      setElementData(tokenizer, ElementTypes.JSON_OBJECT_END);
  }

  private void setElementData(JsonTokenizer tokenizer, byte elementType) {
     this.elementBuffer.position[this.elementIndex] = tokenizer.tokenPosition();     
     this.elementBuffer.length  [this.elementIndex] = tokenizer.tokenLength();         
     this.elementBuffer.type    [this.elementIndex] = elementType;      
     this.elementIndex++;
  }

parseObject()方法能够接受的信息包括:一个左大括({)后接着一个字符串令牌;或是一个逗号后跟着一个字符串令牌;或是某个数组的开始符号([);或是另一个JSON对象。当JsonParser从JsonTokenizer中获得了这些令牌之后,就将它们的开始位置、长度和语义信息保存在它自己的elementBuffer字段中。数据处理代码就可以随后浏览elementBuffer中的信息,从输入数据中获取所需的数据了。

看过了JsonTokenizer和JsonParser的核心代码部分之后,你应该对令牌生成器和解析器的工作方式有所了解了。如果要完整地了解代码的工作方式,你可能需要查看JsonTokenizer和JsonParser的完整实现。它们的代码都不超过115行,理解它们应该不是难事。

JsonNavigator组件

JsonNavigator是一个元素访问组件。它可以帮助我们访问 JsonParser
和JsonParser2创建的元素索引。两个组件产生的索引是相同的,所以来自两个组件的任何一个索引都可以。如下是代码示例:

JsonNavigator jsonNavigator = new JsonNavigator(dataBuffer, elementBuffer);

一旦JsonNavigator创建,您可以使用它的导航方法,next(),previous()等等。你可以使用asString(),asInt()和asLong()来提取数据。你可以使用isEqualUnencoded(String)来比较在数据缓冲器中元素的常量字符串。

使用JsonNavigator类看起来非常类似于使用GSON流化API。可以比较一下AllBenchmarks类的gsonStreamBuildObject(Reader)方法,和JsonObjectBuilder类parseJsonObject(JsonNavigator)方法。

他们看起来很相似,不是么?
只是,parseJsonObject()方法能够使用JsonNavigator的一些优化(在本文后面讨论),像数组中基本元素计数,以及对JSON字段名称更快的字符串比较。

性能基准测试

VTD-XML已经为它的XML解析器与StAX、SAX和DOM解析器进行过大量的性能基准比较测试了,从性能上来看VTD-XML无疑是最大的赢家。

为了让使用者对索引覆盖解析器的性能建立起信心,我也对我的JSON解析器实现与Google的JSON解析器——GSON,进行了性能对比。GSON的方式是从某个JSON输入(字符串或流)中创建一棵对象树。

请记住,GSON是一个非常成熟的产品,品质优秀,经过了大量的测试,并且接受用户的错误报告。而我的JSON解析器还只是处于概念产品的级别。这次测试仅仅是对性能的表现,这个结果也不代表最终的结论。也请注意阅读该测试的相关讨论。

这里有一些关于构建该测试的具体细节:

  • 为了使JIT预热以减少启动时的负载,对该JSON的输入解析一共运行了1千万次。
  • 该测试一共对三个不同的文件重复运行了相同的次数,以测试解析器解析小文件、中等文件和大文件的效果。文件的大小分别为64字节、406字节和1012字节。因此测试的过程就是首先对小文件进行1千万次解析,并分析其结果,然后解析中等文件并分析结果,最后是解析大文件并分析结果。
  • 在解析和分析工作开始前,文件已经全部加载到内存中,因此避免了将文件加载的时间算到整个解析时间里。
  • 对1千万次解析的分析过程会在自己的进程中进行,这意味着每个文件都在独立的进程中进行解析,在每个时间点只有一个文件在进行解析。
  • 每个文件会进行3次分析,因此对文件的1千万次解析工作一共会进行3次,每1次的分析工作是顺序进行的,而没有采用并行方式。

测试结果表格包括以下三列:

  • 原始数据缓冲区的迭代数目
  • JSON解析器
  • GSON

第一列中的内容是原始数据缓冲区中的所有数据的迭代数目,这个数字仅仅是用以表示极限的最小时间,即理论上处理所有这些数据的最小时间。当然不可能有任何解析器能够达到这一速度,不过这个数字能够起到参照作用,以显示出解析器和原始迭代速度的差距。第二列中显示了我的JSON解析器的运行时间,第三列则是Google的GSON解析器的运行时间。

以下数据是对三个文件(64字节、406字节、1012字节)各运行1千万次解析所需的毫秒数:

File Run Iteration JSON Parser GSON
Small 1 2341 69708 91190
Small 2 2342 70705 91308
Small 3 2331 68278 92752
Medium 1 13954 122769 314266
Medium 2 13963 131708 316395
Medium 3 13954 132277 323585
Big 1 33494 239614 606194
Big 2 33541 231866 612193
Big 3 32462 232951 618212

 

如你所见,索引覆盖的实现比起GSON(一种对象JSON解析器)要快得多。虽然结果在预计之中,不过你现在能够了解到它们的性能差距到底有多大了。

值得注意的一点是,在测试进程的执行过程中,内存占用的指标一直非常稳定。尽管GSON创建了大量的对象树,但它的内存占用并没有疯狂地增长。而索引覆盖方式的内存占用也非常稳定,比起GSON还要小了1兆左右,这有可能是因为加载到JVM中的GSON代码库较大的缘故。

基准化分析

VTD-XML对StAX,SAX和DOM解析器等XML解析器做了的广泛的基准化比较测试。在核心性能上,VTD-XML赢得了他们。

为了对索引叠加解析器的性能建立一些信任依据,我已经参考GSON实现了我的JSON解析器。本文的第一个版本只测算了解析一个JSON文件的速度与通过GSON反射构造对象。基于读者的意见,我现在已经扩大了基准,基于四种不同的模式来测算GSON:

1、访问JSON文件所有元素,但不做任何数据处理。

2、访问JSON文件所有元素,并建立一个JSONObject。

3、解析JSON文件,并构建了一个Map对象。

4、解析JSON文件,并使用反射它建立一个JSONObject。

请记住,GSON是一个高质量的产品,经过了很好的测试,也具有良好的错误报告等。只有我的JSON解析器是在概念验证级别。基准测试只是用来获得性能上的差异指标。他们不是最终的数据。也请阅读下文的基准讨论。

如下是一些基准结构化组织的细节:

·
为了平衡JIT,尽量减小一次性开销,诸如此类。JSON输入完成1000万次的小文件解析,100万次中等文件和大文件。

· 基准化测试分别重复三个不同类型的文件,
看看解析器如何做小的,中等和大文件。上述文件类型大小分别为58字节,783字节和1854字节。这意味着先迭代1000万次的一个小文件,进行测算。然后是中等文件,最后在大文件。上述文件存于GitHub库的数据目录中。

· 在解析和测算前,文件完全装载进内存中。这样解析耗时不包含装载时间。

·
1000万次迭代(或100万次迭代)测算都是在自己的进程中进行。这意味着,每个文件在单独的进程进行解析。一个过程运行一次。每个文件都测算3次。解析文件1000万次的过程启动和停止3次。流程是顺序进行的,而不是并行。

如下是毫秒级的执行时间数据:

基准
小1 小2 小3 中1 中2 中3 大1 大2 大3
JsonParser2 8.143 7.862 8.236 11.092 10.967 11.169 28.517 28.049 28.111
JsonParser2 + Builder 13.431 13.416 13.416 17.799 18.377 18.439 41.636 41.839 43.025
JsonParser 13.634 13.759 14.102 19.703 19.032 20.438 43.742 41.762 42.541
JsonParser + Builder 19.890 19.173 19.609 29.531 26.582 28.003 56.847 60.731 58.235
Gson Stream 44.788 45.006 44.679 33.727 34.008 33.821 69.545 69.111 68.578
Gson Stream + Builder 45.490 45.334 45.302 36.972 38.001 37.253 74.865 76.565 77.517
Gson Map 66.004 65.676 64.788 42.900 42.778 42.214 83.932 84.911 86.156
Gson Reflection 76.300 76.473 77.174 69.825 67.750 68.734 135.177 137.483 134.337

如下是比较基准所处理事情的说明:

描述
JsonParser2 使用JsonParser2解析文件和定位索引。
JsonParser2 + Builder 使用JsonParser2解析文件和在解析文件上构建JsonObject。
JsonParser 使用JsonParser解析文件和定位索引。
JsonParser + Builder 使用JsonParser解析文件和在解析文件上构建JsonObject。
Gson Stream 使用Gson streaming API解析文件和迭代访问所有令牌。
Gson Stream + Builder 解析文件和构建JsonObject。
Gson Map 解析文件和构建Map。
Gson Reflection 使用反射解析文件和构建JsonObject。

如你所见,索引叠加实现(JsonParser和JsonParser2)比Gson更快。下面我们将讨论一下产生上述结果的原因的推测。

关于测试结果

如果我们只是简单地说对一个为数据创建对象树的解析器(GSON)和一个标记出数据中所找到的元素位置的解析器进行比较,这种说法有欠公平。我们还需要分析一下具体比较了哪些内容。

在一个运行中的应用程序对文件进行解析通常包含以下步骤:

澳门新葡亰娱乐官网 15

首先从磁盘或者网络上加载数据,然后对数据进行解析,最后进行数据处理。

为了准确测量数据解析部分的速度,我将被解析的文件预先加载入内存中,并且测试代码对数据完全不做任何处理。这种方式虽然测量了纯粹的解析速度,但这一性能差别并不能代表在实际运行中的应用程序一定会获得更好的性能,原因如下:

一个流解析器通常能够在所有数据加载到内存之前就开始解析正在加载中的数据,而我的JSON解析器目前还没有实现这一功能,这意味着虽然它在单纯的解析速度上要快上一筹,但运用在实际运行中的应用程序上时,由于它必须等待所有数据加载完成,因此真实的完成速度不一定会更快。下图就表现了这一过程:

澳门新葡亰娱乐官网 16

为了加快整体的解析速度,你也可以对我的解析器进行一些修改,让它能够边加载数据边进行解析,不过这样做也许会稍稍降低单纯的解析性能。当然,最终的运行速度或者还是得到一些提升。

与上面的情况类似的是,我的JSON解析器对已解析的数据也没有进行任何处理。如果你需要从大量的已解析数据中抽取字符串,那么GSON已经为你的需求做好了准备工作,因为它已经为已解析数据创建了一棵对象树。下图就表现了这一过程:

澳门新葡亰娱乐官网 17

如果你打算使用GSON,那么它或许已经为你实现了在数据处理中所需的数据抽取过程,如果整个数据处理过程可以省略数据抽取(例如抽取为字符串)这一步骤,那么它的整体速度还要再快一点。

因此,为了准确地测量解析器对你的应用程序的影响,你必须将不同的解析器在你的应用程序中的表现进行测量。我仍然确信使用索引覆盖解析器的速度要更快,但具体有多少差距还不好说。

性能分析

GSON Streaming
API并非更快的主要原因是当遍历时所有数据都从流中抽取,即使不需要这些数据。每一个令牌变成一个string,int,double等,存在消耗。这也是为什么用Gson
streaming API解析JSON文件和构建JsonOject和访问元素本身是一样快。
唯一增加的显式时间是JsonObject内部的JsonObject和数组的实例化。

数据获取不能解释这一切,尽管,使用JsonParser2构建一个JSONObject比使用Gson
streaming
API构建JSONObject几乎快两倍。如下说明了一些我看到的索引叠加解析器比流式解析器的性能优势:

首先,如果你看一下小的和大的文件的测试数据,每一次解析式GSON都存在一次性开销。
JsonParser2+
JsonParser和GSON基准测试间的性能差异在小的文件上更明显。可能原因是theCharArrayReader创建,或类似的事情。也可能是GSON内部的某项处理。

第二,索引叠加解析器可以允许你控制你想抽取的数据量。这个让你更细粒度的控制解析器的性能。

第三, 若一个字符串令牌含有需要手动从UTF-8转换为UTF-16的转义字符(如“”
t N
R“),JsonParser和JsonParser2在分析时能够识别。如果一个字符串令牌不包含转义字符,JsonNavigator可以用一个比它们更快的字符串创建机制。

第四,JsonNavigator能够让数据缓冲区中的数据的字符串比较更快。 当你需要检查字段名是否等于常量名时,非常方便。使用Gson’s
streaming
API,你将需将字段名抽取为一个String对象,并比较常量字符串和String对象。JsonNavigator可以直接比较常量字符串和数据缓冲区中的字符,而无需先创建一个String对象。这可以节省一个String对象的实例化,并从数据缓冲区中的数据复制到一个String对象的时间,它是仅用于比较(如检查JSON字段名称是否等于“key”或“name”或其它)。JsonNavigator使用方式如下所示:

if(jsonNavigator.isEqualUnencoded("fieldName")) { }

第五,JsonNavigator可以在其索引向前遍历,计数包含原始值(字符串,数字,布尔值,空值等,但不包含对象或嵌套数组)数组中的元素数量。当你不知道数组包含有多少个元素,我们通常抽取元素并把它们放到一个List中。一旦你遇到数组结束的标记,将List转成数组。这意味着构建了非必要的List对象。此外,即使该数组包含原始值,如整数或布尔值,所有抽取的数据也必须要插入到List对象。抽取数值插入List时进行了不必要的对象创建(至少是不必要的自动装箱)。再次,创建基础值数组时,所有的对象都必须再次转换成原始类型,然后插入到数组中。如下所示是Gson
streaming API工作代码:

List<Integer> elements = new ArrayList<Integer>();
reader.beginArray();
while (reader.hasNext()) {
   elements.add(reader.nextInt());
}
reader.endArray();
int[] ints = new int[elements.size()];
for (int i = 0; i < ints.length; i++) {
   ints[i] = elements.get(i);
}

当知道数组包含的元素数时,我们可以立即创建最终的Java数组,然后将原始值直接放入数组。在插入数值到数组时,这节省了List实例化和构建,原始值自动装箱和对象转换到原始值的时间。如下所示是使用JsonNavigator功能相同的代码:

int[] ints = new int[jsonNavigator.countPrimitiveArrayElements()];
for (int i = 0, n = ints.length; i < n; i++) {
   ints[i] = jsonNavigator.asInt();
   jsonNavigator.next();
}

即使刚刚从JSON数组构建List对象,知道元素的个数可以让你从一开始就能正确的实例化一个ArrayList对象。这样,你就避免了在达到预设阈值时需动态调整ArrayList大小的麻烦。如下是示例代码:

List<String> strings = new ArrayList<String>(jsonNavigator.countPrimitiveArrayElements());
jsonNavigator.next(); // skip over array start. 
while (ElementTypes.JSON_ARRAY_END != jsonNavigator.type()) {
   strings.add(jsonNavigator.asString());
   jsonNavigator.next();
}
jsonNavigator.next(); //skip over array end.

第六,当需访问原始数据缓冲区时,可以在很多地方用ropes代替String对象。一个rope是一个含有char数组引用的一个字符串令牌,有起始位置和长度。可以进行字符串比较,就像一个字符串复制rope等。某些操作可能用rope要比字符串对象快。因为不复制原始数据,它们还占用更少的内存。

第七,如果需要做很多来回的数据访问,您可以创建更高级的索引。
VTD-XML中的索引包含元素的缩进层次,以及同一层的下一个元素(下一个同级)的引用,带有更高缩进层的第一个元素(初始元素),等等。这些都是增加到线性解析器元素索引顶部的整型索引。这种额外的索引可以让已解析数据的遍历速度更快。

对索引覆盖解析器的总体讨论

我经常听到一种关于索引覆盖解析器的争论,这种说法认为由于索引覆盖解析器为了实现对原始数据的索引,而不是将原始数据抽取为对象树,它在解析时必须将所有数据读入内存中,这种方式在解析大文件时会对内存产生很大的负担。

这种说法其实就是表明了流解析器(例如SAX或StAX)能够解析巨大的文件,而不需要将整个文件读入内存中。但这种说法成立的前提是,该文件中的数据可以分为多个小块进行解析与处理,而且每个小块可以独立地被解析与处理。举例来说,一个大XML文件包含了一系列的元素,每个元素都可以进行独立的解析和处理(类似于一个日志记录集合)。但如果你的数据可以以独立的小块进行分别解析的话,那么你也完全可以实现一个能够做到这一点的索引覆盖解析器。

而如果该文件不能够分解为多个独立的小块进行解析的话,那无论如何你必须将信息加载到某种结构中,以便代码在处理之后的小块时访问这一部分信息。而如果你能够在流解析器中做到这一点的话,那么也同样可以在一个索引覆盖解析器做到这一点。

那些为输入数据创建对象树的解析器往往会占用更大的内存,因为对象树的内存占用会超过原始数据的尺寸。其原因在于不仅每个对象实例会占用内在,而且对象之间的引用也占用了一部分内存数据。

此外,由于所有数据必须一次性全部加载到内存中,因此你需要预先为数据缓冲区预留足以保存全部数据的空间。但如果在开始解析某个文件的数据时,你还不知道整个文件的大小,又该怎么做呢?

假设你有一个允许用户上传文件的web应用程序(或者是web
service,或其它类型的服务端应用程序),你很难判断这些文件会有多大,那又如何能够在开始解析之前为它们分配足够大小的缓冲区呢?当然,出于安全性的考虑,你应该设定一个允许上传文件的最大尺寸,否则用户可以通过上传超大文件使你的系统完全崩溃,或者编写一段程序以模拟浏览器上传文件的操作,让这段程序不停地向你的服务器发送数据。你可以考虑为缓冲区分配与允许上传文件的最大尺寸相同的值,这样可以保证你的缓冲区对于有效的上传不会占用所有的内存。如果缓冲的尺寸真的过大,那一定是因为你的用户上传了超大的文件。

 

性能和错误报告

若看看JsonParser和JsonParser2代码,你将看到更快的JsonParser2比JsonParser更糟糕的错误报告。当分析和解析阶段一分为二时,良好的数据验证和错误报告更易于实现。

通常情况下,这种差异将触发争论,在解析器的实现进行取舍时,优先考虑性能还是错误报告。然而,在索引叠加解析器中,这一讨论是没有必要的。

因为原始数据始终以其完整的形式存在于内存中,你可以同时具有快和慢的解析器解析相同的数据。您可以快速启动快的解析器,若解析失败,您可以使用较慢的解析器来检测其中输入数据中的错误位置。当快的解析器失败时,只要将原始数据交给较慢的解析器。基于这种方式,你可以获得两个解析的优点。

基准分析

基于数据(GSON)创建的对象树与仅标识在数据中找到的数据索引进行比较,而没有讨论比较的标的,这是不公平的比较。

在应用程序内部解析文件通常需要如下步骤:

澳门新葡亰娱乐官网 18

首先是数据从硬盘或者网络上装载。接着,解码数据,例如从UTF-8到UTF-16。第三步,解析数据。第四步,处理数据。

为了只测量原始的解析器速度, 我预装载待解析的文件到内存。 该基准测试的代码没有以任何方式处理数据。尽管该基准化测试只是测试基础的解析速度,在运行的应用程序中,性能差异并没有转化成性能显著提高。如下是原因:

流式解析器总是能在所有数据装载进内存前开始解析数据。我的JSON解析器现在实现版本不能这样做。这意味着即使它在基础解析基准上更快,在现实运行的应用程序中,我的解析器必须等待数据装载,这将减慢整体的处理速度。如下图说明:

澳门新葡亰娱乐官网 19

为了加速整体解析速度,你很可能修改我的解析器为数据装载时即可以解析数据。但是很可能会减慢基本解析性能。但整体速度仍可能更快。

此外,通过在执行的基准测试之前数据预加载到内存中,我也跳过数据解码步骤。数据从UTF-8转码为UTF-16是也存在消耗。在现实应用程序中,你不可以跳过这一步。每个待解析的文件来必须要解码。这是所有解析器都要支持的一点。流式解析器可以在读数据时进行解码。索引叠加分析器也可以在读取数据到缓冲区时进行解码。

VTD-XML 和Jackson
(另一个JSON解析器)使用另一种技术。它们不会解码所有的原始数据。相反,它们直接在原始数据上进行分析,消费各种数据格式,如(ASCII,UTF-8等)。这可以节省昂贵的解码步骤,解码要使用相当复杂分析器。

一般来说,要想知道那个解析器在你的应用程序更快,需要基于你真实需要解析的数据的基准上进行全量测试。

索引叠加解析器一般讨论

我听到的一个反对索引叠加分析器的论点是,要能够指向原始数据,而不是将其抽取到一个对象树,解析时保持所有数据在内存中是必要的。在处理大文件时,这将导致内存消耗暴增。

一般来说,流式分析器(如SAX或StAX)在解析大文件时将整个文件存入内存。然而,只有文件中的数据可以以更小的块进行解析和处理,每个块都是独立进行处理的,这种说法才是对的。例如,一个大的XML文件包含一列元素,其中每一个元素都可以单独被解析和处理(如日志记录列表)。如果数据能以独立的块进行解析,你可以实现一个工作良好的索引叠加解析器。

如果文件不能以独立块进行解析,你仍然需要提取必要的信息到一些结构,这些结构可以为处理后面块的代码进行访问。尽管使用流式解析器可以做到这一点,你也可以使用索引叠加解析器进行处理。

从输入数据中创建对象树的解析器通常会消耗比原数据大小的对象树更多的内存。对象实例相关联的内存开销,加上需要保持对象之间的引用的额外数据,这是主要原因。

此外,因为所有的数据都需要同时在内存中,你需要解析前分配一个数据缓冲区,大到足以容纳所有的数据。但是,当你开始解析它们时,你并不知道文件大小,如何办呢?

假如你有一个网页应用程序(如Web服务,或者服务端应用),用户使用它上传文件。你不可能知道文件大小,所以开始解析前无法分配合适的缓存给它。基于安全考虑,你应该总是设置一个最大允许文件大小。否则,用户可以通过上传超大文件让你的应用崩溃。或者,他们可能甚至写一个程序,伪装成上传文件的浏览器,并让该程序不停地向服务器发送数据。您可以分配一个缓冲区适合所允许的最大文件大小。这样,你的缓冲区不会因有效文件耗光。如果它耗光了空间,那说明你的用户已经上传了过大的文件。

You can leave a response, or trackback from your own site.

Leave a Reply

网站地图xml地图