Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

Simple code to check if a word is in a dictionary... and a question

Discussion in 'iOS and tvOS' started by JohnnyA, Oct 28, 2010.

  1. JohnnyA

    JohnnyA

    Joined:
    Apr 9, 2010
    Posts:
    5,041
    Bored on the train last night I wrote a fairly naive little trie search for determining if a given word (string) is in a dictionary, thought it might be useful to some.

    A node in the Trie (Node.js):
    Code (csharp):
    1.  
    2. class Node {
    3.         var word:boolean;
    4.         var children:Node[];
    5.        
    6.         function Node(word:boolean) {
    7.           this.word = word;
    8.           children = new Node[5];
    9.         }
    10.        
    11.         function Node(word:boolean, children:Node[]) {
    12.           this.word = word;
    13.           this.children = children;
    14.         }
    15. }
    16.  
    The main class (Dictionary.js), the search itself is only 8 lines (and I could get rid of one of them by removing the superfluous else):
    Code (csharp):
    1.  
    2. // An in memory representation of the entire dictionary, and a function to check if a word is in that dictionary.
    3. // It sacrifices memory for speed. That said the Trie structure is fairly efficient in terms of memory use.
    4. class Dictionary{
    5.    
    6.     // Fake dictionary ... letters: a,b,c,d,e  words: ace,aced,add,bad,bade,cab,dab  
    7.     static var aced:Node = new Node(true);
    8.     static var bade:Node = new Node(true);
    9.  
    10.     static var ace:Node = new Node(true, [null,null,null,aced,null]);  
    11.     static var add:Node = new Node(true);      
    12.     static var bad:Node = new Node(true, [null,null,null,null,bade]);        
    13.     static var cab:Node = new Node(true);  
    14.     static var dab:Node = new Node(true);  
    15.      
    16.     static var ac:Node = new Node(false, [null,null,null,null,ace ]);  
    17.     static var ad:Node = new Node(false, [null,null,null,add ,null]);  
    18.     static var ba:Node = new Node(false, [null,null,null,bad ,null]);  
    19.     static var ca:Node = new Node(false, [null,cab ,null,null,null]);  
    20.     static var da:Node = new Node(false, [null,dab ,null,null,null]);  
    21.      
    22.     static var a:Node = new Node(false, [null,null,ac,  ad,  null]);
    23.     static var b:Node = new Node(false, [ba,  null,null,null,null]);
    24.     static var c:Node = new Node(false, [ca,  null,null,null,null]);
    25.     static var d:Node = new Node(false, [da,  null,null,null,null]);
    26.      
    27.     static var words:Node = new Node(false,[a,b,c,d,null]);  
    28.    
    29.     static function isWord(word:String):boolean {
    30.         return isWord(word, 0, words); 
    31.     }  
    32.    
    33.     // Recursive function to traverse to the correct position of the Trie and determine if we are at a word.
    34.     static function isWord(word:String, pos:int, trie:Node):boolean {
    35.     var c:Node = trie.children[charToAscii(word[pos])];
    36.         if (c != null) {
    37.             if (word.length == pos + 1) {
    38.               return c.word;
    39.             } else {
    40.                 return isWord(word, pos + 1, c);
    41.             }
    42.         } else {
    43.           return false;
    44.         }
    45.     }
    46.  
    47.     // Char is not an int in javascript, how annoying. I'm sure there is a better way to do this, but this will do for now.
    48.     static function charToAscii(c:char):int {
    49.     switch (c) {
    50.         case "a"[0] : return 0;
    51.         case "b"[0] : return 1;
    52.         case "c"[0] : return 2;
    53.         case "d"[0] : return 3;
    54.         case "e"[0] : return 4;
    55.             // Something has gone wrong if we get here, however for simplicities sake we don't handle the error.
    56.             default: return -1;
    57.     }
    58.     }
    59. }
    60.  
    A simple test class:
    Code (csharp):
    1.  
    2. function Start () {
    3.     Debug.Log("'abc' is a word: " + Dictionary.isWord("abc"));
    4.     Debug.Log("'ace' is a word: " + Dictionary.isWord("ace"));
    5.     Debug.Log("'ead' is a word: " + Dictionary.isWord("ead"));
    6.     Debug.Log("'dab' is a word: " + Dictionary.isWord("dab"));
    7.     Debug.Log("'eeee' is a word: " + Dictionary.isWord("eeee"));               
    8. }
    9.  
    Note that I made a few by hand untested modifications while posting this, may not compile as is.

    I'll generate an example from a full dictionary and also test memory usage and speed when I get a chance.

    My question is simply is there an inbuilt function to replace my : static function charToAscii(c:char):int
     
    Last edited: Oct 30, 2010
  2. JohnnyA

    JohnnyA

    Joined:
    Apr 9, 2010
    Posts:
    5,041
    PS Feel free to use and/or modify this in any way. Be great if you let me know if you use it, but certainly not a requirement.
     
  3. andeeeee

    andeeeee

    Joined:
    Jul 19, 2005
    Posts:
    8,768
    The existence of different character encodings nowadays makes this task a bit more complicated than it was in the past. You will find what you are looking for in the System.Text classes, specifically in System.Text.ASCIIEncoding.
     
  4. JohnnyA

    JohnnyA

    Joined:
    Apr 9, 2010
    Posts:
    5,041
    Useful advice but here it's simply about turning the (standard uppercase ASCII) letters A-Z in to integers 0-25 (-97 in c). To be honest an inbuilt function is probably no faster than switch statement, but saving 28 lines of code might be convenient for people.

    PS thanks for the link to the class :)
     
    Last edited: Oct 28, 2010