Кнут-Морис-Пратт алгоритмі. Боуер-Мур алгоритмі
Кнут – Моррис – Пратт алгоритмі (КМП-алгоритм) — берілген текст жолында ішкі жол тармағын табу алгоритмін айтамыз.
Кнут-Морис-Пратт (КМП) алгоритмы кірісінде мынандай сөзден құралады X=x[1]x[2]...x[n] және әріптердің әрқайсысын солдан оңға қарай тексереді де, массивтың натурал сандарын енгізеді l[1],...,l[n], сонда l[i]=len(n(x[1]...x[i])), т.е. l[i] – бұл сөздің бастапқы ұзындығы x[1]...x[i], ол сонымен қатар оның соңы болып та табылады.
Сол кезде мынадай сұрақ туындайды: мұның бәрі ішкі сөзді іздеуге қандай қатысы бар? Басқа сөзбен айтқанда, В сөзінде А сөзі ішкі сөз болатынын анықтау үшін Кнут-Морис-Прат алгоритмын қалай қолданады? Жауап алу үшін Кнут-Морис-Прат алгоритмын A#B сөзіне қолданайық, мұндағы # - әріп, ол А-ға да, В-ға да кірмейді.
Кнут-Морис-Пратт алгоритмын A#B сөзіне қолданамыз. l[1],...,l[n] мәнін есептеу үшін n ұзындығы бар X сөзіне бұл мәндерді есте сақтаймыз. Әрі қарай біз і – дан және l[1],...,l[n] массивынан басқа l[i] мәнін есептеу үшін ештеңе керек емес.
Практикада X және Y бірінен соң бірі орналаспауы да мүмкін, сондықтан Х және У сөзінің қарастыруын бөлек циклдар ретінде жүзеге асырған жөн. Бұл сөздердің арасында "#" символды қоюға керек емес.
Енді тиісті алгоритмді жазып көрейік (тексеруші, мынау сөз X=x[1]...x[n] ішкі сөз бол ала ма Y=y[1]...y[m]) ( [Шень, 1995,с.169]):
|
|
|
PROGRAM Knuth_Morris_Pratt;
{ тексеруші, мынаусөз X=x[1]...x[n] }
{ ішкісөзболалама Y=y[1]...y[m] }
var Wrd1: String[255]; { Іздеуүшінберілгенсөз }
Wrd2: String[255]; { Берілгенсөз }
l : Array[0..255] of Byte; { Функция n }
i : Byte; { Циклпараметрі }
j : Byte; len : Byte;
BEGIN
Write('Іздеуүшінбосемессөздіенгізіңіздер: ');
ReadLn(Wrd1);
Write('Берілгенсөздіенгізіңіз : ');
Read(Wrd2); {Хсөзіүшін l функциясыныңмәнінесептеу }
i:=1;
l[1]:=0; { l[1],...,l[i] мәніосыуақытқаесептелегнболсын }
While i<>Length(Wrd1) do
begin
len:=l[i]; { len – бастапқысөздіңұзындығы Wrd1[1]...Wrd1[i], }
{ оныңсоңыболыпесептелінеді }
While (Wrd1[len+1]<>Wrd1[i+1]) AND (len>0) do
{Басытиістіемесболыпшыққандықтан
оған n функциясынқолданамыз }
len:=l[len];
If Wrd1[len+1]=Wrd1[i+1] { бастаудытауыпнемесеоныңжоқтығынакөздеріжетті }
then l[i+1]:=len+1 { Wrd1[1]...Wrd1[len] – керектіеңұзынсөз }
else l[i+1]:=0; { керектібастапқысөздержоқ }
|
|
|
i:=i+1
end;
{ ------------------------------------------------------- }
j:=0;
len:=0; { len – Хсөзініңбастапқымаксималдыұзындығы }
{ сөздіңсоңыдаболады Wrd2[1]...Wrd2[j] }
While (len<>Length(Wrd1)) AND (j<>Length(Wrd2)) do
begin
While (Wrd1[len+1]<>Wrd2[j+1]) AND (len>0) do
{ басыдұрысболмағандықтаноғанбасқафункциянықолданамыз n }
len:=l[len];
If Wrd1[len+1]=Wrd2[j+1] { Керектіфункциянытаптынемесеоныңжоқтығынакөздерінжеткізді }
then len:=len+1 { Wrd1[1]...Wrd1[len] – керектіеңұзынсөз}
else len:=0; { керектісөзжоқ }
j:=j+1
end;
If len=Length(Wrd1) then WriteLn(' X сөзікездесті.')
else WriteLn('X сөзікездескенжоқ..')
END.
Боуэр-Мур (Boyer-Moore) алгоритмініңқарапайымнұсқасы
Қарастырылыпжатқаналгоритмалғашқыжағдайдақарапайымсияқтыкөрінеді, бұлалгоритмбарлықәріптердіңқандайдабірбөлігінғанаоқиды. Бұлқалайболуымүмкін? Мұныңидеясыөтеқарапайым.
Мысалы, егербіз "abcd" үлгінітапқымызкелсе. Осыкездесөздіңтөртіншіәріпіненазараударамыз, егердеолмысалы "e", ондаалдыңғыүшәріптіоқуғакерекемес (шындададаүлгіде "e" әріпіжоқ, сондықтанолбесіншіәріптенбұрынбасталмайды.
|
|
|
Бұлалгоритмныңқарапайыммысалынкелтіреміз, бұлалгоритмбарлықжағдайлардатезжұмысістемейді.
X=x[1]...x[n] – сөз - үлгі, бұлсөздііздеуқажет. S – тіңәрбірсөзінеХсөзініңоңжақкіріссөзінтабукерек, яғни k еңүлкен, мұндағы x[k]=s. Бұлмәліметтерді Posit[s] массивтесақтуақажет. Егер s әріпімүлдекездеспесе, онда Posit[s]=0 теңболады (әріқарайнегеекенінқараймыз).
PROGRAM Boyer_Moore_1;
{ Алгоритмдіжасайтынбағдарлама }
{ X=x[1]...x[n] Y=y[1]...y[m] сөзініңішкісөзіболама}
var Wrd1 : String[255]; { Іздеуүшінқолданылатынсөз }
Wrd2 : String[255]; { Берілгенсөз }
Posit: Array['a'..'z'] of Byte; i : Byte; { Циклпараметрі }
s : Char; { Циклпараметрі }
last : Byte;
n,m : Byte;
Flag : Boolean; { Флаг - қорытынды }
BEGIN
Write('Іздеуүшінбосемессөздіенгізіңіз: ');
ReadLn(Wrd1);
Write('Берілгенсөздіенгізіңіздер : ');
Read(Wrd2);
n:=Length(Wrd1);
m:=Length(Wrd2);
Flag:=FALSE;
For s:='a' to 'z' do Posit[s]:=0;
For i:=1 to n do Posit[Wrd1[i]]:=i;
|
|
|
last:=n; { Іздеупроцессікезінде last –тесөздеәріптіңнөмерін, }
{ қарама - қарсысындаүлгініңсоңғысөзіорналасады }
{ Еңбасында last=n, кейін last үлкееді }
{ Wrd1 сөзініңбарлықжағдайларытексерілген }
While last<=m do { Сөзбіткенжоқ }
If Wrd1[n]<>Wrd2[last] then { Соңғыәріптерібөлек }
last:=last+(n-Posit[Wrd2[last]]) { n-Posit[Wrd2[last]] – бұлүлгініңминималды
{ орынауыстыруы}
{ мұндағы Wrd2[last] қарама – қарсысөз }
{ үлгідесондайсөзорналасады.Егердемұндайәріпмүлдеболмаса, ондаүлгінің {барлықұзындығынажалжытубасталады }
else If Wrd1=Copy(Wrd2,last-n+1,n)
{ Егердеберілгенжағдайкелісілетінболса, онда Wrd1[1]...Wrd1[n]=Wrd2[last-n+1]...Wrd2[last],}
{ онда сәйкес келгені туралы хабарлама пайда болады}
then begin
Flag:=TRUE;
WriteLn('Қорытынды: ',Flag);
Halt
end
else last:=last+1;
WriteLn('Қорытынды: ',Flag)
END.
Нәтиже
Сандықемесалгоритмдерәртүрліқұрылымданғанмәліметттерментүрлендірулержүргізугеарналған.
Сызықтықіздеупроцедурасықарапайыммассивнемесежиынныңэлементтерінрет-ретіменқарастыруболыпкеледі.
Рабиналгоритмі SF-алгоритмныңмодификациясынантұратынқарапайымидеяғанегізделген.
Жолдардаішкіжолдардыіздеуталаптарды
Егер x[1],x[2],...,x[n] – қандайдабіралфавиттіңәріптері. Анықтаңыз, x[1],x[2],...,x[n] тізбегіндебіріненсоңбіріорналасқанәріптер x[k],x[k+1],...,x[k+m]. Басқатерминалогиядаанықтауқажет, x[1]x[2]...x[n] сөзінде, ішкісөз x[k]x[k+1]...x[k+m], үлгідепаталады.
Кнут – Моррис – Пратталгоритмі (КМП-алгоритм) — берілгентекстжолындаішкіжолтармағынтабуалгоритмінайтамыз. АлгоритмдіалғашашқанамериканғалымдарыДональдКнутжәнеВонПраттеді, оларжекедараөзбетіментапқанДжеймсМоррисболды. Өзеңбектірініңжемісінолар1977 басыпшығарды.
Боуэр-Мур (Boyer-Moore) алгоритмініңқарапайымнұсқасы
Қарастырылыпжатқаналгоритмалғашқыжағдайдақарапайымсияқтыкөрінеді, бұлалгоритмбарлықәріптердіңқандайдабірбөлігінғанаоқиды. Бұлқалайболуымүмкін? Мұныңидеясыөтеқарапайым.
Мысалы, егербіз "abcd" үлгінітапқымызкелсе. Осыкездесөздіңтөртіншіәріпіненазараударамыз, егердеолмысалы "e", ондаалдыңғыүшәріптіоқуғакерекемес (шындададаүлгіде "e" әріпіжоқ, сондықтанолбесіншіәріптенбұрынбасталмайды.
Бұлалгоритмныңқарапайыммысалынкелтіреміз, бұлалгоритмбарлықжағдайлардатезжұмысістемейді.
X=x[1]...x[n] – сөз - үлгі, бұлсөздііздеуқажет. S – тіңәрбірсөзінеХсөзініңоңжақкіріссөзінтабукерек, яғни k еңүлкен, мұндағы x[k]=s. Бұлмәліметтерді Posit[s] массивтесақтуақажет. Егер s әріпімүлдекездеспесе, онда Posit[s]=0 теңболады (әріқарайнегеекенінқараймыз).
PROGRAM Boyer_Moore_1;
{ Алгоритмдіжасайтынбағдарлама }
{ X=x[1]...x[n] Y=y[1]...y[m] сөзініңішкісөзіболама}
var Wrd1 : String[255]; { Іздеуүшінқолданылатынсөз }
Wrd2 : String[255]; { Берілгенсөз }
Posit: Array['a'..'z'] of Byte; i : Byte; { Циклпараметрі }
s : Char; { Циклпараметрі }
last : Byte;
n,m : Byte;
Flag : Boolean; { Флаг - қорытынды }
BEGIN
Write('Іздеуүшінбосемессөздіенгізіңіз: ');
ReadLn(Wrd1);
Write('Берілгенсөздіенгізіңіздер : ');
Read(Wrd2);
n:=Length(Wrd1);
m:=Length(Wrd2);
Flag:=FALSE;
For s:='a' to 'z' do Posit[s]:=0;
For i:=1 to n do Posit[Wrd1[i]]:=i;
last:=n; { Іздеупроцессікезінде last –тесөздеәріптіңнөмерін, }
{ қарама - қарсысындаүлгініңсоңғысөзіорналасады }
{ Еңбасында last=n, кейін last үлкееді }
{ Wrd1 сөзініңбарлықжағдайларытексерілген }
While last<=m do { Сөзбіткенжоқ }
If Wrd1[n]<>Wrd2[last] then { Соңғыәріптерібөлек }
last:=last+(n-Posit[Wrd2[last]]) { n-Posit[Wrd2[last]] – бұлүлгініңминималды
{ орынауыстыруы}
{ мұндағы Wrd2[last] қарама – қарсысөз }
{ үлгідесондайсөзорналасады.Егердемұндайәріпмүлдеболмаса, ондаүлгінің {барлықұзындығынажалжытубасталады }
else If Wrd1=Copy(Wrd2,last-n+1,n)
{ Егердеберілгенжағдайкелісілетінболса, онда Wrd1[1]...Wrd1[n]=Wrd2[last-n+1]...Wrd2[last],}
{ онда сәйкес келгені туралы хабарлама пайда болады}
then begin
Flag:=TRUE;
WriteLn('Қорытынды: ',Flag);
Halt
end
else last:=last+1;
WriteLn('Қорытынды: ',Flag)
END.
Нәтиже
Сандықемесалгоритмдерәртүрліқұрылымданғанмәліметттерментүрлендірулержүргізугеарналған.
Сызықтықіздеупроцедурасықарапайыммассивнемесежиынныңэлементтерінрет-ретіменқарастыруболыпкеледі.
Рабиналгоритмі SF-алгоритмныңмодификациясынантұратынқарапайымидеяғанегізделген.
Жолдардаішкіжолдардыіздеуталаптарды
Егер x[1],x[2],...,x[n] – қандайдабіралфавиттіңәріптері. Анықтаңыз, x[1],x[2],...,x[n] тізбегіндебіріненсоңбіріорналасқанәріптер x[k],x[k+1],...,x[k+m]. Басқатерминалогиядаанықтауқажет, x[1]x[2]...x[n] сөзінде, ішкісөз x[k]x[k+1]...x[k+m], үлгідепаталады.
2. ДҚБЖ-дегі сұранымдар
SQL стандартындакестеқұруинструкциясынанықтаудыңбірнешежолыбар, соныңішіндебазалыформатыкелесіболады:
<кестеніанықтау> ::= CREATE TABLE кестеаты
{ (баған_атыдеректер_типі [NOT NULL] [UNIQUE]
[DEFAULT <мәні>] [CHECK (<таңдаушарты>)] [,…n]}
[CONSTRAINT шекқоюаты]
[PRIMARY KEY (баған_аты [,…n] ) ]
{ [UNIQUE (баған_аты [,…n] ) ] }
{ [FOREIGN KEY (сыртқыкілттіңбағанының _аты [,…n] )
немесе:
<кестеніанықтау> ::= CREATE TABLE
[деректерқорыаты. [қолданушы]. | қолданушы.] кестеаты
(<кестеэлементі> [,…n] )
мұндағы
<кестеэлементі> ::=
{<бағандыанықтау>}
| бағанаты AS <өрнек>
| <кестегешекқою>
Дата добавления: 2018-08-06; просмотров: 759; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!