Aug 23

算法与数据结构学习笔记(7)

1、图

图由包含数据的顶点(Vertex)以及代表数据间关系的边(Edge)组成。现实中许多问题都可以用图表示。

  • 图有有向图、无向图、加权图等类型
  • 边可用邻接矩阵(Adjecency Matrix)或邻接表(Adjecency Matrix)表示
  • 图的主要遍历方法有深度优先搜索(DFS)、广度优先搜索(BFS)两种
  • 深度优先搜索使用栈实现,广度优先搜索使用队列实现
  • 最小生成树为连接所有顶点最少所需的边
  • 最小生成树中边的数量为顶点数量-1,且不能有循环
  • 可使用DFS建立最小生成树
  • 拓扑排序(Topological sorting)是把有向无循环图(Directed Acyclic Graph)的顶点按照出现顺序排序

2、加权图(Weighted Graph)

加权图的每条边都有一个权重(Weight),可用于表示距离、时间、价格等。

  • 最小生成树为连接所有顶点的总权重最低的边集合
  • 最小生成树建立方法:任选一个顶点为当前顶点,把所有边以权重作为优先级放入优先队列,从优先队列删除两端顶点均已在最小生成树中连接的边,再取出权重最小的边加入最小生成树。移动到新连接的顶点。重复直到所有顶点均已连接或所有边都测试过。
  • 最短路径问题可用Dijkstra算法解决
Aug 05

算法与数据结构学习笔记(6)

1、散列表

使用散列值作为索引存储数据,若散列函数实现得好,效率可接近O(1)。

处理散列碰撞的方法:

  • 线性跳跃:H1(N)+n
  • 平方跳跃:H1(N)+n2
  • 二次散列:H1(N)+n*H2(N)
  • 在内部使用链表(较简单,但性能会轻微下降)

(H1、H2为散列函数,N为数据,n为碰撞次数)

H2(N)必须与散列表大小互质,否则遇到多次碰撞时会陷入死循环。最简单的方法为确保散列表的大小为质数。

非链表实现的散列表的装入率(Load Factor)超过约三分之二时性能会大大下降。

链表实现的散列表装入率为1.0以下时性能最佳,在高装入率时的性能下降速度也比非链表实现慢,所以在数据量未知的情况下较为适合。

2、堆

堆的内部为一棵完整二叉树,其基本特征为:父节点的数据一定大于(或小于)子节点的数据。堆的基本操作有插入和删除,时间复杂度均为O(log N)。

插入:把新节点放置在完整二叉树的尾部,然后上移(trickle up)到适当位置。

删除:保存二叉树的根节点数据,用二叉树的尾部节点替换根节点,再下移(trickle down)到适当位置(在下移时需要同时比较左子节点和右子节点,否则会破坏基本特征),最后返回保存的数据。

由于删除时返回的数据必定为堆内最大(或最小)的数据,而且时间复杂度比有序数组低,所以堆适合作为优先队列的内部结构。

堆排序:把所有数据插入堆,再取出即可。时间复杂度为O(N log N),但比快速排序慢。

提高堆排序的效率:由于对两个子节点为有效堆的节点进行下移后能得到一个有效堆(参考删除操作),所以可以把数组看成一棵二叉树,从底部的非叶节点开始(叶节点可视作一个有效堆),由右到左从下至上进行下移操作,完成后整个数组即成为一个有效堆。

Aug 04

宠物小精灵M10 HDTVRIP制作手记

折腾了一个多星期终于基本完成了。。。接下来就是发布了。。。这次的处理异常复杂,在这里记录一下。。。

1、搞到片源之后发现和去年的m9HD一样还是有水印。。。抱着一线希望拿出某消logo插件(AVSInpaint,之前在m9上面实验失败。。。),结果发现还是消不干净。。。

2、正准备放弃的时候发现原来有些帧是没有水印的(恶心的片源。。。不对。。。是恶心的电视台。。。),估计就是因为这样导致logo分析有误差。遂把找到的无logo的帧切掉,之后logo就可以消到基本看不见了。

before after

3、中间还有几处大的电视台logo,估计是放广告之后出现的。。。其中几个前后都有重复的帧,所以可以直接砍掉。。。最后还剩下两个要手动处理的。

4、手动处理Part1:这个还是比较容易。。。logo跨越了两个场景,第一个场景完全是静态图,直接用前面的一帧完好帧覆盖掉。第二个场景大部分也是静态的,只有中间有移动。要命的是logo有小部分在移动的地方。。。还好那个位置的颜色比较单一,可以用完好帧覆盖然后强力柔化蒙混过关。。。

71976_1 –>71976_2 –>71976_3

5、手动处理Part2:这部分是最麻烦的。。。logo覆盖部分完全动态,logo有一部分也是动态,没有重复帧。。。本来已经是想忽略这部分了,在压片前越看越不顺眼,于是开始尝试。。。在试过多种方法未果后,逼于无奈使出了最EP的办法。。。

1)先把有logo的片段导出为bmp序列(一百多帧。。。

2)祭出PS为每一帧在有logo的地方做mask(还好有一半是非动态的。。。不然一定做得吐血身亡。。。orz

3)翻出去年的m10 dvdrip(没错,就是dvdrip),调整好大小(这片源还有黑边。。。于是还要慢慢测试。。。)

4)imagesource读入mask,把dvdrip的同一部分切出来,然后overlay上原片

就这个场景弄了我大半天。。。orz

结果:

96262_1 –>96262_2

有一点小瑕疵。。。不过还算可以接受吧。。。

大致就是这样了。。。剩下的还有几帧要ps的就忽略不计了。。。orz

Aug 02

算法与数据结构学习笔记(5)

1、2-3-4树

与红黑树相似,也是一种自平衡树。各类节点的红黑树对应结构,如下:

2-节点:黑色节点

3-节点:黑色节点+红色子节点

4-节点:黑色节点+2个红色子节点

4-节点的分割:新建一个节点,把原4-节点第3个元素移至新节点,并把第3、4个子节点连接至新节点;第2个元素移至父节点,最后把新节点连接到父节点。

2-节点的合并:

(1)从父节点移动与当前节点位置相邻的数据到当前节点,使用相邻节点的第一个或最后一个数据(取决于相邻节点的方向)填补空缺,并把相应的子节点连接到当前节点。

(2)若未合并前相邻节点不是2-节点,则可退出。

(3)若父节点为2-节点且不是根节点,先对其进行合并。

(4)把之前移到父节点的数据移动至当前节点,相邻节点剩余的一个子节点连接至当前节点,并删除相邻节点。如父节点未合并前为2-节点且为根节点,则设置当前节点为新根节点。

2、外部存储

  • B-树:二叉查找树及2-3-4树均为B-树的特殊形式
  • 索引
  • 排序:内存不足的情况下可用归并排序