锐客网

  1. 首页 > 睿知 > it技术 > >

php大数据检索 php处理大数据量数据的思路( 三 )

IT技术完毕


"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字节 。
10.分布式处理 mapreduce
适用范围：数据量大，但是数据种类小可以放入内存
基本原理及要点：将数据交给不同的机器去处理，数据划分，结果归约 。
扩展：
问题实例：
1).The canonical example application of MapReduce is a process to count the appearances of
each different word in a set of documents:
void map(String name, String document):
// name: document name
// document: document contents
for each word w in document:
EmitIntermediate(w, 1);
void reduce(String word, Iterator partialCounts):
// key: a word
// values: a list of aggregated partial counts
int result = 0;
for each v in partialCounts:
result += ParseInt(v);
Emit(result);
Here, each document is split in words, and each word is counted initially with a "1" value by
the Map function, using the word as the result key. The framework puts together all the pairs
with the same key and feeds them to the same call to Reduce, thus this function just needs to
sum all of its input values to find the total appearances of that word.
2).海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10 。
3).一共有N个机器，每个机器上有N个数 。每个机器最多存O(N)个数并对它们操作 。如何找到N^2个数的中数(median)？
经典问题分析
上千万or亿数据（有重复），统计其中出现次数最多的前N个数据,分两种情况：可一次读入内存，不可一次读入 。
可用思路：trie树+堆，数据库索引，划分子集分别统计，hash ， 分布式计算，近似统计，外排序
所谓的是否能一次读入内存，实际上应该指去除重复后的数据量 。如果去重后数据可以放入内存，我们可以为数据建立字典，比如通过 map，hashmap，trie，然后直接进行统计即可 。当然在更新每条数据的出现次数的时候，我们可以利用一个堆来维护出现次数最多的前N个数据 ， 当然这样导致维护次数增加，不如完全统计后在求前N大效率高 。

推荐阅读


上一篇：c语言输入x按公式计算y，c语言编写公式计算

下一篇：怎么把显卡的视频剪出来，怎么把显卡的视频剪出来保存