1. 云栖社区>
  2. 博客列表>
  3. 正文

用树结构描述和计算数据

沙漠之鹰123 2016-04-21 13:48:19 浏览586 评论0

摘要: 描述数据最常见的结构是平面表格,数据库,Excel,CSV都是典型的表格。表格是扁平结构,理解起来简单,能方便的增删改查。  下面是一个典型的表格: 时间 小时 分钟 12:03 12 03 15:32 15 32 从上面的表格,明显能看出表格的缺陷: 所有的子项都是平级的,无法描述它们内在的结构 列名很重要,否则很难确定其语义,这和第一条相辅相成 在数据深度上进行规约和下钻时,不可避免的会造成数据重复。

描述数据最常见的结构是平面表格,数据库,Excel,CSV都是典型的表格。表格是扁平结构,理解起来简单,能方便的增删改查。 
下面是一个典型的表格:

时间 小时 分钟
12:03 12 03
15:32 15 32

从上面的表格,明显能看出表格的缺陷:

  • 所有的子项都是平级的,无法描述它们内在的结构
  • 列名很重要,否则很难确定其语义,这和第一条相辅相成
  • 在数据深度上进行规约和下钻时,不可避免的会造成数据重复。
  • 对列的描述,无法直接保存在表格中,还需要另外建立数据结构存储

如果我们将上面的表格描述成下面的树,这些问题就变得容易解决了:

  • (父节点) 
    • (子节点)12
    • (子节点):
    • (子节点)03

因此,父节点不需要存储数据,其值是子节点数据的组合,不会有重复。能够明确的描述数据的层级关系和结构,支持在不同层级检索数据,对上面的例子,第一层是12:03, 细分之后,第二层是12和03。
因此,将表格转换为树,笔者将其称为树表,可能会是两种情况:

  • 结构一致的树的森林,每一棵树代表一行数据
  • 只有一棵树,每个树节点是数组,分别对应了表格中的一列

推荐使用第二种,这样就能方便地将列的元属性记录在节点中,而不造成重复,也可以很容易的将树表打平,变成普通表格。树结构是递归的,因此支持递归操作,下面将讨论树表可能的操作类型。

节点结构

对树子节点的描述,通常有两种:

  • 将子节点作为数组,保存在父节点中
  • 将子节点保存为链表,只将头结点保存在父节点中

第二种方法的优点,比缺点多得多。第二种除了对子节点的索引访问不易之外,其他的操作都要比第一种方便。不用预先声明长度,能方便地拼接,删除。 
但最大的优点,是能够方便的实现缓存机制。重复的数据,能让多个节点指向同一个链表头结点,实现复用。而第一种方案则会复杂得多。 
因此,我们采用第二种策略作为树表的存储结构。

计算

  • 在不同节点读取数据,值为子节点值的组合
  • 在不同节点写入数据,节点负责将数据分配到不同子节点存储
  • 删除一个节点,对应的子节点都会被删除
  • 展平一个节点,将该节点替换为其子节点的头结点
  • 将节点拼接到其他子节点上
  • 描述嵌套结构,子节点的下一个节点指向父节点。
  • 同级节点的推导,如果父节点提供计算能力,则子节点能够被计算并返回结果
  • 转换为xml,json等递归结构类型

应用

从HTML中自动提取树表 

这几乎是树表最正常的用途,随便看一个html的例子,数据都是以树结构存储的,没有明确的列名,但其层级关系却表现了数据的关联性。


<div class="other">
    <div class="con">
        <a href="http://bj.lianjia.com/ershoufang/wangjing/"  data-el="region">望京二手房
        </a>
        <span>/</span>
        中楼层(共26层)
        <span>/</span>
        1997年建塔楼
    </div>
</div

我们很难通过树结构,自动标注“1997年建板楼”的列名,但却知道,它和“中楼层”属于一个层级。这样,自动清洗html就会方便地多。

信息抽取 
信息抽取的结果,一般是树,还是之前时间的例子,12:03提取子信息后,就变成了12点和03分,分别成为了12:03的两个子节点。 
这也同样避免了生成多个列,造成数据重复的问题。

自动推导 
对编译原理有概念的同学,自然会对语法树有印象。语法树代表了当前语句的逻辑结构,分析语法树,能够发现无用冗余节点,或进行规约计算。例如加法(+)的父节点,如果有两个int子节点,那么就可以求和。 
一样的道理,如果在同一层级,分别有长度和宽度,那么这两个指标一般衡量的都是同一个“物体”,那么自然就可以增加“面积”子节点。 
同时,节点可以代表“动作”,也可以保存函数,那么树表本身就提供了自动推导的能力。 
节点的上浮/下沉,都可以通过规则自动实现,而之前对数据上钻和下探,都可以理解为观察树不同的层级而已。 
这极大地简化了编程/推导,甚至能实现一个简单的人工智能。

易于实现Lazy执行 
是否延迟执行,可根据实际要求来决定。如果父节点计算代价高昂,那么可缓存子节点计算值,否则可随时返回子节点的规约新值。 
想要让平面表支持延迟执行,肯定不会太容易。

数据就是对象 
想象一下,以后访问一个数据表,都能通过object.property.subproperty来访问了,那种感觉多爽,还要什么ORM!

缺陷

树表最大的缺陷,是它对用户不友好,理解扁平的表结构是很容易的,但如果看到一片森林,肯定不少程序员会晕菜,普通用户更是不必说,所以这种审查数据的方式显然只应该在后台,面向程序员。 
我们可以用Excel等工具方便地查看表结构,但树表怎么看?这也同样需要可视化设计器,好在这种事情是苦力活,并不难做。

展望

想象一下以后如何处理和清洗数据,把树的某个节点拖到垃圾箱,这一列就自动删除了,可以新建某个层级的节点,然后添加几个节点的连线,它就自动成了它们的父节点;节点和节点之间可以插入新的计算节点,定义新的层级。也可以随时查看不同层级的数据,从而实现更好的洞察力。这一切简直太酷了。

这个问题,确实是我在实际开发爬虫和数据清洗工具时遇到的,平面表格大量的中间计算结果,重复列,无法定义的列名,让我深感平面模式的弊端,我甚至都已经迫不及待地开发这样的数据处理工具,以替代之前的工具。不过,在一切都不明朗之前,这种计划还是往后推一推吧。

有任何问题,欢迎随时讨论。


版权声明:本文内容由互联网用户自发贡献,本社区不拥有所有权,也不承担相关法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:yqgroup@service.aliyun.com 进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。

用云栖社区APP,舒服~

【云栖快讯】哪个编程语言最热门?各个专业领域的技术趋势是什么?如何才能更快速的踏上技术进阶之路……云栖社区2017中国开发者大调查火热进行!答卷可抽奖,红轴机械键盘、天猫精灵,丰富好礼大概率抽取  详情请点击

网友评论

是一种简单易用的云计算资源管理和自动化运维服务。用户通过模板描述多个云计算资源的依赖关系、配置等,并自动完成所有... 更多>

是解决用户结构化数据搜索需求的托管服务,支持数据结构、搜索排序、数据处理自由定制。 为您的网站或应用程序提供简单... 更多>

支持MySQL、SQL Server、PostgreSQL、MongoDB、Redis等关系型数据库和NoSQL... 更多>

为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效率,降低 IT 成本... 更多>
安全技术百问

安全技术百问