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

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

Посмотрите на алгоритм сжатия Лемпеля-Зива-Уэльса . Он основан на обнаружении повторений в строках и использовании их для сжатия. Я считаю, что вы можете использовать Trie за это.

Answer 2

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

Answer 3

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

Answer 4

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