Thread: Implementation of search function for Patricia Trie

Hello every1...

I am trying to implement a search function for the Patricia Trie I developed earlier.
It is actually a hamming distance search wherein the search function will search the nodes recursively until a first match is found which is within the hamming distance D.

For e.g.
For the dictionary of the words:

abscissa
abscises
activity
actressy
bodement
bodiless
chinning
chinones
delusory
deplorer
dewberry
eelgrass
eeriness

I have the tree as follows:

|root|
 |-a
  |--bscis
   |---sa
   |---es
  |--ct
   |---ivity
   |---ressy
 |-bod
  |--ement
  |--iless
 |-chin
  |--ning
  |--ones
 |-de
  |--lusory
  |--plorer
  |--wberry
 |-ee
  |--lgrass
  |--riness

and if I should search for the query string

'deplores'

with a hamming distance of 1,
my search function should output the string

'deplored'

since it is within the hamming distance of 1.

Here's the code I've written so far:

// Create and initialize some Global variables like:
// Weight W, for every difference in the character we compare, increment this variable and compare with distance D
int weight = 0;
 
// Current Position in the q array
int qPos = 0;
 
String rsl; // buffer string to store the node keys as we search a branch
 
void search(String query, int distance) {
 
        // Convert the query string to a char array e.g. qArr
    	char[] qArr = query.toCharArray();
    	final int d = distance; // the Hamming Distance input by the user
    	search(root,qArr,d,qPos);
}
 
/**
* Search a query in the Trie within a Query distance using recursion.
*/
private void search(TrieNode<T> node, char[] q, int distance, int qcurrPos) {
 
    	// For each children of the node do the following
    	// this will start with root's children when first time called
    	for (TrieNode<T> n : node.getChildren()) {
 
		// Get the child's key value and convert it to a temporary char array e.g. char[] temp
    		char[] temp = n.getKey().toCharArray();
 
    		// store the key value in the buffer string 'rsl'
    		String tmp = temp.toString();
    		rsl = rsl + tmp;
 
    		// Do Until the length of temp
    		for (int i = 0; i < temp.length; i++) {
 
			// Compare the contents of temp with the next position of the q array
    			if (temp[i] != q[qcurrPos]) {
 
    				// If the characters differ then add 1 to W
    				weight++;
    				qcurrPos++;
    			} 							
    		} 
 
    		// If W is less than distance D and the node is non-leaf then recurse thru the non-leaf's children
    		if (weight < distance && (!n.isReal()) && qcurrPos < q.length){
 
    			// search the node's children
    			search(n, q, distance, qcurrPos);
    		}
    		// else if W < D and the node is a leaf node, we've found our search string
    		else if (weight < distance && n.isReal()) {
 
    			//print out the buffer string
    			System.out.println("Closest match found in:");
    			System.out.println(rsl);
    		} 
 
    		else System.out.println("No Match Found for the query string!");
    	} // end of 1st for loop
	} // end of function search

My search should end while I am at a leaf node and the Weight W is less than or equal to D
Or Until I have searched all the nodes of the Trie.

If you could point out my flaws or add to my search logic, It would be greatly appreciated.

Thanks.