沙漠之鹰123
TA的个人档案
个人介绍
暂无个人介绍
擅长的技术
- 高分内容
- 最新动态
- 文章
- 问答
-
发表了文章 2016-04-21
Factory模式与Prototype模式的异同
原型模式与工厂模式的定义，本文不想在这讲太多，本文主要想在这讲一下对原型模式的一些误解－－将原型模式等价于工厂模式； 为什么会产生这种误导呢？其实也不是我们的错，关键在于设计模式这本书以及网上的其它资料很喜欢将原型和工厂方法进行比较，从而导致我们误解了原型引入的本质意义。按我的理解，原型引入的根本原因就是在于它可以利用一个原型对象（在这，我指的是实例，而非类），快速地生成一批和原型对象一样的实例。举个例子来说，你有一个类A的实例a (A a=new A()),现在你想生成一个和a一样的实例b,那么，按照原型的定义，你应该可以这样做b=a.clone()。这样，你就可以得到一个和a一模一样的实例b(即a和部b的数据成员的值完全一样）。 上面是原型的一个简单说明，那么引入原型有什么好处呢？按我的理解，就是在于：你如果要生成一大批很相像的类的实例时，省得每次去做重复的赋值工作。再举个例子，如果你有一个类A,它有十个成员变量，现在你打算生成100个A的实例，而这些实例的变量值大部分相同（比如说七个相同），只有一小部分不一样（比如说三个），那么如果没有Prototype,那么你就得每次New一个A的对像，然后赋值，这样，你要重复100次同样的七个变量的赋值工作，显然，这样很麻烦。现在你有了原型，那么问题就简单了，你只要生成一个A的实例，再通过clone来生成其它的实例，然后再一一修改其它实例不同的地方。 可能我这么讲，大家不信，那下面，再让我们来看看Java中活生生的原型应用。 学过Java的人都知道，在Java中,有一个clone()函数，这个函数的功能，就是返回一个和当前调用它的对象一样的实例。那么Java中为什么要引入这个函数呢？在<<Think in Java>>一书中，作者如是解释： 如果，你要将一个对象的引用作为参数传进去，但又不希望函数改变对象的值，那么，你该怎么办？由于在Java中对对象没有像C++那样的Const修饰符，所以，为了实现这个功能，Java中引入了clone函数，使得你将对象的引用作为参数传进函数时，这个函数可以调用该对象的Clone方法生成该对象的一份拷贝，从而达到不修改原对象的目的。 我之所以用上面这么多篇幅来讲述原型本质，目的就在于希望各位不要像我一样，把原型的功能与它的意义给混了，以致于当真正要使用原型来解决问题时，却不知可以使用它。 好了，上面说了原型的本质意义－－至少我认为是这样的。那为什么很多资料喜欢将原型同工厂模式进行比较呢？不知是不是巧合，虽然原型引入的初衷是像我上面所说，但他实现起来，却又完全可以达到工厂模式的郊果（后面，我会用代码实现可以用工厂模式实现的Mac,Win产品系列生成问题）。而且，用起来甚至比工厂模式更方便、灵活。对于工厂模式与原形模式在功能上的这点巧合，我想也许是因为本来工厂模式和原型模式都是创建型模式，这样，他们的基本功能都能生成对象，因而使得原型模式在功能上可以代替工厂模式。对这两种模式在功能上的相同点，程序员2001年第11期杂志上有一篇”非鱼“写的文章，作者理解得非常巧妙，即：如果你将工厂模式的UMl图对折，你得到的就是Prototype原型的UML图。有兴趣比较这两种模式的朋友，可以去参考这篇文章。 接下来，让我们在实现机制上来看看原型模式为什么可以实现工厂模式的功能(本文只限于Java语言）。在Java中，对于原型的实现，其实根本不用我们做，在object类中早就定义了一个clone函数，而这个函数，就使得我们可以动态地生成对象的当前拷贝。即然这样，那么让我们来看看，如果要实现工厂模式的功能，我 们该如何使用原型模式为做到呢？ 工厂模式实现的生产产品的功能，关键是利用了继承的特性。也就是说，你生成的产品，一定是由同一个抽象产品类派生出来的。所以，在工厂模式下，你如果要生成一类产品，就要引入一个抽像产品类，然后再由它派生出具体产品。同样，在原型模式中，你完全可以同样定义一个这样的“抽象产品－－具体产品”层次，再利用具体产品本身的clone功能来产生具体产品本身。从而达到实现工厂模式功能的目的。可能说到这，大家有点糊涂了。实际上，在原型模式中，每个具体产品就扮演了工厂模式里的具体工厂的角色（为什么会这样，其实很简单，因为，每个具体产品都具有生成 自己拷贝的功能？从这种意义上讲，难道这不正是工厂的作用吗？）。另外，要在Java中利用原形模式实现工厂模式的功能，则更为简单，因为object已经为我们实现了clone函数，且对于clone方法，Java中默认是：如果A是父类且A实现了clone函数，B是A的子类，则B不用实现clone函数，它只要调用父类的clone函数，Java就会在运行时动态地为我们生成正确的B的对象。理解这点的关键在于，所有类实现的clone操作都是调用object的clone方法。这也就是说，我上面所说的父类A根本就不用自己实现clone方法，而仅仅是调用父类（object)的clone方法而已。好，到了这，读者也许又有疑问了，既然所有的cloen操作都是由object实现的，而在java中所有的自定义类默认都是由object派生而来，那这样的话，应该所有的类都自动就具有了clone自己的能力？ 确实，如果object不将它的clone函数声明为protect的话，情况的确如此。但Java为了安全方面的原因，所以没有将clone方法公开，而是声明为保护类型，这样的话，子类是不可以直接调用object类的clone方法的，而必须做到如下两点： 1.必须实现Cloneable接口； 2.必须声明一个clone方法，来调用object的clone函数； Java在调用父类的clone函数时，都会在运行时动态地进行检查，如果发现调用的类不符合上面的任何一点，则会抛出一个异常。 明白了上面的原因，那么如果我们希望某个类具备clone自身的能力，那么，我们可以这样做： 1.直接按上面所说，自己实现clone操作； 2.声明一个抽象父类，实现上面的clone操作并将它声明为公开方法，再由此类派生出子类，这样，所有的 子类只要调用父类的clone方法，就能够正确地拷贝自己。 通常，我们都是使用第一种方式，但在我们现在讨论的如何用原型模式实现工厂模式的功能的问题中，我们最好是采用第二种方式。 最后，让我们通过具体的代码来看看如何用Prototype模式实现工厂模式的功能。 问题： 现有两类产品 1－Ram,2--Cpu,现在要生成具体的产品 MacRam,MacCpu和WinRam,WinCpu. 代码如下： /** *A:Abstract *C:Concrete */ /** 定义抽象产品Ram的类 APrototypeRam * 同时他也是抽象工厂 */ abstract class APrototypeRam implements Cloneable { public Object clone() { Object o=null; try { o=super.clone();//调用父类，即Object的clone() } catch(CloneNotSupportedException e) { System.err.println("APrototypeRam is not cloneable!"); } return o; } } /** 定义抽象产品Ram的类APrototypeProductCpu * 同时他也是抽象工厂 */ abstract class APrototypeCpu implements Cloneable { public Object clone() { Object o=null; try { o=super.clone();//调用父类，即Object的clone() } catch(CloneNotSupportedException e) { System.err.println("APrototypeCpu is not cloneable!"); } return o; } } /** 定义具体产品MacRam的类CPrototypeMacRam * 同时他也是具体工厂 */ class CPrototypeMacRam extends APrototypeRam{ public String toString() { return "MacRam"; } } /** 定义具体产品WinRam的类CPrototypeWinRam * 同时他也是具体工厂 */ class CPrototypeWinRam extends APrototypeRam { public String toString() { return "WinRam"; } } /** 定义具体产品MacCpu的类CPrototypeMacCpu * 同时他也是具体工厂 */ class CPrototypeMacCpu extends APrototypeCpu{ public String toString() { return "MacCpu"; } } /** 定义具体产品WinCpu的类CPrototypeWinCpu * 同时他也是具体工厂 */ class CPrototypeWinCpu extends APrototypeCpu{ public String toString() { return "WinCpu"; } } /** 客户端，使用CPrototypeRam和CPrototypeCpu生成如下产品 * MacRam,MacCpu,WinRam,WinCpu */ public class Prototype { public static void main(String[] args) { /** * 在生成产品之前，先生成原型产品，以便后面利用它们成批生产相同产品 * 其作用等价于产品工厂 */ CPrototypeMacRam prototypeMacRam=new CPrototypeMacRam(); CPrototypeWinRam prototypeWinRam=new CPrototypeWinRam(); CPrototypeMacCpu prototypeMacCpu=new CPrototypeMacCpu(); CPrototypeWinCpu prototypeWinCpu=new CPrototypeWinCpu(); CPrototypeMacRam MacRam=(CPrototypeMacRam)prototypeMacRam.clone(); CPrototypeWinRam WinRam=(CPrototypeWinRam)prototypeWinRam.clone(); CPrototypeMacCpu MacCpu=(CPrototypeMacCpu)prototypeMacCpu.clone(); CPrototypeWinCpu WinCpu=(CPrototypeWinCpu)prototypeWinCpu.clone(); System.out.println("打印原形产品与它的克隆产品与比较异同!"); System.out.println("prototypeMacRam:"+prototypeMacRam+" Cloned:"+MacRam); System.out.println("prototypeWinRam:"+prototypeWinRam+" Cloned:"+WinRam); System.out.println("prototypeMacCpu:"+prototypeMacCpu+" Cloned:"+MacCpu); System.out.println("prototypeWinCpu:"+prototypeWinCpu+" Cloned:"+WinCpu); } } 通过上面代码，我们可以清楚地看到，用Prototype模式实现工厂模式更为简单，如果再配上原型管理器的话，那么Prototype模式则会变得更为灵活，限于篇幅，本文没有讲到原型管理器，有兴趣的朋友可以参看后文列出的参考文献。但同时，我们也发现，使用原形模式时，有一个不足之处，即在客户端代码里，我们必须显示进行类型转换，这样可能导致错误。为了改正这一点，我想，我们可以使用真正的工厂模式将Prototype模式再封装一遍。对工厂模式的这项功能，恐怕，Prototype原形模式就无能为力了。 总之，工厂模式和原形模式虽然在引入目的上不同，但在实现上，原形模式可以实现工厂模式同样的功能。但读者也不要因为这样，而将两者混为一体，因为，反过来，在将原形模式作为生成本身拷贝的这项功能使用时，工厂模式根本无法取代它。
-
发表了文章 2016-04-21
[XMove-自主设计的体感解决方案] 系统综述
编者注： X-MOVE是作者在业余时间于2010年6月份启动的以运动传感开发，算法和应用的平台，目前已经发展了三个版本，第四版的开发接近尾声。发布在博客园仅为交流技术，不存在商业目的，作者保留一切权利。 一 . XMOVE 系统简介 X-MOVE是作者于2010年本科四年级年启动的运动传感模拟，建模和计算的平台，已经发展到第四代。利用优秀算法和自主设计的硬件，充分发挥传感器能力，搭建起全新人机交互和动作传感解决方案，并努力实现产品级成熟度。 目前开发了以下应用： 全身动作捕捉和重现 对使命召唤(COD)，街霸，HAWX等主流游戏的体感控制的支持 空中3D鼠标（包含动作识别） 手机屏幕实现电脑触摸板 虚拟现实和远程机械控制 电子指南针 传感器数据采集，分析和重现 其他应用 系统涉及以下关键技术： 作者的目标是将其开发为开放的，可扩展的体感开发和应用平台，以实现以下愿景： XMove是一套可拓展的开放体感系统框架， 可以通过USB,蓝牙，WIFI,3G,串口甚至Kinect等通信方法，接收来自不同传感器，不同节点（包含手机和自制传感器）的数据，通过传感器融合算法，向应用层提供统一和完整的运动数据和扩展信息。以实现在常规环境下，对人体动作的实时监测和输出。 尽最大可能满足高可靠和低功耗设计，并支持异构自组网。 XMove的硬件家族 手持硬件传感器： 系统的实现了三层框架，向上提供统一的传感器数据和API。 虚拟游戏引擎和全身人体动作位置监控演示： XMOVE软件界面系统: 自制嵌入式OS的内置传感器监测显示： 演示视频： 二. XMOVE开发文章系列列表 目前作者已经基本完成大部分的开发任务。作者亦获得了颇大的知识和能力收益，为了与有兴趣的网友一起交流，我在博客园开放此系统的部分设计和技术，与志同道合的朋友分享相关信息。其中也会提到我的一些开发心得和工作感受。 作者将不定期的更新文集，已经或将会包含以下内容： XMOVE系统介绍： XMove已开发应用介绍 XMove-Studio PC端应用和开发平台 各代版本发展情况：XMOVE1.0 各代版本发展情况：XMOVE2.0 各代版本发展情况：XMOVE3.0 各代版本发展情况：XMOVE4.0 Android子系统 XMove的无线通信协议简介 第三方开发开放API使用说明 XMOVE3.0嵌入式手持终端介绍 系统综述: 自制的彩屏手持动作感应终端 软件介绍(一):精简型嵌入式系统的菜单实现和任务切换 软件介绍(二):在2KB内存单片机上实现的彩屏GUI控件库 软件介绍(三):在2KB内存单片机上实现的俄罗斯方块 软件介绍(四):在2KB内存单片机上实现的超精简五子棋算法 软件介绍(五):在2KB内存的单片机上实现的T9中文输入法 设计经验 困扰半年之久的MSP430的I2C问题 设计，成本与开发细节的讨论 动态识别和算法 动态动作识别算法介绍 AHRS传感器融合算法介绍 安卓开发 用手机的屏幕作为电脑触摸板！ 安卓的GPS和远程地理定位 安卓3G高速数据通信 安卓手机端通过蓝牙与PC通信的实现 其他 如果您有任何问题，欢迎联系我：buptzym@gmail.com
-
发表了文章 2016-04-21
使用Python和Perl绘制北京跑步地图
当你在一个城市，穿越大街小巷，跑步跑了几千公里之后，一个显而易见的想法是，如果能把在这个城市的所有路线全部画出来，会是怎样的景象呢？ 文章代码比较多，为了不吊人胃口，先看看最终效果，上到北七家，下到南三环，西到大望路，东到首都机场。二环32公里，三环50公里，这是极限，四环先暂时不考虑了。。。。 （本文工程已经托管在Github,https://github.com/ferventdesert/gpx-crawler） 1.数据来源：益动GPS 首先需要原始位置信息，手机上有众多跑步软件，但它们共同的问题是不允许自由导入导出（可能是为了防止用户脱离吧）。因此有一块智能运动手表应该是不二之选。我的是Garmin Fenix3，推荐一下： 与此同时，益动GPS算是业界良心了，能够同步咕咚，Garmin手表，悦跑圈的数据，因此我将其作为一个入口，抓取所有的GPS数据。 至于如何同步，可参考网站上的相关介绍，下面是我登录该网站后的截图： http://edooon.com/user/5699607196/record/15414378 随便点进去以后，就可以看到导出路线的按钮： 无比坑爹的是，它不提供批量导出的按钮，几百条记录，依次导出都累死了。于是考虑用代码来自动化吧。 2. 获取益动网站上的数据 登录之后，可以看出它是动态加载，当滚轮滚到最下时，自动加载后面的内容。本来是应该嗅探和分析http请求的。后来我懒惰了，采取折中方案，拖到底，全部加载完毕后，保存了当前的html文件。 接下来就是解析这个Html,基本上是通过XPath的来做的。有经验的同学看了下图就都明白了： 图中高亮的部分，就是要下载gpx文件的实际地址。我们将其保存在urllist中。同时，元数据被保存在json文件里。 folder = u'D:/buptzym的同步盘/百度云/我的文档/数据分析/datasets/rungps/'; cookie='JSESSIONID=69DF607B71B1F14AFEC090F520B14B55; logincookie=5699607196$6098898D08E533587E82B33DD9D02196; persistent_cookie=5699607196$42C885AD38F59DCA407E09C95BE1A60B; uname_forloginform="buptzym@qq.com"; __utma=54733311.82935663.1447906150.1447937410.1456907433.7; __utmb=54733311.5.10.1456907433; __utmc=54733311; __utmz=54733311.1456907433.7.3.utmcsr=baidu|utmccn=(organic)|utmcmd=organic; cookie_site=auto' userid='5699607196'; f = codecs.open(folder + 'desert.htm', 'r', 'utf-8'); html = f.read(); f.close(); root = etree.HTML(html) tree = etree.ElementTree(root); listnode=tree.xpath('//*[@id="feedList"]'); numre=re.compile(u'骑行|跑步|公里|，|耗时|消耗|大卡'); urllists=[] records=[]; for child in listnode[0].iterchildren(): record={}; temp=child.xpath('div[2]/div[1]/a[2]') if len(temp)==0: continue; source= temp[0].attrib['href']; record['id']=source.split('/')[-1]; info=temp[0].text; numinfo= numre.split(info); if len(numinfo)<6: continue; record['type']= info[0:2]; record['distance']= numinfo[1]; record['hot']=numinfo[6]; urllists.append('http://edooon.com/user/%s/record/export?type=gpx&id=%s' % (userid, record['id'])); 值得注意的是，因为下载时需要cookie，因此读者需要将自己在益动GPS的userid和登录的cookie都替换掉（这种网站不值得为它开发自动登录）。 接下来就是下载的过程，获取导出数据按钮的URL的XPath，构造一个带cookie的请求，然后保存文件即可，非常容易。 opener = urllib.request.build_opener() opener.addheaders.append(('Cookie', cookie)); path='//*[@id="exportList"]/li[1]/a'; for everyURL in urllists: id = everyURL.split('=')[-1]; print(id); url='http://edooon.com/user/%s/record/%s' % (userid, id); f = opener.open(url); html = f.read(); f.close(); root = etree.HTML(html) tree = etree.ElementTree(root); fs = str(tree.xpath(path)[0]); if fs is None: continue; furl = 'http://edooon.com/user/%s/record/%s' % (userid, fs); f = opener.open(furl); html = f.read(); f.close(); filename=folder+'id'+'.gpx'; xmlfile = codecs.open(filename, 'wb'); xmlfile.write(html); xmlfile.close(); 之后，我们便保存了大约300多个gpx文件。 3. 解析gpx数据 所谓gpx数据，是一种通用规范的GPS数据格式，详细的资料可自行搜索。 我们需要使用python的gpx解析器, gpxpy是个好选择，使用 pip3 install gpxpy 即可安装。 gpxpy提供了丰富的接口，当然为了统计，我们只需要提取一部分数据： def readgpx(x): file= open(dir+x+'.gpx','r') txt=file.read() gpx=gpxpy.parse(txt) mv=gpx.get_moving_data() dat= {'移动时间':mv.moving_time,'静止时间':mv.stopped_time,'移动距离':mv.moving_distance,'暂停距离':mv.stopped_distance,'最大速度':mv.max_speed}; dat['总时间']=(gpx.get_duration()) dat['id']=str(x) updown=gpx.get_uphill_downhill() dat['上山']=(updown.uphill); dat['下山']=(updown.downhill) timebound=gpx.get_time_bounds(); dat['开始时间']=(timebound.start_time) dat['结束时间']=(timebound.end_time) p=gpx.get_points_data()[0] dat['lat']=p.point.latitude dat['lng']=p.point.longitude file.close() return dat readgpx函数会读取文件名x，并将一个字典返回。并得到类似下面的一张表： 因为我们只需要绘制北京的区域，因此需要一个坐标表达式筛掉北京之外的地区。筛选代码使用了pandas,在附件里有更详细的代码。 exceptids=详细[(详细.lng<116.1)|(详细.lng>116.7)|(详细.lat<39.9)|(详细.lat>40.1)].id def filtercity(r): sp=r.split('/')[-1].split('.') if sp[1]!='gpx': return False; if sp[0] in exceptids.values: return False; return True; bjids= [r for r in gpxs if filtercity(r)] 这样，我们就将所有在北京完成的运动数据筛选了出来。 4.绘制GPS数据 反复造轮子是不好玩的，绘制gpx已经有比较强大的库，地址在http://avtanski.net/projects/gps/ 很不幸，这个库使用Perl作为开发语言，并使用了GD作为视觉渲染库。我花费了大量的时间，在安装GD上面。 Ubuntu默认安装Perl, GD是需要libgd的，libgd却在官网上极难下载，下载后却又发现版本不对，这让我在国外互联网上遨游了好几个小时，都要死掉了。。。到最后，我才发现，安装libgd库只要下面这一步就可以了： apt-get install libgd-gd2-perl 我觉得这就是apt-get方式坑爹的地方，apt get gd 或者libgd根本找不到，如果不去查，谁知道这么写啊！ 至于Perl的CPan管理工具，哎，不说了都是泪。 接下来下载gd 2.56，解压之后， perl ./Makefile.PL make make install 即可 这份gpx绘制库是这么介绍自己的： This folder contains several Perl scripts for processing and plottin GPS track data in .GPX format. 当然我们不废话，把所有的gpx数据拷贝到sample_gpx文件夹下，然后华丽丽的运行 ./runme.sh 如果没有问题的话，应该是下面这样： 我假设各位读者对bash都已经很熟悉了，更多的需求可以查看runme.sh。 最后得到的结果如下图： 当时看到这个结果，我都惊呆了！这是自己跑了2000公里左右的结果，北京三环内（主要集中在长安街以北）主要的道路都跑遍了，朝阳公园，天坛公园，尤其北三环和北土城路（10号线北段）被我各种虐。每一段白线都是一段故事，每一个点都是我的一个脚印啊！ 5.总结 这文章写得显然不够详细，远远没有hand by hand。而且并没有提供更多的数据分析（显然这些工作我都做了）不过相信跑步的程序员一定都很厉害，我这就权作抛砖引玉了。 其实完全可以做成一个web服务，跑友们上传自己的跑步软件的id，就可以自动渲染出各种漂亮的跑步路径和分析图，应该会很有意义吧！ 这件事情花费了我七八个小时，简直吐血，大量的时间用在了如何安装GD上，而不是下载数据上。教训告诉我，一定要读安装包里自带的说明文档，因为库和库之间的版本不同，因此可能造成版本地狱，到时候新版本卸载不了，老版本没法用的时候可别说我没提醒啊！ 值得一提的是，益动gps下载的gpx文件不带换行符，这导致gpx_disualization库无法解析它（这货正则表达式写错了），我懒得再去动perl正则，于是通过替换增加了换行符。 GD还需要libpng等一众perl库，在附件里都有提供下载。 附件是GD库和爬取所有gpx数据的python3代码。
-
发表了文章 2016-04-21
简洁的序列预测算法
计算机和人的最大区别在于，人具备彻底的学习和强大的联想能力，而计算机则不同，只能在程序员给定的框架内进行简单的学习（与其说是学习，不如说是参数微调）。 人类可以很容易的发现特有的模式，比如看下面几个例子: 然而，如此简单的模式，计算机却无法发现，但如果能让计算机学习这种模式，那无疑是非常有价值的。 我们的目标，是给定一串序列： 找出其中的规律，并能够推断之后的序列sn，直到无穷，或是序列结束。本文是笔者独立思考得到的，没有参考其他学术论文，如果有更好的方法，欢迎批评指正。 如果不限制模式的长度，那么这个问题可能是无解的，即使出现一长串的A,我们也不能就只认定这就是A的重复序列，很有可能后面会出现B。因此，必须给问题增加限制条件。 模式是递归定义的，对ID=2的例子，是ABC的重复，内部又是一个递增数组。ID=1的例子，则外部是递增数组，内部是重复。若是ABCCBAABCCBA, 则是重复，重复结构是ABCCBA。 如果要求更高，可以发现内部是一个回环。 重复 重复是最基本，最常见的模式，例如AAAAA,ABCABCABC。处理起来也非常容易: 从起始长度n=1为起点，判断之后的结构是否满足重复条件，如果满足，则算法终止，否则n++，直到n=min(MAXREPEATLEN,len(S))，此时序列不存在重复模式。 我们通常需要对重复段的长度增加限制，比如不超过10。 发现重复后，其表达就是数组[Mode]+ ,Mode为子序列，此时即可推导之后的元素。 值递增递减 考虑这样的序列: ABCDEF... ABCCDEEFG... ABCEFGIJK... 它们没有重复模式，但存在子结构，子结构之间有递增和递减关系。我们的思路，是尽可能地将这种模式退化为重复模式，即可使用重复的方法。 聪明的读者可能已经想到，既然是递增递减，则可使用差分。 对第一个序列，后一个元素减去前面的元素，可得: 11111111.... 第二个序列： 110110110.... 第三个序列： 112112112... 之后，即可调用重复模式的分析思路，解决问题。 我们似乎还没有讨论这样的序列: AA AB AC AD.... 差分求解后，得到的是0,0,1,-1,2,-2,3,-3....这并不是一个重复的序列。 但如果按照相隔一个元素求差分，则顿时开朗： 0101010101... 因此，我们可总结值递增递减的模式分析方法： 从起始差分步进长度n=1为起点，判断之后的结构是否满足值递增递减条件，如果满足，则算法转换为处理重复模式，否则n++，直到n=min(MAXLEN,len(S))，此时序列不存在递增递减模式。 长度递增递减 这种模式，分析起来更为复杂，看下面的例子： A AB ABC ABCD... B EF IJK NOPQ... 1 12 112 1112 11112... (中间的空格，是手工加上便于看清规律的) 这种规律很明显，但并不是重复，也不是值递增递减，它的子结构发生了长度上的变化。 按照上一节的思路，从左到右依次差分计算： 0,1,-1,1,1,-2,1,1,1,-3,1,1,1,1,-4.... 2,1,2,1,1,2,1,1,1,1... 0,1,-1,0,0,1,-1,0,0,0,1,-1.... 我想尽办法，试图能通过某种变换，获得像刚才那样简单有效的转换，发现无果。换一个思路，通过类似概率的手段来分析。仔细观察会发现，出现最多的数字是步进值，第一行和第二行都是1，第三行是0。之后按照步进值分割，就成了下面的增减/重复序列: 0,-1,-2,-3.... 1,-1,1,-1,1,-1... 而且，步进值出现的次数，也是一个递增,递减序列: 1 | 1,1 | 1,1,1 | 1,1,1,1| .... 0 | 0,0 | 0,0,0.... 又可以按照增减，重复序列的方式处理。 总结一下这种方式的伪代码： 原始序列S1从左到右依次差分，得到的序列S2，求取出现次数最多的数字，以此为特征分隔符，即可将序列S2分割为两个序列： 其中SA和SB分别为增减/重复序列。 其他更复杂的序列 大家看了以上的处理思路，是不是希望让计算机去求解公务员考试题目？不好意思，复杂的序列非常多，比如下面的序列: 这个问题靠计算机搜索，几乎是不可解的。如果硬要处理，最终会变成一个离散的多项式拟合问题，到了那个时候就一点都不酷了。 好在，现实世界的流程和结构一般没有那么复杂，比如网页的结构，消息出现的样式，重复占据了绝大多数情况。可能最多出现递增递减和重复嵌套的情况。如果是复杂的序列，上面的检测方法最少能告诉我们，这个序列不是重复/递增递减序列，可能需要用更复杂的方式来处理。对于一般的情形，这样的思路基本够用了。 另外要注意的问题是相等性。我们简化了问题的描述，将序列简化为有明确标示和序号的串。看下面的例子: <name>zhao</name> <job>coding</job> <name>wang<name> <job>eating</job> ... 这是个name,job不断重复的xml文档，在解决模式推断之前，你需要一些手段告诉计算机，第一行和第三行，在一定程度上是相等的。如果不相等，这事没戏了。 额外的有益讨论 从刚才那个例子，可以看出文法推断在自动解析上的好处： 如果能够发现序列的规律，就能自动将其结构化 能在一定程度上预测下一条数据是什么类型，从而提升命中效率 能够发现隐含在数据结构中的规律 文法推断是一项相当复杂的命题，即使序列有特定的规律，即使能找到问题的解，解的数量可能也是非常庞大的。通常使用奥卡姆剃刀原理，即认为正确的文法总是最简单的那个。本文描述的，也只是文法推断中一个最为简单的命题，即序列的模式发现。 更多的真实情况，是序列有规律，但却是符合概率的。下面的例子： AAC AAC AAD AAC AAC AAC AAD... 多数情况出现的是AAC,但有较低的可能性出现AAD，如果能从其中找出规律并推算概率，那么也能解决相当多的问题。不过，就需要大量的数学知识和技巧了，笔者望洋兴叹，只能感慨于造物主对人类大脑的恩赐。 一方面，在表面上看起来毫无意义的噪声，经过某种特定的数学变换，却能从中发现稳定的规律。 只要愿意，任何一串序列都能转换为一个特定的整数，而整数处理起来比序列更为简单和纯粹。序列的分解，可以对应为整数的分解。质数为什么如此重要？因为质数提供了乘法计算中不可分解的“元”。 有任何问题，欢迎各位随时讨论。
-
发表了文章 2016-04-21
用树结构描述和计算数据
描述数据最常见的结构是平面表格，数据库，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等工具方便地查看表结构，但树表怎么看？这也同样需要可视化设计器，好在这种事情是苦力活，并不难做。 展望 想象一下以后如何处理和清洗数据，把树的某个节点拖到垃圾箱，这一列就自动删除了，可以新建某个层级的节点，然后添加几个节点的连线，它就自动成了它们的父节点；节点和节点之间可以插入新的计算节点，定义新的层级。也可以随时查看不同层级的数据，从而实现更好的洞察力。这一切简直太酷了。 这个问题，确实是我在实际开发爬虫和数据清洗工具时遇到的，平面表格大量的中间计算结果，重复列，无法定义的列名，让我深感平面模式的弊端，我甚至都已经迫不及待地开发这样的数据处理工具，以替代之前的工具。不过，在一切都不明朗之前，这种计划还是往后推一推吧。 有任何问题，欢迎随时讨论。
滑动查看更多
暂无更多信息
-
发表了文章
2016-04-21
Factory模式与Prototype模式的异同
-
发表了文章
2016-04-21
[XMove-自主设计的体感解决方案] 系统综述
-
发表了文章
2016-04-21
使用Python和Perl绘制北京跑步地图
-
发表了文章
2016-04-21
简洁的序列预测算法
-
发表了文章
2016-04-21
用树结构描述和计算数据
-
发表了文章
2016-04-21
生成Kindle可读的mobi和PDF电子书
-
发表了文章
2016-04-21
文本自动分割算法
-
发表了文章
2016-04-21
跨语言和跨编译器的那些坑（CPython vs IronPython）
-
发表了文章
2016-04-21
空中鼠标算法原理讨论
-
发表了文章
2016-04-21
强大的语言
-
发表了文章
2016-04-21
布点算法的原理和实现
-
发表了文章
2016-04-21
键盘之道：分享三个月中的思维改变
-
发表了文章
2016-04-21
数据分析写作——程序员的另外一种输出
-
发表了文章
2016-04-21
Lisp和SICP
-
发表了文章
2016-04-21
解决HubbleDotNet搜索引擎索引数据不全的问题
-
发表了文章
2016-04-21
How to write perfect C code
-
发表了文章
2016-04-21
How to make a not-so-boring speech?
-
发表了文章
2016-04-21
Don't let self-built concept imprison yourself
-
发表了文章
2016-04-21
《高效程序员的修炼》 读书笔记
-
发表了文章
2016-04-21
《程序员的呐喊》读书笔记
滑动查看更多
暂无更多信息