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