PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : C++ - Vergleich mit Wörterbuch


ethrandil
2005-10-11, 14:47:02
grml... also.

Ich habe versucht im die aufgabe aus dem thread "alle kombinationen finden" zu lösen. Mit einer wörterliste.

folgende Funktion ist zwar ein bisschen zusammengewurschtelt bei der Fehlersuche, aber sie es klappt einfach immer noch nicht zufriedenstellend.

Es soll eine Wörterliste eingelesen werden - in jeder Zeile steht ein Wort.
Dann soll bei allen Permutationen geprüft werden, ob das Wort in der liste steht und jedes falsche Wort gelöscht werden.

void findeWorte(list < Permutation > *perm, char *dict)
{
cout << "reading file " << dict << "..." << flush;

fstream fd(dict, ios::in);
set < string, ltstr > set;
char buff[100];

if(fd.bad() || fd.fail())
return;
//Dictionary parsen
while(!fd.eof()) {
fd.getline(buff, 100);
set.insert(string(buff));
}

cout << " ... done" << endl;

bool end = false;
list < Permutation >::iterator it = perm->begin();

while(!end) {
//cout << ((Permutation) * it).wort << ":" << (set.count(((Permutation) * it).wort)) << endl;
//Prüfen ob wort in liste
if(set.count(((Permutation) * it).wort) == 0) {
//löschen
perm->erase(it);
it = perm->begin();

if(it == perm->end())
end = true;
}
else {
it++;
if(it == perm->end())
end = true;
}
}
}

Das Problem ist, dass es einfach nicht funktioniert wie es soll.. manchmal sind die Ergebnisse zufriedenstellend - manchmal schaffen es aber auch Wörter durch, die gar nicht in der Liste stehen.

Muss dazu sagen, dass ich noch nicht viel Programmiererfahrung mit c++ hab (eher Java).

Generell hab ich nichtmal ne vernünftige Vorlage dazu wie ich durch eine liste iteriere und zwischendrin auch was rauslöschen kann...

mfg
- Eth

Trap
2005-10-11, 15:22:42
Muss dazu sagen, dass ich noch nicht viel Programmiererfahrung mit c++ hab (eher Java).
Das sieht man sehr deutlich, ich hab es mal ein wenig geändert:
void findeWorte(list<Permutation> *perm, char *dict)
{
cout << "reading file " << dict << "..." << flush;

fstream fd(dict, ios::in);
set <string, ltstr> set;
string line;

//Dictionary parsen
while(getline(cin,line)) {
set.insert(line);
}

cout << " ... done" << endl;

bool end = false;
for(list <Permutation>::iterator it = perm->begin();it!=perm->end();++it)
{
//cout << it->wort << ":" << set.count(it->wort) << endl;
//Prüfen ob wort in liste
if(set.count(it->wort) == 0) {
//löschen
it = perm->erase(it);
}
}
}

Sieht eigentlich sinnvoll aus, der Algorithmus, wieso soll der nicht gehen? Groß-/Kleinschreibung?

ethrandil
2005-10-11, 16:04:14
Was nicht geht weiß ich nicht genau. mit deiner Version macht folgender Code eine folgende ausgabe:

(in main:)

findeWorte(&pool, argv[2]);

cout << "übrig nach dictionary: " << pool.size() << endl;
printPermList(&pool);


reading file "wordlisttest"... ... done
tset:0
test:1
tets:0
ttes:0
stte:0
stet:0
etst:0
estt:0
etts:0
tste:0
tets:0
ttes:0
tste:0
ttse:0
sett:0
etts:0
tset:0
ttse:0
test:1
stet:0
etst:0
übrig nach dictionary: 3
test
stte
test

Das Problem ist jetzt aber, dass der Inhalt der datei wordlisttest folgender ist:
test
intim
geheim

und der String 'stte' niemals hätte durchkommen dürfen....

- Eth

P.S.: Wie bekomme ich es denn hin, dass in einer liste alle Dublikate gelöscht werden? sodass nur einmal 'test' vorkommt...

Trap
2005-10-11, 16:16:03
Duplikate löschen geht in Listen am einfachsten so:
list.sort();
list.unique();
Bei Containern allgemein mit den gleich benannten Funktionen aus <algorithm>.

Das Verhalten von deinem Programm kann ich mir nicht erklären. Es waren nur 2 Einträge der Liste im Set enthalte, also müssten im Ergebnis auch nur 2 sein.
Mach mal ans Ende von findeWorte eine Ausgabe für perm->size().

ethrandil
2005-10-11, 16:33:35
das gibt drei aus. Noch seltsamer wirds, wenn ich die komplette Wortliste nehm (viele, viele Dictionarys, dateigröße 7 mb) kommt folgendes:


reading file "wordlist"... ... done
tset:0
test:1
tets:1
ttse:0
stet:1
stte:0
stet:1
stte:0
etts:0
etst:0
tset:0
test:1
tets:1
ttse:0
found 14 strings


fehlerhaft ist daran, dass a) ursprünglich 22 Strings in der liste waren, aber nur 14 zeilen auftauchen und auch 14 durchkommen... (und zwar die 8 fehlenden und die 6 durchgekommenen...).

- Eth

EDIT: Jetzt hab ich vorher mit unique() alle doppelten Einträge eliminiert und nun ist aber der Fehler der selbe... nur halb so groß:
reading file "wordlist"... ... done
estt:0
etts:0
stet:1
stte:0
tets:1
tset:0
ttes:0
found 7 strings
übrig nach dictionary: 7
etst
sett
stet
test
tets
tste
ttse

offenbar werden manche strings nicht in der Schleife geprüft!

EDIT2:
Ich habe mal erst die komplette liste ausgeben lassen und dann den algorithmus laufen lassen. Ergebnis:
estt
etst
etts
sett
stet
stte
test
tets
tset
tste
ttes
ttse
estt:0
etts:0
stet:0
test:1
tets:0
tste:0
ttse:0
etst:0
stte:0
tset:0
jedes mal wenn ein strimg gelöscht wird, wird der nächste aus der liste übersprungen. wieso?!?

EDITxyz: habs gelöst!
for(list <Permutation>::iterator it = perm->begin();it!=perm->end();)
{
cout << it->wort << ":" << set.count(it->wort) << endl;
//Prüfen ob wort in liste
if(set.count(it->wort) == 0)
it = perm->erase(it);
else
it++;
}
falls der iterator nach dem löschen neu gesetzt wird hat er schon die korrekte position für den nächsten schleifendurchlauf und muss nicht nochmal erhöht werden. :up: