tag:blogger.com,1999:blog-73366974420400346482011-11-27T15:18:36.603-08:00Do Best DeveloperSolo Lhttp://www.blogger.com/profile/08279326134525121712noreply@blogger.comBlogger21100tag:blogger.com,1999:blog-7336697442040034648.post-84030006307964977052010-12-21T01:27:00.000-08:002010-12-21T21:47:35.709-08:00设计绘图系统<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://4.bp.blogspot.com/_ll_kCneBVRo/TRGQwyC9kxI/AAAAAAAAAOY/Xpcn0KmwoOI/s1600/001.gif"><img style="float:right; margin:0 0 10px 10px;cursor:pointer; cursor:hand;width: 86px; height: 400px;" src="http://4.bp.blogspot.com/_ll_kCneBVRo/TRGQwyC9kxI/AAAAAAAAAOY/Xpcn0KmwoOI/s400/001.gif" border="0" alt=""id="BLOGGER_PHOTO_ID_5553378983266849554" /></a><br />2007年8月我第一次考虑设计并实现了一个绘图系统。该系统使用图中的一些符号来绘制某些电力行业中要求的图形。系统要求运行在浏览器中，因此我选择了Flash，使用ActionScript3.0来开发。时至今日该系统已经使用了3年多。<br /><br />在这三年中需求不断的增长，其中一些直接暴露了设计中的局限性。我准备通过第二个版本来解决设计中的那些问题，下面是我的一些思考：<br /><br />1.Shape结构，使用组合模式。<br />2.Shape大小调整<br />3.Shape的放大和缩小<br />4.Shape的布局<br />5.shape的绘制<br />6.Focus管理<br />7.Shape的拖拽<br />8.ContextMenu管理<br />9.Event分派<br />10.快捷键<br />11.光标管理<br />12.ScrollView<br /><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/7336697442040034648-8403000630796497705?l=dobestdeveloper.blogspot.com' alt='' /></div>Solo Lhttp://www.blogger.com/profile/08279326134525121712noreply@blogger.com0tag:blogger.com,1999:blog-7336697442040034648.post-25640865147956888092008-11-20T05:02:00.000-08:002008-11-20T05:05:26.147-08:00MMSeg分词算法简述<p>MMSeg只是实现了<a href="http://chtsai.org/" title="Chih-Hao Tsai" target="_blank" style="color: rgb(0, 0, 204); ">Chih-Hao Tsai</a>的MMSEG算法，这是一个来源于网络的分词算法。我照抄了算法开始的部分：</p><p><strong>MMSEG: A Word Identification System for Mandarin Chinese Text Based on Two Variants of the Maximum Matching Algorithm</strong></p><p>Published: 1996-04-29<br />Updated: 1998-03-06<br />Document updated: 2000-03-12<br />License: Free for noncommercial use<br />Copyright 1996-2006 <a href="http://chtsai.org/" title="Chih-Hao Tsai" target="_blank" style="color: rgb(0, 0, 204); ">Chih-Hao Tsai</a> (Email: hao520 at yahoo.com )</p><p>您可以在<a href="http://technology.chtsai.org/" title="Chih-Hao Tsai's Technology Page" target="_blank" style="color: rgb(0, 0, 204); ">Chih-Hao Tsai's Technology Page</a>找到算法的原文。</p><p>我将依据自己的理解来简述MMSeg分词算法的基本原理，如有错误请不吝赐教。</p><p>首先来理解一下chunk，它是MMSeg分词算法中一个关键的概念。Chunk中包含依据上下文分出的一组词和相关的属性，包括长度(Length)、平均长度(Average Length)、标准差的平方(Variance)和自由语素度(Degree Of Morphemic Freedom)。我在下面列出了这4个属性的计算方法：</p><table border="1"><tbody><tr align="center"><td>属性</td><td>含义</td><td>代码位置</td></tr><tr><td>长度(Length)</td><td>chuck中各个词的长度之和</td><td>org.solol.mmseg.internal.Chunk.getLength()</td></tr><tr><td>平均长度(Average Length)</td><td>长度(Length)/词数</td><td>org.solol.mmseg.internal.Chunk.getAverageLength()</td></tr><tr><td>标准差的平方(Variance)</td><td>同数学中的定义</td><td>org.solol.mmseg.internal.Chunk.getVariance()</td></tr><tr><td>自由语素度(Degree Of Morphemic Freedom)</td><td>各单字词词频的对数之和</td><td>org.solol.mmseg.internal.Chunk.getDegreeOfMorphemicFreedom()</td></tr></tbody></table><p><strong>注意：</strong>表中的含义列可能有些模糊，最好参照MMSeg的源代码进行理解，代码所在的函数已经给出了。</p><p>Chunk中的4个属性采用Lazy的方式来计算，即只有在需要该属性的值时才进行计算，而且只计算一次。</p><p>其次来理解一下规则(Rule)，它是MMSeg分词算法中的又一个关键的概念。实际上我们可以将规则理解为一个过滤器(Filter)，过滤掉不符合要求的chunk。MMSeg分词算法中涉及了4个规则：</p><ul><li>规则1：取最大匹配的chunk (Rule 1: Maximum matching)</li><li>规则2：取平均词长最大的chunk (Rule 2: Largest average word length)</li><li>规则3：取词长标准差最小的chunk (Rule 3: Smallest variance of word lengths)</li><li>规则4：取单字词自由语素度之和最大的chunk (Rule 4: Largest sum of degree of morphemic freedom of one-character words)</li></ul><p>这4个规则分别位于org.solol.mmseg.internal.MMRule.java、org.solol.mmseg.internal.LAWLRule.java、org.solol.mmseg.internal.SVWLRule.java和org.solol.mmseg.internal.LSDMFOCWRule.java4个源文件中。之所以这样来处理是因为我们可以方便的增加规则和修改应用规则的顺序。</p><p>这4个规则符合汉语成词的基本习惯。</p><p>再次来理解一下两种匹配方式，简单最大匹配(Simple maximum matching)和复杂最大匹配(Complex maximum matching)。</p><p>简单最大匹配仅仅使用了规则1。</p><p>复杂最大匹配先使用规则1来过滤chunks，如果过滤后的结果多于或等于2，则使用规则2继续过滤，否则终止过滤过程。如果使用规则2得到的过滤结果多于或等于2，则使用规则3继续过滤，否则终止过滤过程。如果使用规则3得到的过滤结果多于或等于2，则使用规则4继续过滤，否则终止过滤过程。如果使用规则4得到的过滤结果多于或等于2，则抛出一个表示歧义的异常，否则终止过滤过程。</p><p>最后通过一个例句--研究生命起源来简述一下复杂最大匹配的分词过程。MMSeg分词算法会得到7个chunk，分别为：</p><table border="1"><tbody><tr><td>编号</td><td>chunk</td><td>长度</td></tr><tr><td>0</td><td>研_究_生</td><td>3</td></tr><tr><td>1</td><td>研_究_生命</td><td>4</td></tr><tr><td>2</td><td>研究_生_命</td><td>4</td></tr><tr><td>3</td><td>研究_生命_起</td><td>5</td></tr><tr><td>4</td><td>研究_生命_起源</td><td>6</td></tr><tr><td>5</td><td>研究生_命_起</td><td>5</td></tr><tr><td>6</td><td>研究生_命_起源</td><td>6</td></tr></tbody></table><p>使用规则1过滤后得到2个chunk，如下：</p><table border="1"><tbody><tr><td>编号</td><td>chunk</td><td>长度</td></tr><tr><td>4</td><td>研究_生命_起源</td><td>6</td></tr><tr><td>6</td><td>研究生_命_起源</td><td>6</td></tr></tbody></table><p>计算平均长度后为：</p><table border="1"><tbody><tr><td>编号</td><td>chunk</td><td>长度</td><td>平均长度</td></tr><tr><td>4</td><td>研究_生命_起源</td><td>6</td><td>2</td></tr><tr><td>6</td><td>研究生_命_起源</td><td>6</td><td>2</td></tr></tbody></table><p>使用规则2过滤后得到2个chunk，如下：</p><table border="1"><tbody><tr><td>编号</td><td>chunk</td><td>长度</td><td>平均长度</td></tr><tr><td>4</td><td>研究_生命_起源</td><td>6</td><td>2</td></tr><tr><td>6</td><td>研究生_命_起源</td><td>6</td><td>2</td></tr></tbody></table><p>计算标准差的平方后为：</p><table border="1"><tbody><tr><td>编号</td><td>chunk</td><td>长度</td><td>平均长度</td><td>标准差的平方</td></tr><tr><td>4</td><td>研究_生命_起源</td><td>6</td><td>2</td><td>0</td></tr><tr><td>6</td><td>研究生_命_起源</td><td>6</td><td>2</td><td>4/9</td></tr></tbody></table><p>使用规则3过滤后得到1个chunk，如下：</p><table border="1"><tbody><tr><td>编号</td><td>chunk</td><td>长度</td><td>平均长度</td><td>标准差的平方</td></tr><tr><td>4</td><td>研究_生命_起源</td><td>6</td><td>2</td><td>0</td></tr></tbody></table><p>匹配过程终止。最终取“研究”成词，以相同的方法继续处理“生命起源”。</p><p>分词效果:</p><p>Simple ->研究生_命_起源_<br />Complex->研究_生命_起源_<br />Simple ->研究生_教育_<br />Complex->研究生_教育_</p><p><strong>注意：</strong>Simple表示简单最大匹配的分词效果，Complex表示复杂最大匹配的分词效果。</p><div class="blogger-post-footer"><img width='1' height='1' src='https://blogger.googleusercontent.com/tracker/7336697442040034648-2564086514795688809?l=dobestdeveloper.blogspot.com' alt='' /></div>Solo Lhttp://www.blogger.com/profile/08279326134525121712noreply@blogger.com0