Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 1 of 1

Thread: Implementation of search function for Patricia Trie

  1. #1
    Junior Member
    Join Date
    Jul 2008
    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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.
    Last edited by Deep_4; November 7th, 2012 at 12:51 PM.


Similar Threads

  1. Frustrating File>save as search function in google script
    By segreto in forum Other Programming Languages
    Replies: 2
    Last Post: August 16th, 2012, 12:40 PM
  2. ArrayList implementation
    By meijuh in forum Collections and Generics
    Replies: 8
    Last Post: March 22nd, 2012, 01:03 PM
  3. Graph Search Theory with extend of BFS, UFS and A* Search in grid
    By keat84 in forum Java Theory & Questions
    Replies: 1
    Last Post: February 7th, 2012, 09:46 AM
  4. Help wih implementation...
    By Frank_nor in forum What's Wrong With My Code?
    Replies: 4
    Last Post: November 24th, 2009, 05:43 PM
  5. Binary Search Tree implementation
    By Ceasar in forum Java Theory & Questions
    Replies: 3
    Last Post: October 9th, 2009, 12:23 AM