NLP笔记(2) -- 基于搜索的模型

写在前面

  • 最近在学习NLP的课程,下面的代码,基本来自我的NLP课程作业,当然大部分都是模仿老师写的,使用Python完成,感兴趣的可以去我的github上面查看:https://github.com/LiuPineapple/Learning-NLP/tree/master/Assignments/lesson-02
  • 作者水平有限,如果有文章中有错误的地方,欢迎指正!如有侵权,请联系作者删除。

Search Based Model(基于搜索的模型)

广度优先搜索(BFS)与深度优先搜索(DFS)

  广度优先搜索(Breadth First Search)与深度优先搜索(Depth First Search)是两种常用的搜索方法。两者之间的区别和算法网上有很多详细介绍,这里不再详述。

北京地铁路线搜索

  使用爬虫,我们可以得到北京地铁的各个站点连接情况,由于作者现在还不能熟练使用爬虫,所以使用了班里同学的爬虫代码——欧同学的代码链接 在此表示感谢,这里不再展示,只展示爬虫的结果的一部分。我们可以看到,结果是一个字典,key是北京地铁所有的站点,value 是一个列表,列表中的元素是与key所代表的站点有一站距离的站点,也就是可以从key所代表的站点直接通往list中的站点。

图片1

  接下来我们创建search()函数,希望输入起点和终点,就能输出乘坐地铁的路线。

from collections import defaultdict
station_net = defaultdict(list)
station_net.update(station_connection)
def search(start,destination,graph):
    routes = [[start]]
    seen = set()
    while routes:
        route = routes.pop(0)
        frontier = route[-1]
        if frontier in seen: continue
        for station in graph[frontier]:
            if station in seen: continue
            new_route= route + [station]
            routes.append(new_route)
            if station == destination: return new_route
        seen.add(frontier)

上段代码中需要注意的地方有:

  1. Python defaultdict 的使用。https://www.jianshu.com/p/bbd258f99fd3
  2. Python3 set(集合)的使用。 https://www.runoob.com/python3/python3-set.html
  3. Python List pop()方法。https://www.runoob.com/python/att-list-pop.html
  4. Python 字典(Dictionary) update()方法。https://www.runoob.com/python/att-dictionary-update.html
  5. 这里使用了广度优先搜索(BFS),如果要使用深度优先搜索(DFS)的话有两种方法,(1)route = routes.pop(0)换成route = routes.pop(0) (2)new_route= route + [station]换成 new_route= [station] + route,结果也可能会有所不同。

search()函数最后输出一个列表,里面的元素按顺序包括起点、终点以及其中所有的经过站。为了让结果更加美观,我们把列表合成一个字符串,站点之间用->连接。

def pretty_print(route):
    return '->'.join(route)
pretty_print(search('天安门西','奥体中心',station_net))
'天安门西->西单->复兴门->阜成门->车公庄->西直门->积水潭->鼓楼大街->安德里北街->安华桥->北土城->奥体中心'

  注意到,上端代码其实是默认了选取换乘最少的路线,如果我们增加一个选项,给routes排个序,就可能实现其他功能(比如选取换乘最少的路线,选取距离最短的路线等),这时候的搜索,既不是BFS也不是DFS。如下所示选取换乘最少的路线,其实跟上一个代码得到的结果相同。

def search(start,destination,graph,sort_candidate):
    routes = [[start]]
    seen = set()
    while routes:
        route = routes.pop(0)
        frontier = route[-1]
        if frontier in seen: continue
        for station in graph[frontier]:
            if station in seen: continue
            new_route= route + [station]
            routes.append(new_route)
            if station == destination: return new_route
        routes = sort_candidate(routes)
        seen.add(frontier)

def transfer_stations_first(pathes): 
    return sorted(pathes, key=len)

pretty_print(search('西单','南锣鼓巷',station_net,transfer_stations_first))
'西单->灵境胡同->西四->平安里->北海北->南锣鼓巷'

最后,欢迎大家访问我的GitHub查看更多代码:https://github.com/LiuPineapple
欢迎大家访问我的简书主页查看更多文章:https://www.jianshu.com/u/31e8349bd083

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • # Python 资源大全中文版 我想很多程序员应该记得 GitHub 上有一个 Awesome - XXX 系列...
    小迈克阅读 3,067评论 1 3
  • Python语言特性 1 Python的函数参数传递 看两个如下例子,分析运行结果: 代码一: a = 1 def...
    时光清浅03阅读 516评论 0 0
  • Python语言特性 1 Python的函数参数传递 看两个如下例子,分析运行结果: 代码一: a = 1 def...
    伊森H阅读 3,101评论 0 15
  • 我,一个很平凡的上班族,天天怀揣着世界旅游和吃穿无忧的梦想,然而还得早八晚五单休的工作,每个月的工资基本月...
    沙柳1989阅读 224评论 0 2
  • 我就想问你一句那是不是爱去 ,冲动不多的都不是爱,对吗?你没有牵我的手,我就知道,你喜欢的是暧昧,太孤单,需要人陪...
    迷于情爱阅读 168评论 0 1