Disjoint-set/Union-find Forest
Поиск дубликатов в CSV файле. Суть задачи состояла в связанном поиска дубликатов в таблице с данными. По требованиям нужно найти из ключевых полей дубликат (в любом поле) и присвоить записи PARENT_ID первого вхождения дубликата.
Было решено использовать Union find, алгоритм который реализовали на PHP находит дубликаты связывает их и формирует результат с ID и PARENT_ID.
Поскольку реализаций данного алгоритма в сети не было, было принято решение написать свою реализацию Union find алгоритма на PHP.
Пример входных данных (за основу взят файл csv):
ID,PARENT_ID,EMAIL,CARD,PHONE,TMP
1,NULL,email1,card1,phone1,
2,NULL,email2,card1,phone2,
3,NULL,email3,card3,phone3,
4,NULL,email1,card2,phone4,
5,NULL,email5,card5,phone2,
6,NULL,email6,card6,phone6,
7,NULL,email3,card9,phone7,
8,NULL,email8,card10,phone8,
9,NULL,email9,card9,phone3,
10,NULL,email2,card10,phone10,
На примере элемента с ID 10 его связали с 2,8,4,1. Оригинальный дубликат 1. Краткая визуализация зависимостей:
- ID1 => ID2 => ID10 => ID8
- php
Выполните в консоли: php index.php или откройте файл в браузере.
ID,PARENT_ID
1,1
2,1
3,3
4,1
5,1
6,6
7,3
8,1
9,3
10,1
PS. Вы можете проверить результат здесь: http://sandbox.onlinephpfunctions.com/