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 that you have read and understand our privacy policy and code of conduct.

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