Delete Redundant Blanks
A Discussion using APL

Back to Topics in APL

Contents

• Introduction
• Discussion
• Examples
• Performance
• Concluding Remarks
• Acknowledgements and References

Introduction

In this talk I will discuss some functions for "deleting redundant blanks". I will use "standard" (ISO) APL and "extended" APL. This is a useful exercise to show different algorithms for a particular problem, how the same algorithm is expressed in different versions of APL, and performance differences between algorithms.

First, a definition: "deleting redundant blanks" typically refers to a function ...

r„db v

... where v is a character vector with an arbitrary number of blanks, and r is the same vector with leading and trailing blanks removed, and multiple internal blanks replaced by a single blank,

For example,

showblank db ' a b c '

a.b.c

(The function "showblank", which replaces a blank with a period, may be used to highlight the positions of the blanks.)

A function for "deleting redundant blanks" is very useful. The requirement for deleting blanks occurs in many applications, such as token processing and text analysis. (An interesting aside - at least one APL interpreter had this algorithm defined as a quad function! And another - the SmartArrays object software has a character method for the vector class to remove redundant blanks. See the [ SmartArrays Documentation Manual ].)

[ Back to top ]

Discussion

The following APL functions (using the specified methods) will be discussed:

An algorithm for removing redundant blanks can be quite simply stated: take each character in turn, and if the character is blank, and its neighbour to the right (i.e. the character with the next highest index) is blank, do not include the character in the result. Most of the algorithms are variations on this theme.

dbloop

• A looping algorithm. A looping algorithm, that is, an algorithm involving explicit indexing, is considered neither elegant nor efficient in APL, but presents a useful starting point for discussion.
• Function below shows how ISO APL represents a looping algorithm. Some recent second-generation APLs such as Dyalog APL and APL2000 provide control structures such as WHILE. (These were not available to me at the time of this talk.)
• Note how we account for the fact that the last element has no neighbour: in line[5] we append a blank to the input, in line [12] the code avoids testing the last character, a blank, and in line [19] we remove the last character. These points must be considered in all algorithms based on comparing a character with its neighbour.

’ r„dbloop v;Œio;b;i;n
[1] © delete blanks using loop
[2] ©.t 1998.6.22.23.2.24
[3] Œio„1
[4] © catenate blank front and back
[5] v„' ',v,' '
[6] b„v=' '
[7] n„(½v)-1
[8] i„0
[9] r„¼0
[10] l10:
[11] i„i+1
[12] …(n<i)/l10end
[13] © if x[i] and x[i+1] are blank, do not keep x[i]
[14] …(b[i]^b[i+1])/l10
[15] r„r,v[i]
[16] …l10
[17] l10end:
[18] © remove blank at front
[19] r„1‡r
’

dbrl

• We use use a vector approach to compare each character with its neighbour "at the same time", at least in an abstract sense. (We imagine this is happening; this is only occurs in practive on a parallel computer.)
• The following function is the common function. To deal with the last character (which has no next highest neighbour), we catenate a character to the beginning, but the analysis of why this works is not obvious, at least to me, and it is often explained with a lot of "hand-waving". (The proof will involve induction and would demonstrate that one blank always remains at the beginning, and all blanks at the end are removed.)

’ r„dbrl v;b
[1] © delete blanks by rotating left
[2] ©.t 1998.6.22.23.2.23
[3] b„v=' '
[4] r„1‡((1,b) 1²1,b)/' ',v
’

dbrlo

• A so-called "optimized" version of the previous function. One might think that this version would be faster because there are fewer "temporary" results, but the improvement, if any, is not significant (see discussion of timings, below).

’ r„dbrlo v;b;bv
[1] © delete blanks by rotating left (optimized)
[2] ©.t 1998.6.24.23.43.35
[3] b„' '=bv„' ',v
[4] r„1‡(b 1²b)/bv
’

dbrlw

• Some people have suggested to use words instead of glyphs for the APL functions, in particular those not expressible in ASCII characters. This is illustrated below. The algorithm perhaps has a more familiar "feeling" for those not conversant with APL notation. It has been suggested both as a training technique and as a technique for communicating algorithms in APL notation on systems without an APL font.
• The technique for executable functions is to define the obvious functions. This is not particularly convenient in most APLs, but it works.

’ r„x Nand y
[1] r„x y
’

’ r„x Rotate y
[1] r„x²y
’

’ r„x Drop y
[1] r„x‡y
’

’ r„dbrlw v;b
[1] © delete blanks by rotating left (words, not glyphs)
[2] ©.t 1998.6.22.23.2.24
[3] b„v=' '
[4] r„1 Drop((1,b) Nand 1 Rotate 1,b)/' ',v
’

dbshiftleft

• A different statement of the algorithm "rotate left" that is sometimes seen.

’ r„dbshiftleft v;b
[1] © delete blanks by shifting left (equivalent to rotating left)
[2] ©.t 1998.6.22.23.2.24
[3] b„v=' '
[4] r„1‡((1,b) b,1)/' ',v
’

dbrr

• If we state the algorithm in a complementary manner, that is, "if a character and its neighbour to the left (i.e. its neighbour with the next lowest index) ...", then we get a parallel set of functions. Other than dealing with the situation that the first character has no next lowest neighbour, the next four functions are equivalent to the four above.

’ r„dbrr v;b
[1] © delete blanks by rotating right
[2] ©.t 1998.6.22.23.2.24
[3] b„v=' '
[4] r„¯1‡((b,1) ¯1²b,1)/v,' '
’

dbrro

’ r„dbrro v;b;vb
[1] © delete blanks by rotating right (optimized)
[2] ©.t 1998.6.24.23.48.0
[3] b„' '=vb„v,' '
[4] r„¯1‡(b ¯1²b)/vb
’

dbrrw

’ r„dbrrw v;b
[1] © delete blanks by rotating right (words, not glyphs)
[2] ©.t 1998.6.22.23.2.24
[3] b„v=' '
[4] r„¯1 Drop((b,1) Nand ¯1 Rotate b,1)/v,' '
’

dbshiftright

’ r„dbshiftright v;b
[1] © delete blanks by shifting right (equivalent to rotating right)
[2] ©.t 1998.6.22.23.2.24
[3] b„v=' '
[4] r„¯1‡((b,1) 1,b)/v,' '
’

dbscan

• Now, here is a different formulation of the "compare neighbour" algorithm

’ r„dbscan v
[1] © delete blanks using "less than" scan
[2] ©.t 1998.6.22.22.35.13
[3] r„v¬' '
[4] r„(rŸ1²r><\r)/v
’

• [Note. This formulation appealed to the author, Rex Swain, who submitted it for this talk, and provided the following explanation.]
  
  Let's say "-" represents blanks and "_" represents deleted blanks:
  
  0 -This--is-a-test X
  1 0111100110101111 Z „ X ¬ ' '
  2 0100000000000000 < \ Z
  3 0011100110101111 Z > < \ Z
  4 0111001101011110 1 ² Z > < \ Z
  5 0111101111111111 Z Ÿ 1 ² Z > < \ Z
  6 _This_-is-a-test (Z Ÿ 1 ² Z > < \ Z ) / X
  
  Step 3 is the key to handle the edge condition. The result is the same as Z but with the first bit turned off, so that when you do the "Ÿ 1 ²" you don't wind up keeping the leading blank. ... [This algorithm] uses nothing but vanilla APL (no ŒSS), does not require raveling the argument to handle a scalar, and does everything with Boolean primitives (which has a certain elegance, and [there is] less chance of a WS FULL if the argument is huge).
  (courtesy Rex Swain, private communication)

dbss

• In second-generation APLs, there is usually a primitive function for "string searching". In Sharp APL this is represented by "epsilon underbar", which returns a boolean vector specifying the beginning of each occurrence of the given sequence, allowing for overlapping occurrences.
• Using "string search" presents the opportunity for a somewhat more intuitive algorithm: remove the first character of each "double blank" sequence. To simplify cases, we first catenate a blank front and back, and afterwards remove them, a technique which recalls the "trick" used in the looping algorithm.

’ r„dbss v
[1] © delete blanks by string search for double blank
[2] ©.t 1998.6.22.23.2.24
[3] v„' ',v,' '
[4] r„1‡¯1‡(~' 'ºv)/v
’

[ Back to top ]

Examples

• The main purpose of the examples is to demonstrate the equivalence of the key algorithms, and to demonstrate that the functions handle the empty vector correctly. The demonstration function "showblank" is also of interest.

’ r„showblank y
[1] © show the positions of blank in vector <y
[2] ©.t 1998.7.12.0.4.45
[3] r„y
[4] r[(r=' ')/¼½r]„'.'
’

cvector„' a b c '
showblank cvector
.a..b..c...
showblank ''

showblank dbloop cvector
a.b.c
showblank dbloop ''

showblank dbrl cvector
a.b.c
showblank dbrl ''

showblank dbscan cvector
a.b.c
showblank dbscan ''

showblank dbss cvector
a.b.c
showblank dbss ''

[ Back to top ]

Performance

• Timings were done on a PC with a Pentium 233, under Windows 95, using ISI APL (Sharp APL PC version implemented by Iverson Software Inc.)
• "rotate right" algorithm is usually somewhat slower (relatively speaking - the difference is not significant) probably due to the method used in Sharp APL to store boolean data.
• There is a noticeable "penalty" for using words.
• The "scan" algorithm is not noticeably worse with larger arguments because boolean scans are optimized in the Sharp APL interpreter. (The timings to demonstrate this are not shown.)
• "dbss" is easily understood, but twice as slow.
• Clearly "dbloop" is not recommended on the basis of performance.
• In the following "cvector" had 1000 elements. The numbers are in seconds and represent one invocation.
• Exercise for the future: assess performance on another APL interpreter!

0.00274 y„dbrl cvector
0.00274 y„dbshiftleft cvector
0.00275 y„dbrlo cvector
0.00275 y„dbrro cvector
0.00275 y„dbscan cvector
0.00275 y„dbshiftright cvector
0.00329 y„dbrr cvector
0.00384 y„dbrlw cvector
0.00384 y„dbrrw cvector
0.00550 y„dbss cvector
1.64619 y„dbloop cvector

[ Back to top ]

Concluding Remarks

• "dbrl" is a suitable choice. It has good performance and the algorithm is easy to understand.

This concludes the discussion of "deleting redundant blanks", using several algorithms, and several formulations, in various versions of APL. Similarities and differences were noted.

I have always had an interest in the problem of deleting redundant blanks, even though it might be considered an "overly simple" function to analyze in depth. Perhaps because when I first learned APL and saw the array solution, I found it quite mysterious. Since then, it continues to appeal to me for several reasons. there are several subtleties and edge conditions, in spite of its apparent simplicity, it is interesting to note the various approaches for even a simple problem; it can be used to illustrate various aspects of the APL language without the distraction of an otherwise complex algorithm, and it remains a nice example of an "array-oriented" solution.

[ Back to top ]

Acknowledgements and References

Notes from a talk given by Richard Levine to a meeting of the Toronto APL Special Interest Group ... June 23, 1998.
Article written ... 29 July 1998
Revised ... 24 September 2003

Thanks to ... Keith Smillie for his comments on the article; Rex Swain for his contribution of algorithm "dbscan".

[ Back to top ]