Алгоритмы. Определение последовательности на сырых данных, или восстановление после аварии
Представим что вы имеете доступ к образовательному ресурсу, где есть каталог курсов и уроков. В какой-то момент вы теряете часть данного каталога и у вас есть только ID единиц контента, наименование урока, а нумерации нет — повреждена таблица. Пишем свой велосипед.
Задача
Восстановить данные — задача №0, построить алгоритм, который поможет собирать последовательность таких уроков в любой момент, даже если автор урока не указал его нумерацию вовремя (такое бывает).
На выходе нужно получить такую таблицу (восстановив данные в колонках Курс и Урок)
wID | Курс | Урок | Наименование |
34f5d3 | 1 | 1 | Бла |
462g6g | 1 | 2 | Бла Бла го |
f63f | … | N | Бла Бла Бла |
wectwa | 2 | 1 | го |
6vva | 2 | 2 | го го Бла |
d35y34 | 2 | … | го го |
wrywyr | 2 | M | Бла Бла |
В теории все просто, вот только курсов море, уроков много, и восстановить нужно 1000+ записей.
Рассмотрели варианты, какие дополнительные данные могут нам помочь для решения задачи. На момент восстановления остался только log nginx в котором можно было бы найти знания о том, какие пользователи (по cookies) в какое время смотрели уроки.
Как решали задачу
Базовый вариант — анализ логов и построение последовательности на основе этих данных. Критическое ограничение — лог только за крайние 30 дней. Даже если учесть тот факт, что уроки должны пользователи смотреть последовательно, то из лога мы могли получить временной ряд: datadate, user, wid
Полный список ограничений:
лог за 30 дней
часть пользователей смотрели уроки рандомно, таких около 5%
статистика по первому курсу бедная так как эти уроки в текущем месяце смотрело меньше людей, так как пик просмотров по ним был 2 месяца назад и этого лога нет
в самих уроках нет указания номера, просто видео файл
бекапа нет (это для текущего кейса на хабре, так интереснее)
Варианты решений для рассмотрения
Статистика. посмотреть частотность ID уроков в логе, гипотеза — более старые уроки должны иметь max частотность так как все начинают с 1 курса и 1 урока и далее. Разочарование — данных мало и самая высокая частотность у уроков, по которым в этом месяце был набор слушателей и более активная реклама
Логика. построить последовательность по логам, найти пользователя который просмотрел все уроки и на основе этих данных принять как данное что это корректное решение, отсортировав лог по времени. Разочарование — нет пользователей которые прошли все уроки. Более того часть пользователей в середине курса могли возвращаться к прежним более старым урокам и потом опять смотреть новое
Дерево. Давайте представим что урок это точка в пространстве дерева, а лучи между ними — это как раз максимально частотные переходы пользователей от урока А до урока Б потом В и т.д. Далее строим корректный путь между точками. Разочарование — собранная частотность не позволяла создать дерево, результат был похож на мусор
Опечаточник. Представим, что один пользователь должен был посмотреть такую последовательность уроков А, B, C, D, E, F, J, а по факту смотрел так А, B, C, E, D, F. Гипотеза, давайте представим что это не отдельные «буквы», а слово «abcedf» написанное с ошибкой. Разделим его на триграммы или биграммы и далее попробуем исправить опечатку, основываясь на статистике биграмм всех юзеров из лога. Разочарование — мало пользователей, которые смотрели более 60% уроков
Вариант который сработал
Гипотеза — даже если есть много пользователей которые смотрели не все уроки, но подавляющее большинство скорее всего смотрели уроки в правильной последовательности. Исключаем тех, кто смотрел часть уроков рандомно т.е. несколько раз за все время. Исключаем тех, кто смотрел только первые N минут видео, возможно это были случайные просмотры или пользователь произвольно выбирал урок или …
Собираем частотность пар, что в последовательности урок А, далее урок В смотрело N юзеров. Урок В далее С — смотрело Y и т.д. Не анализируем пары с минимальной частотностью.
Сортируем пары в порядке убывания частотности, проверяем. Увы мах частотность имеют пары уроков этого курса, который был запланирован в данном месяце, а первый курс опять где-то мимо. Предварительный результат следующий:
последовательность уроков внутри курса собрать получилось
последовательность всех уроков — нет, так как смешиваются уроки разных курсов
выделяем потенциальные группы уроков, которые могут стать курсами, далее нужно понять какой это курс
перебирая список, смотрим частотность внутри предварительного результата, сравнивая пары последовательных ID в этом списке (пара = строка n и строка n+1) . Если попадается пара у которой частотность отсутствует или минимальная, то для ID которая была n+1 присваиваем n+2 (опускаем в этом списке ниже). Если частотность выше среднего, оставляем и идем далее, сравнивая ID которая в списке под номером n+1 со строкой n+2 и т.д.
Отталкиваемся от логики, что пользователь который смотрел 2 урок из 1 курса скорее всего будет смотреть далее 3 урок из 1 курса, а не 7 урок из 2 курса, даже если частотности этих ID в списке стоят рядом.
Результат — обработано 238710 пар уроков, по данным от 3461 пользователя (на основе лога). Время формирование списка пар ~9 сек, время формирование корректной очереди менее 1.7 сек. В качестве проверки результата был взят лог с частью не поврежденного каталога уроков -100% попадание.
Задача поста на хабре — получить от вас идеи как вы бы решали эту задачу?
