数据处理题.md

数据处理题

简单统计文件中的词频

from string import punctuation
 
#对文本的每一行计算词频的函数
def processLine(line,wordCounts):
    #用空格替换标点符号
    line=replacePunctuations(line)
    words = line.split()
    for word in words:
        if word in wordCounts:
            wordCounts[word]+=1
        else:
            wordCounts[word]=1
 
def replacePunctuations(line):
    for ch in line :
        #这里直接用了string的标点符号库。将标点符号替换成空格
        if ch in punctuation:
            line=line.replace(ch," ")
        return line
 
def main():
    infile=open("englishi.txt",'r')
    count=10
    words=[]
    data=[]
 
    # 建立用于计算词频的空字典
    wordCounts={}
    for line in infile:
        processLine(line.lower(), wordCounts)#这里line.lower()的作用是将大写替换成小写，方便统计词频
    #从字典中获取数据对
    pairs = list(wordCounts.items())
    #列表中的数据对交换位置,数据对排序
    items = [[x,y]for (y,x)in pairs]
    items.sort()
    #因为sort()函数是从小到大排列，所以range是从最后一项开始取
    for i in range(len(items) - 1, len(items) - count - 1, -1):
        print(items[i][1] + "\t" + str(items[i][0]))
        data.append(items[i][0])
        words.append(items[i][1])
 
    infile.close()
 
if __name__ == '__main__':
    main()

海量数据求topk

有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。

方案：顺序读文件中，对于每个词x，取hash(x)%5000，然后按照该值存到5000个小文件（记为x0,x1,...x4999）中。这样每个文件大概是200k左右。

如果其中的有的文件超过了1M大小，还可以按照类似的方法继续往下分，直到分解得到的小文件的大小都不超过1M。

对每个小文件，统计每个文件中出现的词以及相应的频率（可以采用trie树/hash_map等），并取出出现频率最大的100个词（可以用含100个结点的最小堆？？？），并把100个词及相应的频率存入文件，这样又得到了5000个文件。下一步就是把这5000个文件进行归并（类似与归并排序）的过程了。

1. python中计算字符串hash的函数就是 hash(x)
2. 使用trie或者hashmap统计每个子文件中的词频
3. 使用heap统计频率前100大的单词或者直接排序
4. 归并子文件中词频前100大的单词

补充：字符串hash方法

求一个字符串的hash值：

• 现在我们希望找到一个hash函数，使得每一个字符串都能够映射到一个整数上
• 比如hash[i]=(hash[i-1]*p+idx(s[i]))%mod
• 字符串：abc，bbc，aba，aadaabac
• 字符串下标从0开始
• 先把a映射为1，b映射为2，c->3，d->4,即idx(a)=1, idx(b)=2, idx(c)=3,idx(d)=4； 好！开始对字符串进行hash

假设我们取p=13 ，mod=101

先把abc映射为一个整数

hash[0]=1，表示 a 映射为1

hash[1]=(hash[0]*p+idx(b))%mod=15，表示 ab 映射为 15

hash[2]=(hash[1]*p+idx(c))%mod=97

这样，我们就把 abc 映射为 97 这个数字了。