Friday, July 29, 2011

Topcoder. String compression.

В прошлый раз, я писал о своем желании провести детальный разбор решений лучших участников топкодера с целью постичь их тайное дао и примкнуть к их рядам. Итак отчитываюсь.
Первым делом я решил разобрать решение победителя последнего онлайн тура Topcoder Open 2011, участника из Китая, с ником ACRush. Его решение было написано на C++ и состояло из более чем 1800 строк кода. Для того чтобы это переварить, я решил переписать его решение на Java.

Для тех кто не в курсе, расскажу условия задачи. На вход вам давалась некая строка, длинной до 100000 символов. Вам нужно было её сжать, представив в виде нескольких строк вида:

1: abc2a3sd4
2: qwelwesdfdf
3: erwe2rew4dfds
4: qweqwe2dferw

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

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

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

Более точно условие задачи можно прочитать тут.



В марафона часто возникают задачи, в которых собственный результат можно оценить. В таких задачах, методика перебора нескольких способов решения и выбора лучшего, очень распространена среди лидеров. И решение ACRush не стало исключением. Я бы выделил в его решении 5 основных подходов.

Итак, решение.


Важный момент о решении, который следовало бы сразу заметить:

Нам важно правильно расставить цифры. Если цифры расставлены правильно, то нет ничего сложного в том, чтобы определить оптимальную комбинацию букв. Достаточно просто развернуть сжатое представление, сравнить с исходной строкой и посчитать какая буква и сколько раз попадает в ту или иную позицию в сжатом представлении. После чего, для каждой позиции, выбрать наиболее часто встречаемую букву. Это, вроде бы, простое умозаключение пришло в мою голову лишь на третий или четвертый день. В решении ACRush оно использовалось повсеместно.

Первый подход. Жадный алгоритм.


Этот алгоритм дает минимальное решение для любых начальных данных. По сути, мы перебираем строки вида:

xxxxxxxxx1
xxxxxxx2
xxxxx333333
xxxxxxxxxx

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

Второй подход. Поиск в глубину.


Этот подход дает идеальное решение для случаев когда процент ошибок в исходной строке мал. Он основан на том, что мы ищем наиболее вероятных кандидатов исходя из частоты вхождений символов. Идея простая, если посмотреть на мой самый первый пример, то понятно, что в разжатой строке чаще всего будет встречаться подстрока номер 2: qwelwesdfdf
И это свойство можно применить для поиска строк, использовавшихся для генерации. В своем решении, я сначала искал подстроки по частотам одного символа. Но точность этого подхода стремительно падала с увеличением ошибки. Потом, я стал искать на основе частот парных комбинаций символов. ACRush пошел еще на шаг дальше и искал наиболее часто встречаемые тройки последовательных символов. Таким образом, на каждом шаге поиска в глубину он выбирал подстроки из исходной, в которых тройки последовательных символов (триплеты) встречаются наиболее часто. Таких подстрок он выбирал сотню штук и для каждой из них оценивал, какое количество очков она даст, если ей воспользоваться (исходя из предполагаемого процента ошибки). Выбирал ту, которая дает максимальное количество очков и шел на следующий цикл поиска в глубину.

Для коротких исходных строк ( < 500 символов) частоты триплетов не считались, просто перебирались все возможные подстроки и для них считалось максимально возможное количество очков.

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

Третий подход. Динамическое программирование.


Здесь, на вход нам подавались частичные решения найденные на предыдущих этапах. Частичные они были в том смысле, что мы могли найти, скажем, 2 или 3 предполагаемых строки из четырех. Поиск в глубину, во втором подходе, идет снизу вверх, т.е. из нашего примера мы сначала ищем строку № 2, выполняем замену, потом ищем строку № 4 и т.д. Слабым местом такого подхода является как раз замена. Ведь мы не знаем процент ошибки в данном конкретном месте строки. Можно, конечно, брать ошибку с запасом, но увеличение ошибки приводит к ложным срабатываниям. Таким образом лучше всего было бы, перебрать все возможные варианты расстановки и выбрать из них оптимальный.
Это и реализовал ACRush использовав динамическое программирование. Все это проводилось для сотни наилучших частичных решений найденных к этому моменту.

Четвертый и пятый подходы.


По моим ощущениям, 99% успеха являются результатом второго и третьего подхода. Однако, видимо для того чтобы совсем добить конкурентов, в решении было реализовано еще два подхода. Случайное блуждание и метод грубой силы.
Для случайного блуждания выбиралось наилучшее имеющееся решение и проводились всевозможные замены цифр в каждой из строк (я уже говорил, что расстановка цифр однозначно определяет максимальное количество очков).
Метод грубой силы выполнялся все оставшееся время решения. Заключался он в том, чтобы перебрать все возможные порядки строк и все возможные расстановки цифр, до тех пор пока время не кончится.


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

No comments:

Post a Comment