軟體開發筆記

Subtitle

0%

用 Python 實作迷你搜尋引擎

Posted on Edited on In

大約在一兩年前，我有一位朋友在華盛頓大學修習CSE 163: Intermediate Data Programming，這門課主要使用Python，課程中的一項作業是實作一個小型搜尋引擎，我覺得很有趣於是寫了一遍，也將這件事情分享出來。

Demo

本作業有附2個資料夾，是搜尋時用的靜態文本庫，分別是wikipedia及small_wiki，裡面放的是一些wikipedia的HTML文本，wikipedia資料夾底下有2,089個文本，small_wiki底下則只有70個文本。

  1. 在專案底下開啟Terminal，執行main.py後，指定搜尋引擎的文本庫為wikipedia (亦可是small_wiki) 第一次建立時，由於需要針對整個文本庫進行分析，文本庫越大，花費的時間越久。
  2. 輸入搜尋關鍵字，本例是”android” 搜尋結果會依關聯性排序，且搜尋速度會非常快。
作業簡述

自定義兩個classes，分別是Document和SearchEngine：

  • Document負責扮演在搜尋引擎中的單個文件
  • SearchEngine負責處理從一堆文件中進行查詢的邏輯

SearchEngine中會使用到TF-IDF演算法計算搜尋關鍵字和每個文件之間的關聯程度。

TF-IDF
Term Fequency - 指搜尋關鍵字在該文件中的出現頻率(詞頻)。
Inverse Document Frequency - 由於某些詞的使用非常普遍而在文件中不斷的出現(比如英文文章中的”the”)，這可能使該詞的權重變高，但它可能不是一個重要的搜尋關鍵字，因此使用IDF來計算該詞在所有文件中的出現頻率，如果在所有文件中，該詞頻仍然很高，那麼它與文件的關聯性被認為是較低的，因此會透過得出的值去減少該詞的權重。

實作

main.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# Author Dylan Jergens
# This program runs the search engine, taking user input

from search_engine import SearchEngine

def main():
    print('Welcome to 6oog13!!')
    directory = input('Please enter a the name of a directory: ')

    print('Building Search Engine...')
    print()
    engine = SearchEngine(directory)

    answer = 'y'
    while (answer == 'y'):
        term = input('Search (enter a term to query): ')
        ranking = engine.search(term)
        print("Displaying results for " + "'" + term + "':")
        if ranking is None:
            print('    No results :(')
        else:
            rank = 1
            for doc in ranking:
                print('    ' + str(rank) + '. ' + doc)
                rank += 1
            print()
        answer = ''
        while not (answer == 'y' or answer == 'n'):
            answer = input('Would you like to search another term (y/n) ')

if __name__ == '__main__':
    main()

document.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import re

class Document:
    def __init__(self, filepath):
        self.filepath = filepath
        self.file = open(filepath)
        self.term_dict = {}
        self.term_list = []

        for line in self.file:
            for word in line.split():
                word = re.sub(r'\W+', '', word)
                self.term_list.append(word.casefold())

        for word in self.term_list:
            num_of_words = len(self.term_list)
            if word not in self.term_dict:
                self.term_dict[word] = 1 / num_of_words
            else:
                self.term_dict[word] = (self.term_dict[word] * num_of_words + 1) / num_of_words

    def get_path(self):
        return self.filepath

    def term_frequency(self, key):
        key = re.sub(r'\W+', '', key)
        key = key.casefold()
        result = self.term_dict.get(key)
        if result is None:
            return 0
        return result

    def get_words(self):
        term_set = set(self.term_list)
        set_to_list = list(term_set)
        return set_to_list

search_engine.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import math
import os
import re
from document import Document

class SearchEngine:
    def __init__(self, directory):
        self.__allDocs = []
        self.__inverse_indexed = {}
        for filename in os.listdir(directory):
            doc = Document(directory + '/' + filename)
            self.__allDocs.append(doc)
        for doc in self.__allDocs:
            for term in doc.get_words():
                if not term in self.__inverse_indexed:
                    self.__inverse_indexed[term] = []
                self.__inverse_indexed[term].append(doc.get_path())

    def _calculate_idf(self, term):
        if term not in self.__inverse_indexed:
            return 0
        else:
            total_num_of_docs = len(self.__allDocs)
            num_of_docs_contain_term = len(self.__inverse_indexed[term])
            idf = math.log(total_num_of_docs / num_of_docs_contain_term)
        return idf

    def search(self, query):
        tf = 0
        tf_idf = 0
        tf_idf_list = []
        return_list = []
        terms = query.split()
        for doc in self.__allDocs:
            tf_idf_sum = 0
            for term in terms:
                term = re.sub(r'\W+', '', term)
                term = term.casefold()
                tf = doc.term_frequency(term)
                idf = self._calculate_idf(term)
                tf_idf = tf * idf
                tf_idf_sum += tf_idf
            tf_idf_list.append((doc.get_path(), tf_idf_sum))
        tf_idf_list = sorted(tf_idf_list, key = lambda tup: tup[1], reverse = True)
        for per_tf_idf in tf_idf_list:
            if per_tf_idf[1]:
                return_list.append(per_tf_idf[0])
        if not return_list:
            return None
        return return_list
結論

除了這門課以外，我也參與過CSE 142: Computer Programming I所有的作業，個人認為華盛頓大學這幾門課，每一次的課堂內容和進度都不多，更多的是給學生時間獨立解決問題，而他們的作業都出得非常用心，每一個作業都和當週課堂內容與老師期望學生得到的技能有很深的關係並讓學生專注於此。另外也有詳細的文件，讓學生清楚作業要求的同時也會一點一點給學生提示和引導，培養學生解題的邏輯。

更重要的是，每個作業都有一個小小的主題而不致乏味，並在作業之中要求學生的程式碼品質，能在一份作業當中同時給予、培養學生多項實用的技能，是我覺得很難得的部分。