Qual è la complessità dell'algoritmo utilizzato per trovare il frammento più piccolo che contiene tutte le parole chiave di ricerca?Risultati di ricerca di Google: come trovare la finestra minima che contiene tutte le parole chiave di ricerca?
Come detto, il problema viene risolto da un piuttosto semplice algoritmo:
Basta guardare attraverso il testo di input in sequenza fin dall'inizio e controllare ogni parola: se è nella chiave di ricerca o no. Se la parola è nella chiave, aggiungila alla fine della struttura che chiameremo The Current Block. Il blocco corrente è solo una sequenza lineare di parole, ogni parola è accompagnata da una posizione in cui è stata trovata nel testo. Il blocco corrente deve mantenere la seguente Proprietà: la prima parola in The Current Block deve essere presente in The Current Block una sola volta. Se aggiungi la nuova parola alla fine di The Current Block e la proprietà sopra descritta viene violata, devi rimuovere la prima parola dal blocco. Questo processo si chiama normalizzazione di The Current Block. La normalizzazione è un processo potenzialmente iterativo, dal momento che una volta rimossa la prima parola dal blocco, la nuova prima parola potrebbe anche violare la proprietà, quindi sarà necessario rimuoverla. E così via.
Quindi, il blocco corrente è una sequenza FIFO: le nuove parole arrivano all'estremità destra e vengono rimosse dal processo di normalizzazione dall'estremità sinistra.
Tutto ciò che dovete fare per risolvere il problema è guardare attraverso il testo, mantenere il blocco corrente, normalizzarlo quando necessario in modo che soddisfi la proprietà. Il blocco più breve con tutte le parole chiave che hai creato è la risposta al problema.
Ad esempio, consideriamo il testo
CxxxAxxxBxxAxxCxBAxxxC
con parole chiave A, B e C. Guardando attraverso il testo potrai costruire la seguente sequenza di blocchi
C
CA
CAB - all words, length 9 (CxxxAxxxB...)
CABA - all words, length 12 (CxxxAxxxBxxA...)
CABAC - violates The Property, remove first C
ABAC - violates The Property, remove first A
BAC - all words, length 7 (...BxxAxxC...)
BACB - violates The Property, remove first B
ACB - all words, length 6 (...AxxCxB...)
ACBA - violates The Property, remove first A
CBA - all words, length 4 (...CxBA...)
CBAC - violates The Property, remove first C
BAC - all words, length 6 (...BAxxxC)
Il miglior blocco abbiamo costruito ha lunghezza 4, che è la risposta in questo caso
CxxxAxxxBxxAxx CxBA xxxC
La complessità esatta di questo algoritmo dipende dall'ingresso, dato che indica il numero di iterazioni del processo di normalizzazione farà, ma ignorando la normalizzazione della complessità sarebbe banalmente essere O(N * log M), dove N è il numero di parole del testo e M è il numero di parole chiave e O(log M) è la complessità di controllare se la parola corrente appartiene alla parola chiave impostata.
Ora, detto questo, devo ammettere che sospetto che questo potrebbe non essere quello che ti serve. Dal momento che hai citato Google nella didascalia, potrebbe essere che la dichiarazione del problema che hai dato nel tuo post non sia completa. Forse nel tuo caso il testo è indicizzato? (Con l'indicizzazione l'algoritmo di cui sopra è ancora applicabile, diventa semplicemente più efficiente). Forse c'è qualche database difficile che descrive il testo e consente una soluzione più efficiente (come senza guardare l'intero testo)? Posso solo indovinare e non stai dicendo ...
Questa è una domanda interessante. di ribadire più formale: Dato un elenco L (la pagina web) di lunghezza n e un insieme S (la query) di dimensione k, trovare il più piccolo elenco secondario di L che contiene tutti gli elementi di S.
Inizierò con una soluzione a forza bruta nella speranza di ispirare gli altri a batterlo. Si noti che l'appartenenza al set può essere eseguita in tempo costante, dopo un passaggio attraverso il set. Vedi this question. Si noti inoltre che questo presuppone che tutti gli elementi di S siano effettivamente in L, altrimenti restituirà semplicemente il sottolista da 1 a n.
best = (1,n)
For i from 1 to n-k:
Create/reset a hash found[] mapping each element of S to False.
For j from i to n or until counter == k:
If found[L[j]] then counter++ and let found[L[j]] = True;
If j-i < best[2]-best[1] then let best = (i,j).
La complessità del tempo è O ((n + k) (n-k)). Vale a dire, n^2-ish.
Già battuto da un algoritmo single-pass nella mia risposta. Inoltre, non capisco come pensi di fare l'appartenenza al set in un tempo costante, dato che i membri del set sono * words *. Un hash perfetto può farlo, ma non è fattibile nel caso generale, dato che stiamo lavorando con parole * arbitrarie *. L'approccio al tuo collegamento è per * sottoinsieme * appartenenza con un insieme "principale" finito, che ovviamente non è il caso in questo problema. – AnT
Bel lavoro, Andrey! Immagino che stavo immaginando di convertire prima tutte le parole in numeri interi. – dreeves
Penso che la soluzione proposta da AndreyT non presuma duplicati nelle parole chiave/termini di ricerca. Inoltre, il blocco corrente può diventare grande quanto il testo stesso se il testo contiene molte parole chiave duplicate. Ad esempio: Testo: 'ABBBBBBBBBB' chiave di testo: 'AB' blocco attuale: 'ABBBBBBBBBB'
In ogni caso, ho implementato in C#, fatto alcuni test di base, sarebbe bello ottenere un feedback sul fatto funziona o meno :)
static string FindMinWindow(string text, string searchTerms)
{
Dictionary<char, bool> searchIndex = new Dictionary<char, bool>();
foreach (var item in searchTerms)
{
searchIndex.Add(item, false);
}
Queue<Tuple<char, int>> currentBlock = new Queue<Tuple<char, int>>();
int noOfMatches = 0;
int minLength = Int32.MaxValue;
int startIndex = 0;
for(int i = 0; i < text.Length; i++)
{
char item = text[i];
if (searchIndex.ContainsKey(item))
{
if (!searchIndex[item])
{
noOfMatches++;
}
searchIndex[item] = true;
var newEntry = new Tuple<char, int> (item, i);
currentBlock.Enqueue(newEntry);
// Normalization step.
while (currentBlock.Count(o => o.Item1.Equals(currentBlock.First().Item1)) > 1)
{
currentBlock.Dequeue();
}
// Figuring out minimum length.
if (noOfMatches == searchTerms.Length)
{
var length = currentBlock.Last().Item2 - currentBlock.First().Item2 + 1;
if (length < minLength)
{
startIndex = currentBlock.First().Item2;
minLength = length;
}
}
}
}
return noOfMatches == searchTerms.Length ? text.Substring(startIndex, minLength) : String.Empty;
}
Ho testato la soluzione di AnT ampiamente. L'unico problema con questa soluzione è che considera solo i duplicati quando appaiono davanti allo snippet. Un chiaro esempio è questo: text = x4x2xx88x4248 key = 4 2 8 quale algoritmo di AnT fallirà nel trovare il caso 248. Per risolvere questo problema, è sufficiente modificare la summenzionata proprietà a questo: Ogni parola chiave deve essere presente nel blocco corrente solo una volta. Quindi ogni volta che aggiungi una nuova chiave al blocco rimuovi l'occorrenza precedente della stessa chiave.
Nella quarta iterazione del tuo esempio, perché dovresti considerare CABA con lunghezza 12 quando hai già CAB con lunghezza 9? CAB ha già tutte le parole chiave, quindi CABA con l'A in più è ridondante. – stackoverflowuser2010
@ stackoverflowuser2010 Non direi così. Immagina il caso in cui la stringa di parole chiave più breve è CA (BAC). Se non considerassimo il caso 4 e ignorassimo l'extra A non verrebbe utilizzato negli schemi successivi. In alternativa, se ho letto male il tuo problema e stai effettivamente chiedendo perché è stato preso in considerazione quando l'altro elemento era più lungo, cioè perché nella rappresentazione che sta usando AndreyT, non stanno mostrando il minimo attualmente registrato, stanno tenendo traccia di la storia della loro traversata. Sarebbe altrettanto valido mantenere un minimo corrente ma questo non è quello che viene mostrato – Paarth
In realtà, non funziona. Guarda l'esempio: x4x2xx88x424, e stai cercando 4,2,8. Utilizzando il tuo algoritmo, non saremo in grado di trovare la soluzione migliore. –