86 Reviewed Article — ARIMASACJ, No. 36., 2006 A Word Game

This article reports on the approach taken, experience gathered, and results found in building a tool to support the derivation of solutions to a particular kind of word game. This required that techniques had to be derived for simple yet acceptably quick

86

ReviewedArticle—ARIMA/SACJ,No.36.,2006

AWordGameSupportToolCaseStudy

TBotha,DGKourie,BWWatson

Fastar/EspressoResearchGroup,DepartmentofComputerScience,UniversityofPretoria,Pretoria,SouthAfrica0001

1INTRODUCTION

”...youshallseekalldayereyou ndthem;and,whenyouhavefoundthem,theyarenotworththesearch.”[MerchantofVenice]Oneisoftensurprisedathowcomplexandchallengingcertainwordpuzzles/gamesarethatareregularly—dailyorweekly—beingsolvedbythousandsofreadersofmagazinesandnewspapers.Thecompilersofthesepuzzlesmakeahostofassumptionsthatarepresumedtobe“commonknowledge”basedontheirownthor-oughbackgroundknowledgeoftherelevantnaturallanguage.Theseassumptionsrelatetomatterssuchaslanguageknowledge,wordconstruction,wordus-age,synonyms,generalcurrenta airsknowledge,etc.

Alongwiththeseassumptions,thetypicalwordpuzzleinvolvesalargebodyofpossiblecandidateso-lutionsthatcan ttheparticularsub-entryofthepuz-zle.Theoverallsolutionisthustosolveapatternmatchingproblemofnaturallanguagewordsthat tthepuzzleinaparticularcombination.Itisthere-forenotsurprisingthatavarietyofsupporttoolsareavailableforpuzzlesolverenthusiasts.Mostofthesesupporttoolsareavailableinbookformatsuchastyp-icaldictionariesororderedwordlistsbasedoncriteriathatareuniquetotherelevantgameorwordproblem.Examplesinclude:

Alphabeticorderingaccordingtowordlength Wordtypesusedforclusteringandordering—suchasclustersofgeographicorpersonnames,

This article reports on the approach taken, experience gathered, and results found in building a tool to support the derivation of solutions to a particular kind of word game. This required that techniques had to be derived for simple yet acceptably quick

JointSpecialIssue—Advancesinend-userdata-miningtechniques

87

fromthenaturallanguageusedinordertofacilitatequeries.Theconclusionofthearticle,insection6,includesanassessmentoffutureworkthatisneededonthesupporttool.

2BACKGROUND2.1ProblemStatement

Thefollowingisashortdescriptionof“letterspeletjie”—awordgamethatappearsinSaturdayeditionsoftheJohannesburg-basedAfrikaansnewspaper,Beeld,andthatisthetargetofthesupporttoolthathasbeenbuilt.Theplayerispresentedwithanumberofcells.Eachcellinthepuzzlecontainsanumber(between1and26)thatrepresentsaletter.Theonlycluegiven,isthatanumberofcells(usually2)arepre- lledwithletters.Thechallengeistoestablishwhichletterisrepre-sentedbywhichnumber.Fortunately,theanswerisalwaysaone-to-onemapping.Someimbedded“clues”arepresentsuchastheparticularwordlengthallowedforanaccompanyingword.Shortwords—2or3characterslong—arethebestcandidateswithwhichtostartandtouseforaninitialtrial-and-errorapproach.

Thechallengetobemetistobuildatoolthatsupportsthequestforasolutiontosuchaproblem—aproblemwhichmaybedescribedroughlyasakindofconstraintsatisfactionproblem.Morespeci cally,asolutiontothisprobleminvolves,ataminimum,apartialmatchsearchandretrieval.Becauseofitscomplexity,anumberofprerequisitesneedtobemetbyatoolthathandlesthistypeofproblem.Themainonesarelistedbelow.

The rstpracticalchallengetoovercomerelatestodealingwiththelargevolumeofwordsthatarepotentialcandidatesforthe“knowledgebase”ofthetool.Intheexamplecasethatwasusedtoimplementthesupporttool,anAfrikaanslanguagedictionaryofmorethan132000wordswasconstructedandused.Thisisinlinewithvarioussourcesthatsuggestthatmorethan130.000andevenasmuchas180.000wordscanbeinvolvedinAfrikaanswordgamepuzzles1.Inordertosetupthedictionary,thefollowingquestionsneededtobeanswered:

Howcanthedictionaryberepresentedtosupportacceptablyfastsearching?

Howcanthestoragevolumeofthedictionarybelimitedtoacceptablelevels?

Whatsearchtechniquesthatencompassstrictpartialmatchsearch/retrievalshouldbeused?Inaddition,arelativesimplebutpowerfulquerylan-guagewasneededtodeliversolutionsforthesearch/retrievalgoals.Thelanguagehadtoallowfordi-rectinteractivepersonalusage,aswellasforprogram-maticaccess.Alsoneededwasasetofsupportand

This article reports on the approach taken, experience gathered, and results found in building a tool to support the derivation of solutions to a particular kind of word game. This required that techniques had to be derived for simple yet acceptably quick

88

typesofsearchesmentionedabove.Therefore,insomecasesahybridapproach(combiningtypesofsearch)istakenbytheproposedsolution.

ReviewedArticle—ARIMA/SACJ,No.36.,2006

arm

1

ar3

da5

em7

rm9

1

.

.

.

1

1

.

11

daar

.

1

.

1

.

.

1

.

.

warm1..1

3PROPOSEDWORDREPRESENTATION

Inderivingtheproposedsolution,the rstconsider-ationwashowtorepresentthethousandsofnaturallanguage(Afrikaans)http://doc.guandang.netplicatedtechniques—mostlyinvolvingtrees,tries,andhashindexing—havebeenproposed.(Seeforexample:[11,5,4,12].)Mostofthesetech-niquesexposestrengthsinsomeareasandweaknessesinothers.Thisstudywasaimedatasimpleyetpow-erfulapproachtoresolvetheproblemathand.Theproposedsolutionisbasedonasimpleyetpowerfulin-verted letechnique.Asmentioned,whencombinedwithotherretrievaltypesthisapproacho ersanele-gantandacceptablyquicksolution.

3.1BuildingtheWordListDatabase

ThedecisionwasmadetousetheObjectREXX2scriptinglanguagefordevelopingtheexampleimple-mentation.ObjectREXX(likeC++)o ersbothtra-ditionalandobject-orientedfeatures.ObjectREXXisparticularlystronginitsstringhandlingfeatures,haspowerfultracingabilities,ando erselegantstreamed lehandlingwhichwasverybene cialfordevelop-mentoftheexampleimplementation3.Despiteitsinterpretivenature,ObjectREXXprovedsurprisinglyadequateforpresentpurposes.However,infutureex-te …… 此处隐藏：24134字，全部文档内容请下载后查看。喜欢就下载吧 ……