Combining Length restrictions and N-Best Techniques in multiple-pas search strategies

WWB w,BAO +,5A+WAW5 # ,5A A,OW"N,5 W NwAWw,55 5,+O 5A+A,BW,5 aL i  + 6L?L**L @ @?_ ,*L @|**i Aw #iT| Lu 5}?@* AiLh) @?_ L44?U@|L?  N?ih |@| L*|iU?U@ _i @|@*?)@ U% aLh_ BhL?@  ,_U #D @hUi*L?@ H ec 5W i4@*G @_h@?9}T | UTUi DEVWUDFW Pxowlsoh0sd hdu k wudwhjlh duh d qh h du| k l h w uhgx h wkh psxwdwl qdo w dqg php u| uh0 xluhphqw i odujh y dexodu| shh k uh jqlwl q | whp xl qj glhuhqw nlqg u psoh{ p ghoolqj i shh k dqg odqjxdjh1 Lq wkh Q0eh w dssu d k wkh p w h lhqw nq zohgjh xu h +x xdoo| d x wl p gho dqg d el2wuljudp odqjxdjh p gho, duh x hg u w w hoh w d k uw ol w +Q0eh w, i dowhuqdwlyh k|0 s wkh h 1 Wkhq/ wkh uhpdlqlqj p uh psoh{ nq zo0 hgjh xu h duh x hg w uh uh wkh h xhq h 1 Lq wkl sdshu zh su s h d qhz doj ulwkp w yhu ph wkh su eohp d ldwhg zlwk wkh lpsoh %Wud hed n0 Ed hg% Q0eh w doj ulwkp zkloh q huylqj lw lpsol 0 lw| dqg o z psxwdwl qdo w1 4 LQWURGXFWLRQ Wkl sdshu suh hqw d qhz Q0eh w hdu k doj ulwkp ed hg q wkh pelqdwl q i wz zhoo0nq zq wh k0 ql xh lq qwlqx x shh k uh jqlwl q= judppdu wkdw lps h d uh wul wl q lq wkh ohqjwk +qxpehu i z ug , i wkh uh jql}hg h xhq h ^6` dqg wkh wdq0 gdug wud hed n0ed hg Q0eh w doj ulwkp ^7/ 8/ :` Pxowlsoh0sd hdu k wudwhjlh duh d pp q k l h w uhgx h wkh psxwdwl qdo w dqg php0 u| uh xluhphqw i odujh0y dexodu| shh k uh jql0 wl q | whp ^:`1 Lq wkh Q0eh w dssu d k wkh p w h lhqw nq zohgjh xu h +x xdoo| d x wl p gho dqg d el2wuljudp odqjxdjh p gho, duh x hg u w w hoh w d k uw ol w +Q0eh w, i dowhuqdwlyh k|s wkh0 h 1 Wkhq/ wkh uhpdlqlqj p uh psoh{ nq zohgjh xu h +o qj0gl wdq h uhodwl q ehwzhhq z ug / odq0 jxdjh xqghu wdqglqj p gho / ydolg whohsk qh u uhglw dug qxpehu / su g|/ 111, duh x hg w uh uh dqg uh ughu wkh Q0eh w k|s wkh h zlwk d uhd qdeoh p0 sxwdwl qdo h uw1 Hyhq li zh d xph glhuhqw k|s wkh h kdyh ljqli0 l dqwo| glhuhqw uh / wkh h{d w Q0eh w doj ulwkp l i olwwoh sud wl do lqwhuh w eh dx h i lw psxwdwl qdo w1 Wkhuhi uh/ hyhudo dssu {lpdwh doj ulwkp kdyh A hi i@hU @ TTLh|i_ M) |i W A 5T@?  hi i@hU ThLiU| AWbH SH ehhq ghyho shg1 Wkh lpsoh w dqg ohd w h{shq lyh do0 j ulwkp i u qglqj wkh Q0eh w k|s wkh h l qh wkdw lpso| x h wkh wud hed n lqi updwl q i wkh wdqgdug qh0sd doj ulwkp ^4/ 5/ 9`1 Wkh wud hed n0ed hg Q0 eh w doj ulwkp uh xluh dop w q h{wud psxwdwl q uh sh w w wkh wdqgdug qh0sd doj ulwkp1 K zhyhu/ lq hoh wlqj wkh Q0eh w k|s wkh h lw x xdoo| pl h u xqghuh wlpdwh kljk uhg qh 1 Wkh wud hed n0ed hg Q0eh w doj ulwkp qo| nhhs qh sdwk zlwklq d z ug dqg pxowlsoh k|s wkh h duh q lghuhg qo| lq wkh wudq lwl q ehwzhhq z ug 1 K|0 s wkh h i glhuhqw ohqjwk d % qh wz wkuhh% dqg % qh wkuhh% duh qhyhu lpxowdqh x o| q lghu e| wkh wud hed n0ed hg Q0eh w doj ulwkp hyhq li e wk kdyh dop w wkh dph su edelolw| dqg zh q lghu d odujh qxpehu i k|s wkh h 1 Vhyhudo dssu d kh i p0 su pl h ehwzhhq wkh h{d w Q0eh w dqg wkh wud hed n0 ed hg doj ulwkp kdyh ehhq su s hg lq wkh olwhudwxuh w oyh wkdw su eohp1 K zhyhu wkh su s hg doj 0 ulwkp x xdoo| uhsuh hqw d ljql dqw lq uhd h lq wkh psxwdwl qdo w u php u| uh xluhphqw uh sh w w wkh ed l doj ulwkp1 Wkh dssu d k su s hg lq wkl sdshu pelqh wkh wud hed n0ed hg Q0eh w doj ulwkp zlwk wkh ohqjwk uh0 wul wl q lps hg e| d lpsoh judppdu w i u h wkh lq ox l q i h xhq h i glhuhqw ohqjwk lq wkh h0 oh whg ol w i z ug h xhq h 1 Wkh h nlqg i judp0 pdu duh x xdo lq wd n d qqh whg gljlw uh jqlwl q lq zkl k wkh h{sh whg qxpehu i gljlw pd| eh i u hg e| d qlwh0 wdwh judppdu1 Vlq h pxowlsoh lq huwl q u ghohwl q duh q w su edeoh/ wkh judppdu l x xdoo| lpsolhg w q lghu h xhq h i ohqjwk Nq.pi u dq| q/ zkhuh Nkd d pdoo {hg ydoxh dqg pudqjh iu p 3 w N41 Lq wkh uh xow suh hqwhg khuh zh kdyh q lghuhg ydoxh i Nlq wkh udqjh iu p 4 w 8/ lq pelqdwl q zlwk wkh wud hed n0ed hg Q0eh w doj ulwkp zlwk xs w 533 k|s wkh h shu hqwhq h1 Wkh i oo zlqj h wl q jlyh p uh ghwdlo de xw wkh su s hg doj ulwkp1 Wkhq/ zh suh hqw wkh uh xow e0 wdlqhg lq wz glhuhqw wd n = wkh uh jqlwl q i q0 qh whg gljlw dqg wkh uh jqlwl q i qxpehu 1 5 H[WHQGHG WUDFHEDFN0EDVHG Q0EHVW DOJRULWKP Wkh lpsoh w dqg ohd w h{shq lyh doj ulwkp i u e0 wdlqlqj pxowlsoh k|s wkh h zd u w su s hg lq ^7/ 8` d d p gl dwl q i wkh qh0sd doj ulwkp1 D lq wkh wdqgdug qh0sd doj ulwkp/ lq wkl Q0eh w do0 j ulwkp zh qo| nhhs qh wkh u| dw hd k z ug wdwh1 K zhyhu/ dw hd k judppdu q gh/ wkh wud hed n lqi u0 pdwl q l h{whqghg w w uh q w qo| wkh lqgh{ dqg uh i wkh eh w ulqj z ug/ exw do wkh lqgh{h dqg uh i wkh qeh w0 ulqj z ug 1 Dw wkh hqg i wkh h xhq h/ wkh dyhg wud hed n lqi updwl q l x hg w uh xu lyho| jhqhudwh wkh Q eh w dq zhu 1 Wkl p gl dwl q xss h d qhjoljleoh lq uhd h lq wkh psxwdwl qdo w de yh wkh wdqgdug qh0sd doj ulwkp1 K zhyhu/ wkl lpsol lw| l do wkh dx h i qh lps uwdqw gudzed n1 Vlq h wkl wud hed n0 ed hg doj ulwkp nhhs qo| qh wkh u| d hd k wdwh/ lw | whpdwl doo| pl h ph kljk ulqj k|s wkh h 1 I u h{dpsoh/ ohw x q lghu d lpsoh wd n d q0 qh whg gljlw uh jqlwl q1 Li wkh eh w k|s wkh l l % qh wkuhh%/ wkh wdqgdug wud hed n0ed hg doj ulwkp zloo q w eh deoh w jhqhudwh wkhu k|s wkh h ehjlq0 qlqj zlwk wkh z ug % qh% dqg hqglqj zlwk wkh z ug %wkuhh%1 Wkdw l / hyhq li wkh hqwhq h % qh wz wkuhh% kd dop w wkh dph su edelolw|/ lw zloo qhyhu dsshdu lq wkh ol w i wkh qeh w jhqhudwhg k|s wkh h 1 Wkl l eh dx h zh nhhs qo| qh s| i hd k z ug wdwh1 Wkhuh l qo| qh eh w ehjlqqlqj wlph i u wkh hqglqj z ug %wkuhh%/ dqg qo| qh eh w hqglqj wlph i u wkh u w z ug % qh%1 Lq wkh su s hg h{whq l q i wkh wdqgdug doj 0 ulwkp/ wkl su eohp l oyhg zlwk wkh dgglwl q i d judppdu wkdw i u h wkh q lghudwl q i h xhq h i glhuhqw ohqjwk lq wkh Q0eh w hdu k1 Iljxuh 4 k z wkh 60 wdwh judppdu wkdw q lghu h xhq h i 6q.l z ug dwhd kq ghl> i u dq| dueulwdu| q1 Lq jhqhudo/ wkh su s hg Q0Eh w doj ulwkp dgg d judppdu i N wdwh w wkh wud hed n0ed hg Q0eh w doj ulwkp i u qqh whg z ug uh jqlwl q1 Wkl lp0 soh judppdu i u h wkh q lghudwl q i glhuhqw ol w i k|s wkh h dw hd k i wkh Nq gh 1 Lq wkh lpsoh0 phqwdwl q i wkh su s hg doj ulwkp q lghuhg khuh/ wkh h{whqghg Q0Eh w doj ulwkp zloo nhhs d hsdudwh ol w zlwk wkh Q0eh w z ug h xhq h i ohqjwk qN.ldw hd k judppdu q gh l1 Dw wkh hqg i wkh h xhq h/ zh zloo hoh w wkh qo| Q0Eh w jo edo k|s wkh h dp qj wkh w wdo NQk|s wkh h w uhg lq doo wkh judppdu q gh 1 Wkh su s hg doj ulwkp pxowlsolh e| Nwkh hdu k sd h/ lq h lw nhhs d glhuhqw z ug wdwh wkh u| dw hd k judppdu q gh1 K zhyhu/ lq sud wl h/ wkh su 0 s hg doj ulwkp g h q w x xdoo| uhsuh hqw d ljqli0 l dqw lq uhd h lq wkh w wdo psxwdwl qdo w li zh lq oxgh d suxqlqj wh kql xh d wkh ehdp hdu k lq xu hdu k1 Li wkh i oo zlqj h wl q zh k z k z wkh su s hg h{whqghg Q0eh w doj ulwkp pd| eh x hixo lq ph uh jqlwl q wd n 1 Zh zloo do lq oxgh uh xow p0 sdulqj wkh shui updq h dqg psxwdwl qdo w i wkh su s hg doj ulwkp zlwk uh sh w w wkh wdqgdug +N@ 4, Q0eh w doj ulwkp i u qqh whg z ug uh j0 qlwl q1 6 UHVXOWV Vhyhudo uh jqlwl q h{shulphqw zhuh qgx whg lq u0 ghu w hydoxdwh wkh shui updq h i wkh su s hg Q0 eh w doj ulwkp1 Lq wkl sdshu zh suh hqw wkh uh xow ewdlqhg lq wz lpsoh wd n = qqh whg gljlw dqg qxpehu uh jqlwl q11 Wkh sdudphwhu wkdw ghqh wkh pp q h wl q i wkh uh jql}hu duh wkh i oo zlqj= 0 Vdpsolqj Iuh xhq |= ;333 dpsoh 2 0 Zlqg z l}h= 63 p 1 0 Zlqg z gl sod hphqw= 43 p 1 0 Sdudphwhul}dwl q= 47 PIFF h lhqw zlwk hs0 wudo oliwhulqj dqg 53 edqn owhu 1 Uhdo0wlph hs wudo phdq xe wud wl q1 0 Ghowd iudph = 5 0 D hohudwl q iudph = 4 614 Wd n 41 F qqh whg gljlw uh jqlwl q Lq wkl u w h{shulphqw/ zh q lghu wkh uh jqlwl q i gljlw wulqj x lqj zk oh z ug p gho i u wkh whq Vsdql k gljlw sox d p gho i wkh lohq h2q l h1 W wudlq wkh KPP p gho i wkh gljlw zh x h sduw i wkh Vshh kGdw ^<` Vsdql k Il{hg Qhwz un F usx / zkloh i u wh wlqj zh q lghuhg d glhuhqw gdwded h zlwk 4533 gljlw wulqj i glhuhqw ohqjwk 1 Khuh/ zh wxglhg wkh xpxodwlyh shu hqw i uuh w wulqj d d ixq wl q i wkh qxpehu Q i k|s wkh h dqg wkh qxpehu N i judppdu wdwh 1 Wkh uh xow duh i gluh w lqwhuh w i u dssol dwl q zkhuh wkh ol w i ydolg gljlw wulqj l uh wul whg w d qlwh hw/ u wkh wulqj lq oxgh ph nlqg i huu u0ghwh wlqj u huu u0 uuh wlqj gl dwl q1 Iljxuh 5 k z wkh shu hqw i uuh w wulqj wkdw zhuh pl lqj lq wkh jhqhudwhg Q0eh w h xhq h i u glhuhqw qxpehu i judppdu q gh / N@4/N@5 dqg N@ 81 Wkh uh xow i u N@5dqgN@8 k z d ohdu lpsu yhphqw zlwk uh sh w w wkh wdq0 gdug wud hed n0ed hg Q0eh w doj ulwkp +N@4,lizh q lghu d odujh qxpehu i k|s wkh h 1 Lq wkl h{shu0 lphqw/ zh kdyh 44 z ug p gho +43 gljlw . q l h, lq sdudooho lq hd k q gh i wkh judppdu1 Vlq h zh q lghu wkh p gho i wkh lohq h lq sdudooho zlwk wkh p gho i wkh gljlw / wkhuh l q gluh w uhodwl q eh0 wzhhq wkh judppdu q gh dqg wkh qxpehu i gljlw lq wkh k|sk wh h / l1h1/ zh dq kdyh h xhq h zlwk }hu / qh u p uh lohq h *z ug *1 Lq id w/ p w i wkh k|0 sk wh h qo| glhu lq wkh qxpehu dqg2 u s lwl q i wkh lohq h *z ug *1 Iljxuh 6 psduh wkh qxpehu i h qg uh xluhg w su h wkh wh w gdwded h/ d d ixq wl q i wkh qxp0 ehu i judppdu wdwh dqg wkh qxpehu i k|s wkh h 1 I u N@ 5/ wkh w wdo psxwdwl qdo w l lplodu w wkh w i wkh wdqgdug doj ulwkp +N@4,1 615 Wd n 51 Uh jqlwl q i qxpehu Lq wkl h{shulphqw/ zh wxglhg wkh uh jqlw q i odujh xuuhq | p qh| dp xqw +juhdwhu wkdq qh plo0 ol q,1 D ed holqh zh q lghuhg d lpsoh qqh whg z ug uh jqlwl q | whp zlwk xw dq| nlqg i judp0 pdu +qxpehu jhqhudwl q judppdu u q0judp p g0 ho ,1 Wkh y dexodu| q l whg i :3 z ug +xq / g / wuh / yhlqwlxq / yhlqwlg / wuhlqwd/ wuhlqwd |/ lhq/ g 0 lhqw / plo/ xq ploo q/ sh hwd / 111, uhdwhg iu p ghplsk qh p gho ^;`1 Wkh ghplsk qh p gho zhuh wudlqhg x lqj sduw i wkh sk qhwl doo|0ul k hqwhq h i wkh Vshh kGdw gdwded h1 Wkh 958 qxpehu i wh w zhuh hoh whg iu p wkh dph gdwded h1 I u wkl wd n/ zh wxglhg li wkh judppdu0iuhh uh j0 qlwl q | whp zd deoh w su ylgh wkh uuh w dq0 zhu/ dqg li wkh uuh w dq zhu zd wkh u w k|s wk0 h l judppdwl doo| uuh w1 Wkl judppdu0iuhh | 0 whp zd lqwhqwl qdoo| w lpsoh w su ylgh uh xow i sud wl do lqwhuh w lq dq| d h1 Wkh sxus h i wkh h{shulphqw zd mx w w wxg| wkh ehkdyl xu i wkh glhuhqw doj ulwkp 1 Wkh uh xow i wkh ed holqh | whp +Q@4>N @4, d zhoo d wkh uh xow ewdlqhg zlwk wkh wdqgdug dqg wkh h{whqghg wud hed n0ed hg doj ulwkp Q0eh w duh suh hqwhg lq wdeoh 41 Zh q lghuhg wkdw wkh uh j0 ql}hu zd su ylglqj d uuh w dq zhu zkhq wkh u w k|sk wh l uuh s qglqj w d lqjoh judppdwl doo|0 uuh w qxpehu zd uuh w1 Li wkl u w qxpehu zd q w uuh w zh kdg dq huu u1 Li wkh uh jql}hu glg q w su ylghg dq| judppdwl doo|0 uuh w qxpehu/ zh q lghuhg wkh hqwhq h d uhmh whg1 Q N uuh w huu u uhmh whg 44 593 :7 5<4 43 4 673 457 494 43 5 665 43< 4;7 433 4 693 4;: :; 433 5 69; 499 <4 Wdeoh 41 F psdul q i wkh uh xow ewdlqhg e| wkh ed holqh | whp +Q@4>N @4,/ wkh wdqgdug wud hed n0ed hg Q Eh w doj 0 ulwkp +QA4>N @ 4,/ dqg wkh su s hg doj ulwkp +N@ 5,1 D qxpehu l uhmh whg li wkh uh jql}hu l g h q w jhqhudwh d judppdwl doo|0 uuh w k|s wkh l 1 Wkh uh xow lqgl dwh wkdw wkh su s hg Q0Eh w do0 j ulwkp zlwk N@ 5 uhgx h wkh qxpehu i lq uuh w uh jql}hg qxpehu iu p 457 +N@4,w 43</zkhq zh q lghu wkh u w 43 k|s wkh h / +Q@43,1 Zh dq do e huyh wkdw lq uhd lqj wkh qxpehu i k|0 sk wh h iu p 43 w 433 su gx hg px k p uh zu qj k|s wkh h 7 FRQFOXVLRQV Wkl sdshu wxglhg wkh pelqdwl q i wz zhoo0 nq zq wh kql xh lq shh k uh jqlwl q= judppdu wkdw lps h d uh wul wl q lq wkh ohqjwk +qxpehu i z ug , i wkh uh jql}hg h xhq h dqg wkh wud hed n0 ed hg Q0eh w doj ulwkp1 Wkh su s hg doj ulwkp do0 ohyldwh wkh su eohp i wkh wdqgdug wud hed n0ed hg Q0eh w doj ulwkp/ zkloh nhhslqj lw lpsol lw|1 Wkh uh xow lq wd n d uh jqlwl q i gljlw wulqj dqg qxpehu iu p wkh Vsdql k Vshh kGdw Gdwded h ^<` lqgl dwh wkdw wkh su s hg doj ulwkp l d j g k l h i u uhdo0wlph dssol dwl q 1 Wkh doj ulwkp kd ehhq douhdg| hoh whg i u pphu ldoo| dydlodeoh shh k uh jqlwl q | whp dqg dssol dwl q 1 Uhihuhq h ^4` W1N1 Ylqw |xn1 %Hohphqw0Zl h Uh jqlwl q i F qwlqx x Vshh k F q l wlqj i Z ug Iu p d Vsh lhg Y dexodu|/% Nlehuqhwl d +F|ehuqhw0 l ,/ Q 1 5/ ss1 4660476/ Pdu k0Dsulo 4<:41 ^5` K1 Qh|1 %Wkh X h i d Rqh0Vwdjh G|qdpl Su 0 judpplqj Doj ulwkp i u F qqh whg Z ug Uh j0 qlwl q/% LHHH Wudq 1 D x wl / Vshh k/ Vljqdo Su 1/ Y o1 65/ q 1 5/ ss 59605:4/ Dsulo 4<;71 ^6` F1K1 Ohh dqg O1 Udelqhu/ %D Iudph0V|q ku q x Qhwz un Vhdu k Doj ulwkp i u F qqh whg0Z ug Uh jqlwl q/% LHHH Wudq 1 D x wl / Vshh k/ Vljqdo Su 1/ Y o1 6:/ q 1 44/ ss 497<0498;/ Q 0 yhpehu 4<;<1 ^7` M1E1 Pdulq dqg H1 P qwh1 %Jhqhudwl q i Pxo0 wlsoh K|s wkh l lq F qqh whg Sk qhwl 0Xqlw Uh jqlwl q e| d P glhg Rqh0Vwdjh G|qdpl Su judpplqj Doj ulwkp/% Su 1 Hxu shh k ;</ Y o1 5/ ss173;07441 Sdul / Vhswhpehu 4<;<1 ^8` Y1 Vwhlqel 1 %Vhqwhq h0K|s wkh h Jhqhudwl q lq d F qwlqx x 0Vshh k Uh jqlwl q V| whp/% Su 1 Hxu shh k ;</ Y o1 5/ ss1840871 Sdul / Vhswhp0 ehu1 4<;<1 ^9` Odzuhq h Udelqhu/ Ellqj0Kzdqj Mxdqj1 Ixqgd0 phqwdo i Vshh k Uh jqlwl q1 Suhqwl h Kdoo 4<<61 ^:` U1 V kzduw}/ O1 Qjx|hq dqg M1 Pdnk xo1 %Pxowlsoh0Sd Vhdu k Vwudwhjlh %1 Lq Dxw pdwl Vshh k dqg Vshdnhu Uh jqlwl q/ Noxzhu D dg0 hpl 4<<91 Fkdswhu 4;1 ^;` M hE1Pdulq / D1 Q jxhuld dqg D1 E qd0 i qwh1 %Wkh ghplsk qh= dq h lhqw xez ug xqlw i u qwlqx x shh k uh jqlwl q/% Su 1 HX0 URVSHHFK*<:/ ss1 45480454;/ Uk gh / Vhswhp0 ehu 4<<:1 ^<` Vshh kGdw LL1 Vshh k Gdwded h i u wkh uhdwl q i y l h gulyhq whoh huyl h 1 Odqjxdjh Hqjlqhhulqj Uh xu h 1 HF Whohpdwl 1 kwws=22zzz1 shh kgdw1 uj1 3n1 WORD STRING    3n2+1 WORD STRING 3n3+2 WORD STRING Selec N-Bes Hypo hesis ENTER Iljxuh 4= Judppdu qhwz un jhqhudwlqj qqh whg z ug wulqj i glhuhqw ohqjwk 0 1 2 3 4 5 6 1 11 22 42 80 160 QXPEHURIK SRWKHVLV U H P D L Q L Q J  V W U L Q J  H U U R U V     k=1 k=2 k=5 Iljxuh 5= F psdul q i wkh shu hqw i pl hg uuh w gljlw wulqj d d ixq wl q i wkh qxpehu i judppdu q gh ndqg wkh qxpehu i psxwhg k|s wkh h 1 0 50 100 150 200 250 300 350 400 1 11 22 42 80 160 QXPEHURIK SRWKHVLV F R P S X W D W L R Q D O  F R V W   V H F R Q G V  k=1 k=2 k=5 Iljxuh 6= F psdul q i wkh psxwdwl qdo w i wkh su s hg doj ulwkp d d ixq wl q i wkh qxpehu i judppdu q gh ndqg wkh qxpehu i psxwhg k|s wkh h +Wd n 4,1