Подтвердить что ты не робот

Строковый анализ

Учитывая последовательность операций:

а * Ь * а * B * A * A * B * A * B

есть способ получить оптимальное подразделение, чтобы включить повторное использование подстроки.

сделать

a * b * a * b * a * a * b * a * b = > c * a * c, где c = a * b * a * b

а затем видя, что

a * b * a * b = > d * d, где d = a * b

в целом сокращает 8 начальных операций в описанном здесь 4?

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

Целью курса является минимизация числа операций

Я рассматриваю суффикс рода.

Меня особенно интересуют линейные эвристики времени или решения. Операции "*" на самом деле являются матричными умножениями.

4b9b3361

ОТВЕТЫ

Ответ 1

Вся эта проблема называется "Common Subexpression Elimination" или CSE. Это немного меньшая версия проблемы, называемая Сокращение графика, с которой сталкивается разработчик компиляторов для языков функционального программирования. Googling "Алгоритм устранения общего подвыражения" дает множество решений, хотя я не вижу особого для ограничений, заданных матричным умножением.

Страницы, ссылки на которые содержат много ссылок.

Мой старый ответ ниже. Однако, исследуя немного больше, решение просто создает дерево суффиксов . Это можно сделать в O (N) времени (много ссылок на странице wikipedia). Сделав это, подвыражения (c, d и т.д. В вашем вопросе) являются только узлами в дереве суффиксов - просто вытащите их.

Однако, я думаю, что MarcoS находится на чем-то с предложением Самая длинная повторяющаяся подстрока, поскольку приоритет сокращения графика может не позволить оптимизировать, что может быть разрешено здесь.

эскиз алгоритма:

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

Каждый запуск самой длинной повторяющейся подстроки занимает время N. Возможно, вы снова можете использовать дерево суффиксов которое вы построите, чтобы решить все это вовремя Н.

Ответ 2

edit: Приращения роста в этом ответе необходимы в дополнение к принятому ответу для запуска умножения на CSE или матричную цепочку

Интересно, что алгоритм сжатия может быть тем, что вы хотите: алгоритм сжатия стремится уменьшить размер сжатия, и если единственный способ, которым это может сделать это замена, вы можете проследить его и получить необходимые подкомпоненты для вашего алгоритм. Это может не дать приятных результатов, хотя для небольших входов.

Какие подмножества ваших операций являются коммутативными, будет важным фактором при выборе такого алгоритма. [edit: OP говорит, что никакие операции не являются коммутативными в его/ее ситуации]

Мы также можем определить оптимальное решение, если игнорировать такие эффекты, как кеширование:

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.

Возникает вопрос, возможен ли жадный подход, а не: нужно ли сжимать повторяющиеся подстроки на каждом шаге. Это может быть не так, например,

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

Однако у меня есть подозрение, что если мы попробуем все заказы сжимать подстроки, мы, вероятно, не будем часто сталкиваться с этой проблемой.

Таким образом, записав то, что мы хотим (затраты) и рассмотрим, возможно, проблемы, у нас уже есть алгоритм грубой силы, который может это сделать, и он будет работать для очень небольшого числа матриц:

# 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

Примечание: согласно другому ответу Asgeir, это называется проблемой оптимизации умножения матрицы. Ник Фортескью отмечает, что это также известно в более общем смысле как http://en.wikipedia.org/wiki/Common_subexpression_elimination - таким образом, можно найти любой общий алгоритм/библиотеку алгоритмов/алгоритмов Matrix-Chain-Multiplication из литературы, и подключить к порядку величины, о которых я упомянул ранее (вам понадобится тот вариант, какое решение вы используете). Обратите внимание, что стоимость вышеупомянутых вычислений (умножение, возведение в степень и т.д.) Предполагает, что они выполняются эффективно с использованием современных алгоритмов; если это не так, замените экспоненты соответствующими значениями, которые соответствуют тому, как будут выполняться операции.

Ответ 3

Если вы хотите использовать наименьшие арифметические операции, вы должны взглянуть на умножение цепочки матриц, которое можно свести к O (n log п)

Ответ 4

С вершины головы проблема кажется в NP для меня. В зависимости от замещений, которые вы выполняете, другие подстановки будут возможны или невозможны, например, для строки d*e*a*b*c*d*e*a*b*c*d*e*a существует несколько возможностей.

Если вы берете самую длинную общую строку, это будет: f = d*e*a*b*c, и вы можете заменить f*f*e*a, оставив вам три умножения в конце и четыре промежуточных (всего семь).

Если вы вместо этого замените следующий способ: f = d*e*a вы получаете f*b*c*f*b*c*f, который вы можете дополнительно заменить с помощью g = f*b*c на g*g*f для всего шести умножений.

В этой задаче возможны и другие возможные замены, но у меня нет времени, чтобы подсчитать их все прямо сейчас.

Я предполагаю, что для полной минимальной подстановки необходимо не только найти самую длинную общую подстроку, но и количество повторений каждой подстроки, что, вероятно, означает, что вы должны отслеживать все подстановки до сих пор и делать обратный поиск. Тем не менее это может быть быстрее, чем фактические умножения.