Обнаружения повторяющихся групп линий

Question

Я получил несколько мегабайт данных, как это:

11 2 1 
4 3 1 
11 2 1 
4 3 1 
11 2 1 
4 3 1 
18 3 2 

Я хотел бы, чтобы сжать его, добавив строки, говоря «предыдущие п строк повторяются т раз.» Алгоритм должен читать строки и задерживать их распечатку до нахождения максимально возможного m * n, но может принимать n < = 10. Какой был бы лучший способ сделать это?

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

Answer 1

«копировать предыдущие n строк, повторенных m раз» - это ограниченная версия «copy k lines, начиная с j строк назад». Первый - второй с k = n * m и j = n. Более общая версия k, j - LZ77. (Хотя обычно это байты, а не линии.)

Алгоритмы LZ77 будут работать очень хорошо для этого. Подход хэш-таблицы, используемый gzip, zlib и т. Д., Быстро и легко кодируется. Сначала определите минимальное значение k (норка), которое вы считаете целесообразным, и определите, как далеко назад вы хотите искать совпадения, т. Е. Максимальное значение j (maxj). Затем постройте скользящее окно для линий maxj для поиска.

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

Используйте lazy-matching, где вы откладываете эмиссию матча, пока не обработает следующую строку, что может привести к более длинному совпадению.

Answer 2

zip-алгоритмы могут сохранять читаемые данные. Они просто создают словари повторяющихся элементов (например, посмотрите на lempel - ziv). Я думаю, что алгоритм, как вы его описываете, может быть проблематичным. Ваша вторая строка отличается от вашей первой строки, так как вы узнаете, что вы должны рассматривать их как одну группу? когда вы ограничите группу и запустите новую?
Как вы можете сказать, что

11 2 1 
4 3 1 

действительно принадлежит к той же группе?

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

11 2 1 
4 3 1 
11 2 1 

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

key   : count 
11 2 1  : 3 
4 3 1  : 3 
11 2 1, 4 3 1: 3 
18 3 2  : 1 

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

Answer 3

Если вы думаете о файле, как долго строка, то я думаю, что ваша проблема заключается в нахождении longest repeated substring