MIT 6.0001 PS5:用 Python 对新闻片段进行触发过滤

请注意,本文编写于 173 天前,最后修改于 148 天前,其中某些信息可能已经过时。

本文是我对 MIT 6.0001 课程(Introduction to Computer Science and Programming in Python)配套作业 Problem Set 5 的解答。仅供参考。

问题描述

详细的要求见原题,从 MIT OCW 下载原题:Problem Set 5 (ZIP) (This file contains: 5 .py files, 1 .pdf file and 1 .txt file.)

求解思路

Problem 1

从谷歌和雅虎下载 RSS feed 和解析 XML 的工作已经完成,我们只需要在其基础上定义NewsStory类即可。NewsStory有五个成员变量,guidtitledescriptionlinkpubdate,构造函数接受相应的五个参数,另外这五个成员变量各自有一个 getter 函数。

该类的实现一目了然:

class NewsStory():
    def __init__(self, guid, title, description, link, pubdate):
        self.guid = guid
        self.title = title
        self.description = description
        self.link = link
        self.pubdate = pubdate
    def get_guid(self):
        return self.guid
    def get_title(self):
        return self.title
    def get_description(self):
        return self.description
    def get_link(self):
        return self.link
    def get_pubdate(self):
        return self.pubdate

运行ps5_test.py,单元测试通过:

testNewsStoryConstructor (__main__.ProblemSet5NewsStory) ... ok
testNewsStoryGetGuid (__main__.ProblemSet5NewsStory) ... ok
testNewsStoryGetLink (__main__.ProblemSet5NewsStory) ... ok
testNewsStoryGetTime (__main__.ProblemSet5NewsStory) ... ok
testNewsStoryGetTitle (__main__.ProblemSet5NewsStory) ... ok
testNewsStoryGetdescription (__main__.ProblemSet5NewsStory) ... ok

Problem 2

触发器概述

“Triggers”译为触发器,旨在根据不同的触发条件对新闻(news story)返回一个布尔值进行触发,进而由程序决定是显示这条新闻还是丢弃它。

Trigger类作为基类,它下面有多个子类,继承关系如下图:

需要注意的是,Trigger对象中的evaluate方法不会被直接调用,因此该方法中抛出一个异常NotImplementedError,防止意外地调用它。正确的操作是,为每一个可调用的类重写evaluate方法,从而处理不同的触发条件。

词组触发器(Phrase Triggers)

PhraseTrigger类有一个成员变量phrase表示作为触发条件的词组。此外类中定义了一个is_phrase_in函数,该函数接受一个参数text,如果phrase完整地按顺序出现在了text中,那么返回 True,否则返回 False。

首先注意phrase对大小写不敏感,所以我们在构造函数中将其转换为全小写:

class PhraseTrigger(Trigger):
    def __init__(self, phrase):
        self.phrase = phrase.lower()

is_phrase_in函数中,首先把textphrase两个字符串分别分割成单词列表text_listphrase_list,然后判断phrase_list是否是phrase_list的子序列。注意“子序列”与“子集”不同,它对顺序有要求。

分割单词前,要首先把text中的特殊符号替换为空格,这使用了字符串的translate方法,传入的参数是构造的一个从特殊符号到空格符的映射关系str.maketrans(string.punctuation, ' '*len(string.punctuation))。然后使用字符串的split方法以空格为分隔符分割单词并得到单词的列表。对于得到的两个列表,判断子序列的方法是,从i = 0开始,判断text_list[i:i+len(phrase_list)]是否与phrase_list相同,逐次递增i,如果到循环结束都没有一个子列相同,那么说明前者不是后者的子列。

def is_phrase_in(self, text):
    text = text.lower()
    text = text.translate(str.maketrans(string.punctuation, ' '*len(string.punctuation)))
    text_list = text.split()
    phrase_list = self.phrase.split()
    for i in range(len(text_list) - len(phrase_list) + 1):
        if text_list[i:i+len(phrase_list)] == phrase_list:
            return True
    return False

这里完成的PhraseTrigger是一个抽象类,不会直接用于创建对象。

Problem 3

TitleTrigger类是PhraseTrigger类的子类,其中重写了Trigger这个间接父类中的evaluate函数。

class TitleTrigger(PhraseTrigger):
    def evaluate(self, story):
        return self.is_phrase_in(story.get_title())

运行ps5_test.py,单元测试通过:

test1TitleTrigger (__main__.ProblemSet5) ... ok

Problem 4

与 Problem 3 非常类似。

class DescriptionTrigger(PhraseTrigger):
    def evaluate(self, story):
        return self.is_phrase_in(story.get_description())

运行ps5_test.py,单元测试通过:

test2DescriptionTrigger (__main__.ProblemSet5) ... ok

Problem 5

TimeTrigger是一个抽象类,其构造函数接受一个表示时间的字符串time_str,时区规定为东部标准时间(EST)。为了统一管理时区,需要用datetime对象的replace(tzinfo=pytz.timezone('EST'))方法转换时区。

class TimeTrigger(Trigger):
    def __init__(self, time_str):
        self.time = datetime.strptime(time_str, "%d %b %Y %H:%M:%S").replace(tzinfo=pytz.timezone('EST'))

Problem 6

BeforeTriggerBeforeTrigger都是TimeTrigger的子类,它们各自重写了Triggerevaluate函数。datetime对象可以直接使用比较运算符来比较。

注意,只有同一时区的时间才能比较,因此也要用replace方法将时间转换为 EST。

class BeforeTrigger(TimeTrigger):
    def evaluate(self, story):
        return story.get_pubdate().replace(tzinfo=pytz.timezone('EST')) < self.time
class AfterTrigger(TimeTrigger):
    def evaluate(self, story):
        return story.get_pubdate().replace(tzinfo=pytz.timezone('EST')) > self.time

运行ps5_test.py,单元测试通过:

test3BeforeAndAfterTrigger (__main__.ProblemSet5) ... ok
test3altBeforeAndAfterTrigger (__main__.ProblemSet5) ... ok

Problem 7

NotTrigger对一个已知的触发器取反。

class NotTrigger(Trigger):
    def __init__(self, trigger):
        self.trigger = trigger

    def evaluate(self, story):
        return not self.trigger.evaluate(story)

运行ps5_test.py,单元测试通过:

test4NotTrigger (__main__.ProblemSet5) ... ok

Problem 8

AndTrigger把两个已知的触发器相与。

class AndTrigger(Trigger):
    def __init__(self, trigger1, trigger2):
        self.trigger1 = trigger1
        self.trigger2 = trigger2

    def evaluate(self, story):
        return self.trigger1.evaluate(story) and self.trigger2.evaluate(story)

运行ps5_test.py,单元测试通过:

test5AndTrigger (__main__.ProblemSet5) ... ok

Problem 9

OrTrigger把两个已知的触发器相或。

class OrTrigger(Trigger):
    def __init__(self, trigger1, trigger2):
        self.trigger1 = trigger1
        self.trigger2 = trigger2

    def evaluate(self, story):
        return self.trigger1.evaluate(story) or self.trigger2.evaluate(story)

运行ps5_test.py,单元测试通过:

test6OrTrigger (__main__.ProblemSet5) ... ok

完成 Problem 9 后,运行ps5.py,可以看到弹出的对话框中显示了大量新闻。从下图右边的滚动条可以看出来显示的内容非常多,这是因为我们还没有使用触发器对新闻进行过滤。

Problem 10

filter_stories函数使用triggerlist列表中的所有触发器对新闻列表stories进行触发,如果一个新闻至少被一个触发器触发,那么保留此新闻;如果一个新闻不能使任何触发器触发,那么丢弃它。这一行为适合用any函数完成。

any函数:若给定的可迭代参数全部为 False,则返回 False;如果至少有一个为 True,则返回 True。

所以思路就是,遍历检查stories,对其中的每条新闻使用any函数检查是否至少有一个触发器返回 True,如果是,则将该新闻添加到result列表中,遍历结束后返回。

def filter_stories(stories, triggerlist):
    result = []  # 成功触发的新闻列表
    for story in stories:
        if any([trigger.evaluate(story) for trigger in triggerlist]):
            result.append(story)
    return result

运行ps5_test.py,单元测试通过:

test7FilterStories (__main__.ProblemSet5) ... ok
test8FilterStories2 (__main__.ProblemSet5) ... ok

运行ps5.py,可以看到新闻数量大大减少(观察右边的滚动条)。

Problem 11

为了突破硬编码触发器的局限性,我们考虑让程序支持从配置文件中读取触发器。使用字典triggers来保存触发器的名称和触发器对象的映射,使用列表result来保存成功添加的触发器对象。

read_trigger_config函数中添加的代码:

triggers = {}  # 文件中触发器名称的字典
result = []    # ADD的触发器列表,作为返回值
for line in lines:
    arguments = line.split(',')  # 用逗号分割一行配置
    if arguments[0] == 'ADD':
        for trigger_name in arguments[1:]:
            result.append(triggers[trigger_name])
    elif arguments[1] == 'TITLE':
        triggers[arguments[0]] = TitleTrigger(arguments[2])
    elif arguments[1] == 'DESCRIPTION':
        triggers[arguments[0]] = DescriptionTrigger(arguments[2])
    elif arguments[1] == 'AFTER':
        triggers[arguments[0]] = AfterTrigger(arguments[2])
    elif arguments[1] == 'BEFORE':
        triggers[arguments[0]] = BeforeTrigger(arguments[2])
    elif arguments[1] == 'NOT':
        triggers[arguments[0]] = NotTrigger(triggers[arguments[2]])
    elif arguments[1] == 'AND':
        triggers[arguments[0]] = AndTrigger(triggers[arguments[2]], triggers[arguments[3]])
    elif arguments[1] == 'OR':
        triggers[arguments[0]] = OrTrigger(triggers[arguments[2]], triggers[arguments[3]])

别忘了最后return result

运行ps5.py,显示了在triggers.txt配置文件中规定的触发器条件下过滤后的新闻。

Problem 12

美国 2016 大选已经过去很长时间了,现在已经不能获得什么相关新闻了。作为代替,我们来关注一下“中美贸易战”。

新建文件trade_triggers.txt,写入以下配置:

// 标题中含有“trade”
t1,TITLE,trade

// 在2019年5月15日后
t2,AFTER,15 May 2019 00:00:00

// 描述中含有“Huawei”
t3,DESCRIPTION,Huawei

// 描述中含有“Trump”
t4,DESCRIPTION,Trump

// t1与t2
t5,AND,t2,t3

// t3与t4
t6,AND,t1,t4

// 加入触发器列表
ADD,t5,t6

将第 250 行代码的参数改为trade_triggers.txt,然后运行ps5.py

运行测试

在 Problem 1~10 中已经进行了单元测试;在 Problem 11 和 Problem 12 中已经进行了整个程序的运行测试。

总结

  • 抽象(基)类。Python 作为一门面向对象编程语言,有着完整的类的继承与多态机制,而且使用起来比 C++ 面向对象更加自由和方便。在 Problem 2 和 Problem 5 中,我们分别定义了PhraseTriggerTimeTrigger这两个抽象类(abstract class),这两个类并没有重写evaluate方法,而是仅仅作为一个接口。具体的方法是由这些抽象类的子类重写的。

Trigger可以称为抽象基类,其中定义了evaluate方法,然而函数体内仅仅是抛出了一个异常。这是因为具体的evaluate功能需要由子类分别实现,Trigger这个抽象基类仅仅是一个接口,事实上不能直接调用Triggerevaluate方法。至于为什么要抛出异常,这只是为了防止我们不小心错误地调用了它,并没有什么实际作用。

另外,在 Python 中,可以使用abc模块来定义抽象基类,这里就不再展开了。

  • 要不要继承 object 类?通过查阅资料得知,在 Python 2 中,继承 object 类的是新式类,不继承 object 类的是经典类。经典类中只有__doc____module__和自己定义的成员;而新式类拥有很多额外的可操作对象(成员变量和方法),如__sizeof____eq____str__等。在 Python 3.x 中,无论是否显式继承 object,都会默认继承 object。所以说这是一个历史遗留问题,现在没必要继承 object

通过以下实验,发现继承与否确实都是一样的(Python 版本为 3.7.1):

>>> class NewClass(object):
...     def __init__(self):
...             print("This is a new class")
...
>>> class OldClass():
...     def __init__(self):
...             print("This is an old class")
...
>>> nc = NewClass()
This is a new class
>>> nc
<__main__.NewClass object at 0x00000159BD9BA908>
>>> oc = OldClass()
This is an old class
>>> dir(nc)
['__class__', '__delattr__', '__dict__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__gt__', '__hash__', '__init__', '__init_subclass__', '__le__', '__lt__', '__module__', '__ne__', '__new__', '__reduce__', '__reduce_ex__',
'__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', '__weakref__']
>>> dir(oc)
['__class__', '__delattr__', '__dict__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__gt__', '__hash__', '__init__', '__init_subclass__', '__le__', '__lt__', '__module__', '__ne__', '__new__', '__reduce__', '__reduce_ex__',
'__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', '__weakref__']
  • datetime 的时区转换。首先注意一点,datetime即是模块名,又是类名,由于在代码文件头部使用了

    from datetime import time

来导入包,因此我们代码中的datetime全部都表示datetime.datetime这个类。

datetime类中有一个replace方法可以改变datetime对象中的值,也可以在不修改时间数值的情况下改变时区,我们用的就是这一功能来将时区规定为 EST 的:

datetime.strptime(time_str, "%d %b %Y %H:%M:%S").replace(tzinfo=pytz.timezone('EST'))

另外需要注意,pytz是外置模块,需要提前 import 进来。

  • any函数。这是一个 Python 内置函数,传入一个可迭代参数,当参数中至少有一个元素是 True 时返回 True;当参数全部都是 False 时返回 False。值得注意的是,元素除了是 0、空值、布尔 False 以外都算作 True。这个函数非常常用,恰当地使用它可以减少代码量和提高可读性。与之类似的函数还有allmap等,它们都是作用于可迭代序列的“统一操作”函数。

随意进行一些测试:

>>> any([0,False, None])
False
>>> any([0, False, None, "", ''])
False
>>> any([0, False, None, "", '', 2])
True
>>> any([0, False, None, "", '', ' '])
True
>>> any(['0', False, None, "", ''])
True

完整代码

本地下载:mit_6.0001_ps5.zip


Comments

添加新评论