Σύγκριση strings σε ANSI C

[Haldol]

Δίνω ως είσοδο γράμματα σε τυχαία σειρά, π.χ. "ΜΡΚΕΛΑΗΑ". Θέλω να βρω σε ποιες λέξεις αντιστοιχεί κάτι τέτοιο, στο παράδειγμά μου είναι η λέξη "ΚΑΛΗΜΕΡΑ".

 

Τι έχω κάνει;

 

Έλεγχος μήκους. Εάν τα δύο strings διαφέρουν δεν έχει νόημα η σύγκριση. Εάν είναι όμως ίσα, ξεκινάει ένα loop που ελέγχει τα δύο strings γράμμα προς γράμμα. Στο παράδειγμα ξεκινάει από το 'Μ' του πρώτου string. Το βρίσκει στη θέση 4 του δεύτερου string, από την οποία και το σβήνει. Συνεχίζει με 'Ρ', το οποίο και βρίσκει στη θέση 6 του δεύτερου string και πάλι το σβήνει. Αυτό γίνεται μέχρι να συγκριθούν όλοι οι χαρακτήρες των δύο strings και είτε α) να υπάρχει στοιχείο που να ταυτίζεται για όλους, ή β) να αποτυγχάνει.

 

Δουλεύει; Ναι. Τότε το πρόβλημα ποιο είναι; Το ότι μέχρι να βρεθεί λέξη που να ταυτίζεται με τους χαρακτήρες που δίνω... μπορεί να 'χω προλάβει να κάνω και κάνα μπανάκι.

 

Για ποιο γρήγορα σκέφτηκα να δίνω "βάρη" σε κάθε γράμμα (π.χ. 'Α' = 1, 'Β' = 2, 'Ω' = 24) και να τροφοδοτώ το πρόγραμμα με λεξικό όπου οι λέξεις θα είναι ταξινομημένες βάση των βαρών των γραμμάτων και όχι αλφαβητικά. Έτσι αντί να ψάχνει κάθε λέξη γράμμα προς γράμμα, θα ξέρει ότι μπορεί να προσπεράσει όσες δεν έχουν το σωστό άθροισμα βαρών.

 

Άλλες ιδέες;

[migf1]

Σίγουρα με λεξικό είναι η ενδεδειγμένη υλοποίηση, το οποίο προφανώς θα περιέχει μόνο έγκυρες λέξεις.

 

Θέλεις μια συνάρτηση isanagram() όπως π.χ. αυτή: http://x-karagiannis...php#s_isanagram (τον κώδικα της βιβλιοθήκης τον έχω ελεύθερο, κατέβασέ τον αν νομίζεις πως θα σε εξυπηρετήσει) την οποία θα την εφαρμόζεις στις λέξεις candidates του λεξικού.

 

Για όποια λέξη στο λεξικό το string εισόδου είναι αναγραμματισμός, θα την εμφανίζεις στην λίστα ταιριάσματος. Το πρόβλημα της ταχύτητας έγκειται περισσότερο στο parsing του λεξικού παρά στη σύγκριση των λέξεων. Οπότε ρίξε εκεί το περισσότερο βάρος.

 

EDIT:

 

Μόλις συνειδητοποίησα πως δεν έχω απαντήσει στη 2η ερώτησή σου

 

Για το λεξικό μπορείς να χρησιμοποιήσεις ένα (ή περισσότερα) hash-table. Στην πιο απλή μορφή, το λεξικό σου θα είναι ένας πίνακας από linked-lists. Κάνε ένα search στο φόρουμ για "hash table", "hash function", κλπ... το έχουμε ξανασυζητήσει (και μάλιστα σχετικά πρόσφατα).

 

Σε αυτή την περίπτωση δεν χρειάζεσαι την isanagram() αλλά μια ομοιογενή hash-function.

 

EDIT 2:

 

Το βρήκα το νήμα: http://www.insomnia.gr/topic/445187-%CE%B1%CE%BD%CE%AC%CE%BB%CF%85%CF%83%CE%B7-%CE%BA%CE%B5%CE%B9%CE%BC%CE%AD%CE%BD%CE%BF%CF%85-%CF%83%CF%84%CE%B7-c/page__p__4723036__hl__hash+table__fromsearch__1#entry4723036

[Erevis]

Πρώτο βήμα είναι να φτιάξεις μια λίστα (δεν εννοώ τη συγκεκριμένη δομή δεδομένων, μπορείς να έχεις οτιδήποτε) από τις λέξεις στο λεξικό που έχουν ίδιο μέγεθος με την δική σου.

 

Δεύτερο βήμα, για κάθε λέξη στη λίστα ταξινομείς τους χαρακτήρες της κατά αύξουσα σειρά. (Μπορεί να συνδυαστεί με το παραπάνω βήμα).

 

Τρίτο βήμα, ταξινομείς τη λέξη που θες να βρεις και τη συγκρίνεις με όλες τις λέξεις στη λίστα.

 

Το να κάθεσαι να υπολογίζεις βάρη για κάθε λέξη δεν αφαιρεί κάτι από την πολυπλοκότητα του αλγορίθμου με την παραπάνω λύση.

[migf1]

Ένας εύκολος και γρήγορος τρόπος είναι ένα 2D hash-table, indexed με το ascii-code 1ου γράμματος και το μήκος της λέξης. Υποθέτοντας πως η πιο μακροσκελής λέξη του λεξικού αποτελείται ας πούμε από 30 γράμματα, με αλφάβητο 26 γράμματα έχεις...

 

>char *dict[30][26] = { {NULL} };

Ότι χρόνο είναι να φάει θα τον φάει κυρίως στην εκκίνηση του προγράμματος για να φορτώσει το λεξικό στην μνήμη. Μετά θα είναι γρήγορο.

 

>
for (every word in file-db)
 load( dict[ wlen ][ word[0] - 'Α' ], word  );

Από εκεί και πέρα διαβάζεις την είσοδο, την κάνεις normalize, και την ψάχνεις μονάχα στην normalized hashed λίστα που αντιστοιχεί στο μήκος της λέξης και το ascii-code του 1ου της γράμματος (το normalization μπορεί π.χ. να είναι κεφαλοποιημένες και ταξινομημένες κατά γράμμα)...

 

>
 len = normalize( read(string) ); 
 for (d=&dict[ len ][ string[0] - 'Α' ]; *d; d++)
if ( 0 == strcmp( normalize(*d), string) )
       	puts( *d );

[defacer]

1. Παίρνεις ένα λεξικό με όλες τις λέξεις που σ' ενδιαφέρουν.

2. Τις φορτώνεις κάπου, π.χ. σε ένα απλό πίνακα strings.

2. Τις περνάς από μια function η οποία αναδιατάσσει τα γράμματα κάθε λέξης με αλφαβητική σειρά (π.χ. ΝΟΜΟ και ΜΟΝΟ γίνονται και τα 2 ΜΝΟΟ).

3. Καθώς το κάνεις αυτό, κρατάς ένα κάποιου είδους dictionary (το καλύτερο πιθανότατα θα ήταν ένα trie, αλλά και με απλό tree ή hashtable δε θα έχει τεράστια διαφορά) όπου αντιστοιχείς την "κανονικοποιημένη" μορφή της λέξης με κάποιου είδους δείκτες στις πραγματικές λέξεις που αντιστοιχούν σ' αυτή τη μορφή. Για παράδειγμα, αν κρατάς τις λέξεις σε πίνακα τότε η καταχώρηση του dictionary για το λήμμα "ΜΝΟΟ" θα δείχνει στα indexes του πίνακα όπου υπάρχουν οι λέξεις NOMO και MONO.

 

Από αυτό το σημείο και μετά, μόλις πάρεις μια λέξη στα χέρια σου μπορείς να βρεις όλους τους αναγραμματισμούς της στιγμιαία ως εξής:

 

1. Κανονικοποιείς τη λέξη που σου έδωσαν (ΝΟΜΟ => ΜΝΟΟ).

2. Κοιτάς στο dictionary. Αν δεν υπάρχει τότε το λεξικό σου δεν περιλαμβάνει αυτή τη λέξη. Αν υπάρχει, ακολουθείς τους pointers ή "pointers" που περιέχει το dictionary και τυπώνεις τις αντίστοιχες λέξεις που αποτελούν αναγραμματισμό της εισόδου.

 

ΥΓ: Γιατί ειδικά σε ANSI C? Σε C++ όλο αυτό θα ήταν άσεμνα σύντομο να γραφεί.

[migf1]

Έχει ο δίκιο ο defacer για την ύπαρξη 2ου λεξικού με τις κανονικές λέξεις και τους δείκτες. Στον ψευδοκώδικα που έδωσα παραπάνω εγώ το έχω ξεχάσει, οπότε δεν λειτουργεί σωστά η εκτύπωση των ταιριασμένων λέξεων.

 

Ένας εναλλακτικός τρόπος σε αυτό που γράφει ο defacer, αν θες δηλ. να χρησιμοποιήσεις τη λογική του παραπάνω ψευδοκώδικα, είναι στο dict να κρατάς και την αυθεντική λέξη μαζί με την normalized στον κάθε κόμβο της κάθε dict[ len ][ ascii ] λίστας.

 

Δηλαδή αντί για ...

 

>
char *dict[30][26]

να έχεις...

 

>
struct {
char *w;    // word
char *wnorm;  // normalized word
} *dict[30][26];

Οπότε η if του for-loop αλλάζει σε...

 

>
...
 if ( 0 == strcmp(d->wnorm, string) )
     	puts( d->w );
...

και προφανώς η load() θα κάνει normalize τις λέξεις του λεξικού καθώς τις φορτώνει στον *dict[][]. Αν θέλεις να επισπεύσεις ακόμα περισσότερο την διαδικασία του αρχικού φορτώματος, μπορείς να έχεις απευθείας αποθηκευμένες και τις 2 μορφές των λέξεων στο αρχείο του λεξικού σου (π.χ.την αυθεντική και την normalized εκδοχή της κάθε λέξης ανά γραμμή)

 

EDIT:

 

Πρώτο βήμα είναι να φτιάξεις μια λίστα (δεν εννοώ τη συγκεκριμένη δομή δεδομένων, μπορείς να έχεις οτιδήποτε) από τις λέξεις στο λεξικό που έχουν ίδιο μέγεθος με την δική σου.

 

Δεύτερο βήμα, για κάθε λέξη στη λίστα ταξινομείς τους χαρακτήρες της κατά αύξουσα σειρά. (Μπορεί να συνδυαστεί με το παραπάνω βήμα).

 

Τρίτο βήμα, ταξινομείς τη λέξη που θες να βρεις και τη συγκρίνεις με όλες τις λέξεις στη λίστα.

 

Το να κάθεσαι να υπολογίζεις βάρη για κάθε λέξη δεν αφαιρεί κάτι από την πολυπλοκότητα του αλγορίθμου με την παραπάνω λύση.

 

Έναν τρόπο υλοποίησης με linked-list των 2 πρώτων βημάτων που περιγράφει ο φίλος erevis μπορείς να τα βρεις στον κώδικα αυτής της απλοποιημένης κρεμάλας: http://x-karagiannis...angman/hang.php (στο τέλος της σελίδας έχω κι ένα link που στέλνει σε online browsing του κώδικα, στο ideone)

 

Η συνάρτηση στην οποία αναφέρομαι είναι στη γραμμή 456, η ...

 

>
void pick_word(char *secret, const int lensecret, const char *dic_fname, const int maxwlen );

 

Στον κόμβο της λίστας χρησιμοποιώ string σταθερού μέγιστου μήκους για την κάθε λέξη, γιατί δεν χρησιμοποιώ σύνθετες δομές. Για εξοικονόμηση μνήμης προτίμησε να τις ορίσεις ως απλούς δείκτες και να τις κάνεις malloc() μέσα στην load() του ψευδοκώδικα.