Search String Algorithm in Table

Question

For a given database table:

DB

id   w1,  w2,  w3,  w4,    v
1    A                    X1
2    B                    X2
3    A    B               Y0
3    A    B    C          Y1
4    C                    X3
5    D                    X4
6    B    C    D          Y2
7    C    D    F          Y3
8    C    D    G          Y4
9    E                    X5

There exists an input with expected output based on a string search/match on the table. What we are trying to do is match the input with a combination of rows from the database. The only portion of the row that we use for matching is from w1 to w4. We then use the v column to identify the row. So, for example, the input string E would produce output X5, while input A, B would produce output Y0. In the case that there is no exact match, we want the elements closer to the front of the list to represent as long a string as possible. For example, with input A, B, C, D, E we could match a number of ways, notably Y1, X4, X5, X1, Y2, X5. We prefer the former, because A, B, C (from Y1) is longer than A (from X1). We want the first item in the output to represent as long a string as possible, and only when two potential outputs have the same length for the initial item do we try to get the longest second item we can.

Example 2:

input = A, B, C, D, F

expected_output => Y0, Y3

Explanation:

We would like to find A, B, C, D, F, but there is no match.

Likewise, we would match A, B, C, D if we could, but we cannot.

We do find Y1 is a match for A, B, C, so we use that. Our partial solution is Y1.

Now we look for D, F, but we don't find it.

We find X4 matches D, so our partial solution is Y1, X4.

Next we look for F but then there is no match. At this point we backtrack until we find a solution that does work. We take X4 off our solution and look for a better match for D, but there is no other way to match it, and we can't match a shorter substring, because that would be empty.

We take Y1 off our solution (now it is empty) and look for another way to match A, B, C. There is no other way, so we look for A, B, which we find with Y0. Our partial solution is Y0.

Now we search for the remainder of the input, C, D, F and we find it with Y3. Our solution is Y0, Y3.

Question:

What algorithms could I use or learn to be able to solve this efficiently?

What is the pseudocode or high level overview of how to solve the problem?

Answer 1

I wrote some code in Python to solve this problem. Python is designed to be very readable. There is a plaintext explanation of the algorithm below to help you understand what's going on. I am treating the database as an array indexable by its columns and rows.

def find_match(db, input_string):
    if input_string == '':
        return list()
    matches = list()
    length = 0
    for row in db:
        for col in [w1, w2, w3, w4]:
            if len(input_string) == length:
                return list(row[v]) # we found a match!
            if row[col] != input_string[length]:
                length = 0
                break
            length += 1
        if length == 0:
            continue
        if len(input_string) == length:
            return list(row[v]) # we found a match!
        matches.append((length, row[v]))
    matches.sort(reverse=True) # this puts longest matches first 
    for length, match in matches:
        solution = find_match(db, input_string[length:]) 
# input_string[length:] means the input_string from index length till the end.
        if solution != []:
            return list(match) + solution
    return list()

Explanation:

This is a recursive algorithm to match the input. What it does is it loops over all rows in the database and finds all the ones that could be part of a match. If it finds anything that is a complete match, then it returns it immediately (there's no point going any further once you've found a solution.)

Then it sorts this list of potential matches so that the longest ones are evaluated first. It loops through these sorted matches and calls the find_match function using the portion of the input string that still needs to be matched, if that match is the one to be used. In this way, you are evaluating the longest matches first, as you requested.

A step-by-step example (Example 2 from your question):

DB

id   w1,  w2,  w3,  w4,    v
1    A                    X1
2    B                    X2
3    A    B               Y0
3    A    B    C          Y1
4    C                    X3
5    D                    X4
6    B    C    D          Y2
7    C    D    F          Y3
8    C    D    G          Y4
9    E                    X5

input_string: [A, B, C, D, F]

input_string is not empty, so we construct matches as an empty list. This is the list of rows that could be part of the final solution (they must entirely match the input string from the beginning until they run out of characters)

We loop over the rows, and find the following potential matches: X1 (A); Y0 (A, B); Y1 (A, B, C)

We add them to the list as a tuple containing their length and the v that corresponds to them. This way we will be able to make sure we check the longest matches first. matches looks like this once we finish iterating over the db: [(1, X1), (2, Y0), (3, Y1)]

Next we sort the list using the length as the key so the longest matches are first: [(3, Y1), (2, Y0), (1, X1)]

Now we iterate over the matches, and try to find a solution using each one. Because we are calling the function recursively, it could be a long time between checking each match, depending on the length of the input string that still needs to be matched.

The first row we try to find a solution with is the first element in matches: Y1 (A, B, C). We call find_match(db, [D, F]) using [D, F] as the input string because that is the portion that still needs to be matched if we use Y1 (A, B, C). We can easily find the input string because we have the length (3, in this case) and so we take input_string from its 3rd index on:

A, B, C, D, F
0, 1, 2, 3, 4
X  X  X  D, F

input_string: [D, F]

we loop over the rows and find only one match: X4 (D)

Our list of matches is [(1, X4)], so we call find_match(db, [F])

input_string: [F]

we loop over the rows and find 0 matches, so matches is [] and when we iterate over it, we immediately continue on to the next block of code which tells us to return []. This is our way of saying we didn't find any match.

Now we go back to when input_string was [D, F]. We set solution equal to [], because that's what we just returned. Our only potential match was (X4, D), which we just checked, so now we are done iterating over the potential matches. Because we couldn't find any match with [D, F] as the input string we return [] as well.

Now we go back to when [A, B, C, D, F] was the input string and we had just finished trying to match Y1. We continue iterating over matches ([(3, Y1), (2, Y0), (1, X1)]). We call find_match(db, [C, D, F]) using Y0 (A, B) as the match.

input_string: [C, D, F]

We loop over the rows and we would get X3 (C); Y3 (C, D, F); Y4 (C, D, G) as our matches, but once we find that Y3 (C, D, F) exactly matches the input string, we go ahead and return [Y3]

Now we go back to when [A, B, C, D, F] was the input string and we were just using Y1 (A, B, C) as the match. At this point we see that we did find a match (the function returned [Y3]) and we add Y1 to it so that we have the full match: [Y1, Y3]. We return that and the function is done executing.

In the part of the function that compares the row with the input string, there is a little bit of bounds checking to make sure we only take as many characters from the row as it has, and we don't try to match the input string with a row that is longer than it is, but I didn't bother elaborating on that because it never came up in this example.