CSV-Tool: Ähnliche Texte

CSV Dateien aufräumen und Tippfehler etc. entfernen

Projektart
Prototyp
Datum
06.04.2018
Material
GitHub

In den letzten Wochen haben wir uns etwas intensiver mit der Berliner Zuwendungsdatenbank beschäftigt. Dabei sind wir auf ein typisches Open Data-Problem gestoßen: Weil Namen und Adressen der Zuwendungsempfänger händisch in die Verwaltungsdatenbank eingepflegt wurden, haben sich eine ganze Menge Tippfehler und Ungenauigkeiten in die Daten eingeschlichen. Wir haben deshalb ein kleines Tool entwickelt, dass in der Lage ist, solche Ungereimtheiten zu erkennen und für mehr Ordnung in CSV-Dateien zu sorgen. Hier könnt ihr es ausprobieren.

Nehmen wir einmal an, der (fiktive) Verein „Kaninchenfreunde Karlshorst e.V.“ erhält eine finanzielle Förderung aus Landesmitteln und somit auch einen Eintrag in der Zuwendungsdatenbank. Im folgenden Jahr erhält der Verein vielleicht erneut eine Förderung. Diesmal vergisst die in der Verwaltung zuständige Person jedoch einen Punkt und trägt „Kaninchenfreunde Karlshorst e.V“ in die Datenbank ein. Aufgrund der unterschiedlichen Schreibweise würde eine Maschine davon ausgehen, dass es sich um zwei unterschiedliche Träger handelt. Da die Zuwendungsdatenbank mehrere tausend Einträge enthält, ist es mitunter recht schwierig, solche kleinen Vertipper nachträglich aufzuspüren. Hier hilft unser Tool weiter.

Ausgangsdatensatz

Füge den Inhalt einer CSV-Datei in das Textfeld ein oder ziehe die Datei von deinem Rechner direkt auf das Textfeld. Beachte, dass die erste Zeile die Spaltennamen enthalten muss. Für einen ersten Test kannst Du auch die bereits eingetragenen Beispieldaten verwenden.
In der Webversion sollten die Datensätze nicht zu groß sein (<2MB) um schnelle Ergebnisse zu erzielen.



Welches Trennzeichen wird in der Datei eingesetzt?
Dies sollte eigentlich automatisch erkannt werden.


Welche Spalte soll analysiert werden?
Bitte auswählen.

Vergleichs-Algorithmus

Welcher Algorithmus soll für den Vergleich genutzt werden?
Eine Erklärung zu den beiden Methoden findest du weiter unten auf der Seite.

Zusatzparameter für den Fingerprint-Algorithmus:
Art des Fingerprinting:

Sprache:

Sollen die Wörter einem Stemming-Prozess unterzogen werden:
Zusatzparameter für den KNN-Algorithmus:
Mindestanzahl an übereinstimmenden Zeichen (empfohlen: 6):

Maximale Abweichung in Prozent (empfohlen: 10):

Korrektur-Template

Das Tool gruppiert nun ähnlich geschriebene Wörter, die richtige Schreibweise lässt sich auswählen. Im nächsten Schritt werden dann alle Wörter einer Gruppe durch die richtige Schreibweise ersetzt. Soll ein Wort nicht zur Gruppe gehören, kann es entfernt werden.
(Abhängig von der Größe des Ausgangsdatensatzes kann es etwas dauern bis das Template angezeigt wird.)



Korrigierter Datensatz

Im folgenden Textfeld sollten nur noch die korrekten Bezeichnungen auftauchen und alle Fehler entfernt worden sein.
Je nach Größe der Datei kann das Säubern einen Augenblick in Anspruch nehmen.

Was steckt hinter dem Tool?

Zur Erkennung von Ähnlichkeiten greift unser Tool je nach Einstellungen auf die Fingerprint- oder die KNN-Methode zurück.

Fingerprint

Die grundsätzliche Idee des Fingerprinting ist es einen Text auf seine essentiellen Bestandteile zu reduzieren und dadurch einen essentiellen Fingerabdruck zu generieren. Dieser Fingerabdruck wird dann mit anderen verglichen um gleiche Text zu identifizieren.

Normales Fingerprinting

Um dies anzuwenden gibt es zwei Möglichkeiten. In der normalen Variante werden folgende Schritte angewandt:

  • Leerzeichen am Anfang und Ende werden entfernt.
  • Umwandlung in Kleinbuchstaben.
  • Entfernen von Punktation und Leerzeichen.
  • Umwandeln von Sonderzeichen (e.g. ä > ae).
  • Entfernen von unsichtbaren Zeichen.

So wird dann z.B. aus


      'Grips'-Theater gemeinnützige Gesellschaft
      gripstheatergemeinnuetzigegesellschaft
  

Dies bedeutet, dass alle folgenden Varianten zum selben Fingerabdruck werden:


      'Grips'-Theater gemeinnützige Gesellschaft
      Grips-Theater gemeinnützige Gesellschaft
       Grips Theater gemeinnützige Gesellschaft
      Grips Theater gemeinnützigeGesellschaft

      gripstheatergemeinnuetzigegesellschaft
  

Dieses Verfahren ist sehr schnell, kann aber Probleme wie komplexere Tippfehler häufig nicht erkennen.

Phonetisches Fingerprinting

Beim phonetischen Fingerabdruck werden Textelemente erst in ihre phonetischen Marker übersetzt. Hierdurch können häufig kleine Schreibfehler, weil z.B. jemand nach Gehör geschrieben hat erkannt werden.

So haben folgende Schreibweisen die selben phonetischen Marker:



      Sebastian
      Sebästian
      Sebastien

      81826
  

Um die Umwandlung vorzunehmen wurden in unserem Modul zwei Bibliotheken integriert: für deutsch die cologne-Sammlung und für andere Sprachen die metaphone-Sammlung.

KNN / Neighbour

Die Nachbarschaftsmethode ist wesentlich komplexer und damit auch rechenintensiver, dafür aber auch genauer. Die Grundlage ist ein direkter Vergleich zweier Texte, bei dem die Distanz zwischen den Texten berechnet wird, genauer gesagt, die Levenshtein-Distanz. Diese beschreibt die Anzahl an Veränderungen am ersten Text (Löschen, Hinzufügen und Ersetzen von Zeichen), die notwendig sind um den anderen Text zu generieren. Um nicht jeden Text mit jedem anderen Text vergleichen zu müssen, wird vorher überprüft welche Texte überhaupt ähnliche Elemente enthalten. Hierzu wird der Text in kleine Bausteine aufgebrochen und diese werden miteinander verglichen. Umso länger die Bausteine umso schneller und umso kürzer die Bausteine umso genauer (Standardwert: 6).

Folgend ein Beispiel für die Aufteilung eines Textes in 6er Zeichenketten:



      Technologie
      Techno
       echnol
        chnolo
         hnolog
          nologi
           ologie

      Technik
      Techni
       echnik

      Technische
      Techni
       echnis
        chnisc
         hnisch
          nische

  

Im obrigen Beispiel würden Technik und Technische den gemeinsamen Baustein "Techni" haben.

Bei den Texten die eine Ähnlichkeit aufweisen, wird dann die konkrete Distanz berechnet. Hier sind ein paar Beispiele und die entsprechenden Distanzen:



      Technik <> Technische = 4
      Berlin <> Bern = 2
      Senat <> Stern = 4
  

Für die Bewertung der Levenshteinschen Distanz (LD) setzen wir auf das Verhältnis zur Textlänge. Ein sehr langer Text der eine LD von 2 hat ist möglicherweise derselbe, ein Wort von nur 5 Zeichen mit einer LD von 2 ist mit einer geringeren Wahrscheinlichkeit derselbe.

Die hier eingesetzten Methoden haben wir uns nicht ausgedacht, sondern sind gängige Methoden um solche Problem zu lösen. Inspiriert wurde unser Vorgehen von den Funktionalitäten der quelloffenen Desktop-Anwendung Open Refine, die sich bestens eignet um Datensätze zu säubern.

Nutzung/Installation

Das Tool kann nicht nur hier im Browser genutzt, sondern läuft auch auf der Kommandozeile oder lässt sich in eigene Anwendungen integrieren. Entwickler*innen, die damit arbeiten wollen, können via NPM das entsprechende Node-Modul installieren. Der Quellcode ist wie immer offen und unter untenstehendem Github-Link abrufbar. Wir freuen uns über Feedback und Weiterentwicklungen!