Alphabet indexing for approximating features of symbols |
| |
Authors: | Shinichi Shimozono |
| |
Affiliation: | Department of Artificial Intelligence, Kyushu Institute of Technology, Iizuka, 820, Japan |
| |
Abstract: | We consider two maximization problems to find a mapping from a large alphabet forming given two sets of strings to a set of a very few symbols specifying a symbol wise transformation of strings. First we show that the problem to find a mapping that transforms the most of the strings as to form disjoint sets cannot be approximated within a ratio n1/16 in polynomial time, unless P = NP. Next we consider a mapping that retains the difference of the maximum number of pairs of strings over the given sets. We present a polynomial-time approximation algorithm that guarantees a ratio k/(k − 1) for mappings to k symbols, as well as proving that the problem is hard to approximate within an arbitrary small ratio in polynomial time. Furthermore, we extend this algorithm as to deal with not only pairs but also tuples of strings and show that it achieves a constant approximation ratio. |
| |
Keywords: | Alphabet indexing Polynomial-time approximation Nonapproximability Knowledge acquistion Data compression |
本文献已被 ScienceDirect 等数据库收录! |
|