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-树的特殊形式
  • 索引
  • 排序:内存不足的情况下可用归并排序
Jul 28

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

1、二叉查找树

  • 时间复杂度(插入、查找、删除):O(log N)(平衡状态) ~ O(N)(不平衡状态)
  • 访问方法:前序、中序、后序遍历法
  • 删除有两个子节点的节点的方法:使用Inorder successor(这个词不知道怎么翻译。。。orz)替换该节点
  • 使用数组存储二叉树:左子节点索引=i * 2 + 1;右子节点索引=i * 2 + 2;父节点索引=(i -1) / 2

2、霍夫曼编码

  • 基本原理:在一段信息中,最常出现的字符使用最少的位(bit)表示,最少出现的字符使用最多的位表示,以达到压缩信息的目的
  • 编码步骤:
    1. 统计信息中各字符出现的次数
    2. 把所有字符放进一个优先队列,以次数为优先级
    3. 从优先队列取出两个元素组成一个二叉树节点,再以两元素的优先级相加作为新的优先级放回优先队列,重复直到队列里只剩下一个元素,该元素即为霍夫曼树
    4. 遍历霍夫曼树建立码表,节点的左叶表示为0,右叶表示为1
    5. 使用码表编码信息
  • 解码步骤:
    1. 定位到霍夫曼树的根部
    2. 逐位读取编码后的信息,遇到0定位到左叶,遇到1定位到右页
    3. 如到达树底部的字符节点,把该字符写入输出,重新定位到树的根部
    4. 重复2、3直到读取完所有信息

3、红黑树

红黑树为一种特殊二叉查找树,可把插入、删除、查找的时间复杂度保持在O(log N)。

性质:

1、所有节点要么是红色,要么是黑色

2、根节点一定是黑色

3、红色节点的子节点是黑色

4、所有从根节点到子节点或空节点(空节点定义为黑色)的路径,必须包含同等数量的黑色节点

在插入及删除节点时将对一些节点进行旋转及改变颜色,以保持4个性质。

节点的旋转:

以节点A为顶点进行左(右)旋转,即使用A的右(左)子节点代替A,A移至新节点的左(右)子节点。如新节点已存在左(右)子节点,则把它移至A的右(左)子节点。

  A          C

  /\          /\

 B C   --〉      A E

   /\         /\

  D E       B D

注:经过旋转后的节点仍然符合二叉查找树的特征

插入步骤:

1、将新节点设置为红色

2、查找插入点

  *)查找时如遇到黑色节点的两个子节点都为红色的情况,则改变这三个节点的颜色(例外情况:如果该节点为根节点,则仍然为黑色),然后修复红红冲突。

3、插入节点,如新节点为根,则把颜色改为黑色

4、插入后,如遇到红红冲突,则进行以下步骤:

  1. 如当前节点为内侧节点(即节点的方向与父节点不同)则进行旋转以转换为外侧节点,继续2
  2. 把祖父节点和父节点(如在2中进行过旋转,则为新节点)的颜色翻转,然后向父节点的反方向旋转

  G          G         N

  /          /          /\

 P   --〉    N    --〉  P G

  \         /

  N       P

 (1)       (2)

注:因为性质1,祖父节点必然存在;因为性质3,其必然为黑色。

删除步骤:

http://en.wikipedia.org/wiki/Red-black_tree#Removal

(不想打了。。。太复杂了。。。orz

Jul 17

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

1、归并排序(Merge Sort)

  • 时间复杂度:O(N log N)
  • 空间复杂度:O(N)
  • 比较次数比快速排序少,但移动次数比快速排序多

2、希尔排序(Shell Sort)

  • 时间复杂度:O(N log2 N)
  • 空间复杂度:O(1)
  • 选择好的间隔能极大提高性能,目前已知最好的间隔为:1, 4, 10, 23, 57, 132, 301, 701,(2.3hn-1)

3、快速排序(Quick Sort)

  • 时间复杂度:O(N log N)
  • 空间复杂度:O(1)
  • 通常情况下为最快的通用排序算法之一,但某些时候复杂度会提升到O(N2)
  • 预先排序第一个、中间及最后一个元素能减少复杂度为O(N2)的概率

Update 7.17:

4、基数排序(Radix Sort)

  • 时间复杂度:O(N)(?)
  • 空间复杂度:O(N)
  • 速度很快,但是只能排序数值类型
Jul 04

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

1、链表

  • 简单链表
  • 双端链表
  • 双向链表

2、抽象数据类型(ADT)

抽象数据类型描述了数据的储存形式及可对数据实现的操作,其具体实现可以有多种形式。

3、迭代器

迭代器用于遍历数据结构内的数据,并可对其进行某些操作。

Jul 03

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

学了4章才想起来做笔记。。。orz

1、无序数组

运算复杂度:

插入:O(1)

删除:O(N)

查找:O(N)

2、有序数组

运算复杂度:

插入:O(N)

删除:O(N)

查找:O(N)(线性搜索),O(log N)(二分搜索)

3、大O表示法(Big O notation,是这样译没错吧囧)

复杂度排序:O(1) < O(log N) < O(N) < O(N log N) < O(N2)

4、二分搜索

运算复杂度:O(log N)

5、简单排序算法

  • 冒泡排序
  • 选择排序
  • 插入排序

运算复杂度:均为O(N2)

空间复杂度:O(1)

效率比较:冒泡 < 选择 < 插入

6、栈、队列

特性:

栈:后入先出(LIFO)

队列:先入先出(FIFO)

 

运算复杂度:插入和删除均为O(1)

7、优先队列

运算复杂度(数组实现):

插入:O(N)(线性搜索),O(log N)(二分搜索)

删除:O(1)

8、逆波兰表达式

Jun 23

VFRHelper – MKV章节制作工具[6.23更新]

话说这东西已经写好很久了。。。最近才完善了一下发上来。

谜之声:真正的原因是因为很久没有发东西了,所以把这个东西弄上来充数。。。

偷下懒,直接把Readme.txt贴出来好了。。。

 

      VFRHelper - MKV章节制作工具(不要问我为什么叫这个名字。。。

更新日志:
1.0.2
	(+)新增1个快捷键
	(+)FFMpegSource更新到1.19
	(-)使用按钮能够正常打开非AVI文件了(低级错误。。。orz
1.0.1
	(+)新增2个快捷键
	(+)快捷键现在可以自定义
	(*)退出程序时会询问是否保留临时文件(如果有的话)
	
1.0.0
	初始版本

功能:
*可视化制作MKV章节文件
*支持打开TXT及XML格式的章节
*支持VFR(只支持V2的Timecode,如果是V1的话请预先转换好
*查看V2 Timecode各帧的时间(附带功能

支持的视频格式:
AVI
AVS
MKV  <---   支持读取内嵌的Timecode
MP4
FLV
以上格式除AVI外均需AviSynth,请自行安装。
MKV、MP4及FLV需要FFMpegSource.dll支持,可将其放在程序目录或者AviSynth插件自动加载目录里。

快捷键说明:
方向键左/右				跳转至上一个/下一个关键帧
Shift+方向键左/右			跳转至上一帧/下一帧(注意:跳转的时候会忽略空帧)
方向键上/下				上一个/下一个章节
空格					设置当前选中章节的时间
F12					解码速度测试(可以无视
快捷键可以自定义,使用记事本之类的工具编辑keymappings.xml即可。按键名称可查看KeyNames.htm获得。

一些注意事项:
*章节文件的格式无法被改变(即只能保存为打开时候的格式)
*新建章节只支持TXT格式
        

 

下载:

带FFMpegSource版

不带FFMpegSource版

内附源代码

 

系统需求:

.Net Framework 2.0

Windows(废话

AviSynth(可选,不安装的话视频格式只支持AVI

源代码编译需求VS2008

Jun 09

泪流满面。。。LibSSA终于写好了

每天只能弄一点。。。结果弄了3个月。。。囧

然后字体精简工具终于能继续了。。。话说那个bug的解决方法之前就想好了,这个库就是为了里面的配套工具写的,原本以为会很快,结果拖了这么久。。。

顺便把解决方法写一下吧。说起来其实很简单,把字体名字改变就可以了。然后再把字幕文件里的字体名字改掉就ok了。