尝试围绕搜索引擎来展示编程, 让学生更进一步地理解"所谓编程的规律活动", 并且体验不同层次的变成形式, 激发他们后续学习的欲望.
探讨一下"展示型教学"内容分作如下几部分:
- 引言, 搜索引擎简介
- 之
所以选择搜索引擎作为复杂程序实现的解剖案例, 是因为它的概念并不难理解 (可参照图像处理的复杂度) - 不需要复杂的计算公式,
也不需要反复的架构体系. 这样一来, 就可以专注于如何使用编程技巧来尝试不同层次的实现, 易于学生将精力集中于领会"何为编程".
- 这一部分是作为《计算机和计算:概述》一书的实训来设计的, 实施的思路我倾向如下的方式.
- 讲解不同版本的搜索引擎的机制, 给出对应版本的代码框架
- 围绕如何表达所需要的数据及所需要的操作介绍部分代码的设计与实现
- 之后提供给学生相关的代码, 然后要求他们使用那些代码填充(Fulfill)入代码框架
- 凡是完成代码框架的学生即得到基本分数;若想得到满分,则需要完成...
- 简版搜索引擎的实现 - MemSE
- 在《计算机和计算:概述》中“字符串中提取单词”, “线性链表及其操作”和“结构体数组及其操作”的基础上, 完成简版搜索引擎, 即返回包含所有给定关键字的文档集合
- 对应的数据结构采取"哈希链表"
- 支持排序的搜索引擎的实现 - MemTFIDFSE
- 显
然人们更熟悉的搜索引擎并非只是包含关键字的文档而已, 而是那些更为"相似"的文档集合. 那么如何测度文档的相似性呢?
在搜索引擎中广泛使用的是VSM (Vector Space Model)模型和TF*IDF (Term Frequency - Inverse
Document Frequency)公式.
- 为了支持 TF*IDF 的计算, 自然要修改前面的"哈希链表"以保存必要的信息
- FileSE
- 前面的两个版本基本上能够帮助学生理解搜索引擎的工作机制, 但是, 更为贴近实际的搜索引擎还应该能够支持文件 - 不仅是应该能够从文件中提炼单词完成文档比对, 而且还应该实现将"哈希链表"以文件的形式永久保存-这样才可以实现大规模数据的存储:内存总是会不够的
- 必然涉及文件的读写和更新, 而保存"哈希链表"是帮助学生熟悉这些的不错案例
- 在此基础上, 可引出数据库管理系统的实现思路
- 支持网络功能的搜索引起的实现 - CSCLISE
- 如果只是能够搜索本地的文档, 显然不是真正意义的搜索引擎, 因为提供搜索服务的系统是在另外一台机器上, 那么, 就需要网络编程的技巧.
- 此版本将之前的转换为C/S (Client/Server) 架构, 但是, 客户端是CLI (Command Line Interface) 这一古老风格
- CSGUISE
- 软件开发到现今, GUI (Graphic User Interface) 的操控方式已经成为基本的潮流 - 用户可以通过图标、菜单等来直观地知晓要运行的程序和要进行的操作, 并且通过鼠标来直观地告知程序需要完成的操作指令
- 本部分是将客户端由CLI变成GUI, 进一步让学生体会复杂编程仍然是那些步骤规律 - 只是很多操作换成了现成函数的调用而已
- BSSE
- 大
家都熟悉的搜索引擎, 如Google, Bing, BaiDu 等等, 操作模式都是通过浏览器来访问搜索引擎服务.
此处就是展示如何通过C语言的CGI (Common Gateway Interface) 技术来将搜索引擎服务转换为可提供浏览器访问,
实现动态网页显示灯功能
- 可进一步介绍其他的Web 服务器语言 - ASP, JSP, PHP, Python等
- distributedSE
- 有
了网络功能后的搜索引擎, 其实一定意义上就已经具备了分布式特征, 但是此处的分布式指的是服务器端数据的分布 - 因为文档非常多,
整理出来的特征数据也会非常庞大, 都放在一台机器上不太可行 (Google日索引数据量), 那么, 将庞大的数据分布到多态机器上,
并能够提供统一的访问入口, 也就成为必然的思路
- 这里也就需要将前面的"哈希链表"结构进一步调整
- 可进而介绍云计算(Clouding Computing)的概念, 和现在火热的MapReduce/Hadoop框架
- La V.I.T.A
- "La Vita", 是法语里生活的意思, 倒也是跟当前搜索引擎的广泛使用贴切 - 确实已进入人们的广泛生活
- 这
一部分作为汇总和扩展. 首先介绍 La V.I.T.A的意思 - 即现在搜索引擎进一步会扩展至Video, Image, Text, 和
Audio数据; 然后向学生介绍进一步陈述搜索引擎的通用框架 - 特征提取--> 存储+索引 --> 查询处理;
进而以图像搜索引擎为例讲解工作机制
最后, 有一部很值得看的感人的电影, 名字就是 "La Vita est belle", 算是结语.
https://blog.sciencenet.cn/blog-112715-648502.html
上一篇:
一得集[I]:《计算机和计算: 概述》下一篇:
二得集 [I]:尝试提炼《操作系统》