大数据计数原理1+0=1这你都不会算(六)No.57

照例甩一波链接。

大数据计数原理1+0=1这你都不会算(一)No.47 <- HashSet

大数据计数原理1+0=1这你都不会算(二)No.50 <- BitMap

大数据计数原理1+0=1这你都不会算(三)No.51 <- BloomFilter

大数据计数原理1+0=1这你都不会算(四)No.52 <- B-Tree

大数据计数原理1+0=1这你都不会算(五)No.55 <- B+Tree

今天开始进入一个全新的领域,嗯,叫基数估计。

什么叫基数估计呢?

基数是指一个一大堆值集合中,不同的值的个数。

我们之前讲的,都是精确的统计,有一说一有二说二,直接去重统计就可以了。

基数估计,故名思议,估计,意思就是使用概率论的思想,用更低空间更低时间的成本,以一个很低很低的误差率来估计数据的基数。

能不能说说人话呢?

好好好,你长得好看说什么都对。

加入一个集合长这样

{大蕉,小蕉,小蕉,大大蕉,小蕉}

统计思想会这样说。

啊大蕉,嗯,1个。

小蕉,没出现过,嗯,2个。

小蕉,出现过了,嗯,2个。

大大蕉,没出现过,嗯,3个。

小蕉,出现过了,嗯,3个。

概率论思想会这样说。

我夜观天象,掐指一算,公子是个喜脉。

呸呸呸。掐值一算,有99%的概率是3个。

但是又有小伙伴开始说了,我特么把手都快掐出血了,也不知道你吖是怎么估算的。

年轻人不要太着急嘛。

我们今天几乎所有算法的启蒙。Linear Counting(LC)

来自于1900年一个叫 KY · Whang 的大湿的一篇名叫《A linear-time probabilistic counting algorithm for database applications》的论文。

This algorithm has O(q) time complexity, where q is the number of values including duplicates, and produces an estimation with an arbitrary accuracy prespecified by the user using only a small amount of space. Traditionally, accurate counts of unique values were obtained by sorting, which has O(q log q) time complexity. Our technique, called linear counting, is based on hashing.

意思就是,啊传统的精确统计至少要O(q log q)这么死鬼多时间,我们只需要O(q) ,你不觉得很厉害吗?然后我们是用 Hash 实现的,嗯,可牛逼了。

怎么做的呢?

我们先创建一个长度为m的数组,每一个bit都设置为0,然后搞个Hash算法把这些值的位置所对应的0改为1。

比如字符串 “小蕉写得这么给力你不点个赞吗”,经过 Hash 算法1、Hash 算法2、Hash 算法3,生成了数字,1、11、21。

这时候又来了一个字符串 “小蕉写得这么给力你不点个赞”,经过 Hash 算法1、Hash 算..

你等等等等等,这不是BitMap吗?你特么在说啥。

年轻人不要太着急嘛。

我急!这辈子就现在!最!急!

好好好我来了我来了。上面这个数组比BitMap所需要的数组小很多很多很多。然后我们假设最终有u个位置还是0。我们给出一个极大似然估计,估计一下n的估计(下面这个是极大似然估计)就长这样。

好了我要睡觉了,拜拜。

至于详细的数学推导及误差分析推导,且听下回分...

这行字是提前打的

原文发布于微信公众号 - 一名叫大蕉的程序员(DaBananaTalk)

原文发表时间:2017-09-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

【机器学习笔记之一】深入浅出学习K-Means算法

摘要:在数据挖掘中,K-Means算法是一种 cluster analysis 的算法,其主要是来计算数据聚集的算法,主要通过不断地取离种子点最近均值的算法。 ...

3029
来自专栏xingoo, 一个梦想做发明家的程序员

动态规划

基本思想:将待求解问题分解成若干子问题,先求解子问题,然后从子问题的解中得到原问题的解。 与分治不同的是,经分解得到的子问题往往不是互相独立的。 若用分治法来解...

1975
来自专栏数据结构与算法

2853 方格游戏(三维棋盘)

 时间限制: 1 s  空间限制: 128000 KB  题目等级 : 钻石 Diamond 题解  查看运行结果 题目描述 Description 菜菜看到了...

3606
来自专栏趣学算法

数据结构 第2讲 算法复杂性

该内容来源于本人著作《趣学算法》在线章节:http://www.epubit.com.cn/book/details/4825

1242
来自专栏封碎

一些重要的算法 博客分类: 算法 算法网络应用网页游戏领域模型游戏

      下面是一些比较重要的算法,原文 罗列了32个,但我觉得有很多是数论里的或是比较生僻的,和计算机的不相干,所以没有选取。下面的这些,有 的我们经常在用...

1101
来自专栏机器学习算法与Python学习

Encoder-Decoder自动生成对联,要试试么?

另外,点击阅读原文尝试微软的自动对联系统(http://duilian.msra.cn/app/couplet.aspx)

1250
来自专栏PPV课数据科学社区

【大数据问答】SPSS是如何做到发现数据质量问题,例如,如何发现缺失值?

SPSS是如何做到发现数据质量问题,例如,如何发现缺失值? (1)系统缺失值、空白值 每一个变量均有可能出现系统缺失或者空白,当数据量巨大时我们根本无法用眼睛...

4224

组和分组卷积

考虑一个正方形。它是对称的吗?它是如何对称的?它有多少对称性?它有什么样的对称性?

31710
来自专栏数据派THU

手把手教你由TensorFlow上手PyTorch(附代码)

来源:机器之心 作者:Illarion Khlestov 本文为你解读PyTorch 的易用性。 当我第一次尝试学习 PyTorch 时,没几天就放弃了。和 ...

9524
来自专栏趣学算法

算法之美——算法复杂性

《趣学算法》在线章节:http://www.epubit.com.cn/book/details/4825

2851

扫码关注云+社区

领取腾讯云代金券