Προς το περιεχόμενο

hash table για string στη C++


realez

Προτεινόμενες αναρτήσεις

Καλησπέρα, στο παρελθόν είχα φτιάξει πίνακα κατακερματισμού για ένα πρόγραμμα όπου ο χρήστης έδινε το μέγεθος του πίνακα, το πλήθος των στοιχείων που θα δώσει και έπειτα έδινε Input κλειδιά και λέξεις. Οπότε τα πράγματα ήταν αρκετά απλά.

Είχα φτιάξει ένα struct της μορφής:

 

struct data

{

   int key;

   char c[20];

};

Τα βήματα που ακολουθούσα μετά ήταν

-Hashing στο κλειδί που έδινε της μορφής hash(key, m) = key mod m. Όπου key=κλειδί, m=μέγεθος πίνακα

-Πήγαινα στη διεύθυνση (ας πουμε ότι ο πίνακας μου λεγόταν array) array[hash(key,m)]

-Εκεί άμα ήταν άδεια έβαζα το κλειδί και τη λέξη

-Αμα δεν ήταν το έβαζα στην επόμενη κενή θέση που θα έβρισκα

-Αμα ξαναέφτανε στην αρχική θέση ο πίνακας ήταν γεμάτος.

 

Τώρα προσπαθώ να φτιάξω έναν πίνακα κατακερματισού αλλά αυτή τη φορά το Input το παίρνω από txts (γύρω στα 30 και το καθένα περιέχει μυθιστορήματα) και τα κλειδιά αυτή τη φορά είναι strings.

Οι απορίες μου είναι οι εξείς:

-Ποιό πρέπει να είναι το μέγεθος του πίνακα (σταθερό η να το αλλάζω);

-Πως μπορώ να κάνω σωστό hasing στις λέξεις;

-Τι είναι πιο σωστό να χρησιμοποιήσω hashing με ανοιχτή διεύθυνση η με αλυσίδες;

ps: Οί γνώσεις μου στη C++ είναι αρκετά περιορισμένες.

Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Μου φένεται πολύ δύσκολο να καταλάβω πως λειτουργεί αυτό που μου έστειλες. Δεν έχω ξαναχρησιμοποιήσει κάτι τέτοιο . Θα ήταν πολύ δύσκολο να το φτιάξω μόνος μου?

Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Νομίζω πως εννοείται αφού ήδη έχεις κάποιες πολύ βασικές απορίες. Αλλά ίσως θα ήταν σκόπιμο να ξεκινήσει η κουβέντα από λίγο νωρίτερα: τι σκοπεύεις να κάνεις μ' αυτό το hashtable? Για ποιό λόγο επέλεξες hashtable και όχι κάποιο άλλο data structure? (Είναι δύο διαφορετικές ερωτήσεις).

 

Νομίζω καλύτερα να μη πω τίποτα παραπάνω για τη χρήση του unordered_map (ή βασικά και του σκέτου map που εσωτερικά δεν είναι hash αλλά tree, εξωτερικά όμως το ίδιο) -- μπορεί να συζητάμε για hashtable και να μην υπάρχει ιδιαίτερος λόγος.

Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Καλησπέρα, στο παρελθόν είχα φτιάξει πίνακα κατακερματισμού για ένα πρόγραμμα όπου ο χρήστης έδινε το μέγεθος του πίνακα, το πλήθος των στοιχείων που θα δώσει και έπειτα έδινε Input κλειδιά και λέξεις. Οπότε τα πράγματα ήταν αρκετά απλά.

Είχα φτιάξει ένα struct της μορφής:

 

struct data

{

   int key;

   char c[20];

};

Τα βήματα που ακολουθούσα μετά ήταν

-Hashing στο κλειδί που έδινε της μορφής hash(key, m) = key mod m. Όπου key=κλειδί, m=μέγεθος πίνακα

-Πήγαινα στη διεύθυνση (ας πουμε ότι ο πίνακας μου λεγόταν array) array[hash(key,m)]

-Εκεί άμα ήταν άδεια έβαζα το κλειδί και τη λέξη

-Αμα δεν ήταν το έβαζα στην επόμενη κενή θέση που θα έβρισκα

-Αμα ξαναέφτανε στην αρχική θέση ο πίνακας ήταν γεμάτος.

 

Τώρα προσπαθώ να φτιάξω έναν πίνακα κατακερματισού αλλά αυτή τη φορά το Input το παίρνω από txts (γύρω στα 30 και το καθένα περιέχει μυθιστορήματα) και τα κλειδιά αυτή τη φορά είναι strings.

Οι απορίες μου είναι οι εξείς:

-Ποιό πρέπει να είναι το μέγεθος του πίνακα (σταθερό η να το αλλάζω);

-Πως μπορώ να κάνω σωστό hasing στις λέξεις;

-Τι είναι πιο σωστό να χρησιμοποιήσω hashing με ανοιχτή διεύθυνση η με αλυσίδες;

ps: Οί γνώσεις μου στη C++ είναι αρκετά περιορισμένες.

 

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

Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Εχει hasher η C++; Μπραβο...

 

Κλασικά είναι template defined μόνο για συγκεκριμένα standard types, αν θέλεις για δικά σου πρέπει να δώσεις ένα definition για τα types που σ' ενδιαφέρουν. Αλλά υπάρχει και επιπλέον έτοιμο πράγμα στη Boost.

 

PS: migf1 δεν ξέρω αν πρόσεξες ότι η std::hash επιστρέφει πάντα μια τιμή σε συγκεκριμένο range (στην προκειμένη size_t) ανεξάρτητα από το μέγεθος που έχει ο hashtable που θα κρατήσει τα αντικείμενα. Όχι πως θα αλλάξει γνώμη κανείς αλλά έτσι για το χαβαλέ.

Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

...

 

PS: migf1 δεν ξέρω αν πρόσεξες ότι η std::hash επιστρέφει πάντα μια τιμή σε συγκεκριμένο range (στην προκειμένη size_t) ανεξάρτητα από το μέγεθος που έχει ο hashtable που θα κρατήσει τα αντικείμενα. Όχι πως θα αλλάξει γνώμη κανείς αλλά έτσι για το χαβαλέ.

 

Γιατί απευθύνεις σε μένα το PS? Στείλε το στο Virginia Tech, στο Princeton, στο MIT και στο Carnegie Mellon. Έτσι για τον χαβαλέ γράψε μας και τι σου απάντησαν (αν δηλαδή σου απαντήσουν καν).

Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Κλασικά είναι template defined μόνο για συγκεκριμένα standard types, αν θέλεις για δικά σου πρέπει να δώσεις ένα definition για τα types που σ' ενδιαφέρουν. Αλλά υπάρχει και επιπλέον έτοιμο πράγμα στη Boost.

 

PS: migf1 δεν ξέρω αν πρόσεξες ότι η std::hash επιστρέφει πάντα μια τιμή σε συγκεκριμένο range (στην προκειμένη size_t) ανεξάρτητα από το μέγεθος που έχει ο hashtable που θα κρατήσει τα αντικείμενα. Όχι πως θα αλλάξει γνώμη κανείς αλλά έτσι για το χαβαλέ.

Δεν ηξερα οτι υπαρχει καν. Εγω χρησημοποιουσα αυτη του winapi  :wacko:

Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Δημοσ. (επεξεργασμένο)

Νομίζω πως εννοείται αφού ήδη έχεις κάποιες πολύ βασικές απορίες. Αλλά ίσως θα ήταν σκόπιμο να ξεκινήσει η κουβέντα από λίγο νωρίτερα: τι σκοπεύεις να κάνεις μ' αυτό το hashtable? Για ποιό λόγο επέλεξες hashtable και όχι κάποιο άλλο data structure? (Είναι δύο διαφορετικές ερωτήσεις).

 

Νομίζω καλύτερα να μη πω τίποτα παραπάνω για τη χρήση του unordered_map (ή βασικά και του σκέτου map που εσωτερικά δεν είναι hash αλλά tree, εξωτερικά όμως το ίδιο) -- μπορεί να συζητάμε για hashtable και να μην υπάρχει ιδιαίτερος λόγος.

Με αυτό το hashtable θέλω να φτιάξω ενα αντεστραμένο ευρετήριο για περύπου 20 txt.  Αυτο που έχω κάνει μέχρι στιγμής είναι να γράψω κώδικα για να διαβάζει ενα ενα τα αρχεία και να βάζει σε ενα string μία μία της λέξης(μονο της λέξης). Αν φτιάξω το hashtable θα παίρνω μία μία της λέξης και θα της βάζω εκεί(με μια διαδικασία και ελέγχους σίγουρα) αλλά νομίζω αυτή είναι η λογική. Τώρα προσπαθώ να φτιάξω ένα πίνακα κατακερματισμού με αλυσίδες. Νομίζω αυτό χρειάζεται.

Επεξ/σία από realez
Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Δεν ηξερα οτι υπαρχει καν. Εγω χρησημοποιουσα αυτη του winapi  :wacko:

 

Είναι C++11 feature, αλλά βέβαια υπάρχει απο καιρό στη Boost.

 

Με αυτό το hashtable θέλω να φτιάξω ενα αντεστραμένο ευρετήριο. Ανεβάζω την εκφώνηση για να μην υπάρχει παρερμήνευση.  Αυτο που έχω κάνει μέχρι στιγμής είναι να γράψω κώδικα για να διαβάζει ενα ενα τα αρχεία και να βάζει σε ενα string μία μία της λέξης(μονο της λέξης). Αν φτιάξω το hashtable θα παίρνω μία μία της λέξης και θα της βάζω εκεί(με μια διαδικασία και ελέγχους σίγουρα) αλλά νομίζω αυτή είναι η λογική. Τώρα προσπαθώ να φτιάξω ένα πίνακα κατακερματισμού με αλυσίδες. Νομίζω αυτό χρειάζεται.

 

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

 

Τέλος πάντων αν αξιοποιήσεις τη standard library της c++ μπορείς να βρεις πολλές έτοιμες υλοποιήσεις, ακόμα και το πιο απλό πράγμα θα δούλευε εδώ. Για παράδειγμα, δημιουργία ευρετηρίου για τις λέξεις που εμφανίζονται σε ένα συγκεκριμένο έγγραφο:

 

vector<string> words;                   // εδώ θα μπουν οι λέξεις
ifstream file("document.txt");          // ένα έγγραφο που θα κάνεις index
istream_iterator input(file), eof;
copy(file, eof, back_inserter(words));  // πρόσθεση των λέξεων στον πίνακα
sort(words.begin(), words.end());       // ταξινόμηση πίνακα λέξεων

// αφαίρεση διπλών καταχωρήσεων 
words.resize(distance(words.begin(), unique(words.begin(), words.end()));

 

6 γραμμές και δε χρειάστηκε να κάνεις απολύτως τίποτα, αν και βέβαια χρησιμοποιούμε τον ορισμό της standard library όσον αφορά το τι είναι "λέξη" (αλλά και πάλι, με μία remove_if στον ταξινομημένο πίνακα τα κανονίζεις όπως θες). Στη συνέχεια μπορείς απλά να κάνεις binary search για να δεις αν μια λέξη needle βρίσκεται στον πίνακα:

if (binary_search(words.begin(), words.end(), needle)) // βρέθηκε 

Αυτά τα λέω για να δεις ότι δε θέλει κόπο, θέλει τρόπο. Βέβαια εσύ θέλεις η κάθε λέξη να αντιστοιχίζεται στα έγγραφα μέσα στ α οποία εμφανίζεται. Για το σκοπό αυτό σου χρειάζεται ένας associative container όπως είναι ο map (που είναι tree) και ο unordered_map (που είναι hashtable). Παρόλο που τα 2 αυτά containers διαφέρουν τόσο στα χαρακτηριστικά τους (αυτά τα μάθατε στις δομές δεδομένων) όσο και στις απαιτήσεις που έχουν από τον τύπο κλειδιού (αυτά τα λέει το manual της C++), στη συγκεκριμένη περίπτωση και για κλειδί std::string που μιλάμε πρακτικά δεν υπάρχει διαφορά είτε χρησιμοποιήσεις το ένα είτε το άλλο.

 

Θα μπορούσες επομένως να πεις ότι θα έχω ένα map που αντιστοιχίζει string (λέξη) σε vector<string> (ονόματα αρχείων στα οποία η λέξη εμφανίζεται) και να παίξεις έτσι. Αλλά ακόμα κι αυτό είναι πιο δύσκολο απ' όσο χρειάζεται, γιατί υπάρχουν επίσης τα multimap και unordered_multimap που είναι όπως τα παραπάνω με μόνη διαφορά ότι επιτρέπονται διπλά κλειδιά. Έτσι, αντί για ένα μόνο κλειδί που αντιστοιχεί σε μια λίστα με Ν αρχεία, μπορείς πολύ πιο απλά να έχεις Ν αντίγραφα του κλειδιού το καθένα εκ των οποίων αντιστοιχεί σε 1 αρχείο -- θα σου διευκολύνει πάρα πολύ το γράψιμο του κώδικα.

 

Άρα:

multimap<string, string> index;

for ( .... έστω filename το όνομα κάθε εγγράφου που θα κάνεις index) {
    ifstream file(filename);
    istream_iterator input(file), eof;
    while(input != eof) {
        string word(*(input++));
        // εδώ κάνεις κανονικοποίηση του word όπως νομίζεις εσύ
        index.insert(make_pair(word, file));
    }
}

 

...και αυτό ήταν αρκετό για να κάνεις το index.

 

Τώρα αν θέλεις να δεις σε ποιά έγγραφα εμφανίζεται η λέξη foo:

auto boundaries = index.equal_range("foo");
for (auto i = boundaries.first; i != boundaries.second; ++i) {
    cout << i->second << endl;
} 

 

Είμαι βέβαιος πως πολλά από αυτά που αναφέρω σου είναι άγνωστα (και ίσως και καλύτερα γιατί δεν ήθελα να δώσω έτοιμη λύση) αλλά νομίζω πως το γεγονός ότι με 10 σειρές κώδικα έχεις καθαρίσει με το index και το searching επιλέγοντας μάλιστα σαν κύριος και το αν θέλεις tree ή hashtable μιλάει από μόνο του όσον αφορά το αν αξίζει να γράψεις κάτι μόνος σου από την αρχή. Αξίζει για να μάθεις τι κάνει η standard library και με 10 σειρές σε κάνει μάγκα, δεν αξίζει για να λύσεις την άσκηση.

 

Αν θέλεις να το ψάξεις περισσότερο μπορείς να χρησιμοποιήσεις για αναφορά τα cplusplus.com και cppreference.com ή να ρωτήσεις εδώ. Προσωπικά εφόσον οι γνώσεις σου στη C++ είναι περιορισμένες όπως μας είπες αλλά το ίδιο ισχύει και για τις γνώσεις σου σχετικά με τους hashtables όπως προκύπτει από τις ερωτήσεις σου, νομίζω ότι πιο κερδισμένος θα βγεις μαθαίνοντας να αξιοποιείς τα πλούσια ελέη της standard library παρά να παιδευτείς να το κάνεις manually.

 

PS: Δεν κατάλαβα καθόλου από την εκφώνηση που κολλάνε τα skip lists.

  • Like 2
Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Δημοσ. (επεξεργασμένο)

Δυστηχώς το visual studio 2008 που χρησιμοποιώ δεν υποστηρίζει το #include <unordered_map> ακόμα και αν βάλω το using namespace std::tr1;. Έχω μείνει λίγο έκπληκτος από το τι μπορεί να γίνει άμα χρησιμοποιήσει κάποιος τη standar library αλλά σίγουρα πολλά από αυτά δε θα μπορούσα να τα χρησιμοποιήσω μιας και ο σκοπός της άσκησης είναι να μάθω. Παρόλα αυτά και ο ίδιος ο καθηγητής λέει πως μπορούμε να χρησιμοποιήσουμε κώδικα για τον πίνακα κατακερματισμού από 3ους μιας και δεν είναι ο σκοπός του μαθήματος να φτιάξουμε κάτι τέτοιο. Προσπαθώ να φτιάξω τον δικό μου αλλά είμαι αρκετά μπερδεμένος με το πόσο μεγάλος πρέπει να είναι ο πίνακας μιας και στη συγκεκριμένη περίπτωση πρέπει να ευρετηριάσω πάρα πολλές λέξεις και από ότι έχω καταλάβει το έυρος του πίνακα εξαρτάται πολύ απο τη συνάρτηση(hashing) που θα της δίνω ως όρισμα τη λέξη και θα μου επιστρέφει ενα κλειδί(σε μορφή int). Επειδή δεν ξέρω αν θα βγάλω άκρη άμα κάποιος ξέρει που μπορώ να βρω έτοιμο κώδικα για να δημιουργίσω έναν πίνακα κατακερματισμού όπου το  hash function θα παίρνει ως όρισμα string και θα επιστρέφει τιμή int(οπού σε αυτή τη θέση του πίνακα θα βάζω τα στοιχεία μου) θα με βοηθούσε πάρα πολύ.

Επεξ/σία από realez
Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Δυστηχώς το visual studio 2008 που χρησιμοποιώ δεν υποστηρίζει το #include <unordered_map> ακόμα και αν βάλω το using namespace std::tr1;

 

ΟΚ, βάλε απλό map τότε. Επίσης, σίγουρα έχεις δωρεάν πρόσβαση σε VS 2010 και 2012 μέσω του ιδρύματος αν είσαι σε δημόσιο, και αν δεν έχεις πάλι νομίζω πως υπάρχει δωρεάν edition με τον compiler και τις libraries οπότε no problem.

 

 

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

 

Δε μπορεί σε σοβαρή λύση ο πίνακας να έχει στάνταρ μέγεθος. Όταν ο πίνακας γεμίσει αρκετά (ανεβαίνει το load factor που λέμε) θα πρέπει να κάνεις allocate έναν μεγαλύτερο και rehash όλα τα περιεχόμενα (γιατί μπορεί να καταλήξουν σε άλλη θέση στο νέο μεγαλύτερο πίνακα).

 

Για το άλλο που λες, υπάρχει μια... ελαφρά διαφωνία με τον migf1  :P αλλά η άποψή μου (και επίσης ο τρόπος με τον οποίο υλοποιείται το στάνταρ hashtable σε όλες τις γλώσσες όπου ξέρω πώς υλοποιούνται) είναι πως πρέπει να κάνεις μια function που να σου γυρνάει μια τιμή σε ένα "μεγάλο" διάστημα, άσχετο με το μέγεθος του πίνακα. Ας πούμε μια 32 ή 64 bit τιμή. Αυτήν τη γράφεις μια φορά και ξεμπερδεύεις. Όταν θα θέλεις να τη χρησιμοποιήσεις στην πράξη, θα πάρεις την επιστρεφόμενη τιμή και θα την κάνεις modulo Ν όπου Ν το μέγεθος του πίνακα για να μπορείς να τη χρησιμοποιήσεις άμεσα σα θέση.

 

Επειδή δεν ξέρω αν θα βγάλω άκρη άμα κάποιος ξέρει που μπορώ να βρω έτοιμο κώδικα για να δημιουργίσω έναν πίνακα κατακερματισμού όπου το  hash function θα παίρνει ως όρισμα string και θα επιστρέφει τιμή int(οπού σε αυτή τη θέση του πίνακα θα βάζω τα στοιχεία μου) θα με βοηθούσε πάρα πολύ.

 

Πρώτο result στο google που έκανα, έτοιμη η hash function: http://stackoverflow.com/questions/7666509/hash-function-for-string

 

PS: Εφόσον απ όσο βλέπω δεν απαγορεύεται η standard library, δείξε μου έναν καθηγητή που θα του κάνεις αυτή τη λύση και θα σου πει δεν τη δέχομαι.

Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Δημοσ. (επεξεργασμένο)

Κάπου δίαβασα για το md5  http://bobobobo.wordpress.com/2010/10/17/md5-c-implementation/ και νομίζω πως είναι αυτό που χρειάζομαι.(ίσως όχι το τέλειο αλλά από το να μην τρέχει καθόλου και να μηδενιστώ  :ph34r:  ) Εάν είναι αυτό μπορεί κάποιος να μ δώσει οδηγίες για το πως θα το βάλω σε λειτουργία.( δεν έχω ξαναπάρει τέτοιο κώδικα ποτέ)



Αυτό που μου έστειλες πρέπει να το αλλάξω για string και να αλλάξω το return σε hash % m (m το μέγεθος του πίνακα) ώστε να επιστρέφει τιμές για τον πίνακα μου; Φένεται πολύ πιο απλό από το md5 :-D

 

unsigned long hash(unsigned char *str)
{
unsigned long hash = 5381;
int c;

while (c = *str++)
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

return hash;
}

 

unsigned long djb2(const string& str)
{
unsigned long hash = 5381;

for(string::const_iterator it=str.begin();it!=str.end();it++)
hash = ((hash << 5) + hash) + *it; /* hash * 33 + character */

return hash;
}
Επεξ/σία από realez
Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Δημιουργήστε ένα λογαριασμό ή συνδεθείτε για να σχολιάσετε

Πρέπει να είστε μέλος για να αφήσετε σχόλιο

Δημιουργία λογαριασμού

Εγγραφείτε με νέο λογαριασμό στην κοινότητα μας. Είναι πανεύκολο!

Δημιουργία νέου λογαριασμού

Σύνδεση

Έχετε ήδη λογαριασμό; Συνδεθείτε εδώ.

Συνδεθείτε τώρα
  • Δημιουργία νέου...