Think Python/案例研究：資料結構選擇

Think Python

詞頻分析

像往常一樣，在閱讀我的解決方案之前，你至少應該嘗試以下練習。

練習 1

編寫一個程式，讀取檔案，將每行分解成詞語，從詞語中去除空格和標點符號，並將它們轉換為小寫。

提示：'string' 模組提供了名為 'whitespace' 的字串，其中包含空格、製表符、換行符等，以及 'punctuation'，其中包含標點符號字元。讓我們看看我們是否能讓 Python 說髒話

>>> import string
>>> print string.punctuation
!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~

此外，你也可以考慮使用字串方法 'strip'、'replace' 和 'translate'。

練習 2

訪問 Project Gutenberg ('gutenberg.org') 並下載你喜歡的公有領域書籍的純文字格式。

修改你之前練習中的程式，以讀取你下載的書籍，跳過檔案開頭處的標題資訊，並像之前一樣處理其餘的詞語。

然後修改程式以統計書籍中的總詞語數量，以及每個詞語出現的次數。

列印書籍中使用的不同詞語數量。比較不同作者、不同時代寫的不同書籍。哪位作者使用的詞彙最廣泛？

練習 3

修改之前練習中的程式，以列印書籍中最常用的 20 個詞語。

練習 4

修改之前的程式，以讀取一個詞語列表（參見第 '9.1' 節），然後列印書籍中不在詞語列表中的所有詞語。有多少個是拼寫錯誤？有多少個是應該在詞語列表中的常見詞語，又有多少個是真正冷門的詞語？

隨機數

給定相同的輸入，大多數計算機程式每次都會生成相同的輸出，因此被稱為確定性程式。確定性通常是好事，因為我們期望相同的計算產生相同的結果。但是，對於某些應用而言，我們希望計算機是不可預測的。

使程式真正地非確定性並非易事，但有一些方法可以使它至少看起來非確定性。其中之一是使用生成偽隨機數的演算法。偽隨機數不是真正隨機的，因為它們是由確定性計算生成的，但是僅透過檢視這些數字，幾乎不可能將它們與隨機數區分開來。

該random模組提供了用於生成偽隨機數的函式（從這裡開始，我將簡單地稱為“隨機數”）。

該函式random返回一個介於 0.0 和 1.0 之間的隨機浮點數（包括 0.0，但不包括 1.0）。每次呼叫random時，你都會得到一個長序列中的下一個數字。要檢視示例，請執行此迴圈

import random
for i in range(10):
    x = random.random()
    print x

該函式randint接受引數low和high並返回一個介於low和high之間的整數（包括兩者）。

>>> random.randint(5, 10)
5
>>> random.randint(5, 10)
9

要從序列中隨機選擇一個元素，可以使用choice:

>>> t = [1, 2, 3]
>>> random.choice(t)
2
>>> random.choice(t)
3

該random模組還提供了用於從連續分佈中生成隨機值的函式，包括高斯分佈、指數分佈、伽馬分佈以及其他幾個分佈。

練習 5

編寫一個名為 choose_from_hist 的函式，它接受第 '11.1' 節中定義的直方圖作為引數，並從直方圖中返回一個隨機值，該值以與頻率成比例的機率選擇。例如，對於以下直方圖：

>>> t = ['a', 'a', 'b']
>>> h = histogram(t)
>>> print h
{'a': 2, 'b': 1}

你的函式應該以 '2/3' 的機率選擇 '’a’'，以 '1/3' 的機率選擇 b。

詞直方圖

以下是一個讀取檔案並構建檔案中詞語直方圖的程式

import string

def process_file(filename):
    h = dict()
    fp = open(filename)
    for line in fp:
        process_line(line, h)
    return h

def process_line(line, h):
    line = line.replace('-', ' ')
    
    for word in line.split():
        word = word.strip(string.punctuation + string.whitespace)
        word = word.lower()

        h[word] = h.get(word, 0) + 1

hist = process_file('emma.txt')

該程式讀取emma.txt，其中包含簡·奧斯汀的《艾瑪》的文字。

process_file 迴圈遍歷檔案中的行，將它們一次一行地傳遞給 process_line。直方圖h被用作累加器。

process_line 使用字串方法replace在使用split將行分解成字串列表之前，將連字元替換為空格。它遍歷詞語列表，並使用strip和lower去除標點符號並轉換為小寫。（簡而言之，可以說字串被“轉換”；請記住，字串是不可變的，因此像strip和lower這樣的方法會返回新的字串。）

最後，process_line 透過建立新項或遞增現有項來更新直方圖。

要統計檔案中總詞語數量，我們可以將直方圖中的頻率加起來

def total_words(h):
    return sum(h.values())

不同詞語的數量僅僅是字典中的項數

def different_words(h):
    return len(h)

以下是一些列印結果的程式碼

print 'Total number of words:', total_words(hist)
print 'Number of different words:', different_words(hist)

以及結果

Total number of words: 161073
Number of different words: 7212

最常見的詞

要查詢最常見的詞，我們可以應用 DSU 模式；most_common 接受一個直方圖並返回一個詞語-頻率元組列表，該列表按頻率的逆序排序

def most_common(h):
    t = []
    for key, value in h.items():
        t.append((value, key))

    t.sort(reverse=True)
    return t

以下是一個迴圈，列印十個最常見的詞

t = most_common(hist)
print 'The most common words are:'
for freq, word in t[0:10]:
    print word, '\t', freq

以及來自《艾瑪》的結果

The most common words are:
to      5242
the     5204
and     4897
of      4293
i       3191
a       3130
it      2529
her     2483
was     2400
she     2364

可選引數

我們已經看到了內建函式和方法，它們可以接受可變數量的引數。也可以編寫帶可選引數的使用者定義函式。例如，以下函式列印直方圖中最常見的詞。

def print_most_common(hist, num=10)
    t = most_common(hist)
    print 'The most common words are:'
    for freq, word in t[0:num]:
        print word, '\t', freq

第一個引數是必需的；第二個是可選的。的 **預設值** 為num是 10。

如果只提供一個引數

print_most_common(hist)

num獲取預設值。如果你提供兩個引數

print_most_common(hist, 20)

num獲取引數的值。換句話說，可選引數 **覆蓋** 預設值。

如果函式同時具有必需引數和可選引數，則所有必需引數必須放在前面，後面是可選引數。

字典減法

從書中找到不在詞表中的詞words.txt是一個你可能認出的集合減法問題；也就是說，我們想找到一個集合中（書中的詞）不在另一個集合中（詞表中的詞）的所有詞。

subtract接受字典d1和d2並返回一個新的字典，其中包含來自d1但不包含在d2中的所有鍵。由於我們並不關心值，因此將它們全部設定為 None。

def subtract(d1, d2):
    res = dict()
    for key in d1:
        if key not in d2:
            res[key] = None
    return res

為了找到書中不在words.txt中的詞，我們可以使用 process_file 為words.txt構建直方圖，然後減去

words = process_file('words.txt')
diff = subtract(hist, words)

print "The words in the book that aren't in the word list are:"
for word in diff.keys():
    print word,

以下是 Emma 中的一些結果。

The words in the book that aren't in the word list are:
 rencontre jane's blanche woodhouses disingenuousness 
friend's venice apartment ...

其中一些詞是名字和所有格。其他詞，比如“rencontre”，現在已經不再常用。但有一些是應該出現在詞表中的常用詞！

練習 6

Python 提供了一個名為 'set' 的資料結構，它提供了許多常見的集合運算。閱讀 'docs.python.org/lib/types-set.html' 上的文件，並編寫一個使用集合減法查詢書中不在詞表中的詞的程式。

隨機詞

為了從直方圖中選擇一個隨機詞，最簡單的演算法是根據觀察到的頻率構建一個包含每個詞多個副本的列表，然後從該列表中進行選擇。

def random_word(h):
    t = []
    for word, freq in h.items():
        t.extend([word] * freq)

    return random.choice(t)

表示式[word] * freq建立一個包含freq個字串副本的列表word。的extend方法類似於append，只是引數是序列。

練習 7

此演算法有效，但效率不高；每次選擇一個隨機詞時，它都會重建列表，該列表與原始書籍一樣大。一個顯而易見的改進是一次構建列表，然後進行多次選擇，但列表仍然很大。

另一種方法是

使用 'keys' 獲取書中詞的列表。
構建一個包含詞頻率累積和的列表（參見練習 '10.1'）。此列表中的最後一個專案是書中詞的總數 'n'。

從 1 到 'n' 之間選擇一個隨機數。使用二分搜尋（參見練習 '10.8'）查詢將隨機數插入累積和中的索引。

使用該索引在詞表中查詢相應的詞。

編寫一個使用此演算法從書中選擇隨機詞的程式。

馬爾可夫分析

如果隨機選擇書中的詞，你可以瞭解詞彙量，但你可能不會得到一個句子。

this the small regard harriet which knightley's it most things

一系列隨機詞很少有意義，因為連續詞之間沒有關係。例如，在真實的句子中，你希望像“the”這樣的冠詞後面跟著形容詞或名詞，而不是動詞或副詞。

衡量這些關係的一種方法是馬爾可夫分析，它表徵了給定詞序列中下一個詞出現的機率。例如，歌曲 Eric, the Half a Bee 這樣開頭

Half a bee, philosophically,
Must, ipso facto, half not be.
But half the bee has got to be
Vis a vis, its entity. D’you see?

But can a bee be said to be
Or not to be an entire bee
When half the bee is not a bee
Due to some ancient injury?

在這段文字中，短語“half the”後面總是跟著詞“bee”，但短語“the bee”後面可能跟著“has”或“is”。

馬爾可夫分析的結果是從每個字首（如“half the”和“the bee”）到所有可能的詞尾（如“has”和“is”）的對映。

有了這種對映，你可以透過從任何字首開始，並從可能的詞尾中隨機選擇，生成隨機文字。接下來，你可以組合字首的末尾和新的詞尾來形成下一個字首，並重復此過程。

例如，如果你從字首“Half a”開始，則下一個詞必須是“bee”，因為該字首在文字中只出現一次。下一個字首是“a bee”，因此下一個詞尾可能是“philosophically”、“be”或“due”。

在本例中，字首的長度始終為 2，但你可以使用任何字首長度進行馬爾可夫分析。字首的長度稱為分析的“階”。

練習 8

馬爾可夫分析

編寫一個程式從檔案讀取文字並執行馬爾可夫分析。結果應該是一個字典，它將字首對映到可能的詞尾集合。該集合可以是列表、元組或字典；由你來做出適當的選擇。你可以使用長度為 2 的字首測試程式，但你應該以易於嘗試其他長度的方式編寫程式。
在前面的程式中新增一個函式，用於根據馬爾可夫分析生成隨機文字。以下是從 Emma 中以長度為 2 的字首生成的示例：

He was very clever, be it sweetness or be angry, ashamed or only
amused, at such a stroke. She had never thought of Hannah till you were never meant for me?" "I cannot make speeches, Emma:" he soon cut it all himself.

對於此示例，我將標點符號保留在詞語中。結果幾乎是語法正確的，但並不完全。在語義上，它幾乎是有意義的，但並不完全。

如果你增加字首長度會發生什麼？隨機文字是否有更多意義？
程式執行後，你可能想嘗試混搭：如果你分析兩本或更多本書的文字，你生成的隨機文字將以有趣的方式融合來自這些來源的詞彙和短語。

資料結構

使用馬爾可夫分析生成隨機文字很有趣，但這項練習也有一些意義：資料結構選擇。在解決前面練習時，你必須選擇

如何表示字首。
如何表示可能的詞尾集合。
如何表示從每個字首到可能的詞尾集合的對映。

好的，最後一個很簡單；我們唯一見過的對映型別是字典，因此它是自然的選擇。

對於字首，最明顯的選項是字串、字串列表或字串元組。對於詞尾，一個選項是列表；另一個是直方圖（字典）。

你應該如何選擇？第一步是考慮你需要為每個資料結構實現的操作。對於字首，我們需要能夠從開頭刪除詞語並新增到結尾。例如，如果當前字首是“Half a”，下一個詞是“bee”，則你需要能夠形成下一個字首“a bee”。

你可能首先選擇列表，因為它易於新增和刪除元素，但我們還需要能夠在字典中使用字首作為鍵，因此這排除了列表。對於元組，你無法追加或刪除，但你可以使用加法運算子來形成新的元組。

def shift(prefix, word):
    return prefix[1:] + (word,)

shift接受一個詞語元組prefix和一個字串word，並形成一個新的元組，其中包含所有詞語prefix，除了第一個，並將word新增到結尾。

對於詞尾集合，我們需要執行的操作包括新增新的詞尾（或增加現有詞尾的頻率），以及選擇隨機詞尾。

為列表實現或直方圖新增新字尾同樣簡單。從列表中選擇隨機元素很容易；從直方圖中選擇則難以高效地完成（參見練習 13.7）。

到目前為止，我們主要討論了實現的難易程度，但在選擇資料結構時還需要考慮其他因素。其中之一是執行時間。有時，理論上會認為一種資料結構比另一種更快；例如，我提到過，在運算子對字典來說比列表更快，至少在元素數量較大的情況下是這樣。

但通常情況下，你事先並不知道哪種實現更快。一種選擇是同時實現兩種，然後比較哪一種更好。這種方法被稱為**基準測試**。一種實用的替代方案是選擇最容易實現的資料結構，然後看看它是否足夠快以滿足預期應用的需求。如果足夠快，就無需再進行其他操作。如果不夠快，可以使用一些工具，例如profile模組，來識別程式中花費時間最多的部分。

另一個需要考慮的因素是儲存空間。例如，使用直方圖來收集字尾可能會佔用更少的空間，因為你只需要儲存每個單詞一次，無論它在文字中出現多少次。在某些情況下，節省空間也可以使你的程式執行更快，而在極端情況下，如果記憶體不足，你的程式可能根本無法執行。但對於許多應用程式來說，空間在執行時間之後是次要考慮因素。

最後一點：在本次討論中，我隱含地假設應該為分析和生成使用同一種資料結構。但由於它們是獨立的階段，也可以使用一種結構進行分析，然後轉換為另一種結構進行生成。如果生成過程中節省的時間超過了轉換所花費的時間，這將是一次淨收益。

除錯

當你除錯程式時，尤其是在處理棘手的錯誤時，可以嘗試以下四件事

閱讀: 檢查你的程式碼，將其讀給自己聽，並確保它表達了你想要表達的意思。
執行: 透過進行更改並執行不同版本進行實驗。通常情況下，如果你在程式的正確位置顯示了正確的東西，問題就會變得很明顯，但有時你可能需要花費一些時間來搭建腳手架。
沉思: 花一些時間思考！這是什麼型別的錯誤：語法錯誤、執行時錯誤、語義錯誤？你可以從錯誤訊息或程式輸出中獲得什麼資訊？什麼型別的錯誤會導致你看到的這個問題？在你出現問題之前，你最後修改了什麼？
退回: 在某些情況下，最好的辦法是退回，撤消最近的更改，直到你回到一個能夠正常工作且你理解的程式。然後你可以開始重建。

初學者有時會陷入其中一項活動而忘記其他活動。每個活動都有其自身的失敗模式。

例如，如果問題是打字錯誤，閱讀你的程式碼可能會有所幫助，但如果問題是概念性誤解，則不會。如果你不理解你的程式做了什麼，你可以閱讀它 100 次，但永遠不會發現錯誤，因為錯誤是在你的頭腦中。

執行實驗可能會有所幫助，尤其是在執行小型、簡單的測試時。但如果你在沒有思考或閱讀程式碼的情況下執行實驗，你可能會陷入一種我稱為“隨機漫步程式設計”的模式，即透過進行隨機更改直到程式做正確的事情的過程。不用說，隨機漫步程式設計可能需要很長時間。

你必須花時間思考。除錯就像實驗科學。你應該至少有一個關於問題是什麼的假設。如果有兩個或多個可能性，請嘗試想出一個可以消除其中一種可能性的測試。

休息有助於思考。說話也有幫助。如果你向別人（甚至你自己）解釋這個問題，你可能會在問完問題之前找到答案。

但即使是最有效的除錯技巧，如果錯誤過多，或者你試圖修復的程式碼太大太複雜，也會失敗。有時，最好的選擇是退回，簡化程式，直到你得到一個能夠正常工作且你理解的程式。

初學者通常不願意退回，因為他們不喜歡刪除程式碼行（即使是錯誤的程式碼行）。如果你感覺好一些，在你開始拆卸程式之前，將你的程式複製到另一個檔案中。然後，你可以一次將這些片段貼上回去。

找到一個棘手的錯誤需要閱讀、執行、沉思，有時還需要退回。如果你被其中一項活動卡住了，請嘗試其他活動。

術語表

確定性: 指一個程式在每次執行時，給定相同的輸入，都會做同樣的事情。
偽隨機: 指一個序列的數字看起來是隨機的，但實際上是由確定性程式生成的。
預設值: 如果未提供引數，則為可選引數指定的值。
覆蓋: 用引數替換預設值。
基準測試: 透過實現替代方案並在可能的輸入樣本上進行測試來選擇資料結構的過程。

練習

練習 9

一個詞的“等級”是指它在按頻率排序的詞列表中的位置：最常見的詞的等級為 1，第二常見的詞的等級為 2，依此類推。

齊夫定律描述了自然語言中詞的等級和頻率之間的關係¹。具體來說，它預測等級為 r 的詞的頻率 f 為：

f = c r^−s

其中 s 和 c 是取決於語言和文字的引數。如果你對等式兩邊取對數，你會得到

logf = log c − s log r

因此，如果你繪製 $\log {f}$ 相對於 $\log {r}$ 的圖，你應該得到一條斜率為 $-s$ 且截距為 $\log {c}$ 的直線。

編寫一個程式，從檔案讀取文字，統計單詞頻率，並按頻率降序排列，為每個單詞輸出一行，包含 $\log {f}$ 和 $log{r}$ 。使用您選擇的繪圖程式繪製結果，並檢查它們是否形成直線。您可以估計 $s$ 的值嗎？

備註

1: 請參閱wikipedia.org/wiki/Zipf's_law