๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Dictionary Look-Up with One Error

โœ Scribed by Andrew C. Yao; Frances F. Yao

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
136 KB
Volume
25
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

โœฆ Synopsis

Let W be a set of n binary strings of length m each. We are interested in designing data structures for W that can answer d-queries quickly; that is, given in a binary string โฃ, decide whether there is any member of W within Hamming distance d of โฃ. The problem, originally raised by Minsky and Papert, remains a challenge in data structure design. In this paper, we make an initial effort toward a theoretical study of the small d case. Our main result is a data structure that ลฝ . ลฝ . achieves O m log log n query time with O nm log m space for the d s 1 case.

๐Ÿ“œ SIMILAR VOLUMES

Text Indexing and Dictionary Matching wi
Text Indexing and Dictionary Matching with One Error
โœ Amihood Amir; Dmitry Keselman; Gad M. Landau; Moshe Lewenstein; Noa Lewenstein; ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 109 KB
One-pass text compression with a subword
One-pass text compression with a subword dictionary
โœ Jakobsson, Matti ๐Ÿ“‚ Article ๐Ÿ“… 1988 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 842 KB

## A new one-phase technique for compression text files is presented as a modification of the Ziv and Lempel compression scheme. The method replaces parts of words in a text by references to a fixed-size dictionary which contains the subwords of the text already compressed. An essential part of the

Effects of record linkage errors on regi
Effects of record linkage errors on registry-based follow-up studies
โœ Hermann Brenner; Irene Schmidtmann; Christa Stegmaier ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 190 KB ๐Ÿ‘ 1 views

The importance of reliable record linkage for high quality-population-based disease registration is widely recognized. Systematic methodologic work is lacking, however, on the effects of record linkage errors on the use of disease registries for epidemiologic purposes. The present paper provides alg