Airtable, Python and Fuzzy Matching

Jonathan - this solution is really incredible and is exactly what we need! Might you be available to chat about how I get the Airtable–Python link set up? I’m a complete beginning when it comes to this and am assuming it’s super complicated, but perhaps it’s easier to set up, given the script you’ve provided, than I thought?

Hi @Meghan_Moore - yes, it looks more complicated than it really is :slightly_smiling_face:

Will DM you.

JB

Hey JB did you ever figure out to do this entirely in within Scripting Blocks (or better yet in Automation scripting)?

Hi @Matteo_Cossu2 - No, didn’t find a solution for this. Really this needs a library/package to achieve (as with Python), but you can’t import packages on Airtable scripts, so that won’t work. Maybe there’s a non-package solution out there, but I haven’t come across one yet.

@Matteo_Cossu2 - this is a bit embarrasing…I’d actually written a script for this, but had totally forgotten about it. I cribbed some “distance algorithm” code from the web somewhere and incorporated it into an Airtable script:

// Levenshtein distance function
let levenshteinDistance = function(a, b){
    if(!a || !b) return (a || b).length;
    var m = [];
    for(var i = 0; i <= b.length; i++){
        m[i] = [i];
        if(i === 0) continue;
        for(var j = 0; j <= a.length; j++){
            m[0][j] = j;
            if(j === 0) continue;
            m[i][j] = b.charAt(i - 1) == a.charAt(j - 1) ? m[i - 1][j - 1] : Math.min(
                m[i-1][j-1] + 1,
                m[i][j-1] + 1,
                m[i-1][j] + 1
            );
        }
    }
    return m[b.length][a.length];
};

// max string length function (gets the max length of two strings)
let maxStringLength = function(a, b){
    return Math.max(a.length, b.length);
};

//get the ratio that the user wants to use on this iteration, e.g. 0.8
let inputRatio = await input.textAsync("Enter the match ratio for this search (number between 0 and 1)")

// set the tables
let matchTable = base.getTable("Match");
let originalTable = base.getTable("Original");

// get the records from the master and match tables
let matchQuery = await matchTable.selectRecordsAsync({
        fields: ['Name']
});
let originalQuery = await originalTable.selectRecordsAsync({
        fields: ['Name']
});

// iterate through the match records
for (let matchRecord of matchQuery.records) {
    // create an empty array to hold the matched IDs from master
    let matchedIds = []
    // iterate through the master records
    for (let masterRecord of originalQuery.records) {
        // do some regex so that only leters and numbers are considered - also lower case the two strings
        let formattedMatchRecord = matchRecord.name.toLowerCase().replace(/[^a-z0-9]/gi,'');
        let formattedOriginalRecord = masterRecord.name.toLowerCase().replace(/[^a-z0-9]/gi,'');
        
        // calculate the Levenshtein distance
        let ld = levenshteinDistance(formattedMatchRecord, formattedOriginalRecord);
        // calculate the max length of each pair of strings (match and master)
        let maxLength = maxStringLength(formattedMatchRecord, formattedMatchRecord);

        // log the inputs and outputs for debugging
        console.log(formattedMatchRecord, formattedOriginalRecord, ld, maxLength, 1-ld/maxLength);

        // if the calculated ratio is greater than the input threshold
        if(1-ld/maxLength > Number(inputRatio)) {
            // add the master id to the array
            matchedIds.push(
                {id: masterRecord.id}
            )
        }
    }
    // update the match record with the array of master ids
    let update = await matchTable.updateRecordAsync(matchRecord, {
            "Suggested Link to Original": matchedIds
        }
    );
}

The way this works is that you have 2 tables, both with a name column and the script links to suggested records based on the “closeness” of the original name to the match name.

You enter a number between 0 and 1 at the start (try 0.7 or 0.8) - the higher the number the more strict the threshold for suggesting matches. More info here:

The script implements the Levenshtein distance algorithm to check for similarity in two strings. This allows you to suggest links between two sets of data based on the similarity of fields within the base. This might be useful, for example, where you have a “original” customer list and want to try to match or link that to a second source of customer data.

More information on the Levenshtein distance can be found here: Levenshtein distance - Wikipedia

@JonathanBowen this is amazing. I’ll implement it and let you know how it works!

// Levenshtein distance function
let levenshteinDistance = function(a, b){
    if(!a || !b) return (a || b).length;
    var m = [];
    for(var i = 0; i <= b.length; i++){
        m[i] = [i];
        if(i === 0) continue;
        for(var j = 0; j <= a.length; j++){
            m[0][j] = j;
            if(j === 0) continue;
            m[i][j] = b.charAt(i - 1) == a.charAt(j - 1) ? m[i - 1][j - 1] : Math.min(
                m[i-1][j-1] + 1,
                m[i][j-1] + 1,
                m[i-1][j] + 1
            );
        }
    }
    return m[b.length][a.length];
};

// max string length function (gets the max length of two strings)
let maxStringLength = function(a, b){
    return Math.max(a.length, b.length);
};

//get the ratio that the user wants to use on this iteration, e.g. 0.8
let inputRatio = await input.textAsync("Enter the match ratio for this search (number between 0 and 1)")

// set the tables
let matchTable = base.getTable("Match");
let originalTable = base.getTable("Original");

// get the records from the master and match tables
let matchQuery = await matchTable.selectRecordsAsync({
        fields: ['Name']
});
let originalQuery = await originalTable.selectRecordsAsync({
        fields: ['Name']
});

// iterate through the match records
for (let matchRecord of matchQuery.records) {
    // create an empty array to hold the matched IDs from master
    let matchedIds = []
    // iterate through the master records
    for (let masterRecord of originalQuery.records) {
        // do some regex so that only leters and numbers are considered - also lower case the two strings
        let formattedMatchRecord = matchRecord.name.toLowerCase().replace(/[^a-z0-9]/gi,'');
        let formattedOriginalRecord = masterRecord.name.toLowerCase().replace(/[^a-z0-9]/gi,'');
        
        // calculate the Levenshtein distance
        let ld = levenshteinDistance(formattedMatchRecord, formattedOriginalRecord);
        // calculate the max length of each pair of strings (match and master)
        let maxLength = maxStringLength(formattedMatchRecord, formattedMatchRecord);

        // log the inputs and outputs for debugging
        console.log(formattedMatchRecord, formattedOriginalRecord, ld, maxLength, 1-ld/maxLength);

        // if the calculated ratio is greater than the input threshold
        if(1-ld/maxLength > Number(inputRatio)) {
            // add the master id to the array
            matchedIds.push(
                {id: masterRecord.id}
            )
        }
    }
    // update the match record with the array of master ids
    let update = await matchTable.updateRecordAsync(matchRecord, {
            "Suggested Link to Original": matchedIds
        }
    );
}

Wow, this is incredibly timely! I’ve been working on a project for the last couple months, and at some point I was going to need to reconcile two lists with 3,000+ entries each. Luckily for me, I had put off this part of it and just started on today, 2 days after your solution was posted! After some small changes to match my own base, the script is working great. This is going to save me so much time, thank you!

One note, there’s an unintentional issue with your code that will cause it to break if you’re not matching on the Primary field. The .name attribute of a record refers to the value in the Primary field, not the value stored in the field called “Name”. I guess it just so happens that your primary field is also called “Name”, so it works as expected in your case.

To fix this, the following two lines need to be changed:

let formattedMatchRecord = matchRecord.name.toLowerCase().replace(/[^a-z0-9]/gi,'');
let formattedOriginalRecord = masterRecord.name.toLowerCase().replace(/[^a-z0-9]/gi,'');

They should instead look like this:

let formattedMatchRecord = matchRecord.getCellValueAsString('Field Name Here').toLowerCase().replace(/[^a-z0-9]/gi,'');
let formattedOriginalRecord = masterRecord.getCellValueAsString('Field Name Here').toLowerCase().replace(/[^a-z0-9]/gi,'');

let formattedMatchRecord = matchRecord.name.toLowerCase().replace(/[^a-z0-9]/gi,'');
let formattedOriginalRecord = masterRecord.name.toLowerCase().replace(/[^a-z0-9]/gi,'');

let formattedMatchRecord = matchRecord.getCellValueAsString('Field Name Here').toLowerCase().replace(/[^a-z0-9]/gi,'');
let formattedOriginalRecord = masterRecord.getCellValueAsString('Field Name Here').toLowerCase().replace(/[^a-z0-9]/gi,'');

@Tim_Mackey - yes, you have to set the field names to match your base set up. Of course, they also don’t need to be primary fields - you can match any two fields.

let formattedMatchRecord = matchRecord.name.toLowerCase().replace(/[^a-z0-9]/gi,'');
let formattedOriginalRecord = masterRecord.name.toLowerCase().replace(/[^a-z0-9]/gi,'');

let formattedMatchRecord = matchRecord.getCellValueAsString('Field Name Here').toLowerCase().replace(/[^a-z0-9]/gi,'');
let formattedOriginalRecord = masterRecord.getCellValueAsString('Field Name Here').toLowerCase().replace(/[^a-z0-9]/gi,'');

Hey Tim, how’s @JonathanBowen’s algorithm working for you in terms of performance? I have to iterate through 12-13k records and it breaks my AT usage every time. Any suggestions much appreciated!

Are you using it in an automation or in a script extension? It’s a pretty time consuming function to run, so I’d recommend running it in a script extension otherwise I would expect it to time out on a large table.

If you’re running it in an extension and the script is locking up, the issue may be caused by the amount of logging that the script does. I recall running into that issue as I was also dealing with a huge number of records. I made some changes to the script to make the debugging logs optional, and also optimized the update function to update fields in batches of 50, rather than 1 field at a time.

Here’s my updated script based on @JonathanBowen’s example. All the field names and settings are moved to variables at the top of the script:

// Script settings >>
const matchTableName = 'Match Table'; // table name to add matches to
const originalTableName = 'Original Table'; // table name to look for matches

const matchFieldName = 'Name'; // field name to match against in matching table
const originalFieldName = 'Name'; // field name to match against in original table

const suggestedMatchFieldName = 'Suggested Link to Game'; // field name to store suggested matches

const logLevel = 0; // 0 = no logging; 1 = log number of matches for each record; 2 = same as 1 plus log individual match values for every match-field/original-field combination
// << End script settings

// Levenshtein distance function
let levenshteinDistance = function(a, b){
  if(!a || !b) return (a || b).length;
  var m = [];
  for(var i = 0; i <= b.length; i++){
      m[i] = [i];
      if(i === 0) continue;
      for(var j = 0; j <= a.length; j++){
          m[0][j] = j;
          if(j === 0) continue;
          m[i][j] = b.charAt(i - 1) == a.charAt(j - 1) ? m[i - 1][j - 1] : Math.min(
              m[i-1][j-1] + 1,
              m[i][j-1] + 1,
              m[i-1][j] + 1
          );
      }
  }
  return m[b.length][a.length];
};

// max string length function (gets the max length of two strings)
let maxStringLength = function(a, b){
  return Math.max(a.length, b.length);
};

//get the ratio that the user wants to use on this iteration, e.g. 0.8
let inputRatio = await input.textAsync('Enter the match ratio for this search (number between 0 and 1)')

console.log(`Searching for matches...`);

// set the tables
let matchTable = base.getTable(matchTableName);
let originalTable = base.getTable(originalTableName);
let updates = [];

// get the records from the master and match tables
let matchQuery = await matchTable.selectRecordsAsync({
      fields: [matchFieldName]
});
let originalQuery = await originalTable.selectRecordsAsync({
      fields: [originalFieldName]
});

// iterate through the match records
for (let matchRecord of matchQuery.records) {
  // create an empty array to hold the matched IDs from master
  let matchedIds = []
  // iterate through the master records
  for (let masterRecord of originalQuery.records) {
      // do some regex so that only letters and numbers are considered - also lower case the two strings
      let formattedMatchRecord = matchRecord.getCellValueAsString(matchFieldName).toLowerCase().replace(/[^a-z0-9]/gi,'');
      let formattedOriginalRecord = masterRecord.getCellValueAsString(originalFieldName).toLowerCase().replace(/[^a-z0-9]/gi,'');
      
      // calculate the Levenshtein distance
      let ld = levenshteinDistance(formattedMatchRecord, formattedOriginalRecord);
      // calculate the max length of each pair of strings (match and master)
      let maxLength = maxStringLength(formattedMatchRecord, formattedMatchRecord);

      // log the inputs and outputs for debugging
      if (logLevel >= 2) {
        console.log(formattedMatchRecord, formattedOriginalRecord, ld, maxLength, 1-ld/maxLength);
      }

      // if the calculated ratio is greater than the input threshold
      if(1-ld/maxLength > Number(inputRatio)) {
          // add the master id to the array
          matchedIds.push(
              {id: masterRecord.id}
          )
      }
  }

  // log how many matches there are
  if (logLevel >= 1) {
    console.log(matchRecord.name, matchedIds.length);
  }

  // If there are any matches, add them to the list of updates to be made
  if (matchedIds.length > 0) {
    let update = {
      id: matchRecord.id,
      fields: {
        [suggestedMatchFieldName]: matchedIds
      }
    };
    updates.push(update);
  }
}

// Batch update table with all matched fields
// Only up to 50 updates are allowed at one time, so we need to do a loop
while (updates.length > 0) {
  await matchTable.updateRecordsAsync(updates.slice(0, 50));
  updates = updates.slice(50);
}

console.log(`Process complete.`);

Let us know how it goes!

// Script settings >>
const matchTableName = 'Match Table'; // table name to add matches to
const originalTableName = 'Original Table'; // table name to look for matches

const matchFieldName = 'Name'; // field name to match against in matching table
const originalFieldName = 'Name'; // field name to match against in original table

const suggestedMatchFieldName = 'Suggested Link to Game'; // field name to store suggested matches

const logLevel = 0; // 0 = no logging; 1 = log number of matches for each record; 2 = same as 1 plus log individual match values for every match-field/original-field combination
// << End script settings

// Levenshtein distance function
let levenshteinDistance = function(a, b){
  if(!a || !b) return (a || b).length;
  var m = [];
  for(var i = 0; i <= b.length; i++){
      m[i] = [i];
      if(i === 0) continue;
      for(var j = 0; j <= a.length; j++){
          m[0][j] = j;
          if(j === 0) continue;
          m[i][j] = b.charAt(i - 1) == a.charAt(j - 1) ? m[i - 1][j - 1] : Math.min(
              m[i-1][j-1] + 1,
              m[i][j-1] + 1,
              m[i-1][j] + 1
          );
      }
  }
  return m[b.length][a.length];
};

// max string length function (gets the max length of two strings)
let maxStringLength = function(a, b){
  return Math.max(a.length, b.length);
};

//get the ratio that the user wants to use on this iteration, e.g. 0.8
let inputRatio = await input.textAsync('Enter the match ratio for this search (number between 0 and 1)')

console.log(`Searching for matches...`);

// set the tables
let matchTable = base.getTable(matchTableName);
let originalTable = base.getTable(originalTableName);
let updates = [];

// get the records from the master and match tables
let matchQuery = await matchTable.selectRecordsAsync({
      fields: [matchFieldName]
});
let originalQuery = await originalTable.selectRecordsAsync({
      fields: [originalFieldName]
});

// iterate through the match records
for (let matchRecord of matchQuery.records) {
  // create an empty array to hold the matched IDs from master
  let matchedIds = []
  // iterate through the master records
  for (let masterRecord of originalQuery.records) {
      // do some regex so that only letters and numbers are considered - also lower case the two strings
      let formattedMatchRecord = matchRecord.getCellValueAsString(matchFieldName).toLowerCase().replace(/[^a-z0-9]/gi,'');
      let formattedOriginalRecord = masterRecord.getCellValueAsString(originalFieldName).toLowerCase().replace(/[^a-z0-9]/gi,'');
      
      // calculate the Levenshtein distance
      let ld = levenshteinDistance(formattedMatchRecord, formattedOriginalRecord);
      // calculate the max length of each pair of strings (match and master)
      let maxLength = maxStringLength(formattedMatchRecord, formattedMatchRecord);

      // log the inputs and outputs for debugging
      if (logLevel >= 2) {
        console.log(formattedMatchRecord, formattedOriginalRecord, ld, maxLength, 1-ld/maxLength);
      }

      // if the calculated ratio is greater than the input threshold
      if(1-ld/maxLength > Number(inputRatio)) {
          // add the master id to the array
          matchedIds.push(
              {id: masterRecord.id}
          )
      }
  }

  // log how many matches there are
  if (logLevel >= 1) {
    console.log(matchRecord.name, matchedIds.length);
  }

  // If there are any matches, add them to the list of updates to be made
  if (matchedIds.length > 0) {
    let update = {
      id: matchRecord.id,
      fields: {
        [suggestedMatchFieldName]: matchedIds
      }
    };
    updates.push(update);
  }
}

// Batch update table with all matched fields
// Only up to 50 updates are allowed at one time, so we need to do a loop
while (updates.length > 0) {
  await matchTable.updateRecordsAsync(updates.slice(0, 50));
  updates = updates.slice(50);
}

console.log(`Process complete.`);

@Tim_Mackey or @JonathanBowen, might you be able to suggest how this script could be adapted to link similar records within a single table?

The Dedupe extension does an admirable job of finding the records I would like to link together, but can't link them, and the "Mark Duplicates" script example found here seems designed to do the marking, but lacks any sort of fuzzy matching.

I have a database of several thousand test questions imported from multiple tests, some of which I know have been reused.  My goal is to link those near-duplicate records together within the "Questions" table to track how questions are being reused.  Unfortunately, I'm counting on OCR for the question text, which hasn't produced exact duplicate text fields to match.

I'm doing my best to come up with workarounds, but my scripting chops are quite limited.

I appear to have the script running on a set of duplicated tables.  Given the speed at which the script runs, this is probably for the best since I was able to reduce my 15000+ question records to 2 sets of just 1500ish which I'm sure contain the duplicates and don't overlap. I'll copy and paste the link fields back into the original records when it's done.

@JonathanBowen 's version of the script at first locked up pretty quickly, but I commented out the console logging based on @Tim_Mackey comment and now it's chugging away beautifully.

I might try running the script on a truncated part of the match text (full length is often a paragraph or more) and a higher accuracy threshold in the hopes that a shorter string to check produces faster run times without too many false matches. Update: Yes, much faster.

Thanks so much for writing this.

Thank you for this! Couple of things for anyone else using this in the future. 

@Tim_Mackey 's version included this as well, but I didn't catch it in time. The original script has an update at the end of each loop regardless of if the update array was null which was incredibly slow. This part of the script is essential if you have a lot of records!

I also wanted to use this script to compare a values in a single column to each other, rather than to a separate column. I made some modifications to speed up that process by creating an array and 2 counters, then comparing my match value to only what was below it in the column. Here's what I ended up using for that: 

Another update in case folks are looking for alternative fuzzy matching. While the script above did work, the data I had didn't work very well with the Levenshtein Distance Function. I ended up importing the fuse.js library via cdn, which worked very well. in this case, I didn't need the location of the match, just that there was a match, so if you need the record id of the match, you'll want to create that second for loop and push the id's to an array as above.