Thread: LZ77 Match Searching (HELP!)

  1. #1
    Registered User
    Join Date
    Jul 2010
    Posts
    56

    LZ77 Match Searching (HELP!)

    I've learned LZ77 in theory, know I wanna practice, my first attempt was to code a C++ function that finds the best match when comparing the sliding window with the look ahead buffer, this is what i came up with: (btw it must return a array of int, 0->contains distance to run backwards from the lookahead buffer 1->contains how long the match is, it cant be less then 2)

    Code:
    #include <iostream>
    #include <string>
    
    using namespace std;
    
    int * find_match(char * sliding_window, char * look_ahead)
    {
        int distance = 0;
        int lenght = 0;
    
        // for loop runs every character pointed in var sliding_window
        // it searches for a character match longer than 2
        for(int x = 0; *(sliding_window+x) != '\0'; x++)
        {
            if(sliding_window[x] == look_ahead[0])
                if(sliding_window[x+1] == look_ahead[1])
                    if(sliding_window[x+2] == look_ahead[2])
                    {
                        //if reached here, then it means a match longer than 2 bytes has been found
    
                        // distance = ???? dont know how to calculate distance
    
                        lenght++; //previously 2, but 2 has already been checked if it matches, and it does
                        while(sliding_window[x+lenght] == look_ahead[lenght])
                            lenght++;
    
                    }
    
            if(lenght > 0) // if it's bigger than 0, then it means it's already found a match
                break;
        }
    
        if(distance != 0 && lenght != 0)
        {
            int return_array[] = {distance,lenght};
            return return_array;
        }
        else
        {
            return 0;
        }
    }
    
    int main()
    {
        char * str1 = "Just testing my function.";
        char * str2 = "I'm just testing.";
        int lenght_distance[] = find_match(str1, str2);
        cout << "distance: " << lenght_distance[0];
        return 0;
    }
    Somebody help me at making this function work, it's awful so far. And I can't call it on main without bumping into error report.
    Last edited by dhuan; 06-21-2011 at 03:04 PM.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    No such thing as "returning an array". Best you can do is to return an int*, as you have done; but then, you must make sure your memory lasts. Any variable that you declare just as a variable will die the instant the function ends, meaning that your pointer is now pointing to nothing in particular. If for whatever reason you cannot implement the actual solution of passing the array into the function, then you need to acquire memory that will last longer than the function by using "new".

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Exact Match
    By pritin in forum C++ Programming
    Replies: 2
    Last Post: 03-26-2007, 08:50 AM
  2. Lempel-Ziv '77 (LZ77)
    By SMurf in forum C Programming
    Replies: 3
    Last Post: 04-05-2004, 05:02 PM
  3. 2 array match
    By ajastru2000 in forum C++ Programming
    Replies: 5
    Last Post: 07-18-2003, 07:58 AM
  4. soccer match~
    By black in forum A Brief History of Cprogramming.com
    Replies: 8
    Last Post: 05-17-2002, 11:20 AM
  5. How do you match 2 files?
    By sketchit in forum C Programming
    Replies: 1
    Last Post: 11-10-2001, 08:06 PM