1254885Sdumbbell// SPDX-License-Identifier: GPL-2.0 2254885Sdumbbell#include "levenshtein.h" 3254885Sdumbbell#include <errno.h> 4254885Sdumbbell#include <stdlib.h> 5254885Sdumbbell#include <string.h> 6254885Sdumbbell 7254885Sdumbbell/* 8254885Sdumbbell * This function implements the Damerau-Levenshtein algorithm to 9254885Sdumbbell * calculate a distance between strings. 10254885Sdumbbell * 11254885Sdumbbell * Basically, it says how many letters need to be swapped, substituted, 12254885Sdumbbell * deleted from, or added to string1, at least, to get string2. 13254885Sdumbbell * 14254885Sdumbbell * The idea is to build a distance matrix for the substrings of both 15254885Sdumbbell * strings. To avoid a large space complexity, only the last three rows 16254885Sdumbbell * are kept in memory (if swaps had the same or higher cost as one deletion 17254885Sdumbbell * plus one insertion, only two rows would be needed). 18254885Sdumbbell * 19254885Sdumbbell * At any stage, "i + 1" denotes the length of the current substring of 20254885Sdumbbell * string1 that the distance is calculated for. 21254885Sdumbbell * 22254885Sdumbbell * row2 holds the current row, row1 the previous row (i.e. for the substring 23254885Sdumbbell * of string1 of length "i"), and row0 the row before that. 24254885Sdumbbell * 25254885Sdumbbell * In other words, at the start of the big loop, row2[j + 1] contains the 26254885Sdumbbell * Damerau-Levenshtein distance between the substring of string1 of length 27254885Sdumbbell * "i" and the substring of string2 of length "j + 1". 28254885Sdumbbell * 29254885Sdumbbell * All the big loop does is determine the partial minimum-cost paths. 30254885Sdumbbell * 31254885Sdumbbell * It does so by calculating the costs of the path ending in characters 32254885Sdumbbell * i (in string1) and j (in string2), respectively, given that the last 33254885Sdumbbell * operation is a substitution, a swap, a deletion, or an insertion. 34254885Sdumbbell * 35254885Sdumbbell * This implementation allows the costs to be weighted: 36254885Sdumbbell * 37254885Sdumbbell * - w (as in "sWap") 38254885Sdumbbell * - s (as in "Substitution") 39254885Sdumbbell * - a (for insertion, AKA "Add") 40254885Sdumbbell * - d (as in "Deletion") 41254885Sdumbbell * 42254885Sdumbbell * Note that this algorithm calculates a distance _iff_ d == a. 43254885Sdumbbell */ 44254885Sdumbbellint levenshtein(const char *string1, const char *string2, 45254885Sdumbbell int w, int s, int a, int d) 46254885Sdumbbell{ 47254885Sdumbbell int len1 = strlen(string1), len2 = strlen(string2); 48254885Sdumbbell int *row0 = malloc(sizeof(int) * (len2 + 1)); 49254885Sdumbbell int *row1 = malloc(sizeof(int) * (len2 + 1)); 50254885Sdumbbell int *row2 = malloc(sizeof(int) * (len2 + 1)); 51254885Sdumbbell int i, j; 52254885Sdumbbell 53254885Sdumbbell for (j = 0; j <= len2; j++) 54254885Sdumbbell row1[j] = j * a; 55254885Sdumbbell for (i = 0; i < len1; i++) { 56254885Sdumbbell int *dummy; 57254885Sdumbbell 58254885Sdumbbell row2[0] = (i + 1) * d; 59254885Sdumbbell for (j = 0; j < len2; j++) { 60254885Sdumbbell /* substitution */ 61254885Sdumbbell row2[j + 1] = row1[j] + s * (string1[i] != string2[j]); 62254885Sdumbbell /* swap */ 63254885Sdumbbell if (i > 0 && j > 0 && string1[i - 1] == string2[j] && 64254885Sdumbbell string1[i] == string2[j - 1] && 65254885Sdumbbell row2[j + 1] > row0[j - 1] + w) 66254885Sdumbbell row2[j + 1] = row0[j - 1] + w; 67254885Sdumbbell /* deletion */ 68254885Sdumbbell if (row2[j + 1] > row1[j + 1] + d) 69254885Sdumbbell row2[j + 1] = row1[j + 1] + d; 70254885Sdumbbell /* insertion */ 71254885Sdumbbell if (row2[j + 1] > row2[j] + a) 72254885Sdumbbell row2[j + 1] = row2[j] + a; 73254885Sdumbbell } 74254885Sdumbbell 75254885Sdumbbell dummy = row0; 76254885Sdumbbell row0 = row1; 77254885Sdumbbell row1 = row2; 78254885Sdumbbell row2 = dummy; 79254885Sdumbbell } 80254885Sdumbbell 81254885Sdumbbell i = row1[len2]; 82254885Sdumbbell free(row0); 83254885Sdumbbell free(row1); 84254885Sdumbbell free(row2); 85254885Sdumbbell 86254885Sdumbbell return i; 87254885Sdumbbell} 88254885Sdumbbell