Best way to implement a dictionary

Archive
1
:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By porsukk
:warning: Old Version Published before Godot 3 was released.

I need a dictionary to check if a word exist and to make searches like if there is a word which starts with specific letters. For example user input “big”. I need dic.has(“big”) and also dic.get_words(“big”)-> big,bigger. Currently I have a file which contains all the valid words and a file which contains the tokens for searching.
file1:
big
bigger
file2:
b
bi
big
bigg
bigge
bigger
I read the words and tokens to a dictionary and use the dictionary to make the searches. Problem is reading this many words takes 3-4 seconds on mobile phones. There is probably more clever way to do this. Something does not require me to read the whole file. So what is the best way to implement this kind of structure in godot?
Thank you in advance.

4
:bust_in_silhouette: Reply From: Zylann

I think you can load only the file with all words in memory even if it’s a few megabytes, just do it once.
Then, you can store the words in an array (not Dictionary) and sort this array alphabetically. If you don’t want the application to hang when doing this, use a thread.
This way, you can quickly find which words start with the letter you type, because they are listed in order, just like the way you actually search a paper dictionary.

You can try to do the search linearly with a for loop. If it’s too slow, you can precalculate at which index are the first letters in order to jump to them directly (again, like real-life dictionaries) and it will speed up your search to be around 10 times faster.

A more complicated way to go could be to build an actual tree from all the words, that could look like this:

- big
- bigger
- biggest
- butter
- buttefly
- bat
- bass
- battery

Becomes:

b
|-ig
| |-ger
| |-gest
|
|-ut
| |-ter
|   |-fly
|
|-a
  |-ss
  |-t
    |tery

However I imagine this would take a lot more space in memory due to nested containers.

Then I believe sorting the words and calculate indexes to jump could do the job quite fast already.

5
:bust_in_silhouette: Reply From: porsukk

I found a solution. It is not neccessary for any project but for my case it solved my problem. I implemented a DAWG (Direct Acyclic Word Graph). Here

is a nice article which helped me a lot