Duplikate aus einer Textdatei entfernen?

[Roccosi7]

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

 

[DrZoidberg]

Sollen alle Duplikate entfernt werden? Auch wenn die identischen Wörter an völlig verschiedenen Stellen stehen? Oder nur, wenn sie direkt aufeinander folgen?

 

[Roccosi7]

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

 

[Gast2]

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

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);
}

 

[DrZoidberg]

Vielleicht geht es so?

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();

 

[Roccosi7]

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.

 

[Gast2]

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?

 

[Roccosi7]

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....

 

[Gast2]

Klar geht das.
Schnapp dir ne Datenbank (z.b. H2), erstell dir eine Tabelle mit ungefähr folgender Struktur:

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.

 

[Roccosi7]

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?

 

[DrZoidberg]

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.

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();
    }
}

 

[ARadauer]

mehrer Minuten?

Ich würd einfach ein Set nehmen...

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...

 

[Timothy Truckle]

[Filterlösung]

Deine Lösung kommt sogar noch mit viel größeren Dateien zurecht, wenn die Worte sich oft wiederholen...

bye
TT

 

[ARadauer]

Ja wenn 1000 Mrd mal das selbe drinne steht, bleibt das Set relativ klein ;-)

 

[Roccosi7]

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

 

[Gast2]

Kann ich nicht lieber ein Byte-Set nehmen? das wäre doch weniger Speicherintensiv oder nicht?

Wie kommst du dadrauf?

und stimmt es, das UTF-8-codierte Zeichen halb so viel Speicher brauchen wie UTF-16-codierte?

Nicht zwangsläufig, siehe Unicode Transformation Format ? Wikipedia

BufferedReader ist die schnellste möglichkeit, Zeilen einzulesen, oder?

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)

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.

 

[Roccosi7]

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?

 

[DrZoidberg]

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....

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

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;
    }
}

 

[Roccosi7]

Stimmt, auf sowas wäre ich garnicht gekommen!
Danke

 

[DrZoidberg]

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.

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);
    }
}

 

[Bleiglanz]

Wenn ich das ganze über Arrays mache, will ich es ja vorher in Bytecode umwandeln, um Speicher zu sparen.

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.