Оптимизируйте список текстовых дополнений и удалений

Инструменты «Diff», используемые в системах управления исходными кодами, используют алгоритмы, которые создают минимальное редактирование, необходимое для преобразования одного куска исходного кода в другое - возможно, стоит расследовать их. Я думаю, что большинство из них основаны (в конце концов) на в этом алгоритме , но давно я прочитал на эту тему.

Я считаю, что это можно сделать значительно быстрее, чем O(n²) в среднем (скорее всего, вход можно спроектировать так, чтобы не допускать быстрого анализа). Последовательные добавления или удаления можно рассматривать как наборы. Можно анализировать по одной операции за раз, и придется выполнять некоторые условные преобразования:

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

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

Мне нравится идея создания шаблона. По моему опыту, он действительно может очистить эту грязную манипуляцию последовательностями!

Существует много решений, например, взять на изменение John Resig's (создатель jQuery):

http://ejohn.org/blog/javascript-micro-templating/

Использование атрибута видимости по умолчанию и -fvisibility = hidden должно быть дополнено -fisibility-inlines-hidden.

Вы также должны забыть о попытке скрыть экспорт stdlib, см. эту ошибку GCC .

Кроме того, если у вас есть все открытые символы в определенных заголовках, вы можете поместить их в # pragma GCC visibility push (по умолчанию) и # pragma GCC visibility pop вместо использования атрибутов. Если вы создаете межплатформенную библиотеку, посмотрите на Управление экспортированными символами общих библиотек , как унифицировать стратегию экспорта DLL Windows и DSO Linux.

Как уменьшить количество действий: Алгоритмический подход может попытаться отсортировать действия. Я думаю, что после сортировки:

1. Шанс того, что соседние действия могут быть присоединены (так показали Сванте и Петерхен), поднимется.
2. Это может привести к минимальному количеству действий, которые должны быть выполнены?

В следующем «position-number» обозначает позицию вставки или удаления текста.

Предполагается, что можно поменять местами два соседних действия (путем корректировки номеров позиций и свойство text/length этих двух действий), мы можем привести список действий в любой порядок типа. Предлагаю перенести действия удаления на передний план перечислять действий с возрастанием номера позиций. После удаления действия сложения сортируются по возрастанию номера позиций.

Следующие примеры должны продемонстрировать, почему я думаю, что можно поменять местами любые соседние действия.

Свопинг следующих действий:

  1. + 2 aaa -> taaaext
  2. - 3 1   -> taaext

приводит к одному действию:

  1. + 2 aa  -> taaext

Свопинг следующих действий:

  1. + 3 aaa -> teaaaxt
  2. + 1 bb  -> bbteaaaxt

приводит к:

  1. + 1 bb  -> bbtext
  2. + 5 aaa -> bbteaaaxt

Свопинг следующих действий:

  1. + 1 bb  -> bbtext
  2. - 2 2   -> bext

приводит к:

  1. - 1 1   -> ext
  2. + 1 b   -> bext

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

Надеюсь, что я что-то не забыл и рассмотрел все обстоятельства.

При использовании Accordion, http://jqueryui.com/demos/accordion/ jQuureUI проблемы с этими типами контуров возникнуть не должны. Если вы, однако, могли бы сделать следующее:

$(".ui-accordion-header a").click(function(){
  $(this).blur();
});

На самом деле, этот метод будет работать только с любым плагином аккордеона - просто обязательно измените селектор, чтобы нацелить ссылки, ответственные за расширение/свертывание панелей данных.

Эта информация не сохраняется.

Можно использовать уведомление SQL Trace and Event (см. соответствующую статью MSDN ) для регистрации такого рода информации самостоятельно.

У меня нет опыта работы с этими технологиями, хотя...

Предположим для простоты, что в текстах присутствуют только буквы a-z.

Инициализируйте список A со значениями a [i] = i для i = 1-N (вы сами выясните, какой большой должен быть N).

Выполните (смоделируйте) все операции с А. После анализа A найдите необходимые операции:

Найдите требуемые операции удаления, найдя отсутствующие числа в A (они образуют группы последовательных значений, одна группа обозначает одну операцию удаления).

После этого можно найти необходимые операции вставки, найдя последовательности последовательных буквы (одна последовательность - это одна операция вставки).

В примере

введите A:

1 2 3 4 5 6 7 8 9 10

Шаг 1 (+:2: ab):

1 b 2 3 4 5 6 7 8 9 10

Step2 (+:1: cde):

c d e 1 a b 2 3 4 5 6 7 8 9 10

Step3 (-:4:1):

c e a b 2 3 4 5 6 7 8 9 10

Теперь мы ищем недостающие числа для поиска удалений. В нашем примере отсутствует только одно число (а именно число 1), поэтому требуется только 1 удаление, поэтому у нас есть одна операция удаления: -:1:1 (В общем случае может отсутствовать больше номеров, каждая последовательность отсутствующих номеров представляет собой одну операцию удаления. Например, если 1, 2, 3, 5, 6, 10 - все пропущенные числа, то есть 3 операции удаления: -: 1:3, -: 2:2, -: 5:1. Помните, что после каждой операции удаления все индексы уменьшаются, необходимо сохранить общую сумму предыдущих операций удаления, чтобы вычислить индекс текущей операции удаления.)

Теперь мы ищем последовательности символов, чтобы найти операции вставки. В нашем примере существует только одна последовательность: cdeab в индексе 1, поэтому у нас есть одна операция вставки: +: 1: cdeab

Надеюсь, что это достаточно ясно.

Составьте двоичное дерево, представляющее документ до и после внесения всех изменений. Каждый узел представляет либо оригинальный текст, либо вставленный/удаленный текст; последний тип узла включает в себя как количество оригинального текста для удаления (возможно, 0), так и строку текста для вставки (возможно, пустую).

Первоначально дерево имеет только один узел - "0 до конца: исходный текст". Применяйте к нему все изменения, объединяя изменения по мере возможности. Затем пройдитесь по дереву от начала до конца, выдавая окончательный набор правок. Это гарантирует получение оптимального результата.

• Наложение вставки: Найдите подходящую точку дерева. Если она находится в середине или рядом с вставленным текстом, просто измените строку вставки текста в этот узел. В противном случае добавьте узел.

• Применение удаления: Найдите начальную и конечную точки в дереве, не похожем на вставку, удаление может охватить целый ряд существующих узлов. Измените соответственно начальную и конечную точки и убейте все узлы между ними. После этого проверьте, есть ли у вас соседние "вставленный/удаленный текст" узлы. Если да, присоединяйтесь к ним.

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

Для меня это выглядит строго O(n log n) для всех вводимых данных, если вы потрудитесь реализовать сбалансированное дерево и использовать веревки для вставленного текста. Если вы отбросите всю идею дерева и используете векторы и строки, то это O(n²), но на практике может сработать нормально.

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

Начальное состояние:

*: orig

Я сказал выше, что мы будем кэшировать количество текста в каждом поддереве. Здесь я просто ставлю * за количество байт, потому что этот узел содержит весь документ, и мы не знаем, как долго это займет. Вы можете использовать любое достаточно большое число, скажем 0x4000000000000000L.

После вставки "ab" в позиции 2:

    2: orig, 2 bytes
*: insert "ab", delete nothing
    *: orig, all the rest

После вставки "cde" в позиции 1:

        1: orig, 1 byte
    5: insert "cde", delete nothing
        1: orig, 1 byte
*: insert "ab", delete nothing
    *: orig, all the rest

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

Начните с корня. Посмотрите на первый дочерний узел: это поддерево содержит 5 символов. Значит, позиция 4 должна быть там. Перейдите к этому узлу. Посмотрите на его первый дочерний узел. На этот раз он содержит только 1 символ. Не там. Эта редакция содержит 3 символа, поэтому ее здесь тоже нет, она находится сразу после. Перейдите ко второму дочернему узлу. (Этот алгоритм - около 12 строк кода.)

После удаления 1 символа в позиции 4, получается вот это...

    4: orig, 1 byte
        3: insert "cde", delete nothing
*: insert "ab", delete nothing
    *: orig, all the rest

...а затем, заметив два соседних вставных узла, вы их объединяете. (Обратите внимание, что при наличии двух соседних узлов, один всегда находится где-то выше другого в древовидной иерархии. Объедините данные в этот вышестоящий узел; затем удалите нижний и обновите размеры кэшированных поддеревьев между ними.)

    1: orig, 1 byte
*: insert "cdeab", delete nothing
    *: orig, all the rest