サイト運営者ための無料資料館―Free9Home

Googleの大規模な分散処理技術の中で、大きな役割を果たしている
のが、MapReduceというアルゴリズムです。このアルゴリズムは、
Jeffrey Dean とSanjay Ghemawatによって「発見」されたものです。
http://209.85.163.132/papers/mapreduce-osdi04.pdf

ここでは、「あるテキストの中で、出現するwordの数を数える」という、
いわゆるWord Countの例で、このアルゴリズムを説明したいと思います。

話を簡単にするために、ここでのテキストは、次のものとしましょう。

　　TEXT = "TO BE OR NOT TO BE"

もちろん答えは、この例でしたら「人間computing」をすれば、
すぐ分かるのですが

　　TO:2, BE:2, OR:1, NOT:1

ということになります。

MapReduceは、次の三つのステップで、この結果を導きます。

第一段階　Map

Word Countの例でしたら、Mapは、テキスト中のwordを一つ見つけるたびに、
そのwordに"1"という値を割り当てます。

　　  | TO ｜ BE | OR | NOT | TO | BE |
Map  +-----+----+----+-----+----+----+
     |  1  | 1  | 1  |  1  | 1  |  1 |

keyとvalueのペアを、key;valueであらわせば、このMapの処理は、
"TO BE OR NOT TO BE"というテキストから、次のようなkey:valueの
集まりを作り出すことです。

Map:　"TO BE OR NOT TO BE"  --->  [ TO:1, BE:1, OR:1, NOT:1, TO:1, BE:1 ]

第二段階　Sort

Mapの出力をkeyでSortして、同じkeyを持つもの同士が
隣り合うグループを作るようにします。

　   | TO ｜ BE | OR | NOT | TO | BE |　   　| BE ｜ BE | NOT | OR | TO | TO |
Sort +-----+----+----+-----+----+----+　-->　+-----+----+-----+----+----+----+
    |  1  | 1  | 1  |  1  | 1  |  1 | 　    |  1  | 1  |  1  |  1 | 1  |  1 |

Sort:  [ TO:1, BE:1, OR:1, NOT:1, TO:1, BE:1 ]
          ---->  [ BE:1, BE:1, NOT:1, OR:1, TO:1, TO:1 ]

ですね。
この処理は、人間computingで、同じwordを探す処理に対応しています。

第三段階　Reduce

同じkeyを持つものを束ねます。このとき、valueにある操作が必要です。
Word Countの場合には、同じkeyのvalueは、足し合わせるだけです。

　   　| BE ｜ BE | NOT | OR | TO | TO |　　 　| BE       | NOT | OR | TO      |
Reduce +-----+----+--- -+----+----+----+　-->　+-----+----+-----+----+----+----+
      |  1  | 1  |  1  |  1 | 1  |  1 |　　 　|  1  | 1  |  1  |  1 | 1  |  1 |

     | BE      | NOT | OR | TO      |　　 　| BE  | NOT | OR | TO |
-->　+---------+-----+----+---------+　-->　+-----+-----+----+----+
     |  1  + 1 |  1  |  1 | 1  +  1 |　　 　|  2  | 1   |  1 |  2 |

結局、
Reduce: [ BE:1, BE:1, NOT:1, OR:1, TO:1, TO:1 ]
　　　　　---->  [ BE:2, NOT:1, OR:1, TO:2 ]

もちろん、この結果は、人間computingの
　　TO:2, BE:2, OR:1, NOT:1
に一致しています。これだけです。

ここでは、MapReduceが、実際には、Map+Sort+Reduceという
三段階の処理だということに、注目してください

0 Comment

在浩如烟海的Internet上，特别是其上的Web（World Wide Web万维网）上，不会搜索，就不会上网。网虫朋友们，你了解搜索引擎吗？它们是怎么工作的？你都使用哪些搜索引擎？今天我就和大家聊聊搜索引擎的话题。

一、搜索引擎的分类

获得网站网页资料，能够建立数据库并提供查询的系统，我们都可以把它叫做搜索引擎。按照工作原理的不同，可以把它们分为两个基本类别：全文搜索引擎（FullText Search Engine）和分类目录Directory）。

全文搜索引擎的数据库是依靠一个叫“网络机器人（Spider）”或叫“网络蜘蛛（crawlers）”的软件，通过网络上的各种链接自动获取大量网页信息内容，并按以定的规则分析整理形成的。Google、百度都是比较典型的全文搜索引擎系统。

分类目录则是通过人工的方式收集整理网站资料形成数据库的，比如雅虎中国以及国内的搜狐、新浪、网易分类目录。另外，在网上的一些导航站点，也可以归属为原始的分类目录，比如“网址之家”（http://www.hao123.com/）。

全文搜索引擎和分类目录在使用上各有长短。全文搜索引擎因为依靠软件进行，所以数据库的容量非常庞大，但是，它的查询结果往往不够准确；分类目录 依靠人工收集和整理网站，能够提供更为准确的查询结果，但收集的内容却非常有限。为了取长补短，现在的很多搜索引擎，都同时提供这两类查询，一般对全文搜 索引擎的查询称为搜索“所有网站”或“全部网站”，比如Google的全文搜索（http://www.google.com/intl/zh-CN/）；把对分类目录的查询称为搜索“分类目录”或搜索“分类网站”，比如新浪搜索（http://dir.sina.com.cn/）和雅虎中国搜索（http://cn.search.yahoo.com/dirsrch/）。

在网上，对这两类搜索引擎进行整合，还产生了其它的搜索服务，在这里，我们权且也把它们称作阉饕妫饕姓饬嚼啵?

⒈元搜索引擎(META Search Engine)。这类搜索引擎一般都没有自己网络机器人及数据库，它们的搜索结果是通过调用、控制和优化其它多个独立搜索引擎的搜索结果并以统一的格式在 同一界面集中显示。元搜索引擎虽没有“网络机器人”或“网络蜘蛛”，也无独立的索引数据库，但在检索请求提交、检索接口代理和检索结果显示等方面，均有自 己研发的特色元搜索技术。比如“metaFisher元搜索引擎”（http://www.hsfz.net/fish/），它就调用和整合了Google、Yahoo、AlltheWeb、百度和OpenFind等多家搜索引擎的数据。

⒉集成搜索引擎（All－in－One Search Page）。集成搜索引擎是通过网络技术，在一个网页上链接很多个独立搜索引擎，查询时，点选或指定搜索引擎，一次输入，多个搜索引擎同时查询，搜索结果由各搜索引擎分别以不同页面显示，比如“网际瑞士军刀”（http://free.okey.net/%7Efree/search1.htm）。

二、搜索引擎的工作原理

全文搜索引擎的“网络机器人”或“网络蜘蛛”是一种网络上的软件，它遍历Web空间，能够扫描一定IP地址范围内的网站，并沿着网络上的链接从一 个网页到另一个网页，从一个网站到另一个网站采集网页资料。它为保证采集的资料最新，还会回访已抓取过的网页。网络机器人或网络蜘蛛采集的网页，还要有其 它程序进行分析，根据一定的相关度算法进行大量的计算建立网页索引，才能添加到索引数据库中。我们平时看到的全文搜索引擎，实际上只是一个搜索引擎系统的 检索界面，当你输入关键词进行查询时，搜索引擎会从庞大的数据库中找到符合该关键词的所有相关网页的索引，并按一定的排名规则呈现给我们。不同的搜索引 擎，网页索引数据库不同，排名规则也不尽相同，所以，当我们以同一关键词用不同的搜索引擎查询时，搜索结果也就不尽相同。

和全文搜索引擎一样，分类目录的整个工作过程也同样分为收集信息、分析信息和查询信息三部分，只不过分类目录的收集、分析信息两部分主要依靠人工 完成。分类目录一般都有专门的编辑人员，负责收集网站的信息。随着收录站点的增多，现在一般都是由站点管理者递交自己的网站信息给分类目录，然后由分类目 录的编辑人员审核递交的网站，以决定是否收录该站点。如果该站点审核通过，分类目录的编辑人员还需要分析该站点的内容，并将该站点放在相应的类别和目录 中。所有这些收录的站点同样被存放在一个“索引数据库”中。用户在查询信息时，可以选择按照关键词搜索，也可按分类目录逐层查找。如以关键词搜索，返回的 结果跟全文搜索引擎一样，也是根据信息关联程度排列网站。需要注意的是，分类目录的关键词查询只能在网站的名称、网址、简介等内容中进行，它的查询结果也 只是被收录网站首页的URL地址，而不是具体的页面。分类目录就像一个电话号码薄一样，按照各个网站的性质，把其网址分门别类排在一起，大类下面套着小 类，一直到各个网站的详细地址，一般还会提供各个网站的内容简介，用户不使用关键词也可进行查询，只要找到相关目录，就完全可以找到相关的网站（注意：是 相关的网站，而不是这个网站上某个网页的内容，某一目录中网站的排名一般是按照标题字母的先后顺序或者收录的时间顺序决定的）。

一个好的搜索引擎，不仅数据库容量要大，更新频率、检索速度要快，支持对多语言的搜索，而且随着数据库容量的不断膨胀，还要能从庞大的资料库中精确地找到正确的资料。

⒈提高搜索引擎对用户检索提问的理解。为了提高搜索引擎对用户检索提问的理解，就必须有一个好的检索提问语言。为了克服关键词检索和目录查询的缺 点，现在已经出现了自然语言智能答询。用户可以输入简单的疑问句，比如“如何能杀死计算机中的病毒”，搜索引擎在对提问进行结构和内容的分析之后，或直接 给出提问的答案，或引导用户从几个可选择的问题中进行再选择。自然语言的优势在于，一是使网络交流更加人性化，二是使查询变得更加方便、直接、有效。就以 上面的例子来讲，如果用关键词查询，多半人会用“病毒”这个词来检索，结果中必然会包括各类病毒的介绍，病毒是怎样产生的等等许多无用信息，而用“如何能 杀死计算机中的病毒”检索，搜索引擎会将怎样杀死病毒的信息提供给用户，提高了检索效率。

⒉垂直主题搜索引擎有着极大的发展空间。网上的信息浩如烟海，网络资源以惊人的速度增长，一个搜索引擎很难收集全所有主题的网络信息，即使信息主 题收集得比较全面，由于主题范围太宽，很难将各主题都做得精确而又专业，使得检索结果垃圾太多。这样以来，垂直主题的搜索引擎以其高度的目标化和专业化在 各类搜索引擎中占据了一席之地。目前，一些主要的搜索引擎，都提供了新闻、Mp3、图片、Flash等的搜索，加强了检索的针对性。

⒊元搜索引擎，能够提供全面且较为准确的查询结果。现在的许多搜索引擎，其收集信息的范围、索引方法、排名规则等都各不相同，每个搜索引擎平均只 能涉及到整个Web资源的30－50%，这样导致同一个搜索请求在不同搜索引擎中获得的查询结果的重复率不足34%，而每一个搜索引擎的查准率不到 45%。元搜索引擎(META Search Engine)是将用户提交的检索请求发送到多个独立的搜索引擎上去搜索，并将检索结果集中统一处理，以统一的格式提供给用户，因此有搜索引擎之上的搜索 引擎之称。它的主要精力放在提高搜索速度、智能化处理搜索结果、个性化搜索功能的设置和用户检索界面的友好性上，查全率和查准率都比较高。

四、主要的搜索引擎介绍

这里介绍的是在国内外影响比较大的主要的一些搜索引擎和分类目录站点，由于现在的站点一般都同时提供全文搜索和分类目录两种服务，所以我们按照其自有的技术进行分类和介绍。

一主要的全文搜索引擎

⒈Google（http://www.google.com/）。Google成立于1997年，几年间迅速发展成为世界范围内规模最大的搜索引擎。Google数据库现存有42.8亿个Web文件，每天处理的搜索请求已达2亿次，而且这一数字还在不断增长。Google借用Dmoz（http://dmoz.org/）的分类目录提供“网页目录”查询（http://www.google.com/dirhp?hl=zh-CN&tab=wd&ie=UTF-8&oe=UTF-8&q=），但默认网站排列顺序并非按照字母顺序，而是根据网站PageRank的分值高低排列。

⒉百度（http://www.baidu.com/）。 百度是国内最早的商业化（早期为其它门户网站提供搜索服务，现在的竞价排名更是日进斗金）全文搜索引擎，拥有自己的网络机器人和索引数据库，专注于中文的 搜索引擎市场，除有网页搜索外，百度还有新闻、MP3、图片等搜索，并在2003年底推出“贴吧”、按地域搜索等功能。

⒊中国搜索（http://www.huicong.com/）。 中国搜索的前身是慧聪搜索，原慧聪搜索在联合中国网等30多家知名网站的基础上，2002年9月25日，正式组建了中国搜索联盟，经过一年多的发展，联盟 成员就已达630多家，成为中国互联网一支重要的力量。由于发展迅速，慧聪集团借上市之机，将慧聪搜索更名为中国搜索，全力发展其在搜索引擎方面的业务， 以打造中文搜索领域的全新品牌。

二主要分类目录

⒈雅虎中国分类目录（http://cn.yahoo.com/）。雅虎中国的分类目录是最早的分类目录，现有14个主类目，包括“商业与经济”、“艺术与人文”等，可以逐层进入进行检索，也可以利用关键词对“分类网站”进行搜索（http://m6.search.cnb.yahoo.com/dirsrch/）。此外，雅虎中国也可以对“所有网站”进行关键词搜索（http://cn.search.yahoo.com/websrch/），早期，他的搜索结果使用Google的数据，2004年2月正式推出自己的全文搜索引擎，并结束了与Google的合作。

⒉新浪分类目录（http://dir.sina.com.cn/）。 新浪的分类目录目前共有18个大类目，用户可按目录逐级向下浏览，直到找到所需网站。就好像用户到图书馆找书一样，按照类别大小，层层查找，最终找到需要 的网站或内容。通过和其它全文搜索引擎的合作，现在，也可以使用关键词对新浪的“分类网站”或“全部网站”进行搜索。

⒊搜狐分类目录（http://dir.sohu.com/）。搜狐分类目录把网站作为收录对象，具体的方法就是将每个网站首页的URL地址提供给搜索用户，并且将网站的题名和整个网站的内容简单描述一下，但是并不揭示网站中每个网页的信息内容。除此之外，也可以使用关键词对搜狐的“分类目录”或所有网站进行搜索。

⒋网易分类目录（http://search.163.com/）。 网易的分类目录采用“开放式目录”管理方式，在功能齐全的分布式编辑和管理系统的支持下，现有5000多位各界专业人士参与可浏览分类目录的编辑工作，极 大地适应了互联网信息爆炸式增长的趋势。在加强与其它搜索引擎合作的基础上，新版搜索引擎支持使用关键词对所有网站进行检索。

实际上，搜索引擎的众多技术都是高度保密的，以是仅仅是笔者的一些愚见，不足之处，还请众大虾批评指正。



你向百度、Google、Yahoo提交网址是不用花钱的，其提交页面分别为：
http://www.baidu.com/search/url_submit.html
http://www.google.com/intl/zh-CN/add_url.html
http://www.yisou.com/search_submit.html?source=yisou_www_hp

0 Comment

"蜘蛛"（Spider）是Internet上一种很有用的程序，搜索引擎利用蜘蛛程序将Web页面收集到数据库，企业利 用蜘蛛程序监视竞争对手的网站并跟踪变动，个人用户用蜘蛛程序下载Web页面以便脱机使用，开发者利用蜘蛛程序扫描自己的Web检查无效的链接……对于不 同的用户，蜘蛛程序有不同的用途。那么，蜘蛛程序到底是怎样工作的呢？

　　蜘蛛是一种半自动的程序，就象现实当中的蜘蛛在它的Web （蜘蛛网）上旅行一样，蜘蛛程序也按照类似的方式在Web链接织成的网上旅行。蜘蛛程序之所以是半自动的，是因为它总是需要一个初始链接（出发点），但此 后的运行情况就要由它自己决定了，蜘蛛程序会扫描起始页面包含的链接，然后访问这些链接指向的页面，再分析和追踪那些页面包含的链接。从理论上看，最终蜘 蛛程序会访问到
Internet上的每一个页面，因为Internet上几乎每一个页面总是被其他或多或少的页面引用。

　　本文介绍如何用C#语言构造一个蜘蛛程序，它能够把整个网站的内容下载到某个指定的目录，程序的运行界面如图一。你可以方便地利用本文提供的几个核心类构造出自己的蜘蛛程序。
　　C#特别适合于构造蜘蛛程序，这是因为它已经内置了HTTP访问和多线程的能力，而这两种能力对于蜘蛛程序来说都是非常关键的。下面是构造一个蜘蛛程序要解决的关键问题：

　　⑴ HTML分析：需要某种HTML解析器来分析蜘蛛程序遇到的每一个页面。

　　⑵ 页面处理：需要处理每一个下载得到的页面。下载得到的内容可能要保存到磁盘，或者进一步分析处理。

　　⑶ 多线程：只有拥有多线程能力，蜘蛛程序才能真正做到高效。

　　⑷ 确定何时完成：不要小看这个问题，确定任务是否已经完成并不简单，尤其是在多线程环境下。

　　一、HTML解析

　 　C#语言本身不包含解析HTML的能力，但支持XML解析；不过，XML有着严格的语法，为XML设计的解析器对HTML来说根本没用，因为HTML的 语法要宽松得多。为此，我们需要自己设计一个HTML解析器。本文提供的解析器是高度独立的，你可以方便地将它用于其它用C#处理HTML的场合。

　　本文提供的HTML解析器由ParseHTML类实现，使用非常方便：首先创建该类的一个实例，然后将它的Source属性设置为要解析的HTML文档：

ParseHTML parse = new ParseHTML();
parse.Source = "
Hello World
";

while(!parse.Eof())
{
char ch = parse.Parse();

if(ch==0)
{
HTMLTag tag = parse.GetTag();
}

Attribute href = tag["HREF"];
string link = href.Value;

HttpWebRequest request = (HttpWebRequest)WebRequest.Create(m_uri);
response = request.GetResponse();
stream = response.GetResponseStream();

if( !response.ContentType.ToLower().StartsWith("text/") )
{
SaveBinaryFile(response);
return null;
}
string buffer = "",line;

reader = new StreamReader(stream);
while( (line = reader.ReadLine())!=null )
{
buffer+=line+"\r\n";
}

SaveTextFile(buffer);

byte []buffer = new byte[1024];

string filename = convertFilename( response.ResponseUri );

Stream outStream = File.Create( filename );
Stream inStream = response.GetResponseStream();

int l;
do
{
l = inStream.Read(buffer,0,
buffer.Length);
if(l>0)
outStream.Write(buffer,0,l);
} while(l>0);

outStream.Close();
inStream.Close();

string filename = convertFilename( m_uri );
StreamWriter outStream = new StreamWriter( filename );
outStream.Write(buffer);
outStream.Close();

while(!m_spider.Quit )
{
m_uri = m_spider.ObtainWork();

m_spider.SpiderDone.WorkerBegin();
string page = GetPage();
if(page!=null)
ProcessPage(page);
m_spider.SpiderDone.WorkerEnd();
}

public void WaitDone()
{
Monitor.Enter(this);
while ( m_activeThreads>0 )
{
Monitor.Wait(this);
}
Monitor.Exit(this);
}

public void WaitBegin()
{
Monitor.Enter(this);
while ( !m_started )
{
Monitor.Wait(this);
}
Monitor.Exit(this);
}

public void WorkerBegin()
{
Monitor.Enter(this);
m_activeThreads++;
m_started = true;
Monitor.Pulse(this);
Monitor.Exit(this);
}

public void WorkerEnd()
{
Monitor.Enter(this);
m_activeThreads--;
Monitor.Pulse(this);
Monitor.Exit(this);
}

　　WorkerEnd方法减小m_activeThreads活动线程计数器，调用Pulse释放可能在等待Done对象的线程--如前所述，可能在等待Done对象的方法是WaitDone方法。

0 Comment

国外开发的相关程序
1、Nutch

官方网站 http://www.nutch.org/
中文站点 http://www.nutchchina.com/
最新版本：Nutch 0.7.2 Released
Nutch 是一个开源Java 实现的搜索引擎。它提供了我们运行自己的搜索引擎所需的全部工具，可以建立自己内部网的搜索引擎，也可以针对整个网络建立搜索引擎。自由(Free)而免费(Free)。
2、Lucene

官方网站 http://lucene.apache.org
中文站点 http://www.lucene.com.cn/
Lucene是apache软件基金会 jakarta项目组的一个子项目，是一个开放源代码的全文检索引擎工具包[用Java写的]，即它不是一个完整的全文检索引擎，而是一个全文检索引擎的 架构，提供了完整的查询引擎和索引引擎，部分文本分析引擎（英文与德文两种西方语言）。Lucene的目的是为软件开发人员提供一个简单易用的工具包，以 方便的在目标系统中实现全文检索的功能，或者是以此为基础建立起完整的全文检索引擎。
3、Larbin: http://larbin.sourceforge.net/index-eng.html
larbin是一种开源的网络爬虫/网络蜘蛛，由法国的年轻人 Sébastien Ailleret独立开发。larbin目的是能够跟踪页面的url进行扩展的抓取，最后为搜索引擎提供广泛的数据来源。
国内开发的相关程序
1、SQLET - 开放源码的中文搜索引擎
官方网站 http://www.sqlet.com/
SQLET，是Search & Query &Link, 加后缀 let，表示小的，小型的意思.打算建立一个能搜上亿张网页的基于主题功能的中文搜索引擎.支持3种索引方式：MySql_table_Index， Lucene_Index，SQLET_Index.网页抓取可以保存在文件系统及数据库里。自带WebServer.
2、菲度垂直搜索引擎代码
菲度http://www.faydu.net 为一个垂直在线搜索的演示版，主要对国内一些购物站点进行搜索整理，
语言：VB.net(c#)
二、中文分词程序代码
1、计算所汉语词法分析系统 ICTCLAS
中国科 学院计算技术研究所在多年研究基础上，耗时一年研制出了基于多层隐马模型的汉语词法分析系统 ICTCLAS(Institute of Computing Technology, Chinese Lexical Analysis System)，该系统的功能有：中文分词；词性标注；未登录词识别。分词正确率高达97.58%(最近的973专家组评测结果)，基于角色标注的未登录 词识别能取得高于90%召回率，其中中国人名的识别召回率接近98%，分词和词性标注处理速度为31.5KB/s。ICTCLAS 和计算所其他14项免费发布的成果被中外媒体广泛地报道，国内很多免费的中文分词模块都或多或少的参考过ICTCLAS的代码。
下载页面：http://www.nlp.org.cn/project/project.php?proj_id=6
由于 ICTCLAS 是由 C 语言写成的，现在主流的开发工具用起来不太方便，于是有一些热心的程序员把 ICTCLAS 改为 Java 和 C# 等其他语言。
（1）fenci，Java 的 ICTCLAS，下载页面：http://www.xml.org.cn/printpage.asp?BoardID=2&id=11502
（2）AutoSplit，另一个 Java 的 ICTCLAS，已经找不到下载页面，点击本地下载
（3）小叮咚中文分词，曾经有下载页面，现在找不到了。据作者介绍，从 ICTCLAS 中改进，有 Java，C# 和 C++ 三个版本，介绍页面：http://www.donews.net/accesine
2、海量智能分词研究版
海量智能计算技术研究中心为了使中文信息处理领域的研究者们能够共同分享海量智能中心的研究成果，共同提高中文信息处理水平，特此发布《海量智能分词研究版》，供专家、学者和爱好者进行研究。
下载页面：http://www.hylanda.com/cgi-bin/download/download.asp?id=8

3、其他
（1）CSW中文智能分词组件
运行环境：Windows NT、2000、XP 或更高，可以在 ASP，VB 等微软的开发语言中调用。
简介: CSW中文智能分词DLL组件，可将一段文本自动的按常规汉语词组进行拆分,并以指定方式进行分隔，且可对其拆分后的词组进行语义、词频标注。其广范应用于各行各业的信息资料检索、分析。
下载页面：http://www.vgoogle.net/
（2） C# 写的中文分词组件
据作者介绍，一个 DLL 文件，可以做中英文分词组件。完全C#托管代码编写，独立开发。
下载页面：http://www.rainsts.net/article.asp?id=48

0 Comment