The string-to-string correction problem with block moves

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The string-to-string correction problem with block moves

Full text

Pdf (772 KB)

Source

ACM Transactions on Computer Systems (TOCS) archive
Volume 2 , Issue 4 (November 1984) table of contents

Pages: 309 - 321

Year of Publication: 1984

ISSN:0734-2071

Author

Walter F. Tichy

Department of Computer Science, Purdue University, West Lafayette, IN

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 199, Citation Count: 27

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/357401.357404 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	James Gosling, A redisplay algorithm, Proceedings of the ACM SIGPLAN SIGOA symposium on Text manipulation, p.123-129, June 08-10, 1981, Portland, Oregon, United States
	2	Paul Heckel, A technique for isolating differences between files, Communications of the ACM, v.21 n.4, p.264-268, April 1978 [doi>10.1145/359460.359467]
	3	D. S. Hirschberg, A linear space algorithm for computing maximal common subsequences, Communications of the ACM, v.18 n.6, p.341-343, June 1975 [doi>10.1145/360825.360861]
	4	Daniel S. Hirschberg, Algorithms for the Longest Common Subsequence Problem, Journal of the ACM (JACM), v.24 n.4, p.664-675, Oct. 1977 [doi>10.1145/322033.322044]
	5	HUNT, J. W., AND MCILROY, M.D. An algorithm for differential file comparison. Computing Science Tech. Rep. 41. AT&T Bell Laboratories, Murray Hill, N.J., June 1976.
	6	James W. Hunt , Thomas G. Szymanski, A fast algorithm for computing longest common subsequences, Communications of the ACM, v.20 n.5, p.350-353, May 1977 [doi>10.1145/359581.359603]
	7	David B. Leblang , Robert P. Chase, Jr., Computer-Aided Software Engineering in a distributed workstation environment, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.104-112, April 1984
	8	Robert A. Wagner , Roy Lowrance, An Extension of the String-to-String Correction Problem, Journal of the ACM (JACM), v.22 n.2, p.177-183, April 1975 [doi>10.1145/321879.321880]
	9	MASEK, W. J., AND PATERSON, M.S. How to compute string-edit distances quickly. In Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison, D. Sankoff and J. B. Kruskal, Eds. Addison-Wesley, Reading, Mass., 1983, pp. 337-349.
	10	Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
	11	NAKATSU, N., KAMBAYASHI, Y., AND YAJIMA, S. A longest common subsequence algorithm for similar text strings. Act. Inf. 18 (1982), 171-179.
	12	Bruce Walker , Gerald Popek , Robert English , Charles Kline , Greg Thiel, The LOCUS distributed operating system, ACM SIGOPS Operating Systems Review, v.17 n.5, p.49-70, October 1983
	13	ROCHKIND, M. J. The source code control system. IEEE Trans. Softw. Eng. SE-1, 4 {Dec. 1975), 364-370.
	14	SANKOFF, D. Matching sequences under deletion/insertion constraints. Proc. Nat. Acad. Sci. (USA) 69, 1 (Jan. 1972), 4-6.
	15	SANKOFF, D., AND KRUSKAL, J.B. Time Warps, String Edits, and Macromolecules: The Theory of Sequence Comparison. Addison-Wesley, Reading, Mass., 1983.
	16	Walter F. Tichy, Design, implementation, and evaluation of a Revision Control System, Proceedings of the 6th international conference on Software engineering, p.58-67, September 13-16, 1982, Tokyo, Japan
	17	Robert A. Wagner , Michael J. Fischer, The String-to-String Correction Problem, Journal of the ACM (JACM), v.21 n.1, p.168-173, Jan. 1974 [doi>10.1145/321796.321811]

CITED BY 27

	Christoph Reichenberger, Delta storage for arbitrary non-text files, Proceedings of the 3rd international workshop on Software configuration management, p.144-152, June 12-14, 1991, Trondheim, Norway
	Walter F. Tichy, Smart recompilation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.3, p.273-291, July 1986
	Miklos Ajtai , Randal Burns , Ronald Fagin , Darrell D. E. Long , Larry Stockmeyer, Compactly encoding unstructured inputs with differential compression, Journal of the ACM (JACM), v.49 n.3, p.318-367, May 2002
	Randal C. Burns , Darrell D. E. Long, In-place reconstruction of delta compressed files, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.267-275, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Gonzalo Navarro, A guided tour to approximate string matching, ACM Computing Surveys (CSUR), v.33 n.1, p.31-88, March 2001
	Athicha Muthitacharoen , Benjie Chen , David Mazières, A low-bandwidth network file system, ACM SIGOPS Operating Systems Review, v.35 n.5, Dec. 2001
	Lin Yu , Daniel J. Rosenkrantz, A linear-time scheme for version reconstruction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.775-797, May 1994
	James J. Hunt , Kiem-Phong Vo , Walter F. Tichy, Delta algorithms: an empirical analysis, ACM Transactions on Software Engineering and Methodology (TOSEM), v.7 n.2, p.192-214, April 1998
	J. Plaice , W. W. Wadge, A New Approach to Version Control, IEEE Transactions on Software Engineering, v.19 n.3, p.268-276, March 1993
	S. Muthukrishnan , Süleyman Cenk Sahinalp, Approximate nearest neighbors and sequence comparison with block operations, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.416-424, May 21-23, 2000, Portland, Oregon, United States
	Dirk Ohst , Michael Welle , Udo Kelter, Differences between versions of UML diagrams, ACM SIGSOFT Software Engineering Notes, v.28 n.5, September 2003
	Susan Horwitz, Identifying the semantic and textual differences between two versions of a program, ACM SIGPLAN Notices, v.25 n.6, p.234-245, Jun. 1990
	S. Muthukrishnan , S. Cenk Sahinalp, An efficient algorithm for sequence comparison with block reversals, Theoretical Computer Science, v.321 n.1, p.95-101, June 16, 2004
	Raihan Al-Ekram , Archana Adma , Olga Baysal, diffX: an algorithm to detect changes in multi-version XML documents, Proceedings of the 2005 conference of the Centre for Advanced Studies on Collaborative research, p.1-11, October 17-20, 2005, Toranto, Ontario, Canada
	Marek Chrobak , Petr Kolman , Jiří Sgall, The greedy algorithm for the minimum common string partition problem, ACM Transactions on Algorithms (TALG), v.1 n.2, p.350-366, October 2005
	Haim Kaplan , Nira Shafrir, The greedy algorithm for edit distance with moves, Information Processing Letters, v.97 n.1, p.23-27, 16 January 2006
	R. C. Agarwal , K. Gupta , S. Jain , S. Amalapurapu, An approximation to the greedy algorithm for differential compression, IBM Journal of Research and Development, v.50 n.1, p.149-166, January 2006
	Miryung Kim , David Notkin, Program element matching for multi-version program analyses, Proceedings of the 2006 international workshop on Mining software repositories, May 22-23, 2006, Shanghai, China
	John Hershberger, Improved output-sensitive snap rounding, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Tancred Lindholm , Jaakko Kangasharju , Sasu Tarkoma, Fast and simple XML tree differencing by sequence alignment, Proceedings of the 2006 ACM symposium on Document engineering, October 10-13, 2006, Amsterdam, The Netherlands
	Deepak R. Bobbarjung , Suresh Jagannathan , Cezary Dubnicki, Improving duplicate elimination in storage systems, ACM Transactions on Storage (TOS), v.2 n.4, p.424-448, November 2006
	Dana Shapira , James A. Storer, Edit distance with move operations, Journal of Discrete Algorithms, v.5 n.2, p.380-392, June, 2007
	David Rasch , Randal Burns, In-place rsync: file synchronization for mobile and wireless devices, Proceedings of the USENIX Annual Technical Conference 2003 on USENIX Annual Technical Conference, p.15-15, June 09-14, 2003, San Antonio, Texas
	David G. Korn , Kiem-Phong Vo, Engineering a Differencing and Compression Data Format, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.219-228, June 10-15, 2002
	B. Thomas Adler , Luca de Alfaro, A content-driven reputation system for the wikipedia, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada
	Gerardo Canfora , Luigi Cerulo , Massimiliano Di Penta, Identifying Changed Source Code Lines from Version Repositories, Proceedings of the Fourth International Workshop on Mining Software Repositories, p.14, May 20-26, 2007
	Krishnendu Chatterjee , Luca de Alfaro , Ian Pye, Robust content-driven reputation, Proceedings of the 1st ACM workshop on Workshop on AISec, October 27-27, 2008, Alexandria, Virginia, USA