Minimal and Almost Minimal Perfect Hash Function Search with Application to Natural Language Lexicon Design

Get BibTex-formatted data

Author

Nick Cercone,Max Krause,John Boates

Entry type

article

Abstract

New methods for computing perfect hash functions and applications of such functions to the problems of lexicon design are reported in this paper. After stating the problem and briefly discussing previous solutions, we present Cichelli's algorithm, which introduced the form of the solutions we have pursued in this research. An informal analysis of the problemis given, followed by a presentation of three algorithms which refine and generalise Cichelli's method in different ways. We next report the results of applying programmed versions of these algorithms to problem sets drawn from natural and artificial languages. A discusion of conceptual designs for the application of perfect hash functions to small and large computer lexicons is followed by a summary of our research and suggestions for futher work.

Date

1983

Institution

Pergamon Press Ltd.

Journal

CAMWA

Key alpha

Cercone

Number

Pages

215-231

Volume

Publication Date

0000-00-00

Location

A hard-copy of this is in the Papers Cabinet

BibTex-formatted data

To refer to this entry, you may select and copy the text below and paste it into your BibTex document. Note that the text may not contain all macros that BibTex supports.

@Article{ Cercone,
	title = "Minimal and Almost Minimal Perfect Hash Function Search with Application to Natural Language Lexicon Design",
	author = "Nick Cercone,Max Krause,John Boates",
	year = "1983",
	institution = "Pergamon Press Ltd.",
	journal = "CAMWA",
	number = "1",
	pages = "215-231",
	volume = "9",
	abstract = "New methods for computing perfect hash functions and applications of such functions to
the problems of lexicon design are reported in this paper. After stating the problem
and briefly discussing previous solutions, we present Cichelli's algorithm, which
introduced the form of the solutions we have pursued in this research. An informal
analysis of the problemis given, followed by a presentation of three algorithms which
refine and generalise Cichelli's method in different ways. We next report the results
of applying programmed versions of these algorithms to problem sets drawn from natural
and artificial languages. A discusion of conceptual designs for the application
of perfect hash functions to small and large computer lexicons is followed by
a summary of our research and suggestions for futher work.",
}