Hoy me he levantado bastante técnico y con ganas de escribir un artículo en profundidad sobre el algoritmo de la Distancia de Levenshtein. Lo había estudiado en su momento en la carrera y su aplicación en SEO me parece muy acertada. Tras ver una referencia en la página de @jbmoreno, voy a tratar de profundizar un poco más en lo que es y cómo se utilizaría para “hilar fino” en nuestro trabajo SEO.

En Ciencias de la Computación se llama Distancia de Levenshtein al mínimo número de operaciones que son necesarias para transformar una cadena de caracteres en otra. Muchas veces es conocida también como “distancia de edición” o “distancia entre palabras”. Se obtiene a partir de la generalización de otros dos algoritmos:

  • Distancia de Hamming, que viene a ser el número de caracteres diferentes entre dos cadenas de igual longitud
  • Distancia de Damerau-Levenshtein, que consiste en el número mínimo de operaciones requeridas para transformar una cadena de caracteres en otra. A diferencia de la Distancia de Levenshtein, cuenta la transposición de caracteres como una operación y no dos:
    • Damerau-Levenshtein (calle – calpe) = 1
    • Levenshtein (calle – calpe) = 2

seo distancia de levenshtein

Las operaciones posibles en la Distancia de Levenshtein son:

  1. Inserción: googe -> google (insertar ‘l’ entre la ‘g’ y la ‘e’)
  2. Eliminación: bingo -> bing (eliminar ‘o’)
  3. Sustitución: osk -> ask (sustituir la ‘o’ por ‘a’)

Por ejemplo, la distancia entre Cromes y Chrome es de 2, dado que se necesitan 2 operaciones elementales para cambiar de uno a otro:

  1. Cromes – Crome (eliminar ‘s’)
  2. Crome – Chrome (insertar ‘h’)

En nuestro caso, este algoritmo vamos a ponerlo en marcha para cumplir una función seo. Y esto, ¿cuándo ocurre?

  • Cuando al utilizar una url el servidor nos podría devolver un error 404 (“not found”, no se ha encontrado el recurso). Para evitarlo, utilizamos el algoritmo de Levenshtein para encontrar posibles URLs que puedan estar a escasa “distancia”, realizando un redireccionamiento 301 evitando la catástrofe.

Pero… ¿cuándo puede devolver el servidor ese error?

  • En gran cantidad de ocasiones un dirección web puede estar corrompida en ciertos caracteres debido a la codificación empleada.
  • Es posible que al introducir a mano una dirección web, por ejemplo, nos equivoquemos o nos olvidemos de algún carácter sin darnos cuenta.

Implementar este algoritmo requiere el uso de una matriz de tamaño (n + 1) × (m + 1), siendo n y m las longitudes de las cadenas que se comparan. Sin embargo, en PHP tenemos una función nativa para este cálculo:

$distancia = levenshtein($url1, $url2);

¿Cómo debemos implementar la Distancia de Levenshtein en nuestra web?

  1. Tras crearnos nuestra página de error 404 (404.php por ejemplo) y añadirla a nuestro fichero .htaccess, capturamos la URL utilizando las variables de servidor ($_SERVER[‘REQUEST_URI’])
  2. Almacenamos ese valor y lo comparamos, por ejemplo, con todas las URL que tenemos almacenadas en el sitemap.xml de nuestro sitio, usando el algoritmo de la Distancia de Levenshtein
  3. Realizamos una redirección 301 desde la URL almacenada que genera el error 404 hacia la URL de la página que el algoritmo nos indique que tiene el valor mínimo (también podemos acotar este valor a un máximo para minimizar posibles errores como que redireccione a páginas sin ninguna relación con la capturada)

Para añadir a tu .htaccess la página 404, se haría con algo parecido a esto:

ErrorDocument 404 /nuestro404.php

Este podría ser un ejemplo en código, aproximado a la idea de este artículo (extraído de pastebin.com), espero que os sea útil:

function findBest($url) {
    if(stristr($url,"http")) {
        $p = parse_url($url);
        $url = $p['path'];
    }

// recorremos el sitemap.xml URL por URL
    $s = "sitemap.xml";
    for($i=0;$i<10;$i++) {
        if(file_exists($s)) { } else { $s = "../$s"; }
    }

    $data = file_get_contents($s);
    $locs = getMultiMatch("<loc>","</loc>",$data);
    foreach($locs as $loc) {
        if(stristr($loc,"http:")) { $p = parse_url($loc); $loc = $p['path']; }
// Calculamos la distancia de levenshtein comparando
        $l = levenshtein($url,$loc);
        $results[$loc]=$l;
    }
    asort($results);
    foreach($results as $k=>$v) {
        $correct = $k;
        $score = $v;
        break;
    }
// Si obtenemos resultados <3 lo damos por correcto
    if($score<3) {
        return $correct;
    } else {
        return false;
    }
}

function getSingleMatch($start,$end,$content) {
    $exp = explode($start,$content);
    $exp2 = explode($end,$exp[1]);
    return $exp2[0];
}

function getMultiMatch($start,$end,$content) {
   $exp = explode($start,$content);
   for($i=1;$i< count ( $exp );$i++) {
       $exp2 = explode($end,$exp[$i]);
       $arr[] = $exp2[0];
   }
   return $arr;
}

// Extraemos la URL mediante variables internas
$correct = findBest($_SERVER['REQUEST_URI']);

// Si la distancia de levenshtein es <3 realizamos un 301
// redireccionando
if($correct!=false) {
    header("HTTP/1.1 301 Moved Permanently");
    header("Location: $correct");
    exit;
}
[googleplusauthor]

Artículos relacionados...

Sobre El Autor

Coordinador en AnalyticaWeb.com Me encanta el SEO y la Analítica Web. Emprendedor y autodidacta que con pasión intenta alcanzar los máximos de su proyección. Disfruto convirtiendo datos en negocio.

Artículos Relacionados

2 Respuestas

Hacer Comentario

Su dirección de correo electrónico no será publicada.