hey Gurus,
Need a tweak on some logic.Im developing a module for an application that is supposed to take in words(from various sources) in an unscrambbled manner and through some series of queries against a Database return possible words that match the unscrambled word.As an Instance,an unscrambled word is" airnige"(proper form being Nigeria),The module does series of queries and "should " return "Nigeria" as a result.Time is a factor, as this result must be returned to the main Application in a max time of 10 Secs.I've got some logic(wouldnt want to bore us with it's details here) working though, but it becomes inefficient with longer queries.Would appreciate Your side of Logic on solving this more efficiently.The app as a whole is being implement with Java.
Thanks

Let's see the logic. Personally, I would love to see it. It would go a long way in getting you help. Anyone who is bored by it, probably is not willing to or cannot help.

it seems u have ur definition of the word "unscrambled" reversed. u r using it contextually as the exact opposite of what it means.

Yeah, but we get the point though.

thanks Guys,
davidt,There's a database of Official words of the English Language, it has 7 tables each being populated with words of the same length arranged in Alphabetical order(for instance "tableOne" is populated with 2 letter words,"tableTwo " with three letter words, and it goes on like that for the remaining tables with "tableEight"populated with words which length exceed 7). The length method of the String class is used to determine the length of of the "Unscrambled" String that was received.The returned length is used to query a particular table of the Dbase.Various Threads replace each letter(from the received unscrambled word)at a particular index.While this goes on, another thread queries the Dbase with the result of each "newly" formed word after the "index replacement" takes place.Like i said, this works well and is time efficient with Shorter words but misbehaves with words beyond Six letters.I hope my logic was understood.Would really appreciate it.Should Post the code snippet soon.

*Index being the position of a letter in a word.

/*you may try to translate this into java and sql yourself i wrote it with actionscript and sqlite in mind:

My logic is this:
i assumed all your english words are in one sqlite table

split your input word in an array say lojikarray
*/

var lojikarray: Array = inputword.split("";

//try to select the word containing all the letters from an sql db
//to do this, we join the array to generate the sql statement

var joinedarray: String = lojikarray.join("%' AND columnname LIKE '%";

var sqlstatement: String = "SELECT * FROM tablename WHERE columnname LIKE '%" add joinedarray add "%'";

/**
our sql statement should now look like (SELECT * FROM tablename WHERE columnname LIKE '%n%' AND columnname LIKE '%i%' AND columnname LIKE '%g%' AND columnname LIKE '%e%' AND columnname LIKE '%r%' AND columnname LIKE '%i%' AND columnname LIKE '%a%')

You can now query your sql and it will return only the words containing the letters n,i,g,e,r,i,a in any order available in the dictionary.
you should know how to discard results greater than 7 letters

loop the result array and place this in the loop:
if (result.length == inputword.length){ accept result }else{reject result}

**/

That's all folks!
lekeojikutu@yahoo.com

using an SQL only solution will definitely be inefficient as your SQL should simply return all words that have the same length and have all the letters of the word you're descrambling, therefore the SQL statement is dynamically generated, and there r several sub-statements that drill down to the right word. even the best RDBMSes will not help with this as the search deterioration factors include the length of the word (which determines how many select trips you make to the server) as well as the server performance.

since you're using java, the fastest way might be to have a simple select statement that selects only words that have the same length as the word u are descrambling and match @ least one letter (the first letter for instance), the returned resultset is then put in an array (faster) or arraylist. drilling down @ this point becomes real easy.

or u could get real technical @ this point & implement the A* algorithm (meaning u have to figure out how to express this problem as a path-finding problem, which most puzzles really are, define the structure - problem space and solution space etc).

in general, to increase efficiency u simply minimize your server trips (SQL select statements), and populate a java data-structure with the search-space data and finish up the search.

but let me digress and ask, beyond it's academic value, what practical value does this application provide?

thanks lojik,
implementing your logic in Java takes beyond ten seconds to complete even with a dual processor being Used, complicated by the facts that all the english words were in a single table.Thanks all the same, it exposed something to me that's helping

thanks logica,
We've been contemplating doing that. but recently decided to optimize the main application to reduce it's execution time, so this "gained" time(which is estimated to be 4.5secs) can serve as a Plus for this little module.We dont know how this wil turn out though.As regards details of the main application, it's beyond an academic stuff. u could send mail to basmo13@gmail.com for details.i must really say thank you

Well i guess this problem has been solved, but while reading it something popped into my head. It think the spell check in word processors can give an insight to the module. Like just typing a wrong word and it quickly underlines it within a second, and on right clicking it gives possible words. Open office is open source you can take a look at how this feature was implemented

thanks Ade,
will go through the source of the open office project n try implemention.

the logic of auto-complete and spell-check is quite different. they usually have heuristic algorithms to try and figure out what you are trying to spell. this is different from unscrambling a word since the word was not misspelled, but simply having the letters rearranged. only a minute class of misspelled words fall in this category. what you are really trying to do is develop what you can call an anagram resolver or solver.

Just out of curiousity:
When your anagram is unscrambled, is it just meant to return one matching solution or all matching solutions?
Example
Anagram = nosops
will this return just "spoons" or will it also return "snoops"?

implemented the logic of that autocomplete stuff, agreeing with logica,outside being a bit diferent from what we were loking at, the memory usage was high( posibly we didnt optimise it) for a  module.thanks guys , its becoming clearer now.

@tomX
one possible and correct value is returned

oh i forgot to mention. i did develop an anagram resolver just for the fun of it a while back, and it was pretty efficient. no db use (words stored in flat files and r loaded each time the program runs). it returned all possible anagrams, and when it couldn't find any, it actually tried to guess in case of misspelled words like a spell-checker (the algorithm was really simplistic, as a real spell-checker would also take into consideration the proximity of keys on the keyboard e.g. given the spelling "wronh" the spell-checker should correctly guess you were trying to type "wrong". note that "wrong" and "wronh" are not anagrams)

how long ago did u develop that?, played with one a while ago too but it was so inefficient in terms of Execution time. that was in my early days as a programmer.How efficient was yours in terms of execution time(measured in Milliseconds) and possible mem usage~

last year (march) i think, i can send u the bundle if u r so much interested. it was never anything beyond an academic exercise to me. i developed it simply to solve scrambled word puzzles on another forum. if u remove all the unnecessary code such as the output (print) statements as well as the pseudo spell-check it won't take more than 2 secs for any word.

would appreciate it a lot, would possibly have something to learn from it.basm13@yahoo.co.uk.Thanks.

i got an error that ur email doesn't exist.

funny why you got that message, i've been using that mail for the past 6 yrs. basmo13@yahoo.co.uk or basmo13@gmail.com . thanks Man!

Bassie:

. . . .@tomX
one possible and correct value is returned

What criteria will you use to deterimine the value returned?

@tomX
I posted the Logic  i used to achieve that earlier on, the only problem then was it's inefficiency  with longer queries.that has been taken care of though, thanks to guys like you  who contributed.