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;
}