1. 题目
第 0006 题：你有一个目录，放了你一个月的日记，都是 txt，为了避免分词的问题，假设内容都是英文，请统计出你认为每篇日记最重要的词。
2. 扩展
- 利用堆来实现统计Top K的重要的词
- 实现可扩展的堆（支持节点可以为任意类型）
3. 实现堆
class MinHeap:
def __init__(self):
self.heap_list = [()]
self.size = 0
def compare(self, item1, item2):
if item1[1] < item2[1]:
return 1
elif item1[1] == item2[1]:
return 0
else:
return -1
def flow_up(self, i):
while i // 2 > 0:
if self.compare(self.heap_list[i], self.heap_list[i//2]) < 0:
tmp = self.heap_list[i//2]
self.heap_list[i//2] = self.heap_list[i]
self.heap_list[i] = tmp
i //= 2
def insert(self, item):
self.heap_list.append(item)
self.size += 1
self.flow_up(self.size)
def flow_down(self, i):
while i*2 <= self.size:
min_child = self.get_min_child(i)
if self.compare(self.heap_list[i], self.heap_list[min_child]) > 0:
tmp = self.heap_list[min_child]
self.heap_list[min_child] = self.heap_list[i]
self.heap_list[i] = tmp
i = min_child
def get_min_child(self, i):
if i*2+1 > self.size:
return i*2
else:
if self.compare(self.heap_list[i*2], self.heap_list[i*2+1]) < 0:
return i*2
else:
return i*2+1
def pop_min(self):
min_item = self.heap_list[1]
self.heap_list[1] = self.heap_list[self.size]
self.size -= 1
self.heap_list.pop()
self.flow_down(1)
return min_item
def build_heap(self, word_dict):
i = len(word_dict) // 2
self.size = len(word_dict)
for item in word_dict.items():
self.heap_list.append(item)
while i > 0:
self.flow_down(i)
i -= 1
注意：当需要使用堆时，只需要继承这个类，重写compare()和build_heap()方法即可。
4. 实现选词
# -*- coding:utf-8 -*-
import re
import os
import os.path
from min_heap import MinHeap
def get_word_dic(file_path=None):
if file_path is None:
print("Error")
return
word_dict = {}
with open(file_path, "r", encoding="utf-8") as file:
for line in file.readlines():
words = re.findall(r"[a-z\'_-]+\b", line.lower())
for word in words:
if word not in word_dict:
word_dict[word] = 1
else:
word_dict[word] += 1
return word_dict
def get_top_k_words(word_dict, k):
result = []
dont_count = get_not_important_word_list("not-important-words.txt")
min_heap = MinHeap()
min_heap.build_heap(word_dict)
while k > 0:
item = min_heap.pop_min()
if item[0] not in dont_count:
result.append(item)
k -= 1
return result
def get_not_important_word_list(path):
with open(path, "r", encoding="utf-8") as file:
words = re.findall(r"[a-z\'_-]+", file.read().lower())
return words
def get_words_important_dict(dir_path):
if not os.path.isdir(dir_path):
print("plz input path")
return
files = [os.path.join(dir_path, x) for x in os.listdir(dir_path) if os.path.splitext(x)[1] == ".txt" and x != "not-important-words.txt"]
for file in files:
print("File: " + file)
word_dict = get_word_dic(file)
print(get_top_k_words(word_dict, 10))
if __name__ == "__main__":
get_words_important_dict(".")
