Skip navigation.

exploreopera

| Help

Sign up | Help

Frogs Under An Umbrella

蛙仔

Posts tagged with "学习"

如何在windows环境下实现socket编程

,

这是一篇简单的指南性质的文章,主要阐述如何在windows环境下利用socket套接字(有的人把它叫做插座,whatever^_^)来实现TCP/IP级的网络编程。这篇文章主要是讨论高级的socket,如果读者需要自己修改或者封装TCP/IP的数据内容,则这篇文章不适合,请参考相关书籍。本文以C作为计算机语言,没有此类基础的读者可以先找一本关于C的书来看看。windows套接字基本演变自berkley的socket,所以本文内容基本也适用于unix。socket编程从某种角度看是属于程式化的东西,所以本文尽量从编程的角度与顺序来介绍这种编程技术。另外本文的api函数均不作详细介绍,如果需要api的详细解释,可以参考microsoft技术网站msdn的相关内容。最后还要指出本文中列举所有的程序均在Lcc-Win32开发环境下编译且调试成功。

1. Let's be ready to start using sockets(only connern this when you are in MS windows circumstance)
在启动socket前,windows有一个与众不同的步骤(这步怪异的步骤常常为unix的粉丝所不齿),就是要先初始化socket,这一步的主要目的是加载与socket代理有关的dll版本文件(一般我们使用2.0的版本),所以如果你使用unix或者linux或者其它非microsoft的产品,可以省略这一步。
WSAStartup();
就是这个怪异的函数。与此函数相对的是:
WSACleanup();
函数。这个函数用来清除由于调用WSAStartup()所占据的系统资源。
而WSACleanup()只要在程序不再使用网络链接时调用就可以了,一般在程序中止时调用,但是考虑到windows的鲁棒性,在程序中止时windows会自动清除一切占用资源,这一api有时遗漏也不是很严重,但是不推荐这么做。

2. Now let's establish a socket agent.
socket();
这是用来建立socket代理的api,在unix下这个函数返回一个int型的标示符,但是在windows环境下则返回一个SOCKET结构体(注意必须大写)。

在继续往下讨论时,我们碰到了一个问题,在网络编程时,通信的双方在最简单的情况下也要分为服务器(server)和客户(customer),并且服务器与客户处理的是不同的过程,接下去本文将先从服务器的角度来介绍,然后再介绍客户方的内容。

3. If I'm the server, which port should I listen to.
端口是TCP/IP中一个很重要的概念,它主要用来防止多个网络通信程序彼此相互妨碍,所以不同的网络功能程序一般使用不同的端口。根据行业标准,1024(含)以下的端口都是保留的,用户自己最好不要把自己的应用程序定在这些端口上。
在建立了socket代理后,我们还需要让代理知道,它负责哪个端口的网络通信任务。而赋予代理这个任务的api就是:
bind();
函数。

4. I'm stupid, so tell me what should I do.
在固定了代理所负责的端口后,接着就必须让它开始工作,就像一个售货员一样,代理也必须等到有数据请求才开始工作,所以它必须一直看着自己负责的端口是否有请求到来,负责这一功能的api就是:
listen();
注意,要调用listen()时必须要先调用bind(),否则代理根本就不知道自己要listen哪个端口。就像之前的一系列步骤一样,socket编程是有次序的来调用api,不可随意乱跳。

5. Hey, someone is calling me and I want to give a reply.
在通过listen()发现有客户方请求数据时,如果想对其作出接收请求的应答,那么就调用:
accept();
什么,你问我如果不想理睬这个请求怎么办?Oh, easy. You just ignore it.
如果接收了请求,那么accept()将会返回一个全新的SOCKET型的标示,也就是说服务器通过这个新产生的标示符与客户进行通信,也就是通过这个标示符来实现与客户的收发数据。在编程时,一般有两种方法处理这时出现的问题。一是停止程序监听端口,使用另一个标识符与客户开始进行通信,等此服务结束后在重新来监听端口。二是可以另外打开一个进程来处理这个请求服务。一般人们会使用方法二,因为其高效,但是方法一方便安全。

6. Let my mouth speak or let my ear can hear something.
send();
使用来发送数据。而
recv();
则是接收数据。
根据TCP/IP协议,任何发送数据过程只是尽力发送,并不保证发送数据一定成功或者一定将全部数据发送出去,所以send()只是返回发送数据的个数。send()则是尽力接收,当其返回值是0时,标示对方关闭了连接。

7. I'm the customer. Hey, I wanna something from you.
讲完了服务器方,现在来看看客户的行为。作为客户在取得服务前必须要现告诉服务器你想取得它得服务。
connect();
就能很好得实现这个功能。通过connect()的返回值就能了解连接请求是否得到承认。然后选择下一步的行为。

8. Goodbye, my client.
在socket代理使用结束后需要使用:
closesocket();
将socket代理关闭。

9. Everything should go to its ending(only in windows).
正如在第一点提到的,当不再使用网络通信时,windows还要多一步就是释放其所占的资源,就是使用api:
WSACleanup();

综上所述,我们可以把最基本的服务过程和客户过程分别以如下所示:
********************************************************************************
服务过程:___________________________________客户过程:_____________________
初始化WSACleanup() --> ______________________WSACleanup() -->
建立socket代理socket() --> __________________建立socket代理socket() -->
绑定端口bind() --> __________________________empty
侦听端口listen() --> ________________________empty
接收连接请求accept() --> _____________________发送连接请求connect() -->
发送/接收数据send()/recv() --> _______________接收/发送数据recv()/send() -->
关闭socket代理closesocket() --> _____________关闭socket代理closesocket() -->
中止winsocket,释放资源WSACleanup() __________中止winsocket,释放资源WSACleanup()
*********************************************************************************
以上就是全部的基本socket函数了,但是在实际使用中我们常常还会需要一些辅助函数,比如获得IP地址等,下面就一一介绍。
1. htons():把机器字序转换做网络字序。这一函数与硬件有关,这里只要记住如果你不清楚自己机器的字序方式,就使用这个函数吧。这里指出Intel的处理器芯片一般和网络字序相反,所以一般都必须使用这个函数。

2. inet_addr():将IP地址转换做一串unsigned long型的数。注意这个函数内的参数无需变换字序了,其内置了变换。在windows下:
inet_ntoa();
是一个与其功能一样的函数。

3. gethostbyname():通过DNS服务器获得IP地址。

以上就将基本的常用的函数都介绍完了,下面通过一个向http服务器请求网页的程序来演示一下其基本的应用方法。
为了使程序更通用话,这里设计了通用的函数以方便编程。
/*------------------------------------------------------------------------
Procedure: StartSocket ID:1
Purpose: 打开winsocket的DLL文件,这个是在windows下特有的,在
Unix下就不需要这步了。
Input:
Output: 函数执行成功则返回1。
Errors: 无法调用DLL则返回-1。
------------------------------------------------------------------------*/
int StartSocket(void)
{
WSADATA WSAData;
if(WSAStartup(MAKEWORD(2,2),&WSAData)!=0){
//printf("Socket init fail!\n");
return -1;
}
return 1;
}
/*------------------------------------------------------------------------
Procedure: CreateSocket ID:1
Purpose: 创建socket代理。
Input: socket结构的一个结构体指针。
Output: 1。
Errors: -1。
------------------------------------------------------------------------*/
int CreateSocket(SOCKET *sock)
{
*sock=socket(AF_INET,SOCK_STREAM,0);
if(*sock==INVALID_SOCKET){
//printf("Socket create fail!\n");
return -1;
}
return 1;
}
这里传递指针是因为SOCKET结构sock在以后还要多次用到,考虑到通用性,将其地址作为参数传递。
/*------------------------------------------------------------------------
Procedure: GetIP ID:1
Purpose: 通过URL结构中的Host名获得相对应的IP地址。
Input: 存放URL结构的结构体,socket专用的sockaddr_in结构体指针。
Output: 1。
Errors: -1。
------------------------------------------------------------------------*/
int GetIP(PtrUrlStrData PtrUrlData,SOCKADDR_IN *PtrServerAddr)
{
struct hostent *PtrHost;
PtrHost=gethostbyname(PtrUrlData->Host);
if(PtrHost==NULL){
//puts("Host name wrong.");
return -1;
}
PtrServerAddr->sin_family=AF_INET;
PtrServerAddr->sin_port=htons(PtrUrlData->Port);
PtrServerAddr->sin_addr.s_addr=inet_addr(inet_ntoa(*((struct in_addr *)PtrHost->h_addr)));
memset(&PtrServerAddr->sin_zero[0],0,8);
return 1;
}
UrlStrData这个结构体采用如下定义:
typedef struct _Url_Str_Data { //a structure for URL
char Protocol[8];
char Host[256];
unsigned short Port;
char Path[1024];
char FileName[256];
} UrlStrData, *PtrUrlStrData;
/*------------------------------------------------------------------------
Procedure: CallServer ID:1
Purpose: 联络服务器方。等待服务器方的accept()回应。
Input: socket结构的结构体指针,sockaddr_in型的指针。
Output: 1
Errors: -1
------------------------------------------------------------------------*/
int CallServer(SOCKET *sock,SOCKADDR_IN *PtrServerAddr)
{
if(CreateSocket(sock)==-1){
//puts("Cannot create socket.");
return -1;
}
if(connect(*sock,(struct sockaddr *)PtrServerAddr,sizeof(SOCKADDR_IN))==SOCKET_ERROR){
//printf("Connect fail.\n");
closesocket(*sock);
return -1;
}
return 1;
}
/*------------------------------------------------------------------------
Procedure: TCPSendAll ID:1
Purpose: 发送所有要求被发送的数据。
这里不用send是因为这个函数只是尽力发送数据,所以要改
进一下。
Input: socket结构体指针,需要被发送的数据指针。
Output: 1。
Errors: -1。
------------------------------------------------------------------------*/
int TCPSendAll(SOCKET *sock,char *data)
{
int length=0;
int TotalSended=0;
int LengthAll=strlen(data);
int bytesleft=LengthAll;
while(TotalSended<LengthAll){
length=send(*sock,data+TotalSended,bytesleft,0);
if(length==SOCKET_ERROR){
printf("send data error!\n");
//closesocket(sock);
//WSACleanup();
return -1;
}
TotalSended+=length;
bytesleft-=length;
}
return 1;
}
/*------------------------------------------------------------------------
Procedure: MakeCommand ID:1
Purpose: 制作发送给服务器方的命令。此处是构建http命令。
Input: 指向存放命令的数据指针,存放URL结构的结构体。
Output:
Errors:
------------------------------------------------------------------------*/
void MakeCommand(char *CommandBox,UrlStrData UrlData)
{
char *Ptr1="GET /";
char *Ptr6=" HTTP/1.1\r\nAccept: */*\r\nAccept-Language: zh-cn\r\n";
char *Ptr3="User-Agent: Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1)\r\n";
char *Ptr4="Host: ";
char *Ptr5="Connection: close\r\n\r\n";
sprintf(CommandBox,"%s%s%s%s",Ptr1,UrlData.Path,UrlData.FileName,Ptr6,Ptr3);
int offset=strlen(CommandBox);
char UnShortToStr[18];
sprintf(CommandBox+offset,"%s%s:%s\r\n",Ptr4,UrlData.Host,itoa((int)(short)UrlData.Port,UnShortToStr,10));
offset=strlen(CommandBox);
sprintf(CommandBox+offset,"%s",Ptr5);
return ;
}

O.K.有了上面的函数,编程起来就方便了,程序清单如下:
//**************************************************
#include <winsock.h>
#include <windows.h>
#include <stdheaders.h>
#define Default_Port 80
#define Default_Connect_Time 10 //define the time we try to connect
#define Max_CommandLen 1000 //define the max length of command we send to a http server
#define Default_Txt_Len 1048576 //假设网页默认长度1M,注意这是一个演示程序,当网页>1M程序出错
typedef struct _Url_Str_Data { //a structure for URL
char Protocol[8];
char Host[256];
unsigned short Port;
char Path[1024];
char FileName[256];
} UrlStrData, *PtrUrlStrData;
char SaveBox[Default_Txt_Len];
//-----------
char *GetHttpFiles(UrlStrData UrlData);
int GetIP(PtrUrlStrData PtrUrlData,SOCKADDR_IN *PtrServerAddr);
int StartSocket(void);
int CreateSocket(SOCKET *sock);
int CallServer(SOCKET *sock,SOCKADDR_IN *PtrServerAddr);
int TCPSendAll(SOCKET *sock,char *data);
void MakeCommand(char *CommandBox,UrlStrData UrlData);
void main(void)
{
UrlStrData UrlData;
strcpy(UrlData.Host,"auto.163.com");
strcpy(UrlData.Path,"\0");
UrlData.Port=Default_Port;
strcpy(UrlData.FileName,"\0");
char *p;
p=GetHttpFiles(UrlData);
printf("%s",p);
free(p);
return ;
}
char *GetHttpFiles(UrlStrData UrlData)
{
SOCKET sock;
SOCKADDR_IN ServerAddr;
if(StartSocket()==-1)
return NULL;
if(GetIP(&UrlData,&ServerAddr)==-1){
WSACleanup();
return NULL;
}
int ServerExist=1; //1表示对方服务器存在
for(int i=0;i<Default_Connect_Time;i++){
if(CallServer(&sock,&ServerAddr)==1){
//puts("Connect OK.");
break;
}
if(i==(Default_Connect_Time-1))
ServerExist=0;
}
if(ServerExist==0){
//puts("Server may not start yet.");
WSACleanup();
return NULL;
}
char SendCommand[Max_CommandLen];
memset(SendCommand,0,Max_CommandLen);
MakeCommand(SendCommand,UrlData);
if(TCPSendAll(&sock,SendCommand)==-1){
//puts("wrong");
closesocket(sock);
WSACleanup();
return NULL;
}
int result=1;
//char SaveBox[Default_Txt_Len];
memset(SaveBox,0,Default_Txt_Len);
char buf[2];
memset(buf,0,2);
while(result>0){
result = recv(sock,buf,1,0);
//printf("%d",result);
//printf("%s",buf);
strcat(SaveBox,buf);
memset(buf,0,2);
}
closesocket(sock);
WSACleanup();
return SaveBox;
}
int StartSocket(void)
{
WSADATA WSAData;
if(WSAStartup(MAKEWORD(2,2),&WSAData)!=0){
//printf("Socket init fail!\n");
return -1;
}
return 1;
}
int CreateSocket(SOCKET *sock)
{
*sock=socket(AF_INET,SOCK_STREAM,0);
if(*sock==INVALID_SOCKET){
//printf("Socket create fail!\n");
return -1;
}
return 1;
}
int GetIP(PtrUrlStrData PtrUrlData,SOCKADDR_IN *PtrServerAddr)
{
struct hostent *PtrHost;
PtrHost=gethostbyname(PtrUrlData->Host);
if(PtrHost==NULL){
//puts("Host name wrong.");
return -1;
}
PtrServerAddr->sin_family=AF_INET;
PtrServerAddr->sin_port=htons(PtrUrlData->Port);
PtrServerAddr->sin_addr.s_addr=inet_addr(inet_ntoa(*((struct in_addr *)PtrHost->h_addr)));
memset(&PtrServerAddr->sin_zero[0],0,8);
return 1;
}
int CallServer(SOCKET *sock,SOCKADDR_IN *PtrServerAddr)
{
if(CreateSocket(sock)==-1){
//puts("Cannot create socket.");
return -1;
}
if(connect(*sock,(struct sockaddr *)PtrServerAddr,sizeof(SOCKADDR_IN))==SOCKET_ERROR){
//printf("Connect fail.\n");
closesocket(*sock);
return -1;
}
return 1;
}
int TCPSendAll(SOCKET *sock,char *data)
{
int length=0;
int TotalSended=0;
int LengthAll=strlen(data);
int bytesleft=LengthAll;
while(TotalSended<LengthAll){
length=send(*sock,data+TotalSended,bytesleft,0);
if(length==SOCKET_ERROR){
printf("send data error!\n");
//closesocket(sock);
//WSACleanup();
return -1;
}
TotalSended+=length;
bytesleft-=length;
}
return 1;
}
void MakeCommand(char *CommandBox,UrlStrData UrlData)
{
char *Ptr1="GET /";
char *Ptr6=" HTTP/1.1\r\nAccept: */*\r\nAccept-Language: zh-cn\r\n";
char *Ptr3="User-Agent: Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1)\r\n";
char *Ptr4="Host: ";
char *Ptr5="Connection: close\r\n\r\n";
sprintf(CommandBox,"%s%s%s%s",Ptr1,UrlData.Path,UrlData.FileName,Ptr6,Ptr3);
int offset=strlen(CommandBox);
char UnShortToStr[18];
sprintf(CommandBox+offset,"%s%s:%s\r\n",Ptr4,UrlData.Host,itoa((int)(short)UrlData.Port,UnShortToStr,10));
offset=strlen(CommandBox);
sprintf(CommandBox+offset,"%s",Ptr5);
return ;
}
这个程序将下载下的网页文件打印在屏幕上,可以复制下来另存为html文件就是我们常用的网页了。

如何在windows环境下实现socket编程.doc

数学之美 系列十九 - 马尔可夫链的扩展 贝叶斯网络 (Bayesian Networks)

,

1/28/2007 09:53:00 下午
发表者:Google 研究员,吴军

我们在前面的系列中多次提到马尔可夫链 (Markov
Chain)
,它描述了一种状态序列,其每个状态值取决于前面有限个状态。这种模型,对很多实际问题来讲是一种很粗略的简化。在现实生活中,很多事物相互的关系并不能用一条链来串起来。它们之间的关系可能是交叉的、错综复杂的。比如在下图中可以看到,心血管疾病和它的成因之间的关系是错综复杂的。显然无法用一个链来表示。

我们可以把上述的有向图看成一个网络,它就是贝叶斯网络。其中每个圆圈表示一个状态。状态之间的连线表示它们的因果关系。比如从心血管疾病出发到吸烟的弧线表示心血管疾病可能和吸烟有关。当然,这些关系可以有一个量化的可信度 (belief),用一个概率描述。我们可以通过这样一张网络估计出一个人的心血管疾病的可能性。在网络中每个节点概率的计算,可以用贝叶斯公式来进行,贝叶斯网络因此而得名。由于网络的每个弧有一个可信度,贝叶斯网络也被称作信念网络 (belief networks)。

和马尔可夫链类似,贝叶斯网络中的每个状态值取决于前面有限个状态。不同的是,贝叶斯网络比马尔可夫链灵活,它不受马尔可夫链的链状结构的约束,因此可以更准确地描述事件之间的相关性。可以讲,马尔可夫链是贝叶斯网络的特例,而贝叶斯网络是马尔可夫链的推广。

使用贝叶斯网络必须知道各个状态之间相关的概率。得到这些参数的过程叫做训练。和训练马尔可夫模型一样,训练贝叶斯网络要用一些已知的数据。比如在训练上面的网络,需要知道一些心血管疾病和吸烟、家族病史等有关的情况。相比马尔可夫链,贝叶斯网络的训练比较复杂,从理论上讲,它是一个 NP-complete 问题,也就是说,对于现在的计算机是不可计算的。但是,对于某些应用,这个训练过程可以简化,并在计算上实现。

值得一提的是 IBM Watson 研究所的茨威格博士 (Geoffrey Zweig) 和西雅图华盛顿大学的比尔默 (Jeff Bilmes) 教授完成了一个通用的贝叶斯网络的工具包,提供给对贝叶斯网络有兴趣的研究者。

贝叶斯网络在图像处理、文字处理、支持决策等方面有很多应用。在文字处理方面,语义相近的词之间的关系可以用一个贝叶斯网络来描述。我们利用贝叶斯网络,可以找出近义词和相关的词,在 Google 搜索和 Google 广告中都有直接的应用。

十说电容

,

话说电容之一:电容的作用


写在前面:本人将着手从电容的作用、分类、选择等诸方面论述,敬请批评指正。


作为无源元件之一的电容,其作用不外乎以下几种:


1、应用于电源电路,实现旁路、去藕、滤波和储能的作用,下面分类详述之:


1)旁路

旁路电容是为本地器件提供能量的储能器件,它能使稳压器的输出均匀化,降低负载需求。就像小型可充电电池一样,旁路电容能够被充电,并向器件进行放电。为尽量减少阻抗,旁路电容要尽量靠近负载器件的供电电源管脚和地管脚。这能够很好地防止输入值过大而导致的地电位抬高和噪声。地弹是地连接处在通过大电流毛刺时的电压降。


2)去藕

去藕,又称解藕。从电路来说,总是可以区分为驱动的源和被驱动的负载。如果负载电容比较大,驱动电路要把电容充电、放电,才能完成信号的跳变,在上升沿比较陡峭的时候,电流比较大,这样驱动的电流就会吸收很大的电源电流,由于电路中的电感,电阻(特别是芯片管脚上的电感,会产生反弹),这种电流相对于正常情况来说实际上就是一种噪声,会影响前级的正常工作。这就是耦合。


去藕电容就是起到一个电池的作用,满足驱动电路电流的变化,避免相互间的耦合干扰。

将旁路电容和去藕电容结合起来将更容易理解。旁路电容实际也是去藕合的,只是旁路电容一般是指高频旁路,也就是给高频的开关噪声提高一条低阻抗泄防途径。高频旁路电容一般比较小,根据谐振频率一般是0.1u,0.01u等,而去耦合电容一般比较大,是10uF或者更大,依据电路中分布参数,以及驱动电流的变化大小来确定。


旁路是把输入信号中的干扰作为滤除对象,而去耦是把输出信号的干扰作为滤除对象,防止干扰信号返回电源。这应该是他们的本质区别。


3)滤波

从理论上(即假设电容为纯电容)说,电容越大,阻抗越小,通过的频率也越高。但实际上超过1uF的电容大多为电解电容,有很大的电感成份,所以频率高后反而阻抗会增大。有时会看到有一个电容量较大电解电容并联了一个小电容,这时大电容通低频,小电容通高频。电容的作用就是通高阻低,通高频阻低频。电容越大低频越容易通过,电容越大高频越容易通过。具体用在滤波中,大电容(1000uF)滤低频,小电容(20pF)滤高频。
曾有网友将滤波电容比作“水塘”。由于电容的两端电压不会突变,由此可知,信号频率越高则衰减越大,可很形象的说电容像个水塘,不会因几滴水的加入或蒸发而引起水量的变化。它把电压的变动转化为电流的变化,频率越高,峰值电流就越大,从而缓冲了电压。滤波就是充电,放电的过程。


4)储能

储能型电容器通过整流器收集电荷,并将存储的能量通过变换器引线传送至电源的输出端。电压额定值为40~450VDC、电容值在220~150 000uF之间的铝电解电容器(如EPCOS公司的 B43504或B43505)是较为常用的。根据不同的电源要求,器件有时会采用串联、并联或其组合的形式, 对于功率级超过10KW的电源,通常采用体积较大的罐形螺旋端子电容器。


2、应用于信号电路,主要完成耦合、振荡/同步及时间常数的作用:


1)耦合

举个例子来讲,晶体管放大器发射极有一个自给偏压电阻,它同时又使信号产生压降反馈到输入端形成了输入输出信号耦合,这个电阻就是产生了耦合的元件,如果在这个电阻两端并联一个电容,由于适当容量的电容器对交流信号较小的阻抗,这样就减小了电阻产生的耦合效应,故称此电容为去耦电容。


2)振荡/同步

包括RC、LC振荡器及晶体的负载电容都属于这一范畴。


3)时间常数

这就是常见的 R、C 串联构成的积分电路。当输入信号电压加在输入端时,电容(C)上的电压逐渐上升。而其充电电流则随着电压的上升而减小。电流通过电阻(R)、电容(C)的特性通过下面的公式描述:

i = (V/R)e-(t/CR)

话说电容之二:电容的选择


通常,应该如何为我们的电路选择一颗合适的电容呢?笔者认为,应基于以下几点考虑:


1、静电容量

2、额定耐压

3、容值误差

4、直流偏压下的电容变化量

5、噪声等级

6、电容的类型

7、电容的规格


那么,又无捷径可寻呢?其实,电容作为器件的外围元件,几乎每个器件的 Datasheet 或者 Solutions,都比较明确地指明了外围元件的选择参数,也就是说,据此可以获得基本的器件选择要求,然后再进一步完善细化之。


其实选用电容时不仅仅是只看容量和封装,具体要看产品所使用环境,特殊的电路必须用特殊的电容。


下面是 chip capacitor 根据电介质的介电常数分类, 介电常数直接影响电路的稳定性。


NP0 or CH (K<150): 电气性能最稳定,基本上不随温度﹑电压与时间的改变而改变,适用于对稳定性要求高的高频电路。鉴于K值较小,所以在 0402、0603、0805 封装下很难有大容量的电容。如 0603 一般最大的 10nF 以下。


X7R or YB (2000<K<4000): 电气性能较稳定,在温度﹑电压与时间改变时性能的变化并不显著(ΔC<±10%)。适用于隔直、偶合、旁路与对容量稳定性要求不太高的全频鉴电路。

Y5V or YF (K>15000): 容量稳定性较 X7R 差(ΔC<+20%~-80%),容量﹑损耗对温度、电压等测试条件较敏感,但由于其K值较大,所以适用于一些容值要求较高的场合。

话说电容之三:电容的分类


基于电容的材料特性,其可分为以下几大类:


1、铝电解电容

电容容量范围为0.1uF--22000uF,高脉动电流、长寿命、大容量的不二之选,广泛应用于电源滤波、解藕等场合。


2、薄膜电容

电容容量范围为0.1pF--10uF,具有较小公差、较高容量稳定性及极低的压电效应,因此是X、Y安全电容、EMI/EMC的首选。


3、钽电容

电容容量范围为2.2uF--560uF,低等效串联电阻(ESR)、低等效串联电感(ESL)。脉动吸收、瞬态响应及噪声抑制都优于铝电解电容,是高稳定电源的理想选择。


4、陶瓷电容

电容容量范围为0.5pF--100uF,独特的材料和薄膜技术的结晶,迎合了当今“更轻、更薄、更节能”的设计理念。


5、超级电容

电容容量范围为0.022F--70F,极高的容值,因此又称做“金电容”或者“法拉电容”。主要特点是:超高容值、良好的充/放电特性,适合于电能存储和电源备份。缺点是耐压较低,工作温度范围较窄。

话说电容之四:多层陶瓷电容(MLCC)


对于电容而言,小型化和高容量是永恒不变的发展趋势。其中,要数多层陶瓷电容(MLCC)的发展最快。


多层陶瓷电容在便携产品中广泛应用极为广泛,但近年来数字产品的技术进步对其提出了新要求。例如,手机要求更高的传输速率和更高的性能;基带处理器要求高速度、低电压;LCD模块要求低厚度(0.5mm)、大容量电容。 而汽车环境的苛刻性对多层陶瓷电容更有特殊的要求:首先是耐高温,放置于其中的多层陶瓷电容必须能满足150度的工作温度;其次是在电池电路上需要短路失效保护设计。


也就是说,小型化、高速度和高性能、耐高温条件、高可靠性已成为陶瓷电容的关键特性。


陶瓷电容的容量随直流偏置电压的变化而变化。直流偏置电压降低了介电常数,因此需要从材料方面,降低介电常数对电压的依赖,优化直流偏置电压特性。


应用中较为常见的是 X7R(X5R) 类多层陶瓷电容,它的容量主要集中在 1000pF 以上,该类电容器主要性能指标是等效串联电阻(ESR),在高波纹电流的电源去耦、滤波及低频信号耦合电路的低功耗表现比较突出。


另一类多层陶瓷电容是 C0G 类,它的容量多在 1000pF 以下,该类电容器主要性能指标是损耗角正切值 tgδ(DF)。传统的贵金属电极(NME)的 C0G 产品 DF 值范围是(2.0~8.0)×10-4,而技术创新型贱金属电极(BME)的 C0G 产品 DF 值范围为(1.0~2.5)×10-4,约是前者的 31~50%。该类产品在载有 T/R 模块电路的 GSM、CDMA、无绳电话、蓝牙、GPS 系统中低功耗特性较为显著。较多用于各种高频电路,如振荡/同步器、定时器电路等。

话说电容之五:钽电容替代电解电容的误区


通常的看法是钽电容性能比铝电容好,因为钽电容的介质为阳极氧化后生成的五氧化二钽,它的介电能力(通常用ε表示)比铝电容的三氧化二铝介质要高。因此在同样容量的情况下,钽电容的体积能比铝电容做得更小。(电解电容的电容量取决于介质的介电能力和体积,在容量一定的情况下,介电能力越高,体积就可以做得越小,反之,体积就需要做得越大)再加上钽的性质比较稳定,所以通常认为钽电容性能比铝电容好。


但这种凭阳极判断电容性能的方法已经过时了,目前决定电解电容性能的关键并不在于阳极,而在于电解质,也就是阴极。因为不同的阴极和不同的阳极可以组合成不同种类的电解电容,其性能也大不相同。采用同一种阳极的电容由于电解质的不同,性能可以差距很大,总之阳极对于电容性能的影响远远小于阴极。


还有一种看法是认为钽电容比铝电容性能好,主要是由于钽加上二氧化锰阴极助威后才有明显好于铝电解液电容的表现。如果把铝电解液电容的阴极更换为二氧化锰, 那么它的性能其实也能提升不少。


可以肯定,ESR 是衡量一个电容特性的主要参数之一。但是,选用电容,应避免 ESR 越低越好,品质越高越好等误区。衡量一个产品,一定要全方位、多角度的去考虑,切不可把电容的作用有意无意的夸大。


---以上引用了部分网友的经验总结。


普通电解电容的结构是阳极和阴极和电解质,阳极是钝化铝,阴极是纯铝,所以关键是在阳极和电解质。阳极的好坏关系着耐压电介系数等问题。

一般来说,钽电解电容的ESR要比同等容量同等耐压的铝电解电容小很多,高频性能更好。如果那个电容是用在滤波器电路(比如中心为50Hz的带通滤波器)的话,要注意容量变化后对滤波器性能(通带...)的影响。

话说电容之六:旁路电容的应用问题


嵌入式设计中,要求 MCU 从耗电量很大的处理密集型工作模式进入耗电量很少的空闲/休眠模式。这些转换很容易引起线路损耗的急剧增加,增加的速率很高,达到 20A/ms 甚至更快。


通常采用旁路电容来解决稳压器无法适应系统中高速器件引起的负载变化,以确保电源输出的稳定性及良好的瞬态响应。旁路电容是为本地器件提供能量的储能器件,它能使稳压器的输出均匀化,降低负载需求。就像小型可充电电池一样,旁路电容能够被充电,并向器件进行放电。为尽量减少阻抗,旁路电容要尽量靠近负载器件的供电电源管脚和地管脚。这能够很好地防止输入值过大而导致的地电位抬高和噪声。地弹是地连接处在通过大电流毛刺时的电压降。


应该明白,大容量和小容量的旁路电容都可能是必需的,有的甚至是多个陶瓷电容和钽电容。这样的组合能够解决上述负载电流或许为阶梯变化所带来的问题,而且还能提供足够的去耦以抑制电压和电流毛刺。在负载变化非常剧烈的情况下,则需要三个或更多不同容量的电容,以保证在稳压器稳压前提供足够的电流。快速的瞬态过程由高频小容量电容来抑制,中速的瞬态过程由低频大容量来抑制,剩下则交给稳压器完成了。
还应记住一点,稳压器也要求电容尽量靠近电压输出端。

话说电容之七:电容的等效串联电阻ESR



普遍的观点是:一个等效串联电阻(ESR)很小的相对较大容量的外部电容能很好地吸收快速转换时的峰值(纹波)电流。但是,有时这样的选择容易引起稳压器(特别是线性稳压器 LDO)的不稳定,所以必须合理选择小容量和大容量电容的容值。永远记住,稳压器就是一个放大器,放大器可能出现的各种情况它都会出现。


由于 DC/DC 转换器的响应速度相对较慢,输出去耦电容在负载阶跃的初始阶段起主导的作用,因此需要额外大容量的电容来减缓相对于 DC/DC 转换器的快速转换,同时用高频电容减缓相对于大电容的快速变换。通常,大容量电容的等效串联电阻应该选择为合适的值,以便使输出电压的峰值和毛刺在器件的 Dasheet 规定之内。


高频转换中,小容量电容在 0.01μF 到0.1μF 量级就能很好满足要求。表贴陶瓷电容或者多层陶瓷电容(MLCC)具有更小的 ESR。另外,在这些容值下,它们的体积和 BOM 成本都比较合理。如果局部低频去耦不充分,则从低频向高频转换时将引起输入电压降低。电压下降过程可能持续数毫秒,时间长短主要取决于稳压器调节增益和提供较大负载电流的时间。


用 ESR 大的电容并联比用 ESR 恰好那么低的单个电容当然更具成本效益。然而,这需要你在 PCB 面积、器件数目与成本之间寻求折衷。

话说电容之八:电解电容的电参数


这里的电解电容器主要指铝电解电容器,其基本的电参数包括下列五点:


1、电容值


电解电容器的容值,取决于在交流电压下工作时所呈现的阻抗。因此容值,也就是交流电容值,随着工作频率、电压以及测量方法的变化而变化。在标准 JISC 5102 规定:铝电解电容的电容量的测量条件是在频率为 120Hz,最大交流电压为 0.5Vrms,DC bias 电压为1.5~2.0V 的条件下进行。可以断言,铝电解电容器的容量随频率的增加而减小。



2、损耗角正切值 Tan δ


在电容器的等效电路中,串联等效电阻 ESR 同容抗 1/ωC 之比称之为 Tan δ,这里的 ESR 是在 120Hz 下计算获得的值。显然,Tan δ随着测量频率的增加而变大,随测量温度的下降而增大。



3、阻抗 Z


在特定的频率下,阻碍交流电流通过的电阻即为所谓的阻抗(Z)。它与电容等效电路中的电容值、电感值密切相关,且与 ESR 也有关系。

Z = /ESR2 + (XL - XC)2 (此处开平方)

式中,Xc = 1 / ωC = 1 / 2πfC
XL = ωL = 2πfL

电容的容抗(Xc)在低频率范围内随着频率的增加逐步减小,频率继续增加达到中频范围时电抗(XL)降至 ESR 的值。当频率达到高频范围时感抗(XL)变为主导,所以阻抗是随着频率的增加而增加。



4、漏电流


电容器的介质对直流电流具有很大的阻碍作用。然而,由于铝氧化膜介质上浸有电解液,在施加电压时,重新形成的以及修复氧化膜的时候会产生一种很小的称之为漏电流的电流。通常,漏电流会随着温度和电压的升高而增大。



5、纹波电流和纹波电压


在有的资料中称作涟波电流和涟波电压,其实就是 ripple current,ripple voltage。含义就是电容器所能耐受纹波电流/电压值。二者和 ESR 之间的关系密切,可以用下面的式子表示:

Urms = Irms × R

式中,Vrms 表示纹波电压
Irms 表示纹波电流
R 表示电容的 ESR

由上可见,当纹波电流增大的时候,即使在 ESR 保持不变的情况下,涟波电压也会成倍提高。换言之,当纹波电压增大时,纹波电流也随之增大,这也是要求电容具备更低 ESR 值的原因。叠加入纹波电流后,由于电容内部的等效串连电阻(ESR)引起发热,从而影响到电容器的使用寿命。一般的,纹波电流与频率成正比,因此低频时纹波电流也比较低。

话说电容之十:电源输入端的X,Y安全电容


在交流电源输入端,一般需要增加3个电容来抑制EMI传导干扰。


交流电源输入分为3根线:火线(L)/零线(N)/地线(G)。在火线和地线之间及在零线和地线之间并接的电容,一般称之为Y电容。这两个Y电容连接的位置比较关键,必须需要符合相关安全标准,以防引起电子设备漏电或机壳带电,容易危及人身安全及生命,所以它们都属于安全电容,要求电容值不能偏大,而耐压必须较高。一般地,工作在亚热带的机器,要求对地漏电电流不能超过0.7mA;工作在温带机器,要求对地漏电电流不能超过0.35mA。因此,Y电容的总容量一般都不能超过4700PF。


特别提示:Y电容为安全电容,必须取得安全检测机构的认证。Y电容的耐压一般都标有安全认证标志和AC250V或AC275V字样,但其真正的直流耐压高达5000V以上。因此,Y电容不能随意使用标称耐压AC250V,或DC400V之类的普通电容来代用。


在火线和零线抑制之间并联的电容,一般称之为X电容。由于这个电容连接的位置也比较关键,同样需要符合安全标准。因此,X电容同样也属于安全电容之一。X电容的容值允许比Y电容大,但必须在X电容的两端并联一个安全电阻,用于防止电源线拔插时,由于该电容的充放电过程而致电源线插头长时间带电。安全标准规定,当正在工作之中的机器电源线被拔掉时,在两秒钟内,电源线插头两端带电的电压(或对地电位)必须小于原来额定工作电压的30%。


同理,X电容也是安全电容,必须取得安全检测机构的认证。X电容的耐压一般都标有安全认证标志和AC250V或AC275V字样,但其真正的直流耐压高达2000V以上,使用的时候不要随意使用标称耐压AC250V,或DC400V之类的的普通电容来代用。


X电容一般都选用纹波电流比较大的聚脂薄膜类电容,这种电容体积一般都很大,但其允许瞬间充放电的电流也很大,而其内阻相应较小。普通电容纹波电流的指标都很低,动态内阻较高。用普通电容代替X电容,除了耐压条件不能满足以外,一般纹波电流指标也是难以满足要求的。


实际上,仅仅依靠用Y电容和X电容来完全滤除掉传导干扰信号是不可能的。因为干扰信号的频谱非常宽,基本覆盖了几十KHz到几百MHz甚至上千MHz的频率范围。通常,对低端干扰信号的滤除需要很大容量的滤波电容,但受到安全条件的限制,Y电容和X电容的容量都不能用大;对高端干扰信号的滤除,大容量电容的滤波性能又极差,特别是聚脂薄膜电容的高频性能一般都比较差,因为它是用卷绕工艺生产的,并且聚脂薄膜介质高频响应特性与陶瓷或云母相比相差很远,一般聚脂薄膜介质都具有吸附效应,它会降低电容器的工作频率,聚脂薄膜电容工作频率范围大约都在1MHz左右,超过1MHz其阻抗将显著增加。


因此,为抑制电子设备产生的传导干扰,除了选用Y电容和X电容之外,还要同时选用多个类型的电感滤波器,组合起来一起滤除干扰。电感滤波器多属于低通滤波器,但电感滤波器也有很多规格类型,例如有:差模、共模,以及高频、低频等。每种电感主要都是针对某一小段频率的干扰信号滤除而起作用,对其它频率的干扰信号的滤除效果不大。通常,电感量很大的电感,其线圈匝数较多,那么电感的分布电容也很大。高频干扰信号将通过分布电容旁路掉。而且,导磁率很高的磁芯,其工作频率则较低。目前,大量使用的电感滤波器磁芯的工作频率大多数都在75MHz以下。对于工作频率要求比较高的场合,必须选用高频环形磁芯,高频环形磁芯导磁率一般都不高,但漏感特别小,比如,非晶合金磁芯,坡莫合金等。

转自:http://xabai.21ic.org/user1/1721/index.html

电子邮件协议

,


如果你会用socket来编写网络程序的话,那么下面这个东西应该不会很难(easy更为准确)。
你想拥有一个自己的电子邮件发送系统吗?If u want it, then do it.:D
一般我们只需关心客户端处的发送,服务器怎么样就不关我们的事了(sohu或者163可能不这么想问题p: )。利用socket就可以很方便的来实现。
在用connect()成功连接对方服务器后,在客户机上要做的只是发送协议命令即可。这里简要说明一下SMTP的格式。我们用C代表clinet,S代表server。注:RFC协议下一般不区分参数的大小写。

1.SMTP client say 'hello' to SMTP server.
Format: HELO 发送方的主机名 <CRLF> //<CRLF> is '\r'+'\n'
eg:
C: HELO ZZZ // ZZZ is the hostname
S: 250 zzz Hello smtp.163.com,please to meet you
上面这条命令告诉SMTP server你想向他发邮件。250为同意的响应码,如果是550,表示server拒绝了你。

2.To tell the server where the client comes from.
Format: MAIL FROM: 发信人的电子邮件地址 <CRLF>
eg:
C: MAIL FROM: YY@163.com
S: 250 OK
client发送这条命令告知server发信人邮件地址。当投递失败server会根据这个地址退回错误邮件。如果返回250表示session将继续进行。550表示server不想deliver for u。553表示syntax error。

3.To tell where u want to deliver.
Format: RCPT TO: 收信人邮箱地址 <CRLF>
eg:
C: RCPT TO: lau_jia@operamail.com
S: 250<lau_jia@operamail.com>,Recipient ok
clinet发送对方email地址,服务器负责将随后client发送的信件送到这个地址。250表示成功接受命令,553表示邮件地址不合法。

4.Ask for sending the mail.
Format: DATA <CRLF>
eg:
C: DATA
S: 354 Start mail input;end with<CRLF>.<CRLF>
这个命令比较特殊,只有命令,而没有参数。他告知服务器现在要准备发送邮件内容了。354表示server已经准备好了接收邮件数据,client可以发送邮件了。并且响应中也提醒了client邮件要以<CRLF>.<CRLF>来结尾,表示邮件结束。如果邮件内容是一行开头一个句号,那么server会误以为邮件结束。解决方法就是将一个句号写作两个句号相连,作为SMTP协议,会将两个句号自动删掉一个,恢复原来数据面貌。
接下去就可以发送数据了,在收到354后,client可以直接发送email的数据了,直到server收到<CRLF>.<CRLF>为止。这时server会发送一个一个是否成功的指示响应,一般为:
250 ok,message saved
如果响应为503,表示上面的1,2,3,4条命令顺序不对。

5.I wanna do nothing.
Format: NOOP <CRLF>
server收到这个命令什么也不做,仅以250 ok作答,这个可用来测试server与client之间的连接。

6.Is the email address legal.
Format: VRFY 电子邮箱地址 <CRLF>
eg:
C: VRFY ZHANG@263.COM
S: 550 Unknown address:<ZHANG>
or
252 Couldn't verify<ZHANG@263.COM>but will attempt delivery anyway
550表示邮箱的地址格式不合法或者无法发送,如果是252表示邮箱地址格式合法,但是不能确定该邮箱是否存在且有效,但是server愿意尝试发送。

7.Reset the SMTP server.
Format: RSET <CRLF>
这个用来复位链接状态。server收到这个命令后恢复到接收到HELO之前的状态,并以250 ok作答。

8.Ask for help info.
Format: HELP<CRLF>
or
HELP 命令关键字 <CRLF>
对于单纯的HELP命令,服务器返回可用命令的摘要列表,以及关于server的一般信息。关于带关键字的HELP命令,server给出详细帮助信息。

9.I quit.
Format: QUIT <CRLF>
eg:
C: QUIT
S: 221 smtp.163.com ESMTP server closing connection
server接收到后返回221,并关闭TCP连接。

下面给出SMTP常见的响应码:
221 系统状态或者系统帮助应答。
214 帮助信息。
220 服务就绪。
221 服务器关闭传输通道。
250 请求的邮件操作已经完成。
251 非本地用户,按照前向路径(forward-path)转发。
354 启动邮件输入,要求邮件以<CRLF>.<CRLF>结束。
421 服务不可用,关闭传输通道。
450 没有执行请求的邮箱操作,因为邮箱不可用。
451 处理过程出错,请求的操作中止。
452 系统存储空间不够,请求的操作没有发生。
500 语法错误,无法识别命令。
501 参数或者变元存在语法错误。
502 命令不能识别。
503 错误的命令序列。
504 命令的参数不能实现。
550 请求的操作不能发生,邮箱不可用。
551 用户不在本地,请尝试使用前向路径。
552 超出存储分配,请求的邮件操作中止。
553 请求的操作不能执行,因为信箱语法错误。
554 事务失败。
以上就是一般的响应,更多的可以参考RFC2821。

如果想把邮件写的正规一点(好像是FOXMAIL发的一样),可以在邮件内容前加上下面的内容。
From: XXX@xxx.com //表示是哪里发送的
To: XXX@xxx.com //表示要发给谁
Date: Fri,1 Dec 06 14:32:22 EST //表示发送日期
Subject: lunch with me //主题

正文。。。。。。。。。。。。。

如果想抄送等可以加上下面的关键字段(只给出常用的)
Reply-To: xxx@xxx.com //表示这是一封回信
Cc: xxx@xxx.com //抄送
Bcc: xxx@xx.com //密抄送
注意这些头信息中From和Date字段对于标准的服务器是必须要有的,To,Cc,Bcc必须要有一个,其它可选。

通过上述介绍可以发现SMTP有其局限性,于是扩展出了MIME来支持多媒体,不过这个有点复杂了,有兴趣的人可以参考文后的文献。

目前大多数的邮件服务器都支持POP3的服务,这是一种和SMTP类似的协议方式,但是更简单。看下面一个实际的POP3回话例子:

(Connect to the pop3 server...)
S:+OK POP3 server ready //服务器已经准备就绪
C:USER Wang //用户名是Wang
S:+OK
C: PASS table //密码是table
S:+OK login successful //登陆成功
C:LIST //列出邮件清单
S:1 AAAA //第一封信
S:2 BBBB
S:3 CCCC
C:RETR 1 //取回第一封信
S:+OK(send message 1)
C: DELE 1 //删除第一封信
S:+OK
C:RETR 2
S:+OK(send message 2)
C: DELE 2
S:+OK
C:QUIT //退出回话
S:+OK POP3 server disconnecting //POP3断开连接
可以看到应答要比SMTP要简单的多,只有两个应答"+OK"表示成功,"-ERR"表示失败。

下面介绍一些常用命令:

1.USER
Format: USER 用户名 <CRLF>
eg:
C: USER
S: -ERR missing user name argument
C: USER Liu
S: +OK
这个命令用来登陆邮箱时输入用户名。

2.PASS
Format: PASS 口令 <CRLF>
有时在发送完login信息后还是无法登陆,这是因为已经有一个进程登陆了该邮箱,POP3只能独占邮箱访问权,这时如果还要登陆,不能简单的只发送PASS命令,还要重发USER命令。

3.QUIT
中止会话。POP3服务器更新邮箱状态,删除有删除标记(DELE来标记)的邮件,并释放邮箱进程。

4.NOOP
这个命令do nothing,可以用来检测连接。

5.STAT
请求返回邮件数量和邮箱大小,但是不包括已做删除标记的邮件。
eg:
C: STAT
S: +OK 5 9086

6.LIST
Format 1:LIST<CRLF>
这个用来返回所有邮件的信息(序号和大小)。
eg:
C: LIST
S: +OK
1 2090
2 4080
...
...

Format 2:LIST 邮件序号<CRLF>
返回指定序号邮件的信息。如果该邮件已被标记了删除或者不存在,则返回出错信息。

7.RETR
Format: RETR 邮件序号 <CRLF>
用来取回序号指定的邮件。应答为多行应答,包括信头和信体,如果有附件,附件以文本形式返回。最后以和SMTP一样的格式表示中止。
eg:
C: RETR 1
S: +OK 13100 octets
Received:...
Data:...
From:...
...
...

...<CRLF>
.
<CRLF>

8.TOP
Format: TOP 邮件序号 行数 <CRLF>
取回指定邮件的邮件头和指定信体行数。如果行数为0或不指定,则返回头信息和空白行。注意有些POP3并没实现该命令。

9.DELE
Format: DELE 邮件序号 <CRLF>
该命令不会真正删除邮件,而只是加了一个删除标记,只有在正常更新邮箱后才会真正删除。一般为用QUIT命令退出后更新邮箱。

10.REST
复位邮箱,原来被标记删除的全部取消删除标记。

11.UIDL
Format: UIDL 邮件序号 <CRLF>
这个命令返回每封信的唯一标示号,一般只以简单的1,2,3来表示邮件会容易混淆,这个可以帮助client来准确的定位邮件。

参考文献:
网络编程实用教程第10章, 叶树华,高志红 编著,人民邮电出版社

我写的拼音汉字自动转换程序

,

这不是一般的拼音输入法,去google输入一下拼音看看有什么结果,对了,我这个就是那样的一个程序。做这么个东西是看了胡军的数学之美,他在里面稍稍提到了马尔可夫的应用,作为一个google爱好者仿制google的技术一直是我的爱好:hat: ,所以就有了这么个东西。另一个我做的和google相关的技术可以在这里找到。



程序代码及可执行文件下载:yes:
1.rar文件
2.zip文件
为了使结果更好,我把字典改了一下作为补丁放在这里,只要把这个字典替换原来的就可以了。
字典补丁下载

, ,

http://episte.math.ntu.edu.tw/articles/mm/mm_13_3_01/index.html
台湾人写的关于熵的东西,基本上从香农的论文上来得,但是比很多大陆的教授写得要好。

小论文提交了

, ,

今天早上把小论文给改了一下,听了同学的建议先发一下再说,管他行不行呢。我开始是让导师改的,可是中国的情况就是这样,给导师的文章不知道他要到什么时候才看了,下午的时候发到了计算机工程与应用上,内容就是单词的自动纠错。源程序早上也改了一下 ,使得更符合论文的思想了。 现在还提供下载:star:
http://my.opera.com/lau_jia/homes/blog/EngWordMatch.rar
http://my.opera.com/lau_jia/homes/blog/EngWordMatch.zip

数学之美 系列十五 繁与简 自然语言处理的几位精英

,

发表者:吴军,Google 研究员

我在数学之美系列中一直强调的一个好方法就是简单。但是,事实上,自然语言处理中也有一些特例,比如有些学者将一个问题研究到极致,执著追求完善甚至可以说完美的程度。他们的工作对同行有很大的参考价值,因此我们在科研中很需要这样的学者。在自然语言处理方面新一代的顶级人物麦克尔 · 柯林斯 (Michael Collins) 就是这样的人。


柯林斯:追求完美

柯林斯从师于自然语言处理大师马库斯 (Mitch Marcus)(我们以后还会多次提到马库斯),从宾夕法利亚大学获得博士学位,现任麻省理工学院 (MIT) 副教授(别看他是副教授,他的水平在当今自然语言处理领域是数一数二的),在作博士期间,柯林斯写了一个后来以他名字命名的自然语言文法分析器 (sentence parser),可以将书面语的每一句话准确地进行文法分析。文法分析是很多自然语言应用的基础。虽然柯林斯的师兄布莱尔 (Eric Brill) 和 Ratnaparkhi 以及师弟 Eisnar 都完成了相当不错的语言文法分析器,但是柯林斯却将它做到了极致,使它在相当长一段时间内成为世界上最好的文法分析器。柯林斯成功的关键在于将文法分析的每一个细节都研究得很仔细。柯林斯用的数学模型也很漂亮,整个工作可以用完美来形容。我曾因为研究的需要,找柯林斯要过他文法分析器的源程序,他很爽快地给了我。我试图将他的程序修改一下来满足我特定应用的要求,但后来发现,他的程序细节太多以至于很难进一步优化。柯林斯的博士论文堪称是自然语言处理领域的范文。它像一本优秀的小说,把所有事情的来龙去脉介绍的清清楚楚,对于任何有一点计算机和自然语言处理知识的人,都可以轻而易举地读懂他复杂的方法。

柯林斯毕业后,在 AT&T 实验室度过了三年快乐的时光。在那里柯林斯完成了许多世界一流的研究工作诸如隐含马尔科夫模型的区别性训练方法,卷积核在自然语言处理中的应用等等。三年后,AT&T 停止了自然语言处理方面的研究,柯林斯幸运地在 MIT 找到了教职。在 MIT 的短短几年间,柯林斯多次在国际会议上获得最佳论文奖。相比其他同行,这种成就是独一无二的。柯林斯的特点就是把事情做到极致。如果说有人喜欢“繁琐哲学”,柯林斯就是一个。


布莱尔:简单才美

在研究方法上,站在柯林斯对立面的典型是他的师兄艾里克 · 布莱尔 (Eric Brill) 和雅让斯基,后者我们已经介绍过了,这里就不再重复。与柯林斯从工业界到学术界相反,布莱尔职业路径是从学术界走到工业界。与柯里斯的研究方法相反,布莱尔总是试图寻找简单得不能再简单的方法。布莱尔的成名作是基于变换规则的机器学习方法 (transformation rule based machine learning)。这个方法名称虽然很复杂,其实非常简单。我们以拼音转换字为例来说明它:

第一步,我们把每个拼音对应的汉字中最常见的找出来作为第一遍变换的结果,当然结果有不少错误。比如,“常识”可能被转换成“长识”;

第二步,可以说是“去伪存真”,我们用计算机根据上下文,列举所有的同音字替换的规则,比如,如果 chang 被标识成“长”,但是后面的汉字是“识”,则将“长”改成“常”;

第三步,应该就是“去粗取精”,将所有的规则用到事先标识好的语料中,挑出有用的,删掉无用的。然后重复二三步,直到找不到有用的为止。

布莱尔就靠这么简单的方法,在很多自然语言研究领域,得到了几乎最好的结果。由于他的方法再简单不过了,许许多多的人都跟着学。布莱尔可以算是我在美国的第一个业师,我们俩就用这么简单的方法作词性标注 (part of speech tagging),也就是把句子中的词标成名词动词,很多年内无人能超越。(最后超越我们的是后来加入 Google 的一名荷兰工程师,用的是同样的方法,但是做得细致很多)布莱尔离开学术界后去了微软研究院。在那里的第一年,他一人一年完成的工作比组里其他所有人许多年做的工作的总和还多。后来,布莱尔又加入了一个新的组,依然是高产科学家。据说,他的工作真正被微软重视要感谢 Google,因为有了 Google,微软才对他从人力物力上给于了巨大的支持,使得布莱尔成为微软搜索研究的领军人物之一。在研究方面,布莱尔有时不一定能马上找到应该怎么做,但是能马上否定掉一种不可能的方案。这和他追求简单的研究方法有关,他能在短时间内大致摸清每种方法的好坏。

由于布莱尔总是找简单有效的方法,而又从不隐瞒自己的方法,所以他总是很容易被包括作者我自己在内的很多人赶上和超过。好在布莱尔很喜欢别人追赶他,因为,当人们在一个研究方向超过他时,他已经调转船头驶向它方了。一次,艾里克对我说,有一件事我永远追不上他,那就是他比我先有了第二个孩子 :)

在接下来了系列里,我们还会介绍一个繁与简结合的例子。

数学之美 十四 谈谈数学模型的重要性

,

发表者:吴军,Google 研究员

[注:一直关注数学之美系列的读者可能已经发现,我们对任何问题总是在找相应的准确的数学模型。为了说明模型的重要性,今年七月份我在 Google 中国内部讲课时用了整整一堂课来讲这个问题,下面的内容是我讲座的摘要。]

在包括哥白尼、伽利略和牛顿在内的所有天文学家中,我最佩服的是地心说的提出者托勒密。虽然天文学起源于古埃及,并且在古巴比伦时,人们就观测到了五大行星(金、木、水、火、土)运行的轨迹,以及行星在近日点运动比远日点快。(下图是在地球上看到的金星的轨迹,看过达芬奇密码的读者知道金星大约每四年在天上画一个五角星。)

但是真正创立了天文学,并且计算出诸多天体运行轨迹的是两千年前古罗马时代的托勒密。虽然今天我们可能会嘲笑托勒密犯的简单的错误,但是真正了解托勒密贡献的人都会对他肃然起敬。托勒密发明了球坐标,定义了包括赤道和零度经线在内的经纬线,他提出了黄道,还发明了弧度制。

当然,他最大也是最有争议的发明是地心说。虽然我们知道地球是围绕太阳运动的,但是在当时,从人们的观测出发,很容易得到地球是宇宙中心的结论。从地球上看,行星的运动轨迹是不规则的,托勒密的伟大之处是用四十个小圆套大圆的方法,精确地计算出了所有行星运动的轨迹。(托勒密继承了毕达格拉斯的一些思想,他也认为圆是最完美的几何图形。)托勒密模型的精度之高,让以后所有的科学家惊叹不已。即使今天,我们在计算机的帮助下,也很难解出四十个套在一起的圆的方程。每每想到这里,我都由衷地佩服托勒密。一千五百年来,人们根据他的计算决定农时。但是,经过了一千五百年,托勒密对太阳运动的累积误差,还是差出了一星期。

地心说的示意图,我国天文学家张衡的浑天地动说其实就是地心说。

纠正地心说错误不是靠在托勒密四十个圆的模型上再多套上几个圆,而是进一步探索真理。哥白尼发现,如果以太阳为中心来描述星体的运行,只需要 8-10 个圆,就能计算出一个行星的运动轨迹,他提出了日心说。很遗憾的事,哥白尼正确的假设并没有得到比托勒密更好的结果,哥白尼的模型的误差比托勒密地要大不少。这是教会和当时人们认为哥白尼的学说是邪说的一个原因,所以日心说要想让人心服口服地接受,就得更准确地描述行星运动。

完成这一使命的是开普勒。开普勒在所有一流的天文学家中,资质较差,一生中犯了无数低级的错误。但是他有两条别人没有的东西,从他的老师第谷手中继承的大量的、在当时最精确的观测数据,以及运气。开普勒很幸运地发现了行星围绕太阳运转的轨道实际是椭圆形的,这样不需要用多个小圆套大圆,而只要用一个椭圆就能将星体运动规律描述清楚了。只是开普勒的知识和水平不足以解释为什么行星的轨道是椭圆形的。最后是伟大的科学家牛顿用万有引力解释了这个问题。

故事到这里似乎可以结束了。但是,许多年后,又有了个小的波澜。天文学家们发现,天王星的实际轨迹和用椭圆模型算出来的不太符合。当然,偷懒的办法是接着用小圆套大圆的方法修正,但是一些严肃的科学家在努力寻找真正的原因。英国的亚当斯和法国的维内尔(Verrier)独立地发现了吸引天王星偏离轨道的海王星。

讲座结束前,我和 Google 中国的工程师们一同总结了这么几个结论:
1. 一个正确的数学模型应当在形式上是简单的。(托勒密的模型显然太复杂。)
2. 一个正确的模型在它开始的时候可能还不如一个精雕细琢过的错误的模型来的准确,但是,如果我们认定大方向是对的,就应该坚持下去。(日心说开始并没有地心说准确。)
3. 大量准确的数据对研发很重要。
4. 正确的模型也可能受噪音干扰,而显得不准确;这时我们不应该用一种凑合的修正方法来弥补它,而是要找到噪音的根源,这也许能通往重大发现。

在网络搜索的研发中,我们在前面提到的单文本词频/逆文本频率指数(TF/IDF) 和网页排名(page rank)都相当于是网络搜索中的“椭圆模型”,它们都很简单易懂。

昨天那个英语单词自动匹配的修正版本

, ,

对程序进行了修正,原来无法查找单词eh的bug被消除(原因是算法里有个bug,已经修正)修正了单个字母无法匹配的bug。这里要感谢我的同学彭侃,是他在软件的使用中发现了这两个bug,以使程序和算法更完善。
修正版本的下载:EngWordMatch.rar
August 2008
SMTWTFS
July 2008September 2008
12
3456789
10111213141516
17181920212223
24252627282930