基于语义的HTML输入分裂并行解析器的设计
JiHyun Lee，Yeoul Na和Seon Wook Kim
电气与计算机工程系
韩国大学
抽象 -HTML是一种广泛使用的标记语言，以 无数的网页。 HTML解析器的并行化将导致相应的性能改进和更好的用户体验。 然而，并行化HTML解析器是具有挑战性的，因为解析器模型中的强循环依赖性。 在本文中，我们提出了一种基于语义的HTML并行解析器设计，通过一个“div”标签拆分输入HTML文档，并使用多个解析器线程处理独立的部分输入。 我们用从500个网页中选择的基准评估了所提出的HTML并行解析器，并实现了1.49x的最大加速。
关键字 - HTML; 平行化; 多线程;
一、引言
超文本标记语言（HTML）是用于网页的标准标记语言。 尽管HTML的历史悠久，但很少有论文研究利用HTML解析器的数据级并行性。 原因是并行化HTML解析器是一个具有挑战性的任务，由于HTML解析器模型中的强循环依赖性。
在最近的研究中，HPar [1]已经为HTML实现了第一个实用的并行解析器。 他们以面向大小的方式拆分多个解析器线程的HTML输入块。 然而，这种面向大小的分裂导致对并行线程中的分词器的初始状态的推测，并使分析算法更复杂。
在本文中，我们提出了一个基于语义的输入分割机制，用于在HTML解析器中使用数据级并行。 div 标签，HTML文档中的一个部门标签，代表了网页中的剥离部分。 因此，不同的 div 标签 的解析 是相互独立，其中包含潜在的数据级并行性。 我们提出的并行解析器的不同 分区 的部分 分配 到多个线程分析器 在利用HTML解析数据级并行 。 我们实现了基于jsoup [2]，一个用Java编写的独立HTML解析器[3]提出的设计。
本文的主要贡献如下：
- 基于语义的HTML解析器并行 -本文 提出了基于语义的HTML解析器平行分布即通过 div 标签多个线程分析器 分离部分的投入 。 据我们所知，这是第一个利用网页中不同部分的并行性的HTML并行解析器。
- 投机回避 -以前的并行 解析器推测性地执行并行解析器线程，这可能引起大量的推测回滚开销。 本文介绍了并行解析器设计，通过利用一个事实，即独家 div 标签 的解析 是独立的 避免了投机执行 。
- 评价与现实世界中的HTML文档 -我们 实现了基于jsoup，一个用Java编写的HTML解析器的并行解析器。 我们使用来自前500个网站的基准评估了所提出的并行解析器。 通过研究的基准，提出的并行解析器与基准顺序解析器相比实现了性能提高高达1.49倍。
本文的其余部分安排如下。 在第2节，我们解释背景信息。 第3节提出了我们的新的解析模型及其实现。 第4节演示了我们的建议的实验结果。 最后，我们在第5节中总结了这篇文章。
二、背景
A、解析HTML5的模型
HTML5 [4]是HTML标准的最新版本由万维网联盟（W3C）指定。 主要的网络浏览器，如Chrome [5]，Firefox [6]和Safari [7]支持大多数HTML5规范跨浏览器兼容性[8,9]。 在这种情况下，HTML5在许多浏览器中的解析模型几乎是相同的，因此，解析模型的进步可能有积极的影响。
图1中描述了HTML5的解析模型。 输入HTML文档作为字节流进入分词器。 令牌化器执行令牌化，然后将识别的令牌移交给树构造器。 当前的HTML5标准将tokenizer指定为由68个状态组成的状态机。 根据该规范，在消费新识别的令牌之后，由树构造器更新分词器的状态。
B、并行化HTML解析器的障碍
HTML解析器是Web浏览器的一部分，它将输入字节流转换为节点树。 HTML的解析结果称为“文档对象模型（DOM）树”[10]。 每当分词器识别来自输入的令牌时，树构造器将给定的令牌添加到DOM树的节点。
在这个过程中，分词器和树构造器具有强的循环依赖性。 根据HTML5规范，分词器在树构造器完成消耗当前令牌之前不能前进到下一个数据元素。 原因是，标记化依赖于由构造循环依赖的树构造函数产生的标记化器状态。
由于解析器模型中的循环依赖性，先前的并行解析器[1]需要猜测记分器状态。 推测执行涉及推测回滚开销，以保证正确的执行结果[1]。 在本文中，我们建议一个基于语义的HTML并行解析器，不需要推测和回滚开销。
三、并行程序设计
大多数现有的HTML解析器，包括jsoup [2]，顺序处理HTML输入，因为在标记化和树建立之间的循环依赖。 在此背景下，本文提出了一种新的HTML解析器并行设计，通过分发独立的 div 标签将多个线程分析器 利用并行性 。
以下小节描述1）所提出的基于语义的并行化机制和2）在jsoup之上的所提出的设计的实现。
A.基于语义的并行化
为了避免猜测初始化标记化状态，我们提出了一种基于语义的HTML文档的输入分割。 在我们的基于语义的输入拆分机制，线程分配的目标是封闭的 div标签 的完整块 。 以下讨论描述我们的原因 采用这种 div 标签导向机制。
- 为什么输入分配的目标是div 标签：div 标签 的名称 从#39;师#39;来了。 div 标签定义了一个部门或一个HTML文件和组块元素格式化文档的部分。 一个代码块由一个 div 标签 包围 对，它由一开始标记，lt;DIVgt; 和结束标记 lt;/ DIVgt;， 描述了一个HTML文档中一个完全独立的部分。 换言之，一个事实，即输入由 div 标签 切割 装置，每个线程解析HTML文档的一个独立的分部。
- 为什么我们为每个线程分配一个完整的开始和结束标记块：先前的工作[1]采用基于大小的输入分割，不考虑标签结构，即忽略嵌套层次的标签结构和一对开始和结束标签。 然而，以这种方式，每个并行解析器线程不知道分词器的初始状态，因为先前的部分输入的最终状态对于每个线程是未知的。 然后，基于大小的机制引导每个解析器线程基于经验观察来推测初始状态。 有时，这种预测将会是错误的，因此需要一个错误处理函数，这需要推测开销。 为了避免推测，我们决定将第一个令牌与部分输入的最后一个令牌配对，以使部分输入具有完美的代码块。 因此，我们的并行解析器不包括使用这种基于语义的线程分布的推测和错误预测处理惩罚。
B、实施
HTML5规范描述的基本HTML解析模型如图1所示。 在HTML解析器接收到HTML输入流之后，令牌器消耗用于词法分析的输入字符，即令牌化。 令牌器将输入的字符转换为令牌，并将它们发送到树构造器。 树构造函数从tokenizer接收令牌并构建一个DOM树。
在本文中，我们插入了两个阶段：搜索和合并。 搜索阶段用于快速浏览输入并将部分输入分发到解析器线程。 合并阶段用于收集部分DOM树输出并将它们组合成完整的DOM树。 图。 图2示出了用于并行化HTML解析器的基本HTML解析器模型的扩展。
图3描述了我们的并行解析器的执行流程。 搜索阶段查看输入并确定将输入拆分为部分输入的位置。 当并行解析器被给定一个字节流作为其输入时，并行解析器逐字节查看输入流，并决定是否用于分割输入的条件是否满足。 每当满足条件时，则将每个分离的部分输入发送到新的解析器线程。 分裂条件满足时，搜索到达 div 标签对 的结束标记 。另外，重要的是要注意，我们提出的设计识别嵌套标记模式，并且只分割最高级别的嵌套标记对，忽略内部嵌套标记对。 然后，每个被调用的解析器线程接收来自搜索阶段的部分输入，将该部分输入解析成部分DOM树，并将所生成的部分DOM树返回到主线程。 在并行解析完成之后，合并阶段将由多个解析器线程生成的部分DOM树组合成单个DOM树。
四、考核评价
A、方法
我们的并行解析器在Oracle Java Standard Edition开发工具包8上实现[3]。 所有实验在2.6GHz Intel Xeon CPU E5-2650 v2服务器上执行。 目标平台包括16个物理核心，每个物理核心有2个逻辑核心。 系统高速缓存具有32 KB L1，256 KB L2和20 MB L3高速缓存。
我们用表1中列出的流行网页来测量所提出的并行解析器的执行时间。基线HTML解析器是jsoup库的原始顺序解析器。 我们在前面提到的同一个系统上执行了并行解析器和基线解析器。 为了避免测量“离群值”，我们每个基准解析10次，测量结果取平均值。
B、基准
为了评估我们的并行解析器，在前500个网站中选择了7个基准进行性能比较[11]。 我们精心挑选了世界上受欢迎和经常访问的代表性基准。
C、实验结果
图4示出了具有4个线程的并行解析器在基线顺序解析器上的归一化加速比。 每个条表示平均性能改进，最右边的条表示几何平均值。 1.21的最低增速出现了google.com 和 baidu.com。 1.49的最大加速由 wikipedia.org 生产 。 我们在研究的网站上实现了1.29倍的平均加速。
显示出高于平均增速，如 wikipedia.org 和 twitter.com 更好的加速基准测试 有很好的平衡标签的结构。 相反，这显示出较低的加速如 google.com 和baidu.com 其他基准测试 不平衡线程负载。 这种负载不平衡负面影响并行化HTML解析的优势。
五、结论
拟议的HTML解析器通过把HTML文档到 的div 块元素 利用数据级并行 。 我们利用这一事实div 标签分离的网页的部分，且因而分割部分可以解析独立地。 所提出的基于语义的解析模型使得HTML并行解析而不支持推测。 我们的实验结果表明，最大性能提高1.49倍。 我们离开了嵌套标签模式的支持，以提高未来工作的负载平衡。
这项工作得到贸易，工业和能源部（MI，韩国）资助的工业战略技术开发计划（10041664，基于多色器GPU的融合处理器的开发）
[1] Z. Zhao, M. Bebenita, D. Herman, J. Sun, X. Shen, “HPar: a practical
parallel Parser for HTML ̽ taming HTML complexities for parallel
parsing”, ACM Transactions on Architecture and Code Optimization
(TACO), vol. 10(4):44, December 2013.
[2] jsoup: Java HTML Parser, http://jsoup.org/
[3] Oracle Java SE 8, (Java Standard Edition Development Kit 8u20),
http://www.oracle.com/technetwork/java/javase/downloads/javaarchive-javase8-2177648.html#jdk-8u20-oth-JPR
[4] HTML Living Standard, https://html.spec.whatwg.org/multipage/
[5] Google Chrome,
https://www.google.com/chrome/browser/desktop/index.html
[6] Mozilla Firefox, https://www.mozilla.org/ko/firefox/products/
[7] Apple Safari, http://www.apple.com/safari/
[8] G. Anthes, “HTML5 Leads a Web Revolution”, Communications of the
ACM (CACM), vol.55(7), July 2012, pp
全文共7959字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[144294]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
