2006年09月19日

一、BSTR、LPSTR和LPWSTR
   在Visual C++.NET的所有编程方式中,我们常常要用到这样的一些基本字符串类型,如BSTR、LPSTR和LPWSTR等。之所以出现类似上述的这些数据类型,是因为不同编程语言之间的数据交换以及对ANSI、Unicode和多字节字符集(MBCS)的支持。

  那么什么是BSTR、LPSTR以及LPWSTR呢?

  BSTR(Basic STRing,Basic字符串)是一个OLECHAR*类型的Unicode字符串。它被描述成一个与自动化相兼容的类型。由于操作系统提供相应的API函数(如SysAllocString)来管理它以及一些默认的调度代码,因此BSTR实际上就是一个COM字符串,但它却在自动化技术以外的多种场合下得到广泛使用。图1描述了BSTR的结构,其中DWORD值是字符串中实际所占用的字节数,且它的值是字符串中Unicode字符的两倍。

  LPSTR和LPWSTR是Win32和VC++所使用的一种字符串数据类型。LPSTR被定义成是一个指向以NULL(‘\0’)结尾的8位ANSI字符数组指针,而LPWSTR是一个指向以NULL结尾的16位双字节字符数组指针。在VC++中,还有类似的字符串类型,如LPTSTR、LPCTSTR等,它们的含义如图2所示。

  例如,LPCTSTR是指“long pointer to a constant generic string”,表示“一个指向一般字符串常量的长指针类型”,与C/C++的const char*相映射,而LPTSTR映射为 char*。

  一般地,还有下列类型定义:

#ifdef UNICODE
  typedef LPWSTR LPTSTR;
  typedef LPCWSTR LPCTSTR;
#else
  typedef LPSTR LPTSTR;
  typedef LPCSTR LPCTSTR;
#endif

二、CString、CStringA 和 CStringW

  Visual C++.NET中将CStringT作为ATL和MFC的共享的“一般”字符串类,它有CString、CStringA和CStringW三种形式,分别操作不同字符类型的字符串。这些字符类型是TCHAR、char和wchar_t。TCHAR在Unicode平台中等同于WCHAR(16位Unicode字符),在ANSI中等价于char。wchar_t通常定义为unsigned short。由于CString在MFC应用程序中经常用到,这里不再重复。

三、VARIANT、COleVariant 和_variant_t

  在OLE、ActiveX和COM中,VARIANT数据类型提供了一种非常有效的机制,由于它既包含了数据本身,也包含了数据的类型,因而它可以实现各种不同的自动化数据的传输。下面让我们来看看OAIDL.H文件中VARIANT定义的一个简化版:

struct tagVARIANT {
  VARTYPE vt;
  union {
   short iVal; // VT_I2.
   long lVal; // VT_I4.
   float fltVal; // VT_R4.
   double dblVal; // VT_R8.
   DATE date; // VT_DATE.
   BSTR bstrVal; // VT_BSTR.
   …
   short * piVal; // VT_BYREF|VT_I2.
   long * plVal; // VT_BYREF|VT_I4.
   float * pfltVal; // VT_BYREF|VT_R4.
   double * pdblVal; // VT_BYREF|VT_R8.
   DATE * pdate; // VT_BYREF|VT_DATE.
   BSTR * pbstrVal; // VT_BYREF|VT_BSTR.
  };
};

  显然,VARIANT类型是一个C结构,它包含了一个类型成员vt、一些保留字节以及一个大的union类型。例如,如果vt为VT_I2,那么我们可以从iVal中读出VARIANT的值。同样,当给一个VARIANT变量赋值时,也要先指明其类型。例如:

VARIANT va;
:: VariantInit(&va); // 初始化
int a = 2002;
va.vt = VT_I4; // 指明long数据类型
va.lVal = a; // 赋值

  为了方便处理VARIANT类型的变量,Windows还提供了这样一些非常有用的函数:

  VariantInit —— 将变量初始化为VT_EMPTY;

  VariantClear —— 消除并初始化VARIANT;

  VariantChangeType —— 改变VARIANT的类型;

  VariantCopy —— 释放与目标VARIANT相连的内存并复制源VARIANT。

  COleVariant类是对VARIANT结构的封装。它的构造函数具有极为强大大的功能,当对象构造时首先调用VariantInit进行初始化,然后根据参数中的标准类型调用相应的构造函数,并使用VariantCopy进行转换赋值操作,当VARIANT对象不在有效范围时,它的析构函数就会被自动调用,由于析构函数调用了VariantClear,因而相应的内存就会被自动清除。除此之外,COleVariant的赋值操作符在与VARIANT类型转换中为我们提供极大的方便。例如下面的代码:

COleVariant v1("This is a test"); // 直接构造
COleVariant v2 = "This is a test";
// 结果是VT_BSTR类型,值为"This is a test"
COleVariant v3((long)2002);
COleVariant v4 = (long)2002;
// 结果是VT_I4类型,值为2002

  _variant_t是一个用于COM的VARIANT类,它的功能与COleVariant相似。不过在Visual C++.NET的MFC应用程序中使用时需要在代码文件前面添加下列两句:

  #i nclude "comutil.h"

  #pragma comment( lib, "comsupp.lib" )

四、CComBSTR和_bstr_t

  CComBSTR是对BSTR数据类型封装的一个ATL类,它的操作比较方便。例如:

CComBSTR bstr1;
bstr1 = "Bye"; // 直接赋值
OLECHAR* str = OLESTR("ta ta"); // 长度为5的宽字符
CComBSTR bstr2(wcslen(str)); // 定义长度为5
wcscpy(bstr2.m_str, str); // 将宽字符串复制到BSTR中
CComBSTR bstr3(5, OLESTR("Hello World"));
CComBSTR bstr4(5, "Hello World");
CComBSTR bstr5(OLESTR("Hey there"));
CComBSTR bstr6("Hey there");
CComBSTR bstr7(bstr6);
// 构造时复制,内容为"Hey there"

  _bstr_t是是C++对BSTR的封装,它的构造和析构函数分别调用SysAllocString和SysFreeString函数,其他操作是借用BSTR API函数。与_variant_t相似,使用时也要添加comutil.h和comsupp.lib。

五、BSTR、char*和CString转换

  (1) char*转换成CString

  若将char*转换成CString,除了直接赋值外,还可使用CString::Format进行。例如:

char chArray[] = "This is a test";
char * p = "This is a test";

  或

LPSTR p = "This is a test";

  或在已定义Unicode应的用程序中

TCHAR * p = _T("This is a test");

  或

LPTSTR p = _T("This is a test");
CString theString = chArray;
theString.Format(_T("%s"), chArray);
theString = p;

  (2) CString转换成char*

  若将CString类转换成char*(LPSTR)类型,常常使用下列三种方法:

  方法一,使用强制转换。例如:

CString theString( "This is a test" );
LPTSTR lpsz =(LPTSTR)(LPCTSTR)theString;

  方法二,使用strcpy。例如:

CString theString( "This is a test" );
LPTSTR lpsz = new TCHAR[theString.GetLength()+1];
_tcscpy(lpsz, theString);

  需要说明的是,strcpy(或可移值Unicode/MBCS的_tcscpy)的第二个参数是 const wchar_t* (Unicode)或const char* (ANSI),系统编译器将会自动对其进行转换。

  方法三,使用CString::GetBuffer。例如:

CString s(_T("This is a test "));
LPTSTR p = s.GetBuffer();
// 在这里添加使用p的代码
if(p != NULL) *p = _T(‘\0′);
s.ReleaseBuffer();
// 使用完后及时释放,以便能使用其它的CString成员函数

  (3) BSTR转换成char*

  方法一,使用ConvertBSTRToString。例如:

#i nclude
#pragma comment(lib, "comsupp.lib")
int _tmain(int argc, _TCHAR* argv[]){
BSTR bstrText = ::SysAllocString(L"Test");
char* lpszText2 = _com_util::ConvertBSTRToString(bstrText);
SysFreeString(bstrText); // 用完释放
delete[] lpszText2;
return 0;
}

  方法二,使用_bstr_t的赋值运算符重载。例如:

_bstr_t b = bstrText;
char* lpszText2 = b;

  (4) char*转换成BSTR

  方法一,使用SysAllocString等API函数。例如:

BSTR bstrText = ::SysAllocString(L"Test");
BSTR bstrText = ::SysAllocStringLen(L"Test",4);
BSTR bstrText = ::SysAllocStringByteLen("Test",4);

  方法二,使用COleVariant或_variant_t。例如:

//COleVariant strVar("This is a test");
_variant_t strVar("This is a test");
BSTR bstrText = strVar.bstrVal;

  方法三,使用_bstr_t,这是一种最简单的方法。例如:

BSTR bstrText = _bstr_t("This is a test");

  方法四,使用CComBSTR。例如:

BSTR bstrText = CComBSTR("This is a test");

  或

CComBSTR bstr("This is a test");
BSTR bstrText = bstr.m_str;

  方法五,使用ConvertStringToBSTR。例如:

char* lpszText = "Test";
BSTR bstrText = _com_util::ConvertStringToBSTR(lpszText);

  (5) CString转换成BSTR

  通常是通过使用CStringT::AllocSysString来实现。例如:

CString str("This is a test");
BSTR bstrText = str.AllocSysString();

SysFreeString(bstrText); // 用完释放

  (6) BSTR转换成CString

  一般可按下列方法进行:

BSTR bstrText = ::SysAllocString(L"Test");
CStringA str;
str.Empty();
str = bstrText;

  或

CStringA str(bstrText);

  (7) ANSI、Unicode和宽字符之间的转换

  方法一,使用MultiByteToWideChar将ANSI字符转换成Unicode字符,使用WideCharToMultiByte将Unicode字符转换成ANSI字符。

  方法二,使用“_T”将ANSI转换成“一般”类型字符串,使用“L”将ANSI转换成Unicode,而在托管C++环境中还可使用S将ANSI字符串转换成String*对象。例如:

TCHAR tstr[] = _T("this is a test");
wchar_t wszStr[] = L"This is a test";
String* str = S”This is a test”;

  方法三,使用ATL 7.0的转换宏和类。ATL7.0在原有3.0基础上完善和增加了许多字符串转换宏以及提供相应的类,它具有如图3所示的统一形式:

  其中,第一个C表示“类”,以便于ATL 3.0宏相区别,第二个C表示常量,2表示“to”,EX表示要开辟一定大小的缓冲。SourceType和DestinationType可以是A、T、W和OLE,其含义分别是ANSI、Unicode、“一般”类型和OLE字符串。例如,CA2CT就是将ANSI转换成一般类型的字符串常量。下面是一些示例代码:

LPTSTR tstr= CA2TEX<16>("this is a test");
LPCTSTR tcstr= CA2CT("this is a test");
wchar_t wszStr[] = L"This is a test";
char* chstr = CW2A(wszStr);

2006年09月07日

-道德的起源- 
   
  把五只猴子关在一个笼子里,上头有一串香蕉实验人员装了一个自动装置。 
  一旦侦测到有猴子要去拿香蕉,马上就会有水喷向笼子,而这五只猴子都会一身湿。 
  首先有只猴子想去拿香蕉,当然,结果就是每只猴子都淋湿了。 
  之後每只猴子在几次的尝试后,发现莫不如此。 
  于是猴子们达到一个共识:不要去拿香蕉,以避免被水喷到。 
  后来实验人员把其中的一只猴子释放,换进去一只新猴子A。 
  这只猴子A看到香蕉,马上想要去拿。 
  结果,被其他四只猴子海K了一顿。 
  因为其他四只猴子认为猴子A会害他们被水淋到,所以制止他去拿香蕉,A尝试了几次,虽被打的满头包,依然没有拿到香蕉。 
  当然,这五只猴子就没有被水喷到。 
   
  后来实验人员再把一只旧猴子释放,换上另外一只新猴子B。 
  这猴子B看到香蕉,也是迫不及待要去拿。 
  当然,一如刚才所发生的情形,其他四只猴子海K了B一顿。 
  特别的是,那只A猴子打的特别用力(这叫老兵欺负新兵,或是媳妇熬成婆^O^)。 
  B猴子试了几次总是被打的很惨,只好作罢。 
   
  后来慢慢的一只一只的,所有的旧猴子都换成新猴子了,大家都不敢去动那香蕉。 
  但是他们都不知道为什么,只知道去动香蕉会被猴扁。 
   
  这就是道德的起源。 
   
  -阶级的起源- 
   
  实验人员继续他们的实验,不过这一次他们改变了喷水装置。 
  一旦侦测到有猴子要去拿香蕉,马上就会有水喷向拿香蕉的猴子,而不是全体。 
  然后实验人员又把其中的一只猴子释放,换进去一只新猴子C。 
  不同以往的是猴子C特别的孔武有力。 
  当然猴子C看到香蕉,也马上想要去拿。 
  一如以前所发生的情形,其他四只猴子也想海K猴子C一顿。 
  不过他们错误估计了C的实力,所以结果是反被C海K了一顿。 
  于是猴子C拿到了香蕉,当然也被淋了个透湿。 
  C一边打着喷嚏一边吃着香蕉,美味但是也美中不足。 
  A、B、D、E没有香蕉吃却也比较快乐,毕竟没有被淋到嘛。 
  后来C发现只有拿香蕉的那个才会被淋到,他就要最弱小的A替他去拿。 
  A不想被K,只好每天拿香蕉然后被水淋。 
  B、D、E越发的快乐了起来,这就叫比上不足,比下有余嘛 
   
  于是五只猴子有了三个阶级。 
  这下子阶级也随着道德起源了。 
   
  -道德的沦丧- 
   
  天变热了,笼子里的猴子们想冲凉却找不到地方。终于出现了一位反潮流英雄,猴子HERO。HERO在无意中碰到了香蕉,理所当然的引来了一顿饱打。但在挨打的过程中,猴子们享受到了冲凉的乐趣。等身上的水干了之后,猴子A在无意中碰撞了HERO,使HERO又一次接触到了香蕉,于是,猴子们享受了第二次冲凉,HERO遭到了第二次痛殴。 
   
  在此之后,只要大家有冲凉的需要,就会有一只猴子X挺身而出,对HERO进行合理冲撞。 
   
  大家对HERO的态度也有了明显的不同,在平时大家会对HERO异常温和,以弥补在冲凉时为维护规则而不得不对它进行的暴力举动。 
   
  一天,在大家冲凉时,饱受折磨的HERO闻到了香蕉的清香,生物本能使它在别的猴子心有旁鹜时将香蕉吃了。而且此后没有了新的香蕉来填补空缺。猴子们陷入了另一个尴尬境地:没有冲凉的水,也没有香蕉,只有HERO。 
   
  于是,另一个规则形成了。猴子在烦躁的时候会痛打HERO出气,HERO不得反抗。 
  当笼子里的旧猴子被新猴子换掉时,新猴子会在最快的时间内学会殴打HERO。 
   
  终于有一天,老天有眼,历尽沧桑的HERO被另一只猴子代替了。猴子们失去了发泄的对象,只能任意选取一个目标进行攻击。从此以后,笼子里的猴子们不吃不喝不冲凉,唯一的举动就是打架。 
   
  这就是道德的沦丧。 
   
  -道德的重建- 
   
  实验人员对猴子们的争斗不休感到不安。为了重建道德秩序,他们决定继续供应香蕉。 
   
  一天,正在混战的猴子们发现头顶多了一串香蕉,它们其中的一个A不顾身上的剧痛,把香蕉摘了下来。于是久违的甘露出现了,未曾尝过甜头的猴子们先是茫然失措,继而争先恐后的加入冲凉的行列。香蕉反而被遗忘了。当猴子B、C、D、E发现A在享受淋浴的同时还吃着美味的香蕉,嫉妒心使它们暂时团结起来,共同K了A一顿,将A吃剩的香蕉夺过来,但是,此刻的香蕉成了匹夫怀里的宝玉,得到它的猴子虽然可以享受美味,但付出的代价也是巨大的。 
   
  实验人员不断放入香蕉,却发现战斗比以前更激烈了。分析清楚原因后,他们用木头做了一个假香蕉扔进了笼子。此时猴子们已经学聪明了,它们知道触摸香蕉可以享淋浴,而试图独占香蕉则会遭到痛扁。于是,一个新的现象出现了,当猴子们有冲凉的需要时,会有一只猴子将香蕉拿起来,而当它发现有遭到攻击的可能时,它会马上放下香蕉逃到一边去。这样,猴子们都能冲凉,但是又不至于再象以前那样N败俱伤。 
   
  没有猴子发现那个香蕉是假的。 
   
  -信仰的起源- 
   
  五只猴子A、B、C、D、E三个阶级快乐地生活了很久。 
  他们精确的给出了三个阶级的定义,即吃香阶级、拿香阶级和干看着阶级。 
  可惜猴子A由于长期的水中作业无可避免地引发了它肺部功能的衰竭。 
  一天他在例行的拿香蕉作业中跌倒了就再也没有爬起来。 
  于是实验人员又送进了一只同样孔武有力的猴F。 
  当然他还是对屋顶的香蕉很有兴趣。 
  不幸的是他最终以微弱的劣势被以C为首的群猴再次海K。 
  第二天,又到了拿香蕉的时候。 
  猴子C很无所谓,反正他还要吃香蕉,反正他不会被水淋到。 
  真正恐慌的是B、D、E三猴。 
  F是那么的健壮,他们这些媳妇是熬不成婆了 
  他们将面临一个艰难的抉择,谁该去步A的后尘? 
  猴子B、D、E展开了激烈的争论,讨论谁最应该做下一个拿香阶级。 
  猴子F很奇怪也很好奇,什么叫“拿香阶级”呢? 
  猴子B、D、E解释道:所谓“拿香阶级”就是猴子界勇敢者的阶级。 
  需具备一不怕苦二不怕死的大无畏精神方能得此殊荣。 
  猴子F闻听不禁有些神往,有些跃跃欲试。 
  当然他最终达到了目的,作了唯一的拿香阶级。 
  再后来,B、D、E三猴陆续被换出局,换来的猴子个个健壮如C。 
  他们继续大大出手,不过目标不是香蕉,而是那个唯一的拿香阶级。 
   
  于是信仰也出现了 
   
  -迷信的起源- 
   
  后来A终于被好心的实验人员拉出了苦海。 
   
  新来了猴子F。 
   
  C觉得有必要维护自己的阶级地位,B、D、E则生怕自己顶了A的缸……在各种复杂心情的作用下,B、D、E在C的带领下爆扁了F一顿,然后强令F做拿香蕉阶级。 
   
  F开始不乐意,后来慢慢在B等的劝说下等“待多年的媳妇熬成婆”这一宿命。 
   
  慢慢的老资格的B、D、E猴子渐渐被淘汰,C发现自己在体力上不再占有优势,很难再通过武力让这一游戏规则继续下去,觉得十分苦恼。 
   
  这时,一只最有希望升级为吃香蕉阶级(暨C的理所当然接班人)也是C谋臣的H向C进言。于是君臣定计。 
   
  H开始依靠自己多懂几种猴语而在其他若干猴面前树立的权威形象向其他猴鼓吹:“每一只新来笼子的猴子都是有罪的,这种罪责来自血统。……只有摘香蕉的猴子才能被(实验人员)送到天堂。” 
   
  事实上,因为被水冲很容易得肺炎病倒而被实验人员淘汰掉,猴子们不知道反而以为被淘汰的猴子真的进了天堂。 
   
  渐渐,猴子都相信了这套理论,并且讲给每一只新猴子听。 
   
  然后就这么流传下去越传越神奇。以至于后来摘香蕉阶级的猴子都为了能摘香蕉而大打出手。…… 
   
  这些都是C没有想到,H没有看到的,那时他们都已经死了。 
   
  然而迷信就这么诞生了。

Google 的秘密- PageRank 彻底解说 中文版

原著:Google の秘密 – PageRank 徹底解説 Hajime BABA / 馬場 肇   
翻译:Kreny / 袁 黄琳 <krenyATdalouis.com>
创作于:2003/12   最后更新: 2004年10月28日 3:53  关键词:pagerank, google, link
翻译说明: 一些语句的翻译上使用了意译,使得尽可能得符合中文的理解和说明思路。
版权声明:可以任意转载,转载时请务必以超链接形式标明文章原始出处和作者信息及本声明
http://www.kreny.com/pagerank_cn.htm

返回首页


本文对作为评价甚高的搜索引擎 Google 的核心技术之一 PageRank (网页等级)的基本的概念和评价原理进行解释。

索引

  1. 前言
  2. PageRank 的基本概念
  3. 怎样求得 PageRank
  4. 实际应用时的问题
  5. Namazu 上的实际安装实验
  6. 对 PageRank 的个人见解
  7. 参考文献
  8. 附录:「guguru?/gouguru?

★(2003/7/1) 拙著『Namazu系统的构筑和活用』已作修订。 详情请看 介绍页面

★(2003/5/20) 与 Google 有关的在线新闻报道一览(日语)已被分离到 另一张页面(googlenews.html)

★(2001/2/28) Namazu 的索引中使用的计算 PageRank 的 Perl 脚本 prnmz-1.0.tar.gz 公开下载。

1.前言

最近,搜索引擎 Google (http://www.google.com/)非常引人注目。Google 是基于现担任 CEO 的 Larry Page 和担任总经理的 Sergey Brin (2001年2月)在就读于美斯坦福大学研究生院时所开发的搜索引擎的一种检索服务。Google 从1998年9月开始服务,但 Netscape Communications 在 Google 的测试阶段就开始与其合作,美国 Yahoo! 公司也从2000年6月起将默认搜索引擎(美国 Yahoo! 不能检索时作为增补的搜索引擎)由原先合作的 Inktomi 转换为了 Google。日语版 Google 在2000年9月正式登场,现已被 BIGLOBE(NEC)所采用。 (注:2001年4月 Yahoo! JAPAN 和 @NIFTY,7月索尼,2002年1月 Excite 也相继与 Google 建立了协作关系)。

Google 被评价的优点不仅仅在于去除无用的(广告)标语构成单一页面的功能、独自的 Cache 系统、动态制成摘要信息、为实现高速检索而设置的分散系统(数千台规模的Linux群集器)等,而其中最大的优点正是它检索结果的正确性。一种能够自动判断网页重要性的技术「PageRank是(网页等级)」就是为此而设计的一种技术。 本文的目的就是以尽可能浅显易懂的语言来说明 PageRank 系统的概要和原理。

以下是 PageRank 的一篇基础文章。

Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd, ‘The PageRank Citation Ranking: Bringing Order to the Web’, 1998,
http://www-db.stanford.edu/~backrub/pageranksub.ps

为了更高效地计算 PageRank,以下是改良以后的一篇论文。

Taher H. Haveliwala, ‘Efficient Computation of PageRank’, Stanford Technical Report, 1999,
http://dbpubs.stanford.edu:8090/pub/1999-31

另外,以下是 PageRank 的演示用资料(PowerPoint)。

Larry Page, ‘PageRank: Bringing Order to the Web’,
http://hci.stanford.edu/~page/papers/pagerank/ (已失效)

接下来就对这两篇文章(另加一篇资料)进行基本说明。 首先,用简单的例子来解说 PageRank 的概念,再归结到使用超链接关系的排序系统来解决大规模疏松疏矩阵的特性值的问题。然后我们会接触一些在现实世界中应用基本模型时出现的问题和对应方法。接下来,为了探讨是否能够作为「个人化 PageRank」使用,进行对免费全文检索系统 Namazu 的安装实验并对其结果进行阐述。最后发表我对 PageRank 的个人见解。

另外,为了能够理解以下的说明内容,需要大学基础课程程度的数学知识(尤其是线形代数)。然而为使文科生也能够顺利读下去,尽可能地不用算式来说明问题,同时,为了加入笔者个人的见解,没有加入像原文那么多的算法和数字,也存在许多不够严密和欠正确的地方,事先在次声明。具体内容请参照原文。

PageRank(TM) 是美国 Google 公司的登记注册商标。

2. PageRank 的基本概念

PageRank 是基于「从许多优质的网页链接过来的网页,必定还是优质网页」的回归关系,来判定所有网页的重要性。

在以下冗长的说明中,许多部分大量地使用了专业用语,会造成理解上的困难。这一章虽然准备集中于定性而简单的解说,但是,即使如此也会有怎么也不明白的时候,此时只要能够理解「从许多优质的网页链接过来的网页,必定还是优质网页」这一思考方法也就非常得可贵了。因为在所有几个要点中,这个是最重要的思考方法。

来自于 Google 自己的介绍「Google的受欢迎的秘密(http://www.google.co.jp/intl/ja/why_use.html)」 是象以下一样解说的。

关于PageRank
    PageRank,有效地利用了 Web 所拥有的庞大链接构造的特性。 从网页A导向网页B的链接被看作是对页面A对页面B的支持投票,Google根据这个投票数来判断页面的重要性。可是 Google 不单单只看投票数(即链接数),对投票的页面也进行分析。「重要性」高的页面所投的票的评价会更高,因为接受这个投票页面会被理解为「重要的物品」。
    根据这样的分析,得到了高评价的重要页面会被给予较高的 Page Rank(网页等级),在检索结果内的名次也会提高。PageRank 是 Google 中表示网页重要性的综合性指标,而且不会受到各种检索(引擎)的影响。倒不如说,PageRank 就是基于对"使用复杂的算法而得到的链接构造"的分析,从而得出的各网页本身的特性。
    当然,重要性高的页面如果和检索词句没有关联同样也没有任何意义。为此 Google 使用了精练后的文本匹配技术,使得能够检索出重要而且正确的页面。

通过下面的图我们来具体地看一下刚才所阐述的算法。具体的算法是,将某个页面的 PageRank 除以存在于这个页面的正向链接,由此得到的值分别和正向链接所指向的页面的 PageRank 相加,即得到了被链接的页面的 PageRank。

PageRank 的概念图
PageRank 概念图。(引自 Page et al.(1998) Figure 2 ‘Simplified Page Calculation’)

让我们详细地看一下。提高 PageRank 的要点,大致有3个。

  • 反向链接数 (单纯的意义上的受欢迎度指标)
  • 反向链接是否来自推荐度高的页面 (有根据的受欢迎指标)
  • 反向链接源页面的链接数 (被选中的几率指标)

首先最基本的是,被许多页面链接会使得推荐度提高。也就是说「(被许多页面链接的)受欢迎的页面,必定是优质的页面」。所以以反向链接数作为受欢迎度的一个指标是很自然的想法。这是因为,“链接”是一种被看作「可以看看这个页面/这个页会有用」的推荐行为。但是,值得骄傲的是 PageRank 的思考方法并没有停留在这个地方。

也就是说,不仅仅是通过反向链接数的多少,还给推荐度较高页面的反向链接以较高的评价。同时,对来自总链接数少页面的链接给予较高的评价,而来自总链接数多的页面的链接给予较低的评价。 换句话说「(汇集着许多推荐的)好的页面所推荐的页面,必定也是同样好的页面」和「与感觉在被胡乱链接的链接相比,被少数挑选出的链接肯定是优质的链接」这两种判断同时进行着。一方面,来自他人高水平网页的正规链接将会被明确重视,另一方面,来自张贴有完全没有关联性的类似于书签的网页的链接会作为「几乎没有什么价值(虽然比起不被链接来说好一些)」而被轻视。

因此,如果从类似于 Yahoo! 那样的 PageRank 非常高的站点被链接的话,仅此网页的 PageRank 也会一下子上升;相反地,无论有多少反向链接数,如果全都是从那些没有多大意义的页面链接过来的话,PageRank 也不会轻易上升。不仅是 Yahoo!, 在某个领域中可以被称为是有权威的(或者说固定的)页面来的反向链接是非常有益的。但是,只是一个劲地在自己一些同伴之间制作的链接,比如像「单纯的内部照顾」这样的做法很难看出有什么价值。也就是说,从注目于全世界所有网页的视点来判断(你的网页)是否真正具有价值。

综合性地分析这些指标,最终形成了将评价较高的页面显示在检索结果的相对靠前处的搜索结构。

以往的做法只是单纯地使用反向链接数来评价页面的重要性,但 PageRank 所采用方式的优点是能够不受机械生成的链接的影响。 也就是说,为了提高 PageRank 需要有优质页面的反向链接。 譬如如果委托 Yahoo! 登陆自己的网站,就会使得 PageRank 骤然上升。但是为此必须致力于制作(网页的)充实的内容。这样一来,就使得基本上没有提高 PageRank 的近路(或后门)。不只限于PageRank (Clever 和 HITS 等也同样),在利用链接构造的排序系统中,以前单纯的 SPAM 手法将不再通用。这是最大的一个优点,也是 Google 方便于使用的最大理由。(虽然是最大的理由,但并不是唯一的理由。)

在这里请注意,PageRank 自身是由 Google 定量,而与用户检索内容的表达式完全无关。就像后边即将阐述的一样,检索语句不会呈现在 PageRank 自己的计算式上。不管得到多少的检索语句,PageRank 也是一定的、文件固有的评分量。

PageRank 的定性说明大致就是这样一些。但是,为了实际计算排列次序、比较等级,需要更定量性的讨论。以下一章将做详细的说明。

3.怎样求得 PageRank

我们感兴趣的是,在有像超级链接构造那样的互相参照关系的时候,定量地知道哪一个页面是最「重要」的。换句话大胆地说,这个也就是严密计算「应该从哪一页开始读取」这个指标的过程。就算从谁都不看的小页面开始读取也没有办法。

那么,一般地说为了使得像 Web 那样的超级链接构造能够反映在在排列次序上,需要在计算机上建立超级链接构造的数字模型。 怎么模型化需要取决于安装者的方针所以一概而论,但是如果应用图表理论来观察超级链接构造的话,最终常常回到线形代数考虑方法上去。这对于 PageRank 也是一样的。

计算方法的原理

作为最基本的考虑方法,就是用行列阵的形式来表达链接关系。从页面 i 链接到另一张页面 j 的时,将其成分定义为1,反之则定义为 0 。即,行列阵 A 的成分 aij 可以用,

  aij=1 if  (从页面 i 向页面 j 「 有 」 链接的情况)
      0 if  (从页面 i 向页面 j 「没有」链接的情况) 

来表示。文件数用 N 来表示的话,这个行列阵就成为 N×N 的方阵。这个相当于在图表理论中的「邻接行列」。也就是说,Web 的链接关系可以看做是采用了邻接关系有向图表 S。总而言之,只要建立了链接,就应该有邻接关系。

(*注)由点和点连接的线构成的图形被称为「图表(graph)」。这些点被称为「顶点(vertex)」或者「节点(node)」;这些线被称为「边(edge)」或者「弧(arc)」。图表分为两类,“边”没有方向的图表被称为「无向图表(undirected graph)」,“边”带有方向的图表被称为「有向图表(directed graph)」。把有向图表想像成单向通行的道路就可以了。 图表能用各种的方法来表示,但一般用在数据结构上的是「邻接行列(adjacency matrix)」和「邻接列表(adjacency list)」。需要注意的是,如果是无向图表,邻接行列 A 就成为了对称行列,而如果是有向图表,A 就会成为不对称行列。

以下是用位图表示的 Apache 的在线手册(共128页)的邻接行列。当黑点呈横向排列时,表示这个页面有很多正向链接(即向外导出的链接);反之,当黑店呈纵向排列时,表示这个页面有很多反向链接

邻接行列的例子
邻接行列的例子(采用了Apache 的在线手册)

PageRank 的行列阵是把这个邻接行列倒置后(行和列互换),为了将各列(column)矢量的总和变成 1 (全概率), 把各个列矢量除以各自的链接数(非零要素数)。这样作成的行列被称为「推移概率行列」,含有 N 个概率变量,各个行矢量表示状态之间的推移概率。倒置的理由是,PageRank 并非重视「链接到多少地方」而是重视「被多少地方链接」。

PageRank 的计算,就是求属于这个推移概率行列最大特性值的固有矢量(优固有矢量)。

这是因为,当线性变换系 t→∞ 渐近时,我们能够根据变换行列的"绝对价值最大的特性值"和"属于它的固有矢量"将其从根本上记述下来。换句话说,用推移概率行列表示的概率过程,是反复对这个行列进行乘法运算的一个过程,并且能够计算出前方状态的概率。

再者,虽然听起来很难,但是求特性值和固有矢量的值是能够严密分析的一种基础的数学手段。我们能够自由地给矢量的初始值赋值,但是因为不断地将行列相乘,得到的矢量却会集中在一些特定数值的组合中。我们把那些稳定的数值的组合称为固有矢量,把固有矢量中特征性的标量(scalar)称为特性值,把这样的计算方法总称为分解特性值,把解特性值的问题称为特性值问题

(*注) 对 N 次的正方行列 A 把满足 Ax =λx 的数 λ 称为 A 的特性值,称 x 为属于 λ 的固有矢量。如果你怎么也不能适应行列的概念的话,你也可以考虑 N×N 的二元排列就可以了。同时,也可以把矢量考虑成为长度为 N 的普通的(一元)排列就可以了。

简单的例子

让我们用简单的例子来试着逐次计算 PageRank 。首先考虑一下有像下图表示那样的链接关系的7个HTML文件。并且,这些HTML文件间的链接关系只是闭合于这1-7的文件中。也就是说,除了这些文档以外没有其他任何链接的出入。另外请注意,所有的页面都有正向和反向链接(即没有终点),这也是后面将提出的一个重要假定,在此暂且不深入探讨。

链接关系的推移图
表示页面间互相链接关系的推移图

首先,把这张推移图图表构造的邻接列表表示为排列式,就有以下式子。即,根据各个链接源ID列举链接目标的ID。

链接源I D 	链接目标 ID
1		2,3 ,4,5, 7
2		1
3		1,2
4		2,3,5
5 		1,3,4,6
6		1,5
7		5

以这个邻接列表中所表示的链接关系的邻接行列 A 是以下这样的 7×7 的正方行列。一个仅有要素 0 和 1 位图行列(bitmap matrix)。横向查看第 i 行表示从文件 i 正向链接的文件ID。

A = [
	 0, 1, 1, 1, 1, 0, 1;
	 1, 0, 0, 0, 0, 0, 0;
	 1, 1, 0, 0, 0, 0, 0;
	 0, 1, 1, 0, 1, 0, 0;
	 1, 0, 1, 1, 0, 1, 0;
	 1, 0, 0, 0, 1, 0, 0;
	 0, 0, 0, 0, 1, 0, 0;
 ]

PageRank 式的推移概率行列 M ,是将 A 倒置后将各个数值除以各自的非零要素后得到的。即以下这个 7×7 的正方行列。横向查看第 i 行非零要素表示有指向文件 i 链接的文件ID(文件 i 的反向链接源)。请注意,各纵列的值相加的和为 1(全概率)。

M = [
	0, 	1,	1/2,	0,	1/4,	1/2,	0;
	1/5,	0,	1/2,	1/3,	0,	0,	0;
	1/5,	0,	0,	1/3,	1/4,	0,	0;
	1/5,	0,	0,	0,	1/4,	0,	0;
	1/5,	0,	0,	1/3,	0,	1/2,	1;
	0,	0,	0,	0,	1/4,	0,	0;
	1/5,	0,	0,	0,	0,	0,	0;
]

表示 PageRank 的矢量 R (各个的页面的等级数的队列),存在着 R = cMR 的关系(c 为定量)。在这种情况下,R 相当于线形代数中的固有矢量,c 相当于对应特性值的倒数。为了求得 R ,只要对这个正方行列 M 作特性值分解就可以了。

在分解特性值时有相应的各种各样的数值分析法,但是本文将不在这里对各种方法详细说明,请读者自己去阅读一本恰当的教科书(在你的暑假里一定有这么一本被埋没的教科书)。在此,我们就暂且使用决 GNU Octave 这个计算程序实际计算一下特性值和固有矢量。

(*注) GNU Octave ,是支持数值计算,类似于描述性出色的 MATLAB 的编程语言。扩展后的处理语言更适合于行列演算,但基本上和C语言的语风相像,因此可读性很高。详细请参照 http://www.octave.org/。 当然,除了Octave以外 MATLABScilab 也是非常不错的语言,但是根据 GPL, Octave 是最容易得到的。

实际举例

下面我们举一个实际例子。如果不太明白以下例子在做什么的话,只要认为我们能够使用 Octave 这个程序来解特性值问题即可。

首先,使用恰当的编辑器制作以下 Octave 脚本。(在行尾加上分号就能消去多余的结果输出,不过,此次为了说明特意去掉了。)

% cat pagerank.m
#!/usr/bin/octave
## pagerank.m - 计算 PageRank(TM) 用的简单的 GNU Octave 脚本

##设置计时器。
tic(); 

## 根据PageRank 的定义,将从文件 i 链接到文件 j 的链接状态的推移概率行列定义为 M(i,j)

M = [
	0,	1,	1/2,	0,	1/4,	1/2 ,	0;
	1/5,	0,	1/2,	1/3,	0,	0,	0;
	1/5,	0,	0,	1/3,	1/4,	0,	0;
	1/5,	0,	0,	0,	1/4,	0,	0;
	1/5,	0,	0,	1/3,	0,	1/2,	1;
	0,	0,	0,	0,	1/4,	0,	0;
	1/5,	0,	0,	0,	0,	0,	0;
]
##计算 全部 M 的特性值和固有矢量列的组合。

[V,D]= eig(M)

## 保存与绝对价值最大的特性值对应的固有矢量到EigenVector。

 EigenVector = V(:, find(abs(diag(D))==max(abs(diag(D))))) 

## PageRank 是将 EigenVector 在概率矢量上标准化后得到的值。
 PageRank = EigenVector./ norm(EigenVector,1) 

## 输出计算时间。
elapsed_time = toc()

(2003/7/23: 修正上述脚本的错误。)

误: EigenVector = V(:, find(max(abs(diag(D))))  )
正: EigenVector = V(:, find(abs(diag(D))== max(abs(diag(D))))) 

用 Octave 运行这个 pagerank.m 脚本后在标准输出中得到以下结果。

% octave pagerank.m
GNU Octave, version 2.0.16 (i586-redhat-linux-gnu).
Copyright (C) 1996, 1997, 1998, 1999, 2000 John W. Eaton.
This is free software with ABSOLUTELY NO WARRANTY.
For details, type `warranty'. 

M =

0.00000 1.00000 0.50000 0.00000 0.25000 0.50000 0.00000
0.20000 0.00000 0.50000 0.33333 0.00000 0.00000 0.00000
0.20000 0.00000 0.00000 0.33333 0.25000 0.00000 0.00000
0.20000 0.00000 0.00000 0.00000 0.25000 0.00000 0.00000
0.20000 0.00000 0.00000 0.33333 0.00000 0.50000 1.00000
0.00000 0.00000 0.00000 0.00000 0.25000 0.00000 0.00000
0.20000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 

V =

Columns 1 through 3: 

0.69946 + 0.00000i 0.63140 + 0.00000i 0.63140 + 0.00000i
0.38286 + 0.00000i -0.28715 + 0.15402i -0.28715 - 0.15402i
0.32396 + 0.00000i -0.07422 - 0.10512i -0.07422 + 0.10512i
0.24297 + 0.00000i 0.00707 - 0.24933i 0.00707 + 0.24933i
0.41231 + 0.00000i -0.28417 + 0.44976i -0.28417 - 0.44976i
0.10308 + 0.00000i 0.22951 - 0.13211i 0.22951+ 0.13211i
0.13989 + 0.00000i -0.22243 - 0.11722i -0.22243 + 0.11722i 

Columns 4 through 6: 

0.56600 + 0.00000i 0.56600 + 0.00000i -0.32958 + 0.00000i
0.26420 - 0.05040i 0.26420 + 0.05040i 0.14584 + 0.00000i
-0.10267 + 0.14787i -0.10267- 0.14787i 0.24608 + 0.00000i
-0.11643 + 0.02319i -0.11643 - 0.02319i -0.24398+ 0.00000i
-0.49468 - 0.14385i -0.49468 + 0.14385i 0.42562 + 0.00000i
-0.14749+ 0.38066i -0.14749 - 0.38066i -0.64118 + 0.00000i
0.03106 - 0.35747i 0.03106+ 0.35747i 0.39720 + 0.00000i 

Column 7: 

0.00000 + 0.00000i
-0.40825 + 0.00000i
-0.00000 + 0.00000i
0.00000 + 0.00000i
-0.00000 + 0.00000i
0.81650 + 0.00000i
-0.40825 + 0.00000i 

D = 

Columns 1 through 3: 

1.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i
0.00000 + 0.00000i -0.44433 + 0.23415i 0.00000 + 0.00000i
0.00000 + 0.00000i 0.00000 + 0.00000i -0.44433 - 0.23415i
0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i
0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i
0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i
0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 

Columns 4 through 6: 

0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i
0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i
0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i
0.02731 + 0.31430i 0.00000 + 0.00000i 0.00000 + 0.00000i
0.00000 + 0.00000i 0.02731 - 0.31430i 0.00000 + 0.00000i
0.00000 + 0.00000i 0.00000 + 0.00000i -0.16595 + 0.00000i
0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 

Column 7: 

0.00000 + 0.00000i
0.00000 + 0.00000i
0.00000 + 0.00000i
0.00000 + 0.00000i
0.00000 + 0.00000i
0.00000 + 0.00000i
-0.00000 + 0.00000i 

EigenVector =
0.69946
0.38286
0.32396
0.24297
0.41231
0.10308
0.13989 

PageRank =
0.303514
0.166134
0.140575
0.105431
0.178914
0.044728
0.060703 

elapsed_time = 0.063995

Octave 的输出中,特性值被表示为对角行列 D 的对角成分,各个特性值相对应的固有矢量被表示为行列 V 对应列的列矢量。也就是说 M * V = D * M 成立。 如果包含复数特性值的话这里的特性值有7个,其中绝对价值最大的特性值 λ 是λ=1。与之相对应的固有矢量为实矢量:

EigenVector =
	0.69946
	0.38286
	0.32396
	0.24297
	0.41231
	0.10308
	0.13989

即行列 V 的第1列。请注意,这个求得的固有矢量中概率矢量(要素的和等于1的 N 次元非负矢量)没有被标准化,只是矢量的「大小」等于 1。 用算式来表达就是,Σpi ≠1 ,Σ(pi)2=1。 在这里,对概率矢量进行标准化

PageRank =
	0.303514
	0.166134
	0.140575
	0.105431
	0.178914
	0.044728
	0.060703

PageRank 就是排位了。 注意,全部相加的和为 1。 计算只用了0.064秒。

求得的 PageRank 的评价

将 PageRank 的评价按顺序排列 (PageRank 小数点3位四舍五入)。

名次 PageRank   文件ID    发出链接ID  被链接ID
  1     0.304     1       2,3,4,5,7   2,3,5,6
  2     0.179     5       1,3,4,6     1,4,6,7
  3     0.166     2       1           1,3,4
  4     0.141     3       1,2         1,4,5
  5     0.105     4       2,3,5       1,5
  6     0.061     7       5           1
  7     0.045     6       1,5         5

首先应该关注的是,PageRank 的名次和反向链接的数目是基本一致的。无论链接多少正向链接都几乎不会影响 PageRank,相反地有多少反向链接却是从根本上决定 PageRank 的大小。但是,仅仅这些并不能说明第1位和第2位之间的显著差别(同样地、第3位和第4位,第6位和第7位之间的差别)。总之,绝妙之处在于 PageRank 并不只是通过反向链接数来决定的。

让我们详细地看一下。ID=1 的文件的 PageRank 是0.304,占据全体的三分之一,成为了第1位。特别需要说明的是,起到相当大效果的是从排在第3位的 ID=2 页面中得到了所有的 PageRank(0.166)数。ID=2页面有从3个地方过来的反向链接,而只有面向 ID=1页面的一个链接,因此(面向ID=1页面的)链接就得到了所有的 PageRank 数。不过,就因为 ID=1页面是正向链接反向链接最多的页面,也可以理解它是最受欢迎的页面吧。

反过来,最后一名的 ID=6 页面只有 ID=1 的15%的微弱评价,这可以理解为是因为没有来自 PageRank 很高的 ID=1 的链接而使其有很大地影响。 总之,即使有同样的反向链接的数目,链接源页面评价的高低也影响 PageRank 的高低。

链接关系的推移图(PageRank)
表示页面互相的链接关系的推移图(加入了PageRank)

实际地试着计算一下PageRank的收支。因为λ=1所以计算很简单,只要将自各页的流入量单纯相加即可。譬如 ID=1 的流入量为,

流入量=(ID=2发出的Rank)+(ID=3发出的Rank)+(ID=5发出的Rank)+(ID=6发出的Rank)
    = 0.166+0.141/2+0.179/4+0.045/2
    = 0.30375

在误差范围内PageRank的收支相符合。其他页面ID的情况也一样。以上的 PageRank 推移图正表示了这个收支。沿着各自的链接发出的PageRank等于此页面原有的PageRank除以发出链接数的值,而且和各自的页面的PageRank收支相平衡。

不过,这样绝妙均衡的本身,对理解线形代数的人来说当然不会是让人惊讶的事情。因为这正是「特性值和固有矢量的性质」,总之这样被选的数值的组就是固有矢量。但即使是这样,实际试着确认一下的话,已经能够很好地使用PageRank的方法来考虑了。

以上就是 PageRank 的基本原理。 Google 做的就是大规模地处理这样的非常特性值问题。

4.实际应用时的问题

PageRank 的基本考虑方法并不是很难的东西。实用效果中的巨大成分并不是复杂离奇的算法,而是进行简单的线性变换,倒不如都属于简明直观的类别吧。但是,实际使用 Web 超级链接构造来计算 PageRank 的话,不是简单地能够用嘴巴来说明的东西。主要的困难主要有二个。一、由来于纯粹假设的数值模型和现实世界的不同;二,在实际数值计算上(专门技术的)困难。

准备:数学用语(主要概率过程)的解说

推移概率行列和概率过程上的马尔可夫过程存在很深的关系。本章先离开与 PageRank 本身的说明,预先说明几个呈现在概率过程上的数学用语。因为会设计相当难的部分,如果不能够理解也可以跳过这里。(也可能是我的说明方法不好) 同时,请注意这里几乎没有证明就直接使用了。详细的解说请阅读教科书。

从有向图表S的状态 i 出发,将有限时间之后再次回复到状态 i 的概率作为 1 时,也就是说,当沿着(有向)图表的方向前进能够回到原来位置的路径存在的时候,i 就被成为「回归」。不能回归的状态被称为「非回归」。从状态 i 出发,当通过有限次数的推移达到状态 j 的概率非负的时候,我们就说「从状态 i 到达状态 j 是可能的」。当反方向也可能到达的时候,我们称「i 和 j 互相可能到达」。从状态 i 不能到达其他任何状态的时候,称 i 为「吸收状态」。

从邻接行列 A 所决定的图表(graph)的任意顶点出发,指向其他任意的顶点图表的路径能够像箭头那样到达时被称为「强联结」( 也被称为「分解不能」)。强联结,等价于从任意状态到任意状态可以互相到达。邻接行列 A 的成分中有很多 0 时,强联结性就会有问题。注意,如果全部成分都为 aij ≠0 的话,则都属于强联结。因为,对应的 马尔可夫链的样本路径表示 S 的任意两点间以正的概率来往通行。

我们可以把全体状态以等价类(或者回归类)来划分。在这里,回归类是指链接所围成的范围。属于一个等价类的状态可以互相到达。从一个类出发以正的概率进入到其他的类的可能性也是存在的。可是很明显,在这种情况下不可能回复到原来的类。不然的话,这两个类就归于等价类了。下图表示了,当 T 作为非回归性的等价类、R 作为回归性等价类时,虽然存在 马尔可夫链 既不来自回归类,也不来自非回归类的情况,但如果一旦来自前两者的话,就不再会回到非回归类中了。

重归?非重归的图
回归、非回归示意图(修改了小谷(1997)的图11.1)

这个等价关系中只有一个回归类的时候,那个 马尔可夫链就被称为「最简」。换句话说,全部的状态之间互相可以到达时就被称为最简。最简时都是强联结。

互相完全没有关联的邻接行列(或推移概率行列),乘以恰当的置换行列(掉换行和列)以后得到

P = | P1 0 |
    | 0 P2 |

这样的关系。这表示回归类 P1 和 P2 间完全不存在直接的链接关系。

回归类、非回归类掺杂在一起的邻接行列(或推移概率行列),乘以恰当的置换行列后得到,

P = | P1 0 |
    | Q P2 |

这样的关系(Q≠0)。此时,P1是非回归类,P2是回归类。

推移概率行列有时也被称作马尔可夫行列。称马尔可夫过程的试验行列的观测结果为马尔可夫链(Markov chain)。 当经过相当的时间后马尔可夫链会趋向某种平衡状态。对任意的状态 i, 如果 j 是非回归状态,则 Pij(n)→0。相反,当 i 为非回归、j 为回归时,停留在状态 i 上着的概率是0。如果 i,j 属于同样的非周期性回归类的话,Pij(n)→Pj≥0。

定理:若 P 是有限马尔可夫行列的话,P 的特性值 1 的重复度等于 P 决定的回归类的数目。(证明太长,省略)。

跟随着推移概率行列的有向图表的最大强联结成分(与之对应的状态的集合)被称为Ergodic部分(历遍部分),此外的强联结成分被称为消散部分。因为无论从怎样的初期状态概率 x(0)开始,经过时间 n 后 x(n) = P(n)x(0),所以属于消散部分的状态概率几乎接近于0。关于EllGoth部分,连同与各联结成分对应状态的类、像独立的最简的马尔可夫链一样行动,其中,各类中的状态概率(即从过去开始的平均值)的值和初期状态概率无关,换言之,是近似于与对应 P 的最简成分的固有矢量成比例的东西。在类之间概率的分配依存于初期状态的概率。

离散时间型马尔可夫链的不变分布是属于极限分布,从那个分布开始已经不是在分布意义上的随时间的变化了。状态的概率分布在时间变化时也不会变化时被称为固定分布。PageRank 用马尔可夫过程来说就是,PageRank就是以一定时间内用户随机地沿着(网页)链接前进时对各个页面访问的固定分布

假想模型和现实世界的不同

那么,让我们将概率过程(即图表原理)的考虑方法和实际的网页链接构造合起来看一看。

对于刚才举例的假想网页群来说,只要相互顺着链接前进则在彼此页面间必定有相互链接的关系。即,有向图表是强联结的行列既是回归又是最简。像上面举的很多的概率过程的教科书一样,许多证明都是把回归和最简作为前提来证明的,如果是最简的话,各种各样的性质就变得容易说了。

但是现实的网页并不是强联结。也就是说邻接行列不是最简的。具体来说,顺着链接前进的话,有时会走到完全没有向外链接的网页。通常这样的情况,只有利用 web 浏览器的「返回」功能了。如果人们只是浏览而已的话,一切就到此结束了,然而 PageRank 的计算却不能到此结束。因为PageRank 一旦被引入以后是不能返回的。Pagerank 称这种页面为为「dangling page」。同样道理,只有向外的链接而没有反向链接的页面也是存在的。但 Pagerank 并不考虑这样的页面,因为没有流入的 PageRank 而只流出的 PageRank,从对称性来考虑的话必定是很奇怪的。

同时,有时候也有链接只在一个集合内部旋转而不向外界链接的现象。这是非周期性的回归类多重存在时可能出现的问题。(请读者考虑一下陷入上图中一个 R 中而不能移动到别的 R 和 T 的情况)。 Pagerank 称之为「rank sink」。在现实中的页面,无论怎样顺着链接前进,仅仅顺着链接是绝对不能进入的页面群总归存在,也就是说,这些页面群是从互相没有关联的多数的同值类(回归类)形成的。

总之,由现实的 Web 页组成的推移概率行列大部分都不是最简的。当不是最简时,最大特性值(即1)是重复的,并且不能避免优固有矢量多数存在的问题。换句话说,PageRank 并不是从一个意义上来决定的。

在此,Pagerank 为了解决这样的问题,考虑了一种「用户虽然在许多场合都顺着当前页面中的链接前进,但时常会跳跃到完全无关的页面里」,这样的浏览模型。再者,将「时常」固定为 15% 来计算。用户在 85% 的情况下沿着链接前进,但在 15% 的情况下会突然跳跃到无关的页面中去。(注:Pagerank 的原始手法是各自87%(=1/1.15 )和13%(=0.15/1.15)。)

将此用算式来表示的话得到以下公式。

M’= c*M +(1-c)*[1/N]

其中,[1/N]是所有要素为 1/N 的 N次正方行列,c =0.85(=1-0.15)。M’当然也同样是推移概率行列了。也就是说,根据 Pagerank 的变形,原先求行列 M 的特性值问题变成了求行列 M’的优固有矢量特性值问题。M 是固定无记忆信息源(i.i.d.)时,M’被称为「混合信息源」,这也就是固定但非ellGoth信息源的典型例子。

如果从数学角度看,「把非最简的推移行列最简化」操作的另外一种说法就是「把不是强联结的图表变成强联结」的变换操作。所谓对全部的要素都考虑0.15的迁移概率,就是意味着将原本非最简的推移概率行列转换为最简并回归的(当然非负的情况也存在)推移概率行列。针对原本的推移概率行列,进行这样的变换操作的话,就能从一个意义上定义 PageRank、也就是说能保证最大特性值的重复度为1。如果考虑了这样的变换操作的话,因为推移概率行列的回归类的数目变成 1 的同时也最简化,根据前面的定理,优固有矢量(即 PageRank)就被从一个意义上定义了。

数值计算上的问题点(其1)

在此,只要大概明白 PageRank 的概念就可以了,不需要很深的陷入数值计算上的技术的问题中(其实,笔者自己即使有自信也说不清楚)。但是,因为特性值分析和联立一次方程式分析一样,是利用在各种的统计分析中重要的数值计算手法的一中,所以这里我们简单的触及一些分析方法。

主记忆领域的问题是在数值计算上的问题之一。

假设 N 是 104 的 order。通常,数值计算程序内部行列和矢量是用双精度记录的,N 次正方行列 A 的记忆领域为 sizeof(double)* N * N =8 *104 * 104=800MB。 800MB 的主记忆领域不是那种经常会拥有的东西, 虽然这么说也非那种不可能的数字。但是,N 如果变成 105 或106 的话,各自就变成80GB,8TB。这样的话不用说内存就连硬盘也已经很困难了。 Google 从处理着10亿以上的页面(2001年时)以来,就知道这种规矩的做法已经完全不适用了。

不过,A 只是稀疏(sparse)行列。因为即使有一部分的页面拼命地进行链接,但是向整个Web展开链接的页面是没有的,即使有也是极为稀少的。平均一下,每一张页面有10-20个左右的链接(根据 IBM Almaden 研究所’Graph structure in the web‘ 的统计,平均在16.1个左右)。因此,我们可以采用恰当的压缩方法来压缩 A 。 N 即使是 106 时,如果平均链接数是10,最终的记忆领域只要 80MB,从规模上来说可以收纳到合理的数字里。

稀疏行列的容纳方式当今已经被充分地研究(有限要素法的解法等),在恰当的数值计算的专业书中就可以学到。虽然这么说,因为相当地难解还是需要很复杂的手法。但想指出的是如果可以很好的解决的话,并列化的高速计算(也许)就变得可能了。因为比起怎样排列并容纳非零要素来说,计算性能和并列性能对其的影响会更大。

数值计算上的问题点(其2)

另一个是收敛问题。

固定方程式

xi=ΣAijxi

是 N 元的联立一次方程式,一般地不能得到分析解,所以只能解其数值。刚才举的例子中为了求特性值和固有矢量,使用了 Octave 的 eig()函数, 不过,这个在问题小的时候不能适用。说起来,并不需要计算全部的特性值/固有矢量。

求最大特性值和属于它的固有矢量(优固有矢量)的数值计算手法中,一般使用「幂乘法」(也叫反复法)。这是指,取适当初期矢量 x0 ,当 x(n+1) = A y(n) (其中 y(n) = x(n) / c(n) )中的 n →∞ 时,x 向拥有最大特性值的固有矢量收敛的同时 c 向此最大特性值收敛的利用线形代数性质的计算方法(证明请参照线形代数的教科书)。幂乘法(反复法)的特长与逐次反复计算的近似法比,能够改善解矢量的问题。它的优点是,因为只要反复对行列和矢量进行适当次数的乘法运算,所以只要通过程序就能够简单地解决,并且还可以进行由于受到内存和硬盘的限制通过直接法不能解决的大规模分析。这是许多的实用算法的出发点。

在这里,请注意从线形代数的简单定理(Peron-Frobenius定理)得到推移概率行列的绝对价值的最大特性值是1。如果采用了这个,就会使得反复法的 PageRank 的计算变得更容易。即,因为最大特性值是既知的,比起求满足 Ax=x 的矢量 x来说 ,变成更加简单的问题了。这虽然是很细小的地方但是很重要。首先,可以去掉比较花费成本的除法计算 (y(n)=x(n)/c(n))不用完成。如果是反复法的话,不能得到很高的精确度,并且如果搞错了加速方法的话,计算出的不是是最大特性值而是第二大特性值和属于它的固有矢量(虽然这种情况很少,但是说不定就是从根本上错误的值)。但如果知道了最大特性值,就可以进行核对了。在 Pagerank 的第一篇论文中他们似乎没有注意到这个事情,但在 Haveliwala 的第二论文中增加了关于此的修正。

反复的次数取决于想要求的精度。也就是说,想要求的精度越高,反复的次数就越多。可是,幂乘法(反复法)的误差的收敛比与系数行列的谱段特性(特性值的绝对值分布)有很强的依存关系。具体地说,绝对值最大的特性值用λ1表示,第二位用 λ2 表示,优越率(收敛率 probability of dominance)为 d =λ12 话,可以知道d离1越近收敛就变得越慢。在 N 很大的情况时d当然离1很近。这是因为,绝对值最大的特性值是1,而其他所有的 N-1 个特性值的绝对值都比1小。但是,N-1个特性值之间非常的拥挤,所以λ1和λ2 之间几乎没有差别。因此一般来说,收敛会变慢。

所谓收敛变慢,严密地说,就是无论经过多少时间也完成不了的计算。对此,为了使收敛加快的适当的加速方法也是存在的,应用这些方法时,需要对数值计算技术有十二分的理解,因此如果不是数值计算的专家就很难引入。

5. Namazu 上的实际安装实验

为了使更简单地推测上文描述的问题,PageRank 并不是非世界所有的web页面而不能使用的考虑方法,即使是个人的利用方法也能实现。为了实现「Personalized PageRank」,针对在各种 UNIX 和 Windows 上运作的中小规模网站适用的全文检索系统 Namazu 进行了实际安装实验。(关于Namazu可参考 日语全文检索引擎软件列表。)

由于实验能简单地控制内存的使用量,并将最大特性值用1来考虑,所以将 Have liwala(1999)的想法做为基本的考虑方法。但是对 dangling pages 的处理有少许不同。固有矢量的计算内核使用了数值计算脚本 GNU Octave。所以基本的代码编写自己只用了一天就解决了。另外,从用 mknmz 编写的索引不能直接计算 PageRank,而要事前准备表示邻接关系的索引(邻接列表)。这个也有可能被编入检索者(Indexer)的主要部分。

以下表示了实际计算时间(单位:秒)。运行机器的配置为 PentiumII 400MHz x 2,内存512MB,Kondara MNU/Linux 1.2的(kernel-2.2 .17-15ksmp),Octave-2.0.16(一般状态分发物)。收敛精度(剩余差矢量的L1规范)取了到1.0e-10,也许有些过分精确了。

文书数N     mknmz时间    准备时间   PageRank计算时间
============================================================
128          58          2          6
2,301       1, 575       46         214
49,604      15,975       478        5,872

因为没用一些巨大的web页群来做测试,所以实验只停留在小规模的基础上。虽然有这个难点,但从基本上可以了解与索引所花的时间相比,在很短的时间里就可以计算 PageRank 的倾向吧。

因为 Namazu 自身中也有很多难题,所以并不寄予很大的奢望,但至少使用 105 程度(尽可能 106)规模的web页面群来实验。从趋势来看可以预想 N=106 的计算时间恐怕会发散开去,所以在 N=106 时,若是能够讨论把mknmz时间变成和comparable一样的加速方法的话,对于Personalized PageRank 来说就十分实用了。作为参考,根据Page et al.(1998),Google 对7500万的URL的实际 PageRank 计算时间约是5小时。(2001年2月现在不明)。从这个角度来说,研究更加高效的加速法的余地就十分得必要了吧。

计算实际运行时的使用内存最大也是10几MB左右。如果是Haveliwala (1999)那样的「吝啬地作战」的话,最大只有O(3N+2)左右的内存使用量就做完了,不过 N 是 104-5 程度和内存的使用量连 N2 也放不进的话,其他的也只能勉强调谐了,所以以 O(5N+α) (α是疏松行列的非零成分数字,典型的是5-20N左右) 程度来编写代码。另外 N 是103 左右时,可以确认不压缩疏松行列就在内存上使用幂乘法来计算,从速度面上来说是非常有利的。实测时速度为上述数字的6-7倍左右的。但遗憾的是,这个方法从内存的限制来看,尽可能地只使用2-3千页以内。

此次我们使用了 Octave 分发附属的「Tsurushi」,不过,正像大家知道的那样,如果把 Octave 调谐的好的话,会戏剧性地提高完成的速度。Octave-2.1.x 和 ATLAS 的组合有时候根据情况甚至会使大规模行列乘法的运算速度提高10倍以上。

实验的详细结果请参照prnmz-1.0.tar.gz 中的文档。

Personalized PageRank 的基本性质

人们经常会利用 MHonArc、latex2html 或者 PowerPoint 这样的工具将文档变成 HTML,针对这样的人工制作的HTML链接群求 PageRank 的话,大部分页面的得分几乎都是一样的(~1/N)。如果考虑邻接行列,则大部分的成分是1,或者对角成分附近全部是1。因为这样的推移概率行列的固有矢量成为(1,1,…,1)。

或是象 sitemap.html 一样变成树状的情况下,分数会集中在sitemap.html中。就算占据全体的9成也不算新奇。

从现在起能说的是,为了计算有意义的 PageRank,要尽可能地排除机械生成的链接关系。如果把链接关系看做是推荐关系的话更加容易认同了吧。

6.对 PageRank 的个人的见解

(读者)应该没有余地去怀疑象 PageRank 那样利用超级链接来决定排列次序有效手法吧。

不过,阅读了这些论文以后笔者自身也考虑了许多问题。在这里,列举几个对 PageRank 的个人见解。虽是见解,说到底就是方法论,也许会有很多错误的地方。

  • 关于 dangling page,不相反考虑的原因是什么?

只是因为考虑一定的变异概率时「偶然」会变成最简才不予考虑吗?还是有时看漏了什么吗?稍微有点不太明白。

  • 改善推移概率行列的可能性

    说起来,为了保证 PageRank 的单一意义的性质(一意),只要保证推移概率行列是最简(有向图表是强联结)就行了,没有必要所有的要素 aij 都是非零要素。事实上,像在web上浏览 Toyota 汽车网站后紧接着跳向色情网站,接着又继续跳到白宫网站浏览的怪异的人应该是不存在的吧。(请注意这里是指在随时间变化连续的形式)。因此,从实用的意义上来说,区别于改善多少的使用方便程度,应该留下对算法改良的余地。

  • 考虑「逗留概率」会怎样

根据 PageRank 的考虑方法,在一定的时间后必定顺着链接前进到其他的页面,或者突然怪异的、歪曲的跳到其他页面。但是如果对照现实的web浏览模型,也要考虑一定的逗留概率。具体地说,就是推移概率行列的对角成分中只取( 1-c)/N 的话取得过小了。在原本所有变迁概率都一定的情况下,更加进一步分析会怎样?因为对于无聊的页面(浏览者)必定会想都不想就转到另外的页面,反过来对于重要的页面却会停留较长的时间。

  • 如果考虑概率论应用的话必定会考虑其他许多问题

即使是将实现性置之度外,我们也再来试着进一步考虑这个想法。概率论中,存在着一种叫消灭概率或叫固定概率的概率。比起 PageRank 的单纯而同样考虑方法,导入这种考虑方法会得到更期望的结果,所以理所当然被大家所期待。大家都知道马尔可夫链中的分枝过程的考虑方法。这是考虑遗传基因突变时的一个模型,即,说明经过一定的时间而产生淘汰的可能性的模型。很多人认为这个考虑方法或许会被采用。那么导入带有限制的概率(禁忌概率)又会怎么样呢? 即,相当于导入通过 n 次的推移从状态 i 移动到状态 j 时,不经过状态 k 的概率。如果考虑到web浏览的性质的话,不是也能理所当然地成为假定吗?

  • 不能作为非马尔可夫过程(或者说 m次的多重马尔可夫过程)来考虑吗

所谓马尔可夫过程,就是与过去的经历无关,只从现在的状态来确定未来的概率法则的概率过程。 马尔可夫过程只依存于1步之前的过程。这个过程和没有对过去的记忆,没有依存于过去经历的要素。 PageRank 是在单纯马尔可夫过程随时间变化而固定的状态下计算时候所求得的结果。但是,人类的理性行动必须以非马尔可夫过程来表现。复杂的过程总是以一些形式和过去有着牵连。因此,不仅仅单一地分析从哪个页面连接来,而要分析沿着怎样的路径连接而来的。这样的分析才会使其有可能成为更有用的排序系统。在能抑制住计算量爆炸的范围内,试着引入非马尔可夫过程来研究说不定也很有趣。

在考虑到和看到的许许多多中,有像实际安装那样不太难的东西,也有因为只是嘴上说说而不知道怎样实际安装的东西,不管怎样,定量地评价它的效果是极为困难的。难道真的是不能实现的东西吗?

PageRank 的技术有多少

即使只是采用评价很高的 PageRank 技术,作为基本的想法也只是使用了枯竭的数值分析的手法来实现的。但是,象我在这里说明的事情,如果从专业的研究者来看完全是理所当然的事情了。只是克服规模这一点就能建立一个专业的研究领域吧。 也可以认为专业领域的内部并没有那么深的尽头。事实上,我做事,充其量只是表示了「如果是极其小规模的问题,即使是教科书的手法也能大约地得到满足计算量的结果」。

尽管是这样,充其量只触及了概要的表面就在嘴边说「没什么嘛,原来是程度这么简单的技术呀」 的那种不懂装懂的人也是有的。在这里事先强调:这种浅薄的看法是从根本上完全错误的

当然,PageRank 技巧的非常好的地方是「从许多优质的页面连接过来的页面是还是优质的页面」,如果明白了就会觉得是简单的想法。但更进一步说,真正绝妙的地方是,不仅仅只是想到一个主意,而是将想法用固定状态变迁的概率分布来定式化,为了实证其有效性而实际地进行安装实验,并证明其在现实领域也能很好地运作的过程。在所有的这些阶段都成功了才是真正值得被称赞的。

的确,不仅有斩新而且巧妙的想法,再加上结合教科书的手法,也有可能制造出能和 Google 匹敌(或是凌驾)的搜索引擎。也可以说实际上 Google 自己也在这么做着。但是,实际完成的人却是少得惊人。假想模型中的「肯定能够完成」的东西和实际运作的东西之间有着天差地别。在实际问题上,处理大规模疏松行列本身,通过一般的手法也是相当的困难,需要高度的专业技术。应该铭记在头脑中总觉得能够理解的事和实现中能够做的事之间绝对会有不能填埋的差距。不可过分轻率地考虑。

7.参考文献

以下列举了除了在「前言」中介绍的基本论文以外的关联论文。(译者去掉了许多无用的连接)

以下列举数学关联的参考书籍。

  • S.卡琳 著,佐藤健一,佐藤由身子译,『概率过程讲义』(数理分析与周边3),1974年,产业图书
  • 岩堀信子著,『图表和概率过程』 (与数理分析与周边4),1974年,产业图书
  • 伊藤升 他著,『经济系、工学系的行列及应用』, 1987年,纪伊国屋书店, ISBN4-314-00477-0
  • L.V.Atokinson, P.J.哈里, J.D.赫德森 共著,神谷纪生,大野信忠,佐胁丰,北荣辅 合译,『数值计算及其应用- FORTRAN77-』, 1993年,Science公司,ISBN4-7819-0690-7
  • 宫泽政清著,『概率和概率过程』(现代数学研究小组17),1993年,近代科学社, ISBN4-7649-1034-9
  • 伊理正夫著,『线形代数II』(岩波讲座应用数学11) ,1994年,岩波书店, ISBN4-00-010521-3
  • 韩太舜,小林欣吾著,『信息和符号化数理』(岩波讲座应用数学13) ,1994年,岩波书店, ISBN4-00-010523-X
  • 小国力著,『MATLAB及其实际利用-现代应用数学和CG -』( Information & Computing=86),1995年,Science公司, ISBN4-7819-0763-6
  • 长谷川里美,长谷川秀彦,藤野清次译,『反复法 Templates』(应用数值计算Library),1996年,朝仓书店, ISBN4-254-11401-X
  • 小谷真一著,『测每次和概率2』(岩波讲座现代数学基础10 ),1997年,岩波书店, ISBN4-00-010640-6
  • 藤野清次著,『数值计算之基础-以数值解法做为中心』(Library新信息工程之基础9),1998年,Science公司,ISBN4-7819-0861-6

与有关 Google 的在线新闻报道(日语新闻)已经分离到其另一张页面(googlenews.html) 。(2003/5/20)

其他,特别列出几个认为有关联的页面。

感谢转载!其他许多的个人站点和BBS都介绍了此文。

8.附录:「guguru?/ goguru?」

英语(美式英语)中是不可能把 Google 念成「goguru」的。 和没有人拉面的 noodle 发音或标记为「nodoru」一样,如果硬要用片假名来表示的话应该写成「グーグル」。

不过,有oo 这个拼写的英文单词有以下这些。

book, bool, cook, cool, food, good, hook, look, loop, loose, mood, moon, noon, pool, roof, soon, tool, wood, zoo, …

这些都是简单的一般的英文单词,但不论取哪个都有「u:」这个发音。至少,对许多的典型的日本人来说听起来是这样的吧。英语(美式英语),oo 的拼写基本读成「u」。当然,goo就读成「gu:」。 广末凉子不也在中古车信息杂志的电视广告中说「如果要说车,gu―」吗?另外,游泳时使用游泳眼镜的拼写是 goggle。

当然,如果 Google 不是英语(美式英语)话那就另当别论了。但是,Google 名字的由来是从表示10的100次方的英文单词「googol」而来的,也许还是英语发音比较适合(google)吧。不用说,googol 的发音也是「guguru」吧。

另外,创业者之一是 Sergey Brin,从他的名字就能明白他是俄罗斯出身,也有可能是他的英语发音带有自己的方言。如果扯到那里的话,已经是牵强附会了。而且,我也不太清楚Google 用俄罗斯的地方口音怎么发音。如果有识之士在的话,请一定告诉我。

补充(2001/4): 给Google的支持中心发了「是goguru,还是guguru?」的询问信的一位读者,热情地给我转发了这封邮件。对方说虽然 Google 自己本身的发音是「guguru」,不过,你以你自己喜欢的叫法称呼也决不会介意的哦。

Date: Wed,31 Jan 200116:12:01-0800
From:”GoogleTech”<googletech@google.com>
Subject: RE:{Google#034-917 } pronunciation
To:转送邮件者(Thanks)!

We go by:”GU Gul” 

But you are welcome to say whichever you prefer! 

Regards,
The Google Team 

补充2(2001/10/29):请看Google的页面 ”Google”怎么发音


Hajime BABA / 馬場 肇 <baba@kusastro.kyoto-u.ac.jp>
Copyright (C) 2001-2003 Hajime BABA. All rights reserved.
$Id: pagerank.html,v 1.113 2003/07/23 00:38:48 baba Exp $
 翻译:Kreny / 袁 黄琳 <krenyATdalouis.com>
创作于:2003/12   最后更新: 2004年10月28日 3:53

返回首页

2006年08月24日

我们在使用和安装Windows程序时,有时会看到以“2052”、“1033”这些数字为名的文件夹(如Office),这些数字似乎和字符集有关,但它们究竟是什么意思呢?研究这个问题的同时,又会遇到其它问题。我们会谈到Windows的内部架构、Win32 API的A/W函数、Locale、ANSI代码页、与字符编码有关的编译参数、MBCS和Unicode程序、资源和乱码等,一起经历这段琐碎细节为主,间或乐趣点缀的旅程。

0 Where is Win32 API

Windows程序有用户态和核心态的说法。在32位地址空间中,0×80000000以下属于用户态(0×0~0×7FFFFFFF=2GB,0×0~0×10000是保留的),0×80000000以上属于核心态。所有硬件管理都在核心态。用户态程序的不能直接使用核心态的任何代码。所谓核心态其实只是CPU的一种保护模式。在x86 CPU上,用户态处于ring 3,核心态处于ring 0。

从用户态进入核心态的最常用的方法是在寄存器eax填一个功能码,然后执行int 2e。这有点像DOS时代的DOS和BIOS系统调用。在NT架构中这种机制被称作system service。

在核心态提供system service的有两个家伙:ntoskrnl.exe和win32k.sys。ntoskrnl.exe是Windows的大脑,它的上层被称为Executive,下层被称作Kernel。Win32k.sys提供与显示有关的system service。

在用户态一侧,有一个重要的角色叫作ntdll.dll,大多数system service都是它调用的。它封装这些system service,然后提供一个API接口。这个接口被称作native API。 native API的用户是各个子系统(subsystem),包括Win32子系统、OS/2子系统、POSIX子系统。各个子系统为Win32、OS2、POSIX程序提供了运行平台。

ntdll.dll由于提供了平台无关的API接口,所以被看作是NT系统的原生接口,由之得到了“native API”的匪号。其实它的主要工作是将调用传递到核心态。

Win32、OS/2、POSIX,听起来很庞大。其实真正做好的只有Win32子系统。OS2、POSIX都是Console UI,即只有字符界面。提供OS/2子系统,只因为在1988年,NT的主要设计目标就是与OS/2兼容,后来由于Windows 3.0卖得很好,所以设计目标被变更为与Windows兼容。提供POSIX子系统,是为了应付美国政府的一个编号为FIPS 151-2的标准。

Win32子系统的管理员是一个叫作csrss.exe的弟兄,它的全名是:Client/Server Run-Time Subsystem。它刚上任时,本来要分管所有的子系统,但后来POSIX和OS/2都被分别处理了,所以只管了一个Win32。即使这样也很了不起,所有的Win32程序的进程、线程们都要向它登记。

不过Win32程序用得最多的还是Win32子系统的DLL们,最核心的DLL包括:kernel32.dll、User32.dll、Gdi32.dll、Advapi32.dll(高级Win32应用程序接口)。这些DLL包装了ntdll.dll的native API。其中Gdi32.dll比较特殊,它与核心态的win32k.sys直接保持联系,以提高NT系统的图形处理能力。Win32子系统的DLL们提供的接口函数在MSDN文档中被详细介绍,它们就是Win32 API。

附录0 Windows的启动

计算机上电后,从BIOS的ROM开始运行。BIOS在做一些初始化后会将硬盘的第一个扇区的数据读入内存,然后将控制权交给它,这段数据被称作Master Boot Record(MBR)。

MBR包含一段启动代码和硬盘的主分区表。这段启动代码扫描主分区表,找到第一个可以启动的分区,然后将这个分区的第一个扇区读入内存并运行。这个扇区被称作引导扇区(boot sector)。

引导扇区的代码具备读文件系统根目录的能力,显然不同的文件系统需要不同的代码。引导扇区会从根目录中读出一个叫作ntldr的文件。顾名思义,这个文件是load NT的主要角色。它的业绩主要包括将CPU从实模式转入保护模式,启动分页机制,处理boot.ini等。

如果boot.ini中有一句:

C:\bootsect.rh=”Red Hat Linux”

bootsect.rh的内容是Linux引导扇区,用户又选择了“Red Hat Linux”,ntldr就会将执行Linux的引导扇区,开始Linux的引导。如果用户选择继续使用Windows,ntldr会装载并运行我们前面提到的ntoskrnl.exe。

ntoskrnl.exe会启动会话管理器smss.exe。smss.exe启动csrss.exe和winlogon.exe。smss.exe会永远等待csrss.exe和winlogon.exe返回。如果两者之一异常中止,就会导致系统崩溃。所以病毒们经常以打击csrss.exe为乐。

winlogon.exe负责用户登录,在完成登录后,它会启动注册表HKLM\SOFTWARE\Microsoft\Windows NT\Current Version\Winlogon项下Userinit值指定的程序。该值的缺省数据是userinit.exe。userinit.exe会装载个人设置,让硬盘响个不停,并考验我们的耐性,最后启动注册表同一项下Shell值指定的程序。该值的缺省数据是Explorer.exe。Explorer.exe运行后,我们就会看到熟悉的开始菜单和桌面。

1 Win32 API的A/W函数

要了解Win32子系统的DLL们提供了哪些API,最直接的方法就是用Win32dsm直接查看DLL们的导出表。这时我们会发现Win32 API中带字符串的API一般都有两个版本,例如CreateFileA和CreateFileW。当然也有例外,例如GetProcAddress函数。

A代表ANSI代码页,W是宽字符,即Unicode字符。Windows中的Unicode字符一般指UCS2的UTF16-LE编码。让我们通过几个实例观察A/W版本间的关系。

例1:用WIn32dsm查看gdi32.dll的汇编代码,可以看到TextOutA调用GdiGetCodePage获取当前代码页,再调用MultiByteToWideChar转换输入的字符串,然后调用一个内部函数。而TextOutW直接调用这个内部函数。

例2:用调试器跟踪一个使用了CreateFileA的程序,可以看到:CreateFileA在将输入字符串转换为Unicode后,会调用CreateFileW。假设输入文件名是“测试.txt”,对应的数据就是:“B2 E2 CA D4 2E 74 78 74 00”。
在调试器中可以看到传给CreateFileW的文件名数据是:“4B 6D D5 8B 2E 00 74 00 78 00 74 00 00 00”。 这是”测试.txt”对应的Unicdoe字符串。CreateFileW会接着调用ntdll.dll中的NtCreateFile。顺便看看NtCreateFile的代码:
mov eax, 00000020
lea edx, dword ptr [esp+04]
int 2E
ret 002C
可见这个native API只是简单地调用了核心态提供的0×20号system service。

例3:gdi32.dll中的GetGlyphOutline函数可以获取指定字符的字模。GetGlyphOutlineA和GetGlyphOutlineW函数都会调用同一个内部函数(记作F)。函数F在返回前将通过int 2E调用0×10B1号system service。
GetGlyphOutlineW直接调用函数F。GetGlyphOutlineA在调用函数F前,要依次调用GdiGetCodePage、IsDBCSLeadByteEx和MultiByteToWideChar,将当前代码页的字符编码转换成Unicode编码。
如果我们调用GetGlyphOutlineA时传入“baba”,这是“汉”字的GBK编码,用调试器可以看到传给函数F的字符编码是“6c49”,这是“汉”字的Unicode编码。

从以上例子可见,A版本总会在某处将输入的字符串转换为Unicode字符串,然后和W版本执行相同的代码。在由A/W版本API引出MBCS程序和Unicode程序前,让我们先解释一下Locale和ANSI代码页。

2 Locale和ANSI代码页

2.1 Locale和LCID

Locale是指特定于某个国家或地区的一组设定,包括字符集,数字、货币、时间和日期的格式等。在Windows中,每个Locale可以用一个32位数字表示,记作LCID。在winnt.h中可以看到LCID的组成。它的高16位表示字符的排序方法,一般为0。在它的低16位中,低10位是primary language的ID,高4位指定sublanguage。sublanguage被用来区分同一种语言的不同编码。下面是部分primary language和sublanguage的常数定义:

#define LANG_CHINESE 0×04
#define LANG_ENGLISH 0×09
#define LANG_FRENCH 0×0c
#define LANG_GERMAN 0×07

#define SUBLANG_CHINESE_TRADITIONAL 0×01 // Chinese (Taiwan Region)
#define SUBLANG_CHINESE_SIMPLIFIED 0×02 // Chinese (PR China)
#define SUBLANG_ENGLISH_US 0×01 // English (USA)
#define SUBLANG_ENGLISH_UK 0×02 // English (UK)

好,现在我们可以计算简体中文的LCID了,将sublanguage的常数左移10位,即乘上1024,再加上primary language的常数:2*1024+4=2052,16进制是0804。美国英语是:1*1024+9=1033,16进制是0409。。繁体中文是1*1024+4=1028,16进制是0404。

2.2 代码页

每个Locale都联系着很多信息,可以通过GetLocalInfo函数读取。其中最重要的信息就是字符集了,即Locale对应的语言文字的编码。Windows将字符集称作代码页。

每个Locale可以对应一个ANSI代码页和一个OEM代码页。Win32 API使用ANSI代码页,底层设备使用OEM代码页,两者可以相互映射。

例如English (US)的ANSI和OEM代码页分别为“1252 (ANSI – Latin I)”和“437 (OEM – United States)”。 Chinese (PRC)的ANSI和OEM代码页都是“936 (ANSI/OEM – Simplified Chinese GBK)”。  Chinese (TW)的ANSI和OEM代码页都是“950 (ANSI/OEM – Traditional Chinese Big5)”。

附录1中有一张很长的表。列出了我正在使用的Windows所支持的135个Locale的部分信息,包括 LCID、国家/地区名称、语言名称、语言缩写和对应的ANSI代码页。

2.3 系统Locale、用户Locale,再谈ANSI代码页

在Windows中,通过控制面板可以为系统和用户分别设置Locale。系统Locale决定代码页,用户Locale决定数字、货币、时间和日期的格式。这不是一个好的设计,后面会谈到它带来的问题。

使用GetSystemDefaultLCID函数和GetUserDefaultLCID函数分别得到系统和用户的LCID。有很多材料将这两个函数和另外两个函数混淆:GetSystemDefaultUILanguage和GetUserDefaultUILanguage。

GetSystemDefaultUILanguage和GetUserDefaultUILanguage得到的是您当前使用的Windows版本所带的UI资源的语言。

用户程序缺省使用的代码页是当前系统Locale的ANSI代码页,可以称作ANSI编码,也就是A版本的Win32 API默认的字符编码。对于一个未指定编码方式的文本文件,Windows会按照ANSI编码解释。

2.4 AppLocale

如果一个文本文件采用BIG5编码,系统当前的ANSI代码页是GBK。打开这个文件,就会显示乱码。例如“中文”在BIG5中的编码是A4A4、A4E5,这两个编码在GBK中对应的字符是“いゅ”。这是日文的两个平假名。

在Windows XP平台有一个AppLocale程序,可以以指定的语言运行非Unicode程序。用Win32dsm打开看一看,其实它只是在运行程序前设置了两个环境变量。我们可以用个批处理文件模仿一下:

@ECHO OFF
SET __COMPAT_LAYER=#ApplicationLocale
SET ApplocaleID=0404
start notepad.exe

在简体中文平台,用这个批处理文件启动的记事本可以正确显示BIG5编码的文本文件。用它打开GBK编码的文本文件会怎么样?“中文”会被显示为“笢恅”。设置这两个环境变量会作用于当前进程和其子进程。Windows 2000平台不支持这个方法。

3 MBCS程序和Unicode程序

3.1 与字符编码有关的编译参数

让我们回到Win32 API。我们在程序中使用的Win32 API没有A/W后缀,Windows的头文件会根据编译参数UNICODE将没有后缀的函数名替换为A版本或W版本,例如:

#ifdef UNICODE
#define CreateFile CreateFileW
#else
#define CreateFile CreateFileA
#endif

C RunTime库(CRT)使用_UNICODE和_MBCS来区分三套字符串处理函数,分别用于SBCS、MBCS和Unicdoe字符串。SBCS和MBCS分别指单字节字符串和多字节字符串。例如_tcsclen的3个版本分别为strlen、_mbslen和wcslen ,猜猜以下函数返回几?

strlen(”VOIP网关”);
_mbslen((unsigned char *)”VOIP网关”);
wcslen(L”VOIP网关”);

答案是8、6、6。L”ANSI字符串”通知编译器将ANSI字符串转换为Unicode字符串,这是VC++编译器提供的一个小甜点。不过我们应该用宏:_T(”ANSI字符串”)。_T宏只在我们定义了_UNICODE时才转换。这样同一套代码既可以编译MBCS版本,也可以编译Unicode版本。

MFC用_UNICODE参数区分Unicode版本特有的代码,决定使用什么版本的导入库或静态库。

3.2 Unicode程序、MBCS程序和多语言支持

Unicode程序直接使用Unicode版本的CRT和Win32 API。Unicode程序的运行与当前的ANSI代码页没有关系。MBCS程序的运行依赖于ANSI代码页。如果设计者和使用者使用不同的代码页,就可能出现乱码。微软开发的程序大都是Unicode程序,不管我们怎样变换系统Locale,它们总能正常运行。

使用VCL类库的Delphi程序都是MBCS程序。VCL框架在程序启动会调用GetThreadLocale获取当前用户的LCID,然后在当前目录查找对应的资源文件,命名规则是:程序名+’.’+语言缩写,语言缩写可以参见附录1。在找不到时才会使用EXE文件中的资源。不过如果系统LCID是English(United States),用户LCID是Chinese(PRC),由VCL产生的程序就会出现乱码。读者可以自己分析原因。

为VCL程序做多语言版本。只要用Delphi自带的Resource DLL Wizard再做一个特定语言的资源DLL,原来的程序都不用改。不过很多程序员用其它组件做多语言版本,例如TsiLang 。

MBCS程序虽然也可以做成多语言版本,但它无法在同时显示不同代码页特有的字符,这时就必须使用Unicode程序了。

VS.NET文档中有个多语言资源的例子:SatDLL。它只用Win32 API的例子,却用了VC7项目。我在学习时将它改成了VC6项目,并纠正了它的两个问题:
1、用GetUserDefaultUILanguage读到的是Windows资源版本,不是当前用户设置的代码页。
2、启动时没有使用资源DLL里的菜单。

在我的个人主页(http://fmddlmyy.home4u.china.com)上可以下载修改过的SatDLL。这个程序说明了支持多语言资源的基本思路:将不同语言资源放到不同的DLL中,在程序启动时根据当前Locale装载对应的资源DLL。必要时动态切换资源。为了标记不同语言的资源,可以将它们放到不同的目录中,以LCID作为目录名,例如“2052”、“1033”。当然我们也可以用其它方法联系LCID和资源DLL。

MFC程序可以在App类的InitInstance函数中用AfxSetResourceHandle函数设置资源DLL。在Delphi中动态切换资源可以参考Delphi Demo目录RichEdit项目的ReInit.pas。在读取当前设定时,建议用GetSystemDefaultLCID函数,因为系统Locale决定ANSI代码页。

3.4 资源和乱码

通过检查可执行文件,我们可以确定VC和Delphi的资源编译器都以Unicode保存字符资源。在VC环境编辑资源时,我们会指定资源的代码页。编译器根据资源的代码页,将其转换到Unicode。

Unicode程序直接使用以Unicode编码保存的资源。MBCS程序需要将Unicode资源先转换回当前ANSI代码页,然后再使用。如果资源中的Unicode字符串不能映射到当前代码页中的字符,就会出现??。

例如Windows的标准对话框也会出现乱码。假设我们使用简体中文Windows,当前Locale是Chinese (TW),我们的程序是MBCS的,使用标准的打开文件对话框。因为在BIG5中没有“开”这个字,所以“打开”会被显示成“打?”。将程序编译成Unicode版本,就可以避免这个问题。

如果字符不是保存在资源中,而是硬编码在程序中。然后开发者和用户使用不同的代码页,就会导致乱码。假设开发者的Locale是Chinese (PRC),用户的Locale是English (US),程序中硬编码了字符串“文件”。 Chinese (PRC)的ANSI代码页是GBK,“文件”的编码“CE C4 BC FE”。English (US)的ANSI代码页是Latin I,用户按照Latin I编码去解释“CE C4 BC FE”,就会看到“Îļþ”。

回答我前面提过的一个问题:Delphi程序根据用户LCID转换资源中的字符串。如果用户LCID是Chinese (PRC),系统LCID是English (US)。那么资源中的Unicode字符串会被转换为GBK编码,然后按照Latin I显示,这时我们看到的就是类似“Îļþ”的东东,不是??。

既然资源是以Unicode保存的,MBCS程序如果不将其转换到ANSI代码页,而用W版本的函数直接显示,就不会产生乱码。例如MFC程序菜单里的中文,在English (US)的Locale也可以正常显示。不过这取决于各部分代码的具体实现,menu bar控件里的中文在English (US)的Locale会全部显示成??。

进一步的参考资料

本文的第0节和附录0主要参考了《Inside Windows 2000 Third Edition》,国内出过该书的影印版。DDK文档中有大量Windows内核的信息。用Win32dsm和各种调试器查看Windows系统文件可以获得更直接的信息。

关于Window程序的字符编码,最好的参考资料是winnt.h等SDK的包含文件、VCL、MFC、CRT的源文件。我们不需要阅读它们,只要找到自己感兴趣的信息就可以了,用Source Insight可能方便一些。

本文所谈的不是什么万古不迁的道理,只是别的程序员的一些设定,我们因为需要使用他们的程序,所以有必要了解一些细节。研究问题的方法和兴趣永远比问题本身重要,如一句拉丁俗语所说:res, non verba,实质胜于文字。

尾声

“明月虽有圆缺,但毕竟永恒不灭,人生却如过眼烟云,一去不回,真不知计较为何?”

“蛙声虽是短促,但却是万籁中一个活泼的禅机,也可以说万古如斯,永恒不迁,无奈感受到的,能有几人?”

这是一本武侠书中的对话。在时间的长河中,人生和蛙声一样易逝。说到蛙声,我的20个月的小宝宝在喝汤后,略加酝酿,就会紧闭着嘴巴,发出很像蛙鸣的声音。我们会逗他说:“小青蛙又来了”。小家伙益发得意,不管我的抗议,将连汤带油的小下巴亲热地贴在我的身上。

 

附录1 一些关于LCID的信息

使用EnumSystemLocales函数可以枚举系统支持的LCID。用GetLocaleInfo可以得到ANSI代码页的ID,再通过GetCPInfoEx可以获得代码页的全称。以下是我在中文Windows XP上读到的内容。

LCID 国家或地区 语言 语言缩写 ANSI代码页
1025 沙特阿拉伯 阿拉伯语(沙特阿拉伯) ARA 1256  (ANSI – 阿拉伯文)
1026 保加利亚 保加利亚语 BGR 1251  (ANSI – 西里尔文)
1027 西班牙 加泰隆语 CAT 1252  (ANSI – 拉丁文 I)
1028 台湾 中文(台湾) CHT 950   (ANSI/OEM – 繁体中文 Big5)
1029 捷克共和国 捷克语 CSY 1250  (ANSI – 中欧)
1030 丹麦 丹麦语 DAN 1252  (ANSI – 拉丁文 I)
1031 德国 德语(德国) DEU 1252  (ANSI – 拉丁文 I)
1032 希腊 希腊语 ELL 1253  (ANSI – 希腊文)
1033 美国 英语(美国) ENU 1252  (ANSI – 拉丁文 I)
1034 西班牙 西班牙语(传统) ESP 1252  (ANSI – 拉丁文 I)
1035 芬兰 芬兰语 FIN 1252  (ANSI – 拉丁文 I)
1036 法国 法语(法国) FRA 1252  (ANSI – 拉丁文 I)
1037 以色列 希伯来语 HEB 1255  (ANSI – 希伯来文)
1038 匈牙利 匈牙利语 HUN 1250  (ANSI – 中欧)
1039 冰岛 冰岛语 ISL 1252  (ANSI – 拉丁文 I)
1040 意大利 意大利语(意大利) ITA 1252  (ANSI – 拉丁文 I)
1041 日本 日语 JPN 932   (ANSI/OEM – 日文 Shift-JIS)
1042 朝鲜 朝鲜语 KOR 949   (ANSI/OEM – 韩文)
1043 荷兰 荷兰语(荷兰) NLD 1252  (ANSI – 拉丁文 I)
1044 挪威 挪威语(伯克梅尔) NOR 1252  (ANSI – 拉丁文 I)
1045 波兰 波兰语 PLK 1250  (ANSI – 中欧)
1046 巴西 葡萄牙语(巴西) PTB 1252  (ANSI – 拉丁文 I)
1048 罗马尼亚 罗马尼亚语 ROM 1250  (ANSI – 中欧)
1049 俄罗斯 俄语 RUS 1251  (ANSI – 西里尔文)
1050 克罗地亚 克罗地亚语 HRV 1250  (ANSI – 中欧)
1051 斯洛伐克语 斯洛伐克语 SKY 1250  (ANSI – 中欧)
1052 阿尔巴尼亚 阿尔巴尼亚语 SQI 1250  (ANSI – 中欧)
1053 瑞典 瑞典语 SVE 1252  (ANSI – 拉丁文 I)
1054 泰国 泰语 THA 874   (ANSI/OEM – 泰文)
1055 土耳其 土耳其语 TRK 1254  (ANSI – 土耳其文)
1056 巴基斯坦伊斯兰共和国 乌都语 URD 1256  (ANSI – 阿拉伯文)
1057 印度尼西亚 印度尼西亚语 IND 1252  (ANSI – 拉丁文 I)
1058 乌克兰 乌克兰语 UKR 1251  (ANSI – 西里尔文)
1059 比利时 比利时语 BEL 1251  (ANSI – 西里尔文)
1060 斯洛文尼亚 斯洛文尼亚语 SLV 1250  (ANSI – 中欧)
1061 爱沙尼亚 爱沙尼亚语 ETI 1257  (ANSI – 波罗的海文)
1062 拉脱维亚 拉脱维亚语 LVI 1257  (ANSI – 波罗的海文)
1063 立陶宛 立陶宛语 LTH 1257  (ANSI – 波罗的海文)
1065 伊朗 法斯语 FAR 1256  (ANSI – 阿拉伯文)
1066 越南 越南语 VIT 1258  (ANSI/OEM – 越南)
1067 亚美尼亚 亚美尼亚语 HYE 936   (ANSI/OEM – 简体中文 GBK)
1068 阿塞拜疆 阿塞拜疆语(拉丁文) AZE 1254  (ANSI – 土耳其文)
1069 西班牙 巴士克语 EUQ 1252  (ANSI – 拉丁文 I)
1071 前南斯拉夫马其顿共和国 马其顿语(FYROM) MKI 1251  (ANSI – 西里尔文)
1078 南非 南非语 AFK 1252  (ANSI – 拉丁文 I)
1079 格鲁吉亚 格鲁吉亚语 KAT 936   (ANSI/OEM – 简体中文 GBK)
1080 法罗群岛 法罗语 FOS 1252  (ANSI – 拉丁文 I)
1081 印度 印地语 HIN 936   (ANSI/OEM – 简体中文 GBK)
1086 马来西亚 马来语(马来西亚) MSL 1252  (ANSI – 拉丁文 I)
1087 吉尔吉斯坦 哈萨克语 KKZ 1251  (ANSI – 西里尔文)
1088 吉尔吉斯斯坦 吉尔吉斯语 (西里尔文) KYR 1251  (ANSI – 西里尔文)
1089 肯尼亚 斯瓦希里语 SWK 1252  (ANSI – 拉丁文 I)
1091 乌兹别克斯坦 乌兹别克语(拉丁文) UZB 1254  (ANSI – 土耳其文)
1092 鞑靼斯坦 鞑靼语 TTT 1251  (ANSI – 西里尔文)
1094 印度 旁遮普语 PAN 936   (ANSI/OEM – 简体中文 GBK)
1095 印度 古吉拉特语 GUJ 936   (ANSI/OEM – 简体中文 GBK)
1097 印度 泰米尔语 TAM 936   (ANSI/OEM – 简体中文 GBK)
1098 印度 泰卢固语 TEL 936   (ANSI/OEM – 简体中文 GBK)
1099 印度 卡纳拉语 KAN 936   (ANSI/OEM – 简体中文 GBK)
1102 印度 马拉地语 MAR 936   (ANSI/OEM – 简体中文 GBK)
1103 印度 梵文 SAN 936   (ANSI/OEM – 简体中文 GBK)
1104 蒙古 蒙古语(西里尔文) MON 1251  (ANSI – 西里尔文)
1110 西班牙 加里西亚语 GLC 1252  (ANSI – 拉丁文 I)
1111 印度 孔卡尼语 KNK 936   (ANSI/OEM – 简体中文 GBK)
1114 叙利亚 叙利亚语 SYR 936   (ANSI/OEM – 简体中文 GBK)
1125 马尔代夫 第维埃语 DIV 936   (ANSI/OEM – 简体中文 GBK)
2049 伊拉克 阿拉伯语(伊拉克) ARI 1256  (ANSI – 阿拉伯文)
2052 中华人民共和国 中文(中国) CHS 936   (ANSI/OEM – 简体中文 GBK)
2055 瑞士 德语(瑞士) DES 1252  (ANSI – 拉丁文 I)
2057 英国 英语(英国) ENG 1252  (ANSI – 拉丁文 I)
2058 墨西哥 西班牙语(墨西哥) ESM 1252  (ANSI – 拉丁文 I)
2060 比利时 法语(比利时) FRB 1252  (ANSI – 拉丁文 I)
2064 瑞士 意大利语(瑞士) ITS 1252  (ANSI – 拉丁文 I)
2067 比利时 荷兰语(比利时) NLB 1252  (ANSI – 拉丁文 I)
2068 挪威 挪威语(尼诺斯克) NON 1252  (ANSI – 拉丁文 I)
2070 葡萄牙 葡萄牙语(葡萄牙) PTG 1252  (ANSI – 拉丁文 I)
2074 塞尔维亚 塞尔维亚语(拉丁文) SRL 1250  (ANSI – 中欧)
2077 芬兰 瑞典语(芬兰) SVF 1252  (ANSI – 拉丁文 I)
2092 阿塞拜疆 阿塞拜疆语(西里尔文) AZE 1251  (ANSI – 西里尔文)
2110 文莱达鲁萨兰 马来语(文莱达鲁萨兰) MSB 1252  (ANSI – 拉丁文 I)
2115 乌兹别克斯坦 乌兹别克语(西里尔文) UZB 1251  (ANSI – 西里尔文)
3073 埃及 阿拉伯语(埃及) ARE 1256  (ANSI – 阿拉伯文)
3076 香港特别行政区 中文(香港特别行政区) ZHH 950   (ANSI/OEM – 繁体中文 Big5)
3079 奥地利 德语(奥地利) DEA 1252  (ANSI – 拉丁文 I)
3081 澳大利亚 英语(澳大利亚) ENA 1252  (ANSI – 拉丁文 I)
3082 西班牙 西班牙语(国际) ESN 1252  (ANSI – 拉丁文 I)
3084 加拿大 法语(加拿大) FRC 1252  (ANSI – 拉丁文 I)
3098 塞尔维亚 塞尔维亚语(西里尔文) SRB 1251  (ANSI – 西里尔文)
4097 利比亚 阿拉伯语(利比亚) ARL 1256  (ANSI – 阿拉伯文)
4100 新加坡 中文(新加坡) ZHI 936   (ANSI/OEM – 简体中文 GBK)
4103 卢森堡 德语(卢森堡) DEL 1252  (ANSI – 拉丁文 I)
4105 加拿大 英语(加拿大) ENC 1252  (ANSI – 拉丁文 I)
4106 危地马拉 西班牙语(危地马拉) ESG 1252  (ANSI – 拉丁文 I)
4108 瑞士 法语(瑞士) FRS 1252  (ANSI – 拉丁文 I)
5121 阿尔及利亚 阿拉伯语(阿尔及利亚) ARG 1256  (ANSI – 阿拉伯文)
5124 澳门特别行政区 中文(澳门特别行政区) ZHM 950   (ANSI/OEM – 繁体中文 Big5)
5127 列支敦士登 德语(列支敦士登) DEC 1252  (ANSI – 拉丁文 I)
5129 新西兰 英语(新西兰) ENZ 1252  (ANSI – 拉丁文 I)
5130 哥斯达黎加 西班牙语(哥斯达黎加) ESC 1252  (ANSI – 拉丁文 I)
5132 卢森堡 法语(卢森堡) FRL 1252  (ANSI – 拉丁文 I)
6145 摩洛哥 阿拉伯语(摩洛哥) ARM 1256  (ANSI – 阿拉伯文)
6153 爱尔兰 英语(爱尔兰) ENI 1252  (ANSI – 拉丁文 I)
6154 巴拿马 西班牙语(巴拿马) ESA 1252  (ANSI – 拉丁文 I)
6156 摩纳哥公国 法语(摩纳哥) FRM 1252  (ANSI – 拉丁文 I)
7169 突尼斯 阿拉伯语(突尼斯) ART 1256  (ANSI – 阿拉伯文)
7177 南非 英语(南非) ENS 1252  (ANSI – 拉丁文 I)
7178 多米尼加共和国 西班牙语(多米尼加共和国) ESD 1252  (ANSI – 拉丁文 I)
8193 阿曼 阿拉伯语(阿曼) ARO 1256  (ANSI – 阿拉伯文)
8201 牙买加 英语(牙买加) ENJ 1252  (ANSI – 拉丁文 I)
8202 委内瑞拉 西班牙语(委内瑞拉) ESV 1252  (ANSI – 拉丁文 I)
9217 也门 阿拉伯语(也门) ARY 1256  (ANSI – 阿拉伯文)
9225 加勒比海 英语(加勒比海) ENB 1252  (ANSI – 拉丁文 I)
9226 哥伦比亚 西班牙语(哥伦比亚) ESO 1252  (ANSI – 拉丁文 I)
10241 叙利亚 阿拉伯语(叙利亚) ARS 1256  (ANSI – 阿拉伯文)
10249 伯利兹 英语(伯利兹) ENL 1252  (ANSI – 拉丁文 I)
10250 秘鲁 西班牙语(秘鲁) ESR 1252  (ANSI – 拉丁文 I)
11265 约旦 阿拉伯语(约旦) ARJ 1256  (ANSI – 阿拉伯文)
11273 特立尼达和多巴哥 英语(特立尼达) ENT 1252  (ANSI – 拉丁文 I)
11274 阿根廷 西班牙语(阿根廷) ESS 1252  (ANSI – 拉丁文 I)
12289 黎巴嫩 阿拉伯语(黎巴嫩) ARB 1256  (ANSI – 阿拉伯文)
12297 津巴布韦 英语(津巴布韦) ENW 1252  (ANSI – 拉丁文 I)
12298 厄瓜多尔 西班牙语(厄瓜多尔) ESF 1252  (ANSI – 拉丁文 I)
13313 科威特 阿拉伯语(科威特) ARK 1256  (ANSI – 阿拉伯文)
13321 菲律宾共和国 英语(菲律宾) ENP 1252  (ANSI – 拉丁文 I)
13322 智利 西班牙语(智利) ESL 1252  (ANSI – 拉丁文 I)
14337 阿联酋 阿拉伯语(阿联酋) ARU 1256  (ANSI – 阿拉伯文)
14346 乌拉圭 西班牙语(乌拉圭) ESY 1252  (ANSI – 拉丁文 I)
15361 巴林 阿拉伯语(巴林) ARH 1256  (ANSI – 阿拉伯文)
15370 巴拉圭 西班牙语(巴拉圭) ESZ 1252  (ANSI – 拉丁文 I)
16385 卡塔尔 阿拉伯语(卡塔尔) ARQ 1256  (ANSI – 阿拉伯文)
16394 玻利维亚 西班牙语(玻利维亚) ESB 1252  (ANSI – 拉丁文 I)
17418 萨尔瓦多 西班牙语(萨尔瓦多) ESE 1252  (ANSI – 拉丁文 I)
18442 洪都拉斯 西班牙语(洪都拉斯) ESH 1252  (ANSI – 拉丁文 I)
19466 尼加拉瓜 西班牙语(尼加拉瓜) ESI 1252  (ANSI – 拉丁文 I)
20490 波多黎各(美) 西班牙语(波多黎各(美)) ESU 1252  (ANSI – 拉丁文 I)

LCID取决于语言,在表中列出国家名只是为了增加趣味性。例如可以看到以色列还在使用古老的希伯来语。“希伯来语”的法文是hébreu,这个单词还有一个意思,就是“不能理解的东西”。

 

在winnt.h中,对subsystem的定义如下:
#define IMAGE_SUBSYSTEM_UNKNOWN 0 // Unknown subsystem.
#define IMAGE_SUBSYSTEM_NATIVE 1 // Image doesn’t require a subsystem.
#define IMAGE_SUBSYSTEM_WINDOWS_GUI 2 // Image runs in the Windows GUI subsystem.
#define IMAGE_SUBSYSTEM_WINDOWS_CUI 3 // Image runs in the Windows character subsystem.
#define IMAGE_SUBSYSTEM_OS2_CUI 5 // image runs in the OS/2 character subsystem.
#define IMAGE_SUBSYSTEM_POSIX_CUI 7 // image runs in the Posix character subsystem.
#define IMAGE_SUBSYSTEM_NATIVE_WINDOWS 8 // image is a native Win9x driver.
#define IMAGE_SUBSYSTEM_WINDOWS_CE_GUI 9 // Image runs in the Windows CE subsystem.
CUI就是Console UI了。我们使用的subsystem主要是3和2。

在用户态看起来很底层的东西,例如Win32 subsystem的核心:kernel32.dll、user32.dll、gdi32.dll,基本上只是ntdll.dll的一个包装,而ntdll.dll包装了从用户态到核心态的system call,也称作“Native System Service”。
用户态不能访问核心态的任何函数和变量,所以system call不同于一般的API调用。system call可以被看作:将要调用的功能ID放到eax,然后执行INT 2e。
ntdll.dll通过system call使用核心态的ntoskrnl.exe和win32k.sys提供的功能。ntoskrnl.exe被尊称为“Executive”,可以看作是NT的大脑级模块。win32k.sys提供NT图形库接口的API。

2006年05月20日

【玛雅】因为我相信你 寒风呼啸而过,厚厚的绒毛不能阻挡,冷风一丝一丝地啃噬着我的身体,望着灿烂的极光,我迷茫的回忆,终止在杰瑞上飞机前…

他抱着我的身子,亲吻我的额头.他的嘴唇冰冷,但我却触碰到了他滚烫的泪,那一秒,我有一种不好的预感,但我没想到,我们会遭遇这一切…

老杰克还是没有和我们一起走,他说他想守着自己的岗位,等杰瑞回来.我也不想离去,但身为领头犬,我别无选择.如果可以,我愿意和他一起等,因为杰瑞说过:我发誓,我会回来.那一句话,和我的生命一样重要.

已经40多天了,希望越来越渺茫,杰瑞真的会回来么…会么…会么…我暴怒地打断自己的思维,我怎么可以怀疑杰瑞,他留下的那句话,难道还有我置疑的余地么…

杜威的死,让杜鲁门深深受伤了,他那悲寂的嚎叫几乎要让我落泪,但我没有哭,我是首领,我不会软弱.我大声地告诉他们:杰瑞会回来,请支持下去.他们坚定的眼神和我一样,杰瑞,快些回来吧!

Max终于归队了,但我的腿也受了重伤.添着温热的血液,我想起了以前杰瑞为我包扎伤口时的样子,心疼,担心…想到这里,我不禁微笑起来.杰瑞,在赶来的路上对不对…杰瑞,我们如此勇敢,请快些回来!Max年纪还太小,将队伍交给他我还是会有些担心,可我已经没有了领头的能力,我只想安静地等你回来,杰瑞,回来吧,我们都在等你!

冷…寒冷侵蚀着我的身子.厚厚的雪层让我窒息,Max趴着我的身边,他眼里的害怕我知道,我哽咽着说:Max,带领好大家,等着杰瑞接你们回去…Max的眼里都是泪水,我知道他和我一样深信着杰瑞,他是好样的!我安静的闭上了眼睛,眼前是杰瑞微笑的脸,抱歉,杰瑞,我没有勇敢地等你回来…

脸上好湿呵…又是Max这个调皮的家伙在往我脸上流口水吗…我疲倦的睁开眼睛…眼前的是…杰瑞么…杰瑞么?!我惊慌地想起身,想好好看看170多天没有见过的杰瑞,但瑞上剧烈的疼痛让我又坐了下来,我一声不响的坐在他面前,杰瑞,你终于来了么…终于来了么…眼泪在他脸上疯狂的蔓延,他激动得几乎不能说话,只是在喃喃:玛雅,我的好姑娘!你是好样的!我开心地笑了,杰瑞,见到你真好,我以为我再没有机会了呢…我安静地趴在他怀里,我觉得从他体内涌出来的,浓浓的幸福让我好舒服…真像一个梦啊…我沉沉睡去… 【Max】暗夜后的黎明 我的名字叫Max,给我起名字的,是一个名叫杰瑞的年轻人,他有着坚毅的面容和宽厚的肩膀,他总是喜欢微笑着看着我,说着,Max,你会成为最棒的!而每每这个时候,领头犬玛雅总是淡淡地看着我们,眼角偶尔闪过一丝担忧.当是的我还太小,我只有1岁,我不明白他们对我,是一种什么样的期望,直到,那个博士的来临,或者说,直到灾难的来临. 南极的温度总是不给人幻想的余地,我把身体埋在雪地里,明天就要出发了吧,玛雅说是莫尔本山,我还没有去仔细看过呢!微微的兴奋在我的血液里撞击,我眨了眨清亮的眼睛,缩进了雪窝. 当我全力奔跑着的时候,我兴奋的全身每一丝肌肉都紧绷起来,呵呵~我开心的笑着,风在我耳边呼啸而过,我肆意地奔跑着~呵呵!呵呵! 停下!Max停下!杰瑞拼命的呼喊声突然把我拉回了现实,恩?怎么了? 大家狼狈地站成一排,老杰克微微瘸着腿,玛雅愤怒地看着我,我突然发现,我偏离了道路,是我,才这样的么… 心情沮丧的我,漫不经心地跑着,老杰克有点担忧地看着我,我微微地叹着气,玛雅回头看了我一眼,面无表情地转过身去.哎…犯了错以后玛雅总是这样…真是的! 眼前的一切让我傻了眼,博士半个身子陷在冰窟里,他的脸色发蓝,我的呼吸几近停止,天啊,这可怎么办? 在我焦躁不安地来回踱步的时候,杰瑞已经为玛雅缠上了绳子.玛雅,要去做什么呢?! 看着玛雅小心翼翼地移动着步子,我才体会到了几乎要窒息的感觉,玛雅!小心啊!玛雅似乎也感觉到了危险,突然停了下来,杰瑞在她身后拼命地喊着:好姑娘,相信我!玛雅听到这句话,又奋力前进着.是啊,无论何时,玛雅永远都是队伍里最忠诚杰瑞的,但这种忠诚也让我深深地不解,为什么要这样忠诚? 当绳子终于套进了博士的身子,我和其他狗儿们奋力狂奔起来的时候,我的眼泪几乎摇摇欲坠,玛雅没事呢,太好了.我回头去看玛雅,她的身子在一片雪原中毫发毕现,充满了一股王者之风,第一次,我对她心悦诚服. 回到基地,我发现事情并没有很简单地结束,杰瑞的手指发黑,而博士陷入了昏迷,我隐隐地预感着,要发生些什么了… 果然,杰瑞他们开始收拾物品,很快,他们走到了飞机边.我用力挣脱了链子,走到杰瑞身边,仰起脑袋看着他.也是第一次,杰瑞没有和我玩耍,他吻着我的额头,把我栓回了链子,他最后的一次回眸,让我瞬间感到前所未有的黑暗,杰瑞!你要走了么?回来么?!我疯狂的吼叫起来. 玛雅慢慢走到他身边,他捧起玛雅的脸,带着哽咽地说:好姑娘,我发誓,我一定会回来!玛雅安静地看着他,表情仿佛是千年不化的寒冰,但那双清澈的眼睛里,还是让我看到了隐隐的担忧…玛雅,到底是什么事? 5天了,我沉默地计算着时间,时而会起来吼叫几声,可是其他的狗狗们经常在沉睡,他们是在等着杰瑞发回来吧,我知道我不该例外,但我敏感地觉得,事情不会那么简单. 那面蓝色的旗子让风刮跑了,我迅速地挣脱了链子,追着它跑过去,当我终于衔着旗子回来时,大家都挣脱了链子,看着站在老杰克身边的玛雅. 玛雅温柔地添着老杰克,慢慢地劝说着他,可是老杰克只是静静地望着她.那一秒,我看到玛雅眼睛里有晶莹地水光,玛雅,是哭了么? 玛雅探身去咬老杰克的链子,老杰克躲闪了一下,仍然淡淡地看着玛雅,玛雅像是下了很大的决心,急速地转身,其他狗狗们跟着玛雅迅速离开,我看了老杰克一眼后,连忙赶了上去. 玛雅,为什么留下老捷克?玛雅,他会饿死的!玛雅,我们回去救他啊!玛雅,玛雅!我疯狂地对着玛雅吼叫,玛雅却淡然地看着远处.玛雅,原来你是这样的!我恨恨地想着. 远处是一群海鸥. 我可以听见大家咽口水的声音,但却没有任何一个走出队伍,大家只是静静地看着玛雅.玛雅沉默了一会,做出了判断:全面进攻,由她进行驱赶,其他狗狗负责追逐.很快,别的狗狗散开准备出击,我一动不动地站着,看着玛雅. 玛雅的眼睛里已经有了隐隐地怒火,我更像个无赖一样坐到了地上,玛雅没有多看我一眼,跑了下去追逐海鸥.那个瞬间,我心里闪过一丝难过,就像一个想要恶作剧的小孩计划失败了一样,我颓然地看着玛雅和其他狗狗们. 几乎是全胜,很多很多的海鸥躺在面前,谁也没有吃,依然是望着玛雅. 玛雅叼过一只开始吃起来,别的狗狗才开始吃起来.我凑到玛雅的身边,像以前一样想要吃她的食物,突然,她像我呲开了牙齿. 她脸上骇人的表情吓了我一跳,我惊悚地跳开,玛雅,竟然用这种方式惩罚我?!我闷闷不乐地凑近了小个子身旁,他安静地吃着,毫不介意我在分享他的食物,总算,我没有挨饿. 【OLD JACK】一直在等待 依然是那么冷的清晨,和往常一样,抖下身上的积雪,开始新的一天,JERRY,那熟悉的呼唤,陪伴了我服役的10年,我深深眷恋着这片土地,以及爱我的人们,还有我生死相依的兄弟。 耳边传来飞机的轰鸣,又有新的任务了吧,心里有那么一丝兴奋,访客们带着许多许多的行李,可是看JERRY的表情,这次任务好象非同寻常,夜深了,JERRY在牌桌上和他们谈论着什么,他好象很不乐意,很不开心,JERRY,你怎么了,每次和我们一起出去探路,你不是一直充满笑容么,怎么今天,难道。。。。 我们要出发了,带上了厚重的行李,那个博士和JERRY一起去,还有他那些冰冷的器材,好象对他们很重要,JERRY在和博士介绍我的时候,眼里总有很多的鼓励和赞许,这是我在这里流汗所得到的最满意的回报。 出发了,这些东西好象蛮重,年轻的伙伴们,加油啊!这可能是我最后一次任务了,10年了,就这样过去,许多许多的回忆突然涌上心头。 不对,怎么叫停了,前面的路好象很危险,JERRY叫MAYA带队,并且改变了队型,JERRY,怎么下来了,他一直在前面探路,好象真的危险,MAYA带领我们从另外一边走,MAX,你干什么,不!!!! 是冰缝,加油啊大家,一定要保护我们的客人,我们能行。 危险终于过去了,好累啊,脚都一直在发麻,JERRY替所有的同伴检查他们的状况,看的出来,疲劳的我们让他看起来很心疼,JERRY,我们是最棒的,没事,相信我们。 JERRY和博士去了那么久,天气好象又变了许多,他们怎么还不回来,我有不好的预感…… 他们终于回来了,好象很高兴,我们要回家了,我的最后一次任务就这样过去了…… 啊……博士,他掉进了水里,MAYA,加油,他的生死就在你手中,MAYA,棒极了,你做到了,你救了他,可是天气更糟糕了,快,我们得回去,JERRY,坐好了,MAYA,你带领同伴,冲吧! JERRY快不行了,大家努力,MAYA,我们的骄傲,加油!我看见基地了,看见了,我们到了,JERRY回头对我们大喊:“都是好样的!。”我为我们感到自豪。 恩?怎么了,要走了嘛,为什么把我们栓那么紧,JERRY,你们要去哪?如果不能全部带上,至少也带上他们呀,MAX还小,MAYA那么优秀,还有…… 飞机飞了,JERRY丢下了我们,不对,他和MAYA说过,一定会回来,我相信我的主人,一定要等他回来。 好饿,同伴们好象有点沮丧,MAYA你觉的呢,他们会回来么,MAX,你安静点,BUCK,你去哪,旗子飞了,快!那是我们的骄傲,一定要追回来,MAX,站住,不要轻易离开,怎么……大家都挣脱了,去寻找食物,MAYA?不,我不走,我要等他们回来,你们还年轻,去寻找你们的生路吧,这里是我的家,我的一切,MAYA,请不要流泪,我为这里工作了10年,没有主人的命令,我不能离开,MAYA,你是最棒的,你能带领他们活下去,我相信你,MAYA,再见,希望不是永别。 好安静啊,JERRY,你在想我么,你还记得我么,怀念暖暖的帐篷,JERRY摸着我的头:“OLD JACK,加油,你很棒。” 每次出行:“OLD JACK,加油,好样的。” 怀念我们在排桌上一起游戏,JERRY和伙伴们一起探路。 我的意识,在渐渐消失,耳边是轰轰的声音,是JERRY回来了么,难道是暴风雪,不……JERRY,你一定在回来的路上,JERRY……

2006年03月25日

『一:前期工作』

    所有长线进程中的相关文章标题都应以“【第N 组长线杀人】”开头,下略。

    1、申请开设长线

    长线杀人开设由kingkiller板务组决定,或由欲担任长线法官的网友向版务组申请
并征得同意后开设。如果申请者本人不愿担任法官,则应先征集一名熟悉规则与网络规
则的法官之后方可申请。申请可采用板面发文或私下交流等方式。

    2、宣布规则

    规则由该组长线杀人法官宣布,标题为“规则”。板务组应将此规则在该组长线进
行过程中置底。此步骤可以省略,则视为该组长线使用默认规则——即本规则。

    3、征集报名

    法官负责征集报名,在Kingkiller板发表题目为“开始报名”的文章。游戏人数建
议为8 人或者11人(可在征集报名文章中注明,也可不注明并根据实际报名人数决定)
。报名者要确保自己能够做到每天上站至少一次(法官在每一进程结束时会在版面上发
表进入下一程序的文章以及给所有参与者发信)。法官征集到足够的人数后宣布报名结
束。法官可有条件地选择参与游戏者的名单。报名参加同时进行的几组长线游戏者,应
使用不同的报名ID。

『二:游戏进程』

    1、分配身份

    本程序支配权归法官,可选择分配也可随机分配,法官无需报知板务组。如果参加
人数为8人,则分配为2个警察身份,2个杀手身份,4个平民身份。如果参加人数为11人
,则分配为3个警察身份,3个杀手身份,5 个平民身份。每个身份的具体含义可以参见
本板FAQ。

    分配后法官应以信件方式通知参加者。对于杀手或者警察除了通知其本人身份外还
应通知他其他的杀手或者警察同伙的报名ID。

    2、黑夜


    分配身份完毕后法官应在版面上发表标题为“第一天黑夜”的文章。
    (从这一程序起,每进行下一个程序,法官“宣布”即为在板面上发文公告并以信
件方式通知每个参与游戏者的报名ID。下略)

    杀手经过相互交流后应在24小时内由一人作为代表以报名ID发信告知法官谋杀对象
,法官以第一个发信者的信件为准,此程序原则上不得以其他方式(如电话)进行。

    警察经过相互交流后应在24小时内由一人作为代表发信告知法官验证对象。法官应
尽快回信告知警察被验证者是否杀手。原则同上。

    以上环节结束后法官应在第一夜开始24小时后宣布“ID被杀,请留遗言”。

    法官不得提前结束黑夜程序。

    3、死者留遗言

    死者在收到法官提示信件后应在24小时内尽快发表遗言,格式为“ID遗言”,并将
文章设定为不可回复。(遗言文章不可修改)

    法官在死者遗言完毕可立刻进入下一程序:指正。

    4、指正

    所有幸存者在法官宣布“指正开始”后24小时内必须提出怀疑对象,格式为“ID指
正ID”,并将文章设定为不可回复。
    (指正文章不可修改,内容允许阐述自己的各种观点。)

    法官在所有人都指正完毕后可提前进入下一程序:辩护。

    5、辩护

    法官宣布“辩护开始”,并在文中写明被指正者ID、辩护起止时间(24小时)。

    被指正者在24小时内以“ID辩护”为标题在板面发表文章(辩护原文),在自己的
辩护原文发表之后,可对任何其他被指正者的辩护原文进行回复(辩护re文),每位被
指正(即有辩护资格)的参与游戏者可有n-1篇回复机会(n为被指正者总数,回复对象
可为辩护原文亦可为re文),辩护和回复机会均可放弃。
    (辩护文章、Re文都不得修改)

    法官不许提前结束该程序。

    6、投票

    法官宣布“投票开始”,并在文中写明被指正者ID。所有幸存者在24小时内发信给
法官进行投票,每人必须且只能投一票,此程序原则上不得以其他方式进行。

    幸存者投票时只能写明所投玩家的报名ID,并且投票不得更改(法官以收到的第一
封投票信为准)。法官可在整理出投票情况后宣布。

    法官在投票结束后后可提前进入下一程序。

    投票结果规则:

    A) 一人所得票数超过半数,则法官判其死亡。
        如果被投死的ID为杀手,法官宣布“ID被处决,没有遗言”,并进入程序 7。
        如果被投死ID不是杀手,法官则宣布“ID被处决,请留遗言”。死者应在法官
        宣布后24小时内尽快在板面上发表遗言,并设定为不可回复(遗言文章不可修
        改)。法官可在死者遗言发表后进入程序 7。死者可放弃发表遗言权利,则24
        小时计时终止后法官宣布“ID放弃遗言权利”,并进入程序 7。

    B) 所有人票数均未过半,则得票最多的至少两人再次辩护(如:票数为1233,则
        33辩;票数为1223,则223 辩以此类推),规则同程序5,然后执行程序6。

    C) 如果进行B步骤之后依旧出现平票,但根据B原则再次进入辩护的人减少,则继
        续进行步骤B。以此类推。
        如果同人数平票连续两次,则采用抽签方式决定某个人死亡。返回步骤A。

    D) 杀手在有发言权时发表标题为“ID崩溃”的文章,则法官直接判其死亡。如果
        该杀手为最后一名杀手,法官可立即宣布游戏结束;否则,法官判其死亡,其
        他处于该进程且有发言权的人还有发言机会,该机会可放弃,法官在该进程结
        束时直接宣布下一程序。
        (警察与平民无权崩溃。)

    10、第二夜

    法官发表文章“第二夜开始”并开始重复执行程序2~7。

    11、游戏结束

    A) 杀手、警察或者平民某一阵营全部死亡,则游戏结束。杀手全部死亡,判警察
        与平民获胜。警察全部死亡或者平民全部死亡,均判杀手获胜。

    B) 杀手一方在游戏进程中任意时间可发信给法官主动提出认负,法官核准后也可
        提前结束游戏。

    C) 任何一天程序9结束之后,如杀手人数>=警察人数+平民人数-1,则法官宣布游
        戏结束,杀手获胜。(绝对必胜局)
        相对必胜局概念在长线杀人游戏规则中不予支持。

    D) 因特殊原因造成该组长线无法正常继续进行,经法官提出,板务组核准后,也
        可由法官或板务组宣布提前结束游戏。

『三、限制规则』

    1、 所有参与游戏者,均应尊重、遵守法官与板务组的裁决、判罚。同时尽量做好
应对各种特殊情况的准备,确保不因个人原因影响长线进程。

    2、 游戏进入任何程序均以法官公告为准(除特别注明),玩家不得在法官未宣布
进入某程序前即自行发表该进程规定的文章或信件。

    3、 所有长线游戏中的平民,只允许根据规则发表文章(和投票)进行游戏。所有
长线游戏中的警察或者杀手,除根据规则发表文章外,还可以与自己的同伙进行各种私
下交流,方式不限。(警察或者杀手死亡后只取消其以板面发文方式继续游戏的权利,
但依然保留其与同伙私下交流的权利)

    4、 除以上交流为规则允许外,其余游戏者之间有关本组或其他组进行中的长线游
戏的相互交流均为规则所禁止。任何游戏者不得以任何理由向其他游戏者泄露自己的游
戏身份,也不得采取违规手段套取他人的游戏身份。

    5、 某组长线杀人进行期间,任何非游戏参加者不得在板面发表有关该组长线的文
章。更不得私下为某游戏者打听其他游戏者的身份。该组长线结束后,限制自动解除。

    6、 板务组负责根据长线进程及时在进板画面公布最新的幸存者名单,利用置底等
方式提示游戏参加者当前的游戏进程,及时标记板面长线相关文章并整理进入精华区,
及时删除违规文章等。

    7、Kingkiller板面上一般最多允许三组长线游戏同时进行。

『四、违规处罚』

    1、 参与游戏者在规定时限外发表游戏文章或者信件(投票、杀人、验证),影响
长线进程的,经法官提出,板务组可根据其对游戏影响严重程度以及其给出原因是否合
理给予犯规ID封禁Kingkiller板0 -14天发文权限的惩罚。

    2、 参与游戏者违反限制私聊规定的,经法官提出,版务组可根据其对游戏影响大
小以及其给出原因是否合理给予犯规ID封禁0 -14天发文权限的惩罚。

    3、 法官在游戏过程中有违规行为,该组长线参与者可在板面发文或给板务组发信
投诉,(非参与者投诉只能发信给板务组)并写明违规过程和证据,板务组将根据该犯
规行为对游戏进程影响的严重程度决定给予法官ID封禁0-7天的发文权限的惩罚。以上
处罚均待该组长线杀人结束之后再予执行。

    4、 非游戏参与者违反规则发文、泄露或获取游戏信息的,板务组应及时删除违规
文章,同时根据情节给予犯规ID封禁0 -14天发文权限的惩罚。

    5、 在长线杀人中因违规被处罚者,被封者将被收入【长线违规处罚记录】,违规
记录超过3次者,今后的长线杀人游戏法官可以无条件拒绝其参与游戏。

『五、补充说明』

    1、 本规则以“【规则】长线网络杀人游戏4.0 版”及其补充规定为基础,如有冲
突以本规则为准。

    2、 本规则解释权归我爱南开BBS 站Kingkiller板板务组。

    3、 本规则由发布之日起开始执行。

                                                                2004.2.24 –

2006年01月15日

Google自从出现的那一天起,就一直为大家带来惊喜。各种新奇独特的Google软件层出不穷,如Google桌面、Google Toolbar、Blogger for Word、Google Talk、Google Earth等都各具特色,均有神奇妙用,让大家大呼过瘾。如果你还不了解Google的软件世界,那么以下笔者所介绍的内容,相信一定会让你惊喜不已。
●盛雪锋(全文统一编号:5071001)
1用Google桌面阅读RSS
很多朋友选择下载安装RSS阅读器来阅读来自RSS网站中的资料,其实这样操作稍显复杂,另外RSS阅读器的使用也不是很方便。如果你想寻找一种更加简便的方法,不妨试试Google桌面。大家都知道Google桌面工具栏十分精美,但你是否知道它还具有比普通的RSS阅读器更加方便的RSS阅读功能呢?
软件小档案
软件名称:Google桌面
软件大小:1.62MB
下载地址:http://desktop.google.com/
将软件下载并安装,然后从程序组中运行Google桌面程序,在系统托盘区会新增加一个Google桌面图标,用鼠标右击它,并在弹出的快捷菜单中选择“辅助工具”项,这样你在桌面上就会拥有一个个性十足的Google桌面工具栏了。
点击工具栏顶端的下拉菜单按钮并选择“添加/删除板块”项,在弹出的窗口中将“Web剪辑”项勾选,单击“确定”按钮。这样在Google桌面工具栏中就会新增加一个“Web剪辑”小窗口,用鼠标点击该小窗口顶端的下拉菜单按钮并选择“选项”,在弹出窗口中的网络剪辑列表中添加你要查看的RSS网站的网址,或者通过点击“添加最近的剪辑”按钮来添加你最近所浏览的RSS网站的网址(如图所示)。
这样当该RSS网站的资料有更新时,它就会及时在“Web剪辑”窗口中通知你,如果要查看更新的详细内容,只须点击相应的标题链接即可。使用起来十分方便。
小提示:Google桌面的功能十分强大,它不但提供有新闻、电子邮件、Web剪辑、照片等数十种不同功能的工具面板。而且你还可以根据你个人的需要,随意添加或删除第三方面板,创造属于你个人的面板。
2Google Toolbar
让人英文写作无忧
如果你对自己的英文没有信心,每次写信时你可能就会先在Word中编写,并利用它的拼写检查功能来修正英文文章或语句中的拼写错误,然后再拷贝到电子邮件中,这样虽然能避免出错,但操作过程十分麻烦。为何不用Google Toolbar来帮助你进行英文写作呢?只要利用它的英文纠错功能,就可以直接在IE浏览器中编写邮件,而不用担心会有英文拼写错误了。
软件小档案
软件名称:Google Toolbar
软件大小:550KB
下载地址:http://www.google.com/downloads/
将软件下载,安装运行后,在IE浏览器中会自动出现一个Google工具栏。然后打开电子邮件编写页面并编写好信件的内容,点击Google工具栏中的“Check”按钮(如图所示),系统就会自动检测信件内容是否有拼写错误,并将拼写错误的单词用红色字体标注出来。如果要修正错误的单词,只须在错误的单词上点击鼠标,在弹出的快捷菜单中提供了备选单词,选择拼写正确的单词,就能完成单词拼写错误的修正操作,且修正后的单词字体将以绿色显示。
小提示:Google Toolbar可以自动检测并修正包括英语、德语、法语、西班牙语、意大利语等10种语言单词的拼写错误,能极大地满足不同用户的需求。
3让Word也“博客”
“博客”们如果不用打开浏览器,能在Word中直接撰写、编辑及发布Blog,那该是一件多么令人兴奋的事情啊!其实要实现这一愿望也很容易,只要使用软件Blogger for Word即可。它可以让你在Word中轻松做博客(注:本工具目前仅支持www.blogger.com)。
软件小档案
软件名称:Blogger for Word
软件大小:1.95MB
下载地址:http://desktop.google.com/download/blogger/
BloggerForWordSetup.exe
将软件下载,注意安装时要先将Word程序关闭,待安装完成后,重新打开Word窗口时你会发现多出了一个Blogger工具条。
点击“Blogger Setting”按钮,在弹出的窗口中输入你的Blogger用户名和账号,点击“OK”按钮(如图所示)。这样就让Word与你的博客联结起来了。
然后你就可以在Word中像编辑普通文本那样新建、撰写、修改你的Blog了。当你要发布Blog时,只需点击“Publish”按钮即可。而对于还没有完全写好的文章,可以通过点击“Save Draft”按钮来将它暂时保存,留待以后继续完善。
目前,Blogger for Word可以打开和编辑最新发布的15篇文章,能帮助用户检查是否存在错误的拼写和用词。它对中文字符具有非常好的支持,不管是标题还是正文中的中文都可以正常显示,且Blog的发布速度极快。遗憾的是目前它还不支持文章中图片的发布。
小提示:该软件只能在Windows 2000及以上版本的系统中运行。
4Gmail来信早知道
相信很多人都是Gmail邮箱的忠实用户,由于通过Web进入邮箱页面来查看是否有新邮件到达的操作十分麻烦,导致经常会有一些重要的邮件不能及时被发现并查看,最终可能会给用户造成一定的损失。如果你不想品尝因以上错误留下的苦果,想在第一时间查看新到达的邮件,使用软件Gmail Notifier就是一个不错的解决方案。
软件小档案
软件名称:Gmail Notifier
软件大小:292KB
下载地址:http://www.onlinedown.net/
soft/34082.htm
将软件下载并安装后,就会在系统托盘区出现一个信封图标(如图所示)。
用鼠标右击该图标,并在弹出的快捷菜单中选择“Check Mail Now”项,在弹出的用户登录窗口中输入你的Gmail邮箱账号和密码,点击“确定”按钮后,系统就会自动检测并实时监控该Gmail信箱的邮件内容。如果发现有新邮件到达,就会立即在系统托盘区浮出一个提示小窗口,显示邮件标题和邮件内容摘要等信息。点击相应的邮件信息链接,就可以直接打开Web页面来查看邮件的内容。这样你就再也不用担心会有新邮件到达而你却不知道的情况发生了。另外如果双击右下角的信封图标,还可以打开Gmail的Web页面。为你的工作和生活带来极大的方便。
5足不出户,用Google Earth逛世界
如果你像我一样,虽然喜欢旅游,但却没有足够的经济实力,怎么办呢?那就先用Google Earth来开开眼界吧!相信它一定会带给你一种全新的体验。用它来把地球放到电脑桌面上,坐在电脑前来翱翔世界各地的感觉一定会让你兴奋不已。
软件小档案
软件名称:Google Earth
软件大小:11635KB
下载地址:http://dl.pconline.com.cn/html/1/5/dlid
=13885&dltypeid=1&pn=0&.html
将软件下载。安装运行后,程序就会自动与网络进行连接,若连接成功,最终就会出现一个三维地球图形。此时如果你想去北京逛逛,只需在搜索关键字输入框中输入英文“Beijing”,点击“Search”按钮,屏幕就会以鸟瞰的浏览方式自动飞向北京市区,然后你可以通过地图下面的控制面板来放大、缩小和移动画面图像(如图所示)。
由于Google Earth目前只支持中国较大城市的直接查找,如:北京、上海、西安等。对于不能直接查找的地区,你可以通过手动放大和移动地球来进行查找,也很方便。只要你有足够的耐心,Google Earth就可以帮助逛遍地球的任何地方。而它比普通的平面地图更具真实性,能让你感受到前所未有的视觉冲击。
编后:通过以上介绍,相信你已经初步领略到了Google软件的独特魅力。它们种类繁多,使用简便,分布在IT业的各个领域,其功能也远远超出以上所介绍的范围。因此你要想充分享受它们所带来的乐趣,不妨自己亲自下载试试,相信它们的表现一定会让你满意!

Google不断推出的新功能让人眼花缭乱,最近又向广大站长推出了一项新的服务“Google Analytics”,这项服务为所有网站管理员提供免费的站点访问统计分析系统(该系统来自于Google 3月份收购的Urchin软件公司),让你不用花钱即可了解到自己的网站访问情况。下面让我们看看使用这项服务的几个步骤。
Google Analytics分析系统能帮你做什么?
1.能找出哪些关键字或目标网页带来的回应最多;
2.不必添加关键字代码即可查看Google AdWords(Google关键词广告)投资回报率指标;
3.可以通过关键字跟踪数据并计算投资回报率;
4.无论是对于搜索引擎还是网页,或是电子邮件,都可通过系统进行跟踪分析。
相关链接:
2005年第47期《电脑报》F1版《天下流量Google皆知》
直观的网站统计图
步骤一:提交网站资料
进入http://www.google.com/analytics/zh-CN页面右侧,用你的Gmail账户完成登录,之后点击页面中的“注册”按钮(图1)。在页面中登记你要统计访问量的网站资料(图2),然后点击“继续”,在填写个人信息后点击“继续”。
最后在接受用户协议页面下方勾选“是,我同意上述条款”,然后点击“创建新账户”,完成创建使用该项服务的新账户的工作(实际上就是创建一个网站配置文件)。
提示:网站配置文件是定义要查看的报告的一组规则。通常,网站配置文件和域相对应,即每个域都有一个配置文件,因此可以分别查看每个域的报告。
步骤二:在网站上添加跟踪代码
在创建成功新账户后,从页面中将所提供的一段代码选中(图3),然后执行,打开你的网站首页,将代码添加到网站首页文件的<head>与</head>段落之间。
提示:Google Analytics(分析)会检查跟踪代码是否已正确地添加在网站主页上。当你创建新的配置文件之后,跟踪状态将显示警告“跟踪状态未知”,直到系统检测到跟踪代码。
为了避免出现不能跟踪到的现象,最好进入网页编辑软件中,切换源代码方式,将类似以下的代码放在源代码的<head>部分的所有 <meta> 标记后,最好直接放在</HEAD>之前。
<script src="http://www.google-analytics.com/urchin.js" type="text/javascript">
</script>
<script type="text/javascript">
_uacct="UA-××××-×";
urchinTracker();
</script>
在这里,_uacct=后中的“××××-×”是你注册时的账户编号,这是由注册成功“Google Analytics”后服务器自动给出的,和你的账户有关,你应该直接使用网页上提供的数字,而不要随意更改。
添加代码的工作完成后,在Google Analytics页面中点击“完成”按钮。在新页面中你可以点击“检查状态”按钮来查看网站跟踪功能是否已经生效,同时,在页面下方还可更改网站设置,或者添加新的网站配置文件,也就是说同一个账户下可以添加多个网站信息。
步骤三: 添加访问统计的过滤器
用于统计的过滤器可对最终数据进行操控以便提供准确的报告。单击“添加过滤器”,然后开始创建新过滤器的工作。Google Analytics服务提供了一些预定义的过滤器。现解释如下:
“排除某个域(主机名)的所有网页点击”:使用此过滤器可排除来自特定网络的网页点击,如你的内部工作网络。设置此种过滤器需要你提供此网络的主机名。
“排除某个 IP 地址的所有网页点击”:此过滤器也可以用来排除特定来源的网页点击。你可以输入单个 IP 地址或地址范围。
“仅包括子目录的点击量”:如果想让配置文件只报告某个子域或子目录(如 aaa.example.com 或www.example.com/bbb),就要使用此过滤器。
此外,还可以设置“自定义过滤器”,它提供了更为灵活的过滤规则:“排除”将排除和过滤模式匹配的日志文件行(匹配行),匹配的行将完全被忽略;“包含”将包含和过滤模式匹配的日志文件行(匹配行),所有非匹配的内容将被忽略,并且这些内容的数据无法在最终查看的报告中获得;“搜索和替换”是一种简单的过滤器,可用于查找在某个字段内的模式并用另外一种模式替换找到的模式;“查找表格”则可以让你选择一个查找表格名称。
例如,作为网站管理员,肯定要经常点击自己的网站来例行检查,这个点击量不应归入统计数据,则可以在“过滤器类型”下选择“排除某个IP地址的所有访问量”,然后在下面输入IP地址(图4),至于过滤器名称可以随意。
过滤规则设置后,在页面下方可用的网站配置文件中选中要应用该过滤规则的网站,点“添加”将它加入在“选定的网站配置文件”列表中,最后点击完成。
技巧:跟踪所有子域
如果你希望统计aaa.example.com 和www.example.com 的访问量,则要分别对两个域做如下修改:新建一个过滤器,过滤器类型为:“仅包括子目录点击量”,“子目录”为“^aaa.example.com”,在可用网站配置文件中选“example.com”,添加到选定的网站配置文件中,完成后,再按同样方法添加一个过滤器,过滤器类型同样为“仅包括子目录点击量”,不过子目录应写成“^www.example.com”,然后在可用配置文件中选择“example.com”并添加。这样便可对上述两个子域进行跟踪。
步骤四:授权分析报告访问权限
Google Analytics不仅可让你查看到最终的分析报告,也可以授权其他用户来访问。它能将任何数量的用户添加到你的账户,还能对你的报告授予不同级别的访问权限。你可以在添加新用户时允许访问特定配置文件的报告,也可以修改现有用户的访问权限。添加新用户时授予访问权限的步骤如下:
点击“Analytics(分析)设置”页面下方的“访问管理器”,在新出现的页面中点击“添加用户”,输入其他用户的Gmail地址(必须是Gmail用户)和姓名,并设置其“访问类型”。访问类型有“仅查看报告”和“账户管理员”,除非你希望其他用户也能管理网站配置文件,否则一般选择“仅查看报告”(图5)。选择此用户有权访问的配置文件(对于没有选择的网站配置文件,此用户将无法访问网站的报告),将选择好的配置文件添加到网站配置文件列表中;最后点击“完成”选项完成用户的授权。
步骤五:查看网站分析报告
为了在日后能查看网站访问信息,你需要登录Google Analytics的管理页面,然后在网站配置文件列表中点击要查看网站后面的“查看报告”链接,在打开的页面中来观察网站访问信息。在该网页中,你不仅可查看最近一周的访问量和综合浏览量折线图,也能查看新访量、回访量,还可以知道是分布于哪些地方的人曾经浏览过你的网站,以及他们是通过何种方式(访问量来源)进入你的网站统计图(图6)。
提示:首次添加跟踪代码后,Google Analytics一般每小时更新一次报告,但报告数据可能需要 6 小时左右才会出现在账户管理页面中,而要看到网站访问量,你可能还需要过几天才能得到有关数据。

 Google于近期“偷偷”地发布了一个新功能:Google Suggest,当用户在搜索栏中输入查找请求时,搜索栏中会出现一个下拉列表,列出许多与用户输入的内容相近的提示,供用户选择。

  Google Suggest的主页面如图1所示。从主页面我们可以看到,该功能目前还处于测试阶段。


 

供用户选择Google提示功能新鲜试用
图1 Google Suggest的主页面

  我们来试一下。比如在搜索栏中输入“刘”,立刻就会出现如图2所示的下拉列表,并在每一个提示右侧列出该项被搜索的次数。当列表出现时,移动鼠标指针到一个提示上面并单击,就会搜索该内容并列出搜索结果。

供用户选择Google提示功能新鲜试用
图2 提示列表

  Google的“提示”功能使用大范围信息来预测用户要搜索的内容,列出多数用户经常搜索的问题清单,包括各种搜索内容的整体普及率数据。Google表示,公司没有使用个体搜索历史记录帮助生成提示列表。Google还在Google Zeitgeist列出了搜索内容的排名,我们可以点击该链接查看这个页面,如图3所示,你会发现它与百度的中文搜索风云榜非常类似。

供用户选择Google提示功能新鲜试用
图3 Google Zeitgeist

  使用Google的“提示”功能在某种程度上可以使用户的搜索更加便利和有效,同时Google提供的这些提示还会让你了解全球的网友都对哪些内容比较感兴趣。

2006年01月08日

天极网 1月8日消息(孙淑艳 编译) 据外电报道,Google正在发布一款旨在使计算更安全和方便的免费软件包。

Google的创始人佩奇于当地时间上周五在“消费电子展”(CES)上作主题发言时公布了这款软件包━━Google Pack,它也是Google对微软发动的最新一次攻击。这款软件包旨在使基本软件的安装和维护更方便。


通过这一软件包,Google希望证明,在帮助人们充分利用计算机方面,它比大牌软件厂商━━特别是微软做得更好。Google负责搜索产品和用户体验的副总裁玛丽萨说,我们在考虑这样一个问题:为什么不能更有趣、更简单、更有效地使用计算机?

该软件包中的6款软件属于Google,此前已经分别提供给了用户,一个能够自动将存储在PC中的图像显示为屏保的软件是首次“亮相”。除了一款诺顿反病毒软件只提供6个月的免费试用期外,Google Pack中的其它7款软件都已经被免费提供在互联网上。

玛丽萨表示,Google和Google Pack中其它软件的开发商之间相互无需支付费用。

尽管整合免费软件并非什么新创举,但它却预示着Google可能会有更大的动作。Google正在试图进军桌面软件领域,挑战微软在桌面领域的霸主地位。Forrester资讯公司的分析师沙琳说,如果Google Pack获得成功,会有更多的软件厂商加入,这将使Google在与微软的较量中获得更大的力量。它可能会使Google对软件供应链有更多的控制。

玛丽萨说,目前,Google的兴趣主要在使计算机的使用更容易、更有趣。Google认为,如果人们花更多的时间使用计算机,它就能够获得更多的搜索流量,带来更多的收入。

Google Pack中包含有Adobe的Acrobat Reader、RealNetworks的媒体播放机软件、Mozilla的Firefox浏览器软件、Cerulean Studios的Trillian即时通讯软件,但是,其中却不包含有文字处理和电子表格软件。