ChickenLipsRfun2eat
Anmeldungsdatum: 6. Dezember 2009
Beiträge: 12067
|
Hab es eben mit meiner Testdatei durchlaufen lassen. Das Programm beendete sich allerdings nicht (keine Ursache gesucht, weil egal ☺ ). input.txt
Hello User! :D
I'd like to become a beefsteak^^!
Eine Rose ist eine Rose ist eine Rose. Eine Tulpe ist keine Rose.
Wir schreiben das Jahr 2016!
Das wars! statistik.txt
hello: 1-mal
user: 1-mal
D: 1-mal
i: 1-mal
d: 1-mal
like: 1-mal
to: 1-mal
become: 1-mal
a: 1-mal
beefsteak: 1-mal
eine: 4-mal
rose: 4-mal
ist: 3-mal
tulpe: 1-mal
keine: 1-mal
wir: 1-mal
schreiben: 1-mal
das: 2-mal
jahr: 1-mal
: 0-mal
wars: 1-mal
|
circular
(Themenstarter)
Anmeldungsdatum: 14. Mai 2016
Beiträge: Zähle...
|
ChickenLipsRfun2eat schrieb: : 0-mal
das liegt daran das 2016 für isalpha halt 0 ergibt
|
ChickenLipsRfun2eat
Anmeldungsdatum: 6. Dezember 2009
Beiträge: 12067
|
War auch nur als Info gedacht. Mehr nicht ☺ Ich hatte halt nen anderen Ansatz als du, was aber natürlich nix macht. Deine ursprüngliche Eingabedatei sah ja auch sowas nicht vor, bzw. überstieg wohl auch die Anforderungen der Hausaufgabe. Ich wollte lediglich mitlernen...ein Blick über den Tellerrand schadet ja bekanntlich nicht und Wissen ist selten schädlich ☺
|
Dakuan
Anmeldungsdatum: 2. November 2004
Beiträge: 6345
Wohnort: Hamburg
|
@ChickenLipsRfun2eat Das Programm beendete sich allerdings nicht (keine Ursache gesucht, weil egal
Hängt vielleicht noch bei getchar()? Habe ich aber auch nicht ausprobiert.
|
rklm
Projektleitung
Anmeldungsdatum: 16. Oktober 2011
Beiträge: 12823
|
Aus Spaß habe ich mal die Trie-Lösung ausprogrammiert: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172 | #include <stdlib.h>
#include <ctype.h>
#include <stdio.h>
#include <errno.h>
#include <string.h>
struct trie_node {
unsigned char c;
unsigned int count;
struct trie_node* next[256];
};
struct trie {
struct trie_node* root;
unsigned int max_depth;
};
struct trie_node* trie_node_create(unsigned char c) {
struct trie_node* n = (struct trie_node*) malloc(sizeof(struct trie_node));
int i;
n->c = c;
n->count = 0;
for ( i=0; i<256; ++i ) {
n->next[i] = 0;
}
return n;
}
struct trie* trie_create() {
struct trie* t = (struct trie*) malloc(sizeof(struct trie));
t->root = trie_node_create(0);
t->max_depth = 0;
return t;
}
struct trie_node* trie_add_node(struct trie_node* n, unsigned char c) {
struct trie_node* next = n->next[c];
if ( !next ) {
next = trie_node_create(c);
n->next[c] = next;
}
return next;
}
void trie_node_release(struct trie_node* n) {
if ( !n ) {
return;
}
int i;
for ( i=0; i<256; ++i ) {
trie_node_release(n->next[i]);
}
free(n);
}
void trie_release(struct trie* t) {
if ( t ) {
trie_node_release(t->root);
free(t);
}
}
int is_word_char(unsigned char c) {
/* return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); */
return isalpha(c);
}
void process(struct trie* t, FILE* fd) {
unsigned char buffer[4096];
int word = 0;
size_t i;
unsigned int depth = 0;
struct trie_node* current = t->root;
while ( !feof(fd) ) {
size_t read = fread(buffer, 1, 4096, fd);
if ( ferror(fd) ) {
fprintf(stderr, "Error during reading: %s\n", strerror(errno));
return;
}
for ( i=0; i<read; ++i ) {
unsigned char ch = tolower(buffer[i]);
int w = is_word_char(ch);
if ( w ) {
++depth;
current = trie_add_node(current, ch);
}
else {
/* non word char */
if (word) {
++current->count;
if ( depth > t->max_depth ) {
t->max_depth = depth;
}
depth = 0;
current = t->root;
}
}
word = w;
}
}
}
unsigned int trie_node_print(struct trie_node* n, unsigned char buffer[], unsigned int pos) {
unsigned int i;
unsigned int words = 0;
if ( n->count > 0 ) {
++words;
buffer[pos] = 0;
printf("%10u %s\n", n->count, buffer);
}
for ( i=0; i<256; ++i ) {
struct trie_node *nn = n->next[i];
if ( nn ) {
buffer[pos] = nn->c;
words += trie_node_print(nn, buffer, pos + 1);
}
}
return words;
}
void trie_print(struct trie* t) {
unsigned char buffer[t->max_depth + 1];
printf("%u different words.\n", trie_node_print(t->root, buffer, 0));
}
int main(int argc, char* argv[]) {
struct trie *words = trie_create();
if ( argc == 0 ) {
process(words, stdin);
}
else {
int i;
for ( i=1; i<argc; ++i ) {
FILE* f = fopen(argv[i], "r");
if ( f ) {
process(words, f);
fclose(f);
}
else {
fprintf(stderr, "Error during reading of '%s': %s\n", argv[i], strerror(errno));
trie_release(words);
exit(1);
}
}
}
trie_print(words);
trie_release(words);
exit(0);
}
|
Die arbeitet allerdings nur mit ASCII, d.h. ohne Berücksichtigung irgendwelcher Encodings.
|
Lysander
Anmeldungsdatum: 30. Juli 2008
Beiträge: 2669
Wohnort: Hamburg
|
|
Dakuan
Anmeldungsdatum: 2. November 2004
Beiträge: 6345
Wohnort: Hamburg
|
Wow, das sieht sehr interessant aus. Ist übrigens das erste Mal, das ich etwas von Tries höre. Die Beschreibung klingt aber so, als wenn das möglicherweise eine Alternative zu den von mir bisher verwendeten Heaps sein könnte. Die Arbeitsweise erinnert mich irgendwie an die LZW Kompression. Nachtrag: Ich habe das gerade mal ausprobiert und dabei einen unbedeutenden Schönheitsfehler entdeckt. Am Anfang von main() sollte es wohl eher so aussehen:
| if ( argc < 2 ) {
process(words, stdin);
}
|
denn argc ist eigentlich nie 0.
Die arbeitet allerdings nur mit ASCII, d.h. ohne Berücksichtigung irgendwelcher Encodings.
Ich denke da gerade über UTF-8 codierte Texte nach ...
|
rklm
Projektleitung
Anmeldungsdatum: 16. Oktober 2011
Beiträge: 12823
|
Lysander schrieb: @rklm: Nice!
Merci! Hier noch ein kleiner Patch, der die Speichernutzung effektiver macht (jeder Knoten hat nur 16 Verzweigungen anstatt 256). So kommt man von ~256*8 = 2k (auf 64-Bit-Systemen) zu wenigen Bytes per Knoten (~128). Dafür benötigt man natürlich mehr Knoten. Interessant ist, dass weite Teile der Verarbeitung unverändert bleiben können: 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112 | --- words.c 2016-05-22 14:24:06.142320886 +0200
+++ words3.c 2016-05-22 19:12:26.269555253 +0200
@@ -3,12 +3,16 @@
#include <stdio.h>
#include <errno.h>
#include <string.h>
+#define bits 4
+#define variants (1 << bits)
+#define mask (variants - 1)
+
struct trie_node {
unsigned char c;
unsigned int count;
- struct trie_node* next[256];
+ struct trie_node* next[variants];
};
struct trie {
struct trie_node* root;
@@ -20,9 +24,9 @@
int i;
n->c = c;
n->count = 0;
- for ( i=0; i<256; ++i ) {
+ for ( i=0; i<variants; ++i ) {
n->next[i] = 0;
}
return n;
@@ -35,15 +39,24 @@
return t;
}
struct trie_node* trie_add_node(struct trie_node* n, unsigned char c) {
- struct trie_node* next = n->next[c];
+ struct trie_node* next = n;
+ int i;
- if ( !next ) {
- next = trie_node_create(c);
- n->next[c] = next;
+ for ( i=0; i<8; i += bits ) {
+ int idx = (c >> i) & mask;
+ struct trie_node* tmp = next->next[idx];
+
+ if ( !tmp ) {
+ tmp = trie_node_create(0);
+ next->next[idx] = tmp;
+ }
+
+ next = tmp;
}
+ next->c = c;
return next;
}
void trie_node_release(struct trie_node* n) {
@@ -52,9 +65,9 @@
}
int i;
- for ( i=0; i<256; ++i ) {
+ for ( i=0; i<variants; ++i ) {
trie_node_release(n->next[i]);
}
free(n);
@@ -115,26 +128,29 @@
}
}
unsigned int trie_node_print(struct trie_node* n, unsigned char buffer[], unsigned int pos) {
+ if ( !n ) {
+ return 0;
+ }
+
unsigned int i;
unsigned int words = 0;
- if ( n->count > 0 ) {
- ++words;
- buffer[pos] = 0;
- printf("%10u %s\n", n->count, buffer);
- }
+ if ( n->c ) {
+ buffer[pos++] = n->c;
- for ( i=0; i<256; ++i ) {
- struct trie_node *nn = n->next[i];
-
- if ( nn ) {
- buffer[pos] = nn->c;
- words += trie_node_print(nn, buffer, pos + 1);
+ if ( n->count > 0 ) {
+ ++words;
+ buffer[pos] = 0;
+ printf("%10u %s\n", n->count, buffer);
}
}
+ for ( i=0; i<variants; ++i ) {
+ words += trie_node_print(n->next[i], buffer, pos);
+ }
+
return words;
}
void trie_print(struct trie* t) {
|
Man kann natürlich auch noch bits auf 2 setzen. Dann erhält man vier Verzweigungen pro Knoten und wiederum mehr Knoten. Man sollte auch beachten, dass dann kürzere Wörter erfasst werden können, da ich aus Faulheit Rekursion gewählt habe und die Stackgröße schneller aufgebraucht wird.
|
rklm
Projektleitung
Anmeldungsdatum: 16. Oktober 2011
Beiträge: 12823
|
Dakuan schrieb: Wow, das sieht sehr interessant aus. Ist übrigens das erste Mal, das ich etwas von Tries höre. Die Beschreibung klingt aber so, als wenn das möglicherweise eine Alternative zu den von mir bisher verwendeten Heaps sein könnte. Die Arbeitsweise erinnert mich irgendwie an die LZW Kompression.
Heaps und Tries verwendet man aber zu unterschiedlichen Zwecken, insbesondere gibt es die Möglichkeit, das minimale Element zu entfernen nicht, deretwegen man typischerweise Heaps verwendet. Dafür haben Tries andere Vorteile, z.B. kann man effizient mit Präfixen Mustererkennung betreiben bzw. alle Sequenzen identifizieren, die einen bestimmten Präfix haben (z.B., wenn es um Auto Completion geht).
Nachtrag: Ich habe das gerade mal ausprobiert und dabei einen unbedeutenden Schönheitsfehler entdeckt. Am Anfang von main() sollte es wohl eher so aussehen:
| if ( argc < 2 ) {
process(words, stdin);
}
|
denn argc ist eigentlich nie 0.
Oh, ja! Danke! 👍
Die arbeitet allerdings nur mit ASCII, d.h. ohne Berücksichtigung irgendwelcher Encodings.
Ich denke da gerade über UTF-8 codierte Texte nach ...
Dann musst Du natürlich etwas mehr Aufwand beim Lesen treiben. Der Trie kann dann trotzdem so bleiben, weil er ja mit den Bits arbeitet (wird vielleicht in der modifizierten Version klarer).
|
Dakuan
Anmeldungsdatum: 2. November 2004
Beiträge: 6345
Wohnort: Hamburg
|
Das Programm macht richtig Spaß. Habe das gerade mal über eine Zitatensammlung laufen lassen (meistens Sprüche aus Fernsehkrimmies). Da gibt es schon lustige Sequenzen:
...
1 deutschland
8 die
1 diese
1 dir
1 doch
1 doktor
1 drogendealer
3 du
1 dummer
...
aber bei:
1 ffelt
dachte ich dann an einen Schreibfehler. Musste dann aber feststellen, das es an den Umlauten lag. Originaltext: Haben Sie heimlich am Lachgas geschnüffelt?
Dann musst Du natürlich etwas mehr Aufwand beim Lesen treiben.
Ich denke das lohnt sich.
(z.B., wenn es um Auto Completion geht)
Danach hatte ich schon immer gesucht, das aber nicht wirklich ernsthaft verfolgt.
|
rklm
Projektleitung
Anmeldungsdatum: 16. Oktober 2011
Beiträge: 12823
|
Dakuan schrieb: Das Programm macht richtig Spaß. Habe das gerade mal über eine Zitatensammlung laufen lassen (meistens Sprüche aus Fernsehkrimmies). Da gibt es schon lustige Sequenzen:
Du Drogendealer! 😉
Dann musst Du natürlich etwas mehr Aufwand beim Lesen treiben.
Ich denke das lohnt sich.
Klar.
|