MIT6.006是算法导论,Lec02讲的是Document Distance(文档距离),比如比较两个文档相似度或者搜索引擎中都会用到。

计算步骤为:

1.将每个文档分离为单词

2.统计词频

3.计算点积(并做除法)

说明:

1.“单词”指的是字母和数字(alphanumeric)

2.每个文档统计完词频后得到的list,可看作一个向量

3.两个文档间的相似度,是相似的单词除以总的单词,类似于两个向量的夹角公式

MIT6.006下载的相关资源中,给出了8个逐渐改善的代码版本,但本质都是一样的。代码8短小精悍,我添加了一些中文注释

#coding:utf8
#description:计算文档距离
import sys
import math
import string ######################################
#步骤1:读取文件
######################################
def read_file(filename):
try:
f = open(filename, 'r')
return f.read()
except IOError:
print "Error opening or reading input file: ", filename
sys.exit() #####################################
#步骤2:从文本中分离单词
#####################################
translation_table=string.maketrans(string.punctuation+string.uppercase,
" "*len(string.punctuation)+string.lowercase) def get_words_from_line_list(text):
"""从给定的文本中找出所有的单词,返回一个list"""
text = text.translate(translation_table)
word_list = text.split()
return word_list ######################################
#步骤3:统计词频
######################################
def count_frequency(word_list):
D = {}
for new_word in word_list:
if new_word in D:
D[new_word] = D[new_word] + 1
else:
D[new_word] = 1
return D def word_frequencies_for_file(filename):
"""返回(单词,频率)组成的list"""
line_list = read_file(filename)
word_list = get_words_from_line_list(line_list)
freq_mapping = count_frequency(word_list)
return freq_mapping def inner_product(D1, D2):
sum = 0.0
for key in D1:
if key in D2:
sum += D1[key] * D2[key]
return sum def vector_angle(D1, D2):
"""计算两个向量的夹角"""
numerator = inner_product(D1, D2)
denominator = math.sqrt(inner_product(D1,D1)*inner_product(D2,D2))
return math.acos(numerator/denominator) def main():
if len(sys.argv) != 3:
print "Usage: docdist.py filename_1 filename_2"
else:
filename_1 = sys.argv[1]
filename_2 = sys.argv[2]
sorted_word_list_1 = word_frequencies_for_file(filename_1)
sorted_word_list_2 = word_frequencies_for_file(filename_2)
distance = vector_angle(sorted_word_list_1, sorted_word_list_2)
print "The distance between the document is: %0.6f (radians)"%distance if __name__ == '__main__':
main()

 Lec02的讲义在这里 

05-11 21:53