Duplikate aus einer Textdatei entfernen?

R

Roccosi7

Mitglied
Hi!
Ich möchte ein Programm schreiben, mit dem ich aus einer beliebig großen Textdatei duplikate entfernen kann, ohne dabei die bestehende Ordnung zu zerstören.

Mein bisheriger Lösungsansatz:
Die Liste wird zunächst alphabetisch Sortiert (Dabei müsste die ursprüngliche Reihenfolge irgendwie gemerkt werden).
Anschließend wird immer ein Wort auf übereinstimmung mit dem Folgenden geprüft.
Wenn sie nicht übereinstimmen, wird das Wort in die Zieldatei geschrieben.
Frage: wie könnte man die Reihenfolge "merken" und anschliessend wiederherstellen?
Und wie performant wäre das ganze bei ca. 5M Zeilen in der Datei?

Könnte man vielleicht irgendwie "häppchenweise" Wörter in ein Byte-Array laden und dann vergleichen?
Würde wohl schneller gehen.

Oder habt ihr noch ganz andere Ideen?

Lg
 
Sollen alle Duplikate entfernt werden? Auch wenn die identischen Wörter an völlig verschiedenen Stellen stehen? Oder nur, wenn sie direkt aufeinander folgen?
 
Es sollen alle Duplikate entfernt werden.
aber wenn die Liste alphabetisch sortiert ist, folgen Duplikate ja auch immer direkt aufeinander 😉

Ich hatte vielleicht gedacht, das man eine Art Tabelle mit zwei Spalten anlegt:
Eine Spalte mit den Wörtern in der ursprünglichen Reihenfolge, eine mit einem fortlaufenden Index.
Dann werden die Wörter alphabetisch sortiert, die Duplikate nach der von mir genannten Methode entfernt und anschließend wird wieder nach Index sortiert.

Ich weiss wie man in PHP mit Tabellen arbeitet, aber nicht in Java.
Da bräuchte ich eure Hilfe.

Oder ihr schlagt eine andere, vielleicht einfacherer oder performantere Methode vor, wie ich mein Vorhaben realisieren kann.

Lg
 
Zuletzt bearbeitet:
Solange die Datei nicht zu groß ist würd ich das so machen:


Java: 
BufferedReader in = ...;
List<String> strings = new ArrayList<String>();

String line = "";
while ((line = in.readLine()) != null) {
  if (!strings.contains(line)) {
    strings.add(line);  
  }
}

FileWriter out = ...;
for (String s : strings) {
  out.write(s);
  out.write(NEW_LINE);
}
 
Vielleicht geht es so?

Java: 
BufferedReader in = new BufferedReader(new FileReader("in.txt"));
PrintWriter out = new PrintWriter("out.txt");
StringBuilder sb = new StringBuilder();
String str = in.readLine();
while(str != null) {
    sb.append(str); sb.append(" ");
    str = in.readLine();
}
String[] words = sb.toString.split("\\s");
HashSet<String> set = new HashSet<String>();
for(String word: words) {
    if(!set.contains(word)) {
      set.add(word)
      out.print(word);
      out.print(" ");
    }
}
out.close();
in.close();
 
Das Problem dabei ist ja, dass die Wörter in den Ram geladen werden.
Das dürfte bei zu großen Dateien zum Problem werden.
Deshalb will ich ja eine Art Datenbank-Tabelle mit den Wörtern und einem fortlaufenden Index erstellen.
Das würde ja nur zur laufzeit des Programms noch einmal die größe der Datei (oder etwas mehr...) an Festplattenspeicher beanspruchen.
Nur weiss ich nicht wie das in Java geht, und auch nicht wie man so eine Tabelle dann alphabetisch sortiert.
 
Kommst du denn wirklich in Bereiche wo du dir darüber Gedanken machen musst?
Wie groß ist die Datei? Wieviel Ram hast du zur Verfügung?
 
Das dürfte in meinem Fall nicht das Problem sein, es geht mir dabei eher ums Prinzip...das die Größe der Datei oder der verfügbare Ram keine Rolle spielen darf.

Gibt es denn keine möglichkeit mit Java eine Tabelle auf der Festplatte zu erstellen und dann die Zeilen alphabetisch oder numerisch nach einer der Spalten zu sortieren?

Wenn das wirklich nicht möglich ist, ohne alles in den Ram zu laden muss ich mich wohl damit abfinden....
 
Klar geht das.
Schnapp dir ne Datenbank (z.b. H2), erstell dir eine Tabelle mit ungefähr folgender Struktur:
SQL: 
CREATE  TABLE word (
  `id` INT NOT NULL AUTO_INCREMENT ,
  `word` VARCHAR(255) NOT NULL ,
  PRIMARY KEY (`id`) ,
  UNIQUE INDEX `word_UNIQUE` (`word` ASC) 
)
Da lässt du alle Wörter reinlaufen. Wenn du fertig bist schreibst du alles zurück in die Datei.

Den Aufwand würde ich mir aber sparen wenns nicht unbedingt sein muss.
 
Ich werde das dann wohl so machen, dass bis zu einer bestimmten größe das ganze über den Ram gemacht wird und wenn die Datei größer wird über eine Datenbank.
Eine letzte Frage habe ich noch:
Wenn ich das ganze über Arrays mache, will ich es ja vorher in Bytecode umwandeln, um Speicher zu sparen.
Wieviel Speicher spart das in etwa?
und liege ich richtig wenn ich sage, dass utf8 halb so viel Speicher verbraucht wie utf16?

Edit: Und kann man bei h2 eine Art query machen oder muss man doe ganze Tabelle einlese?
 
Zuletzt bearbeitet:
Ich hätte hier noch einen Vorschlag.
Funktioniert mit beliebig großen Dateien und macht fast alles über die Festplatte. Ist allerdings etwas langsam. Benötigt für 1 Millionen Wörter (ca. 4MB große Datei) schon mehrere Minuten. Ich poste es aber trotzdem mal.
Java: 
import java.io.*;
import java.util.Random;
import java.util.HashSet;
import java.util.Scanner;

public class Test {
    static void createRandomFile(String name, int length) throws Exception {
        Random rand = new Random();
        BufferedWriter out = new BufferedWriter(new FileWriter(name));
        for(int wordIndex = 0; wordIndex < length; wordIndex++) {
            int strLength = rand.nextInt(5)+1;
            char[] word = new char[strLength];
            for(int i = 0; i < strLength; i++) word[i] = (char)(rand.nextInt(26)+'a');
            out.write(word);
            out.write(' ');
        }
        out.close();
    }
    
    static final String dictionaryFolder = "dictionary";
    static HashSet<Character> charSet = new HashSet<Character>();
    
    static boolean addWord(String str) throws Exception {
        if(str.length() == 0) return false;
        else if(str.length() == 1) {
            char c = str.charAt(0);
            return charSet.add(c);
        } else {
            String id = str.substring(0, 2);
            File idFile = new File(dictionaryFolder + "/" + id);
            if(!idFile.exists()) idFile.createNewFile();
            else {
                BufferedReader in = new BufferedReader(new FileReader(idFile));
                String line = "";
                while((line = in.readLine()) != null) {
                    if(line.equals(str)) {
                        in.close();
                        return false;
                    }
                }
                in.close();
            }
            Writer out = new FileWriter(idFile, true);
            out.write(str);
            out.write('\n');
            out.close();
            return true;
        }
    }
    
    public static void main(String[] args) throws Exception {
        createRandomFile("largeText.txt", 1000000);
        File folder = new File(dictionaryFolder);
        folder.mkdir();
        for(File file: folder.listFiles()) {
            file.delete();
        }
        
        Scanner in = new Scanner(new File("largeText.txt"));
        BufferedWriter out = new BufferedWriter(new FileWriter("out.txt"));
        while(in.hasNext()) {
            String word = in.next();
            boolean newWord = addWord(word);
            if(newWord) {
                out.write(word);
                out.write(' ');
            }
        }
        in.close();
        out.close();
    }
}
 
mehrer Minuten?

Ich würd einfach ein Set nehmen...

Java: 
public static void main(String[] args) throws Exception {
        createRandomFile("largeText.txt", 1000000);
        
        System.out.println("file erstellt");
        
        long t = System.currentTimeMillis();
        BufferedReader reader = new BufferedReader(new FileReader("largeText.txt"));
        BufferedWriter writter = new BufferedWriter(new FileWriter("small.txt"));
        HashSet<String> set = new HashSet<String>();
        
        String line = null;
        while((line =reader.readLine()) != null){
        	if(set.contains(line))
        		continue;        	
        	writter.write(line+"\n");
        	set.add(line);
        }
        reader.close();
        writter.close();
        System.out.println("fertig");
        System.out.println("T: "+(System.currentTimeMillis()-t));
    }
wie groß, kann das file werden? 4, 40, 400 mb? 400mb sollte für einen rechner mit 4 GB kein Problem sein..

10 Mio Zeilen, 10 Sekunden... wenns an die 1 Mrd zeilen geht, würd ich auch eine db nehmen...
 
Zuletzt bearbeitet:
Ihr habt wohl recht....das ganze kann man wohl wirklich besser über den Ram machen.
Trotzdem werde für sehr große Dateien auch die Datenbank-Methode mit einbauen (oder die von Zoidberg, muss ich mir nochmal anschauen).
Kurze Frage hätte ich noch: Kann ich nicht lieber ein Byte-Set nehmen? das wäre doch weniger Speicherintensiv oder nicht? und stimmt es, das UTF-8-codierte Zeichen halb so viel Speicher brauchen wie UTF-16-codierte? Laut Definition müsste es ja so sein....

Und eine Letzte Frage allgemeiner Natur noch:
BufferedReader ist die schnellste möglichkeit, Zeilen einzulesen, oder?
Hab nämlich auch gelesen das man so oft wie möglich RandomAccessFile benutzen sollte weil es fortschrittlicher ist? (oder so)

Auf jeden Fall vielen Dank für eure Hilfe!
freut mich das einem in diesem Forum so gut geholfen wird, das kenn' ich so ja garnicht 🙂

Lg
 
Kann ich nicht lieber ein Byte-Set nehmen? das wäre doch weniger Speicherintensiv oder nicht?
Zum Vergrößern anklicken....
Wie kommst du dadrauf?

und stimmt es, das UTF-8-codierte Zeichen halb so viel Speicher brauchen wie UTF-16-codierte?
Zum Vergrößern anklicken....
Nicht zwangsläufig, siehe Unicode Transformation Format ? Wikipedia

BufferedReader ist die schnellste möglichkeit, Zeilen einzulesen, oder?
Zum Vergrößern anklicken....
Ja, zumindest die einfachste.

Hab nämlich auch gelesen das man so oft wie möglich RandomAccessFile benutzen sollte weil es fortschrittlicher ist? (oder so)
Zum Vergrößern anklicken....
Ne, das ist falsch. Das kommt eher auf den Anwendungsfall an. Um Daten zeilenweise auszulesen würde ich den BufferedReader nutzen, wenn man auf beliebige Daten zugreifen will, dann das RAF.
 
Naja im Bytecode dürfte die Datei im Ram doch nicht wesentlich mehr Speicher verbrauchen als die Datei groß ist?
(zumindest nicht 7-10-mal so viel...)
Oder hab ich da 'nen Denkfehler drin?
 
Roccosi7 hat gesagt.:
und stimmt es, das UTF-8-codierte Zeichen halb so viel Speicher brauchen wie UTF-16-codierte? Laut Definition müsste es ja so sein....
Zum Vergrößern anklicken....

Also, wenn die Strings möglichst wenig Speicher verbrauche sollen, kannst du deine eigene String Klasse definieren. Die equals und hashCode Methoden sollten dabei überschrieben werden, damit die Klasse mit HashSets und ähnlichem korrekt zusammenspielt. Angenommen die Strings enthalten nur Ascii Zeichen, dann geht es z.b: so

Java: 
class AsciiString implements Comparable<AsciiString> {
    private final byte[] array;
    private final short hash;
    
    public AsciiString(String str) {
        try {
            array = str.getBytes("ascii");
        } catch(UnsupportedEncodingException e) {
            throw new RuntimeException();
        }
        short hash = 0;
        if(array.length > 0) hash = array[0];
        if(array.length > 1) hash = (short)(hash*256+array[1]);
        this.hash = hash;
    }
    
    @Override
    public int hashCode() {
        return hash;
    }
    
    public int compareTo(AsciiString other) {
        int i = 0;
        while(i < array.length && i < other.array.length) {
            if(array[i] != other.array[i]) return array[i] - other.array[i];
            i++;
        }
        return array.length - other.array.length;
    }
    
    @Override
    public boolean equals(Object o) {
        if(o == this) return true;
        if(o instanceof AsciiString) {
            return compareTo((AsciiString)o) == 0;
        } else if(o instanceof String) {
            String str = (String)o;
            if(str.length() != array.length) return false;
            for(int i = 0; i < array.length; i++) {
                if(array[i] != str.charAt(i)) return false;
            }
            return true;
        } else return false;
    }
}
 
Du kannst statt Ascii natürlich auch utf8 nehmen, falls da Sonderzeichen drin sind. Utf8 ist fast genauso kurz wie Ascii.
Hab die Klasse mal etwas abgeändert, jetzt funktioniert sie mit jeder beliebigen Kodierung, HashSet Operationen mit der Klasse sind allerdings auch ein klein wenig langsamer.

Java: 
import java.nio.charset.Charset;

public class AsciiString implements Comparable<AsciiString> {
    private final byte[] array;
    static final Charset ENCODING = Charset.forName("utf8");
    
    public AsciiString(String str) {
        array = str.getBytes(ENCODING);
    }
    
    @Override
    public int hashCode() {
        int hash = 0;
        if(array.length > 0) hash = array[0];
        if(array.length > 1) hash = hash*256+array[1];
        return hash;
    }
    
    public int compareTo(String str) {
        return toString().compareTo(str);
    }
    
    public int compareTo(AsciiString other) {
        return compareTo(other.toString());
    }
    
    @Override
    public boolean equals(Object o) {
        if(o == this) return true;
        if(o instanceof AsciiString) {
            return compareTo((AsciiString)o) == 0;
        } else if(o instanceof String) {
            return compareTo((String)o) == 0;
        } else return false;
    }
    
    @Override
    public String toString() {
        return new String(array, ENCODING);
    }
}
 
Zuletzt bearbeitet:
Wenn ich das ganze über Arrays mache, will ich es ja vorher in Bytecode umwandeln, um Speicher zu sparen.
Zum Vergrößern anklicken....

hört sich schon sehr nach troll an...

Aber wenn das ernst ist: was für eine Datei ist das überhaupt? Warum nennst du das immer wieder mal "Liste"? Ist das freier Text oder etwas CSV ähnliches, dann gibt es uU besser Lösungen für dein Problem.
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

Textdatei einlesen und in HashMap speichern (duplikate entfernen)
Antworten: 12
Duplikate aus ArrayList entfernen
Antworten: 2
Duplikate aus Liste entfernen
Antworten: 16
Duplikate aus eigenen Datentypen entfernen
Antworten: 14
Entfernen aus einer Collection soll zum Entfernen einer Beziehung führen
Antworten: 3

Zurück
Oben