📄 ictclas分词系统研究（五）--n最短路径 - sinboy的菜地 - csdnblog.mht
字号:
all the=20
edges </P>
<P> <FONT color=3D#0000ff>=20
//=E5=AF=B9=E7=A0=94=E7=A9=B6=EF=BC=88=E5=9B=9B=EF=BC=89=E4=B8=AD=E7=9A=84=
=E5=9B=BE=E5=85=AD=E6=89=80=E7=A4=BA=E7=9A=84=E8=A1=A8=EF=BC=8C=E6=8C=89=E5=
=88=97=E4=BC=98=E8=BF=9B=E8=A1=8C=E9=81=8D=E5=8E=86=EF=BC=8C=E6=8A=8A=E6=AF=
=8F=E4=B8=AA=E5=88=97=E7=9A=84=E6=95=B0=E6=8D=AE=E6=94=BE=E5=88=B0=E4=B8=80=
=E4=B8=AA=E4=B8=B4=E6=97=B6=E5=B7=A5=E4=BD=9C=E9=98=9F=E5=88=97=E4=B8=AD<=
/FONT> <BR> =20
while(pEdgeList!=3D0 && =
pEdgeList->col=3D=3DnCurNode)<BR> =20
{<BR> =20
nPreNode=3DpEdgeList->row;<BR> =20
eWeight=3DpEdgeList->value;//Get the value of=20
edges<BR> =20
for(i=3D0;i<m_nValueKind;i++)<BR> =20
{<BR> if(nPreNode>0)//Push the weight =
and the=20
pre node infomation<BR> =20
{<BR> =20
if(m_pWeight[nPreNode-1][i]=3D=3DINFINITE_VALUE)<BR> &nb=
sp; &nbs=
p;=20
break;</P>
<P> <FONT=20
color=3D#0000ff> =
//=E6=8A=8A=E8=A1=8C=E5=80=BC=EF=BC=88ROW=EF=BC=89=E6=94=BE=E5=85=A5=E9=98=
=9F=E5=88=97=E4=B8=AD=EF=BC=8C=E5=B9=B6=E4=B8=94=E4=BF=9D=E8=AF=81=E9=98=9F=
=E5=88=97=E7=9A=84=E6=8E=92=E5=BA=8F=E6=98=AF=E6=8C=89Weight=E5=80=BC=E4=BB=
=8E=E5=B0=8F=E5=88=B0=E5=A4=A7=E6=8E=92=E5=88=97</FONT></P>
<P> queW=
ork.Push(nPreNode,i,eWeight+m_pWeight[nPreNode-1][i]);<BR> &nb=
sp; =20
}<BR> =
else<BR> =20
{<BR> =20
queWork.Push(nPreNode,i,eWeight);<BR> =
=20
break;<BR> }<BR> =
}//end=20
for<BR> =20
pEdgeList=3DpEdgeList->next;<BR> =
<BR> =20
}//end while<BR> =
<BR> =20
//Now get the result queue which sort as weight.<BR> =
//Set the=20
current node information<BR> =20
for(i=3D0;i<m_nValueKind;i++)<BR> =20
{<BR> m_pWeight[nCurNode-1][i]=3DINFINITE_VALUE;<BR>&nbs=
p; =20
}<BR> //memset((void=20
*),(int),sizeof(ELEMENT_TYPE)*);<BR> =
//init=20
the weight<BR> i=3D0; </P>
<P><FONT color=3D#0000ff> =20
//=E4=B8=B4=E6=97=B6=E5=B7=A5=E4=BD=9C=E9=98=9F=E5=88=97=E4=B8=AD=E5=8F=96=
=E5=87=BA=E5=89=8D=E9=9D=A2=E7=9A=84=E4=B8=80=E4=B8=AA=EF=BC=8C=E5=B9=B6=E8=
=AE=B0=E8=B7=AF=E8=B7=AF=E5=BE=84=E9=95=BF=E5=BA=A6=E7=9A=84=E5=92=8C</FO=
NT><BR> =20
while(i<m_nValueKind&&queWork.Pop(&nPreNode,&nIndex,&a=
mp;eWeight)!=3D-1)<BR> =20
{//Set the current node weight and parent<BR> =20
if(m_pWeight[nCurNode-1][i]=3D=3DINFINITE_VALUE)<BR> &nb=
sp; =20
m_pWeight[nCurNode-1][i]=3DeWeight;<BR> else=20
if(m_pWeight[nCurNode-1][i]<eWeight)//Next =
queue<BR> =20
{<BR> i++;//Go next queue and record next=20
weight<BR> if(i=3D=3Dm_nValueKind)//Get =
the last=20
position<BR> =20
break;<BR> =20
m_pWeight[nCurNode-1][i]=3DeWeight;<BR> =20
}<BR> =20
m_pParent[nCurNode-1][i].Push(nPreNode,nIndex);<BR> =20
}<BR> }//end for</P>
<P> return 1;<BR>}</P>
<P>m_nParent=E7=9A=84=E6=9C=80=E7=BB=88=E7=BB=93=E6=9E=9C=E5=A6=82=E4=B8=8B=
=E5=9B=BE=E4=B8=89=E6=89=80=E7=A4=BA=EF=BC=8C=E5=AE=83=E5=9C=A8=E5=BD=93=E5=
=89=8D=E4=BD=8D=E7=BD=AE=E8=AE=B0=E5=BD=95=E8=AF=A5=E8=AF=8D=E7=9A=84=E7=88=
=B6=E8=8A=82=E7=82=B9=E4=BD=8D=E7=BD=AE=EF=BC=88=E5=AF=B9=E5=BA=94=E4=BA=8E=
=E7=A0=94=E7=A9=B6=EF=BC=88=E5=9B=9B=EF=BC=89=E4=B8=AD=E7=9A=84=E5=9B=BE=E5=
=9B=9B=EF=BC=89</P>
<P align=3Dright><IMG alt=3D""=20
src=3D"http://p.blog.csdn.net/images/p_blog_csdn_net/sinboy/queResult2.jp=
g"></P>
<P align=3Dcenter> =E5=9B=BE=E4=B8=89</P>
<P> int CNShortPath::Output(int **nResult,bool bBest,int=20
*npCount)<BR>{//sResult is a string array</P>
<P> ......<BR> =20
GetPaths(m_nVertex-1,i,nResult,bBest);<BR> <BR>}</P>
<P><FONT =
color=3D#0000ff>//=E8=8E=B7=E5=8F=96=E5=88=86=E8=AF=8D=E8=BE=93=E5=87=BA=E8=
=B7=AF=E5=BE=84=E3=80=82=E6=8C=87=E7=A0=94=E7=A9=B6=EF=BC=88=E5=9B=9B=EF=BC=
=89=E4=B8=AD=E7=9A=84=E5=9B=BE=E5=9B=9B</FONT></P>
<P>void CNShortPath::GetPaths(unsigned int nNode,unsigned int nIndex,int =
**nResult,bool bBest)<BR>{<BR> CQueue=20
queResult;<BR> unsigned int=20
nCurNode,nCurIndex,nParentNode,nParentIndex,nResultIndex=3D0;<BR> &n=
bsp; =20
<BR> if(m_nResultCount>=3DMAX_SEGMENT_NUM)//Only need 10=20
result<BR> return=20
;<BR> nResult[m_nResultCount][nResultIndex]=3D-1;//Init the result=20
<BR> queResult.Push(nNode,nIndex);<BR> =20
nCurNode=3DnNode;<BR> nCurIndex=3DnIndex;<BR> =
bool=20
bFirstGet;<BR> =20
while(!queResult.IsEmpty())<BR> {<BR> while(nCurNode>0=
)//<BR> {//Get=20
its parent and store them in=20
nParentNode,nParentIndex<BR> if(m_pParent[nCurNode-1][nC=
urIndex].Pop(&nParentNode,&nParentIndex,0,false,true)!=3D-1)<BR>&=
nbsp; {<BR> =20
nCurNode=3DnParentNode;<BR> =20
nCurIndex=3DnParentIndex;<BR> }<BR> if(=
nCurNode>0)<BR> &=
nbsp; =20
queResult.Push(nCurNode,nCurIndex);<BR> }<BR> if(nC=
urNode=3D=3D0)<BR> {=20
//Get a path and output<BR> =20
nResult[m_nResultCount][nResultIndex++]=3DnCurNode;//Get the first=20
node<BR> =
bFirstGet=3Dtrue;<BR> =20
nParentNode=3DnCurNode;<BR> =20
while(queResult.Pop(&nCurNode,&nCurIndex,0,false,bFirstGet)!=3D-1=
)<BR> =20
{<BR> =20
nResult[m_nResultCount][nResultIndex++]=3DnCurNode;<BR> =
=20
=20
bFirstGet=3Dfalse;<BR> =20
nParentNode=3DnCurNode;<BR> =
}<BR> =20
nResult[m_nResultCount][nResultIndex]=3D-1;//Set the=20
end<BR> m_nResultCount+=3D1;//The number of =
result add by=20
1<BR> =
if(m_nResultCount>=3DMAX_SEGMENT_NUM)//Only need=20
10 result<BR> return =
;<BR> =20
nResultIndex=3D0;<BR> =20
nResult[m_nResultCount][nResultIndex]=3D-1;//Init the result </P>
<P> if(bBest)//Return the best result, ignore=20
others<BR> return=20
;<BR> }<BR> queResult.Pop(&nCurNode,&nCurIn=
dex,0,false,true);//Read=20
the top node<BR> =20
while(queResult.IsEmpty()=3D=3Dfalse&&(m_pParent[nCurNode-1][nCur=
Index].IsSingle()||m_pParent[nCurNode-1][nCurIndex].IsEmpty(true)))<BR>&n=
bsp; {<BR> =20
queResult.Pop(&nCurNode,&nCurIndex,0);//Get rid of=20
it<BR> =20
queResult.Pop(&nCurNode,&nCurIndex,0,false,true);//Read the top=20
node<BR> }<BR> =20
if(queResult.IsEmpty()=3D=3Dfalse&&m_pParent[nCurNode-1][nCurInde=
x].IsEmpty(true)=3D=3Dfalse)<BR> {<BR> =
=20
m_pParent[nCurNode-1][nCurIndex].Pop(&nParentNode,&nParentIndex,0=
,false,false);<BR> =20
nCurNode=3DnParentNode;<BR> =20
nCurIndex=3DnParentIndex;<BR> =20
if(nCurNode>0)<BR> &nbs=
p;=20
queResult.Push(nCurNode,nCurIndex);<BR> }<BR> }<BR>}<BR><=
/P>
<P>=E6=9C=80=E7=BB=88=E5=BE=97=E5=88=B0=E6=9C=80=E7=9F=AD=E8=B7=AF=E4=B9=88=
=EF=BC=880=EF=BC=8C1=EF=BC=8C2=EF=BC=8C3=EF=BC=8C6=EF=BC=8C9=EF=BC=8C11=EF=
=BC=8C12=EF=BC=89=EF=BC=8C=E9=87=8C=E9=9D=A2=E7=9A=84=E6=95=B0=E5=80=BC=E5=
=88=86=E5=88=AB=E5=AF=B9=E5=BA=94=E7=A0=94=E7=A9=B6=EF=BC=88=E5=9B=9B=EF=BC=
=89=E4=B8=AD=E5=9B=BE=E5=9B=9B=E7=9A=84=E4=B8=8B=E6=A0=87=EF=BC=8C=E5=88=B0=
=E6=AD=A4=E5=88=86=E8=AF=8D=E7=9A=84=E7=AC=AC=E4=B8=80=E5=A4=A7=E6=AD=A5=E5=
=B0=B1=E7=BB=93=E6=9D=9F=E4=BA=86=EF=BC=8C=E5=B9=B6=E5=BD=A2=E6=88=90=E6=9C=
=80=E7=BB=88=E7=BB=93=E6=9E=9C=EF=BC=9A=E5=A7=8B##=E5=A7=8B/=E4=BB=96/=E8=
=AF=B4/=E7=9A=84/=E7=A1=AE=E5=AE=9E/=E5=9C=A8/=E7=90=86/=E6=9C=AB##=E6=9C=
=AB</P>
<P> </P><BR><BR>
<P id=3DTBPingURL>Trackback:=20
http://tb.blog.csdn.net/TrackBack.aspx?PostId=3D745498</P><BR></DIV>
<DIV class=3DpostFoot>
<SCRIPT src=3D""></SCRIPT>
[<A =
title=3D=E5=8A=9F=E8=83=BD=E5=BC=BA=E5=A4=A7=E7=9A=84=E7=BD=91=E7=BB=9C=E6=
=94=B6=E8=97=8F=E5=A4=B9=EF=BC=8C=E4=B8=80=E7=A7=92=E9=92=9F=E6=93=8D=E4=BD=
=9C=E5=B0=B1=E5=8F=AF=E4=BB=A5=E8=BD=BB=E6=9D=BE=E5=AE=9E=E7=8E=B0=E4=BF=9D=
=E5=AD=98=E5=B8=A6=E6=9D=A5=E7=9A=84=E4=BB=B7=E5=80=BC=E3=80=81=E5=88=86=E4=
=BA=AB=E5=B8=A6=E6=9D=A5=E7=9A=84=E5=BF=AB=E4=B9=90=20
href=3D"javascript:d=3Ddocument;t=3Dd.selection?(d.selection.type!=3D'Non=
e'?d.selection.createRange().text:''):(d.getSelection?d.getSelection():''=
);void(saveit=3Dwindow.open('http://wz.csdn.net/storeit.aspx?t=3D'+escape=
(d.title)+'&u=3D'+escape(d.location.href)+'&c=3D'+escape(t),'keyi=
t','scrollbars=3Dno,width=3D590,height=3D300,left=3D75,top=3D20,status=3D=
no,resizable=3Dyes'));saveit.focus();">=E6=94=B6=E8=97=8F=E5=88=B0=E6=88=91=
=E7=9A=84=E7=BD=91=E6=91=98</A>] =20
sinboy=E5=8F=91=E8=A1=A8=E4=BA=8E 2006=E5=B9=B405=E6=9C=8819=E6=97=A5 =
13:43:00 </DIV></DIV><LINK=20
href=3D"http://blog.csdn.net/sinboy/Services/Pingback.aspx" =
rel=3Dpingback><!--<rdf:RDF =
xmlns:rdf=3D"http://www.w3.org/1999/02/22-rdf-syntax-ns#"xmlns:dc=3D"http=
://purl.org/dc/elements/1.1/"xmlns:trackback=3D"http://madskills.com/publ=
ic/xml/rss/module/trackback/"><rdf:Descriptionrdf:about=3D"http://blog.cs=
dn.net/sinboy/archive/2006/05/19/745498.aspx"dc:identifier=3D"http://blog=
.csdn.net/sinboy/archive/2006/05/19/745498.aspx"dc:title=3D"ICTCLAS=E5=88=
=86=E8=AF=8D=E7=B3=BB=E7=BB=9F=E7=A0=94=E7=A9=B6=EF=BC=88=E4=BA=94=EF=BC=89=
--N=E6=9C=80=E7=9F=AD=E8=B7=AF=E5=BE=84"trackback:ping=3D"http://tb.blog.=
csdn.net/TrackBack.aspx?PostId=3D745498" /></rdf:RDF>-->
<SCRIPT>function hide(){showComment();}</SCRIPT>
<BR><BR><BR>
<DIV class=3Dpost id=3Dcsdn_zhaig_ad_yahoo></DIV><SPAN=20
id=3DAnthem_Comments.ascx_ltlComments__><SPAN =
id=3DComments.ascx_ltlComments><BR>
<DIV id=3Dcomments>
<H3></H3>
<DIV class=3Dpost>
<DIV class=3DpostTitle><A title=3D"permalink: =
=E5=9B=9E=E5=A4=8D=EF=BC=9AICTCLAS=E5=88=86=E8=AF=8D=E7=B3=BB=E7=BB=9F=E7=
=A0=94=E7=A9=B6=EF=BC=88=E4=BA=94=EF=BC=89--N=E6=9C=80=E7=9F=AD=E8=B7=AF=E5=
=BE=84"=20
href=3D"http://blog.csdn.net/sinboy/archive/2006/05/19/745498.aspx#452886=
">#</A> <A=20
name=3D452886> </A>solarsoft =E5=8F=91=E8=A1=A8=E4=BA=8E2006-06=
-11 11:04:00 IP:=20
60.178.99.*</DIV>
<DIV =
class=3DpostText>=E6=AC=A2=E8=BF=8E=E5=8A=A0=E5=85=A5=E8=87=AA=E7=84=B6=E8=
=AF=AD=E8=A8=80=E5=A4=84=E7=90=86QQ=E7=BE=A4:25885352</DIV></DIV><BR></DI=
V></SPAN></SPAN>
<SCRIPT language=3Djavascript>
ad_width=3D468;
ad_height=3D60;
adcss=3D2;
unionuser=3D19;
ad_type=3D'j';
count=3D5;=20
</SCRIPT>
<SCRIPT language=3Djavascript src=3D"http://tagegg.csdn.net/showads.js"=20
type=3Dtext/javascript></SCRIPT>
<SCRIPT language=3Djavascript src=3D"http://blog.csdn.net/js/showgm.js"=20
type=3Dtext/javascript></SCRIPT>
<SCRIPT type=3Dtext/javascript>document.write("<img =
src=3Dhttp://counter.csdn.net/pv.aspx?id=3D24 border=3D0 width=3D0 =
height=3D0>");</SCRIPT>
<DIV class=3DCommentForm id=3Dcommentform>
<H3>=E5=8F=91=E8=A1=A8=E8=AF=84=E8=AE=BA</H3>
<DIV id=3DAnthem_PostComment.ascx_UpdatePanel1__>
<DIV id=3DPostComment.ascx_UpdatePanel1>
<TABLE class=3DCommentForm>
<TBODY>
<TR>
<TD width=3D69 height=3D0></TD>
<TD></TD></TR>
<TR>
<TD width=3D70>=E5=A4=A7=E5=90=8D=EF=BC=9A</TD>
<TD align=3Dleft><INPUT id=3DPostComment.ascx_tbName style=3D"WIDTH: =
300px"=20
disabled maxLength=3D32 size=3D40 name=3DPostComment.ascx:tbName> =
<SPAN=20
id=3DPostComment.ascx_RequiredFieldValidator2=20
style=3D"DISPLAY: none; COLOR: red" initialvalue=3D""=20
evaluationfunction=3D"RequiredFieldValidatorEvaluateIsValid"=20
display=3D"Dynamic" =
errormessage=3D"<br>=E8=AF=B7=E8=BE=93=E5=85=A5=E5=B0=8A=E5=A7=93=E5=A4=A7=
=E5=90=8D"=20
=
controltovalidate=3D"PostComment.ascx_tbName"><BR>=E8=AF=B7=E8=BE=93=E5=85=
=A5=E5=B0=8A=E5=A7=93=E5=A4=A7=E5=90=8D</SPAN> </TD></TR>
<TR>
<TD width=3D70>=E7=BD=91=E5=9D=80=EF=BC=9A</TD>
<TD align=3Dleft><INPUT id=3DPostComment.ascx_tbUrl style=3D"WIDTH: =
300px"=20
disabled maxLength=3D256 size=3D40 name=3DPostComment.ascx:tbUrl> =
</TD></TR>
<TR>
<TD colSpan=3D3>=E8=AF=84=E8=AE=BA <SPAN =
id=3DPostComment.ascx_RequiredFieldValidator3=20
style=3D"DISPLAY: none; COLOR: red" initialvalue=3D""=20
evaluationfunction=3D"RequiredFieldValidatorEvaluateIsValid"=20
display=3D"Dynamic" =
errormessage=3D"<br>=E8=AF=B7=E8=BE=93=E5=85=A5=E8=AF=84=E8=AE=BA"=20
=
controltovalidate=3D"PostComment.ascx_tbComment"><BR>=E8=AF=B7=E8=BE=93=E5=
=85=A5=E8=AF=84=E8=AE=BA</SPAN> <BR><TEXTAREA =
id=3DPostComment.ascx_tbComment style=3D"WIDTH: 381px; HEIGHT: 193px" =
disabled name=3DPostComment.ascx:tbComment rows=3D10 =
cols=3D50></TEXTAREA>=20
</TD></TR>
<TR>
<TD colSpan=3D3><SPAN=20
id=3DAnthem_PostComment.ascx_btnSubmit__></SPAN> =
</TD></TR>
<TR>
<TD colSpan=3D3><SPAN id=3DPostComment.ascx_Message=20
style=3D"COLOR: =
red">=E6=B3=A8=E5=86=8C=E7=94=A8=E6=88=B7=E6=89=8D=E8=83=BD=E5=8F=91=E8=A1=
=A8=E8=AF=84=E8=AE=BA=E3=80=82=E5=A6=82=E6=9E=9C=E4=BD=A0=E6=B2=A1=E6=9C=89=
=E7=99=BB=E5=BD=95=EF=BC=8C=E8=AF=B7=E7=82=B9=E5=87=BB<A=20
=
href=3D"http://passport.csdn.net/member/UserLogin.aspx?from=3Dhttp://blog=
.csdn.net/sinboy/archive/2006/05/19/745498.aspx">=E7=99=BB=E5=BD=95</A></=
SPAN>=20
</TD></TR></TBODY></TABLE></DIV></DIV></DIV></DIV>
<P id=3Dfooter>Powered by: <BR><A id=3DFooter1_Hyperlink2=20
href=3D"http://scottwater.com/blog" name=3DHyperlink1><IMG=20
src=3D"http://blog.csdn.net/images/100x30_Logo.gif" border=3D0></A> <A=20
id=3DFooter1_Hyperlink3 href=3D"http://asp.net/" name=3DHyperlink1><IMG=20
src=3D"http://blog.csdn.net/images/PoweredByAsp.Net.gif" border=3D0></A> =
<BR>Copyright =C2=A9 sinboy </P>
<SCRIPT src=3D"http://www.csdn.net/common/counter.js"></SCRIPT>
<SCRIPT type=3Dtext/javascript>
<!--
var Page_Validators =3D new =
Array(document.getElementById("PostComment.ascx_RequiredFieldValidator2")=
, document.getElementById("PostComme⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -