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

Unity Engine
,
1

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):

class Node {
        var word:boolean;
        var children:Node[];
        
        function Node(word:boolean) {
          this.word = word;
          children = new Node[5];
        }
        
        function Node(word:boolean, children:Node[]) {
          this.word = word;
          this.children = children;
        }
}

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):

// An in memory representation of the entire dictionary, and a function to check if a word is in that dictionary. 
// It sacrifices memory for speed. That said the Trie structure is fairly efficient in terms of memory use.
class Dictionary{
	
    // Fake dictionary ... letters: a,b,c,d,e  words: ace,aced,add,bad,bade,cab,dab   
    static var aced:Node = new Node(true);
    static var bade:Node = new Node(true);

    static var ace:Node = new Node(true, [null,null,null,aced,null]);   
    static var add:Node = new Node(true);       
    static var bad:Node = new Node(true, [null,null,null,null,bade]);         
    static var cab:Node = new Node(true);   
    static var dab:Node = new Node(true);   
      
    static var ac:Node = new Node(false, [null,null,null,null,ace ]);   
    static var ad:Node = new Node(false, [null,null,null,add ,null]);   
    static var ba:Node = new Node(false, [null,null,null,bad ,null]);   
    static var ca:Node = new Node(false, [null,cab ,null,null,null]);   
    static var da:Node = new Node(false, [null,dab ,null,null,null]);   
      
    static var a:Node = new Node(false, [null,null,ac,  ad,  null]);
    static var b:Node = new Node(false, [ba,  null,null,null,null]);
    static var c:Node = new Node(false, [ca,  null,null,null,null]);
    static var d:Node = new Node(false, [da,  null,null,null,null]);
      
    static var words:Node = new Node(false,[a,b,c,d,null]);  
    
    static function isWord(word:String):boolean {
    	return isWord(word, 0, words);	
    }   
    
    // Recursive function to traverse to the correct position of the Trie and determine if we are at a word.
    static function isWord(word:String, pos:int, trie:Node):boolean {
	var c:Node = trie.children[charToAscii(word[pos])];
        if (c != null) {
            if (word.length == pos + 1) {
              return c.word;
            } else {
                return isWord(word, pos + 1, c);
            }
        } else {
          return false;
        } 
    }

    // 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.
    static function charToAscii(c:char):int {
	switch (c) {
	    case "a"[0] : return 0;	
 	    case "b"[0] : return 1;	
	    case "c"[0] : return 2;	
	    case "d"[0] : return 3;	
	    case "e"[0] : return 4;
            // Something has gone wrong if we get here, however for simplicities sake we don't handle the error.
            default: return -1;	
	}
    }
}

A simple test class:

function Start () {
	Debug.Log("'abc' is a word: " + Dictionary.isWord("abc"));
	Debug.Log("'ace' is a word: " + Dictionary.isWord("ace"));
	Debug.Log("'ead' is a word: " + Dictionary.isWord("ead"));
	Debug.Log("'dab' is a word: " + Dictionary.isWord("dab"));
	Debug.Log("'eeee' is a word: " + Dictionary.isWord("eeee"));				
}

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

2

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

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

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 :slight_smile: