Введение в нормализацию данных

Итак, моё решение 😏 Идея у меня была простая: я решил группировать записи по емэйлам, но сделать это при помощи стандартных операторов = и LIKE невозможно. Можно попробовать зайти со стороны регулярных выражений, но я не пробовал, на мой взгляд это было бы чрезвычайно сложно и малоэффективно. Я решил использовать функцию Левенштейна. Если в общих чертах, то она возвращает число, которое обозначает количество операций, которое надо выполнить, чтобы сделать две строки полностью одинаковыми. Например, у нас есть строки banana1 и ban2ana. Чтобы сделать их одинаковыми, нужно во вторую строку добавить символ 1 и удалить символ 2, а это два действия. Соответственно, расстояние Левенштейна между данными строками будет 2. По умолчанию в Postgres отсутствует функция Левенштейна, но её можно подключить с расширением fuzzystrmatch:

CREATE EXTENSION IF NOT EXISTS "fuzzystrmatch";

Теперь вы можете использовать функцию levenshtein:

-- Данный запрос возвращает 2
SELECT levenshtein('banana1', 'ban2ana');

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

Реализация функции Левенштейна описана вот здесь при помощи псевдокода. Если хотите сами переписать её в виде функции для Postgres, то не берите самую первую реализацию, она очень медленная, для моего запроса не подошла (но у меня не самый эффективный запрос). Реализация функции Левенштейна:

CREATE OR REPLACE FUNCTION get_levenshtein_distance(a TEXT, b TEXT)
    RETURNS INTEGER
    LANGUAGE plpgsql
    IMMUTABLE STRICT
AS
$$
DECLARE
    a_length  INT := LENGTH(a);
    b_length  INT := LENGTH(b);
    indicator INT;
    distance  INT[][];
BEGIN
    distance := (SELECT ARRAY_FILL(0, ARRAY [a_length + 1,b_length + 1])::INT[][]);

    FOR i IN 0..a_length
        LOOP
            distance[i + 1][1] := i;
        END LOOP;

    FOR j IN 0..b_length
        LOOP
            distance[1][j + 1] := j;
        END LOOP;

    FOR j IN 1..b_length
        LOOP
            FOR i IN 1..a_length
                LOOP
                    IF SUBSTRING(a FROM i + 1 FOR 1) = SUBSTRING(b FROM j + 1 FOR 1) THEN
                        indicator := 0;
                    ELSE
                        indicator := 1;
                    END IF;

                    distance[i + 1][j + 1] := LEAST(distance[i][j + 1] + 1,
                                                    distance[i + 1][j] + 1,
                                                    distance[i][j] + indicator);
                END LOOP;
        END LOOP;

    RETURN distance[a_length][b_length];
END;
$$;

На этом же сайте я нашёл способ ускорения функции:

CREATE OR REPLACE FUNCTION get_levenshtein_distance_faster(a TEXT, b TEXT)
    RETURNS INTEGER
    LANGUAGE plpgsql
    IMMUTABLE STRICT
AS
$$
DECLARE
    common_prefix_length INTEGER := 0;
    common_suffix_length INTEGER := 0;
    a_length             INTEGER := LENGTH(a);
    b_length             INTEGER := LENGTH(b);
    reversed_a           TEXT;
    reversed_b           TEXT;
    tmp                  TEXT;
BEGIN

    FOR i IN 1..LEAST(a_length, b_length)
        LOOP
            IF SUBSTRING(a FROM i FOR 1) = SUBSTRING(b FROM i FOR 1) THEN
                common_prefix_length := common_prefix_length + 1;
            ELSE
                EXIT;
            END IF;
        END LOOP;

    a := SUBSTRING(a FROM common_prefix_length + 1);
    b := SUBSTRING(b FROM common_prefix_length + 1);
    a_length := LENGTH(a);
    b_length := LENGTH(b);

    reversed_a := REVERSE(a);
    reversed_b := REVERSE(b);
    FOR i IN 1..LEAST(a_length, b_length)
        LOOP
            IF SUBSTRING(reversed_a FROM i FOR 1) = SUBSTRING(reversed_b FROM i FOR 1) THEN
                common_suffix_length := common_suffix_length + 1;
            ELSE
                EXIT;
            END IF;
        END LOOP;

    a := SUBSTRING(a FROM 1 FOR a_length - common_suffix_length);
    b := SUBSTRING(b FROM 1 FOR b_length - common_suffix_length);
    a_length := LENGTH(a);
    b_length := LENGTH(b);


    IF a_length = 0 THEN
        RETURN b_length;
    END IF;

    IF b_length = 0 THEN
        RETURN a_length;
    END IF;

    IF b_length > a_length THEN
        tmp := a;
        a := b;
        b := tmp;
    END IF;

    RETURN get_levenshtein_distance(a, b);
END;
$$;

Функция get_levenshtein_distance_faster использует функцию get_levenshtein_distance, сокращая сравниваемые строки и пытаясь выполнить быстрое сравнение без вызова главной функции.

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

CREATE OR REPLACE FUNCTION is_similar(email_1 TEXT, email_2 TEXT)
    RETURNS BOOLEAN
    LANGUAGE plpgsql
    IMMUTABLE STRICT
AS
$$
BEGIN
    RETURN (SELECT (CAST(get_levenshtein_distance_faster(email_1, email_2) AS DECIMAL)
                        / (LENGTH(email_1) + LENGTH(email_2)) / 2 * 100) <= 8);
END;
$$;

Во-первых, почему я создаю plpgsql, а не sql функцию? Потому что иначе ругается валидатор. Что происходит в данной функции? 1. Получаем расстояние Левенштейна между двумя строками и конвертируем его в вещественное число, чтобы при дальнейших операциях не терялась дробная часть. 2. В правой части выражения из длин двух строк мы получаем среднюю длину строки. 3. Расстояние Левенштейна делится на среднюю длину строки и умножается на 100. Так мы получаем коэффициент, который демонстрирует относительную разницу между строками. 4. Проверяем, что вычисленный коэффициент не больше 8.

Где я нашёл формулу для вычисления коэффициента и откуда взял число 8? Просто взял из головы 🙂 Мы не можем ориентироваться только на расстояние Левенштейна, потому что, будучи одним и тем же для строк разной длины оно обозначает разные вещи. Например, расстояние Левенштейна между строками abc и ade, как и между строками banana1 и ban2ana составляет 2. Но в первом случае строки отличаются очень сильно, а во втором случае они отличаются слабо. Поэтому, в моей формуле также используется длина строк, чтобы вычислять не абсолютную, а относительную схожесть. Что касается числа 8, то это то число, которое подходило для значений в задаче. То есть, в рамках задачи я группировал записи по емэйлам студентов. Если использовать число больше 8, то в группировку будут попадать чужие емэйлы. А если задать слишком маленькое число, то в группировку не попадут емэйлы, которые должны были попасть.

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

Итак, настало время основного запроса. НЕ ЧИТАЙТЕ ДАННЫЙ КОММЕНТАРИЙ, ЕСЛИ ХОТИТЕ РЕШИТЬ ЗАДАЧУ САМОСТОЯТЕЛЬНО!

WITH RECURSIVE chain AS (SELECT DISTINCT scd.student_email             AS email,
                                         scd.student_name              AS name,
                                         TRIM(LOWER(scd.course_title)) AS counted_courses,
                                         1                             AS courses_count
                         FROM student_course_data AS scd
                         WHERE (scd.student_email, scd.student_name, scd.course_title) IN
                               (SELECT DISTINCT iscd.student_email, iscd.student_name, iscd.course_title
                                FROM student_course_data AS iscd
                                WHERE is_similar(iscd.student_email, scd.student_email)
                                ORDER BY iscd.student_email, iscd.student_name, iscd.course_title
                                LIMIT 1)

                         UNION

                         SELECT c.email                                                       AS email,
                                c.name                                                        AS name,
                                CONCAT(c.counted_courses, '|', TRIM(LOWER(scd.course_title))) AS counted_courses,
                                c.courses_count + 1                                           AS courses_count
                         FROM student_course_data AS scd
                                  INNER JOIN chain AS c ON is_similar(scd.student_email, c.email)
                             AND c.counted_courses NOT LIKE CONCAT('%', TRIM(LOWER(scd.course_title)), '%'))
SELECT name, MAX(courses_count)
FROM chain
GROUP BY email, name;

В данном запросе есть три части: 1. Стартовая часть (до UNION). 2. Рекурсивная часть (после UNION). 3. Запрос, который выводит полученные данные в приемлемом виде. Подробнее про рекурсивные запросы рекомендую почитать вот здесь. Основная идея здесь следующая. В стартовой части я получаю уникальных студентов. Как я это делаю? Я нахожу все записи со схожими емэйлами, сортирую и использую самую первую. В рекурсивной части я на основании схожести емэйла присоединяю к стартовым данным новые записи, но при этом избегаю присоединения тех записей, который уже были обработаны (данная логика у меня реализована при помощи поля counted_courses). В целом, это всё. Задача определённо слишком сложная для данного уровня, но попробуйте решить и поделитесь своим решением, мне очень интересно 😉

Вот мое решение. Я пошел через создание временной таблицы, куда записал только нужные мне данные - имена студентов и названия курсов чего и просили в задаче. Имена студентов кейсил черещ LIKE '%surname%', а название курсов через убирание лишних пробелов (других ошибок в данных я не обнаружил). Затем сделал выборку из этой таблицы для подсчета количества курсов на каждого студента.

drop table temp_student_course_data;

create temp table temp_student_course_data (
    id serial primary key,
    name varchar(50) not null,
    course varchar(50) not null
);

-- truncate temp_student_course_data restart identity;

insert into temp_student_course_data (name, course)
select distinct
    case
        when LOWER(TRIM(student_name)) like '%volkova%' then 'Maria Volkova'
        when LOWER(TRIM(student_name)) like '%orlov%' then 'Dmitry Orlov'
        when LOWER(TRIM(student_name)) like '%petrov%' then 'Ivan Petrov'
        else student_name
    end as name,
    TRIM(course_title) as course
from student_course_data;

-- select * from temp_student_course_data;

select
    name as name,
    Count(LOWER(course))
from temp_student_course_data
group by
    name
;

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

Ага... Оказывается у нас там есть один курс с двумя разными преподавателями, и валидатор ХОЧЕТ считать эти курсы - РАЗНЫМИ курсами! Естественно в условии это вообще не написано. Но после этого валидатор вспомнил, что там еще чето со временем нужно распарсить, а когда я распарсил - он начал жаловаться что я не использую распарсенную дату в дальнейшем запросе (а нахера бы?) В общем задачу писал (и добавил сюда) полный мудак. "Решить" ее не представляется возможным и можно только случайно. Хотя правильный ответ получен легко и просто. Также не подходит ни "правильное" решение от гениев из JavaRush, ни одно из написанных выше (я попробовал, ребят, эта херня всегда на что-то жалуется). P.S. Кстати, хотите лулзов? 😂 Вы можете общаться с валидатором через комментарии к коду. У меня получилось начать спорить на тему, нужна ли проверка парсинга дат, если в основном задании она не указана и для решения - не нужна. И ответы валидатора начали меняться, где он мне отвечал, что раз написано в условии - значит нужно! 🤣🤣🤣 Попробуйте!

Внезапно после пятого рестарта Web-Storm, валидатор решил принять мое изначальное решение, не задавая своих тупых вопросов! Я бы расписал подробно, что я думаю об этом курсе - но как показала практика - такие комментарии отсюда удаляются 😉

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