Liste in pseudo geordnete Reihenfolge bringen

[harte-nuss]

Hi. Ich habe eine Liste, in der IP-Adresse aufsteigend sortiert sind. Zwei IP-Adressen können ähnliche GPS haben. Wie entscheide ich dann bei Duplikaten, welche IP-Adresse behalten werden soll, sodass nicht immer nur die kleinste oder größte IP des gleichen GPS erhalten bleibt? Das Resultat sollte jedoch auch replizierbar sein, das heißt, wenn in einem Intervall neue und gleiche IPs hinzukommen, dann soll das Resultat auch das gleiche sein.

Beispiel:

    TreeMap<Point2D, String[]> database = new TreeMap<>(Comparator.comparingDouble(Point2D::getX).thenComparingDouble(Point2D::getY));
    //...
    double minDistance = 0.01; // approx ~1km
    for (Point2D p1 : new LinkedList<>(database.keySet())) {
      for (Point2D p2 : new LinkedList<>(database.keySet())) {
        if (p1.equals(p2)) {
          continue;
        }
        if (p1.distance(p2) < minDistance) {
          // Was hier tun?
          //database.remove(p2);
          //System.out.println("Removed duplicate GPS entry at " + p2 + " with distance " + p1.distance(p2));
        }
      }
    }

 

[KonradN]

Ich fürchte, Du hast bisher noch nicht wirklich beschrieben, was genau Du haben willst. Vermutlich erklärt das auch Dein Problem, hier irgend welchen sinnvollen Code abzuliefern. Du musst also wirklich die Problemdomain sorgfältig beschreiben und darauf basierend dann die notwendige Businesslogik beschreiben.

Wenn Du etwas beschreibst, dann muss es auch dem Code entsprechen - "Ich habe eine Liste" und dann eine TreeMap<Point2D, String[]> passt nicht wirklich.

Vermutlich kommt daher dann auch so ein erster Ansatz, der relativ an den Haaren herbei gezogen ist. Wie kommst Du auf zwei Listen, die Du durchgehst? Und die Listen erstellst Du einmal aus der Map und nimmst dann nur Elemente aus der Map? Du wirst abgearbeitete Elemente also wieder und wieder bearbeiten und erneut prüfen. Dabei willst Du doch unter dem Strich nur eine Liste einmal durchgehen um dann eben die Zielliste zu erstellen. So habe ich zumindest deine grobe Anforderung verstanden.

Also Du hast bisher eine "Liste" von jeweils einer Koordinate und dazu dann ein Array mit IPs. (Aus Deiner TreeMap kannst Du das z.B. über entrySet() bekommen - ist dann zwar ein Set, aber das ist hier jetzt eine umgangssprachliche Ungenauigkeit. Generell wäre aber die Frage: Was bekommst Du wirklich bzw. hast Du genau?

Nun willst Du da weitere Gruppierungen vornehmen - über den Abstand und das Resultat soll immer gleich sein? Halte ich für so nicht möglich:
Nehmen wir drei Punkte, die annähernd auf einer Geraden Strecke liegen: A-B-C - die Abstände von A,B und B,C sind kleiner als dein minimaler Abstand, A,C ist aber größer. Nun hängt es von der Reihenfolge ab, wie das Ergebnis erfasst wird:
Kommt B zuerst, dann wird festgestellt: A liegt dichter dran -> Kommt zu B, C liegt dichter dran -> kommt zu B. Du hast also B mit IPs von A,B und C
Kommt A zuerst, dann wirst Du A mit Werten von A und B haben und C mit dem Wert von C.
Kommt C zuerst, dann wirst Du C mit den Werten von C und B haben und A mit dem Wert von A.

Hier müsste man also entweder akzeptieren, dass es eben abhängig von der Reihenfolge der Punkte ist, was als Ergebnis heraus kommt. (Wenn Du nur einmal eine Liste hast und diese sortiert ist, dann hättest Du bei jedem durchlauf natürlich immer das gleiche Ergebnis), oder Du müsstest Dir hier genauer überlegen, was die Anforderung ist und wie Du diese erfüllen könntest.

Wenn man dann so einen Algorithmus entwickeln will, dann sollte man diesen im Detail aufschreiben. Und zwar so genau, dass klar ist, was gemacht werden muss. Dabei wird idealer Weise auch direkt der Algorithmus in viele einzelne unterteilt.

Also hier wäre das etwas wie:

Für jedes Element aus Koordinate und Liste an IPs:
- Füge dieses Element in der Zielstruktur ein.

Einfügen von Koordinate Kneu / IPs in die Zielstruktur wäre dann:
- finde das erste Element für das gilt Abstand von Knew zu Kelem < minDistance
-- Wenn so ein Element gefunden wurde, dann füge die IPs vom neuen Element diesen IPs des bisherigen Elements hinzu
-- Wenn so ein Element nicht gefunden wurde, dann füge Kneu mit den IPs in der Zielstruktur hinzu.

Einfügen von IPs in eine vorhandene Struktur von IPs
Das wäre dann auch noch zu beschreiben ...

Sowas lässt sich dann relativ einfach und strukturiert entwickeln. Was wir jetzt aber nur betrachtet haben ist der reine logische Ablauf. Wir sollten aber hier auf sinnvolle Datenkonstrukte zurück greifen. Java ist eine objektorientierte Sprache und es bietet sich an, sowas auch zu verwenden. Daher würde ich für die "Zielstruktur" eine eigene Klasse schreiben. Datenklassen sollten die Daten sauber umfassen, also z.B. die Koordinate zusammen mit den IP Adressen ... Die IP Adressen könnte man auch in einer eigenen Struktur umfassen um da die Logik sauber zu kapseln...Aber das hängt davon ab, was Du da brauchst. Evtl. reicht es, hier einfach ein Set<String> zu haben, da dieses bereits alle Logik enthält, die man braucht.

Die Kernidee einer solchen Implementation ist dann also, dass Du eine Klasse hast, die die Daten entsprechend vorhält. Wenn neue Datensätze hinzukommen, dann werden diese entsprechend hinzugefügt. Intern mag das dann eine TreeMap sein, aber das ist erst einmal egal. Das ist ein internes Implementationsmerkmal, das nicht nach aussen geht.

 

[Oneixee5]

Das klingt wie die Implementierung einer sogenannten Bounding Box (Begrenzungsrahmen). Da du nur an den Extremwerten interessiert bist, musst du nicht alle Punkte speichern, sondern nur vier Werte aktualisieren, sobald ein neuer Punkt hinzugefügt wird.

import java.awt.geom.Point2D;

public class PointBounds {
    private double minX = Double.MAX_VALUE;
    private double minY = Double.MAX_VALUE;
    private double maxX = -Double.MAX_VALUE;
    private double maxY = -Double.MAX_VALUE;
    private boolean isEmpty = true;

    /**
     * Fügt einen neuen Punkt hinzu und aktualisiert die Min/Max-Werte.
     */
    public void add(Point2D point) {
        if (point == null) return;

        double x = point.getX();
        double y = point.getY();

        minX = Math.min(minX, x);
        minY = Math.min(minY, y);
        maxX = Math.max(maxX, x);
        maxY = Math.max(maxY, y);
        
        isEmpty = false;
    }

    // Getters
    public double getMinX() { return isEmpty ? 0 : minX; }
    public double getMinY() { return isEmpty ? 0 : minY; }
    public double getMaxX() { return isEmpty ? 0 : maxX; }
    public double getMaxY() { return isEmpty ? 0 : maxY; }

    @Override
    public String toString() {
        if (isEmpty) return "Bounds: empty";
        return String.format("Bounds: [MinX: %.2f, MinY: %.2f] to [MaxX: %.2f, MaxY: %.2f]",
                              minX, minY, maxX, maxY);
    }
}

 

[KonradN]

Bounding Box (Begrenzungsrahmen).

Ich glaube, Du hast bei den Math.min/Math.max Aufrufen in dem gegebenen Code vergessen, x bzw y zu verändern. Du willst da ja nicht x und y speichern sondern jeweils +/- einer bestimmten Boxgröße.

Aber muss man die Box so genau definieren? Durch den Abstand hat man sowas ja bereits prinzipiell (dann nur eben nicht als box sondern als ein Kreis um einen Punkt).

 

[Oneixee5]

Ich glaube, Du hast bei den Math.min/Math.max Aufrufen in dem gegebenen Code vergessen, x bzw y zu verändern. Du willst da ja nicht x und y speichern sondern jeweils +/- einer bestimmten Boxgröße.

Aber muss man die Box so genau definieren? Durch den Abstand hat man sowas ja bereits prinzipiell (dann nur eben nicht als box sondern als ein Kreis um einen Punkt).

Ich denke nicht, GPS-Koordinaten sind absolut, nicht +/-. Man kann also genau herausfinden, ob eine IP in einem bestimmten Umfeld liegt oder nicht.

 

[Oneixee5]

Zu den IP's selbst: Wenn man die kleinste oder größte IP wählt, erzeugt man einen Bias (systematische Bevorzugung). Um das zu vermeiden und gleichzeitig ein gleiches Ergebnis bei gleichen Daten zu garantieren, ist Hashing die beste Lösung. Anstatt min(IP) zu nehmen, nimmt man die IP, mit dem Hash der am kleinsten ist. Da der Hash-Wert einer IP immer gleich bleibt, ist das Ergebnis wiederholbar. Da Hash-Werte aber nichts mit der numerischen Größe der IP zu tun haben, verhinderst man den Bias für kleine/große IPs.
Wenn man eine neue IP zum Cluster hinzugefügt, wird diese nur dann der neue Gewinner/Endwert, wenn der Hash noch kleiner ist als der des bisherigen Gewinners. Der bisherige Gewinner wird niemals gegen eine IP verlieren, gegen die er vorher schon mal gewonnen hat.

 

[Oneixee5]

Ich habe mal versucht, das Vorherige in Code zu schreiben:

public class IPDeduplicator {

    record IPPoint(String ip, double lat, double lon) {}

    public List<IPPoint> deduplicate(List<IPPoint> input) {
        return input.stream()
            .collect(Collectors.groupingBy(
                // 1. Key: GPS auf ca. 11m genau runden (4 Dezimalstellen)
                p -> Math.round(p.lat() * 10000) + ":" + Math.round(p.lon() * 10000),
                Collectors.collectingAndThen(
                    Collectors.toList(),
                    list -> list.stream()
                        // 2. Die IP mit dem kleinsten Hash-Wert auswählen
                        .min(Comparator.comparing(p -> getHash(p.ip())))
                        .orElseThrow()
                )
            ))
            .values()
            .stream()
            .toList();
    }

    // Erzeugt einen stabilen, wiederholbaren Wert für jede IP
    private String getHash(String input) {
        try {
            MessageDigest md = MessageDigest.getInstance("SHA-256");
            byte[] hash = md.digest(input.getBytes(StandardCharsets.UTF_8));
            return Base64.getEncoder().encodeToString(hash);
        } catch (NoSuchAlgorithmException e) {
            //-> todo
        }
    }
}

Wenn man die GPS-Koordinaten nur rundet, kann es passieren, dass zwei Punkte, die sehr nah beieinander liegen getrennt werden. Wenn das ein Problem ist, solltest man über sowas wie DBSCAN nachdenken, wobei dort wieder der IP-Hash angewendet wird.

 

[harte-nuss]

Freunde, es hat schon geklappt...

Das klingt wie die Implementierung einer sogenannten Bounding Box (Begrenzungsrahmen)

Ja, fast. Mann muss erst einen Clustering Algorithmus anwenden und dann für jedes Cluster einen Repräsentanten finden. Dieser Repräsentant kann die GPS sein, die dem Cluster-Zentrum am nächsten ist:

  private static TreeMap<Point2D, String[]> findClusters(
      TreeMap<String, IPInfo> databaseCopy, double minDistance) {
    TreeMap<Point2D, String[]> clusteredDatabase =
        new TreeMap<>(Comparator.comparingDouble(Point2D::getX).thenComparingDouble(Point2D::getY));
    for (Map.Entry<String, IPInfo> entry : databaseCopy.entrySet()) {
      String[] gpsData = entry.getValue().toCsvRow2();
      if (gpsData == null) {
        continue;
      }
      Point2D key =
          new Point2D.Double(Double.parseDouble(gpsData[0]), Double.parseDouble(gpsData[1]));
      if (clusteredDatabase.containsKey(key)) {
        continue;
      }
      clusteredDatabase.put(key, gpsData);
    }
    LinkedList<TreeMap<Point2D, String[]>> clusters = new LinkedList<>();
    for (Map.Entry<Point2D, String[]> entry : clusteredDatabase.entrySet()) {
      TreeMap<Point2D, String[]> cluster =
          new TreeMap<>(
              Comparator.comparingDouble(Point2D::getX).thenComparingDouble(Point2D::getY));
      cluster.put(entry.getKey(), entry.getValue());
      clusters.add(cluster);
      for (Map.Entry<Point2D, String[]> entry2 : clusteredDatabase.entrySet()) {
        if (entry == entry2) {
          continue;
        }
        if (entry.getKey().distance(entry2.getKey()) < minDistance) {
          cluster.put(entry2.getKey(), entry2.getValue());
        }
      }
    }
    clusteredDatabase.clear();
    for (TreeMap<Point2D, String[]> cluster : clusters) {
      if (cluster.size() == 1) {
        Map.Entry<Point2D, String[]> entry = cluster.firstEntry();
        clusteredDatabase.put(entry.getKey(), entry.getValue());
        continue;
      }
      Map.Entry<Point2D, String[]> representative = findRepresentative(cluster);
      clusteredDatabase.put(representative.getKey(), representative.getValue());
    }
    // Round coordinates to 3 decimal places
    TreeMap<Point2D, String[]> roundedDatabase =
        new TreeMap<>(Comparator.comparingDouble(Point2D::getX).thenComparingDouble(Point2D::getY));
    for (Map.Entry<Point2D, String[]> entry : clusteredDatabase.entrySet()) {
      double lngRounded =
          BigDecimal.valueOf(entry.getKey().getX()).setScale(3, RoundingMode.HALF_UP).doubleValue();
      double latRounded =
          BigDecimal.valueOf(entry.getKey().getY()).setScale(3, RoundingMode.HALF_UP).doubleValue();
      Point2D roundedKey = new Point2D.Double(lngRounded, latRounded);
      if (roundedDatabase.containsKey(roundedKey)) {
        // Just for debugging, should never happen ...
        System.out.println("Error: Duplicate rounded key found: " + roundedKey);
        continue;
      }
      roundedDatabase.put(roundedKey, entry.getValue());
    }
    return roundedDatabase;
  }

  private static Map.Entry<Point2D, String[]> findRepresentative(
      TreeMap<Point2D, String[]> cluster) {
    double centerX = 0;
    double centerY = 0;
    for (Point2D point : cluster.keySet()) {
      centerX += point.getX();
      centerY += point.getY();
    }
    centerX /= cluster.size();
    centerY /= cluster.size();
    Point2D center = new Point2D.Double(centerX, centerY);
    double minDistance = Double.MAX_VALUE;
    Map.Entry<Point2D, String[]> representative = null;
    for (Map.Entry<Point2D, String[]> entry : cluster.entrySet()) {
      double distance = entry.getKey().distance(center);
      if (distance < minDistance) {
        minDistance = distance;
        representative = entry;
      }
    }
    return representative;
  }

Und mir ist bewusst, dass bei Longitude und Latitude die Luftlinie von der tatsächlichen Entfernung abweicht (wegen Erdkrümmung). Bei 10 km ist es aber vernachlässigbar.