Buon algoritmo per trovare tutte le coppie di stringhe tra 2 set in modo che tutte le parole della prima stringa siano tutte contenute nella seconda stringa?

Question

Ho 2 grandi set di stringhe (in realtà sono nomi di prodotti)."Grande" significa pochi milioni di stringhe.

Esempio:

Insieme 1:

Some good product
Another product
Some name
Blah

Insieme 2:

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

Il set 1 contiene nomi "buoni".Il set 2 contiene nomi "sporchi".

Voglio: per ogni articolo del Set 2 (inoltre:item2) trova l'oggetto più lungo dal Set 1 (inoltre:item1) in modo che tutte le parole di item1 siano contenute in item2.

Per l'esempio riportato le coppie saranno le seguenti:

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

Finora non sono riuscito a pensare a niente di meglio dell'algoritmo di forza bruta:

1. Dividi ogni stringa del Set 1 in parole = otteniamo una serie di elenchi di parole, lascia che sia il Set 3
2. Dividi ogni stringa del Set 2 in parole = otteniamo una serie di elenchi di parole, lascia che sia il Set 4
3. Prendi un elenco di parole dal set 3 (inoltre:list3), confrontalo con tutti gli elenchi di parole del set 4 fino a trovare un elenco che sia completamente contenuto in list3.

Tuttavia ha una complessità piuttosto elevata e funziona piuttosto lentamente.La mia semplice implementazione richiede circa 1,8 secondi per trovare 1 coppia (il set 1 ha 3 milioni di articoli, il set 2 ha 4 milioni di articoli).Se implemento la stessa attività utilizzando gli indici fulltext MySQL (consente di cercare stringhe che contengono tutte le parole indicate), 1 ricerca richiede circa 0,4 secondi.Quindi mi chiedo se ci siano alcuni buoni approcci che potrebbero essere applicati qui con il sangue piccolo :)

Il mio linguaggio di programmazione è PHP7.I dati vengono archiviati nel DB MySQL.

Answer 1

Elencherò due possibili approcci che potrebbero essere ragionevolmente efficaci nella pratica, sebbene il loro tempo di esecuzione nel caso peggiore non sia migliore di quello che hai elencato.

Indici

Puoi creare un indice per ogni parola.Costruisci una tabella hash.Per ogni parola che appare in qualsiasi nome pulito, la tabella hash mappa quella parola in un elenco di tutti i nomi sporchi che contengono quella parola.Questa tabella hash può essere creata una volta in una scansione lineare dell'insieme di nomi sporchi (Set2).

Quindi, dato un nome pulito, ripetere le parole nel nome pulito.Per ogni parola, cercala nella tabella hash e ripeti tutti i nomi sporchi che contengono quella parola e controlla quante parole ha in comune con il nome pulito.Mantieni la corrispondenza migliore.

Questo può essere ottimizzato un po'.Se il nome pulito contiene una parola che ricorre in molti nomi sporchi, la gestione di quella parola risulterà lenta.Quindi, potresti trovare il numero di volte in cui ciascuna parola ricorre in un nome sporco (la sua frequenza) e memorizzarlo in una tabella hash.Quindi, dato un nome pulito, potresti scorrere le parole nel nome pulito in ordine di frequenza crescente, tenendo traccia della migliore corrispondenza trovata finora.Se hai trovato una corrispondenza di length $\ell$, è possibile interrompere anticipatamente l'iterazione senza ripetere l'iterazione $\ell-1$ parole con la frequenza più alta nel nome pulito senza perdere alcuna corrispondenza valida.

Cerca

L'ordine delle parole in un nome è irrilevante, quindi ordina le parole in ciascuna frase.Ad esempio, "qualche buon prodotto" diventa "un buon prodotto".Fallo per ogni nome in ogni set.

Successivamente, costruisci una struttura per rappresentare l'insieme dei nomi validi (Set1).Ad esempio, nel tuo esempio il trie sarà

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

Ora scegli un nome sporco.Vogliamo trovare una corrispondenza dal trie.Ti suggerisco di utilizzare un algoritmo ricorsivo per trovare tutte le corrispondenze:per trovare una corrispondenza per il nome $w_1 \cdots w_n$ nel triennio $T$, controlla se c'è un bordo fuori dalla radice di $T$ etichettato $w_1$, e, in tal caso, trova ricorsivamente tutte le corrispondenze per $w_2 \cdots w_n$ nel sottotrime indicato da quel bordo;trova anche ricorsivamente tutte le corrispondenze per $w_2 \cdots w_n$ In $T$.Una volta trovate tutte le corrispondenze, mantieni quella più lunga.

Ad esempio, per "un altro nome di prodotto molto lungo", dopo l'ordinamento diventa "un altro nome di prodotto molto lungo".Puoi cercarlo nel trie trovando ricorsivamente tutte le corrispondenze per "nome lungo prodotto molto" nel sottotrie +-- product --+, e trovando tutte le corrispondenze per "nome lungo prodotto molto" nel trie principale.

Questo processo di ricerca può essere ottimizzato in vari modi, ad esempio tenendo traccia della corrispondenza più lunga trovata finora e interrompendosi presto se non è possibile che la chiamata ricorsiva possa trovare una corrispondenza più lunga in base a quante parole hai trovato finora e come rimangono molte parole.

Non è necessario ordinare in base all'ordine lessicografico.Puoi ordinare in qualsiasi altro ordine, purché sia ​​coerente.Ad esempio, potresti ordinare in base alla frequenza delle parole nell'intero set di dati (prima nelle parole meno comuni), il che potrebbe aiutare a ridurre il numero di chiamate ricorsive.