Mythsman


乐极生悲,苦尽甘来。


标签: Algorithm


  1. 网易2017春招笔试真题编程题集合题解

    前言想想已经有一年多没有接触算法题了,忙活了一年多没什么用的东西,才陡然发现自己竟然就要毕业了,然而审视了下自己的水平估计还达不到大一的程度,甚是惊恐。于是下定决心开始刷一点题,打好基本功。正好有同学在做网易笔试题的时候来向我问问题,我看了看有12道,好像也不多,于是就顺便刷了刷。本以为会是一帆风顺的,可是事实是,我果然还是太菜了。。。 双核处理题目一种双核CPU的两个核能够同时的处理任务,现在有n个已知数据量的任务需要交给CPU处理,假设已知CPU的每个核1秒可以处理1kb,每个核同时只能处理…

    Algorithm, C/C++, MathJax阅读全文

  2. 面向最小哈希签名的LSH

    LSH我们知道最小哈希签名能够把一篇较大的文档压缩成一个较短的签名并且不影响文档间的Jaccard相似度。很多情况下,我们用最小哈希签名的目的就是为了方便的对文档进行存储,并且对于给定的文档,能在大量的文档中快速的查找相似的文章。现在我们能做到快速的对两篇文章进行相似度比较,但是当总的文档数目比较大的时候,比较所有文档的最小哈希签名仍然是一个非常耗时耗力的事。而我们知道,对于给定的文档而言,文档库中的绝大多数文档其实都没有比较的意义,如果能有一个方法能过滤掉不需要比较的大量文档,那么显然就能加快…

    BigData, MathJax, Algorithm, LSH阅读全文

  3. 最小哈希签名(MinHash)简述

    最小哈希签名(minhashing signature)解决的问题是,如何用一个哈希方法来对一个集合(集合大小为n)中的子集进行保留相似度的映射(使他在内存中占用的字节数尽可能的少)。 其实哈希本身并不算难,难的是怎么保留两个子集的相似度的信息。所谓保留相似度,就是说我们能十分直观的从两个子集的哈希结果中看出他们的相似度。当然,朴素的办法就用是一个长度为n的二进制数的每个位来分别对应集合中的每个元素。不过当n比较大而待hash的集合的数目比较小的时候,这种方法的效率就太低了。这时候最常用的方法就…

    BigData, Algorithm, MathJax阅读全文

  4. 文档分割的shingling算法

    shingling算法是最常见的文档分割算法,说白了就是将一个文档分解成由短字符构成的字符串集合。分割后的文档就可以通过Jaccard相似度等简单的度量标准进行相似度检测了。 k-shingling对于任意一篇文档,我们把他当成一个字符串,那么他的k-shingling集合就被定义为文档中所有长度为k的子字符串的集合。比如字符串“abcdabd”,他的2-shingling集合就是{ab,bc,cd,da,bd}。 当然,所有类型的子字符串只会在集合中出现一次。不过实际的文档中可能会有连续的空格…

    Algorithm, BigData阅读全文

  5. 幂定律和齐夫定律

    幂定律幂定律又叫幂律,大量的事实表明,很多现象都服从类似于幂函数$y=cx^a$的形式,其中$a$是幂,而且通常是负数。 幂定律可以非常直观的用马太效应(Matthew effect)解释,说白了其实就是所谓的“富者越富,穷者越穷”。例如图书的销售,本来销售好的图书可能会发布更多的广告,做更多的营销从而导致销量更多。这样如果将图书销售量按照名次排列下来就会发现图书销量会随着名次的提高而指数性的提高。 齐夫定律齐夫定律(Zipf's Law)其实可以说是幂定律的一种形式,只是由于在曾经一次语料库的…

    Maths, Algorithm, MathJax阅读全文

  6. 用于文档关键字提取的TFIDF指标

    关键字提取问题在大规模网络文章整合的过程中,我们经常需要对某一篇文章提取关键字。比如对于某一篇关于计算机的文章,我们应该提取出类似于“计算机”、“编程”、“CPU”之类的符合人类认知习惯的关键词,但是这个过程却不是那么容易。现在,我们把问题归结为,在不使用机器学习方法的情况下,给定一个文档集,仅从单词频率等角度对文档集当中的某一篇文档进行考虑,期望能够对于该篇文章,我们能从文章中依次提取出最有代表性的关键词。 我们很容易想到的方法就是统计每个词的词频了,但是对于任何文章而言,出现频率最多的应该是…

    BigData, Algorithm, MathJax, Machine Learning阅读全文

  7. Huffman无损压缩和解压算法实现

    高中学信息论的课后作业,本来自己的项目文档和中期汇报还没写,为了强行装x答应了下来,结果硬是熬夜到四点才敲完。。。。(以后绝不装逼了) 虽然算法看上去不难,但是不得不说还是走了很多弯路,学到了很多东西,在这里做个记录。 需求用Huffman 编码实现文件的无损压缩和解压。 算法算法当然用到了霍夫曼编码,构造霍夫曼树。具体过程也很简单,就是把读入的字节流按照字节进行频数分析,对频率高的字符用短编码,对频率低的用长编码。然后将编码的映射表和编码后的结果写入文件,这时候生成的文件就是压缩后的文件了。根…

    Algorithm, Java阅读全文

  8. GeoHash空间索引算法简述

    背景在空间索引类问题当中,一个最普遍而又最重要的问题是:”给定你某个点的坐标,你如何能够在海量的数据点中找到他所在的区域以及最靠近他的点”? 最常见的应用就像是**POI(Point of Interest)**的查询了,比方说客户在路上突然想吃饭了,那么我就要根据他的位置查询最近的餐馆并根据这个做出推荐。 通常情况下,一提到查找类问题,我们就会想到二分查找或者是B树查找。但是问题在于我们不仅要找到这个点,而且要找到这个点附近的点。因此对于以经纬度来确定的坐标又不好直接进行二分查找。(如果是直接…

    BigData, MathJax, GeoHash, Algorithm阅读全文

  9. 朴素贝叶斯分类器

    简述朴素贝叶斯分类器是机器学习中最基础的分类算法了,之前一直忽视这个算法,感觉这种简单利用贝叶斯公式的方法的确很Naive。但是事实上这个算法在对于特征相互独立的分类问题来说还是非常好用的。其基本思想就是在给定在各种情况下一个事件发生的先验概率的情况下,套用贝叶斯公式求出给定各种情况下给定事件发生的后验概率。思想非常简单,但是在某些情况下效果还是非常好的,值得掌握。 贝叶斯公式贝叶斯公式很简单了,对于事件A和事件B,下面的公式显然成立: $$P(A|B)=\frac{P(A)P(B|A)}{P(…

    Machine Learning, MathJax, Algorithm阅读全文

  10. 二叉堆简述

    简述对于堆,我个人的理解就是一种优先队列,从队列中取元素的时候总是取出最大(或最小)的元素。二叉堆是一种堆的一种实现形式,是一棵完全二叉树。对于二叉堆,我们显然可以分成两类:大根堆和小根堆,表示他每次取出的是最大元素还是最小元素。而大根堆一定是满足这样的一个性质,即:对于任意一个节点,他一定不大于他的父亲,而且不小于他的两个儿子。小根堆反之。 实现功能以$O(n)$的时间建树,并以$O(logn)$的复杂度实现插入、寻找最小(或最大)值,修改元素,删除元素。 实现思路(小根堆)我们用一个数组来储…

    MathJax, Algorithm阅读全文