Partial-Match Retrieval Algorithms

作者：Ronald L. Rivest · 发表于：SIAM Journal on Computing · 年份：1976 · DOI：10.1137/0205003 · 被引用次数：245 · 研究领域：Algorithms and Data Compression、Data Management and Algorithms、Advanced Image and Video Retrieval Techniques

We examine the efficiency of hash-coding and tree-search algorithms for retrieving from a file of k-letter words all words which match a partially-specified input query word (for example, retrieving all six-letter English words of the form S**R*H where “*” is a “don’t care” character). We precisely characterize those balanced hash-coding algorithms with minimum average number of lists examined. Use of the first few letters of each word as a list index is shown to be one such optimal algorithm. A new class of combinatorial designs (called associative block designs) provides better hash functions with a greatly reduced worst-case number of lists examined, yet with optimal average behavior maintained. Another efficient variant involves storing each word in several lists. Tree-search algorithms are shown to be approximately as efficient as hash-coding algorithms, on the average. In general, these algorithms require time about $O(n^{(k - s)/k} )$ to respond to a query word with s letters specified, given a file of nk-letter words. Previous algorithms either required time $O(s \cdot n/k)$ or else used exorbitant amounts of storage.