 |
Das deutsche QBasic- und FreeBASIC-Forum
Für euch erreichbar unter qb-forum.de, fb-forum.de und freebasic-forum.de!
|
| Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
| Autor |
Nachricht |
proXy
Anmeldungsdatum: 29.01.2007
Beiträge: 6
|
 Verfasst am: 29.01.2007, 00:29 Titel: anzahl der zeichen im einem string zählen |
 |
|
Hallo zusammen......
Ich hab mich, nachdem ich mich etwas mit qbasic beschäftigt hab, mal an ein kleines programm gemacht, das die anzahl der zeichen eines strings zählen (und später dann noch nach häufigkeit ordnen) soll:
| Code: | DECLARE SUB zaehlen ()
DIM SHARED anzahl%(126)
CLS
PRINT "HUFFMANN-CODE:"
PRINT "=============="
PRINT
INPUT "Text eingeben:", text$
CALL zaehlen
REM CALL ordnen
PRINT anzahl%(97)
PRINT anzahl%(98)
PRINT anzahl%(99)
PRINT anzahl%(100)
SUB zaehlen
FOR i = 1 TO LEN(text$)
zeichen$ = MID$(text$, i, 1)
anzahl%(ASC(zeichen$)) = anzahl%(ASC(zeichen$)) + 1
NEXT i
END SUB |
Doch ständig wird irgend ein fehler gemeldet, denn ich nach seeehr langem suchen immer noch nicht gefunden hab!  Ich wäre froh, wenn mir diesbezüglich jemand behilflich sein könnte... 
Gruss und Dank im Voraus... |
|
| Nach oben |
|
 |
SpionAtom
Anmeldungsdatum: 10.01.2005
Beiträge: 395
|
| Verfasst am: 29.01.2007, 02:58 Titel: |
|
|
Ganz einfach: Die SUB kannte den Text nicht.
Außerdem hab ich mir erlaubt, die Ausgabe etwas umzugestalten
| Code: | DECLARE SUB zaehlen (text$)
DIM SHARED anzahl%(126)
CLS
PRINT "HUFFMANN-CODE:"
PRINT "=============="
PRINT
INPUT "Text eingeben:", text$
CALL zaehlen(text$)
REM CALL ordnen(text$)
FOR i = 32 TO 126
PRINT CHR$(i); ": "; anzahl%(i),
NEXT
SUB zaehlen (text$)
FOR i = 1 TO LEN(text$)
zeichen$ = MID$(text$, i, 1)
anzahl%(ASC(zeichen$)) = anzahl%(ASC(zeichen$)) + 1
NEXT i
END SUB |
_________________
Inzwischen gehöre ich auch zu den BlitzBasicern. Also verzeiht mir, wenn mir mal ein LOCATE 100, 100 oder dergleichen rausrutscht. |
|
| Nach oben |
|
|
proXy
Anmeldungsdatum: 29.01.2007
Beiträge: 6
|
| Verfasst am: 29.01.2007, 06:50 Titel: |
|
|
Autsch... da hät ich noch lange suchen können.
Danke für deine schnelle Hilfe! |
|
| Nach oben |
|
|
proXy
Anmeldungsdatum: 29.01.2007
Beiträge: 6
|
| Verfasst am: 29.01.2007, 12:41 Titel: |
|
|
Ich melde mich nun doch nochmals zu wort..
Der nächste Schritt soll sein, die arrays nach anzahl der häufigkeit zu ordnen (kleinste anzahl zuerst!).
Ursprünglich wollte ich das prog mit python schreiben. Dort gibt es sogenannte dictionaires (ähnlich arrays) bei denen der schlüssel eine bestimmte position im dictionaire hat und ausserdem ein string sein kann.
Nachdem ich das programm nun aber im qbasic schreiben will, tauchte das problem auf, das arrays als "schlüssel" nur zahlen aufnehmen können. Ich hab kurzerhand den ascii-code genommen. Nun, da ich das ganze nach häufigkeit des zeichens ordnen möchte, stellt dies ein problem dar. Hat jemand eine idee, wie dies zu lösen sein könnte??
PS:
-Später möchte ich die häufigkeiten mehrerer zeichen addieren und dies wiederum speichern. Es soll dabei immer noch "ersichtlich" sein, aus welchen zeichen diese summe stammt... Ich hoffe, keine unlösbare
aufgabe...
-Ich liege in meinem Glauben, dass die "schlüssel" der arrays nur zahlen sein könne, nicht falsch, oder?? |
|
| Nach oben |
|
|
SpionAtom
Anmeldungsdatum: 10.01.2005
Beiträge: 395
|
| Verfasst am: 29.01.2007, 13:00 Titel: |
|
|
Wenn du unter Schlüssel das verstehst, was ich als Index verstehe, so stimmts. Die können nur ganzzahlige Werte sein.
Du kannst dieses Problem umschiffen, indem du ein zweites Array anlegst (oder ein zweidimensionales). Beide Arrays sind gleich lang, in einem steht, um welches Zeichen es sich handelt, in dem anderen steht die Häufigkeit des Zeichens.
| Code: |
dim ArrayZeichen$(26), ArrayHaeufigkeit(26)
ArrayZeichen$(1) = "A": ArrayHaeufigkeit(1) = 5
ArrayZeichen$(2) = "B": ArrayHaeufigkeit(2) = 3
ArrayZeichen$(3) = "C": ArrayHaeufigkeit(3) = 6
.
.
|
_________________
Inzwischen gehöre ich auch zu den BlitzBasicern. Also verzeiht mir, wenn mir mal ein LOCATE 100, 100 oder dergleichen rausrutscht. |
|
| Nach oben |
|
|
dreael
Administrator
Anmeldungsdatum: 10.09.2004
Beiträge: 2531
Wohnort: Hofen SH (Schweiz)
|
| Verfasst am: 29.01.2007, 14:21 Titel: |
|
|
| SpionAtom hat Folgendes geschrieben: | | Ganz einfach: Die SUB kannte den Text nicht. |
Typischer Fall für einen meiner berühmten Artikel:
http://www.dreael.ch/Deutsch/BASIC-Knowhow-Ecke/SUB-Unterprogramme.html
Dort wird sonst das ganze Thema der Variablen-Sichtbarkeiten ausführlich durchgekaut.
| proXy hat Folgendes geschrieben: | | -Ich liege in meinem Glauben, dass die "schlüssel" der arrays nur zahlen sein könne, nicht falsch, oder?? |
Dictionaries kenne ich selber auch und verwende auch ich an vielen Orten noch recht häufig, z.B. Shellscript unter Linux, PHP und VBScript (alle drei beherrschen dies).
Ansonsten hast Du vollkommen richtig erkannt, dass in QB Arrays in dem Sinn nur als starre Gebilde operieren, die man zu Beginn dimensioniert (wobei dies aber auch erst zur Laufzeit geschehen kann - Stichwort REM $DYNAMIC) und nicht in dem Sinn dynamisch wachsen können. REDIM PRESERVE ist in dem Sinn überhaupt nicht mit der dynamischen Speicherverwaltung richtiger Dictionaries zu vergleichen...
Von daher ist für Deine spezielle Anwendung auch der ASCII-Code des Buchstabens noch am ehesten geeignet, z.B.
| Code: | DIM haeufigkeit%(ASC("A") TO ASC("Z"))
FOR i%=1 TO LEN(wort$)
z% = ASC(UCASE$(MID$(wort$, i%, 1)))
haeufigkeit%(z%) = haeufigkeit(z%) + 1
NEXT i% |
Wikipedia: http://de.wikipedia.org/wiki/Assoziatives_Array
_________________
Teste die PC-Sicherheit mit www.sec-check.net |
|
| Nach oben |
|
|
proXy
Anmeldungsdatum: 29.01.2007
Beiträge: 6
|
| Verfasst am: 30.01.2007, 14:12 Titel: |
|
|
Nochmals Danke für eure Hilfe! Ich hätte nicht gedacht, dass es für qBasic noch funktionierende Foren oder überhaupt Programmierer gibt.. 
Ich konnte mein Problem mit eurer Hilfe ohne grössere Zwischenfälle lösen.
Eine kleine Frage hätt ich aber noch: Das Resultat der ganzen Sache ist der String "chiffre$", der beispielsweise so aussieht: 01010001000110110101
Bei Hashsummen (z.B. md5) sieht das resultat ähnlich aus, ausser das es mit den Zeichen des ascii-codes dargestellt wird. Wie läuft diese Umwandlung von binär zu ascii genau ab??
Ansonsten funktioniert meine Huffmankomprimierung (nicht dekomprimierung  ) schon recht ordentlich. Falls sich jemand dafür interessiert:
| Code: | DECLARE SUB ersetzen ()
DECLARE SUB code ()
DECLARE SUB ordnen2 ()
DECLARE SUB ordnen ()
DECLARE SUB zaehlen ()
DIM SHARED anzahluns%(126), symboluns$(126), symbol$(126), anzahl%(126), pfad$(126)
COMMON SHARED n, chiffre$, text$
CLS
PRINT " _ _ ___ ___ ______ _ "
PRINT " | | | | / __)/ __) / _____) | | "
PRINT " | |__ | |_ _| |__| |__ ____ ____ ____ | / ___ _ | | ____"
PRINT " | __)| | | | | __) __) \ / _ | _ \ | | / _ \ / || |/ _ )"
PRINT " | | | | |_| | | | | | | | ( ( | | | | | | \____| |_| ( (_| ( (/_/ "
PRINT " |_| |_|\____|_| |_| |_|_|_|\_||_|_| |_| \______)___/ \____|\___)"
PRINT
INPUT " Texteingabe:", text$
CALL zaehlen
CALL ordnen
CALL code
CALL ersetzen
PRINT
PRINT " Textausgabe:"; chiffre$
PRINT
PRINT " Kompression: x%"
SUB code
FOR i = 1 TO n
pfad$(i) = ""
NEXT i
DO WHILE n <> 1
count = 0
DO WHILE count <> LEN(symbol$(1))
count = count + 1
z$ = MID$(symbol$(1), count, 1)
pfad$(ASC(z$)) = "1" + pfad$(ASC(z$))
LOOP
count = 0
DO WHILE count <> LEN(symbol$(2))
count = count + 1
z$ = MID$(symbol$(2), count, 1)
pfad$(ASC(z$)) = "0" + pfad$(ASC(z$))
LOOP
count = 0
anzahl%(1) = anzahl%(1) + anzahl%(2)
anzahl%(2) = 0
symbol$(1) = symbol$(1) + symbol$(2)
symbol$(2) = ""
CALL ordnen2
LOOP
END SUB
SUB ersetzen
chiffre$ = ""
count = 0
DO WHILE count < LEN(text$)
count = count + 1
z% = ASC(MID$(text$, count, 1))
chiffre$ = chiffre$ + pfad$(z%)
LOOP
END SUB
SUB ordnen
REM Alle Symbole, die im Text vorkommen, werden nach symbol/anzahl uebertragen! n gibt die anzahl der verschiedenen zeichen an.
n = 1
FOR i = 33 TO 126
IF anzahluns%(i) <> 0 THEN
symbol$(n) = symboluns$(i)
anzahl%(n) = anzahluns%(i)
n = n + 1
END IF
NEXT
n = n - 1
REM es wird nun nach haeufigkeit sortiert. (Bubblesort-Algorithmus)
FOR i% = 1 TO n
FOR j% = n TO i% + 1 STEP -1
IF anzahl%(j%) < anzahl%(i%) THEN
SWAP anzahl%(j%), anzahl%(i%)
SWAP symbol$(j%), symbol$(i%)
END IF
NEXT j%
NEXT i%
END SUB
SUB ordnen2
leer = 0
FOR i = 1 TO n
FOR j = n TO i + 1 STEP -1
IF anzahl%(i) = 0 THEN
symbol$(i) = " "
SWAP anzahl%(i), anzahl%(n)
SWAP symbol$(i), symbol$(n)
ELSEIF anzahl%(j) = 0 THEN
symbol$(j) = " "
SWAP anzahl%(j), anzahl%(n)
SWAP symbol$(j), symbol$(n)
leer = 1
ELSEIF anzahl%(j) < anzahl%(i) THEN
SWAP anzahl%(j), anzahl%(i)
SWAP symbol$(j), symbol$(i)
END IF
NEXT j
NEXT i
IF leer = 1 THEN
n = n - 1
END IF
END SUB
SUB zaehlen
FOR i = 33 TO 126
anzahluns%(i) = 0
symboluns$(i) = CHR$(i)
NEXT i
FOR i% = 1 TO LEN(text$)
zeichen$ = MID$(text$, i%, 1)
anzahluns%(ASC(zeichen$)) = anzahluns%(ASC(zeichen$)) + 1
NEXT i%
END SUB
|
|
|
| Nach oben |
|
|
SpionAtom
Anmeldungsdatum: 10.01.2005
Beiträge: 395
|
| Verfasst am: 30.01.2007, 23:14 Titel: |
|
|
Den Ascii-Wert erhälst du ja mit ASC(zeichen$), die Umkehrfunktion dazu ist CHR$(ascii). Dem übergibst du eine Nummer (Integer 0-256).
Umwandlung von Binärzahlen zu Zeichen ist wie folgt: Jedes Ascii-zeichen wird mit 8 Bit verschlüsselt, damit ergeben sich 256 verschiedene Zeichen. Du musst also immer 8 Bit lesen und den Dezimalwert dazu ausrechnen.
Bei der Huffman-codierung ist es aber doch so, dass du die Codierung für die einzelnen Zeichen ausrechnest. Ich erinnere mich noch schwach an diesen Huffman-Baum, mit dem man sowas codieren konnte... Ist leider schon zu lange her für mich, dass ich das gelernt habe^^. Aber das Thema ist interessant, ich werd mich auch mal dran setzen, das zu programmieren.
_________________
Inzwischen gehöre ich auch zu den BlitzBasicern. Also verzeiht mir, wenn mir mal ein LOCATE 100, 100 oder dergleichen rausrutscht. |
|
| Nach oben |
|
|
proXy
Anmeldungsdatum: 29.01.2007
Beiträge: 6
|
| Verfasst am: 31.01.2007, 23:07 Titel: |
|
|
| Zitat: | | Bei der Huffman-codierung ist es aber doch so, dass du die Codierung für die einzelnen Zeichen ausrechnest. Ich erinnere mich noch schwach an diesen Huffman-Baum, mit dem man sowas codieren konnte... Ist leider schon zu lange her für mich, dass ich das gelernt habe^^. Aber das Thema ist interessant, ich werd mich auch mal dran setzen, das zu programmieren. |
Die Huffmancodierung nutzt folgende zwei Gegebenheiten, um Zeichen kürzer zu codieren und somit einen Text zu komprimieren:
1.) In einem Text kommen normalerweise nicht alle Zeichen des Ascii-Codes vor. Lässt man diese nicht verwendeten Zeichen weg, ist es möglich, die verwendeten Zeichen mit deutlich weniger Bits zu codieren. (In einem normalen Text werden kaum mehr als 60 verschiedene Zeichen verwendet. Deutlich weniger als die 256 im Ascii-code )
2.) Einige Zeichen weisen in einem Text eine deutlich höhere Häufigkeit als andere auf. Das "e" wird in einem Text öfters als beispielweise das "?" zu finden sein. Deshalb werden beim Huffmancode die Zeichen je nach Häufigkeit mit einer anderen Länge codiert. Je häufiger ein Zeichen, desto kürzer soll sein Code sein.
Da die verschiedenen Zeichen aber verschieden lange Codes aufweisen, weiss man nicht, wo ein Zeichen aufhört und das nächste beginnt. Deshalb ist zur Entschlüsselung ein sogenannter Huffman-Baum nötig. (Einfach mal googlen, man findet genügend Beispiele )
Man kann für jeden zu komprimierenden Text einen individuellen Baum erstellen, oder einen "Allgemeingültigen", der nach empirischen Erhebungen der Häufigkeit der einzelnen Buchstaben in der deutschen Sprache in einem durchschnittlichen Text, erstellt wurde. (Killersatz.. *ggg*)
Zurück zu meinem Programm: Ein individueller Baum wird in der Subroutine "code" erstellt. Anstatt einer graphischen Darstellung wird der Code von jedem Zeichen in "pfad$(ASC(zeichen))" als String gespeichert. Danach wird im Eingabetext (text$) einfach Zeichen für Zeichen erstetzt und in "chiffre$" gespeichert.
Natürlich wird aber im String "chiffre$" jede Null und jede Eins mit 8 Bit (Ascii-code) verschlüsselt; der Eingabetext wurde also keineswegs komprimerit sondern noch verlängert worden. Deshalb meine Frage, wie ich aus dem binären String einen "Ascii-String" machen könnte:
| Zitat: | Den Ascii-Wert erhälst du ja mit ASC(zeichen$), die Umkehrfunktion dazu ist CHR$(ascii). Dem übergibst du eine Nummer (Integer 0-256).
Umwandlung von Binärzahlen zu Zeichen ist wie folgt: Jedes Ascii-zeichen wird mit 8 Bit gespeichert, damit ergeben sich 256 verschiedene Zeichen. Du musst also immer 8 Bit lesen und den Dezimalwert dazu ausrechnen. |
Um den binären String in einen "Ascii-String" umzuwandeln, müsste ich ihn also in Blöcke zu je 8 Bit einteilen. Wandle ich nun einen solchen Block ins dekadische Zahlensystem um, erhalte ich eine Zahl zwischen 0 und 256. mit "ASC(diese Zahl)" würde ich ein Symbol erhalten, das ich anstelle des 8 Bit langen binären Blocks einsetzen könnte. Somit wäre der Eingabetext auch wirklich komprimiert. Sehe ich das so richtig??
Wenn ja, 3 weitere Probleme:
1.) In den meisten binären Strings (in 7 von 8 ) wird es nicht möglich sein, das alle Blöcke genau 8 Bit lang sind. Beim letzten Block wird dies meist nicht der Fall sein. Dieses Problem ist noch relativ einfach zu lösen: Den letzten Block einfach solange mit Einsen oder Nullen "auffüllen", bis er 8 Bit lang ist. Man muss dann einfach irgendwo speichern, wieviele Bits noch "angehängt" wurden, die Nachricht wieder eindeutig entschlüsseln zu können.
2.) Nicht alle "Nummern" im Ascii-Code sind auch mit Zeichen besetzt worden. "7" wurde beispielsweise für ein "BEEP" reserviert.
3.) Wie lässt sich ein binärer Sting in eine dekadische Zahl umwandeln? Gibt es dafür eine Funktion?
PS: Genauere Infos zum Huffmancode: http://www.inf.fh-flensburg.de/lang/algorithmen/code/huffman/huffman.htm |
|
| Nach oben |
|
|
SpionAtom
Anmeldungsdatum: 10.01.2005
Beiträge: 395
|
| Verfasst am: 01.02.2007, 00:55 Titel: |
|
|
Binärzahl zu Dezimal solltest du zuhauf finden, wenn du danach suchst.
Für das Speicherproblem würde ich mir den Datei-Modus Binary mal ansehen. Damit hab ich selbst noch nie gearbeitet, aber vielleicht ists das richtige.
_________________
Inzwischen gehöre ich auch zu den BlitzBasicern. Also verzeiht mir, wenn mir mal ein LOCATE 100, 100 oder dergleichen rausrutscht. |
|
| Nach oben |
|
|
Skilltronic
Anmeldungsdatum: 10.09.2004
Beiträge: 1148
Wohnort: Köln
|
| Verfasst am: 01.02.2007, 23:16 Titel: |
|
|
Hallo
| proXy hat Folgendes geschrieben: | | Mit "ASC(diese Zahl)" würde ich ein Symbol erhalten, das ich anstelle des 8 Bit langen binären Blocks einsetzen könnte. Somit wäre der Eingabetext auch wirklich komprimiert. Sehe ich das so richtig?? |
Ja, ganau.
| proXy hat Folgendes geschrieben: | Wenn ja, 3 weitere Probleme:
1.) In den meisten binären Strings (in 7 von 8 ) wird es nicht möglich sein, das alle Blöcke genau 8 Bit lang sind. Beim letzten Block wird dies meist nicht der Fall sein. Dieses Problem ist noch relativ einfach zu lösen: Den letzten Block einfach solange mit Einsen oder Nullen "auffüllen", bis er 8 Bit lang ist. Man muss dann einfach irgendwo speichern, wieviele Bits noch "angehängt" wurden, die Nachricht wieder eindeutig entschlüsseln zu können.
2.) Nicht alle "Nummern" im Ascii-Code sind auch mit Zeichen besetzt worden. "7" wurde beispielsweise für ein "BEEP" reserviert.
3.) Wie lässt sich ein binärer Sting in eine dekadische Zahl umwandeln? Gibt es dafür eine Funktion? |
zu 1.) Ich habe in meinem Beispiel (s.u.) genau das gemacht. Maximal werden sieben Bit angehängt, also braucht man drei Bit, um zu speichern, wieviele. Ich habe diese drei Bit dem String chiffre$ vorangestellt, danach wird die Zahl der Bits in chiffre$ plus eben dieser drei auf das nächstgrösste Vielfache von acht normiert, indem Nullen angehängt werden. Beim Dekomprimiren später, müsste man dann eben zuesrt die drei führenden Bits einlesen bzw. auswerten und dann hinten ensprechend viele Bits abschneiden.
zu 2.) Das ist doch im Prinzip egal, der komprimierte Text soll ja später sowieso nicht mehr angezeigt werden und beim reinen Speichern oder Lesen ist es ja wurst, ob es sich um irgendein Sonderzeichen handelt. Byte ist Byte.
zu 3.) Eine Funktion gibt es dafür in QBasic nicht, dazu musst du den String zerlegen und die Bitwerte jeweils mit ihrem Stellenwert im Byte malnehmen oder so.
Ich habe mir mal erlaubt, deinem Programm eine weitere SUB hinzuzufügen. Die kannst du in dein Programm einfügen, nur muss die Veriable neutext$ als SHARED deklarieren. In der werden die Bytes abgelegt, die aus den Bits aus chiffre$ gewonnen werden.
| Code: | ...
CALL ordnen
CALL code
CALL ersetzen
CALL wandeln
PRINT
PRINT " Textausgabe:"; chiffre$
PRINT
PRINT " Komprimierter Text:"; neutext$
PRINT
k = (LEN(text$) - LEN(neutext$)) / LEN(text$) * 100
PRINT " Kompression:"; : PRINT USING "###.#"; k; : PRINT " %"
------------------------------------------------------------------------------------
SUB wandeln
neutext$ = ""
anhang$ = ""
l = LEN(chiffre$) + 3
rest% = 8 - 8 * (l / 8 - FIX(l / 8))
merkrest% = rest%
FOR p% = 2 TO 0 STEP -1
zhp% = 2 ^ p%
IF rest% >= zhp% THEN
rest% = rest% - zhp%
anhang$ = anhang$ + "1"
ELSE
anhang$ = anhang$ + "0"
END IF
NEXT
chiffre$ = anhang$ + chiffre$
FOR r% = 1 TO merkrest%
chiffre$ = chiffre$ + "0"
NEXT
FOR stelle% = 1 TO LEN(chiffre$) - 1 STEP 8
byte% = 0
FOR bit% = 0 TO 7
wert% = 2 ^ (7 - bit%) * (ASC(MID$(chiffre$, stelle% + bit%, 1)) - 48)
byte% = byte% + wert%
NEXT
neutext$ = neutext$ + CHR$(byte%)
NEXT
END SUB |
Das geht sicher noch eleganter, aber es sollte funktionieren. Die Beschränkung auf Zeichen von 33-126 finde ich nicht so gut. Umlaute, Satzzeichen oder Absätze (ENTER) bringen auf diese Art das Programm zum Absturz.
Gruss
Skilltronic
_________________
Elektronik und QB? www.skilltronics.de ! |
|
| Nach oben |
|
|
|
|
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
|
|
FAQ
Suchen
Mitgliederliste
Benutzergruppen
Registrieren
Profil
Einloggen, um private Nachrichten zu lesen
Login
