python - Número máximo de subcadenas únicas de una partición

string algorithm (7)

Modificó el título un poco para hacerlo más comprensible.

Aquí está la versión detallada. Supongamos que tenemos una cadena s , queremos dividirla en algunas subcadenas . Cada subcadena es diferente entre sí. ¿Cuál es el número máximo de subcadenas únicas que podemos tener de un corte? En otras palabras, puede recuperar s concatenando esas subcadenas.

Aquí hay unos ejemplos:

Example 1 s = ''aababaa'' output = 4 Explain: we can split it into aa|b|aba|a or aab|a|b|aa, and 4 is the max number of substrings we can get from one split. Example 2 s = ''aba'' output = 2 Explain: a|ba Example 3 s = ''aaaaaaa'' output = 3 Explain: a|aa|aaaa

Nota : s solo contiene caracteres en minúscula. No estoy seguro de cuánto tiempo es lo que me hace no podría adivinar la complejidad de tiempo óptima. :(

¿Es un problema NP-difícil? Si no, ¿cómo resolverlo de manera eficiente?

Escuché este problema de uno de mis amigos. Y no pude sacarlo. Estoy tratando de usar un Trie + codicioso para resolver este problema. Pero falla en el primer ejemplo.

Aquí está la solución trie que se me ocurrió:

def triesolution(s): trie = {} p = trie output = 0 for char in s: if char not in p: output += 1 p[char] = {} p = trie else: p = p[char] return output

Por ejemplo 1, el código anterior devolverá 3, ya que está tratando de dividirlo en a|ab|abaa .

Agregue: Gracias a la idea de todos, parece que este problema está muy cerca de un problema de NP. En este momento, estoy tratando de pensarlo desde esta dirección. Supongamos que tenemos una función Guess(n) . Esta función devolverá True si pudiéramos encontrar n subcadenas únicas de una división o False contrario. Una observación aquí es que si Guess(n) == True , entonces Guess(i) == True para todo i <= n . Ya que podemos fusionar dos subcadenas adyacentes juntas. Esta observación puede conducir a una solución binaria. Sin embargo, todavía requiere que podamos calcular la función Guess manera muy eficiente. Lamentablemente, todavía no pude encontrar una forma polinómica para calcular Guess(n) .

(Muchas gracias a Gilad Barkan (גלעד ברקן) por informarme sobre esta discusión).

Permítanme compartir mis pensamientos sobre este problema desde un punto de vista puramente teórico (tenga en cuenta que también uso "factor" en lugar de "subword").

Creo que una definición suficientemente formal del problema (o problemas) considerada aquí es la siguiente:

Dada una palabra w, encuentre las palabras u_1, u_2, ..., u_k de modo que

u_i! = u_j para cada i, j con 1 <= i <j <= k y
u_1 u_2 ... u_k = w

Variante de maximización (queremos muchos u_i): maximizar k

Variante de minimización (queremos corto u_i): minimizar max {| u_i | : 1 <= i <= k}

Estos problemas se convierten en problemas de decisión al dar además un límite B, que, de acuerdo con si estamos hablando de la variable "muchos factores" o de la variable "factores cortos", es un límite inferior en k (queremos al menos B factores), o un límite superior en max {| u_i | : 1 <= i <= k} (queremos factores de longitud como máximo B), respectivamente. Para hablar sobre la dureza NP, necesitamos hablar sobre problemas de decisión.

Usemos los términos SF para la variable "factores cortos" y MF para la variable "muchos factores". En particular, y este es un punto realmente crucial, los problemas se definen de tal manera que obtenemos una palabra sobre un alfabeto que no está restringido de ninguna manera. La versión del problema es que sabemos a priori que solo recibimos palabras de entrada, por ejemplo, el alfabeto {a, b, c, d} es un problema diferente. La dureza NP no se transfiere automáticamente de la variante "sin restricciones" a la "alfabeto fijo" (esta última podría ser más simple).

Tanto SF como MF son problemas NP-completos. Esto se ha demostrado en [1, 1b] y [2], respectivamente (como Gilad ya lo ha señalado). Si entiendo la definición de problema informal (tal vez también) aquí al comienzo de esta discusión correctamente, entonces el problema de esta discusión es exactamente el problema MF. Inicialmente no se menciona que las palabras están restringidas para provenir de un alfabeto fijo, luego se dice que podemos suponer que solo se usan letras minúsculas. Si esto significa que solo consideramos palabras sobre el alfabeto fijo {a, b, c, ..., z}, entonces esto realmente cambiaría mucho en términos de dureza NP.

Una mirada más cercana revela algunas diferencias en la complejidad de SF y MF:

el trabajo [1, 1b] muestra que SF sigue siendo NP-completo si fijamos el alfabeto a uno binario (más precisamente: obteniendo una palabra w sobre las letras a y by un B, podemos factorizarla en distintos factores de longitud en más B?)
el artículo [1, 1b] muestra que SF sigue siendo NP completo si arreglamos el límite B = 2 (más precisamente: obteniendo una palabra w, ¿podemos factorizarla en distintos factores de longitud como máximo 2?).
El artículo [3] muestra que si tanto el alfabeto como el B unido están fijos, entonces SF puede resolverse en tiempo polinómico.
El documento [2] muestra que MF es NP-completo, ¡pero solo si el alfabeto no está restringido o fijado a priori! En particular, no responde a la pregunta si el problema es NP-completo si solo consideramos las palabras de entrada sobre algún alfabeto fijo (como es habitual en casos prácticos).
el artículo [3] muestra que MF puede resolverse en tiempo polinómico si los límites de entrada B están nuevamente limitados por alguna constante, es decir, la entrada del problema es una palabra y un límite B de {1, 2, ..., K} , donde K es una constante fija.

Algunos comentarios sobre estos resultados: Wrt (1) y (2), es intuitivamente claro que si el alfabeto es binario, entonces, para dificultar el problema SF, el límite B no se puede arreglar también. Por el contrario, corregir B = 2 significa que el tamaño del alfabeto debe ser bastante grande para producir instancias difíciles. Como consecuencia, (3) es bastante trivial (de hecho, [3] dice un poco más: luego podemos resolverlo en tiempo de ejecución no solo polinomial, sino también | w | ^ 2 veces un factor que solo depende del tamaño del alfabeto y obligado B). (5) tampoco es difícil: si nuestra palabra es larga en comparación con B, entonces podemos obtener la factorización deseada simplemente dividiéndonos en factores de diferentes longitudes. Si no, podemos forzar todas las posibilidades, lo cual es exponencial solo en B, que en este caso se supone que es una constante.

Entonces, la imagen que tenemos es la siguiente: SF parece más difícil, porque tenemos dureza incluso para alfabetos fijos o para un límite fijo B. El problema MF, por otro lado, se resuelve en el tiempo polivinílico si el límite es fijo (en esto es más fácil que SF), mientras que la pregunta correspondiente es el tamaño del alfabeto abierto. Por lo tanto, MF es un poco menos complejo que SF, incluso si resulta que MF para alfabetos fijos también es NP completo. Sin embargo, si se puede demostrar que MF se puede resolver para alfabetos fijos en tiempo múltiple, entonces se muestra que MF es mucho más fácil que SF ... porque el único caso para el que es difícil es algo artificial (¡alfabeto sin límites!) .

Hice un esfuerzo para tratar de resolver el caso de MF con alfabeto limitado, pero no pude resolverlo y desde entonces dejé de trabajar en él. No creo que otros investigadores hayan intentado mucho resolverlo (por lo que este no es uno de estos problemas abiertos muy difíciles, muchas personas ya lo han intentado y fracasado; lo considero factible de alguna manera). Supongo que también es NP-hard para alfabetos fijos, pero tal vez la reducción es tan complicada que obtendrías algo como "MF es difícil para alfabetos de tamaño 35 o mayor" o algo así, que tampoco sería súper agradable .

Con respecto a la literatura adicional, conozco el artículo [4], que considera el problema de dividir una palabra w en factores distintos u_1, u_2, ..., u_k que son todos palíndromos, que también es NP completo.

Eché un vistazo rápido al papel [5], señalado por Gilad. Sin embargo, parece considerar una configuración diferente. En este artículo, los autores están interesados en la pregunta combinatoria de cuántas subsecuencias o subpalabras distintas pueden estar contenidas en una palabra determinada, pero estas pueden superponerse. Por ejemplo, aaabaab contiene 20 subpalabras diferentes a, b, aa, ab, ba, bb, aaa, aab, aba, baa, aaab, aaba, abaa, baab, aaaba, aabaa, abaab, aabaab, aaabaa, aaabaab (tal vez yo mal contado, pero entiendes la idea). Algunos de ellos tienen una sola aparición, como baa, algunos de ellos varios, como aa. En cualquier caso, la pregunta no es cómo podemos dividir la palabra de alguna manera para obtener muchos factores distintos, ya que esto significa que cada símbolo individual contribuye exactamente a un factor.

Con respecto a las soluciones prácticas para este tipo de problemas (tenga en cuenta que soy un teórico, así que tómelo con gran detalle):

Que yo sepa, no hay límites inferiores teóricos (como la dureza NP) que descartarían resolver MF en tiempo polinómico si consideramos solo las palabras de entrada sobre un alfabeto fijo. Sin embargo, hay una advertencia: si obtienes un algoritmo de poli-tiempo, ¡esto debería ejecutarse exponencialmente en el número de símbolos del alfabeto fijo (o exponencial en alguna función de eso)! De lo contrario, también sería un algoritmo de tiempo polinómico para el caso de alfabetos no acotados. Entonces, como teórico, estaría buscando tareas algorítmicas que se puedan calcular en tiempo exponencial solo si el número de símbolos y que de alguna manera ayudan a diseñar un algoritmo para MF. Por otro lado, es probable que dicho algoritmo no exista y MF también sea NP-hard en el caso del alfabeto fijo.
Si está interesado en soluciones prácticas, puede ser útil aproximar la solución. Por lo tanto, obtener la factorización que se garantiza que sea solo la mitad del óptimo en el peor de los casos no sería tan malo.
Supongo que las heurísticas que no ofrecen una relación de aproximación demostrable, pero funcionan bien en un entorno práctico también serían interesantes.
Transformar las instancias problemáticas en instancias SAT o ILP no debería ser demasiado difícil y luego podría ejecutar un SAT o ILP-Solver para incluso obtener soluciones óptimas.
Mi opinión personal es que, aunque no se sabe si el caso del alfabeto fijo de MF es NP-hard, hay suficientes conocimientos teóricos que sugieren que el problema es lo suficientemente difícil como para justificar la búsqueda de soluciones heurísticas, etc. funcionan bien en un entorno práctico.

Bibliografía:

[1] Anne Condon, Ján Manuch, Chris Thachuk: La complejidad de la partición de cuerdas. J. Algoritmos discretos 32: 24-43 (2015)

[1b] Anne Condon, Ján Manuch, Chris Thachuk: Complejidad de un problema de partición de cuerdas consciente de colisión y su relación con el diseño de Oligo para la síntesis génica. COCOON 2008: 265-275

[2] Henning Fernau, Florin Manea, Robert Mercas, Markus L. Schmid: coincidencia de patrones con variables: algoritmos rápidos y nuevos resultados de dureza. STACS 2015: 302-315

[3] Markus L. Schmid: Computación de factorizaciones de cuerdas repetitivas y sin igualdad. Theor Comput Sci. 618: 42-51 (2016)

[4] Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Kärkkäinen, Dominik Kempa, Marcin Piatkowski, Shiho Sugimoto: la factorización palindrómica diversa es NP-completa. En t. J. encontrado. Comput Sci. 29 (2): 143-164 (2018)

[5] Abraham Flaxman, Aram Wettroth Harrow, Gregory B. Sorkin: Cuerdas con muchas subsecuencias y subcadenas distintas. Electr. J. Comb. 11 (1) (2004)

Aquí hay una respuesta basada en la teoría de grafos.

Modelado
Este problema se puede modelar como un problema de conjunto independiente máximo en un gráfico de tamaño O(n²) siguiente manera:
Sea w = c_1, ..., c_n la cadena de entrada.
Sea G = (V,E) un gráfico no dirigido, construido de la siguiente manera:
V = { (a, b) such that a,b in [1, n], a <= b } . Podemos ver que el tamaño de V es n(n-1)/2 , donde cada vértice representa una subcadena de w .
Luego, para cada par de vértices (a1, b1) y (a2, b2) , construimos el borde ((a1, b1), (a2, b2)) iff
(i) [a1, b1] cruza [a2, b2] o
(ii) c_a1...c_b1 = c_a2...c_b2 .
Dicho de otro modo, construimos un borde entre dos vértices si (i) las subcadenas que representan se superponen en w o (ii) las dos subcadenas son iguales.

Entonces podemos ver por qué un conjunto independiente máximo de G proporciona la respuesta a nuestro problema.

Complejidad
En el caso general, el problema del conjunto independiente máximo (MIS) es NP-hard, con una complejidad temporal de O(1.1996^n) y en el espacio polinomial [Xiao, NamaGoshi (2017)] .
Al principio pensé que el gráfico resultante sería un gráfico cordal (sin ciclo inducido de longitud> 3), lo que habría sido muy bueno desde entonces, el problema MIS se puede resolver en tiempo lineal en esta clase de gráficos.
Pero rápidamente me di cuenta de que no es el caso, es bastante fácil encontrar ejemplos donde hay ciclos inducidos de longitud 5 y más.
En realidad, el gráfico resultante no exhibe ninguna propiedad ''agradable'' que generalmente buscamos y que permite reducir la complejidad del problema MIS a uno polinómico.
Esto es solo un límite superior en la complejidad del problema, ya que la reducción del tiempo polinomial va solo en una dirección (podemos reducir este problema al problema MIS, pero no al revés, al menos no trivialmente). Así que finalmente terminamos resolviendo este problema en O(1.1996^(n(n-1)/2)) en el peor de los casos.
Entonces, por desgracia, no pude demostrar que está en P, o que es NP completo o NP-duro. Una cosa segura es que el problema está en NP, pero supongo que esto no es una sorpresa para nadie.

Implementación
La ventaja de reducir este problema al problema MIS es que el MIS es un problema clásico, para el cual se pueden encontrar varias implementaciones, y que el problema MIS también se escribe fácilmente como un ILP.
Aquí hay una formulación ILP del problema MIS:

Objective function maximize sum(X[i], i in 1..n) Constraints: for all i in 1..n, X[i] in {0, 1} for all edge (i, j), X[i] + X[j] <= 1

En mi opinión, esa debería ser la forma más eficiente de resolver este problema (usando este modelado como un problema MIS), ya que el solucionador de ILP es increíblemente eficiente, especialmente cuando se trata de grandes instancias.

Esta es una implementación que hice usando Python3 y el solucionador GLPK . Para probarlo, necesita un solucionador de LP compatible con el formato de archivo Cplex.

from itertools import combinations def edges_from_string(w): # build vertices vertices = set((a, b) for b in range(len(w)) for a in range(b+1)) # build edges edges = {(a, b): set() for (a, b) in vertices} for (a1, b1), (a2, b2) in combinations(edges, 2): # case: substrings overlap if a1 <= a2 <= b1: edges[(a1, b1)].add((a2, b2)) if a2 <= a1 <= b2: edges[(a2, b2)].add((a1, b1)) # case: equal substrings if w[a1:b1+1] == w[a2:b2+1]: if a1 < a2: edges[(a1, b1)].add((a2, b2)) else: edges[(a2, b2)].add((a1, b1)) return edges def write_LP_from_edges(edges, filename): with open(filename, ''w'') as LP_file: LP_file.write(''Maximize Z: '') LP_file.write("/n".join([ "+X%s_%s" % (a, b) for (a, b) in edges ]) + ''/n'') LP_file.write(''/nsubject to /n'') for (a1, b1) in edges: for (a2, b2) in edges[(a1, b1)]: LP_file.write( "+X%s_%s + X%s_%s <= 1/n" % (a1, b1, a2, b2) ) LP_file.write(''/nbinary/n'') LP_file.write("/n".join([ "X%s_%s" % (a, b) for (a, b) in edges.keys() ])) LP_file.write(''/nend/n'') write_LP_from_edges(edges_from_string(''aababaa''), ''LP_file_1'') write_LP_from_edges(edges_from_string(''kzshidfiouzh''), ''LP_file_2'')

Luego puede resolverlos con el comando glpsol :
glpsol --lp LP_file_1
La aababaa se resuelve rápidamente (0.02 segundos en mi computadora portátil), pero como se esperaba, las cosas se ponen (mucho) más difíciles a medida que crece el tamaño de la cuerda ...
Este programa solo proporciona el valor numérico (y no la partición óptima), sin embargo, la partición óptima y las subcadenas correspondientes se pueden encontrar con una implementación similar, utilizando una interfaz de solucionador / python LP como pyomo

Tiempo y memoria
aababaa : 0.02 segundos, 0.4 MB, valor: 4
kzshidfiouzh : 1.4 segundos, 3.8 MB, valor: 10
aababababbababab : 60,2 segundos, 31,5 MB, valor: 8
kzshidfiouzhsdjfyu : kzshidfiouzhsdjfyu segundos, 55.7 MB, valor: 14
Tenga en cuenta que el solucionador de LP también ofrece los límites inferior y superior actuales de la solución, por lo que para el último ejemplo, podría obtener la solución real como límite inferior después de un minuto.

Aquí hay una solución, pero explota muy rápido y no está cerca de una solución eficiente. Primero divide la cadena en una lista de subcadenas únicas sin preocuparse por ordenar, luego intenta usar itertools.permutation para volver a ensamblar esas subcadenas en la cadena original, probando CADA permutación para ver si coincide con la cadena original.

import itertools as it def splitter(seq): temp = [seq] for x in range(1, len(seq)): print(seq[:x], seq[x:]) temp.append(seq[:x]) temp.append(seq[x:]) return temp if __name__ == "__main__": test = input("Enter a string: ") temp = splitter(test) copy = temp[::] condition = True for x in temp: if len(x) > 1: copy.extend(splitter(x)) copy = sorted(list(set(copy))) print(copy) count = [] for x in range(len(test)): item = it.permutations(copy, x) try: while True: temp = next(item) if "".join(list(temp)) == test: if len(temp) == len(set(temp)): count.append((len(temp), temp)) except StopIteration: print(''next permutation begin iteration'') continue print(f"All unique splits: {count}") print(f"Longest unique split : {max(count)[0]}")

Para la primera prueba obtenemos esto:

All unique splits: [(1, (''aababaa'',)), (2, (''a'', ''ababaa'')), (2, (''aa'', ''babaa'')), (2, (''aab'', ''abaa'')), (2, (''aaba'', ''baa'')), (2, (''aabab'', ''aa'')), (2, (''aababa'', ''a'')), (3, (''a'', ''ab'', ''abaa'')), (3, (''a'', ''aba'', ''baa'')), (3, (''a'', ''abab'', ''aa'')), (3, (''aa'', ''b'', ''abaa'')), (3, (''aa'', ''ba'', ''baa'')), (3, (''aa'', ''baba'', ''a'')), (3, (''aab'', ''a'', ''baa'')), (3, (''aab'', ''ab'', ''aa'')), (3, (''aab'', ''aba'', ''a'')), (3, (''aaba'', ''b'', ''aa'')), (3, (''aaba'', ''ba'', ''a'')), (4, (''a'', ''aba'', ''b'', ''aa'')), (4, (''aa'', ''b'', ''a'', ''baa'')), (4, (''aa'', ''b'', ''aba'', ''a'')), (4, (''aab'', ''a'', ''b'', ''aa''))] Longest unique split : 4

Quizás esto se pueda optimizar de alguna manera, pero eso lleva unos segundos en esta máquina.

Esto se conoce como el problema de partición de cuerdas con detección de colisión y se demuestra que se completa NP mediante una reducción de 3-SAT en un documento de Anne Condon, Ján Maňuch y Chris Thachuk - Complejidad de un problema de partición de cuerda con detección de colisión relación con el diseño del oligo para la síntesis génica ( International Computing and Combinatorics Conference , 265-275, 2008).

He intentado este problema y lo he pensado en términos o si hacer una partición en un índice dado. Entonces, esta función es recursiva y crea 2 ramas en cada índice 1. No particione en el índice i 2. Partición en el índice i.

Basado en la partición, completo un conjunto y luego devuelvo el tamaño del conjunto

def max(a,b): if a>b: return a return b def keep(last, current, inp, map): # print last # print current # print map if len(inp) == 2 : if inp[0]==inp[1]: return 1 return 2 if current >= len(inp): return len(map) // This is when we are at the start of the string. // In this case we can only do one thing not partition and thus take the entire string as a possible string. if current == last : map11 = map.copy() map11.add(inp[current:]) return keep(last, current + 1, inp, map11) map1 = map.copy(); if current != (len(inp)-1): map1.add(inp[last:current]) map2 = map.copy() return max(keep(last,current+1,inp, map2), keep(current, current+1, inp, map1)) print keep(0,0,"121", set([])) print keep(0,0,"aaaaaaa", set([])) print keep(0,0,"aba", set([])) print keep(0,0,"aababaa", set([])) print keep(0,0,"21", set([])) print keep(0,0,"22", set([]))

https://onlinegdb.com/HJynWw-iH

Mi otra answer estaba estrechamente relacionada, pero no se correspondía exactamente con este problema, dejando ambiguo si encontrar la factorización de cuerdas libre de igualdad más grande podría ser de una clase de complejidad diferente que si existe alguna factorización libre de igualdad con longitud de factor enlazado (este último siendo abordado por el documento citado).

En el documento, Coincidencia de patrones con variables: Algoritmos rápidos y nuevos resultados de dureza (Henning Fernau, Florin Manea, Robert Mercaş y Markus L. Schmid, en Proc. 32º Simposio sobre aspectos teóricos de la informática, STACS 2015, volumen 30 de Leibniz International Proceedings in Informatics (LIPIcs) , páginas 302–315, 2015), los autores muestran que es NP completo para decidir, para un número dado k y una palabra w , si w puede factorizarse en k factores distintos.

Si consideramos el comment de templatetypedef, lo que implica que podría haber una solución de tiempo polinomial para la factorización libre de igualdad más grande y sin restricciones, entonces seguramente podríamos usar dicho algoritmo para responder si pudiéramos dividir la cadena en k factores distintos (subcadenas) simplemente observando si k es menor que el máximo que ya conocemos.

Schmid (2016), sin embargo, escribe que "todavía es un problema abierto si MaxEFF-s permanece NP-completo si el alfabeto es fijo". (Cálculo de factorizaciones de cuerdas repetitivas y sin igualdad, Theoretical Computer Science Volume 618 , 7 de marzo de 2016, páginas 42-51)

Sin embargo, el tamaño máximo de factorización libre de igualdad (MaxEFF-s) todavía está parametrizado y se define como:

Instancia: una palabra w y un número m , 1 ≤ m ≤ |w| .

Pregunta: ¿Existe una factorización libre de igualdad p de w con s(p) ≥ m ? ( s(p) es el tamaño de la factorización).

Puede utilizar una función recursiva con un conjunto como segundo parámetro para realizar un seguimiento de las cadenas únicas en la ruta actual hasta el momento. Para cada recursión, repita todos los índices más 1 para dividir la cadena para una posible cadena candidata, y si la cadena candidata aún no está en el conjunto, realice una llamada recursiva con la cadena restante y el candidato agregado al conjunto Para obtener el número máximo de subcadenas únicas de la cadena restante, agregue 1 y devuelva el máximo de los máximos de las iteraciones. Devuelve 0 si la cadena dada está vacía o si todas las cadenas candidatas ya están en el conjunto:

def max_unique_substrings(s, seen=()): maximum = 0 for i in range(1, len(s) + 1): candidate = s[:i] if candidate not in seen: maximum = max(maximum, 1 + max_unique_substrings(s[i:], {candidate, *seen})) return maximum

Demostración: https://repl.it/@blhsing/PriceyScalySphere

En Python 3.8, la lógica anterior también se puede escribir con una llamada a la función max con una expresión de generador que filtra los candidatos que se han "visto" con una expresión de asignación:

def max_unique_substrings(s, seen=()): return max((1 + max_unique_substrings(s[i:], {candidate, *seen}) for i in range(1, len(s) + 1) if (candidate := s[:i]) not in seen), default=0)