Как вы обнаруживаете повторения в списке строк?

Question

У меня есть последовательность SQL-вызовов, которые я хочу использовать для обнаружения циклов (и, следовательно, ненужных дублирующих вызовов sql), но мне стало интересно, что это более общая проблема.

Учитывая список, скажем [a,b,c,b,c,a,b,c,b,c,a,b,b]

Есть ли какой-то способ, которым я могу превратить это в a,[[b,c]*2,a]*2,b*2

или [a,[b,c]*2]*2,a,b*2

То есть, обнаружить повторы (возможно, вложенных из них).

Answer 1

Посмотрите на Lempel-Ziv-Welsh compression algorithm. Он построен на обнаружении повторений в строках и использовании их для сжатия. Я считаю, что вы можете использовать Trie .

Answer 2

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

Answer 3

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

Answer 4

Если строка достаточно большая, интересный подход заключается в том, чтобы запустить на нем инструмент сжатия (например, gzip, bzip или 7zip). Эти инструменты работают путем поиска повторений (на разных уровнях) и подстановки их указателями на первый экземпляр текста (или словаря). Сжатие, которое вы достигаете, является мерой повторения. Сбрасывая файл (вы должны будете написать код для этого), вы получите повторный контент.