by topherPedersen

Simple String Similarity Algorithm in JavaScript or, How to Tell if Two Strings are Similar, even if they aren’t exactly the same

This blog post is brought to you by the developer of BitBudget. BitBudget is an automated budgeting app for Android and iOS which syncs with your bank account and helps you avoid overspending. If you’d like to quit living paycheck-to-paycheck and get a better handle on your finances, download it today! https://bitbudget.io

At the moment I happen to be working on a personal finance app called BitBudget, where I need to be able to figure out if two purchases were made with the same merchant, or different merchants. For example, does a financial transaction labeled “VZWRLSS*PRPAY AUTOPAY 02/19 PURCHASE” represent a transaction with the same company as “VZWRLSS*PRPAY AUTOPAY 03/19 PURCHASE”? What about “CALM 03/26 PURCHASE” and “CALM 02/26 PURCHASE INTERNET”? Many transactions are easy to compare, “McDonald’s” vs “Amazon”, or “Chipotle Mexican Grill” vs “Starbucks”, but once banks and payment processors start throwing in all this extra information things get tricky.

While I personally am not really a computer science / algorithms kind of guy, sometimes you really need an algorithm to get the job done! So if you find yourself in the same boat I have your answer right here. After a quick google search on this topic I discovered that there appear to be three different types of string comparison algorithms:

  1. Edit Distance Based
  2. Token Based
  3. Sequence Based

If you’d like to read more about the three types of algorithm’s I suggest reading: String similarity — the basic know your algorithms guide!

For my use-case, I decided that an Edit Distance Based algorithm would be the quickest strategy to implement myself, so that’s what I’m going with and would like to present below. The actual code that I will end up using in my app may feature a few modifications for speed, such as shortening the number of iterations before returning a result, but what I have so far should be a good start if you need something quick and easy:

var string = [];
string[0] = 'CALM 03/26 PURCHASE';
string[1] = 'CANVA* 02644-3020257 03/28 PURCHASE HTTPSCANVA.CO DE';
string[2] = 'VZWRLSS*PRPAY AUTOPAY 03/19 PURCHASE';
string[3] = 'WWW.NORDVPN.COM HTTPSWWW.NORD';
var findMe = 'CALM 02/26 PURCHASE INTERNET';
function calculateSimilarity(aString, bString) {
var matchingCharacters = 0;
var totalCharacters;
if (aString.length >= bString.length) {
totalCharacters = aString.length;
} else {
totalCharacters = bString.length
}
var shortestStringLength;
if (aString.length < bString.length) {
shortestStringLength = aString.length;
} else if (bString.length < aString.length) {
shortestStringLength = bString.length;
} else {
shortestStringLength = aString.length;
}
for (var i = 0; i < shortestStringLength; i++) {
if (aString[i] === bString[i]) {
matchingCharacters++;
}
}
var percentSimilar = matchingCharacters / totalCharacters;
return percentSimilar;
}
console.log(calculateSimilarity(findMe, string[0]).toString());
console.log(calculateSimilarity(findMe, string[1]).toString());
console.log(calculateSimilarity(findMe, string[2]).toString());
console.log(calculateSimilarity(findMe, string[3]).toString());
view raw edit_distance_based_string_similarity.js hosted with ❤ by GitHub
 

topherPedersen