2

Есть большой входной файл (10^12 строк) со следующим форматом: Имя|Фамилия|Дата Рождения

Пример:

Yana|Petrova|21.01.1990
Kseniya|Ivanova|22.02.1990
Kseniya|Ivvanova|22.02.1990
Jana|Petrova|21.01.1091

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

Необходимо реализовать MapReduce приложение, которое выделит уникальных пользователей.

Пример выходного файл после работы алгоритма:

1|Yana|Petrova|21.01.1991
2|Kseniya|Ivanova|22.02.1990
2|Kseniya|Ivvanova|22.02.1990
1|Jana|Petrova|21.01.1091

Где первое поле – ID уникального пользователя. Порядок строк в выходном файле не важен. Важны лишь правильно проставленные ID уникального пользователя, минимизирующие выбранную метрику.

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

0

1 ответ 1

4

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

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

Поскольку вы предполагаете, что имя и фамилия могут быть перепутаны местами, придется делать два сравнения (склеивая имя с фамилией в прямом и обратном порядке, после чего брать лучшее (меньшее) значение.

public boolean fuzzyEqual(String firstname1, String lastname1, String firstname2, String lastname2, int treshold) {
    return treshold >= Math.min(
               dist(firstname1 + " " + lastname1, firstname2 + " " + lastname2),
               dist(firstname1 + " " + lastname1, lastname2 + " " + firstname2)
    );
}

public int dist(String a, String b) {
    // тут ваша реализация расстояния Левенштейна
}

PS. При использовании алгоритма строки, само собой, нужно привести к верхнему или нижнему регистру.

3
  • Так в конечном итоге, что именно Вы предлагаете передавать в fuzzeEual()? Все пары из 10^12 строк? Это будет, если не ошибаюсь, 10^24 вызовов функции...
    – avp
    27 июн 2016 в 21:04
  • @avp, мой ответ - на непосредственно алгоритмический вопрос ТС - в особенности интересует стадия reduce. Как лучше выполнять сравнения и распознавать одинаковых пользователей?. Что делать с файлом, в котором 27 терабайт имен и фамилий - вопрос интересный сам по себе, и тут консультировать я пока не берусь. Но еще в 14м году на Apache Spark отсортировали 100TB данных на 200 амазоновских нодах всего за 23 минуты.
    – Nofate
    27 июн 2016 в 21:58
  • Подозреваю, что данные уже были распределены хотя бы по дискам этих нодов. Понятно, что в задаче ТС первым делом надо выкинуть реальные дубликаты, которых там минимум 99.9% (исходим из численности населения страны), а fuzzy применять уже к сильно усеченному множеству. Возможно после этого усечения стоит вычислить удаление от некого эталона (например, всех пробелов), потом можно перебирать уже не все пары. И конечно, совсем забыл, на какой-то стадии деления обязательно надо учесть дни рождения в качестве первичного ключа деления.
    – avp
    27 июн 2016 в 22:19

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.