Εύρεση τέλειας συνάρτησης κατακερματισμού με τη χρήση στοχαστικού αλγόριθμου (καταργήθηκε 2007)

Η στατική δομή αναζήτησης είναι ένας αφηρημένος τύπος δεδομένων ο οποίος επιτρέπει την εισαγωγή και την αναζήτηση στοιχείων. Όλες οι εισαγωγές γίνονται πριν από τις αναζητήσεις με αποτέλεσμα να είναι δυνατός ο υπολογισμός μιας στατικής δομής που να επιτρέπει τη γρήγορη εύρεση στοιχείων. Μια τέτοια δομή μπορεί να βασίζεται σε συνάρτηση κατακερματισμού. Για παράδειγμα, το πρόγραμμα gperf υπολογίζει βέλτιστες τέτοιες συναρτήσεις για χρήση στο τμήμα της λεκτικής ανάλυσης μεταγλωττιστών. Η πληθώρα των δυνατών συναρτήσεων κατακερματισμού και ο εύκολος τρόπος αξιολόγησής τους επιτρέπουν τη χρήση γενετικών αλγορίθμων για την "εξέλιξη" μιας βέλτιστης συνάρτησης από έναν πληθυσμό δυνατών συναρτήσεων. Η εργασία περιλαμβάνει τη χρήση γενετικών αλγορίθμων για τον υπολογισμό βέλτιστων συναρτήσεων κατακερματισμού. Η δυναμική αποτίμηση της συνάρτησης μπορεί να οδηγήσει σε αποδοτικό αλγόριθμο αναζήτησης.

Βιβλιογραφία

David E. Goldberg. Genetic Algorithms: In Search of Optimization & Machine Learning. Addison-Wesley, 1989.
Schmidt, Douglas C. GPERF: A Perfect Hash Function Generator Second USENIX C++ Conference Proceedings, April 1990.
Χρήστος Κοίλιας Δομές Δεδομένων και Οργανώσεις Αρχείων. σ. 208-221 Εκδόσεις Νέων Τεχνολογιών, 1993.
Donald E. Knuth. The Art of Computer Programming, volume 3 / Searching and Sorting. Addison-Wesley, second edition, 1973.
Andrew Hume. Grep wars: The strategic search initiative. In Proceedings of the EUUG Spring 88 Conference, pages 237-245. European UNIX User Group, 1988.
Niklaus Wirth. Algorithms + Datastructures = Programs. p. 169-280. Prentice-Hall, 1976.
Chang, C.C.: A Scheme for Constructing Ordered Minimal Perfect Hashing Functions Information Sciences 39(1986), 187-195.
Cichelli, Richard J. Author's Response to "On Cichelli's Minimal Perfect Hash Functions Method" Communications of the ACM, 23, 12(December 1980), 729.
Cichelli, Richard J. Minimal Perfect Hash Functions Made Simple Communications of the ACM, 23, 1(January 1980), 17-19.
Cook, C. R. and Oldehoeft, R.R. A Letter Oriented Minimal Perfect Hashing Function SIGPLAN Notices, 17, 9(September 1982), 18-27.
Cormack, G. V. and Horspool, R. N. S. and Kaiserwerth, M. Practical Perfect Hashing Computer Journal, 28, 1(January 1985), 54-58.
Jaeschke, G. Reciprocal Hashing: A Method for Generating Minimal Perfect Hashing Functions Communications of the ACM, 24, 12(December 1981), 829-833.
Jaeschke, G. and Osterburg, G. On Cichelli's Minimal Perfect Hash Functions Method Communications of the ACM, 23, 12(December 1980), 728-729.
Sager, Thomas J. A Polynomial Time Generator for Minimal Perfect Hash Functions Communications of the ACM, 28, 5(December 1985), 523-532
Sebesta, R.W. and Taylor, M.A. Minimal Perfect Hash Functions for Reserved Word Lists SIGPLAN Notices, 20, 12(September 1985), 47-53.
Sprugnoli, R. Perfect Hashing Functions: A Single Probe Retrieving Method for Static Sets Communications of the ACM, 20 11(November 1977), 841-850.