文档章节

将多个路径字符串转换成XML文档树

摆渡者
 摆渡者
发布于 2014/09/28 21:51
字数 1768
阅读 150
收藏 0

假设有下面的字符串:

/home/usr/abc/def/文本.txt
/home/usr/desktop/音乐.mp3
/etc/init.d/mysql/mysql
/etc/profile
/tmp/垃圾.tmp
/usr/bin/open-jdk7/java
...

给定一个根节点名字root和叶子节点名字leaf,如何将它们转换成一颗像下面这样的XML文档树呢?

<root>
  <home>
    <usr>
      <abc>
        <leaf>文本.txt</leaf>
      </abc>
      <desktop>
        <leaf>音乐.mp3</leaf>
      </desktop>
    </usr>
  </home>
  <etc>
    <init.d>
      <mysql>
        <leaf>mysql</leaf>
      </mysql>
    </init.d>
    <leaf>profile</leaf>
  </etc>
  <tmp>
    <leaf>垃圾.tmp</leaf>
  </tmp>
  <usr>
    <bin>
      <open-jdk7>
        <leaf>java</leaf>
      </open-jdk7>
    </bin>
  </usr>
</root>

对于这个问题,一个解决的思路是:先创建一颗以root作为根标签的XML文档树,再循环迭代每个字符串,将其按照'/'切开(Split),然后依次对每个文件夹名字创建一个XML节点(Node),并搜索整棵树,如果该节点存在,则直接pass掉,否则将节该点追加到某个父节点下。但是此种方法太麻烦,因为每次增加一个节点,你就需要去遍历一次。有很多情况下,前几层节点是存在的,这样判断就不那么高效了。举个例子,现在有一条深度为10的文件夹路径(比如/a/b/c/d/e/f/g/h/i/j/**.sh),为了插入这条路径,首先需要判断/a是否存在,存在就pass掉,不存在就创建/a;之后判断/a/b是否存在;之后是/a/b/c是否存在。。。

很显然,这样做,越到后面效率越低。而且,直接操作Xml文档会占用很多资源。

那么,有没有一种简单又高效的方式呢?答案是肯定的,这就是写这篇博客的原因了。这只是一种方案,也许还有更好的,有兴趣的同学可以自行研究,哈哈……

首先,我们可以将这些文件夹路径进行预处理────转换成中间格式进行存储。这里,我们可以先定义一个Map结构,Key用于保存当前节点名字和节点的XPath,中间可用特殊字符隔开;Value用于保存当前节点的父节点的名字和父节点的XPath(根节点root的父亲为null),中间也用相同的特殊字符隔开,像下面这样:

<home#/root, root#null>
<user#/root/home, home#/root>

第一行表示:当前的home节点XPath为/root,其父节点root的xPath为null,同理,第二行表示:当前节点user的XPath为/root/home,而其父节点home的XPath为/root。把Key设计成这样有一个好处是,当一条路径中的多层里有相同名字的文件夹时,也可以轻易分辨。比如有一条路径为:/home/home/home,那么在创建节点时,会创建以下几个键值对:

<home#/root, root#null>
<home#/root/home, home#/root>
<home#/root/home/home, home#/root/home>

就是说,在同一个XPath(例如/root/home)下,只会存在一个名为home的文件夹。如果以后的文件夹路径中还包含/home/home/home这样的地址,那么这些文件夹的子文件夹将会被放在已经存在的/root/home/home/home路径下。再通俗一点:每个Key-Value都是唯一的,它唯一表示了一条路径的存在。

有人可能会问:为什么Value也要设计成一样的结构呢?

答案很简单,便于在以后的处理中直接使用这个值,后面会提到。

通过这样的转换,我们可以看出,第二行的value实际上就是第一行的key,这样我们就可以表示一条一条的子孙——祖宗链,都是由子节点指向父节点。

转换之后的Map像下面这样:

<home#/root, root#null>
<user#/root/home, home#/root>
<abc#/root/home/user, user#/root/home>
<def#/root/home/user/abc, abc#/root/home/user>
<文本.txt#/root/home/user/abc/def, def#/root/home/user/abc/def>

<!-- 第二个URL中的home文件夹和user文件夹对应的key就是第一个key,
已经存在,则不会在增加这个key了 -->
<desktop#/root/home/user, user#/root/home>
<音乐.mp3#/root/home/user/desktop, desktop#/root/home/user>

<etc#/root, root#null>
<init.d#/root/etc, etc#/root>
<mysql#/root/etc/init.d, init.d#/root/etc>
<mysql#/root/etc/init.d/mysql, mysql#/rot/etc/init.d>
...

细心的同学可能已经看见了,第5行以后,处理第二个URL时,home和user两个文件夹已经存在,则直接pass掉,接着处理desktop文件夹了。还有desktop文件夹对应的value是user#/root/home,这和第3行的value相同,因此文件夹desktop和abc属于同一级,都在/root/home/user下。

转换后,我们可以做以下几件事:

  1. 直接遍历这个Map,先找出根目录(即value为root#null的)root下的所有节点(这里是home, etc, tmp, usr,当然也可能直接就是一个文件了)。判定的标准为:所有的value都为root#null的。

  2. 循环遍历root的子节点集合,判定每个子节点是否为叶子节点(即文件),若是,则加上<leaf>节点名字<leaf>,可以考虑使用StringBuilder.append();,若不是,则对每个子节点做以下几件事:

    1. 加上节点开始标记<节点名字>

    2. 做第1步,只是当前目录不是根目录而已(递归了)

    3. 加上节点结束标志<节点名字>


这样递归下去,就会形成多颗以文件夹路径开始的文件夹作为根目录的XML树,最后将所有得到的小树都添加到新创建的<root></root>根标签中,到此,文档生成完成。

代码就不写了,思路已经相当清晰了,哈哈

使用这种方式,虽然迭代次数可能比较多,但是使用Map来保存树的结构以及使用字符串来生成XML的资源消耗都不大,而且效率都相当高。至于有多高,我用以上数据做了个测试,执行时间在1~3ms,感兴趣的亲们可以试试。


后记

    开始的一个版本是:将Map中的Key和Value都表示为当前【节点名字#深度】,但是当我按照这种思路写完后,立刻发现生成的XML不是我想要的,因为我的测试数据中存在多个【节点名字】和【深度】都相同的节点,但是其根节点不同。。。。究其原因,是因为我们设计时可能存在同样的Key,于是后面的同深度且同名的文件夹名字则被pass掉了,导致该深度下所有同名的文件夹都被添加到了第一颗根节点下。

    后来想了半天,才把这个【节点名字#深度】替换为【节点名字#XPath】,这个必须是唯一的了。


© 著作权归作者所有

摆渡者
粉丝 346
博文 171
码字总数 206504
作品 0
成都
程序员
私信 提问
调查最先进的 XML 压缩技术

原文转自:http://www.ibm.com/developerworks/cn/xml/x-datacompression/ XML 是因为 HTML 和万维网的广泛普及而出现的最有用、最重要的技术之一。XML 解决了许多问题,因为它可以在不同的架...

IBMdW
2011/09/13
1K
0
[python知识] 爬虫知识之BeautifulSoup库安装及简单介绍

一. 前言 在前面的几篇文章中我介绍了如何通过Python分析源代码来爬取博客、维基百科InfoBox和图片,其文章链接如下: [python学习] 简单爬取维基百科程序语言消息盒 [Python学习] 简单网络爬...

Eastmount
2015/03/25
0
0
AJAX基础(四)——DOM与xml及xpath

Javascript中装载XML文档 装载同域的XML文件 装载一段表示XML的字符串 装载的js代码 function loadXML(flag,xmldoc){ } 调用装载代码: function text(){ IE和FireFox类的浏览器对于这两种情...

白志华
2015/09/28
65
0
org.w3c.dom(java dom)解析XML文档

位于org.w3c.dom操作XML会比较简单,就是将XML看做是一颗树,DOM就是对这颗树的一个数据结构的描述,但对大型XML文件效果可能会不理想 首先来了解点Java DOM 的 API: 1.解析器工厂类:Docum...

二团长的迫击炮
03/20
108
0
【Qt笔记】使用 DOM 处理 XML

DOM 是由 W3C 提出的一种处理 XML 文档的标准接口。Qt 实现了 DOM Level 2 级别的不验证读写 XML 文档的方法。 与之前所说的流的方式不同,DOM 一次性读入整个 XML 文档,在内存中构造为一棵...

大道无名
2016/08/05
45
0

没有更多内容

加载失败,请刷新页面

加载更多

15、SpringMVC进行json交互

SpringMVC进行json交互 json数据格式在接口调用中、html页面中较常用,json格式比较简单,解析还比较方便。 请求json、输出json。要求请求的是json串,前端页面中需要将请求的内容转成json,...

快乐的瓶子
28分钟前
6
0
delphi版插apc杀进程驱动源码

从c代码转的,备份一下,里面有硬编码unit MyDriver;{$HINTS OFF}{$WARNINGS OFF}interfaceusesnt_status, ntoskrnl, native, winioctl, fcall, macros;typeTKILL = ...

simpower
32分钟前
4
0
带你上手一款下载超 10 万次的 IDEA 插件

作者 | 倪超(银时) 阿里云开发者工具产品专家 本文整理自 11 月 7 日社群分享,每月 2 场高质量分享,点击加入社群。 导读:Cloud Toolkit 是本地 IDE 插件,帮助开发者更高效地开发、测试...

阿里云官方博客
32分钟前
4
0
GMAT语法7个常考重要考点分析

GMAT语法考点多,并非所有考点都值得重点关注。实际上GMAT语法存在一些高频考点,考生需要优先掌握它们才能更好地保证得分。同时GMAT备考中大家还需要培养连续做题的耐力。下面小编就来做具体...

bole6
37分钟前
4
0
最佳实践 | RDS & POLARDB归档到X-Pack Spark计算

X-Pack Spark服务通过外部计算资源的方式,为Redis、Cassandra、MongoDB、HBase、RDS存储服务提供复杂分析、流式处理及入库、机器学习的能力,从而更好的解决用户数据处理相关场景问题。 RD...

一肥仔
38分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部