Безрисковая иерархическая длина пробега

Ответ 1

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

Вы можете вставить следующий код в LINQPad и запустить его, и он должен произвести следующий вывод:

ABCBCABCBCDEEF = (2A(2BC))D(2E)F
ABBABBABBABA = (3A(2B))ABA
ABCDABCDCDCDCD = (2ABCD)(3CD)

Как вы можете видеть, средний пример закодировал ABB как A(2B) вместо ABB, вам нужно было бы сделать это суждение самостоятельно, если последовательности с одним символом должны быть закодированы как повторяющийся символ или нет, или если необходимо использовать определенный порог (например, 3 или более).

В основном код работает следующим образом:

• Для каждой позиции в последовательности попытайтесь найти самое длинное совпадение (на самом деле это не так, оно принимает первое совпадение 2+, которое оно находит, я оставил остальное как упражнение для вас, так как я должен покинуть свой компьютер в течение нескольких часов)
• Затем он пытается закодировать эту последовательность, ту, которая повторяется, рекурсивно и выплескивает объект типа X * seq
• Если он не может найти повторяющуюся последовательность, он выплескивает единственный символ в этом месте
• Затем он пропускает кодировку и продолжает С# 1

В любом случае, здесь код:

void Main()
{
    string[] examples = new[]
    {
        "ABCBCABCBCDEEF",
        "ABBABBABBABA",
        "ABCDABCDCDCDCD",
    };

    foreach (string example in examples)
    {
        StringBuilder sb = new StringBuilder();
        foreach (var r in Encode(example))
            sb.Append(r.ToString());
        Debug.WriteLine(example + " = " + sb.ToString());
    }
}

public static IEnumerable<Repeat<T>> Encode<T>(IEnumerable<T> values)
{
    return Encode<T>(values, EqualityComparer<T>.Default);
}

public static IEnumerable<Repeat<T>> Encode<T>(IEnumerable<T> values, IEqualityComparer<T> comparer)
{
    List<T> sequence = new List<T>(values);

    int index = 0;
    while (index < sequence.Count)
    {
        var bestSequence = FindBestSequence<T>(sequence, index, comparer);
        if (bestSequence == null || bestSequence.Length < 1)
            throw new InvalidOperationException("Unable to find sequence at position " + index);

        yield return bestSequence;
        index += bestSequence.Length;
    }
}

private static Repeat<T> FindBestSequence<T>(IList<T> sequence, int startIndex, IEqualityComparer<T> comparer)
{
    int sequenceLength = 1;
    while (startIndex + sequenceLength * 2 <= sequence.Count)
    {
        if (comparer.Equals(sequence[startIndex], sequence[startIndex + sequenceLength]))
        {
            bool atLeast2Repeats = true;
            for (int index = 0; index < sequenceLength; index++)
            {
                if (!comparer.Equals(sequence[startIndex + index], sequence[startIndex + sequenceLength + index]))
                {
                    atLeast2Repeats = false;
                    break;
                }
            }
            if (atLeast2Repeats)
            {
                int count = 2;
                while (startIndex + sequenceLength * (count + 1) <= sequence.Count)
                {
                    bool anotherRepeat = true;
                    for (int index = 0; index < sequenceLength; index++)
                    {
                        if (!comparer.Equals(sequence[startIndex + index], sequence[startIndex + sequenceLength * count + index]))
                        {
                            anotherRepeat = false;
                            break;
                        }
                    }
                    if (anotherRepeat)
                        count++;
                    else
                        break;
                }

                List<T> oneSequence = Enumerable.Range(0, sequenceLength).Select(i => sequence[startIndex + i]).ToList();
                var repeatedSequence = Encode<T>(oneSequence, comparer).ToArray();
                return new SequenceRepeat<T>(count, repeatedSequence);
            }
        }

        sequenceLength++;
    }

    // fall back, we could not find anything that repeated at all
    return new SingleSymbol<T>(sequence[startIndex]);
}

public abstract class Repeat<T>
{
    public int Count { get; private set; }

    protected Repeat(int count)
    {
        Count = count;
    }

    public abstract int Length
    {
        get;
    }
}

public class SingleSymbol<T> : Repeat<T>
{
    public T Value { get; private set; }

    public SingleSymbol(T value)
        : base(1)
    {
        Value = value;
    }

    public override string ToString()
    {
        return string.Format("{0}", Value);
    }

    public override int Length
    {
        get
        {
            return Count;
        }
    }
}

public class SequenceRepeat<T> : Repeat<T>
{
    public Repeat<T>[] Values { get; private set; }

    public SequenceRepeat(int count, Repeat<T>[] values)
        : base(count)
    {
        Values = values;
    }

    public override string ToString()
    {
        return string.Format("({0}{1})", Count, string.Join("", Values.Select(v => v.ToString())));
    }

    public override int Length
    {
        get
        {
            int oneLength = 0;
            foreach (var value in Values)
                oneLength += value.Length;
            return Count * oneLength;
        }
    }
}

public class GroupRepeat<T> : Repeat<T>
{
    public Repeat<T> Group { get; private set; }

    public GroupRepeat(int count, Repeat<T> group)
        : base(count)
    {
        Group = group;
    }

    public override string ToString()
    {
        return string.Format("({0}{1})", Count, Group);
    }

    public override int Length
    {
        get
        {
            return Count * Group.Length;
        }
    }
}

Ответ 2

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

ABCBCABCBCDEEF
s->ttDuuF
t->Avv
v->BC
u->E

ABABCDABABCD
s->ABtt
t->ABCD

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

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