algorithm - array - suffix tree c++

Análisis de cadena

Question

Dada una secuencia de operaciones:

a * b * a * b * a * a * b * a * b

¿Hay alguna manera de obtener la subdivisión óptima para permitir el deshecho de la subcadena?

fabricación

a * b * a * b * a * a * b * a * b => c * a * c, donde c = a * b * a * b

y luego viendo eso

a * b * a * b => d * d, donde d = a * b

en general reduciendo las 8 operaciones iniciales a las 4 descritas aquí?

(c = (d = a * b) * d) * a * c

El objetivo, por supuesto, es minimizar el número de operaciones

Estoy considerando una especie de suffixtree.

Estoy especialmente interesado en soluciones o heurísticas de tiempo lineal. Las operaciones ''*'' son en realidad multiplicaciones de matrices.

Answer 1

¿No es este el problema de subcadena repetida más larga ?

Answer 2

Desde la parte superior de la cabeza el problema parece en NP para mí. Dependiendo de las sustituciones que esté haciendo, otras substiciones serán posibles o imposibles, por ejemplo, para la cadena d*e*a*b*c*d*e*a*b*c*d*e*a hay varias posibilidades.

Si tomas la cadena común más larga, será: f = d*e*a*b*c y podrías sustituir f*f*e*a dejándote tres multiplicaciones al final y cuatro intermedias (siete en total).

Si, por el contrario, lo sustituyese de la siguiente manera: f = d*e*a obtienes f*b*c*f*b*c*f que puedes sustituir con g = f*b*c a g*g*f un total de seis multiplicaciones.

Hay otras posibles sustituciones en este problema, pero no tengo tiempo para contarlas todas ahora.

Supongo que para una sustitución mínima completa no solo es necesario averiguar la subcadena común más larga sino también la cantidad de veces que se repite cada subcadena, lo que probablemente signifique que tienes que rastrear todas las sustituciones hasta el momento y realizar un retroceso. Aún así podría ser más rápido que las multiplicaciones reales.

Answer 3

Si quiere usar la menor cantidad de operaciones aritméticas, debería echarle un vistazo a la multiplicación de la cadena de matrices, que puede reducirse a O (n log n)

Answer 4

Todo este problema se conoce como "eliminación de subexpresión común" o CSE . Es una versión ligeramente más pequeña del problema llamado " Reducción de gráficos " que enfrenta el implementador de compiladores para lenguajes de programación funcionales. Buscar en Google el "Algoritmo de eliminación de subexpresión común" ofrece muchas soluciones, aunque ninguna que pueda ver especialmente para las restricciones dadas por la multiplicación de matrices.

Las páginas vinculadas dan muchas referencias.

Mi respuesta anterior está abajo. Sin embargo, habiendo investigado un poco más, la solución es simplemente construir un árbol de sufijos . Esto se puede hacer en el tiempo O (N) (muchas referencias en la página wikipedia). Una vez hecho esto, las subexpresiones (c, d, etc. en su pregunta) son solo nodos en el árbol de sufijos; simplemente extráigalos.

Sin embargo, creo que MarcoS está trabajando en algo con la sugerencia de la subcadena de repetición más larga , ya que la precedencia de reducción de gráficos podría no permitir las optimizaciones que se pueden permitir aquí.

bosquejo del algoritmo:

optimise(s):
    let sub = longestRepeatingSubstring(s).
    optimisedSub = optimise(sub)
    return s with sub replaced by optimisedSub

Cada ejecución de la subcadena repetitiva más larga lleva tiempo N. Probablemente pueda volver a utilizar el árbol de sufijos que construye para resolver todo el asunto a tiempo N.

Answer 5

editar: las órdenes de crecimiento en esta respuesta son necesarias además de la respuesta aceptada para ejecutar CSE o multiplicación de cadenas de matrices

Curiosamente, un algoritmo de compresión puede ser lo que usted quiere: un algoritmo de compresión busca reducir el tamaño de lo que está comprimiendo, y si la única forma en que puede hacerlo es la sustitución, puede rastrearlo y obtener los subcomponentes necesarios para su algoritmo. Esto puede no dar buenos resultados, aunque para pequeñas entradas.

Qué subconjuntos de sus operaciones son conmutativos será una consideración importante al elegir dicho algoritmo. [Editar: OP dice que ninguna operación es conmutativa en su situación]

También podemos definir una solución óptima, si ignoramos los efectos como el almacenamiento en caché:

input: [some product of matrices to compute]

given that multiplying two NxN matrices is O(N^2.376)
given we can visualize the product as follows:
    [[AxB][BxC][CxD][DxE]...]
we must for example perform O(max(A,B,C)^2.376) or so operations in order to combine
    [AxB][BxC] -> [AxC]

The max(...) is an estimate based on how fast it is to multiply two square matrices;
a better estimate of cost(A,B,C) for multiplying an AxB * BxC matrix can be gotten 
from actually looking at the algorithm, or running benchmarks if you don''t know the
algorithm used.

However note that multiplying the same matrix with itself, i.e. calculating
a power, can be much more efficient, and we also need to take that into account.
At worst, it takes log_2(power) multiplies each of O(N^2.376), but this could be
made more efficient by diagonalizing the matrix first.

Existe la pregunta sobre si un enfoque codicioso es factible: si uno DEBERÍA comprimir subcadenas repetitivas en cada paso. Este puede no ser el caso, por ejemplo

aaaaabaab
compressing ''aa'' results in ccabcb and compressing ''aab'' is now impossible

Sin embargo, tengo la corazonada de que, si probamos todas las órdenes de subcadenas de compresión, probablemente no nos topemos con este problema con demasiada frecuencia.

Por lo tanto, habiendo escrito lo que queremos (los costos) y considerado posibles problemas, ya tenemos un algoritmo de fuerza bruta que puede hacer esto, y se ejecutará para un número muy pequeño de matrices:

# pseudocode

def compress(problem, substring)
    x = new Problem(problem)
    x.string.replaceall(substring, newsymbol)
    x.subcomputations += Subcomputation(newsymbol=substring)

def bestCompression(problem)
    candidateCompressions = [compress(problem,substring) for each substring in problem.string]
    # etc., recursively return problem with minimum cost
    # dynamic programming may help make this more efficient, but one must watch
    #   out for the note above, how it may be hard to be greedy

Nota: de acuerdo con otra respuesta de Asgeir, esto se conoce como el problema de optimización de multiplicación de cadena de Matrix. Nick Fortescue señala que esto también se conoce de manera más general como http://en.wikipedia.org/wiki/Common_subexpression_elimination , por lo que uno podría encontrar cualquier algoritmo / biblioteca genérica CSE o Matrix-Chain-Multiplication de la literatura, y conectar el costo Órdenes de magnitud que mencioné anteriormente (necesitará aquellos que nombró qué solución usa). Tenga en cuenta que el costo de los cálculos anteriores (multiplicación, exponenciación, etc.) supone que se están realizando de manera eficiente con algoritmos de última generación; si este no es el caso, reemplace los exponentes con los valores apropiados que correspondan a la forma en que se llevarán a cabo las operaciones.