✔ Nachschlagen durch Permutation entstehende Wörter in einem Thesaurus und Ausgabe

L

luke55

Grünschnabel
Hallo liebe Community,
ich bin komplett neu hier, also sind mir die Gepflogenheiten noch nicht so bekannt, deshalb bitte ich ein wenig um Nachsicht.

Folgendes: Ich muss für ein Projekt ein C-Programm (NICHT C++!) entwickeln, welches ein Wort, per Kommandozeilenparameter übergibt, und es soll anschließend über alle Möglichkeiten permutiert werden, d.h. jeder Buchstabe soll an jede mögliche Stelle getauscht werden.
Des Weiteren soll die durch die Permutation entstehenden Wörter in einem Thesaurus nachgeschlagen werden ob sie dort vorkommen. Der Thesaurus ist eine sortierte Textdatei mit fester Zeilenlänge und einem Wort pro Zeile, eine Beispieldatei "namen.txt" liegt mir vor mit ca. 2000 verschiedenen Namen (mit Klein- und Großbuchstaben). Die Suche sollte möglichst schnell erfolgen (besser als 0(n)). Die Zahl der Treffer und die Treffer sollen ausgegeben werden. Das ganze Verfahren soll case-insensitiv, also ohne Berücksichtigung von Groß- und Kleinbuchstaben erfolgen, deutsche Umlaute müssen nicht ersetzt werden.

Beispiel: die Buchstabenfolge (das Wort) "asd" kann folgendermaßen permutiert werden:
asd, ads, sad, sda, dsa, & das /// Im Thesaurus: der, die, das & ADS ==> damit würden die Wörter "das" und "ADS" gefunden!

Bedingungen: Das Programm muss unter dem aktuellen Linux-GCC fehler- und wartungsfrei übersetzbar sein, nicht Visual Studio!

Ich habe bereits selber programmiert und auch schon eine Musterlösung, allerdings habe ich probleme was eigenes zustande zu bringen, mit alternativen Lösungswegen. Kann mir jemand dabei helfen? Das wäre der Wahnsinn! Ich bin perönlich Mac-User, also bitte nur Code posten, mit dem ich auch was anfangen kann.

Vielen Dank jetzt schon mal von meiner Seite und liebe Grüße :-)
 
Hi und herzlich Willkommen hier,

poste mal bitte (oder schicks mir per PN) deinen Source, wie du ihn bisher umgesetzt hast, dann kann ich mit konkreten Vorschlägen aufwarten :)

Theoretisch würde ich folgendes bei dem Programm beachten / machen:
- Das Wort von der Konsole einlesen
- Das Wörterbuch einlesen.
- Für jede Buchstabenlänge einen Binärbaum erstellen
- In den jeweiligen Baum das Wort einfügen, hier darauf achten, dass dieser balanciert bleibt
- Die einzelnen Buchstaben des Wortes permutieren
- Das entstandene Wort in dem entsprechenden Baum nachschlagen

Der Vorteil von dem / den Binärbäumen ist, dass die Worte da drin schneller gefunden werden wie wenn du sequenziell durch eine Liste durchgehst. Angenommen das Wort "zoo" wird gesucht, dann musst du im Worst-Case beim sequenziellen Suchen die komplette Liste durch, bei einem Binärbaum allerdings nur die entsprechende Tiefe. Die Tiefe wäre bei 2000 Einträgen dann 11, wenn ich mich verrechnet habe.

Zur Permutation fällt mir allerdings gerade kein geeigneter Algorithmus ein, der Baum sollte aber Performance-Technisch schon gute Ergebnisse liefern.

Grüße,
BK
 
Meinst du mit Binärbaum binäre Suche oder ist das was komplett anderes?
Denn dann ist das wohl auch die Vorgehensweise in meiner Musterlösung:

C: 
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>

void swap(char *,int, int); //buchstaben vertauscher
void perm(char *,int,int);   //mr. permutierer
int wordcount();      //zaehlt die lines im Dokument
void uncase(char*);         //macht einen String lowercase
void checkem(char*,int); //allgemeine ueberpruefung des permutierten wortes und dem wort in der datei.

int treffer=0;  //Anzahl der gefundenen worte

int main(int argc,char** argv) {
  FILE *file;
  int words;

  if(argc != 2) { //ueberprueft ob es genau 2 Argumente gibt
    fprintf(stderr,"Falsche Summe von Parametern!\n%s [Wort]\n", argv[0]);
    return 0;
  }

  char* text = argv[1]; //Erst nun wird das zu suchende/permutierende wort als string gespeichert.
  int lastIndex = strlen(text)-1;

  uncase(text); //macht das zu suchende wort lowercase

  file = fopen("namen.txt","r"); //oeffnet namen.txt

  if(file == NULL) { //check ob es die datei berhaupt gibt
      fprintf(stderr,"Datei nicht gefunden!");
      return 1;
  }
  fclose(file);

  words=wordcount(); ///Zaehle wie viele lines (hier wie viele namen es gibt)  inb4 crash
  fprintf(stdout,"Anzahl der gefundenen Namen: %d\n\n", words);

  perm(text,lastIndex,words); //Startet permitierer UND ueberpruefungsprozess
  fprintf(stdout,"\nUebereinstimmungen:  %d\n",treffer);

  fclose(file);
  return 0;
}

void swap(char *text,int i,int j)
{
    char temp=text[i];
    text[i]=text[j];
    text[j]=temp;
}

void perm(char *text,int lastIndex,int words)
{
    if(lastIndex==0)
    {
        checkem(text,words);
    }
    else
    {
        perm(text,lastIndex-1,words);
        int i = 0;
        for(i=0; i<=lastIndex-1; i++){
            swap(text,i,lastIndex);
            perm(text,lastIndex-1,words);
            swap(text,i,lastIndex);
        }
    }
}

int wordcount()
{
  int words = 0;
  FILE *file;

  file = fopen("namen.txt","r"); //oeffnet namen.txt
  fseek(file,0,SEEK_END);
  words=ftell(file)/21;
  fclose(file) ;
  return words;
}

void uncase(char* text) //lowercase fuer die case-insensitive suche
{
   int i;
   for (i = 0; text[i]; i++)    //geht von 0 bis die laenge des strings
    text[i] = tolower(text[ i ]);
}

void checkem(char *word,int words)
{
   static char ** namen = 0;
   static char ** namen2 = 0;
   static char lastfound[22];
   FILE *file;
   static int loaded=0;
   int i=0,first=0, last=words-1, middle=(first+last)/2,n;
   int comparelimit=22;

   if(!loaded)
   {
     namen=malloc(words * sizeof(char *)); //mach ein array mit laenge anzahl an woertern
     namen2=malloc(words * sizeof(char *));
     for (i=0; i<words;i++)
     {
        namen[i] = malloc(22*sizeof(char *)); //mach die strings 22 zeichen lang fr jedes array
        namen2[i] = malloc(22*sizeof(char *));
     }
     file = fopen("namen.txt","r"); //oeffnet namen.txt
        for(i=0; i<words; i++)
        {
            fscanf(file, "%s", namen[i]);  // lies zeile[i] in array[i]
            strcpy(namen2[i],namen[i]);
        }
     for(i=0;i<words;i++)
         uncase(namen[i]);
     loaded=1;   //flag loaded auf eins, nun muss dias alles nicht nocheinmal gemacht werden, dank "static"
     fclose(file);
   }

   while( first <= last )
   {
      n=strncmp (word,namen[middle],comparelimit);
      if (n>0)
         first = middle + 1;
      else if (strncmp(word,namen[middle],comparelimit)==0)
      {
         if(strcmp(lastfound,namen[middle])!=0)
         {
             fprintf(stdout,"%s\n", namen2[middle]);
             treffer++;
             strcpy(lastfound,namen[middle]);
         }
         break;
      }
      else
         last = middle - 1;

      middle = (first + last)/2;
   }
}

Der C-Code verrichtet genau seinen vorgegebenen Dienst, aber kann diese natürlich nicht eins zu eins so verwenden zur Abgabe, aber wenn ich mir so feste Strukturen ansehe zum swap Unterprogramm oder zum Permutation Unterprogramm finde ich leider keine gescheiten Alternativen. :/
 
Hi,


luke55 hat gesagt.:
Meinst du mit Binärbaum binäre Suche oder ist das was komplett anderes?
Zum Vergrößern anklicken....

Genau das meinte ich :)

Sieht ganz gut aus, habe nur ein paar Fragen:


C: 
int wordcount()
{
  int words = 0;
  FILE *file;

  file = fopen("namen.txt","r");
  fseek(file,0,SEEK_END);
  words=ftell(file)/21;   // warum exakt durch 21? */
  fclose(file) ;
  return words;
}
Warum teilst du hier durch genau 21? Wie kommst du auf diese Zahl? Magic-Numbers werden normal als Konstanten definiert, sieht schöner aus.

C: 
void uncase(char* text) //lowercase fuer die case-insensitive suche
{
   int i;
   for (i = 0; text[i]; i++)    //geht von 0 bis die laenge des strings
    text[i] = tolower(text[ i ]);
}
/* mein vorschlag: */
void uncase(char* text) {
  while(*text != '\0') {
    *text++ = tolower(*text);
  }
}
Die Schleife kannst du dir sparen, du kannst mit Pointer-Arithmetik arbeiten.


(in der checkmem):
C: 
     for (i=0; i<words;i++)
     {
        namen[i] = malloc(22*sizeof(char *)); //mach die strings 22 zeichen lang fr jedes array
        namen2[i] = malloc(22*sizeof(char *));
     }
     file = fopen("namen.txt","r"); //oeffnet namen.txt
        for(i=0; i<words; i++)
        {
            fscanf(file, "%s", namen[i]);  // lies zeile[i] in array[i]
            strcpy(namen2[i],namen[i]);
        }
Was passiert wenn ein Wort länger als 21 Zeichen ist? => Es werden nur 22 byte reserviert und mit dem fscanf() dann mehr eingelesen. Dadurch erhältst du einen Buffer Overflow. Besser:

C: 
            fscanf(file, "%21s", namen[i]);  // lies zeile[i] in array[i]

C: 
   while( first <= last )
   {
      n=strncmp (word,namen[middle],comparelimit);
      if (n>0)
         first = middle + 1;
      else if (strncmp(word,namen[middle],comparelimit)==0)
Obwohl du nur mit Strings arbeitest, die immer mit einem \0 terminiert sind, arbeitest du mit strncmp. Löblich ;)

luke55 hat gesagt.:
Der C-Code verrichtet genau seinen vorgegebenen Dienst, aber kann diese natürlich nicht eins zu eins so verwenden zur Abgabe, aber wenn ich mir so feste Strukturen ansehe zum swap Unterprogramm oder zum Permutation Unterprogramm finde ich leider keine gescheiten Alternativen. :/
Zum Vergrößern anklicken....

Was mir noch auffällt, ist dass du zwar eine binäre Suche verwendest, aber nicht überprüfst ob die Datei sortiert ist. Falls dies nicht explizit gegeben ist, musst du dir noch überlegen, wie du den Baum dann aufbauen kannst.

Nun, du könntest für das Wörterbuch ein Struct erstellen:
C: 
struct node;

struct node {
  char* value;
  struct node* left;
  struct node* right;
};

Das Laden der Datei könntest du auch in eine extra Funktion auslagern, genau wie die Suche in dem Tree. Eine Hilfsmethode die true / false zurückgibt, ob ein Element drin ist oder nicht.
So als Denkanstoß:

C: 
bool findInTree(struct node* root, char* find);
struct node* loadDictionary(char* filename);

Wenn du das so umngesetzt hast, dann ist dein Programm nicht mehr mit der Musterlösung zu vergleichen, bzw. es fällt nicht mehr auf.

Grüße,
BK
 
Danke Thomas für den Link, allerdings ist es im Detail doch unterschiedlich und es fand eine Umsetzung über Visual Studio statt.

@Bratkartoffel: Puh. Als Neuling muss ich mich da jetzt überall erstmal schlau machen, aber vielen Dank für deine Anregungen! :-)
 
Hallo,

Danke Thomas für den Link, allerdings ist es im Detail doch unterschiedlich und es fand eine Umsetzung über Visual Studio statt.
Zum Vergrößern anklicken....
Na ja, die Aufgabenstellung sieht für mich leicht erweitert aus ;-) - außerdem habe ich die C Variante sowohl mit Visual Studio als auch mit DevCPP (GCC) entwickelt / getestet ;-)

Aber gut - freut mich wenns dir hilft :)

Gruß Tom
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück