Bom algoritmo para encontrar todos os pares de strings entre 2 conjuntos, de modo que todas as palavras da 1ª string estejam contidas na 2ª string?

Question

Eu tenho 2 grandes conjuntos de strings (na verdade, são nomes de produtos)."Grande" significa alguns milhões de strings.

Exemplo:

Conjunto 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

O conjunto 1 contém nomes "bons".O conjunto 2 contém nomes "sujos".

Eu quero: para cada item do Conjunto 2 (mais:item2) encontre o item mais longo do Conjunto 1 (mais:item1) para que todas as palavras do item1 estejam contidas no item2.

Para o exemplo dado, os pares serão os seguintes:

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

Até agora não consegui pensar em nada melhor do que algoritmo de força bruta:

1. Divida cada string do Conjunto 1 em palavras = obtemos um conjunto de listas de palavras, seja o Conjunto 3
2. Divida cada string do Conjunto 2 em palavras = obtemos um conjunto de listas de palavras, seja o Conjunto 4
3. Pegue uma lista de palavras do Conjunto 3 (mais:lista3), compare-a com todas as listas de palavras do Conjunto 4 até encontrar alguma lista que esteja totalmente contida na lista3.

No entanto, tem uma complexidade bastante elevada e funciona bastante lento.Minha implementação simples leva cerca de 1,8s para encontrar 1 par (o conjunto 1 tem 3 milhões de itens, o conjunto 2 tem 4 milhões de itens).Se eu implementar a mesma tarefa usando índices de texto completo do MySQL (permite pesquisar strings que contenham todas as palavras fornecidas), uma pesquisa levará cerca de 0,4s.Então, estou me perguntando se existem algumas boas abordagens que poderiam ser aplicadas aqui com pouco sangue :)

Minha linguagem de programação é PHP7.Os dados são armazenados no banco de dados MySQL.

Answer 1

Listarei duas abordagens possíveis que podem ser razoavelmente eficazes na prática, embora o tempo de execução no pior caso não seja melhor do que o que você listou.

Índices

Você pode criar um índice para cada palavra.Construa uma tabela hash.Para cada palavra que aparece em qualquer nome limpo, a tabela hash mapeia essa palavra para uma lista de todos os nomes sujos que a contêm.Esta tabela hash pode ser construída uma vez em uma varredura linear do conjunto de nomes sujos (Conjunto2).

Em seguida, dado um nome limpo, repita as palavras do nome limpo.Para cada palavra, procure na tabela hash e repita todos os nomes sujos que contêm essa palavra e verifique quantas palavras ela tem em comum com o nome limpo.Mantenha a melhor combinação.

Isso pode ser um pouco otimizado.Se o nome limpo contiver uma palavra que ocorre em muitos nomes sujos, o manuseio dessa palavra será lento.Assim, você poderia encontrar o número de vezes que cada palavra ocorre em algum nome sujo (sua frequência) e armazenar isso em uma tabela hash.Então, com um nome limpo, você pode iterar as palavras do nome limpo em ordem crescente de frequência, acompanhando a melhor correspondência encontrada até o momento.Se você encontrou uma correspondência de comprimento $\el$, então você pode interromper a iteração mais cedo, sem repetir $\el-1$ palavras de maior frequência no nome limpo sem perder nenhuma correspondência válida.

Tentativas

A ordem das palavras em um nome é irrelevante, então classifique as palavras em cada frase.Por exemplo, 'algum produto bom' torna-se 'algum produto bom'.Faça isso com cada nome em cada conjunto.

A seguir, construa uma tentativa para representar o conjunto de bons nomes (Conjunto1).Por exemplo, no seu exemplo, a tentativa será

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

Agora, escolha um nome sujo.Queremos encontrar uma correspondência para ele na tentativa.Sugiro que você use um algoritmo recursivo para encontrar todas as correspondências:para encontrar uma correspondência para o nome $w_1 \cdots w_n$ na tentativa $T$, verifique se há uma aresta fora da raiz de $T$ rotulado $w_1$, e, em caso afirmativo, encontre recursivamente todas as correspondências para $w_2 \cdots w_n$ na subtrie apontada por essa aresta;também encontrar recursivamente todas as correspondências para $w_2 \cdots w_n$ em $T$.Depois de encontrar todas as correspondências, mantenha a mais longa.

Por exemplo, para 'outro nome de produto muito longo', após a classificação, torna-se 'outro produto com nome muito longo'.Você procura isso na tentativa, encontrando recursivamente todas as correspondências para 'produto de nome longo muito' na subtrie +-- product --+, e encontrando todas as correspondências para 'produto de nome longo muito' na tentativa principal.

Este processo de pesquisa pode ser otimizado de várias maneiras, por exemplo, acompanhando a correspondência mais longa encontrada até o momento e parando mais cedo se não houver como a chamada recursiva encontrar uma correspondência mais longa com base em quantas palavras você combinou até agora e como muitas palavras permanecem.

Não há necessidade de classificar por ordem lexicográfica.Você pode classificar em qualquer outra ordem, desde que seja consistente.Por exemplo, você pode classificar pela frequência das palavras em todo o conjunto de dados (primeiro nas palavras menos comuns), o que pode ajudar a reduzir o número de chamadas recursivas.