期刊
ALGORITHMS
卷 14, 期 4, 页码 -出版社
MDPI
DOI: 10.3390/a14040116
关键词
communication complexity; Hamming distance; Lempel-Ziv compression
资金
- JSPS KAKENHI [JP18K18002, JP20H04141, JP18H04098]
- JST PRESTO [JPMJPR1922]
This article discusses the communication complexity of the Hamming distance of two strings and proposes a new protocol based on the representation of LZ77 without self-references. Original complexity analysis is conducted by introducing Crochemore's C-factorization and Rytter's AVL-grammar.
We consider the communication complexity of the Hamming distance of two strings. Bille et al. [SPIRE 2018] considered the communication complexity of the longest common prefix (LCP) problem in the setting where the two parties have their strings in a compressed form, i.e., represented by the Lempel-Ziv 77 factorization (LZ77) with/without self-references. We present a randomized public-coin protocol for a joint computation of the Hamming distance of two strings represented by LZ77 without self-references. Although our scheme is heavily based on Bille et al.'s LCP protocol, our complexity analysis is original which uses Crochemore's C-factorization and Rytter's AVL-grammar. As a byproduct, we also show that LZ77 with/without self-references are not monotonic in the sense that their sizes can increase by a factor of 4/3 when a prefix of the string is removed.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据