Row replacement algorithms for screen editors
- 1 January 1989
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 11 (1) , 33-56
- https://doi.org/10.1145/59287.59290
Abstract
Interactive screen editors repeatedly determine terminal command sequences to update a screen row. Computing an optimal command sequence differs from the traditional sequence comparison problem in that there is a cost for moving the cursor over unedited characters and the cost of an n -character command is not always the cost of n one-character commands. For example, on an ANSI-standard terminal, it takes nine bytes to insert one character, ten to insert two, eleven to insert three, and so on. This paper presents an O ( MN ) dynamic programming algorithm for row replacement where an n -character command costs α n + β for constants α and β. M is the length of the original row and N is the length of its replacement. Also given is an O ( Cost × ( M + N )) “greedy” algorithm for optimal row replacement. Here Cost is the optimal cost (in bytes) of the replacement, so the algorithm is fast when the require d update is small. Though the algorithm is rather complicated, it is fast enough to be useful in practice.Keywords
This publication has 16 references indexed in Scilit:
- An improved algorithm for matching biological sequencesPublished by Elsevier ,2004
- A simple row‐replacement methodSoftware: Practice and Experience, 1988
- The text editor samSoftware: Practice and Experience, 1987
- A differential compiler for computer animationACM SIGGRAPH Computer Graphics, 1986
- A file comparison programSoftware: Practice and Experience, 1985
- Cwsh: The windowing shell of the Maryland Window SystemSoftware: Practice and Experience, 1985
- A language for bitmap manipulationACM Transactions on Graphics, 1982
- Some biological sequence metricsAdvances in Mathematics, 1976
- A linear space algorithm for computing maximal common subsequencesCommunications of the ACM, 1975
- The String-to-String Correction ProblemJournal of the ACM, 1974