A pangrammatic window es una subcadena de una pieza de texto más grande que contiene las 26 letras del alfabeto. Para citar un ejemplo de Wikipedia, dado este texto:¿Algún algoritmo eficiente para encontrar las ventanas pangramáticas más pequeñas?
Canté, y pensé que cantaba muy bien; pero él simplemente me miró a la cara con una expresión muy burlona, y dijo: "¿Cuánto tiempo ha estado cantando, mademoiselle?"
La ventana pangrammatic más pequeño del texto es esta cadena:
g muy bien; pero él solo me miró a la cara con una pregunta muy burlona ex
que de hecho contiene cada letra al menos una vez.
Mi pregunta es la siguiente: Dado un corpus de texto, ¿cuál es el algoritmo más eficiente para encontrar la ventana pangramática más pequeña en el texto?
Lo he pensado un poco y ya he llegado a los siguientes algoritmos. Tengo una fuerte sensación de que estos no son óptimos, pero pensé que los publicaría como punto de partida.
Hay un simple algoritmo ingenuo que se ejecuta en el tiempo O (n) y el espacio O (1): para cada posición en la cadena, escanee hacia adelante desde esa posición y rastree las letras que haya visto (tal vez en un vector de bits, que, dado que solo hay 26 letras diferentes, ocupa espacio O (1)). Una vez que haya encontrado las 26 letras, tiene la longitud de la ventana pangramática más corta que comienza en ese punto dado. Cada exploración puede tomar tiempo O (n), y hay O (n) escaneos, para un gran total de O (n) tiempo.
También podemos resolver este problema en el tiempo O (n log n) y el espacio O (n) usando una búsqueda binaria modificada. Construya 26 arreglos, uno para cada letra del alfabeto, luego rellene esas matrices con las posiciones de cada letra en el texto de entrada en orden ordenado. Podemos hacer esto simplemente escaneando el texto, añadiendo cada índice a la matriz correspondiente al personaje actual. Una vez que tenemos esto, podemos encontrar, en el tiempo O (log n), la longitud de la ventana pangramática más corta que comienza en algún índice ejecutando 26 búsquedas binarias en las matrices para encontrar la hora más temprana en que aparece cada carácter en la matriz de entrada en o después del índice dado. Cualquiera de estos números sea el más grande da el carácter de "polo largo" que aparece más abajo en la cuerda, y por lo tanto da el punto final de la ventana pangramática. La ejecución de este paso de búsqueda toma el tiempo O (log n), y como tenemos que hacerlo para todos los n caracteres de la cadena, el tiempo de ejecución total es O (n log n), con uso de memoria O (n) para las matrices.
Otro refinamiento del enfoque anterior es reemplazar las matrices y la búsqueda binaria con van Emde Boas trees y las búsquedas predecesoras. Esto aumenta el tiempo de creación a O (n log log n), pero reduce cada tiempo de búsqueda a O (log log n) tiempo, para un tiempo de ejecución neto de O (n log log n) con O (n) uso de espacio.
¿Hay algún algoritmo mejor por ahí?
Estoy bastante seguro de que esto funciona, pero no estoy seguro de ver por qué esto no saltará accidentalmente una ventana de alguna manera. ¿Estás seguro de que esto considerará correctamente todas las ventanas? – templatetypedef
@templatetypedef, la prueba es muy fácil. Invariante del paso 2 es el hecho de que la longitud de la ventana pangramática más corta que comienza en el segundo iterador es exactamente (primer iterador - segundo iterador) porque la disminución del primer iterador elimina uno de los caracteres del conjunto. De modo que puede tratar este algoritmo como una variante optimizada de su algoritmo n^2. –
¿Cómo es esto O (N), y cómo no depende del tamaño del alfabeto M? Específicamente, ¿cómo se hace la comprobación "Parar cuando los 26 contadores no son cero". en O (1), (dado que es constante, se puede hacer en O (1) pero para el caso general de M?) – kolistivra