Algorithms, Part I, https://online.princeton.edu/course/algorithms-part-i Algorithms, Part II, https://online.princeton.edu/course/algorithms-part-ii Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne https://algs4.cs.princeton.edu/ Union−Find Considering the dynamic connectivity problem, modeling of multiple objects connected in a space/network. Applications involve manipulating objects of all types. ・Pixels in a digital photo. ・Computers in a network. ・Friends in a social network. ・Transistors in a computer chip. Given a set of N objects. union(a, b): connect two objects. connected(p, q): is two objects connected? find(p): Find component identifier for p (0 to N – 1) Modeling the objects: array. ...

程序员或者其他需要码字多的人，经常要使用编辑器如sublime、atom 和 Typora等。如果每次都要用鼠标点击才能用sublime打开文件，或者在编辑器中新建文件，那么就会有点麻烦！但你可以用一句命令解决！ 配置在Git Bash中用各种文本编辑器打开文件或者直接新建文件。这里以atom为例。 常规步骤 打开Git Bash并cd到你的目标文件夹, 或者直接在目标文件中右键打开Git Bash. atom xxx.md 就会在弹出的atom窗口中打开名为xxx.md的markdown文件, 如果没有这个文件, 会自动创建一个. 适用于其他类型文件, 如.java等. 如果想用sublime, 可以用subl xxx.java, 同理notepad++ 可以用 notepad++ xxx.java等。 (若出现错误,看下面) 若系统无法识别命令 一般使用sublime或者notepad++的用户, 可能会出现error: 系统无法识别命令...之类的, 可以这么解决: 方法1 新建一个文件命名为subl（注意不能有后缀名），内容： #!/bin/sh "D:\Sublime Text 3\sublime_text.exe" $1 & 第一行指明这是个 shell 脚本. 第二行的字符串是sublime的安装目录, 示例只是我电脑的目录, 注意这里要改为你自己的目录, 第二行的$1 是取的命令之后输入的参数 第二行的&是此命令在后台打开，这样sublime打开之后，就不会阻塞你的git bash 文件保存到 C:\Program Files (x86)\Git\mingW32\bin 目录下(你的git目录可能与我的不一样，注意改成你自己的) 同理适用于其他编辑器，比如用chrome打开.html文件等。如果不想每次都新建一个文件，可以用下面的方法2。 方法2 找到 C:\Users\你的计算机名目录，如果你的计算机名是Administrator，那么你就要去C:\Users\Administrator目录下, 这里一般存放着windows系统的我的文档, 桌面等文件夹. 在该目录下用Git Bash输入notepad .bashrc, 这会用windows记事本新建并打开一个文件.bashrc，这个文件没有名称只有后缀名。.bashrc里面可以给Git Bash设置命令的别名, 设置路径等。 在.bashrc文件加入下面一行文本alias notepad++="/D/Notepad++/notepad++.exe", 这里你需要修改为你电脑的安装路径。alias就是别名的意思，当我们执行notepad++的时候，实际执行的是=后面的语句. 重新打开Git Bash, 设置才能生效，如果不想关掉在打开的话，可以直接在bash下输入source ~/.bashrc就可以立刻加载修改后的设置，设置立即生效。 现在在bash下输入notepad++ test.py, 就直接打开了notepad++并创建了这个叫test的Python文件。这里的别名不一定非要取notepad++，随你想叫什么都行。 同理也可以扩展到别的文本编辑器，alias atom="atom的路径", alias sublime="sublime的路径"等. 最后还要注意一点，上面所说的路径最好不要有空格，括号等，否则会造成命令无效. ...

本篇介绍 topic modeling, 以及一个经典的算法Latent Dirichlet allocation, 文本挖掘与语义理解的集大成者(至少在深度学习统治之前). 当然LDA不仅仅局限于文本, 还可应用于涉及大量数据集的各种问题，包括协同过滤，基于内容的图像检索和生物信息学等领域的数据。 Topic Modelling 大规模文本挖掘的核心问题, 就是用数学模型代替人力来理解文本语义，目标是找到对集合成员（如一堆文本）的数学/统计描述，以便能够对这些大型集合进行高效处理，同时保留对基本任务（如分类，检测，摘要以及相似性和相关性判断）有用的基本统计关系。 在这方面的研究方法很多，特别是信息检索(IR)领域. 一个基本方法是将语料库中的每个文档向量化，向量中的每个实数代表计数率。比如经典的tf-idf方法，用Document-Term Matrix来表达不同词在不同文档出现的情况差异, 一般term就是word作为features, 所以在这里我们表示document-word matrix(DWM), 就是DWM[i][j] = The number of occurrences of word_j in document_i. Doc 1: I have a fluffy cat. Doc 2: I see a fluffy dog. DWM I have a fluffy cat see dog doc1 1 1 1 1 1 0 0 doc2 1 0 1 1 0 1 1 然后进行normalization, 去和 inverse document frequency count(IDF)进行比较. IDF统计每个词在整个文档集合中出现的总次数, 通常转化为log scale, 并进行适当的normalization. ...

参考 CS229: Machine Learning, Stanford 什么是机器学习？目前有两个定义。 亚瑟·塞缪尔（Arthur Samuel）将其描述为：“不需要通过具体的编程，使计算机能够学习”。这是一个较老的，非正式的定义。 汤姆·米切尔（Tom Mitchell）提供了一个更现代的定义： E：经验，即历史的数据集。 T：某类任务。 P：任务的绩效衡量。 若该计算机程序通过利用经验E在任务T上获得了性能P的改善，则称该程序对E进行了学习 “如果计算机程序能够利用经验E，提升实现任务T的成绩P，则可以认为这个计算机程序能够从经验E中学习任务T”。 例如：玩跳棋。E =玩许多棋子游戏的经验，T = 玩跳棋的任务。P = 程序将赢得下一场比赛的概率。 Supervised Learning Linear Regression Weights(parameters) θ: parameterizing the space of linear functions mapping from X to Y Intercept term: to simplify notation, introduce the convention of letting x0 = 1 Cost function J(θ): a function that measures, for each value of the θ’s, how close the h(x(i))’s are to the corresponding y(i)’s Purpose: to choose θ so as to minimize J(θ). Implementation: By using a search algorithm that starts with some “initial guess” for θ, and that repeatedly changes θ to make J(θ) smaller, until hopefully we converge to a value of θ that minimizes J(θ). LMS(least mean squares) algorithm: gradient descent learning rate error term batch gradient descent：looks at every example in the entire training set on every step stochastic gradient descent(incremental gradient descent)：repeatedly run through the training set, and each time we encounter a training example, we update the parameters according to the gradient of the error with respect to that single training example only. particularly when the training set is large, stochastic gradient descent is often preferred over batch gradient descent. The normal equations performing the minimization explicitly and without resorting to an iterative algorithm. In this method, we will minimize J by explicitly taking its derivatives with respect to the θj’s, and setting them to zero. To enable us to do this without having to write reams of algebra and pages full of matrices of derivatives, let’s introduce some notation for doing calculus with matrices ...

Scikit-learn 提供一套实用的工具，用于解决机器学习中的实际问题，并配合适当的方法来制定解决方案。 涉及数据和模型简介，决策树，误差的作用，最小化误差，回归拟合，逻辑回归，神经网络，感知器，支持向量机，朴素贝叶斯，降维，K均值，简单高斯混合模型，分层聚类，模型评估。 实验和代码在GitHub; 练习作业答案可以参考GitHub

语言模型 语言模型Language modeling（LM）最初是针对语音识别问题而开发的, 现在广泛用于其他NLP应用中, 比如机器翻译需要利用LM来给翻译出的句子打分. 假设我们有一个语料库 - 某种语言的句子的无限集合$\mathcal{V^+}$（这些句子是由有限的词$\mathcal{V}$组成的）。例如，我们可能从网上获得大量文本。给定了此语料库，我们想估计LM的参数。这些参数包含语料库中所有单词的有限集合$\mathcal{V}$, 以及句子的概率分布函数$p(x_1, x_2, ..., x_n)$，必须满足 For any $\langle x_1...x_n \rangle \in \mathcal{V^+}$, $p(x_1, x_2, ..., x_n) ≥ 0$ $\sum_{\langle x_1...x_n \rangle \in \mathcal{V^+}}p(x_1, x_2, ..., x_n) = 1$ 比如，当$\mathcal{V}$只有cat, eat, fish, 那么它组合成的句子按照人类的评价标准, 通顺程度从高到低是: cat eat fish, fish eat cat, cat fish eat, eat cat fish, eat fish cat, fish cat eat. 这些是可能出现的句子(还没出现的不代表未来不会出现), 从概率分布的角度看待, 这些句子的概率之和是1, 因为这三个词只能组成这几个句子. 而LM的意义就在于能够赋予cat eat fish最大的概率, 代替人来判断句子是否准确, 通俗的说是一个句子通顺打分机器. ...

Bit Map Bit-map用一个bit位来标记某个元素对应的Value， 而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。 假设我们要对0-7内的5个元素4,7,2,5,3排序（假设这些元素没有重复）。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数，我们就只需要8个Bit（1Bytes）， 首先我们开辟1Byte的空间，将这些空间的所有Bit位都置为0，0 0 0 0 0 0 0 0. 然后遍历这5个元素，首先第一个元素是4，那么就把4对应的位置设为1, p+(i/8)|(0x01<<(i%8)), 这里默认为Big-ending, 0 0 0 0 1 0 0 0. 然后再处理第二个元素7，将第八位置为1,，接着再处理第三个元素，一直到最后处理完所有的元素，将相应的位置为1，这时候的内存的Bit位的状态0 0 1 1 1 1 0 1 遍历一遍Bit区域，把1的索引依次输出（2，3，4，5，7），这样就达到了排序的目的。 算法的关键是如何确定十进制的数映射到二进制bit位的map图。算法占用很少内存，比如N=10000000；只需占用内存为N/8=1250000Byte=1.25M。缺点是不能有重复数据。 Map映射表 假设需要排序或者查找的总数N=10000000，那么我们需要申请内存空间的大小为int a[1 + N/32]，其中：a[0]在内存中占32位, 可以对应十进制数0-31，依次类推： bitmap表为： a[0]--------->0-31 a[1]--------->32-63 a[2]--------->64-95 a[3]--------->96-127 .......... 十进制数需要转换为对应的bit位 位移转换 将十进制数转换为对应的bit位, 申请一个int一维数组，作为32列的二维数组， int a[0] |0000000000000000000000000000000000000| int a[1] |0000000000000000000000000000000000000| ……………… int a[N] |0000000000000000000000000000000000000| 例如十进制0，对应在a[0]第一位： 00000000000000000000000000000001 求十进制0-N对应在数组a的索引：十进制0-31，对应a[0]，先由十进制数n转换为与32的余可转化为对应在数组a中的索引0。比如n=24,那么 n/32=0，则24对应a[0]。又比如n=60, 那么n/32=1，则60对应a[1]。 求0-N对应0-31中的数：十进制0-31就对应0-31，而32-63则对应也是0-31，即给定一个数n可以通过模32求得对应0-31中的数。 利用移位0-31使得对应32bit位为1. 找到对应0-31的数为M, 左移M位：即2 ^ M, 置1. Bloom Filter 为了降低键值冲突的概率，Bloom Filter使用了多个哈希函数：创建一个m位BitSet，先将所有位初始化为0，然后选择k个不同的哈希函数。第i个哈希函数对字符串str哈希的结果记为h(i, str)，且h(i, str)的范围是0到m-1 。 ...

避免歧义的编码 在构建压缩编码的对应关系时，我们使用不同的数量的位来编码不同的字符. 比如摩斯密码. 如果单纯使用这种对应关系，会出现一些问题， 如•••−−−•••会产生歧义: SOS? V7? IAMIE? EEWNI? 所以在实际使用中, 密码使用一些间隔来分隔代码字。 那么对于不同的压缩编码, 有什么常用方法来避免歧义？ 方法是确保没有一个编码是另一个编码的前缀。比如 使用固定长度编码。 为每个编码添加特殊的stop char。 使用一种具备广泛使用性的prefix-free编码。 用什么数据结构来设计prefix-free编码? 用Trie构造编码 一个二叉(0, 1)Trie: 叶节点是字符, 根节点到叶节点的路径就是编码. 压缩: 方法1：从叶开始; 按照路径到达根; 反向打印bits。 方法2：创建键-值对的符号表。 解压: 从根节点开始, 根据位值是0还是1在Trie图上游走, 直到走到叶节点，则解压出一个字符 返回根节点, 继续第一步, 直到跑完所有编码. private static class Node implements Comparable<Node> { private final char ch; // used only for leaf nodes private final int freq; // used only for compress private final Node left, right; public Node(char ch, int freq, Node left, Node right) { this.ch = ch; this.freq = freq; this.left = left; this.right = right; } public boolean isLeaf() { return left == null && right == null; } // compare Nodes by frequency public int compareTo(Node that) { return this.freq - that.freq; } // Runtime - Linear in input size N public void expand() { Node root = readTrie(); // read in encoding trie int N = BinaryStdIn.readInt(); // read in number of chars for (int i = 0; i < N; i++) { Node x = root; while (!x.isLeaf()) { if (!BinaryStdIn.readBoolean()) x = x.left; else x = x.right; } BinaryStdOut.write(x.ch, 8); } BinaryStdOut.close(); } } 如何读取一个Trie：根据Trie的前序遍历序列重构. ...

数据压缩 压缩数据以节省储存空间，节省传输时间。同时很多文件都有很多冗余信息，这为压缩提供了很多可能性。 通用文件压缩 ·文件：GZIP，BZIP，7z ·Archivers：PKZIP ·文件系统：NTFS，HFS +，ZFS 多媒体 ·图像：GIF，JPEG ·声音：MP3 ·视频：MPEG，DivX™，HDTV 通讯 ·ITU-T T4 Group 3 Fax ·V.42bis调制解调器 ·Skype 数据库 压缩率 Compression ratio = Bits in Compressed B / bits in B. 自然语言的压缩率为50-75％或更高. 读写二进制 public class BinaryStdIn { boolean readBoolean() // read 1 bit of data and return as a boolean value char readChar() // read 8 bits of data and return as a char value char readChar(int r) // read r bits of data and return as a char value // similar methods for byte (8 bits); short (16 bits); int (32 bits); long and double (64 bits) boolean isEmpty() // is the bitstream empty? void close() // close the bitstream } public class BinaryStdOut { void write(boolean b) // write the specified bit void write(char c) // write the specified 8-bit char void write(char c, int r) // write the r least significant bits of the specified char // similar methods for byte (8 bits); short (16 bits); int (32 bits); long and double (64 bits) void close() // close the bitstream } 比如使用三种方法表达12/31/1999 1, A character stream (StdOut), ...

数组中有一个数字出现的次数超过数组长度的一半，例如输入一个长度为9的数组1,2,3,2,2,2,5,4,2。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。因为这个数出现次数超过了数组长度一半以上, 那么它就是数组中出现次数最多的数, 故谓之众数. class Solution: def MoreThanHalfNum_Solution(self, numbers): # write code here most = numbers[0] count = 1 for item in numbers: if item == most: count += 1 else: count -= 1 if count < 0: most = item count = 1 return 0 if numbers.count(most) <= len(numbers) / 2 else most 众数问题 众数问题可以推广泛化：给定大小为n的整数数组，找到所有出现超过n / m次的元素。这种问题可以使用 Boyer-Moore 算法解决. The Boyer–Moore majority vote algorithm is an algorithm for finding the majority of a sequence of elements using linear time and constant space. It is named after Robert S. Boyer and J Strother Moore, who published it in 1981, and is a prototypical example of a streaming algorithm. ...