¿Buen algoritmo para encontrar todos los pares de cadenas entre 2 conjuntos de modo que todas las palabras de la primera cadena estén contenidas en la segunda cadena?

Question

Tengo 2 conjuntos grandes de cadenas (en realidad son nombres de productos)."Grande" significa unos pocos millones de cadenas.

Ejemplo:

Serie 1:

Some good product
Another product
Some name
Blah

Conjunto 2:

Very long some product name with words blah
Another very long product name
asd asd sad sad asdsa
Blah blah blah

El conjunto 1 contiene nombres "buenos".El conjunto 2 contiene nombres "sucios".

Deseo: para cada artículo del Conjunto 2 (además:elemento2) busque el elemento más largo del conjunto 1 (además:elemento1) para que todas las palabras del elemento1 estén contenidas en el elemento2.

Para el ejemplo dado, los pares serán los siguientes:

Very long SOME product NAME with words blah => Some name
ANOTHER very long PRODUCT name              => Another product
asd asd sad sad asdsa                       => none
BLAH blah blah                              => blah

Hasta ahora no se me ocurrió nada mejor que el algoritmo de fuerza bruta:

1. Divida cada cadena del Conjunto 1 en palabras = obtenemos un conjunto de listas de palabras, sea el Conjunto 3
2. Divida cada cadena del Conjunto 2 en palabras = obtenemos un conjunto de listas de palabras, sea el Conjunto 4
3. Elija una lista de palabras del Conjunto 3 (además:list3), compárelo con todas las listas de palabras del conjunto 4 hasta encontrar alguna lista que esté completamente contenida en list3.

Sin embargo, tiene una complejidad bastante alta y funciona bastante lento.Mi implementación simple toma alrededor de 1,8 segundos para encontrar 1 par (el conjunto 1 tiene 3 millones de elementos, el conjunto 2 tiene 4 millones de elementos).Si implemento la misma tarea usando índices de texto completo de MySQL (permite buscar cadenas que contengan todas las palabras dadas), entonces 1 búsqueda toma aproximadamente 0,4 segundos.Entonces me pregunto si existen algunos buenos enfoques que podrían aplicarse aquí con sangre pequeña :)

Mi lenguaje de programación es PHP7.Los datos se almacenan en la base de datos MySQL.

Answer 1

Enumeraré dos enfoques posibles que podrían ser razonablemente efectivos en la práctica, aunque su tiempo de ejecución en el peor de los casos no es mejor que el que usted enumeró.

Índices

Puede crear un índice para cada palabra.Construye una tabla hash.Para cada palabra que aparece en cualquier nombre limpio, la tabla hash asigna esa palabra a una lista de todos los nombres sucios que contienen esa palabra.Esta tabla hash se puede crear una vez en un escaneo lineal del conjunto de nombres sucios (Set2).

Luego, dado un nombre limpio, repita las palabras del nombre limpio.Para cada palabra, búsquela en la tabla hash, repita todos los nombres sucios que contienen esa palabra y verifique cuántas palabras tiene en común con el nombre limpio.Mantenga la mejor combinación.

Esto se puede optimizar un poco.Si el nombre limpio contiene una palabra que aparece en muchos nombres sucios, el manejo de esa palabra será lento.Por lo tanto, puede encontrar la cantidad de veces que aparece cada palabra en algún nombre sucio (su frecuencia) y almacenarlo en una tabla hash.Luego, dado un nombre limpio, podría iterar sobre las palabras del nombre limpio en orden de frecuencia creciente, realizando un seguimiento de la mejor coincidencia que haya encontrado hasta el momento.Si has encontrado una coincidencia de longitud $\ell$, entonces puedes detener la iteración antes de tiempo sin iterar más $\ell-1$ palabras de mayor frecuencia en el nombre limpio sin perder ninguna coincidencia válida.

Intentos

El orden de las palabras en un nombre es irrelevante, así que ordene las palabras en cada frase.Por ejemplo, "algún buen producto" se convierte en "algún buen producto".Haga esto con cada nombre en cada conjunto.

A continuación, cree un trie para representar el conjunto de buenos nombres (Conjunto1).Por ejemplo, en su ejemplo el intento será

+-- another --+-- product --+
|`-- blah --+
|`-- good --+-- product --+-- some --+
 `-- name --+-- some --+

Ahora, elige un nombre sucio.Queremos encontrarle una coincidencia en el trie.Le sugiero que utilice un algoritmo recursivo para encontrar todas las coincidencias:para encontrar una coincidencia para el nombre $w_1 \cdots w_n$ en el intento $t$, compruebe si hay un borde fuera de la raíz de $t$ etiquetado $w_1$, y si es así, busque recursivamente todas las coincidencias para $w_2 \cdots w_n$ en la subtrie señalada por ese borde;también buscar recursivamente todas las coincidencias para $w_2 \cdots w_n$ en $t$.Una vez que haya encontrado todas las coincidencias, conserve la más larga.

Por ejemplo, para "otro nombre de producto muy largo", después de ordenarlo se convierte en "otro producto de nombre largo muy".Lo buscas en el trie buscando recursivamente todas las coincidencias para 'producto de nombre largo muy' en el subtrie +-- product --+, y encontrando todas las coincidencias para 'producto de nombre largo muy' en el trie principal.

Este proceso de búsqueda se puede optimizar de varias maneras, por ejemplo, realizando un seguimiento de la coincidencia más larga encontrada hasta el momento y deteniéndose temprano si no hay manera de que la llamada recursiva pueda encontrar una coincidencia más larga en función de cuántas palabras haya coincidido hasta ahora y cómo Quedan muchas palabras.

No es necesario ordenar por orden lexicográfico.Puedes ordenar en cualquier otro orden, siempre que sea coherente.Por ejemplo, podría ordenar por la frecuencia de las palabras en todo el conjunto de datos (primero en las palabras menos comunes), lo que podría ayudar a reducir la cantidad de llamadas recursivas.