Using Levenshtein distance to compare strings

Question

My overall challenge and why this code was written was to compare two strings. One string being a description of a item in inventory and one string being a description of a item, but possibly truncated/missing some characters. I am trying to match up the items I have posted on Craigslist and the items I think I have posted.

So I go to Craigslist and copy the table showing each active item, parse the text, and come up with the item descriptions from craigslist. When they are initially put on craigslist they could have been truncated or possibly I might have missed a few chars when pasting. So I cannot try to find an exact match for each item.

After search for some time I found the Levenshtein edit distance algorithm, which helps. It can reduce the search space by a good amount but it still gives me many false positives (low edit distance, but not the same item string) before I come to the true answer.

It also does not do well when trying to match strings that have been severely truncated (their description is 1.75x bigger than allowed text in craigslist description) because their edit distance is huge.

About the code

After the text is parsed I have a linked list of strings which are from craigslist, I then create a dummy item for each and have a list of possible items to set to active. So for each possible clItem I go through every item in the inventory until I find a match, then break. (I have multiple of the same inventory items, I only want to set one to true if one of them is posted).

For each comparison between a clItem and a Item in my inventory I call sameItemDesc() which uses the Levenshtein distance to determine if two strings are the same.

In this function is where my issues lies, if I allow Levenshtein distance to be looked at that are too large I will have to answer the JOptionPane numerous times for items that have numerous low Levenshtein distance. If it is too low I will not set enough and have to go through manually to set the rest (painstaking).

Are there any good ideas as to how to improve the code, or trim my search space so I might come to a faster solution?

 public boolean updateItems2(LinkedList<String> arg)
 {
    // Create a list of items with the CL descriptions
    LinkedList<Item> clItems = new LinkedList<Item>();
    for(String a : arg)
    {
        Item newCL = new Item();
        newCL.setDesc(a);
        clItems.add(newCL);
    }
    System.out.println("Update Items got " + clItems.size() + " items");

    // Try to set one item in the inventory to active for each clItem
    int setNum = 1;
    for(Item cl : clItems)
        for(Item cur : theApp.TheMasterList.Inventory)
            if(cur.getActv() != "YES" && sameItemDesc(cl.getDesc(), cur.getDesc()))
            {
                System.out.println("Set#:" + setNum + "\nInvItem:" + cur.getDesc() + "\nCLItem:" + cl.getDesc());
                cl.setActv("YES");
                cur.setActv("YES");
                setNum++;
                break;
            }
    // Print out the items that were not set
    int notSet = 0;
    for(Item cl : clItems)
        if(cl.getActv() != "YES")
            {System.out.println("Not Set:" + cl.getDesc());notSet++;}
    // See how many we set
    int actv = 0;
    for(Item a : theApp.TheMasterList.Inventory)
        if(a.getActv() == "YES")
            actv++;
    System.out.println("UpdateItems set:" + actv + " notset:" + notSet);

    showUserDif(clItems);
    return true;
}

public boolean sameItemDesc(String cl, String mark)
{
    // We did this to each read in CLItem so do it to each real item desc too
    mark = mark.replace(" -", "").trim();
    String msg = "Are these the same\n" + cl + "\n" + mark;
    int levD = LD(cl, mark);

    if(levD == 0)
        return true;
    else if(levD < 7)
    {
        int reply = JOptionPane.showConfirmDialog(null, msg, null, JOptionPane.YES_NO_OPTION);
        if (reply == JOptionPane.YES_OPTION) 
            return true;
        else 
            return false;
    }
    else if(levD < 15)
    {
        if(mark.contains(cl.substring(0, 6)))
        {
            int reply = JOptionPane.showConfirmDialog(null, msg, null, JOptionPane.YES_NO_OPTION);
            if (reply == JOptionPane.YES_OPTION) 
                return true;
            else 
                return false;
        }
        else
            return false;
    }
    else
        return false;
}

greybeard · Accepted Answer · 2020-01-19 12:47:39Z

The overall question could be better for stackoverflow. This is more about reviewing code, where one would expect to see the code. There is no source for the Levenshtein distance.

But well, let me separate my answer in two parts.

First, the overall question

Are there any good ideas as to how to improve the code, or trim my search space so I might come to a faster solution?

According to the given preconditions:

One string being a description of a item in inventory and one string being a description of a item, but possibly truncated/missing some characters

One string is correct, the other one has flaws in a way, that characters are missing.
If we rephrase this, we have a string correct and a string flawed with this properties:
For all characters char in flawed

char is included in correct and count(char) in flawed is smaller or equal to count(char) in correct ("contained").
index(char) in flawed is smaller or equal to index(char) in correct ("ordered").

We use this properties to base our algorithm.

Trivial version:
For every flawed string, take every char, look if it is inside any correct string, if yes, remove char from correct string and continue with next char. If we found a correct string, which includes all chars from flawed string, we have a good candidate.
An implementation could be:

public static boolean isCharArrayIncludedInString(final char[] arrayChar, final String string) {
    final char[] targetArray = string.toCharArray();
    for (final char arrayCharItem : arrayChar) {
        boolean isFound = false;
        for (int i = 0; i < targetArray.length; ++i) { //if we have large targetArrays, we could improve this by a linkedlist and removing the entries
            if (arrayCharItem == targetArray[i]) {
                targetArray[i] = 0;
                isFound = true;
                break;
            }
        }
        if (!isFound)
            return false;
    }
    return true;
}

//if we use the ordered property, too:

public static boolean isCharArrayIncludedInString(final char[] arrayChar, final String string) {
    final char[] targetArray = string.toCharArray();
    int innerIndex = 0;
    for (final char arrayCharItem : arrayChar) {
        boolean isFound = false;
        while (innerIndex < targetArray.length) {
            if (arrayCharItem == targetArray[innerIndex++]) { // here we use the "ordered" property
                isFound = true;
                break;
            }
        }
        if (!isFound)
            return false;
    }
    return true;
}
// hint: i choosed isCharArrayIncludedInString instad of isStringIncludedInString, because the second typically assumes contiguous appearance

We can improve this, if you know that at least x of the first characters must be the same. Then do a startsWith for the substring.
The algorithm has a worst time complexity of (nmlen(longest string))

The not trivial solution:

Create a modified trie data structure. If we did not found a character for a node, look for all subnodes. The complexity is hard to guess, but in the average case should be better than the trivial version.

Second part, Code quality

Some parts are already pointed out, I try to avoid them.

public boolean updateItems2(LinkedList<String> arg)

Bad name for method (what is the meaning of the 2? What is the difference between 1 and 2?), expected result from a update method with return boolean is the success state, which is not the case(?). Rename it perhaps to printAllMatchingDescriptions or something like that. getAllMatchingDescriptions if you want to return it later.

public boolean updateItems2(LinkedList<String> arg)

Bad name for argument. Clearly, this is an argument, and arg could be an abbreviation for this. listDescriptions could be a better name. And use List if there is no specific need for LinkedList:

public boolean printAllMatchingDescriptions(List<String> listDescriptions)

 // Create a list of items with the CL descriptions
LinkedList<Item> clItems = new LinkedList<Item>();

Yes, the comment describes the next line. But it has no additional value as already written by the source code. You should avoid such comments.

LinkedList<Item> clItems = new LinkedList<Item>();

Again, i would avoid abbreviations and would name it listItems.

for(String a : arg)
{
    Item newCL = new Item();
    newCL.setDesc(a);
    clItems.add(newCL);
}

It looks like the description is a good candidate for the constructor.
And again, try to avoid abbreviations.
It could be:

    for (final String listDescriptionsItem : listDescriptions)
        listItems.add(new Item(listDescriptionsItem));

System.out.println("Update Items got " + clItems.size() + " items");

A logger could be nice. But ok, for quick & dirty debugging in small programs, println could be fine.

// Try to set one item in the inventory to active for each clItem
int setNum = 1;
for(Item cl : clItems)
    for(Item cur : theApp.TheMasterList.Inventory)
        if(cur.getActv() != "YES" && sameItemDesc(cl.getDesc(), cur.getDesc()))
        {
            System.out.println("Set#:" + setNum + "\nInvItem:" + cur.getDesc() + "\nCLItem:" + cl.getDesc());
            cl.setActv("YES");
            cur.setActv("YES");
            setNum++;
            break;
        }

int setNum = 1;why does it start with 1? From the code, it looks like you are counting the number of activated items. At least, this is what is happening. From the println it looks like this should be a index. If the second is the case, you should modify the code.
Use brackets for statements with more than one line. This is confusing.
Again, abbreviations.
theApp.TheMasterList.Inventory this does not look good. But I can not make any suggestions, because code is unknown. Try to avoid static access for dynamic parts.
The string "YES"/"NO" thing was already mentioned. Names for better method names could be isActivated() and activate().
You could call the sameItemDesc with two items, rather than the description.
cur.setActv("YES"); this does not make sense. You are only inside the statement, if this is already true. It could be:

    for (final Item listItemsItem : listItems) {
        for (final Item inventoryItem : Inventory) {
            if (inventoryItem.isActivated())
                continue;
            if (!isFirstItemSameAsSecondItem(listItemsItem, inventoryItem))
                continue;
            System.out.println("Set#:" + numberOfActivatedItems + "\nInvItem:" + inventoryItem.getDescription() + "\nCLItem:"
                    + listItemsItem.getDescription());
            listItemsItem.activate();
            numberOfActivatedItems++;
            break;
        }
    }

// Print out the items that were not set
int notSet = 0;
for(Item cl : clItems)
    if(cl.getActv() != "YES")
        {System.out.println("Not Set:" + cl.getDesc());notSet++;}

You know it already, abbreviations. And unexpected brackets. And this method is perhaps not necessary. Because the number of deactivated items is size of the list (all items) minus activated:

final int numberOfDeactivatedItems = listItems.size() - numberOfActivatedItems;

// See how many we set
int actv = 0;
for(Item a : theApp.TheMasterList.Inventory)
    if(a.getActv() == "YES")
        actv++;
System.out.println("UpdateItems set:" + actv + " notset:" + notSet);

Why do you calculate this a second time?

The sameItemDesc could be changed too, but I will spare this part because I do not know if it is necessary.

Overall, we could have something like this:

public void printAllMatchingDescriptions(final List<String> listDescriptions) {
    final List<Item> listItems = new LinkedList<Item>();
    for (final String listDescriptionsItem : listDescriptions)
        listItems.add(new Item(listDescriptionsItem));
    System.out.println("Update Items got " + listItems.size() + " items");

    // Plan: Check if any of the listDescriptions is contained in any state in the overall list
    int numberOfActivatedItems = 0;
    for (final Item listItemsItem : listItems) {
        for (final Item inventoryItem : Inventory) {
            if (inventoryItem.isActivated()) // if you have a lot of activated ones, it could be better to create a new list with only deactivated entries
                continue;
            if (!isFirstItemSameAsSecondItem(listItemsItem, inventoryItem))
                continue;
            System.out.println("Set#:" + numberOfActivatedItems + "\nInvItem:" + inventoryItem.getDescription() + "\nCLItem:"
                    + listItemsItem.getDescription());
            listItemsItem.activate();
            numberOfActivatedItems++;
            break;
        }
    }

    final int numberOfDeactivatedItems = listItems.size() - numberOfActivatedItems;

    System.out.println("Items activated:" + numberOfActivatedItems + ", deactivated:" + numberOfDeactivatedItems);

    showUserDif(listItems); // I do not know what is happening here. At least abbreviations again
}

public static boolean isFirstItemSameAsSecondItem(final Item item, final Item other) {
    return isCharArrayIncludedInString(item.getDescription().toCharArray(), other.getDescription());
}

public static boolean isCharArrayIncludedInString(final char[] arrayChar, final String string) {
    final char[] targetArray = string.toCharArray();
    int innerIndex = 0;
    for (final char arrayCharItem : arrayChar) {
        boolean isFound = false;
        while (innerIndex < targetArray.length) {
            if (arrayCharItem == targetArray[innerIndex++]) { // here we use the "ordered" property
                isFound = true;
                break;
            }
        }
        if (!isFound)
            return false;
    }
    return true;
}

I apologize for the poor coding practices (naming, logical errors, bad syntax). When I initially started on this I never thought I might use it more than once. I then got caught trying to write the code as I was using it, thus the piss poor coding. --- Thank you for the extended response, This seems that it will work much better than my current implementation. I will try it later today when i get back home. Thanks tb-!!!! — KDecker, Feb 7, 2013 at 19:19
Do not use harsh words, at least you got some other thoughts, which is always fine. If you experiment with the algorithm, you should create some unit tests. I did some trivial cases for me, too. But you have some real data which makes an advantage. — tb-, Feb 7, 2013 at 19:27

Quentin Pradet · Accepted Answer · 2013-02-07 14:24:10Z

Style

Please use braces everywhere, removing them hurts readability and makes it easier to produces bugs.

   if (reply == JOptionPane.YES_OPTION) 
        return true;
    else 
        return false;

This can be written as return reply == JOptionPane.YES_OPTION.

A simple Levenshtein distance trick

Instead of using absolute distances for the Levenshtein distance, you can define a ratio. That is, if string1 is within 30% of edit distance of string2, then it can considered egal. I've used this trick in the past and accuracy increased a bit.

BumSkeeter-aware distance

You're saying that the errors come from paste errors where a few chars are missing at the end. If this is the only possible error, then you don't need the full power of the Levenshtein Distance, and might want to use a distance which only counts the number of added characters, and use Levenshtein distance * 10 otherwise.

Searching intelligently

(This is the most important point.)

The best way to get good results is to stop pairing two strings when the distance is short enough, but to always assign the best string. That is, you still do your outer loop for(Item cl : clItems), but for the second loop, store the score for every possibility, and assign only the best score. The time complexity is the same, it could possibly be a bit longer, but unless you have thousands or millions of items it's going to produce much better results.

I had been creating a list of the lowest edit distances and then choosing from that, I abandoned it last night after I got to frustrated trying to get it to work properly. I think I might try again, I guess it is the only good way to do this. — KDecker, Feb 7, 2013 at 14:34

GlenPeterson · Accepted Answer · 2013-02-07 20:02:34Z

It sounds from your problem description that the strings can only differ if one is a substring of the other. Maybe even the one will only be truncated at the end? When I look at your code I see that CraigsList may add hyphens and spaces. I think this is a much simpler problem than the more general case of lexical similarity. Would something like the following work for you?

public boolean isSimilar(String orig, String test) {
    // Remove every character that's not relevant to your comparison.
    // (assumes you are writing in ASCII English)
    // The regular expression should be read as: "replace each character that
    // is not a capital or lower-case letter or number with... nothing"
    // Since this will remove all whitespace, you don't need to trim.
    orig = orig.replaceAll("[^A-Za-z0-9]", "");
    test = test.replaceAll("[^A-Za-z0-9]", "");

    return (test.length < orig.length) &&
           orig.substring(0, test.length).equalsIgnoreCase(test);
}

I didn't compile this, so it might be Java-ish pseudo-code, but I hope that gives you an idea.

Also using == or != with Strings in Java is very dangerous. It will not work if your code is ever serialized, or used on separate machines. I would make one or more of the following changes:

// Original
if(cur.getActv() != "YES" && sameItemDesc(cl.getDesc(), cur.getDesc()))

// Better - parenthesis and indentation makes clear two separate comparisons
// Also, makes clear that the != "YES" gets evaluated before the &&
if( (cur.getActv() != "YES") &&
    sameItemDesc(cl.getDesc(), cur.getDesc()) )

// Better: compares the *contents* of the string "YES" with
// the contents of whatever string getActv() returns.  You were comparing
// the *address* of "YES" with the *address* of whatever string cur.getActv()
// returns.
if( !"YES".equals(cur.getActv()) &&
    sameItemDesc(cl.getDesc(), cur.getDesc()) )

// Better still to make getActv return a boolean!  Now you don't
// have to worry about what kind of comparison you use, or even
// typos!
if( !cur.getActv() &&
    sameItemDesc(cl.getDesc(), cur.getDesc()) )

I like to watch the world burn when I code, so I use things like != and use YES and NO instead of booleans. --- Why am I paying for college.....Why did I use YES/NO....Excuse me I'll be slapping my wrists all day for that. — KDecker, Feb 7, 2013 at 14:39

Stack Exchange Network

Using Levenshtein distance to compare strings

3 Answers 3

First, the overall question

Second part, Code quality

Style

A simple Levenshtein distance trick

BumSkeeter-aware distance

Searching intelligently

Your Answer

Not the answer you're looking for? Browse other questions tagged
java
performance
edit-distance
or ask your own question.

Hot Network Questions

Using Levenshtein distance to compare strings

3 Answers 3

First, the overall question

Second part, Code quality

Style

A simple Levenshtein distance trick

BumSkeeter-aware distance

Searching intelligently

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged javaperformanceedit-distance or ask your own question.

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
java
performance
edit-distance
or ask your own question.