DanceFire的专栏

[原]也谈表达式分析和计算

DanceFire — Wed, 04 Feb 2009 12:24:00 +0800

昨天看到王博炜 Blog中《五进制》这篇文章。其中关于5进制到10进制的转换自然没有什么意思，这篇文章给的代码主要是讨论如何进行表达式分析和计算的。作者自制了一个Stack，并且用其形成了两个堆栈分别用于存储数值和运算符。比较典型的表达式处理的方法。从实现上看，代码有些臃肿，而且必要的优化很少，另外就是没有充分利用标准提供的便利。比如那个Stack完全没有必要自制，STL提供的std::stack<T>可以很好的完成任务。

而今天我要做的是，使用boost::spirit来实现同样的表达式分析和计算。众所周知，boost是C++中质量很高的库，被称为准标准库，因为其存在的一个很重要的目的就是为下一代C++库提供预案。目前已经有大量的boost库成为了C++标准库的一部分。我现在要用的是Boost的Spirit库。这个库可以直接在C++代码中撰写EBNF。学过编译原理的朋友应该对此都很熟悉，这是一种比堆栈更灵活的解析表达式甚至程序的方式。

如果我们要处理四则运算的表达式，那么我们只需要在C++中写入下列EBNF的定义：

group = '(' >> expression >> ')'; factor = integer | group; term = factor >> *(('*' >> factor) | ('/' >> factor)); expression = term >> *(('+' >> term) | ('-' >> term));

我们就构成了这个表达式的格式定义，它可以很轻松的处理下列表达式的运算：

12345 -12345 +12345 1 + 2 1 * 2 1/2 + 3/4 1 + 2 + 3 + 4 1 * 2 * 3 * 4 (1 + 2) * (3 + 4) (-1 + 2) * (3 + -4) 1 + ((6 * 200) - 20) / 6 (1 + (2 + (3 + (4 + 5))))

很简单吧？

使用过yacc或者*lex的朋友对这类定义肯定很熟悉。但是所不同的是，他们都是让用户写一个模板，然后用yacc或者*lex处理模板生成相应语言的程序。程序臃肿且很难阅读。而且由于不是自己写的程序，调整起来总要经过一步手续，比较繁琐。

而使用C++的朋友则不用有这种烦恼，Boost的Spirit充分利用了C++强大的语法功能。我们可以直接在程序中写入上述的表达式定义，然后我们的程序就支持这些表达式的处理了。不需要任何额外的程序处理。所需要的仅仅是include一些头文件而已。是的，仅仅是include一些头文件。不要担心需要安装什么额外的东西，或者需要链接什么库，因为Spirit的实现完全是头文件组成的，我们不需要链接任何库。把boost的头文件路径放到编译期中，直接编译就ok了。很轻巧。

下面就是我用Boost Spirit实现的四则运算表达式的代码，由于我的重点是表达式的解析和计算，因此我没有特别处理五进制到十进制的转换问题。但是添加起来显然不麻烦。我只给出了一个五进制整数部分的输出。如果表达式出错，可以直接用箭头指出哪里有错。很方便调试：）而且代码量是原文章的五分之一。编译后也仅仅是35KB，也不是很臃肿的。

大家多了解标准库，多了解Boost，C++的编码也是很有趣味的。

#include <boost/config/warning_disable.hpp> #include <boost/spirit/include/qi.hpp> #include <boost/spirit/include/phoenix_operator.hpp> #include <iostream> #include <string> #include <cmath> #include <limits> using namespace boost::spirit; using namespace boost::spirit::qi; using namespace boost::spirit::ascii; using namespace boost::spirit::arg_names; template <typename Iterator> struct calculator : grammar<Iterator, double(), space_type> { calculator() : calculator::base_type(expression) { expression = term[_val = _1] >> *( ('+' >> term[_val += _1]) | ('-' >> term[_val -= _1]) ); term = factor[_val = _1] >> *( ('*' >> factor[_val *= _1]) | ('/' >> factor[_val /= _1]) ); factor = double_[_val = _1] | '(' >> expression[_val = _1] >> ')' | ('-' >> factor[_val = -_1]) | ('+' >> factor[_val = _1]); } rule<Iterator, double(), space_type> expression, term, factor, number; }; // http://www.jb.man.ac.uk/~slowe/cpp/itoa.html std::string itoa(int value, int base) { const int MAX_DIGITS = 35; const char* DIGITS = "0123456789abcdefghijklmnopqrstuvwxyz"; std::string buf; buf.reserve( MAX_DIGITS ); // Pre-allocate enough space. if (base < 2 || base > 36) return buf; int quotient = value; do { buf.push_back(DIGITS[ std::abs(quotient % base) ]); quotient /= base; } while ( quotient ); if ( value < 0) buf.push_back('-'); std::reverse( buf.begin(), buf.end() ); return buf; } int main(int argc, char* argv[]) { std::cout << "请输入一个表达式，如：3+2.5*(6-25/4)-8.32" << std::endl << std::endl; std::cout << "或输入q退出。" << std::endl << std::endl; std::cout << "> "; calculator<std::string::const_iterator> calc; std::string str; double result; while (std::getline(std::cin, str)) { if (str.empty() || str[0] == 'q' || str[0] == 'Q') break; std::string::const_iterator iter = str.begin(); std::string::const_iterator end = str.end(); bool r = phrase_parse(iter, end, calc, result, space); if (r && iter == end) { std::cout << "输入语法正确，表达式的值为："; if (result == std::numeric_limits<double>::infinity()) std::cout << "∞"; else if (result == std::numeric_limits<double>::quiet_NaN()) std::cout << "结果非数值"; else { std::cout << result << std::endl; std::cout << "整数部分转换为5进制为：" << itoa(static_cast<int>(result), 5); } std::cout << std::endl; } else { std::cout << "[输入的表达式错误]" << std::endl; std::cout << str << std::endl; std::cout << std::string(iter - str.begin(), '-') << "^" << std::endl; } std::cout << std::endl << "> "; } return 0; }

运行结果如下：

请输入一个表达式，如：3+2.5*(6-25/4)-8.32 或输入q退出。 > 3+2.5*(6-25/4)-8.32 输入语法正确，表达式的值为：-5.945 整数部分转换为5进制为：-10 > -6 输入语法正确，表达式的值为：-6 整数部分转换为5进制为：-11 > 6 输入语法正确，表达式的值为：6 整数部分转换为5进制为：11 > 1/0 输入语法正确，表达式的值为：∞ > 23 + 4 ((5)-3* 6) + (-1) [输入的表达式错误] 23 + 4 ((5)-3* 6) + (-1) -------^ > 23 + 4 ( ( 5-3*6) +1) [输入的表达式错误] 23 + 4 ( ( 5-3*6) +1) -------^ > 23 + 4 + ( -5 *3) 输入语法正确，表达式的值为：12 整数部分转换为5进制为：22 >

作者：DanceFire 发表于2009-2-4 12:24:00 原文链接

阅读：2613 评论：0 查看评论

[原]让VS 2008支持Subversion

DanceFire — Sat, 08 Dec 2007 02:48:00 +0800

Visual Studio 2005 有一个开源的Subversion插件，Ankhsvn (http://ankhsvn.tigris.org/)，安装后，VS 2005中将内置Subversion的支持，可以直接在VS里面提交修改。我经常用它和TortoiseSVN 配合来使用Subversion，十分方便。

可是升级到Visual Studio 2008后，发现Ankhsvn没有集成进来，因为目前的Ankhsvn还不支持VS2008，据说下个版本才会支持VS 2008。

不过这不影响我们在Visual Studio 2008中使用Ankhsvn，我们可以自己动手修改注册表，将Ankhsvn集成进VS 2008。方法很简单。

运行 regedit
找到 HKLM/SOFTWARE/Microsoft/VisualStudio/8.0/Addins/Ankh
右键点击它，选择导出，并指定一个文件保存。
用记事本或者其他文本编辑器打开这个文件，将其中的VisualStudio/8.0替换为VisualStudio/9.0。
最后，双击这个修改后的注册表文件，提示是否导入进系统注册表，选择是。

再次打开Visual Studio 2008后，就会发现Ankhsvn已经集成进系统了。

为了方便操作，我写了一个vbscript脚本来进行上述操作。使用很简单，将下面的脚本保存到一个文本文件，命名为ankh.vbs，然后双击该文件即可运行。运行后，重新打开Visual Studio 2008，就会发现Ankhsv已经集成进来了。

顺便再推荐几个常用的免费的插件：

[FREE VISUAL STUDIO ADD-INS]
http://searchwindevelopment.techtarget.com/originalContent/0,289142,sid8_gci1262570,00.html

需要提醒的是，注册表操作不慎可能会导致系统崩溃，因此请谨慎修改注册表。

Dim shell, filename, fso, file, content
Set shell = CreateObject("wscript.shell")
Set fso = CreateObject("Scripting.FileSystemObject")
filename = "ankh.reg"

shell.run "reg export HKLM/SOFTWARE/Microsoft/VisualStudio/8.0/Addins/Ankh " & filename, 1, True

Set file = fso.OpenTextFile(filename, 1, False, True)
content = file.ReadAll
content = Replace(content, "VisualStudio/8.0", "VisualStudio/9.0")
content = Replace(content, ".NET 2005", ".NET 2008")
file.Close()

Set file = fso.OpenTextFile(filename, 2, True)
file.Write content
file.Close()

shell.run "reg import " & filename, 1, true

fso.DeleteFile filename

作者：DanceFire 发表于2007-12-8 2:48:00 原文链接

阅读：9950 评论：4 查看评论

[原]使用XmlWriter时请注意Encoding

DanceFire — Sun, 02 Dec 2007 21:05:00 +0800

这两天用一个常用编辑的软件打开一个最近更新的xml配置文件时突然报编码错误，说不支持utf-16。看到这个错误，我愣了一下，这个软件不支持utf-16的xml我是知道的，但是这个xml配置文件可是用XmlSerializer序列化的一个class，一直都是使用utf-8编码的，怎么突然出utf-16了？用Notepad++打开这个xml，看了一下右下角的编码，显示的还是utf-8，看来文件输出没有错啊，等等，突然注意到第一行：

<?xml version="1.0" encoding="utf-16"?>

咦？文件明明是utf-8，可是xml declaration怎么成utf-16了？赶紧打开以前的xml配置文件对比了一下，发现早期的配置文件的encoding都是utf-8，而从某一天后，都是utf-16了。开始查阅SVN，翻看这段时间涉及到这个序列化的代码变更，发现这段时间唯一可疑的变更就是之前的这个序列化是直接写到文件里的，之前的代码形如：

    XmlSerializer xs = new XmlSerializer(typeof(Site));
    using (StreamWriter sw = new StreamWriter("output.xml"))
    {
        xs.Serialize(sw, site);
    }
    Console.WriteLine(File.ReadAllText("output.xml"));

但是后来由于数据库也需要序列化后的结果，所以将序列化代码移进这个类的ToString()了，之后的代码形如：

    XmlSerializer xs = new XmlSerializer(typeof(Site));
    StringBuilder sb = new StringBuilder();
    using (XmlWriter writer = XmlWriter.Create(sb))
    {
        xs.Serialize(writer, site);
    }
    return sb.ToString();

其中唯一的区别就是一个使用的是TextWriter，而另一个用的是XmlWriter。难道说XmlWriter的Encoding默认是utf-16不成？不是啊，MSDN明明说：

The text encoding to use. The default is Encoding.UTF8.

好吧，我手动加入XmlWriterSettings，结果形如：

    XmlSerializer xs = new XmlSerializer(typeof(Site));
    StringBuilder sb = new StringBuilder();
    XmlWriterSettings settings = new XmlWriterSettings();
    settings.Encoding = Encoding.UTF8;
    settings.Indent = true;
    using (XmlWriter writer = XmlWriter.Create(sb, settings))
    {
        xs.Serialize(writer, site);
    }
    return sb.ToString();

手动将XmlWriter设置为utf-8，这回该好了吧？呵呵，如果好了就没这篇Blog了。很不幸，依旧输出encoding="utf-16"。见鬼了，难不成XmlWriter不支持utf-8？用脚趾头也可以想象这不大可能。又翻开MSDN Library，好好看看到底问题在哪里。

终于在XmlWriterSettings.Encoding的文档里面发现下面一段话：

This property only applies to XmlWriter instances that output text content to a stream; otherwise, this setting is ignored.

看来XmlWriter只支持在Stream类的输出中设置Encoding。其实仔细想想也可以理解，只有stream类的输出，Encoding才可以用来进行编码，对于我们现在使用的StringBuilder来说，Xml的输出直接就变成了字符串了，没有任何编码过程，因此Encoding失效了。

可以说当我们使用StringBuilder的时候，StringBuilder的Encoding overwrite了XmlWriter的Encoding，而StringBuilder将会用StringWriter来包装，StringWriter.Encoding是Encoding.Unicode，也就是utf-16。因此，当我们使用StringBuilder作为XmlWriter的输出时，XmlWriter的Encoding就成了utf-16。而当我们把这个内存中的字符串，以utf-8写入文件的时候，虽然此时编码实际上为utf-8，但是并没有人负责把Xml声明的encoding="utf-16"改回"utf-8"了。错误就这样发生了。

问题明确了，解决起来并不复杂，我们用MemoryStream替换StringBuilder，形如：

    XmlSerializer xs = new XmlSerializer(typeof(Site));
    MemoryStream stream = new MemoryStream();
        XmlWriterSettings setting = new XmlWriterSettings();
       setting.Encoding = new UTF8Encoding(false);
       setting.Indent = true;
    using (XmlWriter writer = XmlWriter.Create(stream, settings))
    {
        xs.Serialize(writer, site);
    }
    return Encoding.UTF8.GetString(stream.ToArray());

这回输出就正常了。这里需要注意的是Encoding那一行，这是设置Encoding不要输出BOM，否则生成的字符串前会有几个字节表示Byte Order。

因此，提醒诸位，如果使用非Stream类的输出，如StringBuilder/StringWriter，作为XmlWriter输出的话，请注意你的xml的Encoding。

关于BOM，请参考：

Byte Order Mark (BOM) FAQ
http://unicode.org/faq/utf_bom.html#BOM

Byte-order mark (wikipedia)
http://en.wikipedia.org/wiki/Byte_Order_Mark

作者：DanceFire 发表于2007-12-2 21:05:00 原文链接

阅读：4162 评论：4 查看评论

[原]Visual Studio 2008 LINQ to SQL 的Beta 2测试版和RTM正式版的差异

DanceFire — Tue, 27 Nov 2007 23:04:00 +0800

Follow Scott Guthrie 的例子学习LINQ，结果找了半天也没有找到Table<TEntity>Add()这个函数，查了MSDN，也没看到，我还以为是static的Class Extension添加的方法呢，正郁闷着到底是少reference了哪个库。呵呵，结果进一步搜索才发现，原来RTM把Table<TEntity>Add()改名为 Table<TEntity>InsertOnSubmit()。这个改名语义更强了，改得确实对的，不然现在有很多人在论坛上问为什么Add()后数据库没变化。Scott Guthrie的Blog上似乎也没说啥，哎，让我这一头雾水呢。找了几个别人总结的差异，大家可以参考一下，用惯了Beta 2的人别想当然，看看有哪些改动。

这些是论坛上找到的关于LINQ to SQL 的Beta 2 到 RTM的改变的讨论：

LINQ to SQL Beta2 to RTM Key Changes

PLEASE READ: Beta2 to RTM Changes in Attach() Behavior

Beta2 to RTM change: XML column default mapping changed to XElement instead of XDocument

LINQ to SQL breaking changes from beta2 to RTM (compiled from my LINQ forum posts)

LINQ to SQL: What is NOT in RTM (V1)

LINQ to SQL: features not in the designer / SqlMetal

后来，微软发了一个文章讲解从Beta 2 => RTM .Net Framework都有哪些变动。这个是微软官方推出的 LINQ to SQL 的Beta 2 to RTM的改动文档：

LINQ to SQL Breaking Changes from Visual Studio 2008 Beta 2 to RTM (docx)

这个文档是Office 2007的docx格式，如果用其他版本打开还需要插件。我把这个文件转换成了PDF格式，可能更方便大家阅读。可以从这里下载：

LINQ to SQL Breaking Changes from Visual Studio 2008 Beta 2 to RTM (pdf)

作者：DanceFire 发表于2007-11-27 23:04:00 原文链接

阅读：4307 评论：0 查看评论

[原]写了一个开源的ASP.Net的系统信息探针（适用于MS.Net 1.x/2.0和Mono 1.0/2.0）

DanceFire — Sun, 25 Nov 2007 12:26:00 +0800

简介

这两天由于需要一个ASP.Net的服务器信息探针。到网上找了找，似乎没有发现什么开源的ASP.Net的系统信息探针（探测器）。由于技术含量不是很高，于是干脆自己动手丰衣足食了。

到网上找了一下各个ASP.Net系统信息探针，把功能总结了一下，基本上都实现出来了。既然实现了就别藏着掖着了，也没什么技术含量，拿出来开源好了。有谁有更好的想法可以告诉我，如果不费劲，我就加进去。

我把这个放到Google code hosting上面了，需要的可以从上面下载：

http://aspnetsysinfo.googlecode.com/

我这个ASP.Net的系统信息探针与其它探针最大的不同处，是我这个探针除了支持Windows平台的IIS服务器环境，它还支持Linux下的Mono假设的ASP.Net环境。为了让探针更通用，我用反射进行调用2.0相关的类库，在1.0下或者Linux下面，使用不同的方式取得同样的信息。所以我的这个探针支持的系统平台应该是最广的。包括Windows下的.Net 1.0/1.1/2.0 以及以上，和Linux下的Mono环境的Mono 1.x 无论是Mono .Net 1.0还是Mono .Net 2.0都可以运行。

目前支持探测的信息有：

探测的信息

系统信息

服务器名
服务器IP
服务器域名
服务器端口
Web服务器版本
请求链接的虚拟路径
请求链接的物理路径
应用程序根路径的虚拟路径
应用程序根路径的物理路径
操作系统
操作系统安装的目录
.Net 版本
.Net 语言
服务器当前时间
服务器持续开机时间
脚本超时时间

处理器信息

处理器个数
处理器Id
处理器类型
处理器Level
处理器OEM Id
页面大小

内存信息

.Net应用程序所影射的当前工作内存大小
物理内存大小
物理空闲内存大小
物理使用空间大小
页面文件大小
可用页面文件大小
虚拟内存大小
可用内存大小

存储器信息

逻辑驱动器信息
驱动器名
卷标
驱动器文件格式 (FAT32, NTFS...)
驱动器类型 (固定硬盘，CDROM...)
空闲和全部的空间

Request Headers

Server Variables

环境变量

Session Information

系统 COM 组件

Adodb.Connection
Adodb.RecordSet
Adodb.Stream
Scripting.FileSystemObject
Microsoft.XMLHTTP
WScript.Shell
MSWC.AdRotator
MSWC.BrowserType
MSWC.Counters
MSWC.NextLink
MSWC.PermissionChecker
MSWC.Status
MSWC.Tools
IISSample.ContentRotator
IISSample.PageCounter

邮件 COM 组件

JMail.SMTPMail
JMail.Message
CDONTS.NewMail
CDO.Message
Persits.MailSender
SMTPsvg.Mailer
DkQmail.Qmail
SmtpMail.SmtpMail
Geocel.Mailer

上传 COM 组件

LyfUpload.UploadFile
Persits.Upload
Ironsoft.UpLoad
aspcn.Upload
SoftArtisans.FileUp
SoftArtisans.FileManager
Dundas.Upload
w3.upload

图像 COM 组件

SoftArtisans.ImageGen
W3Image.Image
Persits.Jpeg
XY.Graphics
Ironsoft.DrawPic
Ironsoft.FlashCapture

其他 COM 组件

dyy.zipsvr
hin2.com_iis
Socket.TCP

使用方法

请从下载页面下载当前版本的zip文件，解压缩后，将 info.aspx 文件置于服务器上任何可以执行 *.aspx 的目录下，然后通过浏览器访问该文件即可。

如，置于服务器 www.example.com 的Web根目录下，那么通过 http://www.example.com/info.aspx，就可以看到结果。

需求

该页面支持Windows的IIS服务器和Linux/Unix下的装有Mono的Apache服务器。

作者：DanceFire 发表于2007-11-25 12:26:00 原文链接

阅读：3895 评论：3 查看评论

[原]C#匿名方法的应用二则–实现异常Retry机制和WinForm线程安全访问

DanceFire — Wed, 07 Nov 2007 23:16:00 +0800

用C# 2.0的朋友可能会经常使用匿名方法(Anonymous Methods)和匿名委托(Anonymous Delegate)。在这里我说2个比较常用的应用环境。

1、Retry机制

C#和C++, Java一样拥有异常处理机制，我相信很多朋友和我一样，第一次接触异常的时候，都非常希望异常能够像内核捕获内存page fault异常一样类似的拥有Retry（重试）的机制，很可惜这些语言中都没有给我们提供Retry机制。

当然原因有很多，比如如果重试，那么到底是重试哪部分代码呢？是try{}catch{}中的代码？还是发生异常那一行的代码？重试多少次？重试之间是不是要再等一会儿？如果再失败怎么处理？而且如果不同层有Retry，那么会出现Retry次数以乘法形式递增（底层Retry 5次，高层Retry 3次，那么实际Retry次数将达到15次）。

在应用环境中的Retry不比内核，处理后只需要重新执行产生异常的那一条指令，应用环境的要求要更复杂。

可是在实际应用中，特别是面对网络应用时候，有可能会有大量的类似于TimeOut(超时)、或者外部资源被临时占用、暂时性的设备较忙的异常产生，只要再重试几次就会正常。如果此时将raise异常，并且扔向更高层，显然是不太明智的。于是就开始有人用有限次循环的办法来模拟Retry。典型的代码如下：

    public static void TraditionalSolution()
    ...{
        int retryTimes = 10;
        
        for (int i = 0; i < retryTimes; ++i)
        ...{
            try
            ...{
                //    do something here, 
                //    such as call WebClient to fetch a webpage.
                //    the code might throw an exception.
                break;
            }
            catch (Exception)
            ...{
                if (i == retryTimes - 1)
                ...{
                    throw;
                }
                else
                ...{
                    System.Threading.Thread.Sleep(TimeSpan.FromSeconds(5));
                }
            }
        }
    }

使用这样的代码可以成功的实现Retry，如果中间的代码发生异常，循环体会捕捉到，如果没有到达retryTimes的要求，那么继续重复执行中间的过程。每次retry前都会先等待5秒钟。如果到达retryTimes后依旧还发生异常，那就没办法，throw到上层。这段代码很典型，在C++和Java中也可以使用类似的方式进行处理。

这段代码的缺点就是，这层循环、等待、判断循环终结抛出异常的代码总要附着在你需要retry的代码块外面的事情周围。如果程序中有不少需要retry的地方，这部分代码反复出现就显得很臃肿了。而且，如果这段代码有一点小小的错误，或者有更多的需求加入进去，要同步项目中其它地方retry代码，这就很不合理了。下面我们就利用C#的匿名方法(anonymous methods)和匿名委托(anonymous delegate)来美化我们的代码。

首先，我们先声明一个无参数委托。

public delegate void NoArgumentHandler();

然后，我们写一个专门处理Retry机制的函数。

    public static void Retry(int retryTimes, TimeSpan interval, bool throwIfFail, NoArgumentHandler function)
    {
        if (function != null)
        {
            for (int i = 0; i < retryTimes; ++i)
            {
                try
                {
                    function();
                    break;
                }
                catch (Exception)
                {
                    if (i == retryTimes - 1)
                    {
                        if (throwIfFail)
                        {
                            throw;
                        }
                        else
                        {
                            break;
                        }
                    }
                    else
                    {
                        if (interval != null)
                        {
                            System.Threading.Thread.Sleep(interval);
                        }
                    }
                }
            }
        }
    }

这段代码实现了前面代码的Retry机制，把需要执行的部分，换成了NoArgumentHandler的函数参数。使用者可以定义function()执行需要retry的次数，retry间隔的等待时间，当retryTimes跑完后，依旧未能成功地话，是否抛出这个异常。

最后，我们应用这个Retry()函数。大家都看到了delegate，那么我们需要对每一个retry块都定义一个函数么？不需要了，C# 2.0早就提供了anonymous methods（匿名方法）来处理。我们看一下，新的Retry调用代码：

    public static void NewApproach()
    {
        //    ...
        Retry(10, TimeSpan.FromSeconds(10), true, delegate
        {
            //    do something here,
            //    such as call WebClient to fetch a webpage.
            //    the code might throw an exception.
        });
        //    ...
    }

这样我们的Retry代码简洁多了。对现有代码增加Retry机制，只需要加上一层括号就可以了，而且Retry行为可以很方便的在参数上调整。
我们可以进一步注意到delegate后面连()也省略掉了，也就是说delegate没有函数调用签名，我们这里使用的是匿名委托(anonymous delegate)，让C#编译器去自己推导正确的delegate类型。在这个case里面，由于Retry()对应位置只有NoArgumentHandler一个delegate类型，因此，将delegate{}自动视为NoArgumentHandler类型。

如果有什么进一步需求的话，可以自己改进Retry()函数，定制为自己的Retry()。举个例子，可以为Retry()再增加一个delegate函数参数，用以进行异常发生后的处理。

注意：Retry机制很方便用，但是不要过分使用Retry。特别是在不同层使用Retry的时候更要细心。特别要注意乘法效应导致Retry次数和时间成倍增长的情况，否则反而不美。

2、WinForm 的线程安全的访问

用C#写Windows程序少不了要写WinForm程序。很多时候，我们还需要写多线程的WinForm应用。最典型的就是为了不因为核心代码执行影响用户对应用程序的响应，当执行一个比较耗时的操作时，为了方式用户界面死掉的情况，常需要建立一个背景线程去运行耗时的代码，并且实时将结果表现在当前窗口上。

在多线程访问WinForm的时候，我们会注意到，WinForm的那些Control不是线程安全的。因此不建议直接访问它们，否则会导致竞争冒险，甚至可能出现死锁。比如在线程中直接使用下面的代码就是不推荐的：

textBox1.Text = “OK”;

微软建议的办法，使建立一个SetTextBox(string text)的函数，里面写上上面这句。然后判断this.InvokeRequired，如果需要，就调用this.Invoke(SetTextBox, “OK”);，否则直接调用textBox1.Text = “OK”。

总结一下会发现，这个建议的方法不合理，因为同样是textBox1.Text = “OK”; 在不同的位置上被写了两次。两次？惊醒。凡是同一个东西，在不同的位置出现了两次，我们就需要惊醒了。很多安全问题都是由于这种两个不同位置表达一个意思而造成。如果修改了一个地方，而忘了修改另一个地方怎么办？如果是数据的话，还会出现，用户代码到底会用哪个数据作为基准？虽然程序员在“尽量”保证两个位置一致，但是历史已经无数次告诉我们这种“尽量”非常不可靠。那么我们如何解决这个问题呢？这次匿名方法和匿名委托又一次显身手了。

首先，我们定义一个线程安全的访问Control的函数 DoThreadSafe()：

        private static void DoThreadSafe(Control control, MethodInvoker function)
        {
            if (function != null)
            {
                if (control.InvokeRequired)
                {
                    control.Invoke(function);
                }
                else
                {
                    function();
                }
            }
        }

这里的代码实现了微软推荐的采用InvokeRequired判断，然后通过Invoke()调用具体操作的逻辑，但是通过入口的MethodInvoker function函数参数避免了同一个东西被写两次的情况。这里MethodInvoker是System.Windows.Forms名字空间下的一个delegate，和上面的NoArgumentHandler定义一样：

delegate void MethodInvoker();

有了这个小小的帮助函数，我们写线程安全的 WinForm 操作就很简单了，比如，这回我们需要设置进度条的Value：

        private void SetProgressBar(int value)
        {
            DoThreadSafe(progressBar1, delegate
            {
                progressBar1.Value = value;
            });
        }

凡是需要访问 WinForm 空间，我们都包裹上这么一行代码，就能够保证对WinForm所作的操作时线程安全的了，很方便。

如果进一步注意，我们会发现，虽然我们的delegate是无参数传递的，但是，在上面的调用代码里面，prograssBar1.Value = value，这个value是delegate外的函数地参数。神奇吧？这是合法的，虽然名义上，这是一个匿名方法，已经不属于当前scope了，但是依旧可以访问当前scope里面的变量，这就给我们很大的便利，我们可以充分利用这一点，而不再需要定义各种各样的有参数的delegate来完成对不同控件所需要的线程安全的操作。呵呵，否则，按照微软的建议，那几乎是要对WinForm上每一个元素都做一个SetXxxxxText(string text), GetXxxxxText()函数了。

这个小小的DoThreadSafe()，大大降低了对那些Delegate的需求，并且利用匿名方法(anonymous methods)大大减少了声明函数的工作量。（当然实际上编译器在生成执行代码的时候会帮你自动产生对应的函数，不信你就用Reflector来看看。）

3、总结

匿名方法可以降低另写method的工作量，而且匿名方法可以访问调用者同scope的变量，利用这点我们可以大大简化委托的声明，和降低传参的复杂度。

好好的利用匿名方法和匿名委托，会让你的代码看起来更加优雅，优雅的代码也会降低错误发生的可能性。

作者：DanceFire 发表于2007-11-7 23:16:00 原文链接

阅读：3561 评论：0 查看评论

[原]中科院中文分词系统ICTCLAS之人名识别词典分析

DanceFire — Sun, 13 May 2007 06:13:00 +0800

前言、

请在阅读本文前，先确认已阅读过论文《张华平,刘群.基于角色标注的中国人名自动识别研究》。

论文把与人名相关的词分为了15个角色，通过词典查询，可以判断某些文字、词所属角色，然后根据模式匹配找到匹配上的名字。

当我分析nr.dct的时候，却发现nr.dct并非完全按照论文所描述的进行的角色划分。以下是我对tag统计后的nr.dct的内容，能够在论文中找到含义的，我标注上了含义。

Tag Count:
    Tag = B(  1), Count =   513,    姓氏
    Tag = C(  2), Count =   955,    双名的首字
    Tag = D(  3), Count = 1,043,    双名的末字
    Tag = E(  4), Count =   574,    单名
    Tag = F(  5), Count =     3,    前缀
    Tag = G(  6), Count =     9,    后缀
    *Tag = K( 10), Count =     0,   人名的上文
    Tag = L( 11), Count = 1,198,    人名的下文
    Tag = M( 12), Count = 1,684,    两个中国人名之间的成分
    Tag = N( 13), Count =    67,    <无>
    *Tag = U( 20), Count =     0,   人名的上文与姓氏成词
    *Tag = V( 21), Count =     0,   人名的末字与下文成词
    Tag = X( 23), Count =    84,    姓与双名首字成词
    Tag = Y( 24), Count =    47,    姓与单名成词
    Tag = Z( 25), Count =   388,    双名本身成词
    Tag = m( 44), Count =    58,    <无>
    Tag = *(100), Count =     1,    始##始
    Tag = *(101), Count =     1,    末##末

一、关于粗分结果的切分

我们可以从这个统计结果看出，nr.dct中并没有U和V这两个标签，那ICTCLAS如何修正在粗分情况下错误切分的词语呢？据两个例子：

1、"邓/颖/超生/前/使用"

其中的"超生"就必须切开，分成"超/生"，后期才可进一步的标注。

2、"叶/莲/美的/一位/亲戚"

其中"美的"必须切开，分成"美/的"，后期才可进一步的标注。

首先是很不幸，对于上面第一个例子FreeICTCLAS无能为力，因为现在的ICTCLAS的nr.dct里面根本没有"超生"这个词，也就是说，如果粗分结果出现了"超生"这个错误组合了部分人名的词，那么ICTCLAS无法将其拆开从而正确识别人名。

那么对于第二个例子呢？

根据对现有的ICTCLAS的分析，注意到关于切分的地方有这么一个代码

if(m_tagType==TT_NORMAL||!dictUnknown.IsExist(pWordItems[nWordsIndex].sWord,44))
{
    //      如果TT_NORMAL 或者NE词典中无此词（with tag 44）
    //      将该词放到m_sWords[i]中，调整m_nWordPosition[i+1]的位置。
    strcpy(m_sWords[i],pWordItems[nWordsIndex].sWord);//store currentword
    m_nWordPosition[i+1]=m_nWordPosition[i]+strlen(m_sWords[i]);
}
else
{
    if(!bSplit)
    {
        strncpy(m_sWords[i],pWordItems[nWordsIndex].sWord,2);//storecurrent word
        m_sWords[i][2]=0;
        bSplit=true;
    }
    else
    {
        unsigned int nLen=strlen(pWordItems[nWordsIndex].sWord+2);
        strncpy(m_sWords[i],pWordItems[nWordsIndex].sWord+2,nLen);//storecurrent word
        m_sWords[i][nLen]=0;
        bSplit=false;
    }
    m_nWordPosition[i+1]=m_nWordPosition[i]+strlen(m_sWords[i]);
}

其中：

dictUnknown.IsExist(pWordItems[nWordsIndex].sWord,44)

到未登录词词典中去寻找标签为44的当前词，由此判定的是否继续执行切分操作。44是谁呢？前面的统计结果中已经有了：

Tag = m( 44), Count = 58, <无>

标签44(m)没有任何对应于论文的说明。关于切分，论文只提到了对于U、V的切分。那m是U还是V呢？因为一共就58个，所以我列出了所有Tag=44的项，大家可以看一下：

Key: 三和      ID=     2,564  (Tag=44, Frequency=1)
Key: 东家      ID=       744  (Tag=44, Frequency=1)
Key: 之和      ID=     4,052  (Tag=44, Frequency=1)
Key: 健在      ID=     1,490  (Tag=44, Frequency=7)
Key: 初等      ID=       482  (Tag=44, Frequency=2)
Key: 到时      ID=       672  (Tag=44, Frequency=1)
Key: 前程      ID=     2,379  (Tag=44, Frequency=1)
Key: 华为      ID=     1,306  (Tag=44, Frequency=3)
Key: 华以      ID=     1,307  (Tag=44, Frequency=1)
Key: 同江      ID=     3,024  (Tag=44, Frequency=1)
Key: 和田      ID=     1,229  (Tag=44, Frequency=2)
Key: 国是      ID=     1,172  (Tag=44, Frequency=1)
Key: 国都      ID=     1,164  (Tag=44, Frequency=1)
Key: 图说      ID=     3,057  (Tag=44, Frequency=1)
Key: 在理      ID=     3,889  (Tag=44, Frequency=1)
Key: 天王      ID=     2,989  (Tag=44, Frequency=1)
Key: 子书      ID=     4,247  (Tag=44, Frequency=1)
Key: 子孙      ID=     4,248  (Tag=44, Frequency=1)
Key: 学说      ID=     3,506  (Tag=44, Frequency=1)
Key: 对白      ID=       780  (Tag=44, Frequency=1)
Key: 帅才      ID=     2,828  (Tag=44, Frequency=1)
Key: 平和      ID=     2,305  (Tag=44, Frequency=2)
Key: 怡和      ID=     4,448  (Tag=44, Frequency=1)
Key: 慈和      ID=       538  (Tag=44, Frequency=1)
Key: 成说      ID=       444  (Tag=44, Frequency=1)
Key: 文说      ID=     3,186  (Tag=44, Frequency=3)
Key: 新说      ID=     3,416  (Tag=44, Frequency=5)
Key: 明说      ID=     2,130  (Tag=44, Frequency=4)
Key: 有请      ID=     3,772  (Tag=44, Frequency=1)
Key: 来时      ID=     1,817  (Tag=44, Frequency=1)
Key: 来由      ID=     1,820  (Tag=44, Frequency=1)
Key: 永不      ID=     3,746  (Tag=44, Frequency=1)
Key: 清谈      ID=     2,434  (Tag=44, Frequency=1)
Key: 清还      ID=     2,429  (Tag=44, Frequency=6)
Key: 特等      ID=     2,957  (Tag=44, Frequency=1)
Key: 王开      ID=     3,115  (Tag=44, Frequency=1)
Key: 生就      ID=     2,674  (Tag=44, Frequency=1)
Key: 石向      ID=     2,720  (Tag=44, Frequency=4)
Key: 维和      ID=     3,152  (Tag=44, Frequency=1)
Key: 美的      ID=     2,075  (Tag=44, Frequency=3)
Key: 老是      ID=     1,852  (Tag=44, Frequency=1)
Key: 良将      ID=     1,938  (Tag=44, Frequency=1)
Key: 若是      ID=     2,556  (Tag=44, Frequency=1)
Key: 行将      ID=     3,450  (Tag=44, Frequency=1)
Key: 远在      ID=     3,847  (Tag=44, Frequency=3)
Key: 长发      ID=       388  (Tag=44, Frequency=1)
Key: 鲁迅文学奖     ID=     2,005  (Tag=44, Frequency=1)
Key: 茅盾文学奖     ID=     2,059  (Tag=44, Frequency=3)

其中有我们刚才说的"美的"，也就是说第二个例句 "叶/莲/美的/一位/亲戚" 会因为这个Tag=m的"美的"词条而成功的被切分为两条。

从这个例句，我们感觉，Tag=m相当于论文里的V，既"人名的末字与下文成词"。可是真的是这样么？

当我继续搜索标签为44的"天王"这个词条的时候，我注意到了199801人民日报语料中只有一条句子和拆分有关：

"前几天王老头刚收到小孩寄来的照片"

这句话是"人名的上文与姓氏成词"，也就是对应于论文的U。

这回就乱套了，"m"既对应U又对应V。按照上面拆分的代码，不管任何情况，将m的第一个字拆出来。

做为V还好说，第一个字是名字的末字。但是对于U来说，可就完全不见得了，对于U，应该是拆除了最后一个字的部分。二者交集只有一种特例情况，就是m的词长是2个字。这样拆第一个字和拆最后一个字事实上一样。观察上面Tag=m的词条，我们会发现，除了"茅盾文学奖"和"鲁迅文学奖"这两个莫名其妙的词条外，其余的词条全都是两个字的。词长上满足刚才说的特例。

难道就没有3个字的U和V了么？我相信肯定会有满足U或者V的三字词、四字词，这才是更通用的情况，而FreeICTCLAS里面将U,V特例化成了只允许为2字的词。估计也是因为这个原因，也就没有对应它为U或者V，而是用了另一个字母小写m来表示。

总结一下，FreeICTCLAS实际上并没有真正的实现论文中所说的U,V这两个需要切分的Tag，取而代之的是一个在2个字成词的特例情况下等效的m来针对两个字成词的特例进行处理。

二、关于前缀、后缀的思考

关于FreeICTCLAS中判定词的Pattern有下列几种：

//BBCD:姓+姓+名1+名2;
//BBE: 姓+姓+单名;
//BBZ: 姓+姓+双名成词;
//BCD: 姓+名1+名2;
//BE:  姓+单名;
//BEE: 姓+单名+单名;韩磊磊
//BG:  姓+后缀
//BXD: 姓+姓双名首字成词+双名末字
//BZ:  姓+双名成词;
//B:   姓
//CD:  名1+名2;
//EE:  单名+单名;
//FB:  前缀+姓
//XD:  姓双名首字成词+双名末字
//Y:   姓单名成词

下面是nr.dct关于前缀的词条：
Tag = F, 前缀

Key: 大         ID=       588  (Tag=5, Frequency=3)
Key: 老         ID=     1,834  (Tag=5, Frequency=56)
Key: 小         ID=     3,359  (Tag=5, Frequency=68)

下面是nr.dct关于后缀的词条：

Tag = G, 后缀

Key: 哥         ID=     1,014  (Tag=6, Frequency=2)
Key: 公         ID=     1,071  (Tag=6, Frequency=13)
Key: 姐         ID=     1,579  (Tag=6, Frequency=4)
Key: 老         ID=     1,834  (Tag=6, Frequency=32)
Key: 某         ID=     2,157  (Tag=6, Frequency=40)
Key: 嫂         ID=     2,573  (Tag=6, Frequency=14)
Key: 氏         ID=     2,758  (Tag=6, Frequency=14)
Key: 帅         ID=     2,827  (Tag=6, Frequency=18)
Key: 总         ID=     4,269  (Tag=6, Frequency=2)

关于前缀、后缀也有些不解。

既然可以如下成词：

//FB: 前缀+姓
//BG: 姓+后缀

那么"张老师"、"周总理"这种两个字的后缀为什么没有收录进来呢？
另外，前缀也有可能是2个字的，比如"馄饨侯"、"泥人张"、"年糕陈"，在前缀中也没有收录进来。

那么"老师"，"总理"这么常用的后缀在词库里是什么呢？

Key: 总理      ID=4,281
    (Tag=11, Frequency=105)
    (Tag=12, Frequency=110)

Key: 老师      ID=1,851
    (Tag=12, Frequency=27)

11是L(实际上是论文中的K)，人名的上文；12是M(实际上是论文中的L)，人名的下文。

在语料库寻找一番后，注意到，"周总理"被标注为"周/nr 总理/n"，并不将二者合并为一个人名，做为同位语处理，后者为名词。因此估计所有两个字的前缀、后缀都是这样进行的标注，而这里所谓的前缀、后缀只是针对单字情况下的前缀、后缀。

三、关于(B)姓氏中出现的错误词条

(B)中有一些词条是不合理的。比如"建军"被标注为B，显然应该拆分为建C军D；而

Key: 孔子 ID=1,779
(Tag=1, Frequency=5)

应该把"子"做为后缀G，"孔"为姓氏B，形成BG搭配。在Tag为B中，有大量的这类的例子。我感觉这是在根据语料库学习过程中，预处理程序做的不够好，从而导致了这种现象。论文中提到，北大标注的语料库没有能够区分姓和名，这应该是导致nr.dct词典里姓名标注错误的主要原因。而且我怀疑，前面的前缀、后缀是人工总结的，而不是自动抽取出来的。

四、关于论文中的(K)人名的上文、(L)人名的下文、(M)两个中国人名之间的成分

这三个角色如果按照论文中的字母去找，一定会出问题。

需要注意，词典中没有标签为K，人名的上文，的词条。却多出来一个N，论文中没有对应条目。我将N对应的词条贴出来：

[ 13]    Key: 帮助     ID=       181  (Tag=13, Frequency=1)
[ 13]    Key: 保        ID=       189  (Tag=13, Frequency=1)
[ 13]    Key: 保山     ID=       192  (Tag=13, Frequency=1)
[ 13]    Key: 背着     ID=       212  (Tag=13, Frequency=1)
[ 13]    Key: 并        ID=       280  (Tag=13, Frequency=1)
[ 13]    Key: 部署     ID=       326  (Tag=13, Frequency=1)
[ 13]    Key: 称        ID=       430  (Tag=13, Frequency=1)
[ 13]    Key: 称赞     ID=       431  (Tag=13, Frequency=1)
[ 13]    Key: 出局     ID=       489  (Tag=13, Frequency=1)
[ 13]    Key: 代表     ID=       630  (Tag=13, Frequency=1)
[ 13]    Key: 的        ID=       685  (Tag=13, Frequency=2)
[ 13]    Key: 对        ID=       779  (Tag=13, Frequency=19)
[ 13]    Key: 分析     ID=       874  (Tag=13, Frequency=1)
[ 13]    Key: 夫人     ID=       905  (Tag=13, Frequency=26)
[ 13]    Key: 赶到     ID=       959  (Tag=13, Frequency=1)
[ 13]    Key: 告诉     ID=     1,012  (Tag=13, Frequency=1)
[ 13]    Key: 给        ID=     1,036  (Tag=13, Frequency=2)
[ 13]    Key: 共诛     ID=     1,085  (Tag=13, Frequency=1)
[ 13]    Key: 和        ID=     1,227  (Tag=13, Frequency=76)
[ 13]    Key: 欢迎     ID=     1,324  (Tag=13, Frequency=1)
[ 13]    Key: 会见     ID=     1,365  (Tag=13, Frequency=3)
[ 13]    Key: 及        ID=     1,410  (Tag=13, Frequency=2)
[ 13]    Key: 将        ID=     1,509  (Tag=13, Frequency=1)
[ 13]    Key: 讲话     ID=     1,524  (Tag=13, Frequency=1)
[ 13]    Key: 交代     ID=     1,530  (Tag=13, Frequency=1)
[ 13]    Key: 接到     ID=     1,555  (Tag=13, Frequency=1)
[ 13]    Key: 来到     ID=     1,813  (Tag=13, Frequency=1)
[ 13]    Key: 老伴     ID=     1,836  (Tag=13, Frequency=1)
[ 13]    Key: 女儿     ID=     2,235  (Tag=13, Frequency=2)
[ 13]    Key: 陪        ID=     2,274  (Tag=13, Frequency=1)
[ 13]    Key: 陪同     ID=     2,276  (Tag=13, Frequency=1)
[ 13]    Key: 妻子     ID=     2,332  (Tag=13, Frequency=3)
[ 13]    Key: 请        ID=     2,439  (Tag=13, Frequency=3)
[ 13]    Key: 饰        ID=     2,756  (Tag=13, Frequency=2)
[ 13]    Key: 受        ID=     2,788  (Tag=13, Frequency=1)
[ 13]    Key: 送行     ID=     2,877  (Tag=13, Frequency=1)
[ 13]    Key: 题词     ID=     2,973  (Tag=13, Frequency=1)
[ 13]    Key: 同        ID=     3,021  (Tag=13, Frequency=5)
[ 13]    Key: 托        ID=     3,078  (Tag=13, Frequency=1)
[ 13]    Key: 文        ID=     3,179  (Tag=13, Frequency=1)
[ 13]    Key: 先锋     ID=     3,294  (Tag=13, Frequency=1)
[ 13]    Key: 向        ID=     3,348  (Tag=13, Frequency=9)
[ 13]    Key: 研究     ID=     3,540  (Tag=13, Frequency=1)
[ 13]    Key: 演        ID=     3,560  (Tag=13, Frequency=1)
[ 13]    Key: 邀请     ID=     3,587  (Tag=13, Frequency=1)
[ 13]    Key: 以        ID=     3,659  (Tag=13, Frequency=1)
[ 13]    Key: 以及     ID=     3,660  (Tag=13, Frequency=4)
[ 13]    Key: 应        ID=     3,720  (Tag=13, Frequency=1)
[ 13]    Key: 由        ID=     3,762  (Tag=13, Frequency=1)
[ 13]    Key: 与        ID=     3,800  (Tag=13, Frequency=19)
[ 13]    Key: 原名     ID=     3,837  (Tag=13, Frequency=1)
[ 13]    Key: 在        ID=     3,886  (Tag=13, Frequency=1)
[ 13]    Key: 赞助     ID=     3,897  (Tag=13, Frequency=1)
[ 13]    Key: 找        ID=     3,964  (Tag=13, Frequency=1)
[ 13]    Key: 争取     ID=     4,011  (Tag=13, Frequency=1)
[ 13]    Key: 直到     ID=     4,059  (Tag=13, Frequency=1)
[ 13]    Key: 侄女     ID=     4,068  (Tag=13, Frequency=1)
[ 13]    Key: 致        ID=     4,083  (Tag=13, Frequency=1)
[ 13]    Key: 主持     ID=     4,176  (Tag=13, Frequency=1)
[ 13]    Key: 祝        ID=     4,201  (Tag=13, Frequency=1)
[ 13]    Key: 总书记  ID=     4,285  (Tag=13, Frequency=1)
[ 13]    Key: 、     ID=     4,336  (Tag=13, Frequency=3,404)
[ 13]    Key: "  ID=     4,347  (Tag=13, Frequency=2)
[ 13]    Key: （     ID=     4,354  (Tag=13, Frequency=18)
[ 13]    Key: ）     ID=     4,355  (Tag=13, Frequency=6)
[ 13]    Key: ，     ID=     4,356  (Tag=13, Frequency=11)
[ 13]    Key: ／     ID=     4,357  (Tag=13, Frequency=15)

我感觉这个N实际上是论文里的M, "两个中国人名之间的成分";
而现在的M，实际上是论文里的L, "人名的下文";
现在的L，实际上是论文里的K, "人名的上文"。

也就是说它们三个都错后了一个字母。

五、总结

那么我们重新整理最初的根据tag进行的词条数目统计表，并理解一下词典里的内容：

Tag Count:
    Tag = B(  1), Count =   513,    (B)姓氏
    Tag = C(  2), Count =   955,    (C)双名的首字
    Tag = D(  3), Count = 1,043,    (D)双名的末字
    Tag = E(  4), Count =   574,    (E)单名
    Tag = F(  5), Count =     3,    (F)前缀
    Tag = G(  6), Count =     9,    (G)后缀
    Tag = L( 11), Count = 1,198,    (K)人名的上文
    Tag = M( 12), Count = 1,684,    (L)人名的下文
    Tag = N( 13), Count =    67,    (M)两个中国人名之间的成分
    Tag = X( 23), Count =    84,    (X)姓与双名首字成词
    Tag = Y( 24), Count =    47,    (Y)姓与单名成词
    Tag = Z( 25), Count =   388,    (Z)双名本身成词
    Tag = m( 44), Count =    58,    (U)人名的上文与姓氏成词 & (V)人名的末字与下文成词
    Tag = *(100), Count =     1,    始##始
    Tag = *(101), Count =     1,    末##末

到现在，nr.dct的内容基本上清晰了。但是也提出了更复杂的要求，原ICTCLAS并没有实现3字以上词的切分，我们可能需要考虑实现；另外，如何有效地生成我们自己的nr.dct也是一个题目，这不同于core的一元词频或者二元转移词频，简单的扫描一遍就可以得出结果。从现有的nr.dct中我们可以看到由于预处理程序不完善，有不少错误的词存在在里面，我们需要在于处理中加入更多的分析和规则判断，从而让根据语料库学习的人名识别词典更加精准。

作者：DanceFire 发表于2007-5-13 6:13:00 原文链接

阅读：9089 评论：3 查看评论

[原]中科院中文分词系统ICTCLAS之CSegment的GenerateWord()详细分析

DanceFire — Sun, 13 May 2007 05:47:00 +0800

一、简介

这次分析的是ICTCLAS中的

//Generate Word according the segmentation route
bool CSegment::GenerateWord(int **nSegRoute, int nIndex)

本来这个函数没有必要详细分析，但是我注意到中科院论文中并没有描述这个函数、而Sinboy和吕震宇也基本上跳过这个函数不讲了，所以这个函数还没有有人详细的分析过呢。在这里，我具体的分析一下这个函数，另外，也提出一些问题供打算重写ICTCLAS的朋友来考虑。

二、功能介绍

这个函数虽然叫做GenerateWord，但是事实上并不仅仅是生成词，准确说，它大部分的工作不是为了将已经计算好的结果以词的形式显示出来，而是处理各种格式的数字。

数字实际上属于Named Entity的一种，属于未登录词识别的一部分。按理说应该像ICTCLAS处理人名、地名的方法一样，利用隐马，利用概率来处理。不过可惜的是，作者在对于数字的处理上，没有能够使用概率的优势来排除歧义，而采取了另一种方式，规则，来进行数字的合并和切分。在稍后，我们会讲述ICTCLAS在数字处理上出现的一些问题。我们先看看它所处理的规则：

合并所有的数字
针对 [数字][-—][数字] 的形式把减号从中分离出来。
合并：[数字]([月日时分秒]|月份)
合并：[数字][年]
处理时间格式：.*[点]$
处理数字格式：[∶·．／./]$

GenerateWord()对满足上述条件的字符串进行拆分和合并的操作，这就是GenerateWord()的主要工作。

三、代码分析

//Generate Word according the segmentation route
bool CSegment::GenerateWord(int **nSegRoute, int nIndex)
{
    unsigned int i=0,k=0;
    int j,nStartVertex,nEndVertex,nPOS;
    char sAtom[WORD_MAXLENGTH],sNumCandidate[100],sCurWord[100];
    ELEMENT_TYPE fValue;
    //    nSegRoute的是原子位置的数组
    //    循环，i初始为0，判断(i)和(i+1)有效，并判断nSegRoute[nIndex][i] < nSegRoute[nIndex][i+1]
    //    这里为什么要加一个小于来判断？必然前面的小于后面的。
    while(nSegRoute[nIndex][i]!=-1&&nSegRoute[nIndex][i+1]!=-1&&nSegRoute[nIndex][i]<nSegRoute[nIndex][i+1])
    {
        nStartVertex=nSegRoute[nIndex][i];
        j=nStartVertex;//Set the start vertex
        nEndVertex=nSegRoute[nIndex][i+1];//Set the end vertex
        nPOS=0;
        //    取得该分段（粗分的词）的词性(nPOS)和词频(fValue)
        m_graphSeg.m_segGraph.GetElement(nStartVertex,nEndVertex,&fValue,&nPOS);

        //    将该分段对应的词保存进sAtom
        sAtom[0]=0;
        while(j<nEndVertex)
        {//Generate the word according the segmentation route
            strcat(sAtom,m_graphSeg.m_sAtom[j]);
            j++;
        }

        //    将sAtom的值赋给sNumCandidate
        m_pWordSeg[nIndex][k].sWord[0]=0;//Init the result ending
        strcpy(sNumCandidate,sAtom);

        //    如果sNumCandidate全是数字的话，进行特殊处理。
        //    这里判断了sNumCandidate是不是全是半角数字或者全角数字。
        //    *需要注意的是*，IsAllChineseNum() 还有部分日期数字的判断功能，不仅仅是全角判断
        while(sAtom[0]!=0&&(IsAllNum((unsigned char *)sNumCandidate)||IsAllChineseNum(sNumCandidate)))
        {
            //Merge all seperate continue num into one number
            //sAtom[0]!=0: add in 2002-5-9
            //    k? 在遥远的前方，在那函数入口的地方，被初始为0
            //    将sNumCandidate对应的词放到结果集m_pWordSeg[nIndex][k].sWord中
            strcpy(m_pWordSeg[nIndex][k].sWord,sNumCandidate);
            //Save them in the result segmentation

            //    开始看下一个分段，将下一段的文字放到sAtom中
            i++;//Skip to next atom now
            sAtom[0]=0;
            //    *注意* 这里是[i+1]，而不是i，也就是说sAtom里面是下一个词啦。
            while(j<nSegRoute[nIndex][i+1])
            {//Generate the word according the segmentation route
                strcat(sAtom,m_graphSeg.m_sAtom[j]);
                j++;
            }

            //    将sAtom追加到sNumCandidate中。
            //    下一个循环的时候依旧再看一下这个sNumCandidate是否是数字。
            //    如果是数字，就替换原有的m_pWordSeg[nIndex][k].sWord
            strcat(sNumCandidate,sAtom);
        }
        //    点评：如果仅仅是为了合并所有的数字，这个循环臃肿了。
        //    可以直接循环判断出数字所在的范围，然后一次性的追加即可。
        //    合并数字这件事情应该在原子处理的时候进行处理，唯一需要注意的是含有数字的日期的合并放在原子上可能并不合适。
        //    至于合并含有除了[0-9０-９零-九]以外的字符，比如分之，大写数字，[几数第上成] *，应该放在这里，但不能是原子切分那里。

        //
        unsigned int nLen=strlen(m_pWordSeg[nIndex][k].sWord);
        if(
            (nLen==4 && CC_Find("第上成±—＋∶·．／",m_pWordSeg[nIndex][k].sWord))
            ||
            (nLen==1 && strchr("+-./",m_pWordSeg[nIndex][k].sWord[0]))
        )
        {
            //    这里的判断很不解。
            //    第一条是判断前缀是否是数字的前缀，但是为什么长度是4？如果长度是4的话，永远都无法满足啊？恐怕这里的长度应该是写2的。
            //    第二条是判断如果只有一个字符而且还是数字的前缀。
            //Only one word
            strcpy(sCurWord,m_pWordSeg[nIndex][k].sWord);//Record current word
            //    i--？为啥让i退一步呢？
            //    什么情况能进这个条件判断语句块呢？我们在上面的循环得到了字符的前缀，可是却发现后面的字符不是数字。
            //    i--，是说既然后面不是数字，那么我们在前面while loop里面的那个i++就盲目了。我们需要退回到这个"第上成"这个字接着考虑其他case。
            i--;
        }
        else if(m_pWordSeg[nIndex][k].sWord[0]==0)//Have never entering the while loop
        {
            //    因为当前词不是数字，没能够进入前面的循环。
            //    将当前词放入结果，并且记录当前词。
            strcpy(m_pWordSeg[nIndex][k].sWord,sAtom);
            //Save them in the result segmentation
            strcpy(sCurWord,sAtom);//Record current word
        }
        else
        {
            //    到这里就说明进入了前面的while loop，而且不仅仅是一个前缀而已，是个真的数字。
            //    真的么？看下面两个if判断的意思，还是可能出现不是数字的，因此还需要i--退一步考虑。
            //It is a num
            if(
                //    看保存在记录里的词是不是"－－","—"或者仅仅是一个"-"
                strcmp("－－",m_pWordSeg[nIndex][k].sWord)==0
                ||
                strcmp("—",m_pWordSeg[nIndex][k].sWord)==0
                ||
                m_pWordSeg[nIndex][k].sWord[0]=='-' && m_pWordSeg[nIndex][k].sWord[1]==0
            )//The delimiter "－－"
            {
                //    设置词性为 'w' : 标点符号。显然也不是数字了，所以i--，退回一个词。
                nPOS=30464;//'w'*256;Set the POS with 'w'
                i--;//Not num, back to previous word
            }
            else
            {
                //Adding time suffix

                char sInitChar[3];
                unsigned int nCharIndex=0;
                //Get first char
                //    取第一个字符。这里是通过判断char是否小于零，从而判断是不是汉字，需不需要追加一个字符的。
                sInitChar[nCharIndex]=m_pWordSeg[nIndex][k].sWord[nCharIndex];
                if(sInitChar[nCharIndex]<0)
                {
                    nCharIndex+=1;
                    sInitChar[nCharIndex]=m_pWordSeg[nIndex][k].sWord[nCharIndex];
                }
                nCharIndex+=1;
                sInitChar[nCharIndex]='';


                //    这个长长的判断是干嘛的呢？我改写为缩进格式，更利于逻辑上的理解。
                //    其实就是为了把原来的[数字], [-][数字],的分词调整为：[数字]、[-]、[数字]
                //    我们看看具体的实现。先进行条件判断：
                if(
                    //    1、只考虑第二个词及其以后的词，因为这里需要考虑前一个词的词性
                    k > 0
                    &&
                    //    2、前一个词的词性是0x6D00('m')数字或0x7400
                    (
                        abs(m_pWordSeg[nIndex][k-1].nHandle) == 27904
                        ||
                        abs(m_pWordSeg[nIndex][k-1].nHandle) == 29696
                    )
                    &&
                    //    3、第一个字符是减号
                    (
                        strcmp(sInitChar,"—") == 0
                        ||
                        sInitChar[0] == '-'
                    )
                    //    4、除了第一个字符还有别的字符。呵呵，其实只有负号的已经在前面被过滤了，按理说这里不该再担心这个问题了。
                    &&
                    (
                        strlen(m_pWordSeg[nIndex][k].sWord)>nCharIndex)
                    )
                {
                    //    这个条件判断到底是什么条件？下面这个注释注释的好，无非就是针对：
                    //        [数字][-—][数字]
                    //    的形式把减号从中分离出来。汗一下……
                    //3-4月
                    //27904='m'*256
                    //Split the sInitChar from the original word
                    strcpy(m_pWordSeg[nIndex][k+1].sWord,m_pWordSeg[nIndex][k].sWord+nCharIndex);
                    m_pWordSeg[nIndex][k+1].dValue=m_pWordSeg[nIndex][k].dValue;
                    m_pWordSeg[nIndex][k+1].nHandle=27904;
                    m_pWordSeg[nIndex][k].sWord[nCharIndex]=0;
                    m_pWordSeg[nIndex][k].dValue=0;
                    m_pWordSeg[nIndex][k].nHandle=30464;//'w'*256;

                    //    将分离出的减号加入优化后的图。
                    m_graphOptimum.SetElement(
                        nStartVertex,
                        nStartVertex+1,
                        m_pWordSeg[nIndex][k].dValue,
                        m_pWordSeg[nIndex][k].nHandle,
                        m_pWordSeg[nIndex][k].sWord
                        );
                    nStartVertex+=1;
                    k+=1;
                }

                //    取得第k个词的长度。如果进了上述循环，那么nLen长度是第二个[数字]的长度。
                nLen=strlen(m_pWordSeg[nIndex][k].sWord);
                //    如果sAtom是 [月日时分秒]或者 "月份" 的话。
                //    等等～，sAtom和m_pWordSeg[nIndex][k].sWord难道还不一样么？
                //    从前面的代码看，sAtom最多也就比sWord多一个减号啊？
                //    我们再回去看第一个循环的时候就会注意到，在那里，sAtom被赋予了[i+1]的字符串
                //    也就是说sAtom实际上已经是下一个词了。
                //    那么重新解释一下下面判断的意思就是：
                //        [数字]([月日时分秒]|月份)
                if(
                    (
                        strlen(sAtom) == 2
                        &&
                        CC_Find("月日时分秒",sAtom)
                    )
                    ||
                    strcmp(sAtom,"月份") == 0
                )
                {
                    //    如果是如下模式：
                    //        [数字]([月日时分秒]|月份)
                    //    将他们视为同一个词，加入到m_pWordSeg里，
                    //    并且将sCurWord设置为"未##时"，词性为't'
                    //2001年
                    //       ^--- 啊？兄弟弄错了吧？下一个条件才是年呢。这个是月啊。：）
                    strcat(m_pWordSeg[nIndex][k].sWord,sAtom);
                    strcpy(sCurWord,"未##时");
                    nPOS=-29696;//'t'*256;//Set the POS with 'm'
                }
                else if(strcmp(sAtom,"年")==0)
                {
                    //    同上表示的话，应该是这个模式：
                    //        [数字][年]
                    //    通过IsYearTime确认[数字]是合法的数字
                    //    如果满足就将年追加其后，将当前词改为特征词"未##时"，并且词性改为't'
                     if(IsYearTime(m_pWordSeg[nIndex][k].sWord))//strncmp(sAtom,"年",2)==0&&
                     {//1998年，
                        strcat(m_pWordSeg[nIndex][k].sWord,sAtom);
                        strcpy(sCurWord,"未##时");
                        nPOS=-29696;//Set the POS with 't'
                     }
                     else
                     {
                         //    如果不满足，那么这些数字就仅仅是数字
                         //    将当前词改为特征词"未##数",词性设为'm'--数字。
                         //    并且因为不是时间，所以就得i--退一步。
                        strcpy(sCurWord,"未##数");
                        nPOS=-27904;//Set the POS with 'm'
                        i--;//Can not be a time word
                     }
                }
                 else
                {
                    //    又不是月份，又不是年，那现在看看是不是时分秒。
                    //早晨/t  五点/t
                    //        .*[点]$
                    //    看看是不是以"点"结尾的
                    if(strcmp(m_pWordSeg[nIndex][k].sWord + strlen(m_pWordSeg[nIndex][k].sWord) - 2,"点") == 0)
                    {
                        //    如果是的话就改sCurWord为特征词"未##时"，词性为't'
                        strcpy(sCurWord,"未##时");
                        nPOS=-29696;//Set the POS with 't'
                    }
                    else
                    {
                        //    如果不是以[∶·．／./]结尾的，那就改sCurWord为特征词"未##数"，词性为'm'
                        if(
                            !CC_Find("∶·．／",m_pWordSeg[nIndex][k].sWord+nLen-2)
                            &&
                            m_pWordSeg[nIndex][k].sWord[nLen-1] != '.'
                            &&
                            m_pWordSeg[nIndex][k].sWord[nLen-1] != '/'
                        )
                        {
                            strcpy(sCurWord,"未##数");
                            nPOS=-27904;//'m'*256;Set the POS with 'm'
                        }
                        else if( nLen > strlen(sInitChar))
                        {
                            //    这两个逻辑合在一起真是够不合适的。
                            //    上面这个else if是说，以[∶·．／./]结尾，并且总长度大于一个字符。

                            //    除掉尾追的[∶·．／./]。
                            //    呵呵，如果2个/呢？
                            //Get rid of . example 1.
                            if(
                                m_pWordSeg[nIndex][k].sWord[nLen-1] == '.'
                                ||
                                m_pWordSeg[nIndex][k].sWord[nLen-1] == '/'
                            )
                                m_pWordSeg[nIndex][k].sWord[nLen-1]=0;
                            else
                                m_pWordSeg[nIndex][k].sWord[nLen-2]=0;

                            //    将sCurWord设为特征词"未##数"，词性设为'm'
                            strcpy(sCurWord,"未##数");
                            nPOS=-27904;//'m'*256;Set the POS with 'm'
                            //    i--？是啊，呵呵，你除去了最后一个字符，自然退一步，让程序接着那个最后的字符处理了。
                            i--;
                        }
                        //    else呢？
                        //    其实上面的那个else if就是else里的if。呵呵。那么也就是说，如果不除去最后一个字符怎么做？
                    }
                    i--;//Not num, back to previous word
                    //    总结一下i--，只要没有把sAtom合并进来，i就要--。
                    //    呵呵，似乎把逻辑换一下可能更合适。满足条件的话i++，把后面的和进来，不满足就什么都不做。
                }
            }
            //    数字处理完后，不管是什么情况，词频设为0
            //    结束位置为下一个起始位置
            fValue=0;
            nEndVertex=nSegRoute[nIndex][i+1];//Ending POS changed to latter
        }
        //    经过了长长的优化后，包括拆开和合并后，我们终于可以保存结果了。
        m_pWordSeg[nIndex][k].nHandle=nPOS;//Get the POS of current word
        m_pWordSeg[nIndex][k].dValue=fValue;//(int)(MAX_FREQUENCE*exp(-fValue));//Return the frequency of current word
        m_graphOptimum.SetElement(nStartVertex,nEndVertex,fValue,nPOS,sCurWord);
        //Generate optimum segmentation graph according the segmentation result
        i++;//Skip to next atom
        k++;//Accept next word
    }
    m_pWordSeg[nIndex][k].sWord[0]=0;
    m_pWordSeg[nIndex][k].nHandle=-1;//Set ending
    return true;
}

其中涉及了一个叫做IsYearTime()的函数，来判断是否是为年的时间：

//    判断数字是否是年号
//        入口：sNum，是一串数字。可能是全角、半角数字。调用方要确保都是数字。
//        判断下面6种模式：(但是最后一种实际上是失效的)
//            1. [0-9]{4} 或者 [5-9][0-9]        四字或者2字年份
//            2. [数字]{6,} or [５６７８９]{2}
//            3. [零○一二三四五六七八九壹贰叁肆伍陆柒捌玖]{2}
//            4. 四个数字的，并且含有2个[千仟零○]的。
//            5. [千仟]
//            6. [甲乙丙丁戊己庚辛壬癸][子丑寅卯辰巳午未申酉戌亥]

bool CSegment::IsYearTime(char *sNum)
{//Judge whether the sNum is a num genearating year
    unsigned int nLen=strlen(sNum);
    char sTemp[3];
    strncpy(sTemp,sNum,2);
    sTemp[2]=0;
    //    [0-9]{4} 或者 [5-9][0-9]
    //    这个逻辑有问题啊，也就是4位数字或者大于50的两位数字。
    //    那么这句话分词就该出错了：
    //        “这59年比49年好多了。”
    //    被分成了：
    //        59年/t  比/p  49/m  年/q  好/a  多/a  了/y  。/w
    //    其中"59年"被识别为时间了，而"49年"就错了变成了一个数字了。
    if(
        IsAllSingleByte((unsigned char *)sNum)
        &&
        (
            nLen == 4
            ||
            nLen == 2 && sNum[0] > '4'
        )
    )//1992年, 90年
        return true;

    //    如果全为数字，并且长度大于等于6，或者长度等于4并且都是"５６７８９"里面的数字。
    //        [数字]{6,} or [５６７８９]{2}
    //    这是要干吗？后一个条件好说，是说两位数的年份，数字要求>=50年。前一个呢？
    if(
        IsAllNum((unsigned char *)sNum)
        &&
        (
            nLen >= 6
            ||
            nLen == 4 && CC_Find("５６７８９",sTemp)
        )
    )
        return true;

    //    [零○一二三四五六七八九壹贰叁肆伍陆柒捌玖]{2}
    if(
        GetCharCount("零○一二三四五六七八九壹贰叁肆伍陆柒捌玖",sNum) == (int)nLen/2
        &&
        nLen>=3    //    3？？前一个条件已经限定了是偶数了，怎么会出来个3？应该是4吧？
    )
        return true;

    //    四个数字的，并且含有2个[千仟零○]的。
    if(nLen==8&&GetCharCount("千仟零○",sNum)==2)//二仟零二年
        return true;

    //    [千仟]
    if(nLen==2&&GetCharCount("千仟",sNum)==1)
        return true;

    //    下面这个比较特殊，逻辑上是：
    //        [甲乙丙丁戊己庚辛壬癸][子丑寅卯辰巳午未申酉戌亥]
    //    但仅仅是这里的逻辑，因为根本不会有含有上述文字的词进入这里，因为在IsAllNumber哪里就被排除了。
    //    开始以为既然如此，那一定识别不了这些年份，结果惊奇的发现虽然词性标注没能成功的标为时间，
    //    但是竟然识别了所有的天干地支。仔细研究后发现，作者竟然把所有的天干地支都放到词库里面了。
    //    词性为数字，词频为0。从这里，至少找到了一部分词频为0的词。
    if(
        nLen==4
        && GetCharCount("甲乙丙丁戊己庚辛壬癸",sNum)==1
        && GetCharCount("子丑寅卯辰巳午未申酉戌亥",sNum+2)==1
    )
        return true;

    return false;
}

在IsYearTime的分析中已经看到了一些问题，50年以前的年就是别不出来了，那么如果说"49年建国"，这句话就会分错误了。

在上面的处理中，调用了一个叫做IsAllChineseNum()的函数，需要说明的是，这个函数在ICTCLAS的原子切分里也用到了，用以判断一个字符串是不是中文数字，其正则表达式为：

[几数第上成]([零○一二两三四五六七八九十廿百千万亿壹贰叁肆伍陆柒捌玖拾佰仟∶·．／点]|分之)

具体的函数分析如下：

//    以正则表达式表示：
//    [几数第上成]([零○一二两三四五六七八九十廿百千万亿壹贰叁肆伍陆柒捌玖拾佰仟∶·．／点]|分之)
bool IsAllChineseNum(char *sWord)
{//百分之五点六的人早上八点十八分起床
  unsigned int  k;
  char tchar[3];
  char ChineseNum[]="零○一二两三四五六七八九十廿百千万亿壹贰叁肆伍陆柒捌玖拾佰仟∶·．／点";//
  char sPrefix[]="几数第上成";
  for(k = 0; k < strlen(sWord); k+=2)
  {
     strncpy(tchar,sWord+k,2) ;
     tchar[2]='';
     if(strncmp(sWord+k,"分之",4)==0)//百分之五
     {
        k+=2;
        continue;
     }

     if(!CC_Find(ChineseNum, tchar)&&!(k==0&&CC_Find(sPrefix, tchar)))
         return false;
  }
  return true;
}

这个函数包含了在原子切分的时候无法处理的高层的功能。

那么问题在哪呢？在这部判断的时候不会考虑上下文，而且也尚未成词，因此我们可以用满足规则的任何方式来构造满足这个规则却不是数字的例子。

1、

原句：他们竟没有算上陆兵。
ICTCLAS分词：他们/r 竟/d 没有/d 算/v 上陆/m 兵/n 。/w

"上陆"被判断为m，即数字，单独成词。这显然不应该。原因是"上"是前缀，"陆"被视为数字。

2、

原句：他从地板上拾起钱包，也没数拾起来就走。
ICTCLAS分词：他/r 从/p 地板/n 上拾/m 起/q 钱/n 包/v ，/w 也/d 没/v 数拾/m 起来/ v 就/d 走/v 。/w

"上拾"，"数拾"，都是和上面一样的原因。

3、

原句：成！就这么干了。
ICTCLAS分词：成/m ！/w 就/p 这么/r 干/v 了/y 。/w

这里"成"是表示肯定的意思，表示可以，认同。显然也不是数词，词性标注错误。

4、

原句：他结巴地说："我......要茶...茶......几。"
ICTCLAS分词：他/r 结巴/a 地/u 说/v ：/w "/w 我/r .../w .../w 要/v 茶/n .../w 茶/n .../w .../w 几/m 。/w "/w

由于标点符号分割，导致最后一个"几"本来是名词的一部分，结果被视为动词了。当然这个不完全算是ICTCLAS的问题，这个甚至都不属于分词领域。

对于数字的原子判断，恐怕只有纯数字和符号才适合做原子，只要有汉字在内，就应该只将其做为一条边来考虑，在后面判断中来判断是否应该组合为日期等等。

四、一些想法和建议

ICTCLAS在数字处理上使用纯规则判断，特别是中文数字，很容易和上下文产生歧义，对于这种歧义的处理，概率已经被证明是相当迅速有效的，我们应该充分利用概率排除歧义的优势。这也是ICTCLAS在汉字分词排除歧义上的优势所在。

其实数字排除歧义和普通汉字排除歧义没有本质差别。

对于普通汉字的排除歧义，我们列举了所有可能的词，添上概率，让最短路径算法寻找最可能的解。

对于数字排歧义，我们完全可以使用同样的办法，通过规则列举所有可能的解，填入概率，让最短路径算法去寻找最可能的解。

在原有的ICTCLAS里面没有能够列举所有数字可能的边，而是人工的强制组合。这种强制组合实际上有些没有道理，而且很局限，你只能对你知道的那几个case组合，但是很可能的结果就是导致你没有想到的某种组合突破了你的规则，导致了错误的结果。然后就只能再调整规则。

再仔细看这种过程，这种反复根据规则的调整的场景不是很熟悉么？就是在利用统计进行排除歧义之前，基于规则的做法啊。既然统计引入后大大的提高了排除歧义的能力，我们何不同样利用规则给出多种选择，让统计算法做决定呢？

规则是死的，只有满足、不满足，是或者非。而统计是灵活的，是更可能，或者不太可能。利用死的规则提出所有可能的解（词），再利用活的统计来全局的判定到底该采用谁。

至于添加边这种行为所应该处的代码位置，我们可以将其放在产生一元图后，建立起一系列的规则过滤，对一元图进行调整。其中一个规则过滤就是增加与数字有关的、根据上下文构成可能的词，添加到一元图中去。其他的一些规则，我们也可以加在这个位置。这类规则不再成为判定了，而是成为提供词库所不能提供的更多种组词的选择了，这么利用规则，可能更加灵活。

参考：

http://www.cnblogs.com/zhenyulu/articles/673650.html

作者：DanceFire 发表于2007-5-13 5:47:00 原文链接

阅读：5003 评论：6 查看评论

[原]中科院中文分词系统ICTCLAS之NShortPath代码的详细分析

DanceFire — Tue, 17 Apr 2007 15:15:00 +0800

这两天我开始看ICTCLAS的实现代码了，和吕震宇的感觉完全一样，代码真的是糟糕透顶，呵呵，非常同情吕震宇和Sinboy能够那么认真地把那些代码读完。有了你们辛苦、认真的分析工作，让我更容易的读懂ICTCLAS的代码了，谢谢了。阅读过程中注意到了他们分析中有些地方有点小错误。

ICTCLAS的命名好像没有正统的学过数据结构一样，对于数据结构的命名非常富有想象力，完全没有按照数据结构上大家公认的术语命名，所以给代码的读者带来很大的迷惑性。所以我们在看名字的时候一定要抛开名字看实现，看本质，看他们到底是个啥。呵呵。

首先就是CQueue的问题，CQueue虽然叫Queue，但是它不是FIFO的Queue。那它是什么呢？CQueue是优先级队列Priority Queue和Stack的杂交。但是没有半点FIFO的Queue的概念在里面。

CQueue元素有一个权重eWeight，这个权重如果不为0（或者说互相之间不等），那么CQueue此时的含义是按照权重由小到大排序的优先级队列。

如果CQueue的所有元素的eWeight都相等，（在ICTCLAS代码里就是都为0），此时CQueue就演变为FILO的Stack，栈。

因此这个CQueue才会有Push和Pop两种插入和删除元素的命名。呵呵，挂着羊头卖的是狗肉，还是两只狗。对于C#、C++、Java来说，类库里面都有现成的优先级队列和栈的实现，而且可以用

List<T>
重载小于号(C++)、重载CompareTo()（C#,Java）
List.Sort()

来代替优先级队列实现和并且具有和作者一样的Iterator的功能。那个CQueue完全可以省略掉。

然后是DynamicArray。动态数组？非也。这个是用来表示稀疏图的邻接表，每一个元素表示的是图上的一条边。对于非稀疏的图往往喜欢用NxN的数组来表示N个节点的连接关系。而对于稀疏图来说，无疑会浪费大量的空间，于是往往采用记录邻接两点的边的方式来记录图。

作者为了能够让以后调用的时候方便，对于起点和终点进行排序（或者说维护了顺序）。对起点排序，就是代码中所谓的RowFirst，对于终点进行排序就是ColumnFirst。

那为何作者叫DynamicArray呢？其实也不难想象，首先是因为邻接表实际上就是边的一个列表，也可以看为数组。但是边的数量是在变化的，而不是最开始就可以知道的。因此这个数组是动态的。于是就叫动态数组了。。。。汗。

对于DynamicArray，我们也完全可以用List<>.Sort()的方式来实现，对于C++来说，我们需要定义2个functor，分别是起点优先比较和终点优先比较。对于Java和C#也有类似的定义比较函数的办法。因此这个DynamicArray()，可以扔掉了。没必要用这么一个奇怪的东西。

接下来我把NShortPath中的最主要的三个函数

int Output(int **nResult,bool bBest,int *npCount);
int ShortPath();
void GetPaths(unsigned int nNode,unsigned int nIndex,int
**nResult=0,bool bBest=false);

的代码和分析帖在下面，分析都写在注释里了。

在具体开始之前，我先明确一个东西，在中科院的论文里称求解多个最优路径问题为N最短路径问题(N-Shortest Paths)，如果你google你会发现没有多少有用的结果，其实不然。不知道是不是作者不了解国际上对该问题的讨论，这个问题应该称为k shortest path（即K最短路径问题）。这个问题也已经有了不错的解法，David Eppstein分别在1994年和1997年已经给出了大约复杂度为O(m + n log n + kn)的解法。而中科院论文里面的解法的复杂度还是比较高的：O(n*N*k)。（两个复杂度的字母含义不同，定义请看原论文）。所以，如果可能，再次实现ICTCLAS的算法的朋友可以考虑抛开中科院的求k shortest path的解法，而使用国际上比较流行的解法。

BTW: 问一下，吕震宇，你有什么比较可爱点的称呼么？呵呵，我这么直呼大名在中文的习惯里似乎不太礼貌。：）

int CNShortPath::ShortPath()
{
    unsigned int nCurNode=1,nPreNode,i,nIndex;
    ELEMENT_TYPE eWeight;
    PARRAY_CHAIN pEdgeList;

    //    循环从1开始，即从第二个节点开始。遍历所有节点。
    for(;nCurNode<m_nVertex;nCurNode++)
    {
       CQueue queWork;
       //    有CNShortPath调用的上下文可知，入口的m_apCost为列优先排序的CDynamicArray。
       //    换句话说就是：
       //    list<Edge> m_apCost;
       //    list.sort(m_apCost, less_column_first());
       //    下面这行代码是将该列的边的起始链表元素赋予pEdgeList，以方便遍历。
       //    算法上的含义是取得图上终点为nCurNode的所有边，并将第一条边放入pEdgeList进行对所有边的遍历。
                eWeight=m_apCost->GetElement(-1,nCurNode,0,&pEdgeList);//Get all the
edges
                while(pEdgeList!=0 && pEdgeList->col==nCurNode)
                {
            //    nPreNode是当前边的起点
           nPreNode=pEdgeList->row;
           //    eWeight是当前边的长度
           eWeight=pEdgeList->value;//Get the value of edges
                   //   对于dijkstra算法来说，我们需要知道当前节点（终点）的通过不同的前方的点到原点的距离
                   //   并且从中知道最短的路径，然后我们会更新当前节点的父节点和当前节点到原点的距离。
                   //   在这个修改后的多最短路径算法中，我们将（当前节点的父节点，当前节点通过该父节点到原点的距离）视为一个配对
                   //   我们保留一个为m_nValueKind大小的数组，记录这些可能的配对，而不仅仅是保留最小的。
                   //   下面这个循环就是将所有可能的组合放到优先级队列中，然后将来可以从优先级队列中选取前m_nValueKind。
                   //   这里循环范围限定到m_nValueKind主要是考虑以后所需要的不会超过这么多个值。
                   //   这里放入优先级队列的是前向节点和长度，相当于是路径，而不是长度的值的列表，与后面表达的意思不同。
           for(i=0;i<m_nValueKind;i++)
           {
                //    如果起点>0，即判断起点是不是第一个节点。
               if(nPreNode>0)//Push the weight and the pre node
infomation
               {
                    //    起点不是第一个节点。
                    //    判断起点到原点的总长度在索引值为i的时候是不是无穷大。
                                        //      如果无穷大了，就说明前一个点已经无法到达了，说明没有更多到前面节点的路径了
                    //    也不必继续向优先级队列中放入点了。
                   if(m_pWeight[nPreNode-1][i]==INFINITE_VALUE)
                       break;
                    //    将起点，索引值i，和终点到原点的总长度压入优先级队列。
                   queWork.Push(nPreNode,i,eWeight
+m_pWeight[nPreNode-1][i]);
               }
               else
               {
                    //    起点为第一个节点。
                    //    将起点，索引值i，和当前边的长度压入优先级队列
                   queWork.Push(nPreNode,i,eWeight);
                   break;
               }
           }//end for

           //    换到下一条边。
           pEdgeList=pEdgeList->next;

                }//end while

       //Now get the result queue which sort as weight.
       //Set the current node information
        //    将起点到原点的长度，对于每个索引值都初始化为无穷。
       for(i=0;i<m_nValueKind;i++)
       {
            m_pWeight[nCurNode-1][i]=INFINITE_VALUE;
       }
       //memset((void *),(int),sizeof(ELEMENT_TYPE)*);
       //init the weight
       i=0;
       //       进行循环，索引值小于想要的索引值时，并且优先级队列不为空。
           //   在这里面的i表达的是长度的值的索引，并不代表不同的路径，同一个i可能对应多个路径。
           //   这个循环过后，m_pWeight[nCurNode-1][] 为可能存在的前m_nValueKind个长度值。
           //   并且把前m_nValueKind个路径压入m_nParent对应的队列中。
           //
       while(i<m_nValueKind&&queWork.Pop(&nPreNode,&nIndex,&eWeight)!
=-1)
       {//Set the current node weight and parent
                        //      从以长度为优先级的队列中，提取第一个（最短的）记录。
                        //      将该记录的起点给nPreNode，索引给nIndex，长度给eWeight

            //    如果起点到原点的长度为无穷。（这在第一次循环的时候显然是无穷）
            //    就将这个长度设为最短边的长度。
           if(m_pWeight[nCurNode-1][i]==INFINITE_VALUE)
               m_pWeight[nCurNode-1][i]=eWeight;
           else if(m_pWeight[nCurNode-1][i]<eWeight)//Next queue
           {
                //    否则，如果起点到原点的长度小于当前边的长度
                //    递增索引值，换到下一套选择值去。如果到达了最大索引值就退出循环。
               i++;//Go next queue and record next weight
               //       既然这里有是否会大于最大索引值的判断，何必在while条件里面加那个条件呢？
               if(i==m_nValueKind)//Get the last position
                   break;
                //    将起点到原点的长度，下一个索引值(i+1)，设为队列中元素的长度。
               m_pWeight[nCurNode-1][i]=eWeight;
           }else{
                           //   如果起点到原点的长度 == 队列中的长度，那么只向当前节点，当前索引的父节点中插入一个配对。
                           //

                           //   如果起点到原点的长度 > 队列中的长度？
                           //   这是不可能出现的，因为这个数值在队列中是有序的。从小到大。
                           //   因此这个数值的变化规律是初始位无穷大，第一次赋值为最小值，然后逐渐增大。
                   }
           //    将（起点，索引值）压入起点的父节点的队列中去
           m_pParent[nCurNode-1][i].Push(nPreNode,nIndex);
       }
    }//end for

    return 1;
}

//bBest=true: only get one best result and ignore others
//Added in 2002-1-24
void CNShortPath::GetPaths(unsigned int nNode,unsigned int nIndex,int
**nResult,bool bBest)
{
    CQueue queResult;
        //      当前节点为最后一个节点
        unsigned int nCurNode = nNode, nCurIndex = nIndex;
        unsigned int nParentNode,nParentIndex;
        unsigned int nResultIndex = 0;

        if(m_nResultCount >= MAX_SEGMENT_NUM)        //      Only need 10 result
        {
                return;
        }
        //      将路径第一点设为-1。
        nResult[m_nResultCount][nResultIndex] = -1;     //      Init the result
        //      此时没有设置weight，此时的CQueue的成为了一个Stack。
        queResult.Push(nCurNode, nCurIndex);
    bool bFirstGet;
    while(!queResult.IsEmpty())
        {
                //      从最后的节点循环到第一个节点
                //      这个循环在第一次循环的时候，会把最优解压入结果栈
                //      第二次循环会把分支解压入结果栈。
                while(nCurNode>0)    //
                {
                        //Get its parent and store them in nParentNode,nParentIndex
                        //      取（当前节点，当前索引）的父节点列表的第一个父节点信息。
                        if(m_pParent[nCurNode-1][nCurIndex].Pop(&nParentNode,&nParentIndex,
0,false,true)!=-1)
                        {
                                //      将当前节点变为父节点
                           nCurNode=nParentNode;
                           nCurIndex=nParentIndex;
                        }
                        //      如果当前节点不是第一个节点的话，就将当前节点入栈。
                        if(nCurNode>0)
                queResult.Push(nCurNode,nCurIndex);
                }
                //      如果nCurNode == 0说明取得了合法的结果，而不是异常退出上一个循环。
                if(nCurNode==0)
                {
                        //Get a path and output
                        //      将路径第一点设为起点
                        nResult[m_nResultCount][nResultIndex++]=nCurNode;//Get the first
node
                        //      第一次从queResult取数据的时候，得将这个标志位设为true。
                        //      这样才可以在bModify = false的时候，取得堆栈的头。
                        //      其目的就是要从头遍历堆栈，但是不修改堆栈内部数据，以方便以后遍历用。（循环不就行了？）
                        bFirstGet=true;
                        nParentNode=nCurNode;
                        //      将堆栈遍历，保存结果路径。
                        while(queResult.Pop(&nCurNode,&nCurIndex,0,false,bFirstGet)!=-1)
                        {
                                nResult[m_nResultCount][nResultIndex++]=nCurNode;
                                bFirstGet=false;
                                nParentNode=nCurNode;
                        }
                        //      设置结果位为-1
                        nResult[m_nResultCount][nResultIndex]=-1;//Set the end
                        m_nResultCount+=1;//The number of result add by 1
                        if(m_nResultCount>=MAX_SEGMENT_NUM)//Only need 10 result
                                return ;
                        nResultIndex=0;
                        nResult[m_nResultCount][nResultIndex]=-1;//Init the result

                        if(bBest)//Return the best result, ignore others
                                return ;
                }

                queResult.Pop(&nCurNode,&nCurIndex,0,false,true);//Read the top node
                //      寻找存在多个父节点的节点。
        while(queResult.IsEmpty()==false&&(m_pParent[nCurNode-1]
[nCurIndex].IsSingle()||m_pParent[nCurNode-1]
[nCurIndex].IsEmpty(true)))
                {
               queResult.Pop(&nCurNode,&nCurIndex,0);//Get rid of it
                   queResult.Pop(&nCurNode,&nCurIndex,0,false,true);//Read the top
node
                }
        if(queResult.IsEmpty()==false&&m_pParent[nCurNode-1]
[nCurIndex].IsEmpty(true)==false)
                {
                        //      如果定位到了节点。将下一种选择入栈。
                        m_pParent[nCurNode-1][nCurIndex].Pop(&nParentNode,&nParentIndex,
0,false,false);
                        nCurNode=nParentNode;
                        nCurIndex=nParentIndex;
                        if(nCurNode>0)
                           queResult.Push(nCurNode,nCurIndex);
                }
        }
}

int CNShortPath::Output(int **nResult,bool bBest,int *npCount)
{
        //      sResult is a string array
        unsigned int i;
        m_nResultCount=0;//The
        //      如果节点数只有2个，就没必要那么复杂运算了。直接返回唯一的路径。
        if(m_nVertex<2)
        {
                nResult[0][0]=0;
                nResult[0][1]=1;
                *npCount=1;
                return 1;
        }
        //              对最后一个节点，遍历每一个可能的长度值，将计算所得的路径放入nResult。
        for(i=0;i<m_nValueKind&&m_pWeight[m_nVertex-2][i]<INFINITE_VALUE;i++)
        {
          GetPaths(m_nVertex-1,i,nResult,bBest);
          *npCount=m_nResultCount;
                //      有返回值，并且只想要一个结果
          if(nResult[i][0]!=-1&&bBest)//Get the best answer
                  return 1;
                //      不能超过内部的最大结果数。这个限制条件可以通过动态的vector<T>来消除掉。
      if(m_nResultCount>=MAX_SEGMENT_NUM)//Only need 10 result
                  return 1;
        }
        return 1;
}

参考：

ICTCLAS分词系统研究（五）--N最短路径
http://blog.csdn.net/sinboy/archive/2006/05/19/745498.aspx

SharpICTCLAS分词系统简介(4)NShortPath-1
http://www.cnblogs.com/zhenyulu/articles/669795.html

SharpICTCLAS分词系统简介(5)NShortPath-2
http://www.cnblogs.com/zhenyulu/articles/672442.html

ICTCLAS的Google网上论坛
http://groups.google.com/group/ictclas

作者：DanceFire 发表于2007-4-17 15:15:00 原文链接

阅读：7618 评论：5 查看评论

[原]警告：为了安全请不要随意将ASP.Net的validateRequest="false"

DanceFire — Wed, 11 Apr 2007 10:52:00 +0800

ASP.Net 1.1后引入了对提交表单自动检查是否存在XSS（跨站脚本攻击）的能力。当用户试图用<xxxx>之类的输入影响页面返回结果的时候，ASP.Net的引擎会引发一个 HttpRequestValidationExceptioin。默认情况下会返回如下文字的页面：

Server Error in '/YourApplicationPath' Application

A potentially dangerous Request.Form value was detected from the client
(txtName="<b>").

Description: Request Validation has detected a potentially dangerous client input value, and processing of the request has been aborted. This value may indicate an attempt to compromise the security of your application, such as a cross-site scripting attack. You can disable request validation by setting validateRequest=false in the Page directive or in the configuration section. However, it is strongly recommended that your application explicitly check all inputs in this case.

Exception Details: System.Web.HttpRequestValidationException: A potentially dangerous Request.Form value was detected from the client (txtName="<b>").

....

这是ASP.Net提供的一个很重要的安全特性。因为很多程序员对安全没有概念，甚至都不知道XSS这种攻击的存在，知道主动去防护的就更少了。ASP.Net在这一点上做到默认安全。这样让对安全不是很了解的程序员依旧可以写出有一定安全防护能力的网站。

但是，当我Google搜索 HttpRequestValidationException 或者 "A potentially dangerous Request.Form value was detected from the client"的时候，惊奇的发现大部分人给出的解决方案竟然是在ASP.Net页面描述中通过设置 validateRequest=false 来禁用这个特性，而不去关心那个程序员的网站是否真的不需要这个特性。看得我这叫一个胆战心惊。安全意识应该时时刻刻在每一个程序员的心里，不管你对安全的概念了解多少，一个主动的意识在脑子里，你的站点就会安全很多。

为什么很多程序员想要禁止 validateRequest 呢？有一部分是真的需要用户输入"<>"之类的字符。这就不必说了。还有一部分其实并不是用户允许输入那些容易引起XSS的字符，而是讨厌这种报错的形式，毕竟一大段英文加上一个ASP.Net典型异常错误信息，显得这个站点出错了，而不是用户输入了非法的字符，可是自己又不知道怎么不让它报错，自己来处理报错。

对于希望很好的处理这个错误信息，而不使用默认ASP.Net异常报错信息的程序员们，你们不要禁用validateRequest=false。

正确的做法是在你当前页面添加Page_Error()函数，来捕获所有页面处理过程中发生的而没有处理的异常。然后给用户一个合法的报错信息。如果当前页面没有Page_Error()，这个异常将会送到Global.asax的Application_Error()来处理，你也可以在那里写通用的异常报错处理函数。如果两个地方都没有写异常处理函数，才会显示这个默认的报错页面呢。

举例而言，处理这个异常其实只需要很简短的一小段代码就够了。在页面的Code-behind页面中加入这么一段代码：

protected void Page_Error(object sender, EventArgs e)
{
    Exception ex = Server.GetLastError();
    if (ex is HttpRequestValidationException)
    {
        Response.Write("请您输入合法字符串。");
        Server.ClearError(); // 如果不ClearError()这个异常会继续传到Application_Error()。
    }
}

这样这个程序就可以截获 HttpRequestValidationException 异常，而且可以按照程序员的意愿返回一个合理的报错信息。

这段代码很简单，所以我希望所有不是真的要允许用户输入<xxx>之类字符的朋友，千万不要随意的禁止这个安全特性，如果只是需要异常处理，那么请用类似于上面的代码来处理即可。

而对于那些通过明确禁止了这个特性的程序员，自己一定要明白自己在做什么，而且一定要自己手动的检查必须过滤的字符串，否则你的站点很容易引发跨站脚本攻击。

关于存在Rich Text Editor的页面应该如何处理？

如果页面有富文本编辑器的控件的，那么必然会导致有<xxx>类的HTML标签提交回来。在这种情况下，我们不得不将validateRequest="false"。那么安全性怎么处理？如何在这种情况下最大限度的预防跨站脚本攻击呢？

根据微软的建议，我们应该采取安全上称为“默认禁止，显式允许”的策略。

首先，我们将输入字符串用 HttpUtility.HtmlEncode()来编码，将其中的HTML标签彻底禁止。

然后，我们再对我们所感兴趣的、并且是安全标签，通过Replace()进行替换。比如，我们希望有"<b>"标签，那么我们就将"<b>"显式的替换回"<b>"。

示例代码如下：

  void submitBtn_Click(object sender, EventArgs e)
  {
    // 将输入字符串编码，这样所有的HTML标签都失效了。
    StringBuilder sb = new StringBuilder(
                            HttpUtility.HtmlEncode(htmlInputTxt.Text));
    // 然后我们选择性的允许<b> 和 <i>
    sb.Replace("<b>", "<b>");
    sb.Replace("</b>", "");
    sb.Replace("<i>", "<i>");
    sb.Replace("</i>", "");
    Response.Write(sb.ToString());
  }

这样我们即允许了部分HTML标签，又禁止了危险的标签。

根据微软提供的建议，我们要慎重允许下列HTML标签，因为这些HTML标签都是有可能导致跨站脚本攻击的。

<applet>
<body>
<embed>
<frame>
<script>
<frameset>
<html>
<iframe>
<img>
<style>
<layer>
<link>
<ilayer>
<meta>
<object>

可能这里最让人不能理解的是<img>。但是，看过下列代码后，就应该明白其危险性了。

通过<img>标签是有可能导致Javascript执行的，这样攻击者就可以做他想伪装的任何事情。

关于<style>也是一样：

参考：

HOW TO: 使用 Visual C# .NET 在 ASP.NET 中创建自定义错误报告
http://support.microsoft.com/kb/306355/zh-cn

HttpRequestValidationException 类 (System.Web)
http://msdn2.microsoft.com/zh-cn/library/system.web.httprequestvalidationexception(VS.80).aspx

MSDN: How To: Prevent Cross-Site Scripting in ASP.NET
http://msdn2.microsoft.com/en-us/library/ms998274.aspx

推荐大家阅读微软关于.Net安全的一系列文章：
http://msdn2.microsoft.com/en-us/library/ms978512.aspx

关于跨站脚本攻击请参考：

Wikipedia 维基大百科全书
http://en.wikipedia.org/wiki/Cross_site_scripting

Xfocus
http://www.xfocus.org/articles/200607/874.html

Google
http://www.google.com/search?q=%E8%B7%A8%E7%AB%99%E8%84%9A%E6%9C%AC%E6%94%BB%E5%87%BB

作者：DanceFire 发表于2007-4-11 10:52:00 原文链接

阅读：9834 评论：7 查看评论