{"id":14575,"date":"2022-05-09T22:37:45","date_gmt":"2022-05-10T02:37:45","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=14575"},"modified":"2022-05-09T22:37:45","modified_gmt":"2022-05-10T02:37:45","slug":"tr-04-a-practical-longest-common-subsequence-algorithm-for-text-collation","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1982-2\/tr-04-a-practical-longest-common-subsequence-algorithm-for-text-collation\/","title":{"rendered":"TR-04: A Practical Longest Common Subsequence Algorithm for Text Collation"},"content":{"rendered":"<p>Carleton University<br \/>\n<a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1982\/\">Technical Report<\/a> <strong>TR-04<\/strong><br \/>\nJune 1982<\/p>\n<h2 class=\"tr_t1\">A Practical Longest Common Subsequence Algorithm for Text Collation<\/h2>\n<p>Jim des Rivieres<\/p>\n<h3>Abstract<\/h3>\n<p>Previously published algorithms for finding the longest common subsequence in less than quadratic space are not well suited to the task of finding the differences between long streams of words (text collation). This paper presents a practical incremental algorithm with typical space requirements small enough to allow the handling of large insertions and deletions.<\/p>\n<h3>Download<\/h3>\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/TR-4.pdf\">TR-04.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton University Technical Report TR-04 June 1982 A Practical Longest Common Subsequence Algorithm for Text Collation Jim des Rivieres Abstract Previously published algorithms for finding the longest common subsequence in less than quadratic space are not well suited to the task of finding the differences between long streams of words (text collation). This paper presents [&hellip;]<\/p>\n","protected":false},"author":49,"featured_media":0,"parent":11682,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_relevanssi_hide_post":"","_relevanssi_hide_content":"","_relevanssi_pin_for_all":"","_relevanssi_pin_keywords":"","_relevanssi_unpin_keywords":"","_relevanssi_related_keywords":"","_relevanssi_related_include_ids":"","_relevanssi_related_exclude_ids":"","_relevanssi_related_no_append":"","_relevanssi_related_not_related":"","_relevanssi_related_posts":"","_relevanssi_noindex_reason":"","_mi_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":"","_links_to":"","_links_to_target":""},"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v21.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>TR-04: A Practical Longest Common Subsequence Algorithm for Text Collation - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-04 June 1982 A Practical Longest Common Subsequence Algorithm for Text Collation Jim des Rivieres Abstract\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1982-2\/tr-04-a-practical-longest-common-subsequence-algorithm-for-text-collation\/\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1982-2\/tr-04-a-practical-longest-common-subsequence-algorithm-for-text-collation\/\",\"url\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1982-2\/tr-04-a-practical-longest-common-subsequence-algorithm-for-text-collation\/\",\"name\":\"TR-04: A Practical Longest Common Subsequence Algorithm for Text Collation - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2022-05-10T02:37:45+00:00\",\"dateModified\":\"2022-05-10T02:37:45+00:00\",\"description\":\"Carleton University Technical Report TR-04 June 1982 A Practical Longest Common Subsequence Algorithm for Text Collation Jim des Rivieres Abstract\",\"breadcrumb\":{\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1982-2\/tr-04-a-practical-longest-common-subsequence-algorithm-for-text-collation\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1982-2\/tr-04-a-practical-longest-common-subsequence-algorithm-for-text-collation\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1982-2\/tr-04-a-practical-longest-common-subsequence-algorithm-for-text-collation\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/carleton.ca\/scs\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Research\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"SCS Technical Reports\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/\"},{\"@type\":\"ListItem\",\"position\":4,\"name\":\"Technical Reports 1982\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1982-2\/\"},{\"@type\":\"ListItem\",\"position\":5,\"name\":\"TR-04: A Practical Longest Common Subsequence Algorithm for Text Collation\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/carleton.ca\/scs\/#website\",\"url\":\"https:\/\/carleton.ca\/scs\/\",\"name\":\"School of Computer Science\",\"description\":\"Carleton University\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/carleton.ca\/scs\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"TR-04: A Practical Longest Common Subsequence Algorithm for Text Collation - School of Computer Science","description":"Carleton University Technical Report TR-04 June 1982 A Practical Longest Common Subsequence Algorithm for Text Collation Jim des Rivieres Abstract","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1982-2\/tr-04-a-practical-longest-common-subsequence-algorithm-for-text-collation\/","schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1982-2\/tr-04-a-practical-longest-common-subsequence-algorithm-for-text-collation\/","url":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1982-2\/tr-04-a-practical-longest-common-subsequence-algorithm-for-text-collation\/","name":"TR-04: A Practical Longest Common Subsequence Algorithm for Text Collation - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2022-05-10T02:37:45+00:00","dateModified":"2022-05-10T02:37:45+00:00","description":"Carleton University Technical Report TR-04 June 1982 A Practical Longest Common Subsequence Algorithm for Text Collation Jim des Rivieres Abstract","breadcrumb":{"@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1982-2\/tr-04-a-practical-longest-common-subsequence-algorithm-for-text-collation\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1982-2\/tr-04-a-practical-longest-common-subsequence-algorithm-for-text-collation\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1982-2\/tr-04-a-practical-longest-common-subsequence-algorithm-for-text-collation\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/carleton.ca\/scs\/"},{"@type":"ListItem","position":2,"name":"Research","item":"https:\/\/carleton.ca\/scs\/research\/"},{"@type":"ListItem","position":3,"name":"SCS Technical Reports","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/"},{"@type":"ListItem","position":4,"name":"Technical Reports 1982","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1982-2\/"},{"@type":"ListItem","position":5,"name":"TR-04: A Practical Longest Common Subsequence Algorithm for Text Collation"}]},{"@type":"WebSite","@id":"https:\/\/carleton.ca\/scs\/#website","url":"https:\/\/carleton.ca\/scs\/","name":"School of Computer Science","description":"Carleton University","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/carleton.ca\/scs\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-US"}]}},"acf":{"banner_opacity":"dark","banner_image_type":"upload","banner_button":"no","banner_uploaded_image":{"ID":8983,"id":8983,"title":"Coding screen","filename":"laptop-code-1600.jpg","filesize":154356,"url":"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/laptop-code-1600.jpg","link":"https:\/\/carleton.ca\/scs\/tech-support\/laptop-code-1600\/","alt":"Coding screen","author":"7","description":"Coding screen","caption":"","name":"laptop-code-1600","status":"inherit","uploaded_to":6535,"date":"2021-02-10 15:47:55","modified":"2021-11-25 20:57:39","menu_order":0,"mime_type":"image\/jpeg","type":"image","subtype":"jpeg","icon":"https:\/\/carleton.ca\/scs\/wp\/wp-includes\/images\/media\/default.png","width":1600,"height":700,"sizes":{"thumbnail":"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/laptop-code-1600-160x70.jpg","thumbnail-width":160,"thumbnail-height":70,"medium":"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/laptop-code-1600-240x105.jpg","medium-width":240,"medium-height":105,"medium_large":"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/laptop-code-1600-768x336.jpg","medium_large-width":768,"medium_large-height":336,"large":"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/laptop-code-1600-400x175.jpg","large-width":400,"large-height":175,"gallery-thumb":"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/laptop-code-1600-300x230.jpg","gallery-thumb-width":300,"gallery-thumb-height":230,"1536x1536":"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/laptop-code-1600-1536x672.jpg","1536x1536-width":1536,"1536x1536-height":672,"2048x2048":"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/laptop-code-1600.jpg","2048x2048-width":1600,"2048x2048-height":700,"banner":"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/laptop-code-1600.jpg","banner-width":1600,"banner-height":700,"people":"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/laptop-code-1600-200x200.jpg","people-width":200,"people-height":200,"post-thumb":"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/laptop-code-1600-300x230.jpg","post-thumb-width":300,"post-thumb-height":230,"rotator-image":"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/laptop-code-1600-800x600.jpg","rotator-image-width":800,"rotator-image-height":600,"video-thumb":"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/laptop-code-1600-360x158.jpg","video-thumb-width":360,"video-thumb-height":158}}},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14575"}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/49"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=14575"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14575\/revisions"}],"predecessor-version":[{"id":14576,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14575\/revisions\/14576"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11682"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=14575"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}