Как правильно сгруппировать строки по значениям столбцов с помощью Union-Find в Java? ⇐ JAVA

[Anonymous]

У меня есть задача, которую я не могу решить. Мне дали файл с миллионом строк. Каждая строка может содержать неограниченное количество элементов следующего типа:

Код: Выделить всё

"111";"123";"222"
"200";"123";"100"
"300";"";"100"

Недопустимые строки (которые следует игнорировать) имеют следующий формат:

Код: Выделить всё

"8383"200000741652251"
"79855053897"83100000580443402";"200000133000191"

Цель состоит в том, чтобы сгруппировать строки по следующим критериям:
Если две строки имеют совпадения в одном или нескольких непустых столбцах, они должны принадлежать к одной группе.
Например:

Код: Выделить всё

"111";"123";"222"
"200";"123";"100"
"300";"";"100"

Все они принадлежат к одной группе, поскольку первые две строки имеют одинаковое значение 123 во втором столбце, а последние две строки имеют одинаковое значение 100 в третьем столбце.
p>
Однако строки типа:

Код: Выделить всё

"100";"200";"300"
"200";"300";"100"

не должны находиться в одной группе, поскольку они не соответствуют критериям сопоставления столбцов.
Программа должна завершиться за 30 секунд и должна работать в пределах 1 ГБ памяти (-Xmx1G).
AI-помощник предложил использовать алгоритм «объединение-поиск» или «непересекающееся-множество» и предоставил исходный код. После внесения некоторых изменений вот моя текущая реализация:

Код: Выделить всё

package com.test;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

public class UniqueLineGrouper {
static class UnionFind {
private int[] parent;
private int[] rank;

public UnionFind(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
rank[i] = 0;
}
}

public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}

public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
}

public static void main(String[] args) {
List rows = new ArrayList();
try (BufferedReader br = new BufferedReader(new FileReader(args[0]))) {
String line;
while ((line = br.readLine()) != null) {
String[] columns = line.split(";");
boolean isValid = true;
for (String column : columns) {
if (column.isEmpty() && !column.matches("\\d{3}")) {
isValid = false;
break;
}
}
if (isValid) {
rows.add(columns);
}
}
} catch (IOException e) {
e.printStackTrace();
}

//This part has a bug
UnionFind uf = new UnionFind(rows.size());
Map columnValueMap = new HashMap();
for (int i = 0; i < rows.size(); i++) {
String[] row = rows.get(i);
for (int j = 0; j < row.length; j++) {
String value = row[j].trim();
if (!value.isEmpty() && !value.equals("\"\"")) {
if (columnValueMap.containsKey(value)) {
int prevRowIdx = columnValueMap.get(value);
uf.union(i, prevRowIdx);
} else {
columnValueMap.put(value, i);
}
}
}
}

Map groups = new HashMap();
for (int i = 0; i < rows.size(); i++) {
int group = uf.find(i);
groups.computeIfAbsent(group, k -> new ArrayList()).add(i);
}

for (List group : groups.values()) {
System.out.println("Group:");
for (int idx : group) {
System.out.println(Arrays.toString(rows.get(idx)));
}
System.out.println();
}
}
}

Группировка работает, но есть ошибка, из-за которой строки группируются, даже если совпадение наблюдается в разных столбцах. Например, следующий набор строк группируется вместе, хотя последние две строки не должны находиться в одной группе согласно правилу сопоставления столбцов:

Код: Выделить всё

"111";"123";"222"
"200";"123";"100"
"300";"";"100"
"100";"200";"300"
"200";"300";"100"

Кроме того, я думал об использовании Collections.disjoint() для пропуска строк, которые не имеют общих элементов, но я не уверен, что это улучшит производительность.
Может ли кто-нибудь помочь мне решить эту проблему?

Подробнее здесь: https://stackoverflow.com/questions/790 ... nd-in-java