Programming interview questions, tips and knowledge, system design, big data.

今天花时间把 github使用中的一些疑点消灭一下。 ###fork & watch & star 到 github 中某人的某个 repo中，会在右上角看到这样的标签： 原来一直困惑为啥要有三个，一个 fork 不就得了嘛，其实有三个还是很有必要的。 fork: 把该 repo 拷贝到自己的账户下，相当于成为自己的 repo。不同之处是可以通过pull request和 original 的那个建立联系。 watch: 分为三种级别：not watching,watching,ignore.其实就是用来设置提醒的，比如watching，该 repo 有任何 update 都

在 Mac 安装 opencv，使用的方案和 linux 是一样的。 先在官网页面右侧下载OpenCV for Linux/Mac。 打开终端，用tar -xvf opencv压缩文件解压文件。 cd 进入解压后的文件夹。 mkdir release cd release cmake -D CMAKE_BUILD_TYPE=RELEASE -D CMAKE_INSTALL_PREFIX=/usr/local .. make sudo make install 依次执行，最后没报错就是成功了。 我在安装的过程中遇到了一个棘手的问题，大概如下： 12345678910111213141516171

数据结构与算法笔记：一 | Zippera’s blog 数据结构与算法笔记：二 | Zippera’s blog 数据结构与算法笔记：三（大结局） | Zippera’s blog #Heap-like Data Structures Heaps：小顶堆（二叉树，完全树），每个节点都比它的左右子树小。按照层级从左到右插入节点，然后自下向上调整大小。删除最小值的时候，直接删除根节点（一直是最小的），然后把最后一个节点移到根节点，然后自顶向下调整大小。若给出一个已经建立好的完全树，想调整为堆，则需要自底向上、从右到左地逐层调整，调整时还需要考虑子树是否不再满足堆条件，if so，自顶向下调整

最近在学习 MCMC，一种特殊的采样方法，顺便把其他常用的方法了解了一下。 ###为什么要采样？ 很多问题，我们只需要使用数学解析的方法即可解决。例如对 f(x)做积分，如果 f(x) = x^2，那么直接积分就行，很简单。 若f(x)是标准正态分布的概率密度函数（pdf），求[a,b]之间的定积分，那么直接用数学解析方法就搞不定了，因为我们知道正态分布的积分是不可求的。既然无法用解析方法计算精确值，那么退而求其次，不妨寻找一种可以求得近似值的方法。例如： f(x) = f(x) * g(x) * 1/g(x) = g(x) * (f(x) * 1/g(x))。这里我们找到一个容易采样的 pd

之前发文剖析了「结巴分词」中用「DAG」和「Viterbi」算法进行中文分词的两个方案。有了前面的基础，这里再来讨论词性标注（POS）与关键词提取。 ###词性标注 如图，在 DAG分词时所用的 dict 里面含有词汇、词频和词性三个信息。所以，最简单的情况下，只需要在分词时查询 dict 记录下每个词的词性即可。 对于 dict 中没有给出 pos 信息，或者采用 Viterbi 算法对 OOV 做分词时，需要采用另外一种方法。这种方法本质上很简单，也是采用 Viterbi 算法，只是 model 稍微做些改变。

去年学习爬虫的时候接触过这个概念，得知可以用来 url 查重。不过当时没有涉及这个问题，就搁置下了。前日又看到这个词，正好最近对各种 filter 有些兴趣，索性 break 一下。 所谓 Bloom filter，实际上就是1个数组加上 k 个 hash function组成的一个数据结构.Bloom 是该数据结构的发明人，filter 表明这个数据结构是个过滤器，可以对数据结构中的一部分内容进行操作。 首先给定一个 m 位的 bit 数组，每位取值0或1.初始设置为0. 再给定 k 个hash function，分别把元素a 映射到m 中的 k 个位置。

所谓大数据时代，大数据带来了巨大的好处，也带来了巨大的挑战，其中之一就是大数据的存储和计算。如新浪微博的巨大用户群，若想用矩阵存储用户之间的关系，矩阵的大小是惊人的，不仅传统的存储方式不再适用，在进行一些矩阵运算（如乘法）时更是无能为力了，这时候就需要我们的 MapReduce 上场啦。 MapReduce 是 Google 提出的概念，由于论文中木有提到实现细节，大家只能根据论文所述理论自己实现了。其中最火的是当年雅虎牵头做的开源项目 Hadoop，目前已经得到了非常广泛的应用（如亚马逊、百度）。尽管有这么多顶尖人才在不断优化，但据说 Hadoop 的性能目前还不及 Google 的十分之一

「熵」这个字，又难念又难记更难理解。「人工智能」课中学习「决策树」时用信息熵增益作为属性的优劣判断标准。下面结合这门课里所学的内容，简单地讲解一下什么叫做熵。 这里，我们把「熵」的概念局限在「信息论」领域里，物理学中所说的熵其实也类似，我们不加考虑。 熵，表征的是状态的混乱程度，或者说是信息的不确定性。熵的值越大，信息的不确定性越大。如等概率的时候熵最大，为1，为什么呢，既然选择 a 和选择 b 是等概率的，就相当于没有一点有用的信息，跟透支骰子似的；如果 a 的概率大一点，b 的小一点，说明我们的信息是有用的，不再是完全随机了，这时候熵就会小点，即不确定性就会小点。

在机器学习中经常需要计算协方差矩阵，本科时没学过这个概念，一直对此非常头疼。现在试图通过实例的计算、图形化的表示来梳理一下什么是协方差矩阵。 ###A numerical example 问题： 有一组数据（如下），分别为二维向量，这四个数据对应的协方差矩阵是多少？ 解答： 由于数据是二维的，所以协方差矩阵是一个2*2的矩阵，矩阵的每个元素为： 元素(i,j) = (第 i 维所有元素 - 第 i 维的均值) * (第 j 维所有元素 - 第 j 维的均值) 。 其中「*」代表向量内积符号，即两个向量求内积，对应元素相乘之后再累加。 我们首先列出第一维： D1: (1,3,4,5) 均值

最近高强度学习人工智能和模式识别，一肚子，不，一脑子的东西想写出来分享，但由于公式太多，写一篇需要很多时间，下周就要考试了，我还是多多学习好了。今天再偷懒下，把我Chrome机器学习书签夹中的一些资料拿来分享下。 机器学习经典书籍 - 算法组：给出了一些经典书籍，并附有 pdf 链接，值得参考并下载。 吴立德 《深度学习课程》 - 专辑 - 优酷视频：几个视频，专门讲解深度学习的，收藏了还没看，看过的可以反馈下。 UFLDL教程 - Ufldl：Ng 的 wiki 项目，有中文翻译，致力于深度学习的方方面面，从神经网络基础概念讲起，非常推荐。 Python 包：Scipy项目下的所有包

仅仅是结构图，没有细部信息。首先copy 课件，画出英文的导图，然后逐条翻译（小伙伴的要求）。最后小伙伴对此进行了校正和着色，对比之下，我的初稿太土鳖了。 使用的软件的是 Mindjet MindManager14，导出为图片。

数据结构与算法笔记：一 | Zippera’s blog 数据结构与算法笔记：二 | Zippera’s blog 数据结构与算法笔记：三（大结局） | Zippera’s blog #Sorting Comparison Sorting Bubble Sort: 从头到尾，两两比较，若>，则交换，再往后比较；实际上就是传递大个，从头往后，遇到大个就让大个往后走，直到最大的挪到最后面。然后从头开始第二遍，一直到倒数第二个…每一次遍历，确定队尾部分的一个元素。 Selection Sort: 有一个 min 指针，先指向第一个，然后依次与后面的比较，如果>，则 min 挪到该出，

数据结构与算法笔记：一 | Zippera’s blog 数据结构与算法笔记：二 | Zippera’s blog 数据结构与算法笔记：三（大结局） | Zippera’s blog 这两天在看一个很不错的资源，通过将常见的数据结构和算法可视化为动画或图画的形式，让学习者直观了解这些数据结构的结构形式与常用操作，以及常用算法的代码执行过程，非常受教。 这些知识大部分都有所涉猎或者在课堂上学过，但直观的观察执行过程有助于加深理解。这里简要做些笔记。打算先把内容都看完，然后写代码练习。 网站地址：http://www.cs.usfca.edu/~galles/visualization/Algo

《中文分词（一）》 《中文分词（二）》 《中文分词（三）》 承接上文《中文分词（二）》，本篇是最后一篇，介绍使用基于 HMM 的 Viterbi 算法做中文分词。 ###Viterbi 算法 了解 HMM（隐马尔可夫模型）的朋友都知道 HMM 这个模型可以用五元组表示： 12345（states，//状态空间observations，//观察空间start_probability，//状态的初始分布transition_probability，//状态的转移概率矩阵emission_probability）//状态产生观察的概率

《中文分词（一）》 《中文分词（二）》 《中文分词（三）》 接上文《中文分词（一）》继续介绍中文分词。 ###Dict to Trie 结巴分词源码中附带了一个 dict.txt 文件，是分词的基础： 2万多条词。 根据北大语料、人民日报1998 语料、小说（用张华平老师的ICTCLAS进行分词）得到。 可加入用户自定义词典。 无dict亦可，用HMM也可实现分词。 dict.txt 的内容如图： 其中第一列是 word，第二列是词频，第三列是词性（pos）。 什么是 Trie? Trie 又称前缀树或字典树，是一种数据结构，可以大大提高词典的查询速度。下图是一个简单的 Trie：

《中文分词（一）》 《中文分词（二）》 《中文分词（三）》 「中文分词」，要求是可以使用任何现有的资料，我们采用的是@TeapDB 的结巴分词，项目主页是：https://github.com/fxsjy/jieba 。 今晚刚刚做完 presentation，不知不觉在台上扯了四十分钟，在空调吹暖气烤的屋里出了一身的汗。汗还没干，把内容整理一下： ###为什么要进行中文分词？ 词是最小的能够独立活动的有意义的语言成分。 汉语是以字为基本的书写单位，词语之间没有明显的区分标记。 正确分词是中文信息处理的基础与关键。 ###中文分词的难点 交集型歧义：结婚的和尚未结婚的 =&g

Bag of Words，即词袋模型，是对样本数据的一种表示方法，主要应用在 NLP(自然语言处理)和 IR(信息检索)领域，近年也开始在 CV（计算机视觉）发挥作用。 ###模型假设 该模型在表示样本数据时，通过如下假设对模型进行简化：一个文本或文档可以看作一袋子的单词，而不考虑其语法和词序关系，每个词都是独立的（有点 unigram 的赶脚）。 ###示例 有这样两个简单的文本文档： 1John likes to watch movies. Mary likes too. 1John also likes to watch football games. 对上述两个文档构造词典： 1234

Git 几乎是程序员的标配和必备技能，但繁复的命令让人头疼，也吓跑了不少希望学习的小孩。今天看到一个很不错的教程，来自于鼎鼎有名的 CodeSchool，让用户在线跟着教程一步一步边学习边练习。 教程的地址在这里。虽然是全英文的，但几乎可以无障碍理解。

前几天帮同学弄 hexo 博客，她的电脑是 windows，不支持 rsync 功能，只能托管到 github。但是代码提交上去之后，访问网址时总不显示最新更新的内容，尝试了所有能够想到的办法，狠命折腾了一番，仍无果（在论坛看到消息，github 最近被黑了）。昨日得朋友指点，gitcafe 好像也可以免费托管静态博客。今日 google 了一下，果然可以用。另外，刚刚知道这家网站是国内的，访问速度刷刷刷，比 github 快多了。 首先，在gitcafe注册并创建项目。与 github 类似，项目名和用户名要一致。(注意：要创建「公开项目」而不是「私有项目」)

今天看酷壳耗子叔的文章时，不经意间又注意到页面右上角的「High一下」功能，玩心顿起，便连High 了好几下。想起中午曾得罪某伙伴，于是想在我的博客放上这个功能，给小伙伴 high 一下作为一个小小的道歉。Google 了一下，介绍此项的网页很少，但在有限的三两个页面里却可以看到其源码，实现起来还是很简单的。 对于 Hexo 用户，可以这样做： 在Hexo/themes/light/layout/_partial/header.ejs中的<ul>标签内部，增加一对<li>标签，并把如下内容拷贝进去：