IT牛人博客聚合

前两天发布那个rsync算法后，想看看数据压缩的算法，知道一个经典的压缩算法Huffman算法。相信大家应该听说过 David Huffman 和他的压缩算法—— Huffman Code，一种通过字符出现频率，Priority Queue，和二叉树来进行的一种压缩算法，这种二叉树又叫Huffman二叉树 —— 一种带权重的树。从学校毕业很长时间的我忘了这个算法，但是网上查了一下，中文社区内好像没有把这个算法说得很清楚的文章，尤其是树的构造，而正好看到一篇国外的文章《A Simple Example of Huffman Code on a String》，其中的例子浅显易懂，相当不错，我就转了过来。注意，我没有对此文完全翻译。

查看全文: http://www.udpwork.com/item/7339.html

rsync是unix/linux下同步文件的一个高效算法，它能同步更新两处计算机的文件与目录，并适当利用查找文件中的不同块以减少数据传输。rsync中一项与其他大部分类似程序或协定中所未见的重要特性是镜像是只对有变更的部分进行传送。rsync可拷贝／显示目录属性，以及拷贝文件，并可选择性的压缩以及递归拷贝。rsync利用由Andrew Tridgell发明的算法。这里不介绍其使用方法，只介绍其核心算法。我们可以看到，Unix下的东西，一个命令，一个工具都有很多很精妙的东西，怎么学也学不完，这就是Unix的文化啊。

本来不想写这篇文章的，因为原先发现有很多中文blog都说了这个算法，但是看了一下，发现这些中文blog要么翻译国外文章

查看全文: http://www.udpwork.com/item/7314.html

这是《小波变换和motion信号处理》系列的第一篇，基础普及。第二篇我准备写深入小波的东西，第三篇讲解应用。

记得我还在大四的时候，在申请出国和保研中犹豫了好一阵，骨子里的保守最后让我选择了先保研。当然后来也退学了，不过这是后话。当时保研就要找老板，实验室，自己运气还不错，进了一个在本校很牛逼的实验室干活路。我们实验室主要是搞图像的，实力在全国也是很强的，进去后和师兄师姐聊，大家都在搞什么小波变换，H264之类的。当时的我心思都不在这方面，尽搞什么操作系统移植，ARM+FPGA这些东西了。对小波变换的认识也就停留在神秘的“图像视频压缩算法之王”上面。

后来我才发现，在别的很广泛的领域中，小波也逐渐开始流行。比如话说很早以前，我们

查看全文: http://www.udpwork.com/item/4266.html

这是《小波变换和motion信号处理》系列的第二篇，深入小波。第一篇我进行了基础知识的铺垫，第三篇主要讲解应用。

在上一篇中讲到，每个小波变换都会有一个mother wavelet，我们称之为母小波，同时还有一个father wavelet，就是scaling function。而该小波的basis函数其实就是对这个母小波和父小波缩放和平移形成的。缩放倍数都是2的级数，平移的大小和当前其缩放的程度有关。

还讲到，小波系统有很多种，不同的母小波，衍生的小波基就完全不同。小波展开的近似形式是这样：

其中的就是小波级数，这些级数的组合就形成了小波变换中的基basis。和傅立叶级数有一点不同的是，小波级数通常是orthonormal

查看全文: http://www.udpwork.com/item/4306.html

从前两篇发布到现在，过去一年多了。当初承诺的主要讲解应用的第三篇迟迟没能出炉的原因主要是这个方法用到了我们组的一篇论文中，所以在论文发表之前，不大方便发出来。倒不是说这个方法有多原创创新，只是这是团队工作，我单独提前发出来不大好。

现在这篇论文已经录取发表，所以可以不用顾虑放上来了。我本来想讲的东西都在论文中，我也比较懒，就不再翻译一遍了。各位感兴趣的可以从这里下载。因为篇幅原因，和小波相关的文字已经被删除来只剩下不到两页了，不过基本思想还在。总的来说，就是我们希望用一个简单有效的方法，能达到这样一个效果：在你乘车的时候，当你的手机随便放在身上哪里，或者是座位上哪里，我们都能把手机感知到的汽车移动信息，和手机载体（比如包，口袋，或

查看全文: http://www.udpwork.com/item/7091.html

相对于英文而言，中文在计算机处理方面有个必须要面对的问题就是中文分词，英文的单词都是空格间隔的，而中文的词语则不同，所以用程序解决中文分词，在很多自然语言处理方面都是首要进行的步骤。

其中最简单的就是最大匹配的中文分词了，比如“今天天气不错”可以分词为“今天/天气/不错”，但是面对一些有歧义的句子时却显得捉襟见肘，于是“南京市长江大桥”就会被分成“南京市长/江/大桥”而不是“南京市/长江/大桥”，于是更好的是基于统计学原理的分词，也就是说看哪种出现的频率更高。
对于一个中文字符串“a1a2a3...an”如何正确的用词语c1,c2..cm表示就是中文分词的任务，也就是说我们要去找寻P(c1c2..cm)最大的分词，按照马尔科夫链

查看全文: http://www.udpwork.com/item/7003.html

在计算机科学里，有时间复杂度的概念，然后就有P,NP,NPC,NP-hard的概念，平常大家说的这个题是np的，只能搜了，其实是理解错了np的概念，首先要明确np并不是“不是p”的意思，p大家都清楚是指有多项式时间的算法，而np看全称是“nondeterministic polynomial time”，是说非确定多项式时间，进一步说，正如图片上说的p是属于np的，所有p问题都是np问题。

ok，下面仔细说一下，按照官方的解释呢
p是指在多项式时间能由确定型图灵机解决的问题
np是指在多项式时间能由非确定型图灵机解决的问题
确定型图灵机可以理解为就是按照某种固定的算法，一步步求出解的程序，而非确定型图灵机其实是概念上的，他的

查看全文: http://www.udpwork.com/item/6876.html

我知道这个文章标题很“学术”化，很俗，让人看起来是一篇很牛B或者很装逼的论文！其实不然，只是一份普通的实验报告，同时本文也不对RMM中文分词算法进行研究。这个实验报告是我做高性能计算课程的实验里提交的。所以，下面的内容是从我的实验报告里摘录出来的，当作是我学习hadoop分享出来的一些个人经验。

实验目标

学习编写 Hadoop 上的 MapReduce 程序。

使用 Hadoop 分布式计算小说《倚天屠龙记》里的中文单词频率，比较张无忌身边的两个女人周芷若与赵敏谁在小说里的热度高。（为什么要提到倚天屠龙记呢？因为我的一位舍友最近把贾静雯演的这部戏看完了，他无时无刻不提到贾静雯演的赵敏，所以这个实验也取材自我的大学生活……）

查看全文: http://www.udpwork.com/item/6548.html

Keith Schwarz是一个斯坦福大学计算机科学系的讲师。他对编程充满了热情。他的主页上他自己正在实现各种各样的有意思的算法和数据结构，http://www.keithschwarz.com/interesting/， 目前这个网页上有88个（见下面的列表），但这位大哥要干135个，你可以看看他的To-Do List。

从这个列表上，我们可以看到，他从去年7月份就在自己实现这些东西了，我把他实现的这些算法转过来，

一方面我们可以学习一下这些算法和代码，因为很多东西对我来说都比较新，我以前列举过一些经典的算法，算法和数据结构词典，还有可视化的数据结构和算法， 不过感觉都没有这个全。

另一方面我希望这个事可以影响到一些正在学习

查看全文: http://www.udpwork.com/item/6424.html

先说一下搜索的原理，其实就是不管你搜索什么，都是将你要搜的东西提取出特征值，然后按照特征值比较相似度，按照相似度排序呈献给用户就可以了，所以总共来说需要解决两个问题，一个是如何取得特征值，一个是如何计算相似度。

首先说特征值，特征值可以用图片的颜色比例来，比如python用PIL中的histogram函数就可以得到颜色分布

这幅图的颜色分布直方图是这样的

通过这样我们就得到了一个图像的特征值，这种方法是得到的颜色的分配，还有另一种方式得到的则是图像的内容特征。
基本想法是将图片弄成8*8的小图片这样摒弃掉细节内容，将图片灰度，根据灰度确定一个阈值，然后转换成01矩阵，其他的内容都好说，简要说一下确定阈值的方法，有一个知名

查看全文: http://www.udpwork.com/item/6399.html

排序算法好像是程序员学习编程最多的算法，也可能是算法研究者们最喜欢研究的算法了。排序有很多很多的算法，比如，冒泡，插入，选择，堆，快速，归并等等（你可以看看本站以前的那些文章：可视化的排序，排序算法比较，显示排序过程的python）这里向大家介绍一个“巨NB”的排序算法——Sleep Sort。

闲言少说，请看下面的代码（用Shell脚本写的）

#!/bin/bash
function f() {
sleep "$1"
echo "$1"
}
while [ -n "$1" ]
do
f "$1" &
shif

查看全文: http://www.udpwork.com/item/5332.html

还记得之前发布过的那个关于可视化排序的文章吗？在网上又看到了一个旧金山大学David Galles做的各种可视化的数据结构和基本算法的主页，网址在这里，大家可以看看。我把这个页面的目录列在下面并翻译了一下，大家可以直接点击了。

不知道国内的教育有没有相关的教学课件，至少在我大学的时候是没有的。

基础

Stack栈: 数组实现

Stack栈: 链表实现

Queues队列: 数组实现

Queues队列: 链表实现

Lists列表: 数组实现 ( java 版演示)

Lists列表: 链表实现 ( java 版演示)

索引

Binary Search Trees 二叉检索树

AVL Trees (平衡二叉检索树)

查看全文: http://www.udpwork.com/item/4990.html

又到了向大家介绍一些最近我在网上发现的有价值的东西的时候了。（下面的链接中很多都被墙）

以前向大家介绍过《一些重要的算法》和《算法和数据结构词典》，不过，你知道有些什么样比较奇怪的数据结构吗？wikipedia上的这个词条可以让你看看各种不同的数据结构。比如：Skip lists， Bloom filters，或是什么Dancing links。你也许会像一个以“如何学好C++”中的朋友们所说的，不削于这种所谓的“奇技淫巧”，甚至觉得这太根本不实用。其实，这些东西还是有用的，至少对你开阔思路，活动编程思维能力很有意义。

本站的关于排序的文章有很多，对于排序算法来说，其受到要排序的个数和数据的杂乱程度的影响，我们知道比较稳定的排序

查看全文: http://www.udpwork.com/item/4739.html

最简单的两种排序方式，不多说。

选择排序的第i次循环中选取对应的第i小的数放在list[i]中。

插入排序第次循环把当前待排序的数插入到适当的位置中。

void selection_sort(int *l, int n)
{
int i, j, tmp, min;

for (i = 0; i < n-1; i++) {
min = i;
for (j = i+1; j < n; j++)
if (l[j] < l[min])
min = j;
tmp = l[min], l[min] = l[i], l[i] = tmp;
}
}

void insertion_sort(i

查看全文: http://www.udpwork.com/item/4547.html

最大堆可以用一棵完全二叉树来实现，插入和删除都是O(lgn)的复杂度。

插入的时候先把待插入的元素设为树的最后一个叶子，然后由下往上递归处理，每次都比较子节点（初始为最后一个叶子节点）与父节点的键值大小。若父节点的键值较小，那么父节点下移，直到父节点的键值大于子节点，这就是合适的插入位置。这里可以很容易推导出插入位置前面所有的节点的键值都是大于待插入节点的键值的，而插入位置后面所有的节点的键值都是小于待插入节点的键值的。

删除的时候总是删除树的根。通常情况下删除之后堆还需要用最后一个叶子进行进一步的调整。这个调整是自上而下的。递归地扫描每一层，假如某层节点的子节点的键值小于最后一个叶子的键值，那么这个叶子就应该放在这一层；假如某

查看全文: http://www.udpwork.com/item/4545.html

下面是一个日本程序员制做的一个可视化的排序过程，包括了各种经典的排序算法，你可以调整速度和需要排序的个数。酷壳以前也介绍过几篇相关的文章 一个排序算法比较的网站，一个显示排序过程的Python脚本 关于各种排序算法的运行复杂度比较，请参看Wikipedia的排序算法比较。

相关文章
2010年07月12日 -- 一些重要的算法
2009年04月15日 -- 一个显示排序过程的Python脚本
2009年04月10日 -- 一个排序算法比较的网站
2011年04月06日 -- 一些有意思的文章和资源
2011年03月04日 -- 一些有意思的贴子和工具
2011年02月28日 -- 打印质数的各种算法
2010年07月26日 --

查看全文: http://www.udpwork.com/item/4543.html