IT工程師數位筆記本

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的講義在這里