Go to Page... |
Thread Tools | Display Modes |
11-06-15, 11:34 AM | #1 |
Efficient string and table manipulation for an in-game dictionary
Hello, friends.
I've written code to auto-complete words in editboxes, using the global environment to scan for and break apart strings to generate a weighted dictionary. On an enUS client, the initial run generates approximately 5000 words, which is a pretty good starting point. Now, when iterating the table of words to find potential matches, I'm using these conditions:
The downside to my current approach is:
Example:
Also, to reduce "unnecessary" calculations, I've put a 20 index max on the generated suggestion list, meaning it will stop comparing words of the dictionary to the suggestion list after hitting the 20th index. The word will still be pushed to the list, though. Without optimizing to some degree, there will be a small FPS stutter when using extremely common combinations of characters, such as "es", "er", "et", "ae", "an", etc. I was wondering if anyone has ideas to improve this algorithm and make it smarter. This is the code used to generate suggestions: Lua Code:
This is the code used to generate the dictionary: Lua Code:
Last edited by MunkDev : 11-07-15 at 09:39 PM. |
|
11-07-15, 10:56 AM | #2 |
Interesting stuff. And a novel approach with the dictionary building.
I'm not sure about the best way to find misspelt words. But I did read this article a while ago: http://www.norvig.com/spell-correct.html It implements a very simple spell checker in Python, and at the bottom are links to other languages as well (since we're talking Lua perhaps a Javascript one would be the closest equivalent). I'm not sure how CPU-heavy it is, though... Perhaps you'd need to only check at certain intervals or reduce the algorithm's complexity if it must run more often. But maybe it's a starting point. Let us know what you end up doing, it's an interesting problem so I'd like to know what you find out. |
|
11-09-15, 11:42 PM | #3 | |
I try it a little, without optimization or deeply consideration :
Lua Code:
Result is
Then calc the ignored chars like 'nd' for 'need', 'ee' is ignored. At the last, calc the diff caused by wrong orders. Then we can get the most expected words with the least diff value. The code is not well designed, may it can provide a little help for you. |
||
WoWInterface » Developer Discussions » General Authoring Discussion » Efficient string and table manipulation for an in-game dictionary |
«
Previous Thread
|
Next Thread
»
|
Display Modes |
Linear Mode |
Switch to Hybrid Mode |
Switch to Threaded Mode |
|
|