Hallo,

ich arbeite grade an einem Programm, das Dateien, egal ob Text oder Binar nach
Wörten abgrasst, die bestimmten Normen entsprechen. Sprich,
die nach logischer erkenntnis ein Wort ergeben/sein könnten.

Wenn ein wahrscheinliches Wort gefunden wurde, wird dieses in einer TList gesucht.
Wenn es gefunden wird, wird sein Zähler weiter gezählt. Ansonsten in die Liste aufgenommen. Mal abgesehn davon, das die suche in der TList schon bei 10.000 Einträgen sehr langsam wird, hängt sich mein Prog bei rund 49.000 Einträgen auf.

Arbeitsspeicher ist genügend da. (Das Prog hat bis zum Crash nur 36MB RAM verbraucht)

An der Begrenzung von Integer-Typen kann es eigentlich auch nicht liegen, da
selbst Word(16-bit) bis zu 65.535 geht.

Das Programm soll später mal das Internet abgrassen, wie ein ROBOT, und somit ein wirklich repräsentatives Wörterbuch erstellen. Was auch nicht gebräuchliche, zb.: Wissenschaftliche oder Technische Begriffe enthält.
(Frei nach dem Motto, wenn ein Wort
9 Millionen mal gefunden wurde, wird es schon eins sein)


Wäre nett wenn mir jemand Helfen kann. Eventuell auch zur schnelleren Überprüfung von vorhandenen Einträgen.


MfG Gothicware


Moderiert von Gausi: Topic aus VCL (Visual Component Library) verschoben am Mo 21.02.2005 um 17:59

Morgen !

Wenn du Pech hast (falsches Betriebssystem etc.) passiert das bei genau 32768 Einträgen. Um das zu vermeiden könntest du TStringList.Capacity mal in der OH nachschlagen...

AXMD

Was Du brauchst sind Hash - Lists, welche z. B. in der Unit INIFILES oder in der Komponentensammlung Jedi enthalten sind. Damit kannst Du sehr schnell durch große Datenbestände suchen.

Gruß
KidPaddle

Vielleicht wären für die Verwaltung und Suche Deiner Daten B-Bäume ganz interessant.
Das Eintragen eines neuen Textes wäre zwar etwas langsamer als in einer linearen Liste,
aber die Suche ginge dann recht flott von statten.

Ich glaube, ich habe irgendwo hier im Forum schon mal Units mit Funktionen gesehen,
die den Aufbau von solchen Bäumen erleichtern. Falls nicht und Du daran solltest
Interesse haben solltest, meld Dich einfach kurz, ich schau dann nach was ich zuhause
zu diesem Thema finden kann.

Danke erstmal für eure Antworten.

@AXMD:
Wie ist das zuverstehen, mit dem Einschnitt durch das OS?
Das ganze soll unter W2k Sp4 und Win-XP Sp1/2 laufen.
Man ist unter Windows zwar einiges gewöhnt, aber Micro$oft könnte ja wenigstens einige Dinge Standariesieren.

@KidPaddle:
Das mit denn HASH hatte ich mir schon mal angeschaut gehabt. Aber wirklich
kapiert habich das nur im Groben. Es wird irgentwie ein Schlüssel zu jeden Eintrag
in einem Array(was schon ein Problem wäre, weil so weit ich weis, nicht Dynamisch),
und man ermittelt anhand des Schlüssels die Relative Position, und prüft dadurch nur einen kleinen Teil. Aber das umsetzen, ist irgentwo Spanisch für mich.
Aber vielleicht hat, oder macht mal jemand eine VCL THashList die alle Funktionen
von TList erbt, und die Hash Funktion beinhalted.

@Wizard of OS :
B-Bäume?? Da denk ich eher an nen Wald. *lol*
Ne, mal im Ernst, wie Funktioniert das im Groben??
Sortiere ich die Einträge dann zb.: Nach jedem Anfangsbuchstaben in einer Extraliste,
so das sich in Etwa die zudurch suchenden Einträge durch 26 Teilen???
Damit wäre das grösse der Liste Problem auch noch nicht ganz gelöst, da ich
alle in einer brauche. Denn es müssen die Einträge auch nach relevants angezeigt werden können.

Hier mal eine Beispiel Liste:

000002# and
000002# aus
000002# Einträge
000002# htmkIm
000002# ist
000002# mal
000002# mit
000002# net
000002# nicht
000002# scout
000002# und
000002# Web
000002# Weitere
000003# Aber
000003# Ergebnisse
000003# ich
000004# Roman
000004# zum
000005# die
000006# der
000006# George
000006# und
000007# das
000007# Seiten
000007# von
000008# Cache
000009# Ähnliche
000009# Download
000010# Orwells

So werden die Einträge in der Liste gehand habt. Damit ich die auch finde, gibt es dazu eine zweite Liste, mit denn selben Einträgen, nur ohne Zähler.

Gruss Gothicware

Zu den B-Bäumen sag ich mal was. Also ein Baum (erstal allgemein ein Baum, was ein B-Baum ist, kommt gleich) in der Informatik sieht so aus: (direkt spezialisiert auf Suchprobleme)

Man hat ganz oben einen Knoten, den man Wurzel nennt. In diesem Knoten ist z.B. eine Zahl gespeichert, oder ein String, oder ein anderes Objekt. Dieser Knoten hat dann mehrere Söhne, was auch wieder Knoten sind, in denen was gespeichert ist. Diese Knoten haben wieder Söhne usw. usf.

Ein Suchbaum sieht nun so aus, dass jeder Knoten höchstens 2 Söhne hat. Wenn man in diesem Suchbaum nun etwas suchen und finden möchte, dann macht man das so: Vergleiche das Element mit dem der Wurzel. Ist das gesuchte größer, suche rechts weiter, ansonsten links.

Bei großen Datenmengen gibt es dabei ein Problem. Die Bäume werden sehr hoch. Und wnn der ganze Baum nicht in den RAM passt, wird das durchsuchen u.U. sehr langsam, weil beim Suchen der Buam komplett von oben nach unten durchsucht werden muss, und evtl. häufig auf die HD zugegriffen werden muss.

Dafür gibt es B-Bäume. Ein B-Baum speichert in jedem Knoten mehrere Elemente (z.B. in einem Array oder Liste). Und jeder Knoten hat da nicht 2 Söhne, sondern mehrere, nämlich genau einen mehr, als er Elemente speichert. Normalerweise so um die 100. Die Suchbaumeigenschaft ibt es auch bei B-Bäumen. Jeder Nachfolger hängt ja "zwischen 2 Elementen". Und in diesem Knoten und sienen Nachfolgern werden nur Elemente gespeichert, die auch tatsächlich in der Sortierung zwischen diesen beiden Elementen stehen.
In einem B-Baum sucht man dann so, dass man die Stelle in dem Array des Knoten herausfindet, zwischen denen das gesuchte Element steht. Dann sucht man in dem Sohn weiter, der "zwischen den beiden" hängt.
Der Vorteil liegt darin, dass die Höhe des Baumes auch bei sehr großen Datenmengen sehr klein bleibt:
In die erste Stufe passen 100 Elemente, in die zweite 100*100=10.000, in die nächste 10.000*100= 1000.000 und in die vierte 100.000.000 Um ein Element zu suchen, muss dann nur 4 mal auf den (langsamen) Hintergrundspeicher zugegriffen werden.

Ansonsten mal danach Googlen. da findest du bestimmt das eine oder andere Informatik-Skript, was das genauer erläutert.

Edit: Aber das ist ja eigentlich kein VCL-Problem. *verschieb*

Die VCL stellt bereits Hash-Listen zur Verfügung:
- TBucketList
- TObjectBucketList
- THashedStringList

Also Baum Strucktur scheint mir doch zu schwer für meine Zwecke, da die Einzelelnen Strings, nicht wirklich einen Zusammenhang untereinander haben. Würde sich vielleicht lohnen, wenn ich nach der Häufigkeit abgrasse, aber ich will ja nur nach dem vorhanden sein eines Strings schauen.

@Mozi:
Die Sache hat nur einen Winzigen Hacken, ich hab dummer Weise meine Delphi 5 Prof. in einen Slot-In Drive zerschrottet, und hab bis jetzt kein Ersatz dafür. Somit Arbeite ich mit meiner alten Delphi 4 (Client/Server). THashedStringList gibts aber erst ab Delphi 5, oder????

Vielleicht, kann mir jemand das mal aus der Enstsprechenden Unit von Delphi,
als Singel-Unit schreiben, und mir Posten. Ich würde dann auch selber versuchen es mir Abwärtz zu übersetzen. Oder kennt jemand ein Link, wo das für Delphi 4 schon gibt? Hab noch nichts beim Metageren gefunden .

Uff! TList (oder andere Klassen, die schneller durchsucht werden können) mit mehreren Mio. Einträgen!

Weißt du eigentlich was das bedeutet

Eine TList enthält nicht die Einträge selbst, sondern die Zeiger auf die Einträge. Und alle anderen genannten Alternativen vermutlich auch!

Um über den benötigten Speicher sinnvolle Aussagen zu machen, ist der Speicherbedarf der TList selbst nur die eine Sache. Die Einträge selbst verbrauchen erheblich mehr Speicher.

Also solltest du dir zunächst mal Gedanken machen, wie du deine Einträge speicherst.
Als string gespeicherte Einträge werden von einem Objekt (Typ string) verwaltet, das selbst ein paar Bytes verbraucht. Dann hat es noch einen Zeiger auf einen Speicherbereich, der die eigentlichen Daten enthält. In der TList würde der Zeiger auf das Objekt stehen und dort dann der zum Text!

Also hier ist schon mal ein riesiges Einsparpotential.

Die Darstellung als Shortstring schneidet hier schon mal besser ab. Da steht dann im Speicher ein Byte für die Länge und dann die Textzeichen. Das mit der Länge im ersten Byte ist für dich von besonderem Interesse! Gleiche Worte haben auch die gleiche Länge! Beim Vergleich kann also schon viel Zeit gespart werden, wenn ich nur die Worte gleicher Länge vergleichen muss.

Also wäre es möglich, verschiedene Listen für verschiedene Längen einzusetzen. Aber wenn ich schon weiß wie lang das Wort ist, dann brauche ich auch das Längenbyte nicht mehr! Gespeichert werden muss nur noch der Text selbst! Besser geht es nur noch mit Komprimierung. Aber auch das ist hier durch aus einfach und sinnvoll zu machen. Die Idee des Morsecodes: Die beiden häufigsten Zeichen werden duch ein Bit (0 oder 1, Pause) dargestellt. Egal welchen Komprimierungsalgorithmus du verwendest, wichtig ist, dass du bei der Suche nicht dekomprimierst, sondern das gesucht Wort komprimierst und dann suchst.

Es bleibt das Problem, das eine TList eine maximale Kapazität hat.
Intern verwendet TList eine TPointerList; In den verschiedenen Units findet sich:


Also ist bei einer Liste nach 13.421.772 Zeigern Schluss. Aber das Prinzip, mehrere Listen einzusetzen, ist ja noch nicht ausgereizt. Wenn du z.B. 256 Listen verwendest, dann kannst du das erste Byte weglassen und einer Liste zuordnen. Das beschleunigt die Suche und reduziert den benötigten Speicher, besonders weil wir den Text ja schon komprimieren, bevor wir ihn in der Liste speichern!

Nach diesem Schema lässt sich alles unendlich fortsetzen. Die bleibende Grenze liegt dann nur im RAM. Alle anderen Verfahren, die nicht im RAM laufen werden sehr viel langsamer.

Darum folgende Strategie: Beschränke die Suche auf Teile, die auf einmal in den Speicher passen und wiederhole die Suche für alle Teile. Und als Konsequenz: Programmier nicht alles und nutze nur einen Teil, sondern halte das Programm einfach und nutze es mehrfach! Heute suchen wir nur Worte, die mit A anfangen, morgen dann die mit B usw.! Bei Bedarf auch gerne feiner eingeteilt
(Erst Worte mit n Buchstaben (a, b, ..., z), dann mit n+1 (a, b, ..., z).

Lass den Rechner rechnen, statt dir den Kopf zu zerbrechen!

Zur Sortierung noch folgendes. Eine TList lässt sich auch sortieren. Dazu wird die Vergleichsfunktion selbst definiert und die Liste mit dem schon eingebauten Quicksort sortiert.
Also schon ganz komfortabel.

In einer sortierten Liste kannst du dann aber z. B. mit dem Halbierungsverfahren suchen:
Erster Suchschritt: Vergleich mit dem Eintrag in der Mitte der (benutzen) Liste. Wenn der neue Werte kleiner ist, das ganze mit der ersten Hälfte wiederholen, wenn größer, mit der zweiten.
Das ist so gut wie ein Binärbaum!

Vorsicht aber beim Sortieren mit Quicksort, das Verfahren ist rekursiv! Es gibt unter Delphi ein mitgeliefertes Beispiel ThrdDemo, bei dem drei Sortierverfahren grafisch dargestellt und zeitlich verglichen werden. Das zweitschnellste Verfahren Selectionsort ist nicht rekursiv und könnte deshalb die bessere Wahls sein (und den Quellcode dazu hast du dort).

Bin schon auf das Wörterbuch gespannt!

@wdbee: Besonders viel zur Klärung trägt dieser sehr lange Beitrag nicht bei. Natürlich ist es sinnvoll, sich bei diesen Massen auch Gedanken über die effiziente Speicherung der Daten zu machen. Aber was die Datenstruktur angeht, wurden schon bessere Vorschläge gemacht.

Zitat:

Zur Sortierung noch folgendes. Eine TList lässt sich auch sortieren. Dazu wird die Vergleichsfunktion selbst definiert und die Liste mit dem schon eingebauten Quicksort sortiert. Also schon ganz komfortabel. In einer sortierten Liste kannst du dann aber z. B. mit dem Halbierungsverfahren suchen: Erster Suchschritt: Vergleich mit dem Eintrag in der Mitte der (benutzen) Liste. Wenn der neue Werte kleiner ist, das ganze mit der ersten Hälfte wiederholen, wenn größer, mit der zweiten. Das ist so gut wie ein Binärbaum!

Prinzipiell ist das gut, aber bei sehr vielen Daten wird auch das unpraktikabel, da man sehr häufig aus dem Hintergrundspeicher (Platte, CD, etc.) nachladen muss, wenn die Liste nicht komplett in den RAM passt. Daher der Hinweis zu B-Bäumen, die dabei wesentlich schneller sein dürften (wenn auch komplizierter zu programmieren)

Zitat:

Vorsicht aber beim Sortieren mit Quicksort, das Verfahren ist rekursiv!

Das ist nicht das Hauptproblem. Quicksort kann im schlimmsten Fall sehr lange dauern. Bei 1.000.000 Einträgen kann Quicksort auch mal ca. 1.000.000.000.000 Vergleiche benötigen.

Zitat:

Das zweitschnellste Verfahren Selectionsort ist nicht rekursiv und könnte deshalb die bessere Wahls sein (und den Quellcode dazu hast du dort).

Das ist ein glatte Falschaussage. Selectionsort (zumindest das, was ich darunter verstehe), ist immer das schlechteste Sortierverfahren. Bei diesen Datenmengen ist es absolut unpraktikabel.

@Gausi: Klar geht das auch alles viel besser und komplexer. Aber nach dem was oben so hin und her ging, habe ich den Eindruck, das einfach zu programmierende Verfahren mit Delphi-Bordmitteln (und dort verfügbaren Quellen) diesem Anwender leichterfallen könnten.

Deshalb auch der Vorschlag, das Programm einfach zu halten und die Suche aufzuteilen. Teile und herrsche, während andere noch programnmieren!

Als zweitschnellstes Verfahren habe ich das von den dreien bezeichnet, was in diesem Beispiel nach Quicksort als zweiter durch Ziel geht! Das war also nicht als allgemeingültige Wertung gemeint!

Erstmal Uff, und Danke.

Ich glaube ich sollte mal klarstellen, das ich auch eine VCL-Unit brauche, die mir die Einträge dann Anzeigt. Denn ich will das Wörterbuch
durch stöbern, und auch gleich sehen welche Wörter am heufigsten vorkommen.
Und das Runtime. Aber ich merk schon, irgentwo findet alles sein Ende.

Also ich werd jetzt mal Alphabetisch Listen Trennung vornehmen. Und eine Extraliste für die Top 100 Wörter. Das sollte vorerst mein Problem lösen.
Fürs durch stöbern muss ich dann wohl auf ein BigMemo zurückgreifen.

Aber nochmal eine andere Frage, wegem Sortieren. Wenn ich wegen Rechenzeit einsparerns, die Strings als nicht Kompriemierte Strings lasse, was wäre dann
so für meine Zwecke die schnellste Suche(auch ohne Hash) ???

Gruss Gothicware

Die VCL-Komponenten wie Memo verwenden für die Anzeige in der Regel intern Listen vom Typ TStringList, die die gleiche maximale Länge haben können wie TList.

Mach dir ein Register für den Anfangsbuchstaben, dann kannst du so deine 26 Listen (plus deine Top 100-Liste und ggf. Sonderzeichen) umschalten wie in einem Wörterbuch. Später kannst du das ja weiter unterteilen.

Zum Thema sortierte Liste und Suchen gibt es gerade eine eigene Diskussion unter Allgorithmen, Optimierung und Assembler: Schnelles Finden in TList mit Suche und schnellem Einfügen in sortierte Listen! Schau dir das doch an!