article

Identification of design motifs with pattern matching algorithms

Authors:

Olivier Kaczor,

Yann-Gaël Guéhéneuc,

Sylvie HamelAuthors Info & Claims

Information and Software Technology, Volume 52, Issue 2

Pages 152 - 168

https://doi.org/10.1016/j.infsof.2009.08.006

Published: 01 February 2010 Publication History

Abstract

Design patterns are important in software maintenance because they help in understanding and re-engineering systems. They propose design motifs, solutions to recurring design problems. The identification of occurrences of design motifs in large systems consists of identifying classes whose structure and organization match exactly or approximately the structure and organization of classes as suggested by the motif. We adapt two classical approximate string matching algorithms based on automata simulation and bit-vector processing to efficiently identify exact and approximate occurrences of motifs. We then carry out two case studies to show the performance, precision, and recall of our algorithms. In the first case study, we assess the performance of our algorithms on seven medium-to-large systems. In the second case study, we compare our approach with three existing approaches (an explanation-based constraint approach, a metric-enhanced explanation-based constraint approach, and a similarity scoring approach) by applying the algorithms on three small-to-medium size systems, JHotDraw, Juzzle, and QuickUML. Our studies show that approximate string matching based on bit-vector processing provides efficient algorithms to identify design motifs.

References

[1]

J. Koskinen, Software maintenance costs, web site (September 2004). <http://www.cs.jyu.fi/~koskinen/smcosts.htm>.

[2]

Lientz, B.P. and Swanson, E.B., Problems in application software maintenance. Communications of the ACM. v24 i11. 763-769.

Digital Library

[3]

Biggerstaff, T.J., Mitbander, B.G. and Webster, D.E., The concept assignment problem in program understanding. In: Basili, V.R., DeMillo, R.A., Katayama, T. (Eds.), Proceedings of the 15th International Conference on Software Engineering, IEEE Computer Society Press/ACM Press. pp. 482-498.

Digital Library

[4]

Gamma, E., Helm, R., Johnson, R. and Vlissides, J., Design Patterns - Elements of Reusable Object-Oriented Software. 1994. first ed. Addison-Wesley.

Digital Library

[5]

Wuyts, R., Declarative reasoning about the structure of object-oriented systems. In: Gil, J. (Ed.), Proceedings of the 26th Conference on the Technology of Object-Oriented Languages and Systems, IEEE Computer Society Press. pp. 112-124.

Digital Library

[6]

Quilici, A., Yang, Q. and Woods, S., Applying plan recognition algorithms to program understanding. Journal of Automated Software Engineering. v5 i3. 347-372.

Digital Library

[7]

Antoniol, G., Fiutem, R. and Cristoforetti, L., Design pattern recovery in object-oriented software. In: Tilley, S., Visaggio, G. (Eds.), Proceedings of the Sixth International Workshop on Program Comprehension, IEEE Computer Society Press. pp. 153-160.

Digital Library

[8]

Guéhéneuc, Y.-G., Sahraoui, H. and Zaidi, Farouk, Fingerprinting design patterns. In: Stroulia, E., de Lucia, A. (Eds.), Proceedings of the 11th Working Conference on Reverse Engineering, IEEE Computer Society Press. pp. 172-181.

Digital Library

[9]

Nikolaos Tsantalis, G.S., Chatzigeorgiou, Alexander and Halkidis, S.T., Design pattern detection using similarity scoring. Transactions on Software Engineering. v32. 896-909.

Digital Library

[10]

Gusfield, D., Algorithms on Strings, Trees and Sequences. 1997. Cambridge University Press, Cambridge, UK.

Digital Library

[11]

Levenshtein, V.I., Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics - Doklady. v10 i8. 707-710.

[12]

Smith, T. and Waterman, M., Identification of common molecular subsequences. Journal of Molecular Biology. v147. 195-197.

[13]

Needlman, S. and Wunsch, C., A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology. v48. 443-453.

[14]

Ukkonen, E., Finding approximate patterns in strings. Journal of Algorithms. v6. 132-137.

[15]

J. Holub, Simulation of NFA in approximate string and sequence matching, in: Proceedings of the Prague Stringology Club Workshop '97, 1997, pp. 39-46.

[16]

Bergeron, A. and Hamel, S., Vector algorithms for approximate string matching. International Journal of Foundation of Computer Science. v13 i1. 53-66.

[17]

Myers, G., A fast bit-vector algorithm for approximate string matching based on dynamic programming. Journal of the ACM. v46 i3. 395-415.

Digital Library

[18]

Baeza-Yates, R.A. and Gonnet, G.H., A new approach to text searching. Communications of the ACM. v35 i10. 74-82.

Digital Library

[19]

Holub, J. and Melichar, B., Implementation of nondeterministic finite automata for approximate pattern matching. In: Champarnaud, J.-M., Maurel, D., Ziadi, D. (Eds.), Proceedings of the Third International Workshop on Implementing Automata, Springer-Verlag. pp. 92-99.

Digital Library

[20]

Beyer, D., Noack, A. and Lewerentz, C., Simple and efficient relational querying of software structures. In: Stroulia, E., van Deursen, A. (Eds.), Proceedings of the 10th Working Conference on Reverse Engineering, IEEE Computer Society Press. pp. 216-225.

Digital Library

[21]

Kaczor, Olivier, Guéhéneuc, Y.-G. and Hamel, S., Efficient identification of design patterns with bit-vector algorithm. In: di Lucca, G.A., Gold, N. (Eds.), Proceedings of the 10th Conference on Software Maintenance and Reengineering, IEEE Computer Society Press. pp. 173-182.

Digital Library

[22]

Krämer, C. and Prechelt, L., Design recovery by automated search for structural design patterns in object-oriented software. In: Wills, L.M., Baxter, I. (Eds.), Proceedings of the Third Working Conference on Reverse Engineering, IEEE Computer Society Press. pp. 208-215.

Digital Library

[23]

Ciupke, O., Automatic detection of design problems in object-oriented reengineering. In: Firesmith, D. (Ed.), Proceeding of 30th Conference on Technology of Object-Oriented Languages and Systems, IEEE Computer Society Press. pp. 18-32.

Digital Library

[24]

Keller, R.K., Schauer, R., Robitaille, S. and Pagé, P., Pattern-based reverse-engineering of design components. In: Garlan, D., Kramer, J. (Eds.), Proceedings of the 21st International Conference on Software Engineering, ACM Press. pp. 226-235.

Digital Library

[25]

Jahnke, J.H., Schäfer, W. and Zündorf, A., Generic fuzzy reasoning nets as a basis for reverse engineering relational database applications. In: Jazayeri, M. (Ed.), Proceedings of the Sixth European Software Engineering Conference, ACM Press. pp. 193-210.

Digital Library

[26]

Guéhéneuc, Y.-G. and Jussien, N., Using explanations for design-patterns identification. In: Bessière, C. (Ed.), Proceedings of the 1st IJCAI Workshop on Modeling and Solving Problems with Constraints, AAAI Press. pp. 57-64.

[27]

Eppstein, D., Subgraph isomorphism in planar graphs and related problems. In: Clarkson, K. (Ed.), Proceedings of the Sixth Annual Symposium on Discrete Algorithms, ACM Press. pp. 632-640.

Digital Library

[28]

N. Jussien, e-Constraints: Explanation-based constraint programming, in: B. O'Sullivan, E. Freuder (Eds.), First CP workshop on User-Interaction in Constraint Satisfaction, 2001. <http://www.emn.fr/jussien/publications/jussien-WCP01.pdf>.

[29]

Guéhéneuc, Y.-G. and Antoniol, G., DeMIMA: A multi-layered framework for design pattern identification. Transactions on Software Engineering. v34 i5. 667-684.

Digital Library

[30]

Kampffmeyer, H. and Zschaler, S., Finding the pattern you need: The design pattern intent ontology. In: Engels, G., Opdyke, B., Schmidt, D.C., Weil, F. (Eds.), Proceedings of the 10th International Conference on Model Driven Engineering Languages and Systems, Springer. pp. 211-225.

Digital Library

[31]

Guéhéneuc, Y.-G. and Albin-Amiot, H., Recovering binary class relationships: putting icing on the UML cake. In: Schmidt, D.C. (Ed.), Proceedings of the 19th Conference on Object-Oriented Programming, Systems, Languages, and Applications, ACM Press. pp. 301-314.

Digital Library

[32]

Mens, K., Wuyts, R. and D'Hondt, T., Declaratively codifying software architectures using virtualsoftware classifications. In: Firesmith, D. (Ed.), Proceedings of the 30th international conference on Technology of Object-Oriented Languages and Systems, IEEE Computer Society Press. pp. 33-45.

Digital Library

[33]

Dantzig, G.B., Linear Programming and Extensions. 1963. Princeton University Press.

[34]

H.A. Eiselt, M. Gendreau, G. Laporte, Arc routing problems. Part I: The Chinese Postman problem, Tech. Rep. CRT-960, Centre de Recherche sur les Transports (March 1994).

[35]

Gluskov, V.M.G., The abstract theory of automata. Russian Mathematical Surveys. v16. 1-53.

[36]

Thompson, K., Regular expression search algorithm. Communications of the ACM. v11. 419-422.

Digital Library

[37]

Hopcroft, J.E. and Ullman, J.D., Introduction to Automata Theory, Languages, and Computation. 1979. Addison-Wesley.

Digital Library

[38]

Guéhéneuc, Y.-G., Ptidej: Promoting patterns with patterns. In: Fayad, M.E. (Ed.), Proceedings of the First ECOOP workshop on Building a System using Patterns, Springer-Verlag.

[39]

Thimbleby, H.W., The directed chinese postman problem. Journal of Software - Practice and Experience. v33 i11. 1081-1096.

[40]

K. Scheglov, J.-M.P. Shackelford, Eclipse profiler (September 2004). <www.eclipsecolorer.sourceforge.net/index_profiler.html>.

[41]

Agerbo, E. and Cornils, A., How to preserve the benefits of design patterns. In: Chambers, C. (Ed.), Proceedings of the 13th Conference on Object-Oriented Programming, Systems, Languages, and Applications, ACM Press. pp. 134-143.

Digital Library

[42]

Wendehals, L., Improving design pattern instance recognition by dynamic analysis. In: Cook, J.E., Ernst, M.D. (Eds.), Proceedings of the First ICSE Workshop on Dynamic Analysis, IEEE Computer Society Press.

[43]

Bieman, J., Straw, G., Wang, H., Munger, P.W. and Alexander, R.T., Design patterns and change proneness: an examination of five evolving systems. In: Berry, M., Harrison, W. (Eds.), Proceedings of the Ninth International Software Metrics Symposium, IEEE Computer Society Press. pp. 40-49.

Digital Library

[44]

Brown, W.J., Malveau, R.C., Brown, W.H., McCormick, H.W., Hays III, W. and Mowbray, T.J., Anti Patterns: Refactoring Software, Architectures, and Projects in Crisis. 1998. first ed. John Wiley and Sons.

Digital Library

Cited By

Shahbazi ZRasoolzadegan APurfallah ZJafari Horestani S(2022)A new method for detecting various variants of GoF design patterns using conceptual signaturesSoftware Quality Journal10.1007/s11219-021-09576-930:3(651-686)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1007/s11219-021-09576-9
Mokaddem CSahraoui HSyriani E(2022)A generic approach to detect design patterns in model transformations using a string-matching algorithmSoftware and Systems Modeling (SoSyM)10.1007/s10270-021-00936-421:3(1241-1269)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1007/s10270-021-00936-4
Yarahmadi HHasheminejad S(2020)Design pattern detection approaches: a systematic review of the literatureArtificial Intelligence Review10.1007/s10462-020-09834-553:8(5789-5846)Online publication date: 1-Dec-2020
https://dl.acm.org/doi/10.1007/s10462-020-09834-5
Show More Cited By

Recommendations

Investigating design anti-pattern and design pattern mutations and their change- and fault-proneness
Abstract
During software evolution, inexperienced developers may introduce design anti-patterns when they modify their software systems to fix bugs or to add new functionalities based on changes in requirements. Developers may also use design patterns to ...
Improving design-pattern identification: a new approach and an exploratory study

The identification of occurrences of design patterns in programs can help maintainers to understand the program design and implementation. It can also help them to make informed changes. Current identification approaches are limited to complete ...
Design pattern alternatives: what to do when a GoF pattern fails
PCI '13: Proceedings of the 17th Panhellenic Conference on Informatics

Design patterns have been introduced in the field of software engineering in the middle of 90s as common solutions to common design problems. Until now, the effect of design patterns on software quality attributes has been studied by many researchers. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information and Software Technology

Information and Software Technology Volume 52, Issue 2

February, 2010

111 pages

ISSN:0950-5849

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2009.

Publisher

Butterworth-Heinemann

United States

Publication History

Published: 01 February 2010

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Shahbazi ZRasoolzadegan APurfallah ZJafari Horestani S(2022)A new method for detecting various variants of GoF design patterns using conceptual signaturesSoftware Quality Journal10.1007/s11219-021-09576-930:3(651-686)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1007/s11219-021-09576-9
Mokaddem CSahraoui HSyriani E(2022)A generic approach to detect design patterns in model transformations using a string-matching algorithmSoftware and Systems Modeling (SoSyM)10.1007/s10270-021-00936-421:3(1241-1269)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1007/s10270-021-00936-4
Yarahmadi HHasheminejad S(2020)Design pattern detection approaches: a systematic review of the literatureArtificial Intelligence Review10.1007/s10462-020-09834-553:8(5789-5846)Online publication date: 1-Dec-2020
https://dl.acm.org/doi/10.1007/s10462-020-09834-5
Dwivedi ATirkey ARath S(2019)Applying learning-based methods for recognizing design patternsInnovations in Systems and Software Engineering10.1007/s11334-019-00329-315:2(87-100)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s11334-019-00329-3
Dwivedi ATirkey ARath S(2018)Software design pattern mining using classification-based techniquesFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-017-6424-y12:5(908-922)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1007/s11704-017-6424-y
Chihada AJalili SHasheminejad SZangooei M(2015)Source code and design conformance, design pattern detection from source code by classification approachApplied Soft Computing10.1016/j.asoc.2014.10.02726:C(357-367)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1016/j.asoc.2014.10.027
Arcelli Fontana FMaggioni SRaibulet C(2011)Understanding the relevance of micro-structures for design patterns detectionJournal of Systems and Software10.1016/j.jss.2011.07.00684:12(2334-2347)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.1016/j.jss.2011.07.006

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents