Esto es lo que estoy tratando de hacer: quiero medir la distancia de Levensthein entre dos cuerdas, usando bash. Encontré una implementación del LD aquí.

Ahora, supongamos que tengo algunos datos de juguetes como este:

1    The brown fox jumped    The green fox jumped
0    The red fox jumped    The green fox jumped
1    The gray fox jumped    The green fox jumped

Y digamos que esto se almacena en data.test.

Luego lo puse a través de un simple comando awk que filtra las filas que comienzan con 1 así:

awk -F '\t' '{if ($1>0) print $2,t,$3}' data.test

El primer resultado de este comando simple será:

The brown fox jumped    The green fox jumped

Ahora quiero medir la distancia de Levenshtein entre estas dos oraciones, canalizando la salida directamente a esta función (levantada del enlace anterior):

function levenshtein {
    if (( $# != 2 )); then
        echo "Usage: $0 word1 word2" >&2
    elif (( ${#1} < ${#2} )); then
        levenshtein "$2" "$1"
    else
        local str1len=${#1}
        local str2len=${#2}
        local d

        for i in $( seq 0 $(( (str1len+1)*(str2len+1) )) ); do
            d[i]=0
        done

        for i in $( seq 0 $str1len );   do
            d[i+0*str1len]=$i
        done

        for j in $( seq 0 $str2len );   do
            d[0+j*(str1len+1)]=$j
        done

        for j in $( seq 1 $str2len ); do
            for i in $( seq 1 $str1len ); do
                [ "${1:i-1:1}" = "${2:j-1:1}" ] && local cost=0 || local cost=1
                del=$(( d[(i-1)+str1len*j]+1 ))
                ins=$(( d[i+str1len*(j-1)]+1 ))
                alt=$(( d[(i-1)+str1len*(j-1)]+cost ))
                d[i+str1len*j]=$( echo -e "$del\n$ins\n$alt" | sort -n | head -1 )
            done
        done
        echo ${d[str1len+str1len*(str2len)]}
    fi
}

Sé que puedes hacer esto, pero me estoy quedando estancado porque hay dos argumentos que necesitan pasar y el hecho de que estoy pasando secuencias.

He intentado usar varias versiones de esta sugerencia, que aboga por el acaparamiento la entrada como tal:

function levenshtein {
    # Grab input.
    declare input1=${1:-$(</dev/stdin)};
    declare input2=${2:-$(</dev/stdin)};
.
.
.
}

Esta es la parte que no puedo llegar a trabajar.

3
Astrid 9 may. 2019 a las 18:22

3 respuestas

La mejor respuesta

No necesitas awk en absoluto:

while IFS=$'\t' read num first second; do
    [[ $num -gt 0 ]] || continue
    levenshtein "$first" "$second"
done < data.txt

(Cierto, awk es más rápido al procesar un archivo grande que bash, pero si está implementando el algoritmo Levenshtein en bash en primer lugar, la velocidad probablemente no sea una preocupación).


Por otro lado, una implementación más simple (aunque mínimamente probada) que no requiere tanta aritmética de índice mediante el uso de una matriz asociativa con "tuplas" como claves.

levenshtein () {
  if (( ${#1} < ${#2} )); then
    levenshtein "$2" "$1"
    return
  fi

  local str1len str2len cost m a b i j
  local -A d

  str1len=${#1}
  str2len=${#2}
  for ((i=0;i<=strlen1;i++)); do
    d[$i,0]=0
  done

  for ((j=0;j<=strlen2;j++)); do
    d[0,$j]=0
  done

  for ((j=1; j<=str2len; j++)); do
    for ((i=1; i<=str1len; i++)); do
      a=${1:i-1:1}
      b=${2:j-1:1}
      [ "$a" = "$b" ] && cost=0 || cost=1
      del=$(( $d[$((i-1)),$j] + 1 ))
      ins=$(( $d[$i,$((j-1))] + 1 ))
      alt=$(( $d[$((i-1)),$((j-1))] + cost ))

      # Compute the min without forking
      m=$del; ((ins < m)) && m=$ins; ((alt < m)) && m=$alt

      d[$i,$j]=$m
    done
  done
  echo ${d[$str1len,$str2len]}
} 
7
codeforester 9 may. 2019 a las 18:56

Si exporta la función Levenshtein en bash antes de llamar a awk con export -f levenshtein, puede llamar fácilmente a la función en awk línea por línea: awk -F '\t' '$1>0 {system("levenshtein \""$2"\" \""$3"\"")}'.

1
xash 9 may. 2019 a las 16:03

Mi voto positivo va a la respuesta de Chepner, pero si por alguna razón te encuentras atrapado en un lugar donde realmente necesitas resolver esto, tampoco es demasiado difícil.

# Awk script refactored slightly for aesthetics
pair=$(awk -F '\t' '$1>0 {print $2 "\t" $3}' data.test)
levenshtein "${pair%$'\t*'}" "${pair#$'*\t'}"

Para desempacar ligeramente esto;

  • Los dos argumentos para levenshtein están entre comillas dobles.
  • Cada argumento consiste en una sustitución de parámetros;
    • ${variable%pattern} produce el valor de variable con cualquier sufijo que coincida con pattern eliminado
    • ${variable#pattern} produce el valor de variable con cualquier prefijo que coincida con pattern eliminado
    • Ambos coinciden con el más corto posible pattern. Si tiene una cadena con varios campos, es posible que necesite las variantes ## o %% que recortan el pattern más largo aplicable desde el frente o el reverso del valor, respectivamente.
  • $'\t' es una cadena de estilo C que contiene una pestaña
  • pattern también contiene un * delante o detrás de la pestaña para eliminar todo antes o después de la pestaña, según sea necesario para obtener solo el primer o el segundo valor de la cadena separada por pestañas.
1
tripleee 9 may. 2019 a las 17:14