Searching for Strings in Strings
Vector 7:2, page 27
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 27
No, this not an introduction to String Theory which I’m told is the latest attempt of Mathematicians to provide the mathematical foundations necessary for Physicists to explain the fundamentals of Nature. Rather just a short article continuing my theme of string handling in APL.
Perhaps the most frequent use of a computer is for word-processing. One of the essential tasks that a word-processor must perform is that of searching for the occurrence of target strings in a text. Facilities are then provided for replacing that string with a preferred string; this can be very useful where a complicated name or phrase occurs often throughout a particular text. Text editors for computing, such as the one I am using now, also provide a ‘search and replace’ facility, so that variable names can be changed through a program.
I was reminded of this topic in a wider context by a letter and newspaper article sent to me by Bill McClean of Dunoon. He sent me an article concerning the work of Andrew Morton and a Computer Science Colleague of mine Mike Farringdon who have recently developed new techniques of examining texts (e.g. novels) to test hypotheses concerning disputed authorship. Specific examples of this are parts of the Bible whose authorship is questionable and the famous case of the Federalist Papers. Their technique depends crucially on being able to search through the text for the occurrences of particular words, or types of words, or phrases, hence the connection with this article.
Let’s start with a simple example.
First I will try to construct ‘an APL solution’ to the problem of string searching (i.e. one without looping). Clearly it is necessary to use = to find the occurrences of each letter of 'CAT' in TEXT. The outer-product ∘.= clearly is what we need.
STRING∘.=TEXT
0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
Now the problem is to look for the diagonal sets of 1’s. One way to do this is by rotation of the second row one place to the left, and the third row 2 places to the left, so that the diagonal lines become columns. This can be done using ⌽ with a left argument. Here are some examples that show you how ⌽ works:
Each number of the left argument of ⌽ tells you how many places to the left the equivalent line is to be rotated. (A negative number indicates rotation to the right.)
This is clearly what we need to align the series of 1’s. We can then test that the aligned columns are all 1’s by using ∧ (‘and’) applied to the columns, i.e. ∧⌿. To achieve the required rotation, we create the vector 0 1 2 (in this case) using the general formula ¯1+⍳⍴STRING (assuming the index origin is 1). Hence,
The position of the 1’s in the resulting vector indicate the required occurrences of 'CAT'.
Having discovered the essential method, and programmed it successfully, now starts the problem of trying to make the method apply in all sensible cases. What happens, for example, if we use the above formula when TEXT←'A'? Can you anticipate the problem? Basically, instead of a Boolean matrix, we obtain a vector, hence ∧⌿ will fail as there are no columns to reduce on. This problem can be easily circumvented by making sure that STRING is a vector, i.e. STRING←,STRING.
A second problem occurs because of the rotation. Suppose TEXT←'THIS CAT IS CALLED ICA'. Then a matching will occur on the penultimate place because the last two letters are CA and the first is T. One easy way to prevent this is by appending to TEXT, a ‘character’ that does not/will not occur in the text, say ⎕AV[1]. Piecing all this together, we get the function SS.
∇ R←STRING SS TEXT
[1] STRING←,STRING ⋄ TEXT←TEXT,⎕AV[1]
[2] R←(∧⌿(¯1+⍳⍴STRING)⌽STRING∘.=TEXT)/⍳⍴TEXT
∇
One drawback of the APL solution, is that for large TEXT and moderate STRING sizes, the ∘.= construct creates a huge array, making this very infeasible. What alternative strategies might be appropriate, still with the aim of achieving efficient APL code?
When thinking about this, it occurred to me that the ‘Sieve of Erastothenes’ method could be adopted to this situation. This method is used to derive the prime numbers in the set of the first N natural numbers, proceeding by deleting all numbers divisible by 2, then all divisible by 3 and so on. For example,
W←⍳50
⎕←X←(0≠2|W)/W
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41
43 45 47 49
⎕←Y←(0≠3|X)/X
1 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49
⎕←Z←(0≠5|Y)/Y
1 7 11 13 17 19 23 29 31 37 41 43 47 49
⎕←(0≠7|Z)/Z
1 7 11 13 17 19 23 29 31 37 41 43 47
In the context of searching for strings, suppose we searched for all the occurrences of the first letter of STRING; then search amongst those positions+1 for the occurrence of the second letter of STRING. At each stage the size of the APL problem is considerably reduced, and looping only has to occur for (⍴STRING) times. The program SS2 executes the new algorithm. It is convenient to append to TEXT some dummy characters so that simple indexing is easy. Once again we coerce STRING to be a vector.
∇ R←STRING SS2 TEXT;L;N;C
[1] STRING←,STRING ⋄ L←⍴STRING ⋄ C←1
[2] TEXT←TEXT,(L-1)⍴⎕AV[3]
[3] R←⍳⍴TEXT
[4] LP:R←(STRING[C]=TEXT[R+C-1])/R
[5] →(L≥C←C+1)/LP
∇
Now let’s test the two algorithms on this article which at present is 5479 characters long.
'STRING' SS2 ARTICLE
1477 1788 2786 2815 2823 3414 3439 3447 3835 3856 3864 3907
3915 4014 4912 5001 5112 5271 5313 5341 5349 5361 5425
… tells me that the first occurrence of (uppercase) STRING is in the 1477th position etcetera. The response is more or less immediate, whereas for SS, it takes about 4 seconds to produce the equivalent result (running on an IBM PS/2 Model 70).
Of course, the next step is to be able to replace STRING with an alternative string. This doesn’t appear to be straightforward, unless the length of the alternative string is the same as the original. If the new string is greater in length, then the original TEXT vector has to be padded out to make room for the extra characters at appropriate places. This can be done using ‘replicate’ (e.g. 1 2 1 2/'ABCD' yields 'ABBCDD'). Then, substitution can take place. If, on the other hand the new string is smaller in length, then appropriate parts of the original text must be dropped e.g. 1 0 1 0/'ABCD' gives 'AC'. Any offers for an APL function REPLACEIN with the syntax as indicated by the example below?
An Even Sneakier String Search!¶
Alan should have known better than to leave me a blank page to fill! A couple of timings on the entire Education Vector (22130←→⍴QQQ) showed that Alan’s SS2 is indeed rather fast, but can be beaten by the APL*PLUS ‘find’ primitive ⍷ …
Clearly, this is not good enough for the true APL hacker! The function below takes the additional step of arranging the substring so that the least frequent letters are matched first! This cuts down the size of the potential targets much faster, and will hit the ‘STRING’ test in 1.46 sec. I believe the APL*PLUS ⎕SS system function is simply an assembler coding of this algorithm; one wonders why they bothered!
∇ POS←SUB ∆SS TARGET;GR;LEN;CT
[1] ⍝ Returns index of all locations in TARGET where
[2] ⍝ substring SUB is found.
[3] ⍝
[4] ⍝ From: APL Design Handbook (Adrian Smith) Wiley
[5] ⍝ Algorithm adapted from Bob Smith's
[6] ⍝ "Collected Whizzbangs" circa 1978 by STSC.
[7] ⍝
[8] TARGET←,TARGET ⋄ SUB←,SUB
[9] →(2 1 0 ≤⍴SUB)/Ok,Single,Empty
[10] Empty:POS←⍳⍴TARGET ⋄ →0
[11] Single:POS←(TARGET=SUB)/⍳⍴TARGET ⋄ →0
[12] Ok:LEN←0⌈(⍴TARGET)-(⍴SUB)-1
[13] SUB←SUB[GR←⍒' ETARINOS'⍳SUB]
[14] GR←GR-1
[15] POS←(LEN↑GR[1]↓TARGET=1↑SUB)/⍳LEN
[16] →(⍴POS)↓0 ⋄ GR←1↓GR ⋄ SUB←1↓SUB ⋄ CT←1
[17] Lp:→(⍴POS←(TARGET[POS+GR[CT]]=SUB[CT])/POS)↓0
[18] →((⍴SUB)≥CT←CT+1)↑Lp
∇