Fragmentary Pattern Matching: Complexity, Algorithms and Applications for Analyzing Classic Literary Works
Pages 719 - 730
Abstract
A fragmentary pattern is a multiset of non-empty strings, and it matches a string w if all the strings in it occur within w without any overlaps. We study some fundamental issues on computational complexity related to the matching of fragmentary patterns. We show that the fragmentary pattern matching problem is NP-complete, and the problem to find a fragmentary pattern common to two strings that maximizes the pattern score is NP-hard. Moreover, we propose a polynomial-time approximation algorithm for the fragmentary pattern matching, and show that it achieves a constant worst-case approximation ratio if either the strings in a pattern have the same length, or the importance weights of strings in a pattern are proportional to their lengths.
References
[1]
D. Angluin. Finding patterns common to a set of strings. J. Comput. Sys. Sci., 21:46-62, 1980.
[2]
D. Angluin. Learning regular sets from queries and counterexamples. Information and Computation, 75(2):87-106, 1987.
[3]
D. Angluin. Queries and concept learning. Machine Learning, 2(4):319-342, 1988.
[4]
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti- Spaccamela, and M. Protasi. Complexity and Approximation. Springer-Verlag, Berlin, 1999.
[5]
G. Ausiello, P. Crescenzi, and M. Protasi. Approximate solution of NP optimization problems. Theor. Comput. Sci., 150: 1-55, 1995.
[6]
A. Z. Broder. On the resemblance and containment of documents. In Proc. Compression and Complexity of Sequences (SEQUENCES'97), pages 21-29, 1997.
[7]
M. Crochemore and W. Rytter. Text Algorithms. Oxford University Press, New York, 1994.
[8]
M. R. Garey and D. S. Johnson. Computers and Intractability. W. H. Freeman & Co., New York, 1979.
[9]
G. Das, R. Fleischer, L. Gasieniec, D. Gunopulos, and J. Karkkainen. Episode Matching. In Proc. 8th Annual Symposium on Combinatorial Pattern Matching (CPM'97), pages 12-27, 1997.
[10]
D. Gusfield. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, New York, 1997.
[11]
T. Kadota, M. Hirao, A. Ishino, M. Takeda, A. Shinohara, and F. Matsuo. Musical sequence comparison for melodic and rhythmic similarities. In Proc. 8th International Symposium on String Processing and Information Retrieval (SPIRE2001), 2001, to appear.
[12]
S. Shimozono, H. Arimura, and S. Arikawa. Efficient discovery of optimal word-association patterns in large databases. New Gener. Comput., 18(1):49-60, 2000.
[13]
M. Takeda, T. Fukuda, I. Nanri, M. Yamasaki, and K. Tamari. Discovering instances of poetic allusion from anthologies of classical Japanese poems. Theor. Comput. Sci., 2001, to appear.
[14]
K. Yamamoto, M. Takeda, A. Shinohara, T. Fukuda, and I. Nanri. Discovering repetitive expressions and affinities from anthologies of classical Japanese poems. In Proc. 4th International Conference on Discovery Science (DS2001), 2001, to appear.
- Fragmentary Pattern Matching: Complexity, Algorithms and Applications for Analyzing Classic Literary Works
Recommendations
Fragmentary Pattern Matching: Complexity, Algorithms and Applications for Analyzing Classic Literary Works
ISAAC '01: Proceedings of the 12th International Symposium on Algorithms and ComputationA fragmentary pattern is a multiset of non-empty strings, and it matches a string w if all the strings in it occur within w without any overlaps. We study some fundamental issues on computational complexity related to the matching of fragmentary ...
Parity Permutation Pattern Matching
WALCOM: Algorithms and ComputationAbstractGiven two permutations, a pattern and a text , Parity Permutation Pattern Matching asks whether there exists a parity and order preserving embedding of into . While it is known that Permutation Pattern Matching is in , we show that adding the ...
Palindrome pattern matching
A palindrome is a string that reads the same forward and backward. For a string x, let Pals(x) be the set of all maximal palindromes of x, where each maximal palindrome in Pals(x) is encoded by a pair (c,r) of its center c and its radius r. Given a text ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 19 December 2001
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 02 Feb 2025