solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看6116次
From Clustering Supersequences to Entropy Minimizing Subsequences for Single and Double Deletions. (arXiv:1802.00703v1 [cs.IT])
来源于:arXiv
A binary string transmitted via a memoryless i.i.d. deletion channel is
received as a subsequence of the original input. From this, one obtains a
posterior distribution on the channel input, corresponding to a set of
candidate supersequences weighted by the number of times the received
subsequence can be embedded in them. In a previous work it is conjectured on
the basis of experimental data that the entropy of the posterior is minimized
and maximized by the constant and the alternating strings, respectively. In
this work, we present an algorithm for counting the number of subsequence
embeddings using a run-length encoding of strings. We then describe two
different ways of clustering the space of supersequences and prove that their
cardinality depends only on the length of the received subsequence and its
Hamming weight, but not its exact form. Then, we consider supersequences that
contain a single embedding of a fixed subsequence, referred to as singletons,
and provide a closed form e 查看全文>>