正则表达式中尽可能匹配最多的

phpmianshi1个月前 (08-18)模式算法62
基础语法和在线测试https://c.runoob.com/front-end/854首先了解如何用字符来描述字符。1. 在正则表达式中,如果直接给出字符,就是精确匹配。用d可以匹配一个数字,w可以匹...

KD-Tree原理详解

phpmianshi6年前 (2015-11-11)模式算法307

这样就会出现很多长条的分割,对于KDTree来说是很不利的。


为了避免这种情况,需要修改一下算法,纬度的选择的依据为数据范围最大的那一维作为分割纬度,之后也是选中这个纬度的中间节点作为轴点,然后进行分割,分割出来的结果是:



这样的结果对于最邻近搜索是非常友好的。

但是这样做还是有一些不好,就是在树上很可能有一些空的节点,当要限制树的高度的时候,这种方法就不合适了。

构建示例

二维样例:{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}

构建步骤:

1、初始化分割轴:

发现x轴的方差较大,所以,最开始的分割轴为x轴。

2、确定当前节点:

对{2,5,9,4,8,7}找中位数,发现{5,7}都可以,这里我们选择7,也就是(7,2);

3、划分双支数据:

在x轴维度上,比较和7的大小,进行划分:

左支:{(2,3),(5,4),(4,7)}

右支:{(9,6),(8,1)}

4、更新分割轴:

一共就两个维度,所以,下一个维度是y轴。

5、确定子节点:

左节点:在左支中找到y轴的中位数(5,4),左支数据更新为{(2,3)},右支数据更新为{(4,7)}

右节点:在右支中找到y轴的中位数(9,6),左支数据更新为{(8,1)},右支数据为null。

6、更新分割轴:

下一个维度为x轴。

7、确定(5,4)的子节点:

左节点:由于只有一个数据,所以,左节点为(2,3)

右节点:由于只有一个数据,所以,右节点为(4,7)

8、确定(9,6)的子节点:

左节点:由于只有一个数据,所以,左节点为(8,1)

右节点:右节点为空。

最终,就可以构建整个的kd-tree了。

邻近搜索

给定一个KDTree和一个节点,求KDTree中离这个节点最近的节点.(这个节点就是最临近点)

这里距离的求法用的是欧式距离。



基本的思路很简单:首先通过二叉树搜索(比较待查询节点和分裂节点的分裂维的值,小于等于就进入左子树分支,等于就进入右子树分支直到叶子结点),顺着“搜索路径”很快能找到最近邻的近似点,也就是与待查询点处于同一个子空间的叶子结点;然后再回溯搜索路径,并判断搜索路径上的结点的其他子结点空间中是否可能有距离查询点更近的数据点,如果有可能,则需要跳到其他子结点空间中去搜索(将其他子结点加入到搜索路径)。重复这个过程直到搜索路径为空。

这里还有几个细节需要注意一下,如下图,假设标记为星星的点是 test point, 绿色的点是找到的近似点,在回溯过程中,需要用到一个队列,存储需要回溯的点,在判断其他子节点空间中是否有可能有距离查询点更近的数据点时,做法是以查询点为圆心,以当前的最近距离为半径画圆,这个圆称为候选超球(candidate hypersphere),如果圆与回溯点的轴相交,则需要将轴另一边的节点都放到回溯队列里面来。


判断轴是否与候选超球相交的方法可以参考下图:



下面再用一个例子来具体说一下查询的过程。

假设我们的k-d tree就是上面通过样本集{(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)}创建的。
我们来查找点(2.1,3.1),在(7,2)点测试到达(5,4),在(5,4)点测试到达(2,3),然后search_path中的结点为<(7,2), (5,4), (2,3)>,从search_path中取出(2,3)作为当前最佳结点nearest, dist为0.141;
然后回溯至(5,4),以(2.1,3.1)为圆心,以dist=0.141为半径画一个圆,并不和超平面y=4相交,如下图,所以不必跳到结点(5,4)的右子空间去搜索,因为右子空间中不可能有更近样本点了。
于是在回溯至(7,2),同理,以(2.1,3.1)为圆心,以dist=0.141为半径画一个圆并不和超平面x=7相交,所以也不用跳到结点(7,2)的右子空间去搜索。
至此,search_path为空,结束整个搜索,返回nearest(2,3)作为(2.1,3.1)的最近邻点,最近距离为0.141。



再举一个稍微复杂的例子,我们来查找点(2,4.5),在(7,2)处测试到达(5,4),在(5,4)处测试到达(4,7),然后search_path中的结点为<(7,2), (5,4), (4,7)>,从search_path中取出(4,7)作为当前最佳结点nearest, dist为3.202;
然后回溯至(5,4),以(2,4.5)为圆心,以dist=3.202为半径画一个圆与超平面y=4相交,如下图,所以需要跳到(5,4)的左子空间去搜索。所以要将(2,3)加入到search_path中,现在search_path中的结点为<(7,2), (2, 3)>;另外,(5,4)与(2,4.5)的距离为3.04 < dist = 3.202,所以将(5,4)赋给nearest,并且dist=3.04。
回溯至(2,3),(2,3)是叶子节点,直接平判断(2,3)是否离(2,4.5)更近,计算得到距离为1.5,所以nearest更新为(2,3),dist更新为(1.5)
回溯至(7,2),同理,以(2,4.5)为圆心,以dist=1.5为半径画一个圆并不和超平面x=7相交, 所以不用跳到结点(7,2)的右子空间去搜索。

至此,search_path为空,结束整个搜索,返回nearest(2,3)作为(2,4.5)的最近邻点,最近距离为1.5。



所以在搜索中可能会出现不同的情况,比如下面的两张图就是比较极端的两个例子。



代码清单

以下是k-d树的c++代码实现,包括建树过程和搜索过程。算法main函数输入k-d树训练实例点,算法会完成建树操作,随后可以输入待查询的目标点,程序将会搜索K-d树找出与输入目标点最近邻的训练实例点。本程序只实现了1近邻搜索,如果要实现k近邻搜索,只需对程序稍作修改。比如可以对每个结点添加一个标记,如果已经输出该结点为最近邻结点,那么就继续查找次近邻的结点,直到输出k个结点后算法结束。

简介kd树(k-dimensional树的简称),是一种分割k维数据空间的数据结构。主要应用于多维空间关键数据的搜索(如:范围搜索和最近邻搜索)。一个KDTree的例子上图的树就是一棵KDTree,形...

腾讯面试题:10G 个整数,乱序排列,要求找出中位数。内存限制为 2G。

phpmianshi7年前 (2015-04-14)模式算法480
题目:在一个文件中有 10G 个整数,乱序排列,要求找出中位数。内存限制为 2G。只写出思路即可(内存限制为 2G的意思就是,可以使用2G的空间来运行程序,而不考虑这台机器上的其他软件的占用内存)。关...

归并排序,外排序,10G文件500M内存的排序

phpmianshi7年前 (2015-04-13)模式算法564
归并排序,外排序,10G文件500M内存的排序
归并排序可以是一种外排序, 外排序是指利用外存也就是磁盘进行排序的一种简称。典型的应用是hadoop 的 mapreduce 的merge 阶段归并排序的: 假设有n 个元素, 将n 个元素分程x 组...

在Laravel中正确地应用 Repository设计模式

phpmianshi8年前 (2014-04-15)模式算法246
在Laravel中正确地应用 Repository设计模式
概念在本文中,我会向你展示如何在 Laravel 中从头开始实现 repository 设计模式。repository 设计模式允许你使用对象,而不需要了解这些对象是如何持久化的。本质上,它是数据层的...

Laravel中用到的设计模式

phpmianshi8年前 (2014-04-10)模式算法1318
1:工厂模式Auth::user()此处Auth这个类就是工厂中的方法,Auth是注册树中的别名。好处:类似于函数的封装,使对象有一个统一的生成(实例化)入口。当我们对象所对应的类的类名发生变化的时候...

Laravel神奇的IoC容器

phpmianshi8年前 (2014-04-09)模式算法841
Laravel 的核心就是一个 IoC 容器,根据文档,称其为“服务容器”通过举例来让读者去理解什么是 IoC(控制反转) 和 DI(依赖注入)超人和超能力,依...

Laravel中的基本概念

phpmianshi8年前 (2014-04-08)模式算法697
一.什么是 DI依赖注入/IOC控制反转DI依赖注入啥都不说,直接上代码<?php     class UserController ...

设计模式概览

phpmianshi8年前 (2014-04-07)模式算法549
设计模式设计模式的世界丰富多彩,比如生产一个个「产品」的工厂模式,衔接两个不相关接口的适配器模式,用不同的方式做同一件事的策略模式,构建步骤稳定、根据构建过程的不同配置构建出不同对象的建造者模式等。面...

代理模式、桥接模式、中介者模式区别和联系

phpmianshi10年前 (2012-05-08)模式算法1007
联系    在现实生活中,如房屋中介、买房人、卖房人,房屋中介是一个中介,因为它担任买房人和卖房人之间的相同;房屋中介也是一个代理,它在卖房人眼前是买房人的代理,在卖房人...

php中介者模式

phpmianshi10年前 (2012-05-07)模式算法409
概念中介者模式用于开发一个对象,这个对象能够在类似对象相互之间不直接相互的情况下传送或者调解对这些对象的集合的修改。一般处理具有类似属性,需要保持同步的非耦合对象时,最佳的做法就是中介者模式。PHP中...

php中的状态模式

phpmianshi10年前 (2012-05-06)模式算法356
概念状态模式当一个对象的内在状态改变时允许改变其行为,这个对象看起来像是改变了其类。状态模式主要解决的是当控制一个对象状态的条件表达式过于复杂时的情况。把状态的判断逻辑转移到表示不同状态的一系列类中,...

php中的模板模式

phpmianshi10年前 (2012-05-05)模式算法596
概念在模板模式(Template Pattern)中,一个抽象类公开定义了执行它的方法的方式/模板。它的子类可以按需要重写方法实现,但调用将以抽象类中定义的方式进行。定义一个操作中的算法的骨架,而将一...

php中的依赖注入模式

phpmianshi10年前 (2012-05-04)模式算法364
概念依赖注入模式(Dependency Injection),用松散耦合的方式来更好的实现可测试、可维护和可扩展的代码。依赖注入模式是控制反转(Inversion of Control)的一种实现方式...

php中的流接口模式

phpmianshi10年前 (2012-05-03)模式算法569
概念 流接口模式(Fluent Interface)用来编写易于阅读的代码,就像自然语言一样(如英语),最关键的一步是:操作函数中必须 return $this,即返回本对象,以调用后续的方...

php中的数据映射模式

phpmianshi10年前 (2012-05-02)模式算法458
概念数据对象映射模式,就是将对象和数据存储映射起来,对一个对象的操作会映射为对数据存储的操作,数据映射模式使您能更好的组织你的应用程序与数据库进行交互。大家如果用过 thinkphp 这个框架,应该知...

php中责任链模式

phpmianshi10年前 (2012-04-28)模式算法440
概念又叫职责链模式。包含了一些命令对象和一些处理对象,每个处理对象决定它能处理那些命令对象,它也知道应该把自己不能处理的命令对象交下一个处理对象,该模式还描述了往该链添加新的处理对象的方法。示例情景一...

php中spl库观察者模式接口

phpmianshi10年前 (2012-04-27)模式算法558
PHP-SPL标准库中实现了观察者模式接口,PHP内置提供了两个接口来供外部应用区实现这个模式。<文档>http://www.php.net/manual/zh/splobserver.u...

php中策略模式详解

phpmianshi10年前 (2012-04-26)模式算法459
概念在策略模式(Strategy Pattern)中,一个类的行为或其算法可以在运行时更改。这种类型的设计模式属于行为型模式。场景场景1:假设现在要设计一个购物车系统,一个最简单的情况就是把所有货品的...

php中的代理模式

phpmianshi10年前 (2012-04-25)模式算法678
概念代理模式(Proxy)为其他对象提供一种代理以控制对这个对象的访问。使用代理模式创建代理对象,让代理对象控制目标对象的访问(目标对象可以是远程的对象、创建开销大的对象或需要安全控制的对象),并且可...