Pruebas de frases para ver si coinciden entre sí

Question

Tengo un gran número de frases (~ varios millones), cada una de menos de seis o siete palabras y la gran mayoría de menos de cinco, y me gustaría ver si "frasean" coinciden "entre sí". Este es un término de marketing de motor de búsqueda: básicamente, una frase coincide con B si A está contenida en B. En este momento, se almacenan en un db (postgres) y estoy realizando un join en expresiones regulares (consulte this question). Se está ejecutando de manera increíblemente lenta incluso después de probar todos los trucos básicos de optimización (indexación, etc.) y probar las sugerencias proporcionadas.
¿Hay alguna manera más fácil de hacerlo? No soy contrario a una solución que no sea DB. ¿Hay alguna razón para pensar que las expresiones regulares son excesivas y están tomando más tiempo que una solución diferente?

Answer 1

Un algoritmo ideal para hacer coincidencias de subcadenas es AhoCorsick.

Aunque tendrá que leer los datos de la base de datos para usarlos, es tremendamente rápido, en comparación con los métodos más ingenuos.

Ver here a una pregunta relacionada con el juego subcadena:

Y here para una aplicación en Java AhoCorsick:

Answer 2

Sería genial tener un poco más de contexto de por qué necesita ver qué frases son subconjuntos de otras: por ejemplo, parece extraño que la base de datos se construya de esa manera de todos modos: está teniendo para hacer el trabajo ahora porque la base de datos no está en un formato apropiado, por lo que tiene sentido que debe 'arreglar' la base de datos o la forma en que está construida, en su lugar.

Depende enormemente de lo que está haciendo con los datos y por qué, pero he encontrado útil en el pasado dividir las palabras en palabras sueltas y pares de palabras, y luego vincular recursos o frases a esos singles/pares.

Por ejemplo, para poner en práctica una búsqueda que he hecho:

Fuente texto:

Testing phrases to see

Entradas:

• prueba
• frases de prueba
• frases
• frases a
• a
• para ver
• ver

para ver si otra frase era similares (de acuerdo, no contenida dentro) que se rompería la otra frase de la misma manera y contar el número de frases común entre ellos.

Tiene el bonito efecto secundario de igualar la coincidencia si utilizara (por ejemplo) "ver fases para probar": porque las palabras individuales coincidirían ... pero dado que el orden es diferente, los pares no, por lo que es tomar en cuenta las frases (palabras consecutivas) al mismo tiempo, el número de coincidencias no sería tan alto, bueno para usar como 'puntaje' en la coincidencia.

Como digo que el "tipo" de cosas me ha funcionado, pero sería genial escuchar algo más de contexto/contexto, para que podamos ver si podemos encontrar una mejor solución.

Answer 3

Cuando tenga la 'columna limpia' de la respuesta anterior de MaasSQL, puede, dependiendo de la forma en que funcione exactamente la frase "coincidencia de frase" (no sé), ordenar esta columna según la longitud de la cadena que contiene.

Luego, asegúrese de ejecutar la consulta de comparación de forma convergente en un procedimiento en lugar de una consulta plana, recorriendo su tabla (con un cursor) y eliminando candidatos para comparar mediante declaraciones WHERE y eliminando candidatos que ya probado (completamente). Es posible que necesite una tabla temporal para hacer esto.

¿Qué quiero decir con la instrucción 'WHERE' anteriormente? Bueno, si el valor de comparación está en una columna ordenada en longitud, nunca tendrá que probar si una cadena más larga coincide dentro de una cadena más corta.

Y con la eliminación de candidatos: a partir de las cadenas más cortas, una vez que haya probado todas las cadenas de cierta longitud, podrá eliminarlas de la tabla de comparación, ya que cualquier prueba siguiente nunca obtendrá una partido.

Por supuesto, esto requiere un poco más de programación que una sola instrucción SQL. Y depende de la forma en que "coincidencia de frase" funcione exactamente.

DTS o SSIS puede ser su amigo aquí también.