Results 1 to 8 of 8
  1. #1
    Join Date
    Oct 2010
    Posts
    35
    Rep Power
    0

    Default Recursive Edit Distance, 1 mistake.. help please

    Hello Everybody...

    Few questions... I am writing this program for school that has to implement both the recursive and dynamic way of editing distance between two strings. I have figured out the dynamic way (levenshtein distance) of editing distance but i am stuck with the recursive... i think it may be a simple little problem but any of your guys help is GREATLY appreciated!
    Here is my code

    Java Code:
    public class editDistance {
        public static int CALLS;
        public static boolean MEMOIZING;
       
    
    // RECURSIVE:     
        public static int distanceB(String s1, String s2, int m, int n){
        	if (n == s2.length()) return s1.length()-m;
        	if (m == s1.length()) return s2.length()-n; 	
        	if (s1 == s2) return distanceB(s1,s2,m+1,n+1);
        	if (s1 != s2) {
    
        return 1+Math.min(Math.min(distanceB(s1,s2,m,n+1), distanceB(s1,s2,m+1,n)), distanceB(s1,s2,m+1,n+1));	 
    
    // this throws an error
        	}
    }
    
     public static int distance (String s1, String s2) {
    
        	// this is without RECURSION VV
        	// dynamic programming
        	
        	int[][] matrix= new int[s1.length() + 1][s2.length() + 1];
    
        for (int i = 0; i < matrix.length; i++) {
    	    for (int j = 0; j < matrix[i].length; j++) {
    
    		matrix[i][j] = i == 0 ? j : j == 0 ? i : 0;
               
                 if (i > 0 && j > 0) {
                        if (s1.charAt(i - 1) == s2.charAt(j - 1))
    			      matrix[i][j] = matrix[i - 1][j - 1];
                      
    	             else
    		        matrix[i][j] = Math.min(matrix[i][j - 1] + 1, Math.min(
    								matrix[i - 1][j - 1] + 1,               matrix[i - 1][j] + 1));
                        //CALLS = matrix [i][j];
    				}
    				MEMOIZING= true;
    				
    				}
    			
    		}
    		
    		return matrix[s1.length()][s2.length()]; 
    
              
    	} // end distance class 
        
      public static void main(String[] args) {
    
        System.out.println( "--------------------------------------------------") ;
        editDistance.MEMOIZING = false ;
        editDistance.CALLS = 0 ;
        System.out.println( editDistance.distance("shoes","socks") ) ;
        System.out.println( editDistance.CALLS ) ;
    
        System.out.println( "--------------------------------------------------") ;
        editDistance.MEMOIZING = true ;
        editDistance.CALLS = 0 ;
        System.out.println( editDistance.distance("shoes","socks") ) ;
        System.out.println( editDistance.CALLS ) ;
    
      }
    
    }

  2. #2
    mine0926 is offline Senior Member
    Join Date
    Apr 2010
    Location
    Philippines
    Posts
    580
    Rep Power
    5

    Default

    What error it throws? Kindly post its stacktrace

  3. #3
    Join Date
    Oct 2010
    Posts
    35
    Rep Power
    0

    Default

    actually its a logic error, im running it through an IDE and it
    Java Code:
     public static int distanceB(String s1, String s2, int m, int n){
        	if (n == s2.length()) return s1.length()-m;
        	if (m == s1.length()) return s2.length()-n; 	
        	if (s1 == s2) return distanceB(s1,s2,m+1,n+1);
        	if (s1 != s2) {
        		return 1+Math.min(Math.min(distanceB(s1,s2,m,n+1), distanceB(s1,s2,m+1,n)), distanceB(s1,s2,m+1,n+1));	
        	}
    		
        }
    the
    Java Code:
    public static int distanceB(String s1, String s2, int m, int n)
    is underlined asking for a return value....

    I just don't know how to implement this using recursion, i dont even know if my return statements are okay

  4. #4
    mine0926 is offline Senior Member
    Join Date
    Apr 2010
    Location
    Philippines
    Posts
    580
    Rep Power
    5

    Default

    All of your return is inside an if statement, what distanceB method will return when it did not meet any of your if statement.
    Java Code:
     private String returnSomeString(int index)
     {  if(index == 0)
        {   return "you choose zero"
        }
        //What will be the return if index is not equals to zero(0)?
        return "you did not choose zero(0)";
     }
    Not really good in explanation, but hope you understand what I am trying to explain here. :)

  5. #5
    subith86 is offline Senior Member
    Join Date
    Jan 2011
    Location
    Bangalore, India
    Posts
    102
    Rep Power
    0

    Cool

    Hi,

    I'm not solving your query now. I want you to know the concept of recursion and implement it by yourself.

    I have attached an image - recursion_flow.jsp
    It'll give you a clear picture of what a recursive method will do.

    after step 1 and 3, the condition inside if is true, so it goes inside, but in step 6, condition is false, so it goes out of the block. This stage ends the recursion. All the steps that follow is some kind of fallback you can say.

    I have made one mistake. Instead of
    recursiveMethod(//some integer);
    it should have been
    x = recursiveMethod(//some integer);
    or
    x += recursiveMethod(//some integer);
    depending on your logic. Here x is some integer.
    Attached Thumbnails Attached Thumbnails Recursive Edit Distance, 1 mistake.. help please-recursion_flow.jpg  

  6. #6
    Join Date
    Oct 2010
    Posts
    35
    Rep Power
    0

    Default

    okay so i have fixed my recursive part... or so i thought but its throwing a OutOfMemoryError.. anybody know whats up? Heres my code
    Java Code:
    public class editDistance {
    
    	public static int CALLS;
        public static boolean MEMOIZING;
    
        int findMin(int d1,int d2, int d3){
        	if ( d1 < d2 && d1 < d3)
        		 return d1;
        	else if (d1 < d3)
        		 return d2;
        	else if (d2 < d3)
        		 return d2;
          else
        		return d3; 
        }
        
        // HERES THE RECURSIVE
        public static int distanceB(String s1, String s2){
        	 int d1, d2, d3;
        	 
        	if (s2.length()==0) return s1.length(); 
        	if (s1.length()==0) return s2.length(); 	
        	
        	if (s1.length() == s2.length()) 
    		   
    		    d1 = distanceB(s1+1, s2+1);
        	else 
        		d1 = 1 + distanceB(s1+1, s2+1);
        	d2 = 1 + distanceB(s1, s2+1);
        	d3 = 1 + distanceB(s1+1, s2);
        	
        	return findMin(d1,d2,d3);
        	
     
        	
        }
        public static int distance (String s1, String s2) {
    
        	// this is without RECURSION VV
        	// dynamic programming
        	
        	int[][] matrix= new int[s1.length() + 1][s2.length() + 1];
    
    		for (int i = 0; i < matrix.length; i++) {
    			for (int j = 0; j < matrix[i].length; j++) {
    
    				matrix[i][j] = i == 0 ? j : j == 0 ? i : 0;
    
    				if (i > 0 && j > 0) {
    
    					if (s1.charAt(i - 1) == s2.charAt(j - 1))
    						matrix[i][j] = matrix[i - 1][j - 1];
                      
    					else
    						matrix[i][j] = Math.min(matrix[i][j - 1] + 1, Math.min(
    								matrix[i - 1][j - 1] + 1, matrix[i - 1][j] + 1));
                        //CALLS = matrix [i][j];
    				}
    				MEMOIZING= true;
    				
    							}
    			
    		}
    		
    		return matrix[s1.length()][s2.length()]; 
    
              
    	} // end distance class 
        
      public static void main(String[] args) {
    
        System.out.println( "--------------------------------------------------") ;
        editDistance.MEMOIZING = false ;
        editDistance.CALLS = 0 ;
        System.out.println( editDistance.distanceB("shoes","socks") ) ;
        System.out.println( editDistance.CALLS ) ;
    
        System.out.println( "--------------------------------------------------") ;
        editDistance.MEMOIZING = true ;
        editDistance.CALLS = 0 ;
        System.out.println( editDistance.distance("shoes","socks") ) ;
        System.out.println( editDistance.CALLS ) ;
    
      }
     
    }
    
    /// End-of-File
    here is my StackTrace
    Java Code:
    --------------------------------------------------
    Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    	at java.util.Arrays.copyOfRange(Arrays.java:3209)
    	at java.lang.String.<init>(String.java:215)
    	at java.lang.StringBuilder.toString(StringBuilder.java:430)
    	at editDistance.distanceB(editDistance.java:28)
    	at editDistance.distanceB(editDistance.java:28)
    	at editDistance.distanceB(editDistance.java:28)
    	at editDistance.distanceB(editDistance.java:28)
    	at editDistance.distanceB(editDistance.java:28)
    	at editDistance.distanceB(editDistance.java:28)
    	at editDistance.distanceB(editDistance.java:28)
    	at editDistance.distanceB(editDistance.java:28)
    	at editDistance.distanceB(editDistance.java:28)
    	at editDistance.distanceB(editDistance.java:28)
    	at editDistance.distanceB(editDistance.java:28)
    	at editDistance.distanceB(editDistance.java:28)
    	at editDistance.distanceB(editDistance.java:28)
    	at editDistance.distanceB(editDistance.java:28)
    	at editDistance.distanceB(editDistance.java:28)
    	at editDistance.distanceB(editDistance.java:28)
    	at editDistance.distanceB(editDistance.java:28)
    	at editDistance.distanceB(editDistance.java:28)
    	at editDistance.distanceB(editDistance.java:28)
    	at editDistance.distanceB(editDistance.java:28)
    	at editDistance.distanceB(editDistance.java:28)
    	at editDistance.distanceB(editDistance.java:28)
    	at editDistance.distanceB(editDistance.java:28)
    	at editDistance.distanceB(editDistance.java:28)
    	at editDistance.distanceB(editDistance.java:28)
    	at editDistance.distanceB(editDistance.java:28)
    	at editDistance.distanceB(editDistance.java:28)
    	at editDistance.distanceB(editDistance.java:28)
    	at editDistance.distanceB(editDistance.java:28)

  7. #7
    mine0926 is offline Senior Member
    Join Date
    Apr 2010
    Location
    Philippines
    Posts
    580
    Rep Power
    5

    Default

    I remember someone's signiture in this forum, he said: "Ever seen a dog chase its tail, now it is an infinite loop"

    This is what happening on your distanceB method. Inside your distanceB method you call distanceB method, it keeps calling distanceB method until it runs out of memory.

    Also, in this statement
    Java Code:
        public static int distanceB(String s1, String s2)
        {
        	int d1, d2, d3;
    
        	if (s2.length()==0) return s1.length();
        	if (s1.length()==0) return s2.length();
        	[b]
            [i]//!it will never reach else statement[/i]
        	if (s1.length() == s2.length()) 
                d1 = distanceB(s1+1, s2+1);
        	else
                d1 = 1 + distanceB(s1+1, s2+1);
                d2 = 1 + distanceB(s1, s2+1);
                d3 = 1 + distanceB(s1+1, s2);
    
        	return findMin(d1,d2,d3);[/b]
        }

  8. #8
    m00nchile is offline Senior Member
    Join Date
    Feb 2010
    Location
    Ljubljana, Slovenia
    Posts
    470
    Rep Power
    5

    Default

    Nice to see my sig gets used as an analogy :)
    Ever seen a dog chase its tail? Now that's an infinite loop.

Similar Threads

  1. What Method and loops to get the distance
    By sirdonclemo in forum New To Java
    Replies: 2
    Last Post: 09-05-2010, 04:21 AM
  2. i can't see the mistake
    By PVL268 in forum New To Java
    Replies: 3
    Last Post: 04-29-2009, 06:26 AM
  3. i can't see the mistake
    By PVL268 in forum New To Java
    Replies: 2
    Last Post: 04-28-2009, 07:30 AM
  4. Calculate X and Y given starting angle and distance
    By nidhirastogi in forum Java 2D
    Replies: 5
    Last Post: 08-18-2008, 11:24 PM
  5. PLEASE!!!help me to find mistake
    By sasha20 in forum New To Java
    Replies: 1
    Last Post: 01-11-2008, 11:50 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •