Wir nehmen die Rechte an Inhalten ernst. Wenn Sie vermuten, dass dies Ihr Inhalt ist, beanspruchen Sie ihn hier.
Verfügbare Formate
Als PDF herunterladen oder online auf Scribd lesen
Input Enhancement in string matching - Horspool’s Algorithm
Input enhancement can be applied to the problem of string matching. Recall that the problem
of string matching requires finding an occurrence of a given string of m characters called
the partern in a longer string of n characters called the text. We discussed the brute-force
algorithm for this problem in first module: it simply matches corresponding pairs of
characters in the pattern and the text left to right and, if a mismatch occurs, shifts the pattem
one position to the right for the nest trial. Since the maximum number of such trials
is a — m+ Land so on,
Horspool’s Algorithm
This Horspool’s Algorithm is one faster algorithm to search the pattem in. the string using
shift table. Ifa mismatch occurs, we need to shift the pattem to the right. Clearly, we would
like to make as large a shift as possible. Horspool’s algoritlua deterinines the size of such a
shift by looking at the character c of the text. Shift the pattem from left to tight as per the
shift table.
Example: How to construct shift table using the patterm text.
1) Text =“WELCOMETOVISHALMORE” and Pattern = “VISHAL”
Length of pattem VISHAL is 6
Shift table
vit{s |H] ATL]
5]4]3|2[1]6)
Formula to find shift Value of each character
By default length of last character is length of pattem i.e. 6
Value = Length —index — 1
V=6-0-1=5
1=6-1-1=4
S=6-2-1=3
H=6-3-1=2
A=6-4-1=1
L =6—5—1=0 (but this is last character length 6) 2) Text =“WELCOMETOAKANKSHAMORE” and Pattem = “AKANKSHA”
Length of pattem AKANKSHA is 8
Shift table
In patter A occurs three time overwrite the value, K occurs two time overwrite the
value and last write * for mismatch but length of * or last character is 8
4]K]N]s/H]* |
8/34 ]2/1 [8]
Formula to find shift value of each character
Value = Length —index — 1
Horspool’s Algorithm (P{], T[], m,n)
// PL] pattem string.
#T[] text string
//m length of pattern
//a length of text
i€ma;
while( i < 7-1) do
k€o;
while (k< m1 and t[i-k]=pfm-i-k]) do
ke kel;
end while
if (=m)
i€m+l;
else
iCi+ sft):
endif
end while Example 1: Construct a shift table for the pattern BABY and search for the same in the
text BOBBY-LIKES-BABY
Solution :
Shit table BABY length of pattern is 4
O}1,2)3
BIA|Y|*
1)2\4)4
Step 1: We scan from right to left B # Y then shift pattern from left to right one
position.
B/O[B/a)Y] -[L[1[KJE|S| -|B/A/B[y
BIA[Bly)
Step 2: We scan B and B ¢ A then shift. pattern
from left to right
B
Step 3: We scan from right to left - 4 Y then shift pattern from left to right
entire patter by four position.
BO[B/B|¥/-\L]1 [K[E|s|- [BlA[BIY
B/A/BlY)
Step 4: We scan from right to left EY then shift pattern from left to right
entire pattern by four position.
B/o[B/BY] - [L[1K/B]s| - [BAB Y!
BIALB|
Step 5: We scan from»right}t0 left A # Y then sh
ift pattern from left to right
pattern by two position,
T|KJE|S|-
BIA
Y
Step 6; Allthe characters of pattern are matching with all the characters in the
text, Hence declare a successful search pattern in text.
B{o|B|B[Y| -|L|1|K[E|s|-{B]A[Bly]
I (BlalBly
Example 2: Construct a shift table for the pattern BAOBAB and search for the same in the
text BESS_KNEW_ABOUT_BAOBABS using Horspool’s algoritlun.
Example 3: Apply this to find the pattem BARBER and search for the same in the text
JIM_SAW_ME_IN_A_BARBER_SHOP using Horspoo!’s algorithm.
Example 4: Apply Horspool’s algorithm to search a pattem PAPPAR in the text
PAPPAPPAPPARRASSAN.
10
Tentu, Ini Adalah Data Dari Foto Anda Yang Telah Diubah Ke Dalam Format Tabel. Anda Bisa Langsung Menyalin (Copy) Dan Menempel (Paste) Data Ini Ke Dalam File Excel Anda. Lampiran KOORDINAT_ Kawasan Peruma