[小学教育]数学之美系列

《[小学教育]数学之美系列》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数学Z美一统计语言模型数V之羌一.谈谈屮文分词数学之羌三隐含马尔可夫模型在语言处理中的应用数学Z美四怎样度量信息？数学之美五简单之美：布尔代数和搜索引擎的索引数VZ美六图论和网络爬虫(Webcrawlers)数学Z美七信息论在信息处理屮的应用数学之美八贾里尼克的故爭和现代语言处理数7之美九如何确定网页和查询的相关性数学之美I-有限状态机和地址识别数学Z美I•一Google阿卡47的制造者阿米特.辛格博上数学Z美十二余弦定理和新闻的分类数学Z美十厂信息指纹及其应川数7之美十四谈谈数7模型的重耍性数学之美I•五繁与简口然

2、语言处理的儿位粹英数学Z美I•六不要把所冇的鸡蛋放在一个篮了小最人爛模型数学之美卜七闪光的不定是金了谈谈:!索引擎作弊问题(SearchEngineAnti-SPAM)数学之天十八炬阵运;:和文本处理中的分类问题数7之美十九气尔丨

3、「夫链的扩•展贝叶斯网络(BayesianNetworks)数学之美二I-

4、'

5、然语言处理的教父马库斯数学Z美-I~~•布隆过滤器(BloomFilter)数学Z美••+•••由电视剧《暗算》所想到的—谈谈密码学的数学原理数学之羌二十三输入•个汉7需要敲多少个键一谈谈香农第•定

6、律数学之美一十从全球导航到输入法谈谈动态规划论和网络爬虫(WebCrawlers)［离散数学是当代数学的一个重要分支,也是计算机科学的数学基础。它包括数理逻辑、集合论、图论和近世代数四个分支。数理逻辑基于布尔运算。这里我们介绍图论和互联网H动下载丁•具网络爬虫(WebCrawlers)之间的关系。顺便提一句，我们用google来搜索一下"离散数学”这个词，可以发现不少有趣的现彖。比如，武汉、哈尔滨、合肥和长沙市对这一数学题冃最有兴趣的城市。］图论的起源可追溯到大数学家歐拉(LeonhardEuler)o1736年欧拉

7、来到德国的诽尼斯堡(Konigsberg,大哲学家康徳的故乡，现在是俄罗斯的加里宁格勒)，发现当地市民们有一项消逍活动，就是试图将下图中的每座桥恰好走过-•遍并回到原岀发点，从來没有人成功过。欧拉证明了这件事是不可能的，并写了一篇论文，一般认为这是图论的开始。图论屮所讨论的的图由一些节点和连接这些节点的弧纟R成。如果我们把中国的城市当成节点，连接城市的国道当成弧，那么全国的公路T线网就是图论小所说的图。关于图的算法有很多，但最重要的是图的遍历算法，也就是如何通过弧访问图的各个节点。以中国公路网为例，我们从北京出发，看

8、一看北京和哪些城市直接相连，比如说和天津、济南、石家庄、南京、沈阳、大同直接相连。我们可以依次访问这些城市，然后我们看看都有哪些城市和这些已经访问过的城市相连，比如说北戴河、秦皇岛与天津相连，青岛、烟台和济南相连，太原、郑州和石家庄相连等等，我们再一-次访问北戴河这些城市,直到小国所有的城市都访问过一遍为止。这种图的遍历算法称为因为它先要尽可能广地访问每个节点所直接连接的其他节点。另外还冇一种策略是从北京出发，随便找到下一个要访问的城市，比如是济南，然后从济南出发到下一个城市，比如说南京，再访问从南京出发的城市，一总

9、走到头。然后再往回找，看看中间是否有尚未访问的城市。这种方法叫,■因为它是-条路走到黑。这两种方法都可以保证访问到全部的城市。当然，不论采用哪种方法，我们都应该用一个小木本，记录已经访问过的城市，以防同一个城市访问多次或者漏掉哪个城市。现在我们看看图论的遍历算法和搜索引擎的关系。互联网其实就是一张人图，我们可以把每一个网页当作一个节点，把那些超链接(Hyperlinks)当作连接网页的弧。很多读者可能已经注意到，网页屮那些蓝色的、带有下划线的文字背后其实藏着对应的网址，当你点下去的的时候，浏览器是通过这些隐含的网址转

10、到相应的网页中的。这些隐含在文字背后的网址称为“超链接雹有了超链接，我们对以从任何一个网页出发，用图的遍历算法，口动地访问到每一个网页并把它们存起来。完成这个功能的程序叫做网络爬虫，或者在一些文献屮称为“机器人”(Robot)。世界上第一个网络爬虫是由麻省理工学院(MIT)的学生马休.格雷(MatthewGray)在1993年写成的。他给他的程序起了个名字叫“互联网漫游者"C'wwwwanderer")o以后的网络爬虫越写越复杂，但原理是一样的。我们來看看网络爬虫如何F载整个互联网。假定我们从一家门户网站的首页出发，

11、先下载这个网页，然示通过分析这个网页，可以找到藏在它里面的所有超链接，也就等于知道了这家门户网站首页所直接连接的全部网页，诸如雅虎邮件、雅虎财经、雅虎新闻等等。我们接下来访问、下载并分析这家门户网站的邮件等网页，又能找到其他相连的网页。我们止计算机不停地做下去，就能下载整个的互联网。当然，我们也要记载哪个网页下载过了，以免重复。在网络爬虫中，我