锐客网

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

数据字典php 数据字典名词解释( 三 )

IT技术语言


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字节 。
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，分布式计算，近似统计，外排序

推荐阅读


上一篇：怎么让手机显卡报废，怎么让一个手机报废

下一篇：如何统计跨境电商，如何统计跨境电商销售数据