cxpos is an implementation of this paper:
=========================================
Copyright 2004, D.Sofyan & Adrian Hafizh,
private property of PT SOFTINDO, Jakarta.
All rights reserved.
=========================================
Title: An analysis of Bound-Range in indexed-character-based string matching scan
Version: 1.0.0.1-beta
Authors: D.Sofyan & Adrian Hafizh
The most important thing when doing a substring scan is to know
WHEN the character sequences in the substring is no longer
matched, as early as possible, and if possible, to detect WHAT
sequences does not worth to scan and could be skipped, as much as
possible, to minimalize useless, discarded matching tries.
Based on this postulate, we would analyze the new algorithm of
character based scanning to quickly locate a position of pattern
or smaller substring against the larger one, much more efficiently
compared to that of conventional scan.
On this paper we propose an improved, sub-optimalization of
character-based pattern match technique.
.
..
...
First, we have to build an INDEX table of substring to be matched
against. This table should be initialized in such a way that the
ordinal position of particular character in the INDEX table
contains the index/position of that character in the substring,
or in other words, every characters in the substring, have their
index/position in the substring recorded in their respective
ordinal position in the INDEX table. For any other characters that
are not in the substrings, their ordinal positions in the INDEX
table should be filled with a value greater than the last position
of the substring (an OUT-RANGE index-value). From now on, for
simplicity shake, the ordinal position of particular character's
value in the INDEX table will be called as only the INDEX-VALUE.
Conveniently, we use 0-based position for the index/position.
When a particular character appears more than once in the
substring, then the ordinal position of that character in the
INDEX table must contain the highest value of the index/position
of that particular character in the substring (the last one). On
further descriptions we will call this kind of characters as TWINS.
After filling the INDEX table with the proper values, we have to know
the index-values range by getting the LOWEST and the HIGHEST
index-value of the characters sequence in the substring (also in
the INDEX table); the HIGHEST index-value is already indicated by
the last position of the substring, whereas the LOWEST index-value
could be gotten by scanning either the substring or the INDEX table,
From now on, they would simply be called them as the LOWEST and the
HIGHEST respectively.
It is also worth to know if there are not any duplicated characters
(TWINS) in the substring. The search algorithm will be much stright
and simpler, for example, any out-of-range character catched during
the skim will result on to rejection of the whole skimmed-substring,
because the LOWEST would have never been reached anyway upto until
the last fetch.
// If they are not any duplicated characters in the substring (TWINS):
// Once the INDEX table has been built, we no longer need the
// substring anymore, all of the informations we need are already
// in the INDEX table.
In this document, we analyze the comprehensive state in general,
which also sorrounding/including this unique character sequences,
should the performance is considered to be much critical, we might
have to do a different branch for this case.
The other advantages of using the INDEX table is that no-case
comparison will no longer need different or additional instructions,
as long as the comparison is based on their index-values, not between
the characters by themselves, because neither lower or uppercase is
treated specially, only the index/position of particular character
in the substring that makes different. .
On further searching, we should avoid doing comparison of substring
with string to be matched against by their character per characters
per-se, instead, we mainly using this INDEX table to do the
comparison. The characters which contained/existed in the substring
will have its index-value equal with its position in the substring,
any character whose index-values higher than the length of substring
(OUT-RANGE) does not need any further processing, or in the other
means, only the characters in the substring will be taken into account.
Second, when doing a skim, we do it in the reversed order, to
take advantages of the length of the substring to be matched
against to be accounted in. This reversed way will also lead to
non-measurable advantages which gain effectiveness when scanning
a recognizable pattern (a word) against sequences of another
recognizable pattern (such a document text), because one word has
a relatively low possibility to match another pattern consisted
by to half words (in the same length), thus the non-match will
detected earlier.
On this algorithm, this reversed way is also aimed at the computation
on how much characters sequences could be skipped at comparison's fail
when skimming.
Finally, mainly by using the index-values we will seek the string to
be matched against, try to locate the possible matched substring, and
if possible, skip any sequence of characters that will never match.
The search begin with comparing the fetched character from the
string with the first character of the substring (we called further
the position of the string at this point as ORIGIN), only if they
are equal then we begin the substring skim cycle, otherwise we
simply skip to the next character.
// If they are not any duplicated characters (TWINS) in the substring:
// The index-value of 0 has the special position here, because it is
// should be used as initial substring skim cycle. The index-value of 0
// means that the character is the first character in the substring,
// which we will seek it first on the string, if the character fetched
// in the string has the index-value other than 0, we simply skip it
// to fetch the next character, only if its index-value is 0 then we
// begin the substring skim cycle.
The substring SKIM CYCLE is the process of comparing the CHUNK of
the string (portion of the string with the length of the substring,
--will be called as only LENGTH on further descriptions) against
the substring, on a indexed-character-based comparison. When the
comparison fails, whe should check WHEN is that happens (denoted
by the position COUNTER) and WHAT is the INDEX-VALUE (of the
character fetched from the chunk, at the offset pointed by the
current counter position). Keep the terminologies in mind, for
those will be carried on further descriptions.
On any conditions, the process will keep going on while the
index-value is equal with the counter, until end-of-loop, that is
the counter reaches its lowest value, which also means that the
substring has found. Only when the index-value is different from
the counter then we have to suspend the process, and do several
investigation to determine the exact state.
On any conditions, if the index-value is higher than the HIGHEST
then the cycle will be ended and the original fetch position could
be skipped to that point. This conditions indicates that the
character in question is out of range, the chunk could be safely
cut to the position after this character.
The skimming cycle started from the HIGHEST value to the LOWEST
value (counted-down), this counter should be compared against the
index-value of current fetched character (original fetched position
with the offset of counter). There are no physical accesses to the
substring at this step, the comparisons are merely of index-values
against the counter.
// If they are not any duplicated characters (TWINS) in the substring:
// We never do physical comparison of the characters at all
// We only need a single comparison stage, any index-value
// different from the counter will lead to suspended skim
// If the index-value is lower than the counter we should shift
// forward the original fetch position by (counter - index-value) away
// if the index-value higher than the counter, then we could
// discard the whole string and skip forward the original fetch
// position to the length of the substring
On comparison fails, and the index-value is between the LOWEST and
the HIGHEST, then we have to do the next step, that is manually
comparing the character from chunk with the substring, both at the
same counter position, if they are equal then we continue the
suspended first-step. For the comparison to be carried on further
processing, then is not the characters itself that we had the
comparison against to, but rather indirectly by their index-values.
Note that if both of the characters are equal (by comparing their
index-values), there is an indication of TWINS, notice also that
their values will have to be higher than the counter.
If the comparison fails at this stage, then one way or another,
the skim have to be ended. But beforewise, we might do another
check to determine how much save we could get by skipping useless
further tries.
At this stage, we virtually try to match the character of
substring[?] where ? is the index-value of the chunk[COUNTER].
Any index-values between the LOWEST and COUNTER are considered
to be OUT-RANGE. Note that the values below the LOWEST will never
exist, so what we have to consider are only the COUNTER value, and
(supposed to be) the appearance of the LOWEST, and the values
between them, if any. The convergency of those lower and
upper-bound makes the RANGE-bound in effect as described later.
The RANGE-bound is a virtual range between the LOWEST and the
(counted-down) HIGHEST, consisted by all of acceptable index-
values. At first, it is composed equally with the substring. The
RANGE-bound length is also in correlation with the LENGTH of the
substring (or the chunk), it supposed to be equal with the
counter itself, in fact it is, if there are not any TWINS. Due to
this TWINS problem, the length of RANGE-bound is practically less
than LENGTH, because of the length of several characters is counted
as only 1. What we do know is only the upper-bound of the RANGE-bound,
indicated by the counter (and the expected lower-bound by the LOWEST).
while skimming, the RANGE-bound length might be virtually decreased
towards the lower bound according to the counter, yet it physically
decreases only if the character fetched IS NOT a TWIN. Wen the fetched
character IS a TWIN, the RANGE-bound decrements virtually mapped to
a corresponding TWIN value, this map is always an index-value higher
than the counter NEVER below them, (because of the increasing rules
of the index-values when they're been built), in consequence of that,
the lower-bound, would be the last index-value reached.
The expected to be found: the LOWEST, is the index-value of the
least and last (the first-reversed) particular character class that
expected to be found. She is the lower-bound of the range, also
implies as the assurance of the RANGE-bound length limit, though
we don't know exactly WHERE she is, neither WHAT of her value, we
just expect (or more precisely: assumed) that she might have been
there at one position later, with one particular value. In opposite
to the upper-bound, that is the counter, we do know exactly
where and what the value is.
In conclusion, If the lower-bound has never been reached, then we
ought to be sure that the length of RANGE-bound is keep intact with
the length of the substring. In contrast, once the LOWEST has been
found (reached), then we might not be confident about the integrity
of (the length of) the RANGE-bound anymore, in fact, the RANGE-bound
is no longer exists.
(It's paradoxial, isn't? We are sure about something based on
what we aren't, yet we aren't when conversely we are).
Implementation:
Since any prior index-values higher than the counter have been
previously mapped to their respective characters, the index-value
may not be higher than the counter (as noted above, the index-
value of TWINS, of course would be higher than the counter, but
consequently, both of the index-values will be once ever equal
anyway), if they did, then we could safely truncate the original
fetch position, right after that out-of-range character. Thus
basically, any OUT-RANGE index-value will result in rejection of
some portion of the chunk, or precisely, truncation of the chunk
up to the position of the OUT-RANGE index-value.
(Please bear in mind that when the LOWEST has been reached, then
the RANGE-bound is not in effect anymore).
If an unexpected index-value appears while the LOWEST has not been
reached yet, then the chunk could be discarded, we do know that
any unexpected index-value (any index-values not in the RANGE)
will violate the RANGE-bound. Since we have a confidence that the
length of RANGE-bound is keep intact with the length of substring
while the LOWEST has not been reached, then any appearance of
OUT-RANGE index-values would violate the length-bound. And since
the LOWEST whose characters implies as the firstly characters at
the sequence are has not been appears yet, we might discard all
the characters sequence that have been passed the prior test from
beginning of the skim cycle, whereas the remaining, untested
characters sequence, might also discarded as well because its
must be shorter than LENGTH as intended by the length of the
substring. They are all bring us the conclusion that the whole
chunk could be safely discarded.
addition:
If the LOWEST has NEVER been reached then the whole chunk could
also be discarded, the fetch position could be skipped by the
length of the substring.
If the LOWEST has EVER been reached then we should put the chunk's
character at her ESTIMATED proper place, in other words, shift
accordingly the original fetch position by length indicated by
the difference between the counter and the index-value. (As would
be described later, the shift would be increased by +1). Note that
we could not truncate the chunk because there could be several
characters in low order counter which might be matched the index-
value of TWINS.
Note: Further checks would be taken place ONLY for inequality.
if the LOWEST has not been reached yet, it means that the acceptable
index-value must be fit between LOWEST and counter (an exception
of this is for TWINS which should have been passed the earlier test).
if the LOWEST has been reached, it means that the counter position
(value) is below the lowest posibble index-value, its impossible
in this position that any lower index-values (compared with the
counter value) will be found, is not worth to test, it must be
higher than the counter value, and also, the index-value must be
equal with the LOWEST (since any TWINS should have been catched
in the prior comparison test, and so did with the out-range
characters, --in fact this state would have never been reached in
the last case), and finally it must be the SECOND LOWEST's
character found (since the first-one, would have been already
passed the previous test).
Nevertheless, at this state we could not discard the chunk
neither truncate it, since it is possible for all characters
(any index-values) betwen the LOWEST and HIGHEST might appear,
(although in this state they must be failed the comparison test).
Those will bring us a conclusion to shift the original fetch
position accordingly so the character in question is virtually
placed BEFORE the LOWEST position (recall that the character is
the SECOND LOWEST's character found), the shift distance it is
equal with the distance between counter and the LOWEST plus one.
It fairly possible that some distance exists between this character
position with the first LOWEST character position found, but we do
not have any information about how much of that, the best that we
could do is to shift the original fetch position as stated above.
(P = P + LOWEST - COUNTER +1).
SUMMARY:
There's always a trade between efficiency and completeness.
On comparison fails, we could simply fetch the next character
instead of doing any further test and processing which may or
may not give any advantages for searching.
Below are the summary of the steps and tests that could be taken,
from a simple to a comprehensive ones.
1. If the comparison fails (the index-value is different from the
counter) we could simply step one forward the original fetch
position.
2. If the comparison fails, we could do a test to check whether the
index-value is OUT-RANGE (higher than the HIGHEST) or not, and if it
did, then we could discard the chunk and skip forward that out-range
character), else we step the original fetch position one forward.
(higher than HIGHEST -> discard)
3. If the comparison fails, the index-value higher than the counter,
then we should get the LOWEST and then test whether she has been
reached or not by comparing her with the counter, if she was greater
than the counter, it means that she has been reached, and vice versa.
If she has NOT been reached yet, then we could discard the chunk,
else we step the original fetch position one forward.
(index-value > counter > LOWEST -> discard)
4. If the comparison fails, we might also do another test, by first
getting the index-value2 of the character in the substring at the
counter position, if only both of the index-values are equal then
the skim continued, else, if the chunk's index-value is out of
RANGE-bound (higher than the counter), then we could discard the
chunk and skip the original fetch to position by the LENGTH away,
else we step the original fetch position one forward.
5. If the comparison fails, the index-value2 we've got from the
substring's character at position of the counter is different
from the chunk's index-value, then we might do a final test, that
is checking whether the LOWEST has beeen reached by comparing the
counter with the LOWEST. If the values are different (and it will
--as described above, the LOWEST's value MUST be higher than the
counter, and also it will be EQUAL with the chunk's index-value),
then we should positioned the chunk's character at her ESTIMATED
proper place, ie. shift the ORIGIN by the difference between the
counter and the (assumed) index-value plus 1 additional offset.
Note that the last step is nothing more but an extension of the
previous one, there is no additional state, neither additional
burden to the program except for computing the skippable distance.
Also in practice, we should not wasted any effort to get the LOWEST
value, for she only exists in concept.
Ch = SubStr[1]
P = address(S)
tail = P + length(S) - length(SubStr) -1
@Loop:
inc(P)
if P > tail then goto @NOTFOUND
if S[P] <> Ch goto @Loop
Counter = length(SubStr)
@SkimLoop:
dec(Counter)
if Counter = 0 then goto @FOUND
I = index-value of S[P]
if I == Counter then goto @SkimLoop
(I could be any value excep Counter)
METHOD1:
if S[P + Counter] = SubStr[Counter] then goto @SkimLoop
else inc(P, Counter +1) (equal with @Shift1 below)
(
Here we assumed that the LOWEST has (always) been reached,
then the LOWEST MUST be equal with Counter.
It is no harm to do a thing like that, since if the LOWEST has
been reached we could either DISCARD or SHIFT the chunk.
I > Counter -> DISCARD
I < Counter -> SHIFT
The beauty of this simplification is that the Counter
value will always match the distance that could be skipped.
On the other hand, with this treatment we might only
shifting the chunk, when it could be discarded at all.
)
METHOD2:
if I > Counter then begin
V = Index-value of SubStr[Counter]
if I == V then goto @SkimLoop
if Counter > LOWEST then goto @Discard (P = P + HIGEHST +1)
else begin
if I > HIGHEST then @Truncate (P = P + Counter)
else @Shift (by delta value: P = P + Counter - I)
end
end
else (I must be < Counter)
goto @Shift1 (P = P + Counter +1)
