Coincidencia parcial de nombre en millones de registros

Hemos desarrollado una aplicación web para la coincidencia de nombres. Funciona dividiendo los nombres en partes y el valor Soundex de cada parte se almacena en una base de datos. La métrica de distancia de Levenshtein se utiliza para aplicar la coincidencia porcentual del sonido, así como la ortografía de un nombre de pila.

En tiempo de ejecución, cargamos todos los registros en la memoria y aplicamos la distancia de Levenshtein a todos los valores de Soundex y la ortografía de todas las partes de todos los nombres.

Al principio esto funcionaba bien porque había un máximo de 20 mil nombres, pero ahora uno de nuestros clientes tiene 30 millones de nombres. Cargar esta lista enorme en la memoria para cada solicitud y aplicar este tipo de coincidencia es un enfoque patético, que utiliza mucha memoria y tiempo de ejecución.

Estamos buscando sugerencias para buscar en la base de datos de 30 millones de registros o más en un futuro cercano con un porcentaje de coincidencia de sonido y ortografía.

Funcionalidad central

El usuario final ingresa el nombre que debe coincidir y el porcentaje mínimo. Se supone que debemos mostrar todos esos nombres en la base de datos para los cuales cualquier parte del nombre coincide con cualquier parte del nombre dado hasta el porcentaje dado. No se requiere que el nombre completo coincida, cualquier parte si coincide con el porcentaje es un éxito. Por ejemplo.

Given Name: Helen Hunt
Name in DB: Holly Hunter 

Ambas partes de ambos nombres no coinciden exactamente, pero hasta cierto punto, supongamos que 80%, por lo que si el usuario ingresa 80%, el nombre en DB debe mostrarse como nombre coincidente.

Sin conocer todos los detalles de lo que necesita, probablemente quiera hacer uno de los siguientes:

• Use una herramienta de búsqueda existente, como Sphinx o Lucene
• Realizar una coincidencia aproximada de n gramos

No sé completamente qué implica la instalación y configuración de sphinx; pero tengo la impresión de que puede apuntarlo a una base de datos, decirle qué campos indexar, cómo ponderar los resultados y le devolverá una lista ordenada de registros coincidentes.

Para las cosas de cara al usuario o de misión crítica, use una herramienta de búsqueda existente.

Si solo te sientes académico ... Juega con ngrams:

Una tabla de búsqueda de ngrams puede servir como su conjunto inicial de coincidencias potenciales, y puede usar las distancias de Levenshtein para podar y ordenar los resultados.

Suponiendo que desea buscar people, puede hacer algo como:

_ people _________
personId: int
name: varchar
soundex_name: varchar

_ people_ngrams __
personId: int
ngramId: int

_ ngrams _________
ngramId: int
ngram: char(3)
count: int

Puede reconstruir periódicamente sus ngrams o construirlos sobre la marcha. De cualquier manera, un algoritmo de búsqueda simple e ingenuo puede verse así:

search_ngrams = ngrammify(soundex(search_string));

notable_ngrams = select top 10 *
  from ngrams
  where ngram in (search_ngrams)
  order by count asc;

possible_matches = select top 1000 distinct people.*
  from people_ngrams, people
  where ngramId in (notable_ngrams);

best_matches = top 100 possible_matches
  ordered by Levenshtein_distance(match, soundex(search_string));

Usando algo bastante similar a esto (pero con un poco más de ajuste de "popularidad" de ngram, listas negras, listas blancas, etc.), he visto este tipo de algoritmo fusionar difusamente registros entre conjuntos de datos en masa, así como facilitar la búsqueda difusa personalizada Servicios públicos y esfuerzos continuos de eliminación de duplicados.

Ahora, en mi caso, no coincidía con millones de registros, estaba buscando seleccionar las mejores combinaciones posibles entre dos conjuntos de datos del orden de cientos de miles de registros cada uno. Y queríamos que funcionara bastante rápido, en unos pocos minutos. (Rápido, ¿qué es 100,000 * 100,000?) Y tuvimos éxito.

Entonces, con el ajuste correcto, este tipo de cosas puede ser ágil y efectivo. En última instancia, pudimos producir un conjunto combinado en una máquina humilde, anticuada y de doble núcleo en unos minutos, con fusiones "cuestionables" marcadas automáticamente para revisión manual. Pero, tomó mucho tiempo encontrar el punto óptimo de popularidad / relevancia de ngram, y los umbrales correctos de distancia de cadena, y listas negras, y listas blancas ... etc.

Dicho eso , realmente puedes ser absorbido por un agujero trabajando en esto. Para cualquier material de nivel de producción del mundo real, generalmente debe usar una herramienta bien establecida que ya está hecha y optimizada para este tipo de búsqueda.

Como Sphinx o Lucene .