12|面向对象(下):如何实现一个搜索引擎?

AI悦创原创
  • Python 进阶
  • Python 进阶
大约 7 分钟

img

你好,我是悦创。这节课,我们来实现一个 Python 的搜索引擎(search engine)。

承接上文,今天这节课的主要目的是,带你模拟敏捷开发过程中的迭代开发流程,巩固面向对象的程序设计思想。

我们将从最简单最直接的搜索做起,一步步优化,这其中,我不会涉及到过多的超纲算法,但不可避免会介绍一些现代搜索引擎中的基础概念,例如语料(corpus)、倒序索引(inverted index)等。

如果你对这方面本身有些了解,自然可以轻松理解;即使你之前完全没接触过搜索引擎,也不用过分担心,我会力求简洁清晰,降低学习难度。同时,我希望你把更多的精力放在面向对象的建模思路上。

“高大上”的搜索引擎

引擎一词尤如其名,听起来非常酷炫。搜索引擎,则是新世纪初期互联网发展最重要的入口之一,依托搜索引擎,中国和美国分别诞生了百度、谷歌等巨型公司。

搜索引擎极大地方便了互联网生活,也成为上网必不可少的刚需工具。依托搜索引擎发展起来的互联网广告,则成了硅谷和中国巨头的核心商业模式;而搜索本身,也在持续进步着, Facebook 和微信也一直有意向在自家社交产品架设搜索平台。

关于搜索引擎的价值我不必多说了,今天我们主要来看一下搜索引擎的核心构成。

听 Google 的朋友说,他们入职培训的时候,有一门课程叫做 The life of a query,内容是讲用户在浏览器中键入一串文字,按下回车后发生了什么。今天我也按照这个思路,来简单介绍下。

我们知道,一个搜索引擎由搜索器、索引器、检索器和用户接口四个部分组成。

搜索器,通俗来讲就是我们常提到的爬虫(scrawler),它能在互联网上大量爬取各类网站的内容,送给索引器。索引器拿到网页和内容后,会对内容进行处理,形成索引(index),存储于内部的数据库等待检索。

最后的用户接口很好理解,是指网页和 App 前端界面,例如百度和谷歌的搜索页面。用户通过用户接口,向搜索引擎发出询问(query),询问解析后送达检索器;检索器高效检索后,再将结果返回给用户。

image-20221008110128108

爬虫知识不是我们今天学习的重点,这里我就不做深入介绍了。我们假设搜索样本存在于本地磁盘上。

为了方便,我们只提供五个文件的检索,内容我放在了下面这段代码中:


# 1.txt
I have a dream that my four little children will one day live in a nation where they will not be judged by the color of their skin but by the content of their character. I have a dream today.

# 2.txt
I have a dream that one day down in Alabama, with its vicious racists, . . . one day right there in Alabama little black boys and black girls will be able to join hands with little white boys and white girls as sisters and brothers. I have a dream today.

# 3.txt
I have a dream that one day every valley shall be exalted, every hill and mountain shall be made low, the rough places will be made plain, and the crooked places will be made straight, and the glory of the Lord shall be revealed, and all flesh shall see it together.

# 4.txt
This is our hope. . . With this faith we will be able to hew out of the mountain of despair a stone of hope. With this faith we will be able to transform the jangling discords of our nation into a beautiful symphony of brotherhood. With this faith we will be able to work together, to pray together, to struggle together, to go to jail together, to stand up for freedom together, knowing that we will be free one day. . . .

# 5.txt
And when this happens, and when we allow freedom ring, when we let it ring from every village and every hamlet, from every state and every city, we will be able to speed up that day when all of God's children, black men and white men, Jews and Gentiles, Protestants and Catholics, will be able to join hands and sing in the words of the old Negro spiritual: "Free at last! Free at last! Thank God Almighty, we are free at last!"

我们先来定义 SearchEngineBase 基类。这里我先给出了具体的代码,你不必着急操作,还是那句话,跟着节奏慢慢学,再难的东西也可以啃得下来。

class SearchEngineBase(object):
    def __init__(self):
        pass

    def add_corpus(self, file_path):
        with open(file_path, 'r') as fin:
            text = fin.read()
        self.process_corpus(file_path, text)

    def process_corpus(self, id, text):
        raise Exception('process_corpus not implemented.')

    def search(self, query):
        raise Exception('search not implemented.')

def main(search_engine):
    for file_path in ['1.txt', '2.txt', '3.txt', '4.txt', '5.txt']:
        search_engine.add_corpus(file_path)

    while True:
        query = input()
        results = search_engine.search(query)
        print('found {} result(s):'.format(len(results)))
        for result in results:
            print(result)

SearchEngineBase 可以被继承,继承的类分别代表不同的算法引擎。每一个引擎都应该实现 process_corpus()search() 两个函数,对应我们刚刚提到的索引器和检索器。main() 函数提供搜索器和用户接口,于是一个简单的包装界面就有了。

具体来看这段代码,其中,

  • add_corpus() 函数负责读取文件内容,将文件路径作为 ID,连同内容一起送到 process_corpus 中。
  • process_corpus 需要对内容进行处理,然后文件路径为 ID ,将处理后的内容存下来。处理后的内容,就叫做索引(index)。
  • search 则给定一个询问,处理询问,再通过索引检索,然后返回。

好,理解这些概念后,接下来,我们实现一个最基本的可以工作的搜索引擎,代码如下:

class SimpleEngine(SearchEngineBase):
    def __init__(self):
        super(SimpleEngine, self).__init__()
        self.__id_to_texts = {}

    def process_corpus(self, id, text):
        self.__id_to_texts[id] = text

    def search(self, query):
        results = []
        for id, text in self.__id_to_texts.items():
            if query in text:
                results.append(id)
        return results

search_engine = SimpleEngine()
main(search_engine)


########## 输出 ##########


simple
found 0 result(s):
little
found 2 result(s):
1.txt
2.txt

你可能很惊讶,只需要短短十来行代码居然就可以了吗?

没错,正是如此,这段代码我们拆开来看一下:

SimpleEngine 实现了一个继承 SearchEngineBase 的子类,继承并实现了 process_corpus 和 search 接口,同时,也顺手继承了 add_corpus 函数(当然你想重写也是可行的),因此我们可以在 main() 函数中直接调取。

在我们新的构造函数中,self.__id_to_texts = {} 初始化了自己的私有变量,也就是这个用来存储文件名到文件内容的字典。

process_corpus() 函数则非常直白地将文件内容插入到字典中。这里注意,ID 需要是唯一的,不然相同 ID 的新内容会覆盖掉旧的内容。

search 直接枚举字典,从中找到要搜索的字符串。如果能够找到,则将 ID 放到结果列表中,最后返回。

你看,是不是非常简单呢?这个过程始终贯穿着面向对象的思想,这里我为你梳理成了几个问题,你可以自己思考一下,当成是一个小复习。

  • 现在你对父类子类的构造函数调用顺序和方法应该更清楚了吧?
  • 继承的时候,函数是如何重写的?
  • 基类是如何充当接口作用的(你可以自行删掉子类中的重写函数,抑或是修改一下函数的参数,看一下会报什么错)?
  • 方法和变量之间又如何衔接起来的呢?

好的,我们重新回到搜索引擎这个话题。

欢迎关注我公众号:AI悦创,有更多更好玩的等你发现!

公众号:AI悦创【二维码】

AI悦创·编程一对一

AI悦创·推出辅导班啦,包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发」,全部都是一对一教学:一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。当然,还有线下线上摄影课程、Photoshop、Premiere 一对一教学、QQ、微信在线,随时响应!微信:Jiabcdefh

C++ 信息奥赛题解,长期更新!长期招收一对一中小学信息奥赛集训,莆田、厦门地区有机会线下上门,其他地区线上。微信:Jiabcdefh

方法一:QQopen in new window

方法二:微信:Jiabcdefh

上次编辑于:
贡献者: AndersonHJB

你认为这篇文章怎么样?

  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
评论
  • 按正序
  • 按倒序
  • 按热度