¿Cómo hago una coincidencia aproximada de nombres de compañías en MYSQL con PHP para autocompletar?

Mis usuarios importan a través de cortar y pegar una cadena grande que contendrá los nombres de las compañías.

Tengo una base de datos MYSQL existente y en crecimiento de nombres de compañías, cada una con un company_id único.

Quiero poder analizar a través de la cadena y asignar una coincidencia difusa a cada uno de los nombres de compañías con el usuario.

En este momento, solo hacer una coincidencia de cuerdas hacia arriba, también es lento. ** ¿La indexación de Soundex será más rápida? ¿Cómo puedo darle al usuario algunas opciones mientras escriben? **

Por ejemplo, alguien escribe:

 Microsoft -> Microsoft
 Bare Essentials -> Bare Escentuals
 Polycom, Inc. -> Polycom

He encontrado los siguientes hilos que parecen similares a esta pregunta, pero el cartel no ha sido aprobado y no estoy seguro de si su caso de uso es aplicable:

Cómo encontrar la mejor coincidencia difusa para una cadena en una gran base de datos de cadenas

Coincidencia de nombres de compañías inexactas en Java

Puede comenzar utilizando SOUNDEX() , esto probablemente servirá para lo que necesita (me imagino un cuadro de sugerencias automáticas de alternativas ya existentes para lo que el usuario está tipeando).

Los inconvenientes de SOUNDEX() son:

  • su incapacidad para diferenciar cadenas más largas. Solo se tienen en cuenta los primeros caracteres, las cadenas más largas que divergen al final generan el mismo valor SOUNDEX
  • el hecho de que la primera letra debe ser la misma o no encontrará una coincidencia fácilmente. SQL Server tiene la función DIFFERENCE () para decirle cuánto se separan dos valores de SOUNDEX, pero creo que MySQL no tiene nada de ese tipo integrado.
  • para MySQL, al menos de acuerdo con los documentos , SOUNDEX está roto para entrada unicode

Ejemplo:

 SELECT SOUNDEX('Microsoft') SELECT SOUNDEX('Microsift') SELECT SOUNDEX('Microsift Corporation') SELECT SOUNDEX('Microsift Subsidary') /* all of these return 'M262' */ 

Para necesidades más avanzadas, creo que debes mirar la distancia de Levenshtein (también llamada “distancia de edición”) de dos cadenas y trabajar con un umbral. Esta es la solución más compleja (= más lenta), pero permite una mayor flexibilidad.

El principal inconveniente es que necesita ambas cadenas para calcular la distancia entre ellas. Con SOUNDEX puede almacenar un SOUNDEX precalculado en su tabla y comparar / clasificar / agrupar / filtrar sobre eso. Con la distancia de Levenshtein, puede encontrar que la diferencia entre “Microsoft” y “Nzcrosoft” es solo 2, pero tomará mucho más tiempo llegar a ese resultado.

En cualquier caso, un ejemplo de la función de distancia de Levenshtein para MySQL se puede encontrar en codejanitor.com: Levenshtein Distance como una función almacenada de MySQL (10 de febrero de 2007) .

SOUNDEX es un algoritmo OK para esto, pero ha habido avances recientes en este tema. Se creó otro algoritmo llamado Metaphone, y luego fue revisado a un algoritmo Double Metaphone. Personalmente, utilicé la implementación de java apache commons de metafonía doble y es personalizable y precisa.

También tienen implementaciones en muchos otros idiomas en la página de wikipedia. Esta pregunta ha sido respondida, pero si encuentra alguno de los problemas identificados con SOUNDEX en su aplicación, es bueno saber que hay opciones. A veces puede generar el mismo código para dos palabras realmente diferentes. Double metaphone fue creado para ayudar a resolver ese problema.

Robado de la wikipedia: http://en.wikipedia.org/wiki/Soundex

Como respuesta a las deficiencias en el algoritmo Soundex, Lawrence Philips desarrolló el algoritmo Metaphone para el mismo propósito. Philips luego desarrolló una mejora para Metaphone, a la que llamó Double-Metaphone. Double-Metaphone incluye un conjunto de reglas de encoding mucho más grande que su predecesor, maneja un subconjunto de caracteres no latinos y devuelve una encoding primaria y secundaria para tener en cuenta las diferentes pronunciaciones de una sola palabra en inglés.

En la parte inferior de la página de doble metafonía, tienen implementaciones para todo tipo de lenguajes de progtwigción: http://en.wikipedia.org/wiki/Doble-Metaphone

Implementación de Python y MySQL: https://github.com/AtomBoy/double-metaphone

En primer lugar, me gustaría añadir que debes ser muy cuidadoso al usar cualquier forma de Algoritmo de Coincidencia Fonética / Fuzzy, ya que este tipo de lógica es exactamente eso, Fuzzy o para decirlo de manera más simple; potencialmente inexacto Especialmente cierto cuando se usa para hacer coincidir nombres de compañías.

Un buen enfoque es buscar la corroboración de otros datos, como información de dirección, códigos postales, números de teléfono, coordenadas geográficas, etc. Esto ayudará a confirmar la probabilidad de que sus datos coincidan con precisión.

Existe una amplia gama de problemas relacionados con la coincidencia de datos B2B que se abordarán aquí. He escrito más sobre la coincidencia de nombres de empresas en mi blog, pero en resumen, los problemas clave son:

  • Observar toda la cadena no es útil ya que la parte más importante de un Nombre de la empresa no es necesariamente al comienzo del Nombre de la empresa. es decir, “The Proctor and Gamble Company” o “Reserva Federal de los Estados Unidos”
  • Las abreviaturas son un lugar común en los nombres de las empresas, es decir HP, GM, GE, P & G, D & B, etc.
  • Algunas compañías deletrean deliberadamente sus nombres incorrectamente como parte de su marca y para diferenciarse de otras compañías.

La coincidencia de datos exactos es fácil, pero la coincidencia de datos no exactos puede consumir mucho más tiempo y sugiero que considere la forma de validar las coincidencias no exactas para garantizar que sean de calidad aceptable.

Antes de construir Match2Lists.com, solíamos pasar una cantidad insalubre de tiempo validando coincidencias difusas. En Match2Lists incorporamos una poderosa herramienta de visualización que nos permite revisar las coincidencias no exactas, esto resultó ser un verdadero cambio de juego en términos de validación de coincidencias, reduciendo nuestros costos y permitiéndonos entregar resultados mucho más rápidamente.

¡¡La mejor de las suertes!!

Aquí hay un enlace a la discusión php de las funciones soundex en mysql y php. Empezaría desde allí y luego ampliaría sus otros requisitos no tan bien definidos.

Su referencia hace referencia a la metodología de Levenshtein para emparejar. Dos problemas 1. Es más apropiado para medir la diferencia entre dos palabras conocidas, no para buscar. 2. Discute una solución diseñada más para detectar cosas como errores de pruebas (usando “Levenshtien” para “Levenshtein”) en lugar de errores de ortografía (donde el usuario no sabe cómo deletrear, decir “Levenshtein” y escribe “Levinstein” Normalmente lo asocio con la búsqueda de una frase en un libro en lugar de un valor clave en una base de datos.

EDITAR: En respuesta al comentario–

  1. Al menos puede hacer que los usuarios pongan los nombres de las compañías en varios cuadros de texto; 2. o use un delimitador de nombre no ambiguo (por ejemplo, barra invertida); 3. omita los artículos (“The”) y las abreviaturas genéricas (o puede filtrarlas); 4. Scumple los espacios y combínelos también (así Micro Soft => microsoft, Bare Essentials => bareessentials); 5. Filtra la puntuación; 6. Haga “O” búsquedas en palabras (“desnudo” O “esenciales”): las personas inevitablemente dejarán a uno o al otro a veces.

Prueba como loco y utiliza el ciclo de retroalimentación de los usuarios.

la mejor función para el emparejamiento difuso es levenshtein. tradicionalmente es utilizado por los correctores ortográficos, por lo que podría ser el camino a seguir. hay una UDF disponible aquí: http://joshdrew.com/

La desventaja de usar levenshtein es que no se escalará muy bien. una mejor idea podría ser volcar toda la tabla en un archivo de diccionario personalizado de corrector ortográfico y hacer la sugerencia desde su nivel de aplicación en lugar del nivel de la base de datos.

Esta respuesta da como resultado una búsqueda indexada de casi cualquier entidad con una entrada de 2 o 3 caracteres o más.

Básicamente, crea una nueva tabla con 2 columnas, palabra y clave. Ejecute un proceso en la tabla original que contiene la columna que se buscará fuzzy. Este proceso extraerá cada palabra individual de la columna original y escribirá estas palabras en la tabla de palabras junto con la clave original. Durante este proceso, las palabras que ocurren comúnmente como ‘the’, ‘and’, etc. deben descartarse.

Luego creamos varios índices en la tabla de palabras, de la siguiente manera …

  • Un índice normal, minúscula en palabra + clave
  • Un índice en el 2º al 5º carácter + tecla
  • Un índice en el 3er al 6º carácter + tecla

    Alternativamente, cree un índice SOUNDEX () en la columna de palabra.

Una vez que esto esté en su lugar, tomamos cualquier entrada de usuario y buscamos utilizando word = input o LIKE input%. Nunca hacemos una entrada LIKE% ya que siempre estamos buscando una coincidencia en cualquiera de los 3 primeros caracteres, que están todos indexados.

Si su tabla original es masiva, puede dividir la tabla de palabras por partes del alfabeto para asegurarse de que la entrada del usuario se reduzca a filas candidatas inmediatamente.

Puede ser demasiado tarde, pero podría ayudar a otros. Verifique este enlace. Utiliza las métricas de distancia levenshtein pero es mucho más rápido. http://narenonit.blogspot.com/2012/07/fuzzy-matching-autocomplete-library.html

    Intereting Posts