用树结构描述和计算数据
描述数据最常见的结构是平面表格,数据库,Excel,CSV都是典型的表格。表格是扁平结构,理解起来简单,能方便的增删改查。
下面是一个典型的表格:
所有的子项都是平级的,无法描述它们内在的结构 列名很重要,否则很难确定其语义,这和第一条相辅相成 在数据深度上进行规约和下钻时,不可避免的会造成数据重复。 对列的描述,无法直接保存在表格中,还需要另外建立数据结构存储
如果我们将上面的表格描述成下面的树,这些问题就变得容易解决了:
(父节点)(子节点)12 (子节点): (子节点)03
因此,父节点不需要存储数据,其值是子节点数据的组合,不会有重复。能够明确的描述数据的层级关系和结构,支持在不同层级检索数据,对上面的例子,第一层是12:03, 细分之后,第二层是12和03。
因此,将表格转换为树,笔者将其称为树表,可能会是两种情况:
推荐使用第二种,这样就能方便地将列的元属性记录在节点中,而不造成重复,也可以很容易的将树表打平,变成普通表格。树结构是递归的,因此支持递归操作,下面将讨论树表可能的操作类型。
对树子节点的描述,通常有两种:
将子节点作为数组,保存在父节点中 将子节点保存为链表,只将头结点保存在父节点中第二种方法的优点,比缺点多得多。第二种除了对子节点的索引访问不易之外,其他的操作都要比第一种方便。不用预先声明长度,能方便地拼接,删除。
但最大的优点,是能够方便的实现缓存机制。重复的数据,能让多个节点指向同一个链表头结点,实现复用。而第一种方案则会复杂得多。
因此,我们采用第二种策略作为树表的存储结构。
从HTML中自动提取树表
这几乎是树表最正常的用途,随便看一个html的例子,数据都是以树结构存储的,没有明确的列名,但其层级关系却表现了数据的关联性。
div div a href="http://bj.lianjia.com/ershoufang/wangjing/" data-el="region" 望京二手房 span / /span 中楼层(共26层) span / /span 1997年建塔楼 /div /div
我们很难通过树结构,自动标注“1997年建板楼”的列名,但却知道,它和“中楼层”属于一个层级。这样,自动清洗html就会方便地多。
信息抽取
信息抽取的结果,一般是树,还是之前时间的例子,12:03提取子信息后,就变成了12点和03分,分别成为了12:03的两个子节点。
这也同样避免了生成多个列,造成数据重复的问题。
自动推导
对编译原理有概念的同学,自然会对语法树有印象。语法树代表了当前语句的逻辑结构,分析语法树,能够发现无用冗余节点,或进行规约计算。例如加法(+)的父节点,如果有两个int子节点,那么就可以求和。
一样的道理,如果在同一层级,分别有长度和宽度,那么这两个指标一般衡量的都是同一个“物体”,那么自然就可以增加“面积”子节点。
同时,节点可以代表“动作”,也可以保存函数,那么树表本身就提供了自动推导的能力。
节点的上浮/下沉,都可以通过规则自动实现,而之前对数据上钻和下探,都可以理解为观察树不同的层级而已。
这极大地简化了编程/推导,甚至能实现一个简单的人工智能。
易于实现Lazy执行
是否延迟执行,可根据实际要求来决定。如果父节点计算代价高昂,那么可缓存子节点计算值,否则可随时返回子节点的规约新值。
想要让平面表支持延迟执行,肯定不会太容易。
数据就是对象
想象一下,以后访问一个数据表,都能通过object.property.subproperty来访问了,那种感觉多爽,还要什么ORM!
树表最大的缺陷,是它对用户不友好,理解扁平的表结构是很容易的,但如果看到一片森林,肯定不少程序员会晕菜,普通用户更是不必说,所以这种审查数据的方式显然只应该在后台,面向程序员。
我们可以用Excel等工具方便地查看表结构,但树表怎么看?这也同样需要可视化设计器,好在这种事情是苦力活,并不难做。
想象一下以后如何处理和清洗数据,把树的某个节点拖到垃圾箱,这一列就自动删除了,可以新建某个层级的节点,然后添加几个节点的连线,它就自动成了它们的父节点;节点和节点之间可以插入新的计算节点,定义新的层级。也可以随时查看不同层级的数据,从而实现更好的洞察力。这一切简直太酷了。
这个问题,确实是我在实际开发爬虫和数据清洗工具时遇到的,平面表格大量的中间计算结果,重复列,无法定义的列名,让我深感平面模式的弊端,我甚至都已经迫不及待地开发这样的数据处理工具,以替代之前的工具。不过,在一切都不明朗之前,这种计划还是往后推一推吧。
有任何问题,欢迎随时讨论。
【戏玩算法】08-树结构 转眼间这个系列已经更新到第八篇了,这篇文章将会介绍一下树,树结构在开发中非常的常见,我们来看一下树这个结构是什么样的,有什么特点。
相关文章
- 显示游戏FPS帧率的几种计算方式
- 物联网、云计算、大数据、人工智能怎么区分,又有何关系
- 大数据催生云计算走向规模化发展
- 我们怎样确保从大数据计算中获得价值
- 大数据和云计算究竟有什么关系?
- 大凯哥说大数据(系列一):没有云计算就没有大数据
- 【阿里巴巴大数据实践笔记】第13章:计算管理
- 脱离互联网与云计算去讲数据是个大误区
- 我们怎样确保从大数据计算中获得价值
- 大数据和云计算究竟有什么关系?
- 存储、传输、计算巧实现,基因数据上云不再难
- 比Hive还快10倍的大数据计算引擎
- Open3D 计算点云平均密度(版本二)
- Open3D——计算三维空间中点到直线的距离
- 基于表格存储的高性能监控数据存储计算方案
- 外送类-间隔15分钟,计算事时间效果demo(整理)
- Python之GUI:基于Python的GUI界面设计的一套AI课程学习(机器学习、深度学习、大数据、云计算等)推荐系统(包括语音生成、识别等前沿黑科技)
- ML之SIFT_FLANN:FLANN算法的简介、使用方法(对图片提取SIFT特征并利用FLANN方法实现计算图像相似度并可视化案例)之详细攻略
- python difflib 文本相似度计算代替NLP度量指标BELU
- 未来云原生世界的“领头羊”:容器批量计算项目Volcano 1.0版本发布
- 基于matlab的GA遗传优化计算抛物线的最大值
- 用树结构描述和计算数据
- 【结构化思考】边缘计算架构 3D模型参考
- 大约值的计算
- 关键路径的计算
- 华为云计算基础之Fusion Compute介绍
- 华为HCIE云计算之Rainbow8.0.0版本迁移windows实战
- 都是 HBase 上的 SQL 引擎,Kylin 和 Phoenix 有什么不同?——Kylin 利用 MapReduce/Spark 将原始数据进行聚合计算,转成了 OLAP Cube 并加载到 HBase 中,以 Key-Value 的形式存储。Cube 按照时间范围划分为多个 segment,每个 segment 是一张 HBase 表,每张表会根据数据大小切分成多个 region
- 【GPU】Nvidia CUDA 编程中级教程——数据复制与计算的重叠
- Vue3中computed计算属性函数
- 【计算机架构】如何计算 CPU 动态功耗