7.倒排索引(Inverted index)
适用范围:搜索引擎,关键字查询
基本原理及要点:为何叫倒排索引?一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。
以英文为例,下面是要被索引的文本:
T0 = "it is what it is"
T1 = "what is it"
T2 = "it is a banana"
我们就能得到下面的反向文件索引:
"a": {2}
"banana": {2}
"is": {0, 1, 2}
"it": {0, 1, 2}
"what": {0, 1}
检索的条件"what", "is" 和 "it" 将对应集合的交集。
正向索引开发出来用来存储每个文档的单词的列表。正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。在正向索引中,文档占据了中心的位置,每个文档指向了一个它所包含的索引项的序列。也就是说文档指向了它包含的那些单词,而反向索引则是单词指向了包含它的文档,很容易看到这个反向的关系。
扩展:
问题实例:文档检索系统,查询那些文件包含了某单词,比如常见的学术论文的关键字搜索。
8.外排序
适用范围:大数据的排序,去重
基本原理及要点:外排序的归并方法,置换选择 败者树原理,最优归并树
扩展:
问题实例:
1).有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16个字节,内存限制大小是1M。返回频数最高的100个词
这个数据具有很明显的特点,词的大小为16个字节,但是内存只有1m做hash有些不够,所以可以用来排序。内存可以当输入缓冲区使用。
9.trie树
适用范围:数据量大,重复多,但是数据种类小可以放入内存
基本原理及要点:实现方式,节点孩子的表示方式
扩展:压缩实现。
问题实例:
1).有10个文件,每个文件1G, 每个文件的每一行都存放的是用户的query,每个文件的query都可能重复。要你按照query的频度排序 。
2).1000万字符串,其中有些是相同的(重复),需要把重复的全部去掉,保留没有重复的字符串。请问怎么设计和实现?
3).寻找热门查询:查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个,每个不超过255字节。
分享到:
相关推荐
海量数据处理方法总结 本文总结了常用的海量数据处理方法,包括 Bloom filter、Hashing 和 bit-map 等。这些方法可以用来解决大数据量的问题,例如数据字典、判重、集合求交集等问题。 Bloom Filter Bloom filter...
大数据量,海量数据,处理方法总结,面试必备。
下面的方法是我对海量数据的处理方法进行了一个一般性的总结,当然这些方法可能并不能完全覆盖所有的问题,但是这样的一些方法也基本可以处理绝大多数遇到的问题。下面的一些问题基本直接来源于公司的面试笔试题目...
这些技术是大数据量和海量数据处理的基石,在数据科学、网络分析、搜索引擎优化等众多领域有着广泛的应用。在实际使用过程中,可以根据数据的特性和处理需求灵活选择合适的处理方法,并结合问题实例进一步理解和掌握...
### 大数据量、海量数据处理方法总结 #### 一、引言 随着互联网技术的发展,数据量呈现出爆炸性增长的趋势。如何高效地处理这些大数据成为了一项挑战性的任务。在IT行业,尤其是在搜索引擎、社交媒体等领域,处理...
海量数据 大数据量 处理的算法和数据结构 对面试IT公司的人非常有用!
【大数据量,海量数据处理方法总结】 大数据量的处理是现代信息技术领域的重要课题,尤其在互联网巨头如百度、谷歌和腾讯等公司中,这类问题尤为常见。本文将概述几种处理海量数据的有效方法,包括Bloom Filter、...
大数据量的问题是很多面试笔试中经常出现的问题,比如百度,谷歌,腾讯这样的一些涉及到海量数据的公司经常会问到。 本文的一些问题基本直接来源于公司的面试笔试题目。包括Bloom filter,Hashing,bit-map,双层桶...
海量数据处理是指基于海量数据上的存储、处理、操作,解决方案包括巧妙的算法搭配适合的数据结构,如 Bloom filter/Hash/bit-map/堆/数据库或倒排索引/trie 树,以及大而化小、分而治之的策略。根据数据处理的场景,...
大数据与海量数据处理算法总结 在当今数据爆炸的时代,大数据处理是IT行业的一个热点。无论是社交网络、电子商务还是搜索引擎公司,都面临着海量数据的存储、查询和分析问题。为了有效应对这些挑战,研究者们提出了...
### 大数据量海量数据处理的关键技术与方法 在当今数字化时代,数据量的爆发式增长使得大数据处理成为了一个至关重要的领域。面对PB级甚至EB级的数据,传统的数据处理技术已无法满足需求,因此,发展出了多种高效的...
大数据量、海量数据处理方法总结 大数据量的问题是许多面试笔试中经常出现的问题,许多涉及到海量数据的公司经常会问到,这些方法可以基本上处理绝大多数遇到的问题。 1. Bloom Filter: Bloom Filter 是一种空间...
【大数据量,海量数据处理方法总结】 大数据量的处理是当今信息技术领域的重要议题,尤其是在互联网巨头如百度、谷歌和腾讯等公司中,处理海量数据的能力是衡量技术实力的关键指标。以下是一些常用的大数据处理方法...
标题中的“大数据量,海量数据处理方法总结参照.pdf”表明这是一个关于处理大量数据的技术文档,主要探讨了在处理海量数据时的各种策略和方法。描述提到这些方法常出现在像百度、谷歌、腾讯这样的大公司面试笔试中,...
【大数据量,海量数据处理方法总结】 大数据量的处理是现代信息技术领域中不可或缺的一部分,尤其在互联网巨头如百度、谷歌和腾讯等公司中,面对海量数据的存储、检索和分析是一项核心挑战。本文将总结一些常见的大...