
COMPUTER ENGINEERING
1999 25 10 Vol.25 No.10 1999



дʶĲʵ
Z־ǿ
ժҪʶڴģʽʶ⣬ò㷨ڵʶдͼٶȡһֺʶ㷨ƷPVMнܷ
ؼʣ㷨д֣б̻ƥ
The Parallel Implementing of the Off-line Chinese Character Discrimination
Shao Xiuli Liu Jing Fan Zhiqiang
(Department of Computer and System Sciences,Nandai University,Tianjin 300071)
AbstractBecause Chinese Character discrimination is a recognizing problem of large number of patern classes,in order to improve the OLCCR's(Off Line Character Recognize)speed running on the stand-alone computer,PA(Parallel Algorithm)should be used instead of SA(Sserial Algorithm).Thus,an efficacious parallel algorithm on Chinese Character recognizing was put forward and its performance in the environment of PVM was dissertated in this paper.
Key wordsParallel algorithm;Off-line Chinese Character discrimination;Parallel environment;Spring match
дַָʶͼģʽʶȵ⣬д뼼ǼӦõĸ֮һ , ɹҪƽ⡣ĿǰûгɹдֵʶϵͳдֵʶҪ豸ƣѧãƽ񻯣ƹӦáͳдַʶ󶼲ûںֱʻṹķֲ𣬲Ϊѻַʶ𷽷ǵͬһֶӦдڱʻĳ̡ǶȲͬ𣬵˴ԴڼԣͼʶͿƶΪݽеƥ䡣ʰд庺ʶΪһռƫƵĵģʽʶƥ⣬ֵͼƥǰͼͼеƥ䣬ҳͼӦּģʽʶŹ㷺Ӧãʶָʶȡ
дַܲ淶ṹӣͨȡֽлֵӡˢķԵõԽܵʶʣҪǽиĽµ㷨Ľ㷨һܴԽܵʱʶ֡ƺõ㷨ڲлִȴԴﵽʵõĳ̶ȣӲǮų̈ͬʱЩʶûǿܳܵģһЩԵĹ
1  㷨ܷ
1.1  ƥ㷨˼
Ŀǰֵͼƥ㷨϶࣬ȡͼϢ㷨ȣԴʶͼҪ̡ʵáǲõĵƥһģʽƥ㷨ͼʶϵͳģʽȫһµ㷨ͼͼ"" Σݶͼͼ֮""ĴСͼӦһдַ , ҵͬĹ , һ㷨ǶдַƹϾʶ̫͡Щԭ , ԰ÿΪάͼʶͳΪάͼƥ , άͼƥǰĶάͼѾڶάͼеƥ䣬ҳͼӦʱĲǸֵĽṹǲȡһֻڽƴƥ㷨ĵƥ㷨˼ͨͼͼ""Σݶͼͼ֮""ĴСӦһĶάͼ󣬼ģͼľ룬СӦģͼΪͼƥ䡣ҲͬһֵĲͬдΪĳ""εĽ,˿Գо㷨Ϊռƫƥƥ㷨[2]н˶άͼƥĶ̬滮㷨 , 㷨ľ˼ǣÿд庺ֱʾΪm*n(һΪ20*16)Ķάͼһm*nľ,ԪͼһһӦҶֵΪ10һάͼͿɱʾΪΪnmڽƴƥеĲ롢ɾ滻ͼĵƥ䡣һдֵʶǰѸд庺ֵͼʾΪdnϵmλ,Ȼ봮ִ֮ľ,ݼȷһֵʶͼĵԾΪƳ̶ȵı׼ͼImagelibƥһʶͼP,ҲһشҳĳͼʶַPСþСĳһ涨ֵʱͿΪʶֵҵ , 㷨μ[2]
1.2  ƥ㷨ܷ
Ϊάͼƥ㷨ЧӦø㷨дʶ˴ʵ鹤ʵǰ׼һС͵д庺ֿ⣬ÿа46֣ÿ10дÿĴСΪ20*16Ĵʶַ뺺ֿеÿֵĵԾ룬ѵԾСĶӦΪʶַӦĺ֡ͨʵõ72%ʶʣȽ⡣ʶʵҲ֣ȻѾý㷨˺ܴĽĶ̬滮㷨ܴСʱȻȽϳʱ临ӶΪÿļΪO(m2n2), mnֱΪеܸÿĲͬдɼ[2]㷨ʱ临Ӷ̫ߣ㷨ڵٶ̫еֻ㷨еٶûܶ޷ƹ,бҪԸ㷨һĴ,нܵĲ㷨ܸĽ⡣[2]е㷨лһֳ԰취ǰд庺ֳֿɼ֣ʶͼֿĵƥ佫м㣬ԵóԾСĺ֣Ȼ⼸СԾҳд庺ֿеԾСĺ֡[2]е㷨лʵַһܺͷ
2  ϵṹ벢г
ĿǰϵṹҪжԳʽദϵͳSMPģдϵͳMPPļȺCluster˵ClusterSMPMPPͷֲʽϵͳĸ໥صĲϵṹУCluster(ļȺ)ŵڽõѸٷչ͹㷺Ӧáŵĸ߿Լ߿ԣȻ磺ɳԭо豸Ͷ룻ɰͬṹɽͬʵŻܣɽлдŵ㣻ClusterܣеĻʩװPCȺʵ顣
2.1  г
һ㲢ģͿɷΪMIMDSIMDģͣMIMD(ָָ)ָָͬɲͬĽͬʱɣַΪࣺSPMDMPMDSPMDеĳͬģͬݲͬMPMDеĳ칹ģ벻ͬ
2.2  бģͼ
бָΪһ㷨һг򣬲бģͿɷΪʽʽģ͡ڱʵУѡϢΪPVMΪб̻PVMһĹϵͳڶĹԼ⹤XPVMȣصǣͨǿʺTCP/IP绷ʺMPPģϵͳϵͳģСԴֻмMBевл̶֧PVMˣPVMһֵ֧Ĺɿ޸ģݳ̶ȸߣ࿪Թ߰ãȫΪһ׼ֲPVM¡
3  㷨Ĳʵ
÷Ļ˼ǽл֣PnֽΪPnӿÿʶһַʱȸԼʶ𣬶ӵóPnַУѡȡʶַԾСġ
PVMб̻£ʵֲ㷨ʱʹõı£
PnPn=Htӽ̺ţ
Patternʶַͼ(һά)
ElasticDistһ飬PatterngиĵԾ룻
AveragElasticDist(Pattern,g)Patternĳgƽ룻
MinDistPatternСԾ룻
GroupNumberPatternʶΪĳеĳַ;
A:СΪPn,A[i]صiӽõƽԾ;
min(A,MinNo)AеСֵ±긳MinNo
Ҫ£
MinDist=ֵ
while g<G do
for t=1 to Pn par_do
A[t]=AveragElasticDist(Pattern,g);g=g+1;
endfor
if MinDist>min(A,MinNo)
MinDist=min(A,MinNo);GroupNumber=MinNo;
endif
endwhile
return GroupNumber
ò㷨̣
ٹ㲥 Pattern ӽ;
ڽͼеǰtеH ݷֱ͸һӽ,ǰg1;
ظ2Pn,ֱ𷢸ڶ,,,Pnӽ;
ܵȴPnؽ;
ݴPnֵȡСֵ,СMinDist,ֵMinDist,GroupNumber=Ӧ;
еݶѲ,н,GroupNumber;ظִТڡ
ӽ̵̣
ٽ̹㲥ַPattern
ڽһַݲѹ
۷ֱʶַÿһַĵԾ룬ȡƽֵ
ܷشƽֵ
㷨ʵʽģ̸ӽ̷ʹʶַռǵʶҼԴõյʶӽ̸Լʶʶַ
4  㷨ķ
ֲл¶Ը㷨ʵ飺һֻPCɵClusterÿ̨PCĻWindows NTһֻ쳱1000AϷ÷Žڵ , ÿڵͨ٣ʱ临ӶΪO(m2n2/Pn +2GH+Gmn/8)+(2G+1)Tpʵͨʱ䲢ûŽڵӶԼ,ӽ̵ͨŷӣҳԭڱ㷨Ĳлƻ,ͬҪ:Ҫڽܵȫnӽ̵ķֵŷһ , ʹɼḺ̌ȺķʱԵȴһּݵĵ÷ĲԽΪ 
1 ڵ 2 ڵ4 ڵ8 ڵ
ʱ21521074626432
ͨʱ21521074624430
ӽƽʱ2134917436.5228.7
ӽƽͨʱ18157186169.3
ٱ0.741.482.533.69
мɱ2152214825024512
Ч0.740.740.630.36
5  
Ŀǵ[2]㷨ʵ֣Ҷκһֶάͼʶ𶼿Բ̫ĸĶͿֱӦãҲҪģеκԤȵĴ(㷨)ֻٶ̫ڲʵ֣ԱĲûж[2]㷨иĽֻʹеѭлĿϣܴӲнǶȶдʶгԡյóǣںǴģʽʶ⣬θĽ㷨ʱ临Ӷȶ̫ߣҪʹдʶٶȿ졢ʶʸߣѸĽ취һõ㷨ʹ֮ʵ֡
߼飺1965ŮڣҪоΪ桢㷨
ߵλϿѧϵͳѧϵ300071
ο
1 Tang D,Gupta G.An Efficient Parallel Dynamic Programming Algorithm.Computers Math Apple,1995,30(8)152
2  ,׸.ѻдַʶDP㷨,йͼͼѧ,1998,3(3)58
ոڣ1999-03-01
