202
𝐸
𝑗
хизмат турида ишлатиладиган маълумотлар бошқа хизмат турларида
ҳам ишлатилиши мумкин. Буни умумий ҳолда қуйидагича бўлади:
𝐸
𝑗
= ℜ
𝑗
(𝐶
𝑗
), 𝐶
𝑗
= ⋃
∆
𝑖𝑗
𝑘
𝑣
𝑛
𝑘=1
, 𝑗 = 1. . 𝑛, 𝑘 = 1. . 𝑣
𝑛
,
(2)
бу
ерда
𝑛
- мос алгоритм рақами,
𝜈
𝑛
- зарур маълумотлар сони.
Берилган
S
матн сўзлар мажмуасидан иборат бўлиб, у
талаб даражасида
узунлик ва шаклда бўлсин. Қатламлаштириш алгоритмида (ҚА) матндаги сўзлар
сонига мос
𝑊
𝑙
= {0 | 𝑠
𝑖
: 𝑖 = 1. . 𝑛 + 1}(𝑙 = 0. .6)
,
𝐷 = {𝑑
𝑖
𝑖
= 0, 𝑖 = 1. . 𝑛}
бўш қийматли
вектор киритилиши зарур бунда
𝑛
сўзлар сони,
𝑊
𝑙
векторини 0 ва
𝑛 + 1
элементларибўш қийматларга эга бўлади.
𝑊
𝑙
вектор қаторлари сўровнома матнни
ҚАнинг ҳар бир қадамида тўлдирилиб борилади.
𝐷
гапдаги сўзлар бирикмалари
ва ажратмалари вектори:
𝑃𝑆 = "|,|ва|ҳам|ҳамда|"; 𝑃𝐸 = "|ё|ёки|ёхуд|";𝑃𝐼 = "|~мас|эмас|ташқари|"
Энди ҚАнинг ушбу қадамларини батафсил қараб чиқамиз.
1-қадам.Сўзлар(0-қатлам).
Дастлаб ҚАда
S
матндаги сўзлар жойлашуви
бўйича
𝑊
0
= {𝑤
𝑖
0
= 〈𝑠
𝑖
〉, 𝑖 = 1. . 𝑛}
векторнинг элементларига берилади. Бу ерда
қўштирноқ ичи ва ажратиш белгилари (вергул каби) битта сўзбўлади.
Матндан 1-6 қатламларини ажратиб олиш муҳим аҳамиятга эга.S берилган
матн бўлсин.
S={aa, “b b” ва cc xx mm qq yy эмас uu ёки hh gg zz ee}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
W
0
w
nn
aa
,
b b
ва cc xx
mm
qq
yy
эмас
uu
ёки
hh
gg
zz
ee
2-қадам. Сўзажратмалари.
Бунда гапдаги сўз боғловчилар ва ажратма
аниқланади.
𝑤
𝑖
0
вектордан
ажратма белгилари
𝐷
мос вектор элементларига
кўчирилади ва ушбу
𝑤
𝑖
0
элемент қиймати ўчирилади.
𝐷 = {∃𝑤
𝑖
0
∈ 𝑃𝑆 → (𝑑
𝑖
𝑛
= 1, 𝑤
𝑖
0
= ∅)}(𝑖 = 1. . 𝑛)
Агар
𝐷 = 1
бўлса, бу ажратиш белгиси мавжудлигини билдиради.
+
i=1..n
w[0,i]
PS
A2
A3
d[i]=1;
i=0..6; j=1..N; W[i,j]=0; d[j]=0;
PS
=
,
ва
хам
ҳамда
;
PE =
ёки
ёхуд
;
PI=
~
мас
эмас
бўлмаса
;
Матнни
сўзларга ажратиш ва
сўзлар сони N
A1
Ажратишларни
аниқлаш
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
203
W
0
w
nn
aa
,
b b
ва cc xx
mm
qq
yy
эмас
uu
ёки
hh
gg
zz
ee
d
1
1
3-қадам. Объектлар(1-қатлам)
.
𝑊
0
= {𝑤
𝑖
0
}
векторнинг бўш бўлмаган
элементларидан КСБга бўйича қидирилади. Агар
𝑤
𝑖
0
элемент КСБ мос келса мос
индексли
𝑊
1
= {𝑤
𝑖
1
}
вектор элементларига (1-қатлам) кўчирилади.
𝑊
1
= {∃𝑤
𝑖
1
∈ КСБ → 𝑤
𝑖
1
= 〈𝑤
𝑖
0
, 𝑝
𝑖
0
, 𝑝
𝑖
1
, 𝑝
𝑖
2
, 𝑝
𝑖
3
〉}(𝑖 = 1. . 𝑛)
бу ерда
𝑤
𝑖
1
КСБдан
топилган объектлар,
𝑝
𝑖
0
топилган калит сўзнинг тартиб
рақами,
𝑝
𝑖
1
топилган калит сўзнинг
S
матндаги жойлашув индекси,
𝑝
𝑖
2
топилган
калит сўзга мос объект номи кўрсатилади.
𝑝
𝑖
3
= 〈0,1〉
объектнинг аниқловчи ёки
аниқланувчи эканлигини англатиб, уни қиймати 4-қатламда аниқланади. КСБ
мосликни қидириш жараёнида
𝑤
𝑖
0
мавжуд бўлса, у ҳолда алгоритм унга қўшиб
𝑤
𝑖+1
0
элементни ҳам қидиради. Бу бирлаштириб қидириш
⋃
𝑤
𝑖
0
𝑚
𝑗=1
(𝑚 ≤ 𝑛)
жараёни
то КСБ мослик бўлмагунча давом этади.
Калит
сўзларни
ўқиш
T[]
//
Жадвал
номлари
M[]
//
Майдон
номлари
i=1..n
c=null; t=0;
j=i..n
c=c&w[1,j];
pr>L
t=t+1
n=n-t-1;
m=m+1
КСБ
М
билан
С
ни
ўхшашлик
даражасини
топиш
ф
-
я
pr=F(c
M);
Kp=M{k};
//
Калит
сўз
индекси
t>0
j=n
+
-
p[1,i]=Kp;
p[0,i]=m;
w[1,i]=c
Kp1=0 & i=n
+
+
Ўхшашлик
даражаси
A3
A4
A2
Агар
сўзлар
КСБда
мавжуд
бўлмаса
1
қатлам
,
объектлар
3-расм. Қатламлаштиришнинг 1-қадам алгоритми
Бу
ердаги
F(l)
функция махсус кўп мезонли қидириш мулоҳазалардаги
объектларни КСБ элементларига мослигини аниқлайди. Алгоритмда аниқланган
𝑊
1
= {𝑤
𝑖
1
: 𝑖 = 1. . 𝑛}
вектор КСБ маълумотларидан иборат ва у берилган
S
матннинг
қисм тўпламидир, яъни,
𝑊
1
⊆ 𝑆
.
204
1
2
3
4
5
6
7
8
8
9
10
11
12
13 14 15 16
W
0
w nn aa
,
b b
ва cc
X
qq
эмас
ёки hh
d
1
1
X
W
1
w
xx mm
X
yy
uu
gg zz ee
p
0
1
X
2
3
4
5
6
p
1
7
X
9
11
14 15 16
p
2
40
X
19
45
93 11
4
p
3
X
4-қадам. Инкорлар(2-қатлам).
Бунда бўш бўлмаган
𝑊
1
= {𝑤
𝑖
1
}(𝑤
𝑖
1
≠
0)
объектлардан кейин келувчи
𝑊
0
= {𝑤
𝑖+1
0
}(𝑑 ≠ 0)
вектор
элементларидан инкор
этувчи (“эмас”, “ташқари” каби) сўзлар қидирилади. Алгоритм натижага эришса,
𝑊
0
= {𝑤
𝑖+1
0
}
элемент бўшатилади ва
{𝑤
𝑖
2
}
элементига 1 қиймати (4-қатлам)
берилади,
𝑊
⃖ (𝑗 = 𝑖 + 1. . 𝑛 + 1)
амали бажарилади.
𝑊
2
= ((∃𝑤
𝑖+1
0
∈ 𝑃𝐼 𝐴𝑁𝐷 𝑑 = 0) → {
𝑤
𝑖
2
= 1, 𝑤
𝑖+1
0
= ∅
𝑊
⃖ (𝑗 = 𝑖 + 1. . 𝑛 + 1)
) (𝑖 = 1. . 𝑛)
бу ерда
𝑤
𝑖
2
= 1
бўлса, инкор белгиси борлигини билдиради.
i=1..n
w[1,i]
PI
d=0
w[2,i]=1;
+
Кўчириш
A4
A5
2
қатлам
,
инкорлар
1
2
3
4
5
6
7
8
9
10
10
11
12
13
14
15
W
0
w
nn
aa
,
b b
ва cc
qq
X
ёки
hh
d
1
1
X
W
1
w
xx mm
yy
X
uu
gg
zz
ee
W
2
1
X
5-қадам. Эквивалентлик (3-қатлам)
.Бу ҳам олдинги қадам каби
𝑊
1
=
{𝑤
𝑖
1
}(𝑤
𝑖
1
≠ 0)
объектлардан
кейин
келувчи
𝑊
0
= {𝑤
𝑖+1
0
}(𝑑 ≠ 0)
вектор
элементларидан эквивалентлик (“ё”, “ёки” каби) сўзлар қидирилади. Натижага
эга бўлган
𝑊
0
веторнинг элементлар
{𝑤
𝑖+1
0
}
бўшатилади ва
{𝑤
𝑖
3
}
элементларига (3-
қатлам) қиймати берилади.
𝑊
⃖ (𝑗 = 𝑖 + 1. . 𝑛 + 1)
амали бажарилади.Бу ерда
𝑤
𝑖
3
≠ 0
бўлса, инкор белгиси борлигини билдиради.
205
i=1..n
w[1,i]
PE
d=0
w[3,i]=1;
+
Кўчириш
A5
A6
3
қатлам
,
эквивалентлик
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
W
0
w
nn
aa
,
b b
ва cc
qq
hh
d
1
1
W
1
w
xx mm
yy
uu
gg
zz
ee
W
2
1
W
3
1
6-қадам.
Аниқловчиларни
ажратиш
.
Бунда
𝑊
1
= {𝑤
𝑖
1
}(𝑤
𝑖
1
≠ 0)
элементлар учун ундан олдинги позиция
𝑤
𝑖−1
0
(𝑑 = 0)
текширилади. Агар 1-қатлам
элементи бўш бўлмаса
(
𝑤
𝑖−1
1
= 0
)
у ҳолда бу
𝑤
𝑖
1
объект аниқланувчи ҳисобланади
ва у жойлашган устун
𝑊
векторининг охирига алмаштирилади. Бу ерда
𝑊
вектор
элементлари қайта индексланади.
+
i=1..n-k
d=0
w[0,i-1]=
w[1,i]
SWAP(W[i], W[n-k])
SWAP(D[i], D[n-k])
k=k+1
k=0
Do'stlaringiz bilan baham: 
