Calculate Levenshtein distance in MATLAB (words or characters) with Wagner–Fischer algorithm
This is a MATLAB implementation of the Wagner–Fischer algorithm.
function y = lvdistance(sentence1, sentence2, penalties, split_characters)
%LVDISTANCE Calculate Levenshtein distance between two strings
% Uses Wagner–Fischer algorithm
% See https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm
%
% Arguments:
% sentence1, sentence2: strings, e.g. 'hello world'
% penalties (optional): vector of penalties for deletion, insertion and
% substitution (default: [1 1 1])
% split_characters (optional): split at each character, not only at spaces
% (default: false)
%
% GPL v3, Nicolai Spohrer <nicolai@xeve.de>
switch nargin
case 2
penalty_deletion = 1;
penalty_insertion = 1;
penalty_substitution = 1;
split_characters = false;
case 3
penalty_deletion = penalties(1);
penalty_insertion = penalties(2);
penalty_substitution = penalties(3);
split_characters = false;
case 4
penalty_deletion = penalties(1);
penalty_insertion = penalties(2);
penalty_substitution = penalties(3);
otherwise
error 'Invalid number of arguments';
end
if split_characters
% split at each character
sentence1 = num2cell(sentence1);
sentence2 = num2cell(sentence2);
else
% split at spaces
sentence1 = strsplit(sentence1, ' ');
sentence2 = strsplit(sentence2, ' ');
end
m = length(sentence1);
n = length(sentence2);
% distance 2D array
d = zeros(m+1, n+1);
for i=1:m+1
d(i, 1) = i-1;
end
for j=1:n+1
d(1, j) = j-1;
end
for j=1:n
for i=1:m
if strcmp(sentence1{i}, sentence2{j})
% words are equal, therefore no operation required
d(i+1, j+1) = d(i, j);
else
% words are not equal
d(i+1, j+1) = min(min(...
d(i, j+1) + penalty_deletion,... % deletion
d(i+1, j) + penalty_insertion),... % insertion
d(i, j) + penalty_substitution); % substitution
end
end
end
y = d(m+1, n+1);
end
Recent Posts
- Vorabpauschale: Theoretische zu versteuernde Rendite seit 1987
- Untersuchung der Kosten der gesetzlichen Kranken- und Pflegeversicherung in Deutschland 1962 – 2026
- Spanish Juggling problem
- Changing the maximum upload file size with Nextcloud in a docker-compose setup
- Shrinking a QNAP Virtualization Station disk image
Recent Comments
- Vorabpauschale: Theoretische zu versteuernde Rendite seit 1987 - Xeve on Untersuchung der Kosten der gesetzlichen Kranken- und Pflegeversicherung in Deutschland 1962 – 2026
- Andreas on Shrinking a QNAP Virtualization Station disk image
- Arjun on Fix for Latex4CorelDraw with CorelDraw 2017
- Harald H on Automatically reboot TP-Link router WDR4300 / N750 with bash script
- Gene on Running multiple Django projects on one Apache instance with mod_wsgi
Leave a Reply