vergleich zweier texte

[latoureiffel]

hi!

ich habe 2 grosse textdateien (eine 1 gb gross, die andere 2 gb) und will beide durchsuchen und zwar nach folgenden muster:
datei 1 bezeichnet einen zahlenbereich (hier 1 bis 5 und nächste zeile 3 bis 9) zb.
A text text 1 5 text text
B text 3 9 text text
Q text text 27 873 text

datei 2 sieht so aus
C text text text 38 text
A text 3 text text
A text text 8 text text

usw. ("text" steht für worte, einzelne buchstaben etc. ist momentan nicht von belang).

ich will jetzt wissen, ob die angegebene zahl in datei 2 in den rahmen von 1 passt, aber nur wenn der erste buchstabe übereinstimmt.
also müsste ich bei meinem beispil eine übereinstimmung finden (weil zeile 2 aus datei 2 (zahl = 3) im bereich von 1-5 liegt und beide zeilen mit A beginnen.

meine fragen sind:

1. mit welchem befehl kann ich so grosse textedateien am besten durchlaufen? schnelligkeit ist nicht wichtig, aber mit zeilenweisem lesen schmiert mein PC ab

2. ist es ok sich die 1. zeile aus datei 1 rauszupicken, dann die ganze datei 2 nach übereinstimmungen abzusuchen und dann mit der nächsten zeile aus datei 1 fortzufahren und wieder datei 2 komplett zu durchlaufenb? das hört sich für mich sehr umständlich an, gibt es da bessere ansätze?
da die dateien ungeordnet sind, kann ich nicht zeile 1 aus datei 1 mit zeile 1 aus datei 2 vergleichen, da würde ich nicht alles finden...

danke!

 

[bone2]

wie liest du die denn zeilenweise ein?

 

[SlaterB]

die Information zum Inhalt ist leider nur begrenzt vorhanden,
z.B. wäre es spannend ob es in Datei 1 mehrere Zeilen mit Intervallen zu A gibt (für 1 GB gibts kaum genug verschiedene Anfangsbuchstaben),
und wie diese Intervalle dann ausfallen, 1-5, 1-10, 1-15, oder eher 1-5, 7-9, 400-410?

generell kann man versuchen, erst eine Datei komplett zu verarbeiten und die enthaltene Information im Arbeitsspeicher geeignet ablegen,
z.B. eine Map Buchstabe -> Intevall oder mehrere Intervalle,
oder andersrum arbeiten, erst Datei 2 durchlaufen und dann eine Map Buchstabe -> Liste aller Zahlen,

bei GB großen Dateien kann das die Grenzen des Arbeitsspeichers überschreiten, anderseits hast ja viel Text zu ignorieren,
wenn du den jeweiligen Text pro Zeile oder allein die Zeilennummer als zusätzliche Info brauchst, dann musst du eben entsprechend mehr speichern


auf diese Weise musst du nicht für jede Zeile die andere Datei komplett durchlaufen,
die Arbeitszeit kann sich um den Faktor 1 Mio. und mehr verbessern, je nachdem wie schlimm es vorher war

falls nicht alles passt, kann man auch schrittweise vorgehen: immer 10.000 Zeilen einer Datei analysieren, dann die zweite Datei durchlaufen,
dann weitere 10.000 Zeilen der ersten Datei usw.
besser als für jede Zeile einzelne die zweite Datei komplett durchzuackern


edit: die Textdateien zu sortieren wäre natürlich auch eine naheliegende Unterstützung,
dann ist schrittweise Durcharbeitung beider Dateien gleichzeitig möglich,
nur ist die Sortierung selber von GB-Dateien auch nicht ganz trivial

 

[RySa]

Ich hab angefangen es zu "bauen" und habe dann festgestellt, dass ich doch zu wenig Info habe ^^ also eine 1GB Datei, bei der sich A's nicht wiederholen (zumindest bei der ersten Datei mit den Bereichen 1-5 etc) ist unmöglich, daher kann man nicht eindeutig prüfen, ob sich die Sachen aus der 2. Datei in den Intervallen von der ersten befinden, da es z.B für A sowohl den Bereich 1-5 als auch vielleicht den 5-17 geben kann. Mehr info ?


Also hier vielleicht so ein kleiner Schubser ( wie, und wie viel Daten du ausließt, überlasse ich dir):

	public static void main(String[] args) {
		String s1 = "A text text 1 5 text text \nB text 3 9 text text \nQ text text 27 873 text";
		String s2 = "C text text text 38 text \nA text 3 text text \nA text text 8 text text";
		Pattern pattern = Pattern.compile("(?s)([A-Z]).*?(\\d+)\\s*(\\d+)?.*?");
		Matcher datei1 = pattern.matcher(s1);
		Matcher datei2 = pattern.matcher(s2);
		while (datei1.find()){
			while (datei2.find()){
				if (datei2.group(1).equals(datei1.group(1))){
					int rangeMin = Integer.valueOf(datei1.group(2)).intValue();
					int rangeMax = Integer.valueOf(datei1.group(3)).intValue();
					int number = Integer.valueOf(datei2.group(2)).intValue();
					if (number >= rangeMin && number <= rangeMax){
						System.out.println(datei2.group(1)+" mit der Nummer "+datei2.group(2)+" passt zwischen "+datei1.group(1)+" mit dem Intervall "+datei1.group(2)+"-"+datei1.group(3));
					}
					else {
						System.out.println(datei2.group(1)+" mit der Nummer "+datei2.group(2)+" passt nicht zwischen "+datei1.group(1)+" mit dem Intervall "+datei1.group(2)+"-"+datei1.group(3));
					}
				}
			}
		}
	}

 

[turtle]

das hört sich für mich sehr umständlich an...

Für mich auch

Kannst Du die Dateien nicht vorher sortieren?

Dann vermute ich, dass die Textdateien über SQL gelesen werden können. Und mein Lieblings-Framework mybatis kennt das Konzept des Resulthandlers, in dem nur eine Zeile aus dem Resultset im Speicher gehalten wird.

Und damit solltest Du über die sortierte Liste von Datei-2 iterieren können.

 

[latoureiffel]

danke schonmal für eure beiträge.

zur frage wie ich einlese:
mittels buffered reader der jede zeile einzeln einliest, aber mein pc hängt sich auf.
oder kann der buffered reader mit so grossen dateien umgehen und es liegt am PC? ich kenne mich da nicht so aus, deswegen die frage wie man die riesendateien am besten einliest.

zur datei 1 und ihr aufbau:
auch hier können sich die buchstaben wiederholen, das hätte ich vielleicht deutlicher machen sollen. ich wollte nur das beispiel kurz halten.
also es ist so dass es zb. 5000 zeilen gibt die mit A beginnen, dann 3 mit F, 20300 mit C, wieder 3000 mit A usw. also schön durcheinander. und die dateien sind wirklich so gross ich habe mal die zeilen zählen lassen (mittels less im terminal und auch da war der pc schon schön ausgelastet) : für eine datei waren es zb. über 3.000.000.000 zeilen.
deswegen geht das mit jeweils 10.000 zeilen lesen wie du (slaterB) es gesagt hast, wohl eher nicht, weil ich dann ja nur die 10.000 zeilen miteinander vergleichen kann... es kann ja aber sein, dass die zahl die in mein intervall aus zeile 1 der datei 1 fällt, am ende von datei 2 liegt.
in den arbeitsspeicher lesen geht auch nicht (denke ich), wie gesagt, mein PC hängt sich dann auf und ich bekommen "kein speicher"-fehler.

zu den intervallen/zahlenbereichen:
die bewegen sich eher in hohen bereichen (1.000.000 - 1.000.020 zb. aber auch 20.000 - 20.002) und sind meist so 10-20 stellen lang (also zb. 4.000.020 - 4.000.030 oder so). aber ist das wichtig zu wissen? die grundfrage bleibt ja die gleiche: gibt es in datei 2 eine zeile die mit dem gleichen buchstaben wie eine zeile in datei 1 beginnt UND deren zahl in das intervall von der zeile in datei 1 fällt? (wenn ja, dann will ich beide zeilen mit println ausgegeben haben, wenn nein, weitersuchen). am ende eines tages mag ich dann eine auflistung der zeilen haben, die übereinstimmen.
bisher habe ich noch nichts gefunden, dass sich zwei zeilen (aus datei 1) in ihrem intervall überlappen, aber vielleicht ist das auch möglich. aber ich denke nicht, dass das wichtig ist. ein fund ist ein fund
ich hoffe es ist jetzt klarer was ich meine, mein deutsch ist leider nicht so gut.

und danke für dein beispiel rysa, ich schaue mir das an!

sortieren wäre auch eine idee. aber das müsste ich ja dann zweifach mache: zuerst nach dem buchstaben sortieren und dann nach der nächsten zahl. aber dann hätte ich beide dateien aufsteigend und dann kann ich vielleicht nachher besser suchen?
mit welchem befehl kann man das tun? ich habe schonmal etwas sortiert, aber da mit collections.sort und das was ich sortiert habe, war eine arraylist. aber mein file ist einfach nur text, getrennt durch leerzeichen und tab und am ende newline. das kann ich ja hier nicht anwenden...

 

[latoureiffel]

kann leider nicht editiren!

wollte nur sagen, dass jetzt beide dateien ca. 3 GB gross sind. mehr wird es aber nicht werden, das ist die endgültige grösse.
ändert an meinem problem aber gar nicht, nur vielleicht ist das für euch als information wichtig?

 

[SlaterB]

zur frage wie ich einlese:
mittels buffered reader der jede zeile einzeln einliest, aber mein pc hängt sich auf.
oder kann der buffered reader mit so grossen dateien umgehen und es liegt am PC? ich kenne mich da nicht so aus, deswegen die frage wie man die riesendateien am besten einliest.

BufferedReader schafft vielleicht 100 MB pro Sekunde, egal ob die Datei 100 MB oder 100 TB groß ist,
deswegen war ja nach Code gefragt,
übe evtl. auch zunächst an kleineren Dateien

deswegen geht das mit jeweils 10.000 zeilen lesen wie du (slaterB) es gesagt hast, wohl eher nicht, weil ich dann ja nur die 10.000 zeilen miteinander vergleichen kann...

mein Vorschlag war nicht, 10.000 Zeilen von A mit 10.000 Zeilen von B vergleichen,
sondern 10.000 Zeilen von A einzulesen und dann das gesamte B zu durchlaufen,
das ist je nach Gegebenheiten 10.000x schneller als erst eine Zeile von A einzulesen, dann komplett B durch, dann die zweite Zeile von A und wieder komplett B durch usw.,
falls man es geschickt anstellt

 

[RySa]

Ja mein Beispiel (so wie es jetzt ist) wird scheitern, da du zu den Zahlen auch Punkte hast (also z.B 1.000.000 , und da müsste es man überarbeiten und vor dem casten nochmal alle . entfernen und ggf. alle , mit . ersetzen (falls du auch nachkommastellen hast).

Und noch eine Frage, sind in dem Text auch Zahlen enthalten ? Also da, wo du jetzt text text text stehen hast. Wenn ja, dann ändert das auch wieder vieles...

 

[turtle]

das hört sich für mich sehr umständlich an...

Für mich auch

Meine 2 Cents

Kannst Du die Dateien nicht vorher sortieren?

Dann können die Textdateien über SQL verarbeitet werden. Und mein Lieblings-Framework mybatis kennt das Konzept des Resulthandlers, in dem nur eine Zeile aus dem Resultset im Speicher sein muss.

Und damit solltest Du über die sortierte Liste von Datei-2 iterieren können.

 

[turtle]

Sorry für meinen Doppel-Post.

hatte gerade PC-Probleme und war nicht sicher, ob mein Post schon durchgegangen war.

 

[vanny]

Warum suchst du nicht in Datei 1 erstmal alle "A" raus und vergleichst die dann mit Datei 2 (und das am besten nach SlaterB in Intervallen).
Wenn "A" fertig ist, nimmste "B" usw.

Hier gehts ja anscheinend nich um performance in Sachen speed sondern ums Speicherhandling.

 

[SlaterB]

'alle 'A' rauszusuchen' wäre quasi mein Intervall, damit dann EINMAL die gesamt Datei 2 durchlaufen,

erst alle 'A' aus Datei 1 und dann bei der zweiten Datei noch irgendwie mit Intervallen anfangen, da sehe ich keinen Sinn

 

[RySa]

Du könntest auch mit Hilfe von Regex sich, wie der SlaterB schon sagte, zuerst alle A's rausholen aus der ersten Datei. Dann alle A's aus der zweiten Datei, vergleichen welche A's aus der zweiten, zu irgendeinem A von der ersten Datei passen, und den Rest als nicht passend ansehen. Dann folgen alle B's aus der 1. und alle B's aus der 2. Datei und wieder das gleiche. Jetzt kann das ganze natürlich wegen dem HeapSpace problematisch werden. Alternativ kannst du wirklich auch für jede Zeile aus der ersten Datei, die gesamte 2. Datei durchlaufen und prüfen (du hast ja gesagt, dass Performance nicht von Bedeutung ist ^^). Oder du speicherst dir immer sagen wir mal 10.000 Zeilen aus der ersten Datei in einer List, und läufst dann die ganze List durch, für jede Zeile der 2. Datei.

Ich finde an sich diese "Aufgabe" blöd....wieso soll es beliebig viele A's geben die verschiede Intervalle haben. Wieso werden dann die ganzen A's aus der ersten Datei, nicht zu einem gemeinsamen A zusammengepackt, bei dem die Intervalle auch zusammen "schmelzen". Oder hängt das mit dem dazugehörigen Text zusammen ?

 

[latoureiffel]

die aufteilung nach buchstaben werde ich mir vornehmen, das ist eine gute idee! da stand ich wohl auf dem schlauch. kann noch nicht vorhersehen, wie viele zeilen tatsächlich dann für einen buchstaben gelten, aber ich hoffe, dass ich da nicht wieder speicherprobleme bekomme. aber das geht nur durch ausprobieren.

sortieren abe ich gerade wieder verworden, das scheint bei so grossen textdateien gar nicht leicht zu sein!
im grunde muss es ja auch ohne sortieren gehen aber wenn ich sortieren könnte, dann könnte ich lesen der datei abbrechen, sobald ein neuer buchstabe auftritt. klingt besser als für jeden buchstaben komplett zu durchlaufen. oder kann mir da noch jemand einen anschubs geben wie man 3 GB sortiert? habe nur ziemlich komplizierte sachen gefunden, ich dachte das geht mit einem einfachen befehl oder so...
aber wie geschrieben, wie lange das programm zum rechnen braucht, ist nicht wichtig (gut, es sollte nicht tagelang dauern, aber ich habe keine vorstellugn davon, wie lange sowas generell dauert. es ist das erste mal, dass ich mit so grossen dateien arbeite)

da ich das alles sehr abstract beschrieben habe, klingt die aufgabe wohl blöd, aber das ist sie nicht
aber ihr könnt es euch so vorstellen: ihr habt X viele zahlenstrahle (benannt mit A, B auch mal AC oder so usw. aber diese buchstaben sind mir alle bekannt), die gehen zb. von 1 - 5.000.000 (achso, die zahlen die mich in der datei interessieren, haben keine punkte. die schreibe ich nur hier zu übersicht, finde ich für grosse zahlen besser lesbar) oder von 1 - 8.000.000.
und auf diesen strahlen gibt es bestimmte intervalle, die mich interessieren KÖNNTEN(warum, ist ja jetzt egal, sonst braucht es einen neuen topic ). also zb. auf strahl A der bereich von 10 - 20. und dann noch ganz viele andere, zb. 4.000 - 4.030.
und gespeichert sind diese infors in datei 1 so:
A 100126100 100126103 *und hier ganz viel text der mich nicht interessiert*
heisst, hier interessiert mich VIELLEICHT ein 3-stellen langes intervall.

und jetzt komtm datei 2 in spiel:
WENN hier etwas zu finden ist, dass in das intervall von datei 1 passt, dann ist die stelle für mich interessant und ich will die zeilen die es betrifft ausgegeben haben. das wäre zb. der fall, wenn datei 2 folgende zeile enthälte:
A 100126102 *und hier ganz viel text der mich nicht interessiert*

so. und wie oft das in meiner datei vorkommt weiss ich nicht. aber die stellen will ich eben finden, ist euch mein problem jetzt klarer?
das hauptproblem ist aber momentan einfach, wie ich diese riesigen dateien handle, denn das kann ich nicht. ich habe schon 2 kleine beispieldateien gemacht mit nur wenigen zeilen und kilobyte um nachher zu testen ob mein programm wirklich alles findet und auch keine false-psitives liefert, ABER before ich nicht weiss wie ich die grossen dateien durchsuchen kann, ohne meinen PC aufhängen zu lassen, brauche ich auch die kleinere nicht zu testen... (da würde ich einfach alles in eine string oder list speichern und dann mit regex udn schleifen absuchen. aber bei insgesamt 6 GB geht das natürlich nicht).

ich mache mich jetzt daran, die dateien nach buchstaben aufzuteilen und diese "packete" miteinander zu vergleichen. drückt mir daumen

 

[latoureiffel]

ohoh, habe ein fehler entdeckt:

und gespeichert sind diese infors in datei 1 so:
A 100126100 100126103 *und hier ganz viel text der mich nicht interessiert*
heisst, hier interessiert mich VIELLEICHT ein 3-stellen langes intervall.

das intervall ist 4 stellen lang, nicht 3: 100126100, 100126101, 100126102, 100126103.

 

[SlaterB]

> da würde ich einfach alles in eine string oder list speichern
viele Strings zusammenzufügen ist eine der größten Bremsen, die man leichtfertig einbauen kann

public class Test {
    public static void main(String[] args)  {
        String st = "";
        StringBuilder stb = new StringBuilder();
        long time = System.currentTimeMillis();
        for (int i = 0; i < 25000; i++) {
            st += String.valueOf(i);
            // stb.append(String.valueOf(i));
        }
        System.out.println("fertig " + (System.currentTimeMillis() - time));
    }
}

das eine dauert fast 7 Sekunden, das andere nicht messbar 0 ms

es ist nicht erkennbar ob deine erneute Frage zum Einlesen nur rhetorisch war,
falls ans Forum gerichtet gilt nach wie vor: Code Code Code posten

 

[RySa]

Also angenommen diese Buchstaben, sind immer groß geschrieben, die Zahlen enthalten keine Punkte oder Leerzeichen, dann gilt folgender Regex:

Pattern pattern = Pattern.compile("([A-Z]+).*?(\\d+)\\s*(\\d+)?.*?");

Dazu kommt, dass du die Zeilenangabe für die Treffer brauchst (ich nehme an, von beiden Dateien, oder soll da stehen, "A mit 5" aus der Zeile "x" passt zu "A mit 3 6" in der Zeile "y")
Du wirst bei so großen Dateien vermutlich nicht in der Lage alle gleichen Buchstaben auf einmal zu laden(zumindest bei der defaultgröße des Heap Spaces).

Also ich würd so vorgehen:

1. Du brauchst die großen Dateien nicht nach Buchstaben zu splitten, du lädst einfach nur aus der ersten Datei dir maximal 10 000 Zeilen auf einmal aus. Lässt dir ein Index laufen, den du bei readLine() hochzählst, und über den du bestimmen kannst, welche Zeile es gerade ist (für die Ausgabe nachher oder sonst was).

2. Dann gehst für jeden Satz von 10 000 Zeilen, die ganze zweite Datei, Zeile für Zeile durch, und überprüfst über die Regex (so ähnlich wie in meinem Beispiel paar Posts höher) ob das zutrifft, wenn ja, machst das was du da damit machen willst, wenn nicht, gehste einfach weiter und löschst aus der List, die aktuelle, schon überprüfte Zeile (weil die 10 000 Zeilen sich am besten in einer List befinden sollten).

3. Wenn die Liste leer ist, holst dir die nächsten 10 000 Zeilen und machst das gleiche.

Ich denke das sollte funktionieren (wird nicht besonders schnell aber was solls )

 

[vanny]

...
erst alle 'A' aus Datei 1 und dann bei der zweiten Datei noch irgendwie mit Intervallen anfangen, da sehe ich keinen Sinn

naja hab ich blöd geschrieben ich meinte mit interval natürlich für die "A"s nich für Datei 2 ^^