levenshtein alternative

Question

tengo un gran conjunto de consultas y uso levenshtein para calcular errores tipográficos, ahora levenshtein hace que mysql tome el tiempo completo de la CPU. Mi consulta es una búsqueda de texto completo + levenshtein en una declaración UNION. sql1 es mi consulta actual, sql2 es solo búsqueda de texto completo que es rápida y no utiliza demasiado tiempo de CPU, ¡el último es el leventhein que alcanzará su pico!

¿Alguno de ustedes tiene una forma alternativa de obtener errores tipográficos también? No respondo datos de normalización, lo he pensado, pero no es aplicable a mis datos, ya que no puedo predefinir las coincidencias/cálculos y crear una tabla separada con índices.

  $sql1 = "(SELECT * FROM ci_sanctions_properties WHERE prop_type='LASTNAME' AND prop_value!='' AND MATCH(prop_value) AGAINST ('+usama bin laden' IN BOOLEAN MODE)) UNION (SELECT s.* FROM (SELECT levenshtein(prop_value, 'usama bin laden') AS dist, sanction_id, prop_type, prop_value FROM ci_sanctions_properties WHERE prop_type='LASTNAME' AND prop_value!='') s WHERE dist < 3) ORDER BY sanction_id"; 

     $sql2 = "SELECT * FROM ci_sanctions_properties WHERE prop_type='LASTNAME' AND prop_value!='' AND MATCH(prop_value) AGAINST ('+usama bin laden' IN BOOLEAN MODE) ORDER BY sanction_id"; 

     $sql3 = "SELECT s.* FROM (SELECT levenshtein(prop_value, 'usama bin laden') AS dist, sanction_id, prop_type, prop_value FROM ci_sanctions_properties WHERE prop_type='LASTNAME' AND prop_value!='') s WHERE dist < 3"; 

Answer 1

Si sólo está atado a MySQL que no hay una solución fácil.

Normalmente esto se resuelve utilizando la indexación ngram especializada para un rápido filtrado de búsqueda de candidatos y luego calculando levensthein solo en 10-50 candidatos, lo que es más rápido que calcular levensthein para todos los pares.

motores de búsqueda de texto completo especializados como Solr/Lucene han construido en esta.

PostgreSQL tiene pg_trgm contrib módulo (http://www.postgresql.org/docs/9.0/static/pgtrgm.html) que funciona como un encanto.

Incluso puede simular esto en MySQL utilizando indexación de texto completo, pero debe recopilar palabras de todos sus documentos para convertirlas a ngrams, crear índices de texto completo sobre ellas y modificarlas para una búsqueda rápida. Lo que trae todo tipo de problemas con redundancia, sincronización ... no vale la pena el tiempo.