-
Isaac64解密算法JNI的封装
前言 众所周知，理论上最安全的加密方式是使用一次一密（OTP）。但是传递与明文长度相等的、完全随机的加密面板这件事情并不具有实践意义，因此就诞生了流密码（Stream Cipher）。流密码将一个密钥作为种子，按照某种伪随机数生成算法生成供OTP使用的加密面板。有了加密面板之后，就可以逐字使用传统的 Vernam 算法 或者 Vigenère 算法进行加密解密。 由于这样进行的加密解密操作没有复杂的计算、并且不需要对数据进行预取分块等复杂操作，因此执行效率很高，非常适合用作流媒体数据的加密。…
-
网易2017春招笔试真题编程题集合题解
前言 想想已经有一年多没有接触算法题了，忙活了一年多没什么用的东西，才陡然发现自己竟然就要毕业了，然而审视了下自己的水平估计还达不到大一的程度，甚是惊恐。于是下定决心开始刷一点题，打好基本功。正好有同学在做网易笔试题的时候来向我问问题，我看了看有12道，好像也不多，于是就顺便刷了刷。本以为会是一帆风顺的，可是事实是，我果然还是太菜了。。。 双核处理 题目 一种双核CPU的两个核能够同时的处理任务，现在有n个已知数据量的任务需要交给CPU处理，假设已知CPU的每个核1秒可以处理1kb，…
-
面向最小哈希签名的LSH
LSH 我们知道最小哈希签名能够把一篇较大的文档压缩成一个较短的签名并且不影响文档间的Jaccard相似度。很多情况下，我们用最小哈希签名的目的就是为了方便的对文档进行存储，并且对于给定的文档，能在大量的文档中快速的查找相似的文章。现在我们能做到快速的对两篇文章进行相似度比较，但是当总的文档数目比较大的时候，比较所有文档的最小哈希签名仍然是一个非常耗时耗力的事。而我们知道，对于给定的文档而言，文档库中的绝大多数文档其实都没有比较的意义，如果能有一个方法能过滤掉不需要比较的大量文档，那么显然就能…
-
最小哈希签名（MinHash）简述
最小哈希签名(minhashing signature)解决的问题是，如何用一个哈希方法来对一个集合（集合大小为n）中的子集进行保留相似度的映射（使他在内存中占用的字节数尽可能的少）。 其实哈希本身并不算难，难的是怎么保留两个子集的相似度的信息。所谓保留相似度，就是说我们能十分直观的从两个子集的哈希结果中看出他们的相似度。当然，朴素的办法就用是一个长度为n的二进制数的每个位来分别对应集合中的每个元素。不过当n比较大而待hash的集合的数目比较小的时候，这种方法的效率就太低了。这时候最常用的方法…
-
文档分割的shingling算法
shingling算法是最常见的文档分割算法，说白了就是将一个文档分解成由短字符构成的字符串集合。分割后的文档就可以通过Jaccard相似度等简单的度量标准进行相似度检测了。 k-shingling 对于任意一篇文档，我们把他当成一个字符串，那么他的k-shingling集合就被定义为文档中所有长度为k的子字符串的集合。比如字符串“abcdabd”，他的2-shingling集合就是{ab,bc,cd,da,bd}。 当然，所有类型的子字符串只会在集合中出现一次。不过实际的文档中可能会有…
-
幂定律和齐夫定律
幂定律 幂定律又叫幂律，大量的事实表明，很多现象都服从类似于幂函数$y=cx^a$的形式，其中$a$是幂，而且通常是负数。 幂定律可以非常直观的用马太效应(Matthew effect)解释，说白了其实就是所谓的“富者越富，穷者越穷”。例如图书的销售，本来销售好的图书可能会发布更多的广告，做更多的营销从而导致销量更多。这样如果将图书销售量按照名次排列下来就会发现图书销量会随着名次的提高而指数性的提高。 齐夫定律 齐夫定律(Zipf's Law)其实可以说是幂定律的一种形式，只是…
-
用于文档关键字提取的TFIDF指标
关键字提取问题 在大规模网络文章整合的过程中，我们经常需要对某一篇文章提取关键字。比如对于某一篇关于计算机的文章，我们应该提取出类似于“计算机”、“编程”、“CPU”之类的符合人类认知习惯的关键词，但是这个过程却不是那么容易。现在，我们把问题归结为，在不使用机器学习方法的情况下，给定一个文档集，仅从单词频率等角度对文档集当中的某一篇文档进行考虑，期望能够对于该篇文章，我们能从文章中依次提取出最有代表性的关键词。 我们很容易想到的方法就是统计每个词的词频了，但是对于任何文章而言，出现频率最多的…
-
Huffman无损压缩和解压算法实现
高中学信息论的课后作业，本来自己的项目文档和中期汇报还没写，为了强行装x答应了下来，结果硬是熬夜到四点才敲完。。。。(以后绝不装逼了) 虽然算法看上去不难，但是不得不说还是走了很多弯路，学到了很多东西，在这里做个记录。 需求 用Huffman 编码实现文件的无损压缩和解压。 算法 算法当然用到了霍夫曼编码，构造霍夫曼树。具体过程也很简单，就是把读入的字节流按照字节进行频数分析，对频率高的字符用短编码，对频率低的用长编码。然后将编码的映射表和编码后的结果写入文件，这时候生成的文件就是…
-
GeoHash空间索引算法简述
背景 在空间索引类问题当中，一个最普遍而又最重要的问题是：”给定你某个点的坐标，你如何能够在海量的数据点中找到他所在的区域以及最靠近他的点”？ 最常见的应用就像是**POI(Point of Interest)**的查询了，比方说客户在路上突然想吃饭了，那么我就要根据他的位置查询最近的餐馆并根据这个做出推荐。 通常情况下，一提到查找类问题，我们就会想到二分查找或者是B树查找。但是问题在于我们不仅要找到这个点，而且要找到这个点附近的点。因此对于以经纬度来确定的坐标又不好直接进行二分查找。（如…
-
朴素贝叶斯分类器
简述 朴素贝叶斯分类器是机器学习中最基础的分类算法了，之前一直忽视这个算法，感觉这种简单利用贝叶斯公式的方法的确很Naive。但是事实上这个算法在对于特征相互独立的分类问题来说还是非常好用的。其基本思想就是在给定在各种情况下一个事件发生的先验概率的情况下，套用贝叶斯公式求出给定各种情况下给定事件发生的后验概率。思想非常简单，但是在某些情况下效果还是非常好的，值得掌握。 贝叶斯公式 贝叶斯公式很简单了，对于事件A和事件B，下面的公式显然成立： $$P(A|B)=\frac{P(A)P(B…