Implementation of Levenshtein distance

levenshtein.red

Red [
	Date: 6-Jan-2019
	File: %levenshtein.red
]
lev: function [s t][
    unless string? s [s: mold s]
    unless string? t [t: mold t]
    case [
        s = t [return 0]
        empty? s [return (length? t)]
        empty? t [return (length? s)]
    ]
    v0: append/dup make block! 1 + length? t none 1 + length? t
    v1: copy v0
    repeat i length? v0 [v0/:i: i - 1]
    repeat i length? s [
        v1/1: i
        repeat j length? t [
            cost: pick [0 1] s/:i = t/:j
            v1/(j + 1): min min v1/:j + 1 v0/(j + 1) + 1 v0/:j + cost
        ]
        repeat j length? v0 [v0/:j: v1/:j]
    ]
    v1/(1 + length? t)
]