Comparar 5000 cadenas con PHP Levenshtein

Question

Tengo 5000, a veces más, cadenas de direcciones en una matriz. Me gustaría compararlos todos con levenshtein para encontrar coincidencias similares. ¿Cómo puedo hacer esto sin recorrer todos los 5000 y compararlos directamente con cada 4999?

Edit: También estoy interesado en métodos alternativos si alguien tiene sugerencias. El objetivo general es encontrar entradas similares (y eliminar duplicados) en función de direcciones de calles enviadas por el usuario.

Answer 1

creo que una mejor forma de agrupar direcciones similares sería:

1. crear una base de datos con dos tablas - uno para la dirección (y un ID), una para los soundexes de palabras o números literales en la dirección (con la clave externa de la tabla de direcciones)

2. mayúscula la dirección, reemplazar elementos que [AZ] o [0-9] nada con un espacio

3. dividir la dirección por el espacio, calcular el soundex de cada 'palabra', dejar nada con sólo dígitos que es y lo almacenan en la tabla soundexes con la clave externa de la dirección que se inició con

4. para cada dirección (con $ ID de destino) encontrar las direcciones más similares:

   SELECT similar.id, similar.address, count(*) 
   FROM adress similar, word cmp, word src 
   WHERE src.address_id=$target 
   AND src.soundex=cmp.soundex 
   AND cmp.address_id=similar.id 
   ORDER BY count(*) 
   LIMIT $some_value; 
   

5. calcule la diferencia levenstein entre su dirección de origen y los primeros valores que devuelve la consulta.

(haciendo cualquier tipo de operación en grandes series es a menudo más rápido en las bases de datos)

Answer 2

Creo que no se puede evitar el bucle a través de la matriz ya que la función levenstein() solo toma cadenas y no una matriz como entrada.

Usted puede hacer algo como:

for($i=0;$i<count($array)-1;$i++) 
{ 
    for($j=$i+1;$j<count($array);$j++) 
    { 
     $lev = levenshtein($array[$i],$array[$j]); 
     if($lev == 0) 
     { 
      // exact match 
     } 
     else if($lev <= THRESHOLD) 
     { 
      // similar 
     } 
    } 
} 

Answer 3

Debido a la naturaleza del algoritmo de Levenshtein (en concreto el hecho de que se trata de una comparación entre dos cuerdas), no puedo ver cómo esto es posible.

Por supuesto, podría reducir el número de comparaciones al realizar algunos requisitos básicos de coincidencia primero, pero esto está fuera del alcance de lo que está preguntando.

Como una opción (muy posiblemente irrelevante), siempre se puede usar algo como soundex que le permitirá precalcular los valores de cadena. (También se puede utilizar directamente en MySQL creo.)

Answer 4

Usted podría agruparlos en base a soundexes entonces limitar las comparaciones a los casos más cercanos N ...

$mashed=array(); 
foreach ($address as $key=>$val) { 
     $mashed[$key]=soundex($val); 
} 
sort($mashed); 

iterar a través de las teclas de $ hecho puré.

C.

Answer 5

Dado que un problema, no veo otro camino que comparar todas las direcciones con cada otra dirección si desea utilizar Lehvenstein distance.

En primer lugar, se debe normalizar addressess, deshacerse de abreviaturas etc.

• Ave -> Avenida
• Rd. -> Ruta

Usted podría tener cierta distancia máx Lehvenstein fijo (N ) para las direcciones similares.

Si es así, podría abortar el algoritmo de Lehvenstein cuando esté seguro de que la distancia de edición para el par de direcciones actual es mayor que N. Para esto, necesita escribir una versión personalizada del algoritmo de Lehvenstein. Esto hará que el algoritmo sea un poco más rápido.

También hay algunas optimizaciones triviales relacionadas. Por ejemplo: si la dirección A tiene 10 caracteres de largo y la dirección B tiene 20 caracteres de largo y considera que las direcciones que tienen una distancia Lehvenstein de menos de 8 son similares. Puede buscar longitudes de direcciones e inmediatamente decidir que no son similares.

Answer 6

Si desea encontrar todos valores similares, tendrá que comparar todos los artículos a todos los demás. Pero elegir las funciones de matriz correctas acelerará las cosas de manera significativa.Aquí está un ejemplo rápido (la matriz de resultados podría haber sido mejor):

$results = array(); 
$count = count($entries); 
while ($count != 0) { 
    # The entry to process 
    $entry = array_shift($entries); 
    # Get levenshtein distances to all others 
    $result = array_map(
     'levenshtein', 
     # array_map() needs two arrays, this one is an array consisting of 
     # multiple entries of the value that we are processing 
     array_fill($entry, 0, $count), 
     $toCompare 
    ); 
    $results[] = array($entry => $result); 
    $count--; 
} 

Answer 7

Puede utilizar un bk-tree para acelerar la búsqueda/comparación.

http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees dice:

Ahora podemos hacer una observación particularmente útil sobre el Levenshtein Distancia: Se forma un espacio métrico.
[...]
Supongamos por un momento que tenemos dos parámetros, consulta, la cadena que estamos utilizando en nuestra búsqueda, y n la distancia máxima que una cadena puede ser de la consulta y aún se puede devolver. Digamos que tomamos una cadena arbitraria, la probamos y la comparamos con la consulta. Llame a la distancia resultante d. Como sabemos que la desigualdad del triángulo se mantiene, todos nuestros resultados deben tener como máximo una distancia d + ny al menos una distancia d-n desde la prueba.
[...]
Las pruebas muestran que la búsqueda con una distancia de 1 consulta no supera el 5-8% del árbol, y la búsqueda con dos errores consulta no más del 17-25% del árbol, una mejora sustancial sobre revisando cada nodo!

editar: Pero eso no lo ayuda con su problema ("12 Bird Road, Apt 6" y "12 Bird Rd. # 6"). Solo con tu fuerza bruta m * n comparación.

Answer 8

Usted dice ...

El objetivo general es encontrar entradas similares (y eliminar duplicados) basado en direcciones de calles enviadas por el usuario.

digo ... utilizar las técnicas en http://semaphorecorp.com/mpdd/mpdd.html

Answer 9

$stringA = "this is php programming language"; 
$stringB = "this is complete programming script in which java php and all other minor languages include"; 

echo "string 1---->".$stringA."<br />"; 
echo "string 2---->".$stringB."<br />"; 
// changing string to arrays 
$array1 = explode(' ', $stringA); 
$array2 = explode(' ', $stringB); 

// getting same element from two strings 
$c = array_intersect($array1, $array2); 
// changing array to the string 
$d=implode(' ',$c); 

echo "string same elements---> ".$d."<br />"; 


// getting difrent element from two arrays 
$result = array_diff($array2, $array1); 
// changing array to the string 
$zem = implode(' ',$result); 

if (!empty($zem)) { 
    echo "string diffrence---> ".$zem."<br />"; 
} else { 
    echo "string diffrence--->both strings are same <br />"; 
} 

similar_text($stringA, $d, $p); 
echo " similarity between the string is ".$p."% <br />";