Forma óptima de encontrar un valor similar en una tabla grande

Question

Tengo una base de datos en la que estoy almacenando más de 1000000 nombres en mysql. Ahora la tarea de mi aplicación es un poco típica. No solo busco nombres en la base de datos, sino que también encuentro nombres similares. Supongamos que el nombre se ingresa como christian, luego la aplicación mostrará nombres sugeridos como christine, chris, etc. ¿Cuál es la forma óptima de hacerlo, sin utilizar la cláusula like? Las sugerencias serán solo sobre los cambios en la última parte del nombre.

Answer 1

Si quieres también nombres similares (por sonido) algo así como SOUNDEX() podría ayudar: http://dev.mysql.com/doc/refman/5.0/en/string-functions.html#function_soundex

De lo contrario … LIKE 'chri%' parece para mí no es una mala idea?

Si realmente quiere solo los primeros caracteres sin LIKE puede usar SUBSTRING().

Answer 2

Podría usar una expersión regular, creo. No estoy de acuerdo, pero hay una función llamada REGEXP que puedes poner en una cláusula WHERE. Mire here

Answer 3

Like es generalmente una buena solución, pero otra forma de mejorar el rendimiento para esto podría ser crear un índice de columna parcial y luego enviar consultas en la misma longitud que su prefijo. Consulte el MySQL documentation con respecto a col_name(length).

Answer 4

Puede usar SOUNDS LIKE, creo que debería ser bastante rápido también.

http://dev.mysql.com/doc/refman/5.0/en/string-functions.html#operator_sounds-like

Answer 5

utilizando como en el lado izquierdo se fija no requerirá un recorrido de tabla. Supongo que esta es la razón por la que no desea utilizar LIKE: SELECT * FROM table WHERE name LIKE CONCAT(?, "%") es rápido y no requerirá un escaneo de tabla para encontrar filas. El CONCAT le permite usar consultas preparadas con% de sintaxis.

También podría hacer algo como:

SELECT * from table WHERE name < 'christian' LIMIT 20

y

SELECT * FROM table WHERE name > 'christian' LIMIT 20

encontrar vecinos en la lista ordenada.

Answer 6

Puede usar la función metaphone() de php para generar el código de metafonía para cada nombre y almacenarlos junto con los nombres.

<?php 
print "chris" . "\t" . metaphone("chris") . "\n"; 
print "christian" . "\t" . metaphone("christian") . "\n"; 
print "christine" . "\t" . metaphone("christine") . "\n"; 

# prints: 
# chris  XRS 
# christine XRSTN 
# christian XRSXN 

continuación, puede utilizar un algoritmo de distancia levenshtein (ya sea en php [http://php.net/manual/en/function.levenshtein.php] o MySQL [http://www.artfulsoftware.com /infotree/queries.php#552]) para calcular la distancia entre los metacódigos. En mi prueba a continuación, una distancia de 2 o menos parecía indicar el nivel de similitud que está buscando.

<?php 
$names = array(
     array('mike',metaphone('mike')), 
     array('chris',metaphone('chris')), 
     array('chrstian',metaphone('christian')), 
     array('christine',metaphone('christine')), 
     array('michelle',metaphone('chris')), 
     array('mick',metaphone('mick')), 
     array('john',metaphone('john')), 
     array('joseph',metaphone('joseph')) 
); 

foreach ($names as $name) { 
     _compare($name); 
} 

function _compare($n) { 
     global $names; 
     $name = $n[0]; 
     $meta = $n[1]; 

     foreach ($names as $cname) { 
       printf("The distance between $name and {$cname[0]} is %d\n",       
        levenshtein($meta, $cname[1])); 
     } 
}