Discovering best variable-length-don’t-care patterns

Shunsuke Inenaga; Hideo Bannai; Ayumi Shinohara; Masayuki Takeda; Setsuo Arikawa

doi:10.1007/3-540-36182-0_10

Discovering best variable-length-don’t-care patterns

Shunsuke Inenaga, Hideo Bannai, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa

Mathematical Informatics

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

13 Citations (Scopus)

Abstract

A variable-length-don’t-care pattern (VLDC pattern) is an element of set Π = (Σ∪{∗})^∗, where Σ is an alphabet and ∗ is a wildcard matching any string in Σ^∗. Given two sets of strings, we consider the problem of finding the VLDC pattern that is the most common to one, and the least common to the other. We present a practical algorithm to find such best VLDC patterns exactly, powerfully sped up by pruning heuristics. We introduce two versions of our algorithm: one employs a pattern matching machine (PMM) whereas the other does an index structure called the Wildcard Directed Acyclic Word Graph (WDAWG). In addition, we consider a more generalized problem of finding the best pair ‹q, k›, where k is the window size that specifies the length of an occurrence of the VLDC pattern q matching a string w. We present three algorithms solving this problem with pruning heuristics, using the dynamic programming (DP), PMMs and WDAWGs, respectively. Although the two problems are NP-hard, we experimentally show that our algorithms run remarkably fast.

Original language	English
Title of host publication	Discovery Science - 5th International Conference, DS 2002, Proceedings
Editors	Steffen Lange, Ken Satoh, Carl H. Smith
Publisher	Springer Verlag
Pages	86-97
Number of pages	12
ISBN (Print)	3540001883, 9783540001881
DOIs	https://doi.org/10.1007/3-540-36182-0_10
Publication status	Published - 2002
Event	5th International Conference on Discovery Science, DS 2002 - Lubeck, Germany Duration: Nov 24 2002 → Nov 26 2002

Publication series

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

Other

Other	5th International Conference on Discovery Science, DS 2002
Country/Territory	Germany
City	Lubeck
Period	11/24/02 → 11/26/02

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/3-540-36182-0_10

Cite this

Inenaga, S., Bannai, H., Shinohara, A., Takeda, M., & Arikawa, S. (2002). Discovering best variable-length-don’t-care patterns. In S. Lange, K. Satoh, & C. H. Smith (Eds.), Discovery Science - 5th International Conference, DS 2002, Proceedings (pp. 86-97). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2534). Springer Verlag. https://doi.org/10.1007/3-540-36182-0_10

Discovering best variable-length-don’t-care patterns. / Inenaga, Shunsuke; Bannai, Hideo; Shinohara, Ayumi et al.
Discovery Science - 5th International Conference, DS 2002, Proceedings. ed. / Steffen Lange; Ken Satoh; Carl H. Smith. Springer Verlag, 2002. p. 86-97 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2534).

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

Inenaga, S, Bannai, H, Shinohara, A, Takeda, M & Arikawa, S 2002, Discovering best variable-length-don’t-care patterns. in S Lange, K Satoh & CH Smith (eds), Discovery Science - 5th International Conference, DS 2002, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2534, Springer Verlag, pp. 86-97, 5th International Conference on Discovery Science, DS 2002, Lubeck, Germany, 11/24/02. https://doi.org/10.1007/3-540-36182-0_10

Inenaga S, Bannai H, Shinohara A, Takeda M, Arikawa S. Discovering best variable-length-don’t-care patterns. In Lange S, Satoh K, Smith CH, editors, Discovery Science - 5th International Conference, DS 2002, Proceedings. Springer Verlag. 2002. p. 86-97. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-36182-0_10

Inenaga, Shunsuke ; Bannai, Hideo ; Shinohara, Ayumi et al. / Discovering best variable-length-don’t-care patterns. Discovery Science - 5th International Conference, DS 2002, Proceedings. editor / Steffen Lange ; Ken Satoh ; Carl H. Smith. Springer Verlag, 2002. pp. 86-97 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{79f787f8039c45bea00adc098da79559,

title = "Discovering best variable-length-don{\textquoteright}t-care patterns",

abstract = "A variable-length-don{\textquoteright}t-care pattern (VLDC pattern) is an element of set Π = (Σ∪{∗})∗, where Σ is an alphabet and ∗ is a wildcard matching any string in Σ∗. Given two sets of strings, we consider the problem of finding the VLDC pattern that is the most common to one, and the least common to the other. We present a practical algorithm to find such best VLDC patterns exactly, powerfully sped up by pruning heuristics. We introduce two versions of our algorithm: one employs a pattern matching machine (PMM) whereas the other does an index structure called the Wildcard Directed Acyclic Word Graph (WDAWG). In addition, we consider a more generalized problem of finding the best pair ‹q, k›, where k is the window size that specifies the length of an occurrence of the VLDC pattern q matching a string w. We present three algorithms solving this problem with pruning heuristics, using the dynamic programming (DP), PMMs and WDAWGs, respectively. Although the two problems are NP-hard, we experimentally show that our algorithms run remarkably fast.",

author = "Shunsuke Inenaga and Hideo Bannai and Ayumi Shinohara and Masayuki Takeda and Setsuo Arikawa",

year = "2002",

doi = "10.1007/3-540-36182-0_10",

language = "English",

isbn = "3540001883",

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

publisher = "Springer Verlag",

pages = "86--97",

editor = "Steffen Lange and Ken Satoh and Smith, {Carl H.}",

booktitle = "Discovery Science - 5th International Conference, DS 2002, Proceedings",

address = "Germany",

note = "5th International Conference on Discovery Science, DS 2002 ; Conference date: 24-11-2002 Through 26-11-2002",

}

TY - GEN

T1 - Discovering best variable-length-don’t-care patterns

AU - Inenaga, Shunsuke

AU - Bannai, Hideo

AU - Shinohara, Ayumi

AU - Takeda, Masayuki

AU - Arikawa, Setsuo

PY - 2002

Y1 - 2002

N2 - A variable-length-don’t-care pattern (VLDC pattern) is an element of set Π = (Σ∪{∗})∗, where Σ is an alphabet and ∗ is a wildcard matching any string in Σ∗. Given two sets of strings, we consider the problem of finding the VLDC pattern that is the most common to one, and the least common to the other. We present a practical algorithm to find such best VLDC patterns exactly, powerfully sped up by pruning heuristics. We introduce two versions of our algorithm: one employs a pattern matching machine (PMM) whereas the other does an index structure called the Wildcard Directed Acyclic Word Graph (WDAWG). In addition, we consider a more generalized problem of finding the best pair ‹q, k›, where k is the window size that specifies the length of an occurrence of the VLDC pattern q matching a string w. We present three algorithms solving this problem with pruning heuristics, using the dynamic programming (DP), PMMs and WDAWGs, respectively. Although the two problems are NP-hard, we experimentally show that our algorithms run remarkably fast.

AB - A variable-length-don’t-care pattern (VLDC pattern) is an element of set Π = (Σ∪{∗})∗, where Σ is an alphabet and ∗ is a wildcard matching any string in Σ∗. Given two sets of strings, we consider the problem of finding the VLDC pattern that is the most common to one, and the least common to the other. We present a practical algorithm to find such best VLDC patterns exactly, powerfully sped up by pruning heuristics. We introduce two versions of our algorithm: one employs a pattern matching machine (PMM) whereas the other does an index structure called the Wildcard Directed Acyclic Word Graph (WDAWG). In addition, we consider a more generalized problem of finding the best pair ‹q, k›, where k is the window size that specifies the length of an occurrence of the VLDC pattern q matching a string w. We present three algorithms solving this problem with pruning heuristics, using the dynamic programming (DP), PMMs and WDAWGs, respectively. Although the two problems are NP-hard, we experimentally show that our algorithms run remarkably fast.

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

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

U2 - 10.1007/3-540-36182-0_10

DO - 10.1007/3-540-36182-0_10

M3 - Conference contribution

AN - SCOPUS:84949815829

SN - 3540001883

SN - 9783540001881

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

SP - 86

EP - 97

BT - Discovery Science - 5th International Conference, DS 2002, Proceedings

A2 - Lange, Steffen

A2 - Satoh, Ken

A2 - Smith, Carl H.

PB - Springer Verlag

T2 - 5th International Conference on Discovery Science, DS 2002

Y2 - 24 November 2002 through 26 November 2002

ER -

Discovering best variable-length-don’t-care patterns

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this