levenshtein.sh

levenshtein.sh

#!/bin/bash

function levenshtein() { a="$1"; b="$2";
  if [ "$a" == "$b" ]; then echo 0; return 0; fi
  if [ 0 -eq ${#a} ]; then echo ${#b}; return 0; fi
  if [ 0 -eq ${#b} ]; then echo ${#a}; return 0; fi

  d0=(0)
  d1=()
  for i in $(seq 1 ${#b}); do d0[$i]=$i; done

  aii=0; ai=1;
  while [ $ai -le ${#a} ]; do
    d1[0]=$ai;
    ae="${a:$ai-1:1}";

    bii=0; bi=1;
    while [ $bi -le ${#b} ]; do
      if [ "$ae" == "${b:$bii:1}" ]; then
        d1[$bi]=${d0[$bii]};
      else
        x=${d0[$bii]}; y=${d0[$bi]}; z=${d1[$bii]};
        if [ $x -lt $y ]; then
          if [ $x -lt $z ]; then
            d1[$bi]=$x;
          else
            d1[$bi]=$z;
          fi
        else
          if [ $y -lt $z ]; then
            d1[$bi]=$y;
          else
            d1[$bi]=$z;
          fi
        fi
        d1[$bi]=$((${d1[$bi]} + 1));
      fi
      bii=$bi; bi=$(($bi+1));
    done
    dd=(${d0[@]}); d0=(${d1[@]}); d1=(${dd[@]});

    aii=$ai; ai=$(($ai+1));
  done

  echo ${d0[${#b}]};
  return 0;
}