Search Unity

Constructing a trie on iOS

Discussion in 'iOS and tvOS' started by BasketQase, Mar 22, 2011.

  1. BasketQase

    BasketQase

    Joined:
    Sep 12, 2005
    Posts:
    97
    Hello,

    I'm porting an old Unity word game I made from PC standalone to iOS and I'm running into a hangup with the time it takes for my code to construct a trie from about 50,000 elements. On the Mac and Windows, it took a little over a second to load the words and construct the trie, but on the iPad I'm testing on, it takes about 30 seconds to do the same job. This is obviously an unacceptable wait time to load the game, so I was hoping someone might have some suggestions for another data structure I could use or some optimizations for the one I've constructed. The following is my trie code (the empty "if" blocks are where I had logging code inserted):

    Code (csharp):
    1.  
    2.  
    3. class TrieNode {
    4.     var letter : String;
    5.     var isWord : boolean;
    6.     var nextNode = new Hashtable();
    7.    
    8.     function Init() {
    9.         this.letter = "\0";
    10.         this.isWord = false;
    11.     }
    12. }
    13.  
    14. var trieRoot = new TrieNode();
    15. var numNodes = 0;
    16.  
    17.  
    18. function NewNode(letter : String) {
    19.     var theNode = new TrieNode();
    20.     numNodes++;
    21.    
    22.     theNode.Init();
    23.     theNode.letter = letter;
    24.    
    25.     return theNode;
    26. }
    27.  
    28. function AddWords(words : String[]) {
    29.         for (var word : String in words) {
    30.             AddWord(word);
    31.         }
    32.  
    33.         var appControl = FindObjectOfType(AppControl) as AppControl;
    34.         appControl.SendMessage("OnLoadWordsComplete");
    35. }
    36.  
    37. function AddWord(word : String) {
    38.     var currNode = trieRoot;
    39.    
    40.     for (var currLetter : char in word) {
    41.         nextLetter = "" + currLetter;
    42.         if ( currNode ) {
    43.             if ( currNode.nextNode[nextLetter] ) {
    44.             }
    45.             else {
    46.                 currNode.nextNode[nextLetter] = NewNode(nextLetter);
    47.             }
    48.             currNode = currNode.nextNode[nextLetter];
    49.         }
    50.         else {
    51.         }
    52.     }
    53.    
    54.     currNode.isWord = true;
    55. }
    56.  
    57. function IsWord(word : String) {
    58.     var currNode = trieRoot;
    59.    
    60.     for (var currLetter : char in word) {
    61.         nextLetter = "" + currLetter;
    62.        
    63.         if ( currNode ) {
    64.             if ( currNode.nextNode[nextLetter] ) {
    65.             }
    66.             else {
    67.                 return false;
    68.             }
    69.             currNode = currNode.nextNode[nextLetter];
    70.         }
    71.         else {
    72.             return false;      
    73.         }
    74.     }
    75.    
    76.     if ( currNode.isWord ) return true;
    77. }
    78.  
    Thanks,
    ~Rob
     
  2. JohnnyA

    JohnnyA

    Joined:
    Apr 9, 2010
    Posts:
    4,653
    Here's some code I have used, might have a few errors in this version(its also not tested on latest Unity), but the data structures are what you need.

    100k word list loads in about 0.1 seconds on my Mac, about 3 seconds on 3GS.

    Main difference I can see is the main data structure uses a (fixed length) array (not a hashtable). Also a node doesn't need to know what letter it is as it's parent "knows" by virtue of the array position. A single hashtable is used during construction to speed the process.

    Code (csharp):
    1.  
    2. class WordTrie {
    3.         var word:boolean;
    4.         var children:WordTrie[];
    5.        
    6.         function WordTrie(word:boolean) {
    7.           this.word = word;
    8.           children = new WordTrie[26];
    9.         }
    10.        
    11.         function WordTrie(word:boolean, children:WordTrie[]) {
    12.           this.word = word;
    13.           this.children = children;
    14.         }
    15.     }
    16.  
    Code (csharp):
    1.  
    2. class Dictionary{
    3.  
    4.     var words:WordTrie;
    5.     var nodes:Hashtable;
    6.  
    7.     // Construct the dictionary        
    8.     function Dictionary() {
    9.         nodes = new Hashtable();   
    10.         generateDictionary();
    11.         words = (nodes[""] as WordTrie);
    12.         nodes = null;
    13.     }
    14.  
    15.     // Check if word is in the dictionary
    16.     function isWord(word:String):boolean {
    17.         return isWord(word, 0, words); 
    18.     }  
    19.    
    20.     function isWord(word:String, pos:int, trie:WordTrie):boolean {
    21.         var c:WordTrie = trie.children[charToAscii(word[pos])];
    22.         if (c != null) {
    23.             if (word.length == pos + 1) {
    24.               return c.word;
    25.             } else {
    26.                 return isWord(word, pos + 1, c);
    27.             }
    28.         } else {
    29.           return false;
    30.         }
    31.     }
    32.    
    33.     function generateDictionary() {
    34.             // Point this at your dictionary file (.txt file with a single word per line)
    35.             var sr:System.IO.StreamReader = new System.IO.StreamReader("/tmp/words.txt");
    36.             var word:String = sr.ReadLine();
    37.             while (word != null) {
    38.                 addWord(word,null,0);  
    39.                 word = sr.ReadLine();
    40.             }
    41.             sr.Close();
    42.     }
    43.    
    44.     function addWord(word:String, child:WordTrie, childPos:int) {
    45.         if (nodes.ContainsKey(word)) {     
    46.             if (child == null){
    47.               (nodes[word] as WordTrie).word = true;
    48.             } else {
    49.                
    50.               (nodes[word] as WordTrie).children[childPos] = child;
    51.             }
    52.         } else if (word.length > 0) {
    53.             var node:WordTrie = new WordTrie(child == null ? true : false);
    54.             node.children[childPos] = child;                        
    55.             nodes[word] = node;
    56.             addWord(word.Substring(0, word.length - 1), node, charToAscii(word[word.length - 1]));
    57.         } else {
    58.           var rootNode:WordTrie = new WordTrie(false);
    59.           rootNode.children[childPos] = child;                        
    60.           nodes[word] = rootNode;
    61.         }
    62.     }
    63.    
    64.     // This is a lot simpler in the c# version :)
    65.     static function charToAscii(c:char) {
    66.         var i:int = -1;
    67.         switch (c) {
    68.           case "a"[0]: i = 0; break;   
    69.           case "b"[0]: i = 1; break;           
    70.           case "c"[0]: i = 2; break;
    71.           case "d"[0]: i = 3; break;               
    72.           case "e"[0]: i = 4; break;   
    73.           case "f"[0]: i = 5; break;       
    74.           case "g"[0]: i = 6; break;   
    75.           case "h"[0]: i = 7; break;               
    76.           case "i"[0]: i = 8; break;   
    77.           case "j"[0]: i = 9; break;       
    78.           case "k"[0]: i = 10;  break; 
    79.           case "l"[0]: i = 11; break;              
    80.           case "m"[0]: i = 12; break;  
    81.           case "n"[0]: i = 13; break;          
    82.           case "o"[0]: i = 14; break;  
    83.           case "p"[0]: i = 15; break;              
    84.           case "q"[0]: i = 16; break;  
    85.           case "s"[0]: i = 17; break;          
    86.           case "s"[0]: i = 18; break;  
    87.           case "y"[0]: i = 19; break;              
    88.           case "u"[0]: i = 20; break;  
    89.           case "v"[0]: i = 21; break;          
    90.           case "w"[0]: i = 22; break;  
    91.           case "x"[0]: i = 23; break;              
    92.           case "y"[0]: i = 24; break;  
    93.           case "z"[0]: i = 25; break;          
    94.          
    95.           case "A"[0]: i = 0; break;   
    96.           case "B"[0]: i = 1; break;           
    97.           case "C"[0]: i = 2; break;   
    98.           case "D"[0]: i = 3; break;               
    99.           case "E"[0]: i = 4; break;   
    100.           case "F"[0]: i = 5; break;           
    101.           case "G"[0]: i = 6; break;   
    102.           case "H"[0]: i = 7; break;               
    103.           case "I"[0]: i = 8; break;   
    104.           case "J"[0]: i = 9; break;           
    105.           case "K"[0]: i = 10; break;  
    106.           case "L"[0]: i = 11;   break;        
    107.           case "M"[0]: i = 12; break;  
    108.           case "N"[0]: i = 13; break;          
    109.           case "O"[0]: i = 14; break;  
    110.           case "P"[0]: i = 15; break;              
    111.           case "Q"[0]: i = 16; break;  
    112.           case "R"[0]: i = 17; break;          
    113.           case "S"[0]: i = 18; break;  
    114.           case "T"[0]: i = 19; break;              
    115.           case "U"[0]: i = 20; break;  
    116.           case "V"[0]: i = 21; break;          
    117.           case "W"[0]: i = 22; break;  
    118.           case "X"[0]: i = 23; break;              
    119.           case "Y"[0]: i = 24; break;  
    120.           case "Z"[0]: i = 25; break;                    
    121.         }
    122.         return i;
    123.     }
    124. }
    125.  
    I did have an attribution requirement on using this code, but I'll waive it for you.

    Also the charToAscii function can be replaced with something like an if statement in conjunction with System.Convert.ToInt32.
     
    Last edited: Mar 30, 2011
  3. BasketQase

    BasketQase

    Joined:
    Sep 12, 2005
    Posts:
    97
    Thanks for the reply, Johnny.

    I'm to still trying to remember what and how the trie works as I'm attempting to implement your code. In the meantime I've gotten the code to compile but Unity throws a NullReferenceException at the first if statement of the addWords() function. I don't use Hashtables a lot myself, so I haven't yet figured out what all is wrong with the implementation as it is. Any thoughts as I continue to hack away at it?

    ~r
     
  4. Eric5h5

    Eric5h5

    Volunteer Moderator Moderator

    Joined:
    Jul 19, 2006
    Posts:
    32,172
    It would be quite a bit faster/better to use Dictionary instead of Hashtable, for the same reasons for using List instead of ArrayList (or the JS Array class).

    --Eric
     
  5. BasketQase

    BasketQase

    Joined:
    Sep 12, 2005
    Posts:
    97
    @JohnnyA:

    Alright, after I figured out my old code (reading years old code is fun . . .) and after I sat starting blankly at my screen for a while trying to grasp why the nodes didn't need to know what letters they were, I finally had my epiphany and did a rewrite of my original trie (I never did get your code working). I came up with the following (for anyone else who comes across this thread):

    Code (csharp):
    1.  
    2.  
    3. class TrieNode {
    4.     var isWord : boolean;
    5.     var nextLetter : TrieNode[];
    6.    
    7.     function TrieNode() {
    8.         isWord = false;
    9.     }
    10. }
    11.  
    12. private var trieRoot : TrieNode;
    13.  
    14. function Start() {
    15.     trieRoot = new TrieNode();
    16.     trieRoot.nextLetter = new TrieNode[26];
    17. }
    18.  
    19. function GenerateDictionary(words : String[]) {
    20.     for (var word : String in words) {
    21.         AddWord(word);
    22.     }
    23.  
    24.     var appControl = FindObjectOfType(AppControl) as AppControl;
    25.     appControl.SendMessage("OnLoadWordsComplete");
    26. }
    27.  
    28.  
    29. function AddWord(word : String) {
    30.     var currNode = trieRoot;
    31.    
    32.     for (var c : char in word) {
    33.         i = charToAscii(c);
    34.         if ( i > -1 ) {
    35.             if ( currNode ) {
    36.                 if ( !currNode.nextLetter[i] ) {
    37.                     currNode.nextLetter[i] = new TrieNode();
    38.                     currNode = currNode.nextLetter[i];
    39.                     currNode.nextLetter = new TrieNode[26];
    40.                 }
    41.                 else {
    42.                     currNode = currNode.nextLetter[i];
    43.                 }
    44.             }
    45.         }
    46.     }
    47.    
    48.     currNode.isWord = true;
    49.  
    50. }
    51.  
    52. function IsWord(word : String) : boolean {
    53.     var currNode = trieRoot;
    54.    
    55.     for (var c : char in word) {
    56.         i = charToAscii(c);
    57.         if ( i > -1 ) {
    58.             if ( !currNode.nextLetter[i] ) {
    59.                 return false;
    60.             }
    61.             currNode = currNode.nextLetter[i];
    62.         }
    63.         else {
    64.             return false;
    65.         }
    66.     }
    67.    
    68.     return currNode.isWord;
    69. }
    70.  
    It works beautifully with 3-4 second generation time on my iPad. FAR more usable!

    Thanks for taking the time to help and for the great suggestions!
    ~Rob
     
    Last edited: Mar 22, 2011
  6. JohnnyA

    JohnnyA

    Joined:
    Apr 9, 2010
    Posts:
    4,653
    @BasketQase

    Sorry code wasn't running for you (I do have a running version on 3.x in a half finished game but thats on a different machine), however I'm glad you solved your problems :)

    @Eric

    I was mainly concerned about memory footprint and look-up speed not generation speed; it wasn't causing an issue so I never got round to optimising the generation. If I ever push the project to release I'll be sure to update and test with Dictionary.

    Cheers.
     
  7. andeeeee

    andeeeee

    Joined:
    Jul 19, 2005
    Posts:
    8,768
    @BasketQase: can you give any more information about what function the trie performs in the game? Historically, they have been an efficient way to check for the presence or absence of a word in a dictionary but they perform quite badly on modern hardware due to the pattern of memory usage. If you need autocompletion or some of the other functions of a trie then it may still be the best option but a simple lookup, say, would be easier to do with a hashtable or skip-list.
     
  8. BasketQase

    BasketQase

    Joined:
    Sep 12, 2005
    Posts:
    97
    @andeeee:

    The user inputs a word from 3-7 characters long and I just need to find out if it exists in a word list consisting of about 50k entries. I don't really remember why I chose to use a trie (I wrote the original app in 2007), but likely it was simpy the first solution that came up in google that I could understand. How would one use a hashtable or skip-list (the latter of which I've not heard of)?

    ~r
     
  9. andeeeee

    andeeeee

    Joined:
    Jul 19, 2005
    Posts:
    8,768
    You can use strings as the keys for a hashtable/dictionary. The value that is looked up by the string is not important since the lookup is simply to determine if the key exists. For example, with the string keys already added to the table, you could check for the presence of a word with something like:-
    Code (csharp):
    1. if (wordList.Contains(candidateWord)) {
    2.   // Word is in the list.
    3. }
    Hashtables are much more efficient than tries both for inserting and looking up items but tries support additional operations (eg, generating all words starting with a given prefix).

    A skip list is just a sorted array or linked list which is accompanied by a second list that acts as a kind of index on the main list. For example, in your game, the main list would contain the words in alphabetical order and the index list might contain every hundredth word in the main list along with its position. You then search the index until you find the last entry that occurs before your candidate word alphabetically. Then, you start at the position of that word in the main list and just search in a linear fashion until you find the word you want or one which is alphabetically after it (which indicates that the candidate word isn't in the dictionary). This type of structure is probably overkill for what you are doing but it can be designed so that it loads very quickly.
     
  10. BasketQase

    BasketQase

    Joined:
    Sep 12, 2005
    Posts:
    97
    @andeeee

    Thanks for the input. I wish I'd known to or thought to use a hashtable before! It was far less complex to implement and is about 4 times faster than the most recent trie implementation I was running (the trie clocked in about 3-4 seconds, a simple hashtable was under a second).


    For anyone who comes across this later, this is the code I'm using now:

    Code (csharp):
    1.  
    2.  
    3. private var wordList : Hashtable;
    4.  
    5. function Start() {
    6.     wordList = new Hashtable();
    7. }
    8.  
    9. function GenerateDictionary(words : String[]) {
    10.     for (var word : String in words) {
    11.         // I just set the value to a boolean, 'cause it's small.  
    12.                 // The boolean's not used for anything.
    13.                 wordList.Add(word, true);  
    14.     }
    15.  
    16.     appControl.SendMessage("OnLoadWordsComplete");
    17. }
    18.  
    19.  
    20. function IsWord(word : String) : boolean {
    21.     return wordList.Contains(word);
    22. }
    23.  
    24.  
    Thanks again for all the help everyone!
    ~Rob
     
  11. JohnnyA

    JohnnyA

    Joined:
    Apr 9, 2010
    Posts:
    4,653
    Bit of a dead topic, but even if you aren't doing auto-completion another reason to use a Trie is memory usage. An efficient trie (which my example certainly isn't) will use a fair bit less memory than the standard hashtable if you have a dataset with a lot of overlapping prefixes (e.g. very large word lists). If you overlap suffixes too you get a directed acylcic graph which is smaller again (although you would probably want to precaclulate this as it can be expensive to generate).

    Also fixed the bug in my sample code so it should run now :)
     
    Last edited: Mar 30, 2011