海量数据处理专题(八)——倒排索引(搜索引擎之基石)

引言:

在信息大爆炸的今天,有了搜索引擎的帮助,使得我们能够快速,便捷的找到所求。提到搜索引擎,就不得不说VSM模型,说到VSM,就不得不聊倒排索引。可以毫不夸张的讲,倒排索引是搜索引擎的基石。

VSM检索模型

VSM全称是Vector Space Model(向量空间模型),是IR(Information Retrieval信息检索)模型中的一种,由于其简单,直观,高效,所以被广泛的应用到搜索引擎的架构中。98年的Google就是凭借这样的一个模型,开始了它的疯狂扩张之路。废话不多说,让我们来看看到底VSM是一个什么东东。 继续阅读

IT程序员笔试面试网

最近开了一个新的博客,里面包含了大量的笔试面试题,这对于要找工作的人,无疑是一个很大的帮助。

IT程序员笔试面试网里面包含有百度笔试面试题,谷歌笔试面试题,腾讯,淘宝,搜狗,人民搜索,有道,EMC,微软等知名企业的笔试面试题,欢迎订阅,此外,也欢迎大家踊跃供稿,大家一起进步。

 

好了,欢迎大家访问.

人脸识别算法综述-(LPP,PCA,K-L,SVM)

[摘 要] 本文通过工业界世界级人脸测试,说明人脸识别发展现状,分别从二维、三维角度,阐述了人脸识别算法现状,并对人脸识别算法发展趋势予以说明。

[关键词] 人脸识别 二维识别算法 三维识别算法

一、引言

1.人脸识别概述。人脸识别由于可接受性好,在生物识别领域得到较快的发展。人脸识别的研究范围广义上来讲大致包括以下五个方面的内容:人脸定位和检测、人脸表征(人脸特征抽取)、人脸鉴别、表情/姿态分析、生理分类五方面内容。 继续阅读

海量数据处理专题(六)——双层桶划分

【什么是双层桶】
事实上,与其说双层桶划分是一种数据结构,不如说它是一种算法设计思想。面对一堆大量的数据我们无法处理的时候,我们可以将其分成一个个小的单元,然后根据一定的策略来处理这些小单元,从而达到目的。

【适用范围】
第k大,中位数,不重复或重复的数字

【基本原理及要点】
因为元素范围很大,不能利用直接寻址表,所以通过多次划分,逐步确定范围,然后最后在一个可以接受的范围内进行。可以通过多次缩小,双层只是一个例子,分治才是其根本(只是“只分不治”)。 继续阅读

海量数据处理专题(四)——Bit-map

【什么是Bit-map】

所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。

如果说了这么多还没明白什么是Bit-map,那么我们来看一个具体的例子,假设我们要对0-7内的5个元素(4,7,2,5,3)排序(这里假设这些元素没有重复)。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数,我们就只需要8个Bit(1Bytes),首先我们开辟1Byte的空间,将这些空间的所有Bit位都置为0(如下图:)

继续阅读

海量数据处理专题(三)——Hash

【什么是Hash】

Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

HASH主要用于信息安全领域中加密算法,它把一些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做HASH值. 也可以说,hash就是找到一种数据内容和数据存放地址之间的映射关系。 继续阅读

海量数据处理专题(二)——Bloom Filter

【什么是Bloom Filter】

Bloom Filter是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的:在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合(false positive)。因此,Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下,采用Bloom Filter的数据结构,可以通过极少的错误换取了存储空间的极大节省。 这里有一篇关于Bloom Filter的详细介绍,不太懂的博友可以看看。

【适用范围】

可以用来实现数据字典,进行数据的判重,或者集合求交集 继续阅读

海量数据处理专题(一)——开篇

大数据量的问题是很多面试笔试中经常出现的问题,比如baidu google 腾讯 这样的一些涉及到海量数据的公司经常会问到。

下面的方法是我对海量数据的处理方法进行了一个一般性的总结,当然这些方法可能并不能完全覆盖所有的问题,但是这样的一些方法也基本可以处理绝大多数遇到的问题。下面的一些问题基本直接来源于公司的面试笔试题目,方法不一定最优,如果你有更好的处理方法,欢迎与我讨论。

本贴从解决这类问题的方法入手,开辟一系列专题来解决海量数据问题。拟包含 以下几个方面。

  1. Bloom Filter
  2. Hash
  3. Bit-Map
  4. 堆(Heap)
  5. 双层桶划分
  6. 数据库索引
  7. 倒排索引(Inverted Index)
  8. 外排序
  9. Trie树
  10. MapReduce

在这些解决方案之上,再借助一定的例子来剖析海量数据处理问题的解决方案。欢迎大家关注。

Top K算法详细解析—百度面试

问题描述:

这是在网上找到的一道百度的面试题:

搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。假设目前有一千万个记录,这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门。请你统计最热门的10个查询串,要求使用的内存不能超过1G。


问题解析:

【分析】:要统计最热门查询,首先就是要统计每个Query出现的次数,然后根据统计结果,找出Top 10。所以我们可以基于这个思路分两步来设计该算法。下面分别给出这两步的算法: 继续阅读