Back to Search
Start Over
On Levenshtein’s Channel and List Size in Information Retrieval.
- Source :
- IEEE Transactions on Information Theory; Jun2021, Vol. 67 Issue 6, p3322-3341, 20p
- Publication Year :
- 2021
-
Abstract
- The Levenshtein’s channel model for substitution errors is relevant in information retrieval where information is received through many noisy channels. In each of the channels there can occur at most t errors and the decoder tries to recover the information with the aid of the channel outputs. Recently, Yaakobi and Bruck considered the problem where the decoder provides a list instead of a unique output. If the underlying code C ⊆ F<subscript>2</subscript><superscript>n</superscript> has error-correcting capability e, we write t = e + ℓ, (ℓ ≥ 1). In this paper, we provide new (constant) bounds on the size of the list. In particular, we give using the Sauer-Shelah lemma the upper bound ℓ + 1 on the list size for large enough n provided that we have a sufficient number of channels. We also show that the bound ℓ + 1 is the best possible. Most of our other new results rely on constant weight codes. [ABSTRACT FROM AUTHOR]
- Subjects :
- INFORMATION retrieval
SIZE
Subjects
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 67
- Issue :
- 6
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 150448688
- Full Text :
- https://doi.org/10.1109/TIT.2020.3016269