Resultados de búsqueda de Google: ¿Cómo encontrar la ventana mínima que contiene todas las palabras clave de búsqueda?

Question

¿Cuál es la complejidad del algoritmo que se utiliza para encontrar el fragmento más pequeño que contiene todas las palabras clave de búsqueda?

Answer 1

Como se ha indicado, el problema se resuelve mediante un algoritmo bastante simple:

Basta con mirar a través de la secuencia de entrada de texto desde el principio y comprobar cada palabra: si se trata de la clave de búsqueda o no. Si la palabra está en la clave, agréguela al final de la estructura a la que llamaremos El bloque actual. El bloque actual es solo una secuencia lineal de palabras, cada palabra acompañada por una posición en la que se encontró en el texto. El bloque actual debe mantener la siguiente propiedad : la primera palabra en The Current Block debe estar presente en The Current Block una vez y solo una vez. Si agrega la nueva palabra al final de The Current Block y se viola la propiedad anterior, debe eliminar la primera palabra del bloque. Este proceso se llama normalización del bloque actual. La normalización es un proceso potencialmente iterativo, ya que una vez que elimina la primera palabra del bloque, la nueva primera palabra también puede violar la propiedad, por lo que tendrá que eliminarla también. Y así.

Por lo tanto, básicamente, el bloque actual es una secuencia FIFO: las palabras nuevas llegan al extremo derecho, y se eliminan mediante el proceso de normalización desde el extremo izquierdo.

Todo lo que tienes que hacer para resolver el problema es mirar a través del texto, mantener The Current Block, normalizándolo cuando sea necesario para que satisfaga The Property. El bloque más corto con todas las palabras clave que hayas creado es la respuesta al problema.

Por ejemplo, considere el texto

CxxxAxxxBxxAxxCxBAxxxC

con palabras clave A, B y C. Mirando a través del texto que va a construir la siguiente secuencia de bloques

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) 

El mejor bloque construimos tiene una longitud de 4, que es la respuesta en este caso

CxxxAxxxBxxAxx CxBA XXXC

La complejidad exacta de este algoritmo depende de la entrada, ya que determina cuántas iteraciones del proceso de normalización hará, pero haciendo caso omiso de la normalización de la complejidad sería trivialmente ser O(N * log M), donde N es el número de palabras en el texto y M es el número de palabras clave, y O(log M) es la complejidad de verificar si la palabra actual pertenece al conjunto de palabras clave.

Ahora, una vez dicho esto, tengo que admitir que sospecho que esto podría no ser lo que necesita. Como mencionaste a Google en el título, es posible que la declaración del problema que diste en tu publicación no esté completa. ¿Tal vez en su caso el texto está indexado? (Con la indexación, el algoritmo anterior sigue siendo aplicable, solo se vuelve más eficiente). Tal vez hay alguna base de datos complicada que describe el texto y permite una solución más eficiente (como sin mirar el texto completo). Solo puedo adivinar y no estás diciendo ...

Answer 2

Esta es una pregunta interesante. Reiterar de manera más formal: Dada una lista L (la página web) de longitud n y un conjunto S (la consulta) de tamaño k, encontrar la más pequeña lista secundaria de L que contiene todos los elementos de S.

Comenzaré con una solución de fuerza bruta con la esperanza de inspirar a otros a vencerla. Tenga en cuenta que la membresía establecida se puede hacer en tiempo constante, después de una pasada por el conjunto. Ver this question. También tenga en cuenta que esto supone que todos los elementos de S están de hecho en L, de lo contrario solo devolverá la sublista de 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). 

complejidad tiempo es O ((n + k) (n-k)). Es decir, n^2-ish.

Answer 3

Creo que la solución propuesta por AndreyT supone que no existen duplicados en las palabras clave/términos de búsqueda. Además, el bloque actual puede llegar a ser tan grande como el texto si el texto contiene muchas palabras clave duplicadas. Por ejemplo: Texto: texto 'ABBBBBBBBBB' Palabra clave: 'AB' bloque actual: 'ABBBBBBBBBB'

De todos modos, he implementado en C#, hice algunas pruebas básicas, sería bueno obtener alguna información sobre si funciona o no :)

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; 
    } 

Answer 4

He probado la solución de AnT extensivamente. El único problema con esta solución es que solo considera duplicados cuando aparecen delante del fragmento. Un ejemplo claro es este: text = x4x2xx88x4248 key = 4 2 8 cuyo algoritmo de AnT fallará al encontrar el caso 248. Para solucionar esto, solo tiene que cambiar la propiedad antes mencionada a esta: Cada palabra clave debe estar presente en el bloque actual solo una vez. Por lo tanto, cada vez que agregue una nueva clave al bloque, elimine la aparición previa de la misma clave.