Fragmentary pattern matching: Complexity, algorithms and applications for analyzing classic literary works

Hideaki Hori; Shinichi Shimozono; Masayuki Takeda; Ayumi Shinohara

doi:10.1007/3-540-45678-3_61

Fragmentary pattern matching: Complexity, algorithms and applications for analyzing classic literary works

Hideaki Hori, Shinichi Shimozono, Masayuki Takeda, Ayumi Shinohara

INF - System Information Sciences

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

6 Citations (Scopus)

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 polynomialtime 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.

Original language	English
Title of host publication	Algorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings
Pages	719-730
Number of pages	12
DOIs	https://doi.org/10.1007/3-540-45678-3_61
Publication status	Published - 2001
Event	12th International Symposium on Algorithms and Computation, ISAAC 2001 - Christchurch, New Zealand Duration: 2001 Dec 19 → 2001 Dec 21

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2223 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	12th International Symposium on Algorithms and Computation, ISAAC 2001
Country/Territory	New Zealand
City	Christchurch
Period	01/12/19 → 01/12/21

Keywords

Fragmentary pattern
NP-completeness
Polynomial-time approximation
String matching
String resemblance

Access to Document

10.1007/3-540-45678-3_61

Cite this

Hori, H., Shimozono, S., Takeda, M., & Shinohara, A. (2001). Fragmentary pattern matching: Complexity, algorithms and applications for analyzing classic literary works. In Algorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings (pp. 719-730). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2223 LNCS). https://doi.org/10.1007/3-540-45678-3_61

Hori, Hideaki ; Shimozono, Shinichi ; Takeda, Masayuki et al. / Fragmentary pattern matching : Complexity, algorithms and applications for analyzing classic literary works. Algorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings. 2001. pp. 719-730 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{13f7962c5098407e83333bf1c37a756a,

title = "Fragmentary pattern matching: Complexity, algorithms and applications for analyzing classic literary works",

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 polynomialtime 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.",

keywords = "Fragmentary pattern, NP-completeness, Polynomial-time approximation, String matching, String resemblance",

author = "Hideaki Hori and Shinichi Shimozono and Masayuki Takeda and Ayumi Shinohara",

year = "2001",

doi = "10.1007/3-540-45678-3_61",

language = "English",

isbn = "3540429859",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "719--730",

booktitle = "Algorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings",

note = "12th International Symposium on Algorithms and Computation, ISAAC 2001 ; Conference date: 19-12-2001 Through 21-12-2001",

}

Hori, H, Shimozono, S, Takeda, M & Shinohara, A 2001, Fragmentary pattern matching: Complexity, algorithms and applications for analyzing classic literary works. in Algorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2223 LNCS, pp. 719-730, 12th International Symposium on Algorithms and Computation, ISAAC 2001, Christchurch, New Zealand, 01/12/19. https://doi.org/10.1007/3-540-45678-3_61

Fragmentary pattern matching: Complexity, algorithms and applications for analyzing classic literary works. / Hori, Hideaki; Shimozono, Shinichi; Takeda, Masayuki et al.
Algorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings. 2001. p. 719-730 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2223 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Fragmentary pattern matching

T2 - 12th International Symposium on Algorithms and Computation, ISAAC 2001

AU - Hori, Hideaki

AU - Shimozono, Shinichi

AU - Takeda, Masayuki

AU - Shinohara, Ayumi

PY - 2001

Y1 - 2001

N2 - 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 polynomialtime 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.

AB - 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 polynomialtime 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.

KW - Fragmentary pattern

KW - NP-completeness

KW - Polynomial-time approximation

KW - String matching

KW - String resemblance

UR - http://www.scopus.com/inward/record.url?scp=33646473101&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33646473101&partnerID=8YFLogxK

U2 - 10.1007/3-540-45678-3_61

DO - 10.1007/3-540-45678-3_61

M3 - Conference contribution

AN - SCOPUS:33646473101

SN - 3540429859

SN - 9783540429852

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 719

EP - 730

BT - Algorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings

Y2 - 19 December 2001 through 21 December 2001

ER -

Hori H, Shimozono S, Takeda M, Shinohara A. Fragmentary pattern matching: Complexity, algorithms and applications for analyzing classic literary works. In Algorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings. 2001. p. 719-730. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-45678-3_61

Fragmentary pattern matching: Complexity, algorithms and applications for analyzing classic literary works

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this