How to efficiently find similar strings in a unique string in JavaScript?

Question

Background: I have a list that contains 13,000 records of human names, some of them are duplicates and I want to find out the similar ones to do the manual duplication process.

For an array like:

["jeff","Jeff","mandy","king","queen"] 

What would be an efficient way to get:

[["jeff","Jeff"]]

Explanation ["jeff","Jeff"] since their Levenshtein distance is 1(which can be variable like 3).

/* 
Working but a slow solution
*/
function extractSimilarNames(uniqueNames) {
  let similarNamesGroup = [];

  for (let i = 0; i < uniqueNames.length; i++) {
    //compare with the rest of the array
    const currentName = uniqueNames[i];

    let suspiciousNames = [];

    for (let j = i + 1; j < uniqueNames.length; j++) {
      const matchingName = uniqueNames[j];
      if (isInLevenshteinRange(currentName, matchingName, 1)) {
        suspiciousNames.push(matchingName);
        removeElementFromArray(uniqueNames, matchingName);
        removeElementFromArray(uniqueNames, currentName);
        i--;
        j--;
      }
    }
    if (suspiciousNames.length > 0) {
      suspiciousNames.push(currentName);
    }
  }
  return similarNamesGroup;
}

I want to find the similarity via Levenshtein distance, not only the lower/uppercase similarity

I already find one of the fastest Levenshtein implementation but it still takes me to 35 mins to get the result of 13000 items list.

Answer 1

Your problem is not the speed of the Levenshtein distance implementation. Your problem is that you have to compare each word with each other word. This means you make 13000² comparisons (and each time calculate the Levenshtein distance).

So my approach would be to try to reduce the number of comparisons.

Here are some ideas:

• words are only similar if their lengths differ less than 20% (just my estimation)
  → we can group by length and only compare words with other words of length ±20%

• words are only similar if they share a lot of letters
  → we can create a list of e.g. 3-grams (all lower case) that refer to the words they are part of.
  → only compare (e.g. with Levenshtein distance) a word with other words that have several 3-grams in common with it.

Answer 2

Approaches to remove similar names:

1. Use phonetical representation of the words. cmudict It works with python nltk. You can find which names are close to each other phonetically.
2. Try different forms of stemming or simplifications. I would try most aggressive stemmers like Porter stemmer.

3. Levenshtein trie. You can create trie data structure that will help to find word with minimum distance to searched item, this is used for full text search in some search engines. As far as I know it's already implemented in Java. In your case you need to search one item then add it to the structure on every step, you need to make sure that item that you search is not in the structure yet.

4. Manual naive approach. Find all suitable representations of every word/name, put all representations to map and find representations that have more than 1 word. If you have around 15 different representations of one word you will need only 280K iterations to generate this object (much faster than compare each word to another, which requires around 80M comparisons with 13K names).

-- Edit --

If there is a choice I would use something like Python or Java instead of JS for this. It's only my opinion based on: I don't know all requirements, it's common to use Java/Python for natural language processing, task looks more like heavy data processing than front end.

Answer 3

As in your working code you use Levenshtein distance 1 only, I will assume no other distances need to be found.

I will propose a similar solution as Jonas Wilms posted, with these differences:

• No need to call a isLevenshtein function
• Produces only unique pairs
• Each pair is lexically ordered

// Sample data with lots of similar names
const names = ["Adela","Adelaida","Adelaide","Adele","Adelia","AdeLina","Adeline",
               "Adell","AdellA","Adelle","Ardelia","Ardell","Ardella","Ardelle",
               "Ardis","Madeline","Odelia","ODELL","Odessa","Odette"];

const map = {};
const pairs = new Set;
for (const name of names) {
    for (const i in name+"_") { // Additional iteration to NOT delete a character
        const key = (name.slice(0, i) + name.slice(+i + 1, name.length)).toLowerCase();
        // Group words together where the removal from the same index leads to the same key
        if (!map[key]) map[key] = Array.from({length: key.length+1}, () => new Set);
        // If NO character was removed, put the word in EACH group
        for (const set of (+i < name.length ? [map[key][i]] : map[key])) {
            if (set.has(name)) continue;
            for (let similar of set) pairs.add(JSON.stringify([similar, name].sort()));
            set.add(name);
        }
    }
}
const result = [...pairs].sort().map(JSON.parse); // sort is optional
console.log(result);

I tested this on a set of 13000 names, including at least 4000 different names, and it produced 8000 pairs in about 0.3 seconds.