Метод пошуку інформації у файлах баз даних, який враховує розподіл імовірностей звертання до записів
Пропонується метод пошуку інформації у файлах баз даних, який враховує розподіл імовірностей звертання до записів, в основі якого лежить поняття умовно середнього запису. Виводяться формули для визначення умовно середнього запису у випадку різних законів розподілу ймовірностей. Досліджується ефектив...
Gespeichert in:
| Veröffentlicht in: | Фізико-математичне моделювання та інформаційні технології |
|---|---|
| Datum: | 2006 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України
2006
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/21152 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Метод пошуку інформації у файлах баз даних, який враховує розподіл імовірностей звертання до записів / Г. Цегелик, А. Мельник // Фіз.-мат. моделювання та інформ. технології. — 2006. — Вип. 4. — С. 169-177. — Бібліогр.: 12 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860062722233729024 |
|---|---|
| author | Цегелик, Г. Мельничин, А. |
| author_facet | Цегелик, Г. Мельничин, А. |
| citation_txt | Метод пошуку інформації у файлах баз даних, який враховує розподіл імовірностей звертання до записів / Г. Цегелик, А. Мельник // Фіз.-мат. моделювання та інформ. технології. — 2006. — Вип. 4. — С. 169-177. — Бібліогр.: 12 назв. — укр. |
| collection | DSpace DC |
| container_title | Фізико-математичне моделювання та інформаційні технології |
| description | Пропонується метод пошуку інформації у файлах баз даних, який враховує розподіл імовірностей звертання до записів, в основі якого лежить поняття умовно середнього запису. Виводяться формули для визначення умовно середнього запису у випадку різних законів розподілу ймовірностей. Досліджується ефективність цього методу порівняно з методами послідовного перегляду та двійкового пошуку для таких законів розподілу ймовірностей як рівномірний, "бінарний", Зіпфа, узагальнений, частковим випадком якого є розподіл, що наближено задовольняє правило "80-20". За критерій ефективності прийнято математичне сподівання кількості порівнянь, необхідних для пошуку запису у файлі.
The method of the information search in database files, which considers the probability distribution of request to records, has been constructed. Formulas for identification of record, which is located in the middle of the file, under certain conditions have been proposed for different laws of distribution. The comparative analysis of efficiency of method with the linear search method and binary search method for different laws of probability distribution of requests to records has been investigated. The mathematical expectation of number of comparisons was used as an efficiency criterion.
Предлагается метод поиска информации в файлах баз данных, учитывающий распределение вероятностей обращения к записям, в основании которого лежит понятие условно средней записи. Выведены формулы для определения условно средней записи для разных законов распределения вероятностей. Исследуется эффективность метода по сравнению с методами последовательного пересмотра и двоичного поиска для таких законов распределения вероятностей обращения к записям, как равномерный, "бинарный", Зипфа, обобщенный, частным случаем которого является распределение, приближенно удовлетворяющее правило "80-20". За критерий эффективности принято математическое ожидание количества сравнений, необходимых для поиска записи в файле.
|
| first_indexed | 2025-12-07T17:05:15Z |
| format | Article |
| fulltext |
Метод пошуку інформації у файлах баз даних, який
враховує розподіл імовірностей звертання до записів
Григорій Цегелик1, Андрій Мельничин2
1 д. ф.-м. н., професор, Львівський національний університет імені Івана Франка, вул. Університетська, 1,
Львів, 79000, e-mail: kafmmsep@franko.lviv.ua
2 Львівський національний університет імені Івана Франка, вул. Університетська, 1, Львів, 79000,
e-mail: andrue_m@mail333.com
Пропонується метод пошуку інформації у файлах баз даних, який враховує розподіл імовір-
ностей звертання до записів, в основі якого лежить поняття умовно середнього запису.
Виводяться формули для визначення умовно середнього запису у випадку різних законів роз-
поділу ймовірностей. Досліджується ефективність цього методу порівняно з методами
послідовного перегляду та двійкового пошуку для таких законів розподілу ймовірностей як
рівномірний, «бінарний», Зіпфа, узагальнений, частковим випадком якого є розподіл, що на-
ближено задовольняє правило «80-20». За критерій ефективності прийнято математичне
сподівання кількості порівнянь, необхідних для пошуку запису у файлі.
Ключові слова: методи пошуку, файли баз даних, закони розподілу ймо-
вірностей.
Вступ. Найуживанішими методами пошуку інформації у файлах баз даних є ме-
тод послідовного перегляду, однорівневий і багаторівневий блочний і двійковий
пошук. Дослідженню ефективності цих методів для різних законів розподілу ймо-
вірностей звертання до записів присвячена низка праць. Зокрема, в [1] розглянуто
ефективність методу послідовного перегляду для таких законів розподілу ймовір-
ностей як рівномірний, «бінарний», Зіпфа та правило «80-20». У [2] побудовано
оптимальну схему блочного пошуку для рівномірного розподілу ймовірностей.
Повне та всестороннє дослідження ефективності методів послідовного перегляду,
однорівневого та багаторівневого блочного і двійкового пошуку для різних законів
розподілу ймовірностей звертання до записів (рівномірного, «бінарного», Зіпфа,
узагальненого, частковим випадком якого є розподіл, що наближено задовольняє
правило «80-20») проведено в [3-11]. За критерій ефективності прийнято матема-
тичне сподівання кількості порівнянь, необхідних для пошуку запису у файлі.
Для кожного закону розподілу ймовірностей проведено порівняльний аналіз ефек-
тивності методів і визначено найкращий метод пошуку. Однак алгоритми методів
послідовного перегляду та двійкового пошуку не враховують розподіл імовірнос-
тей звертання до записів, а алгоритми методів однорівневого та багаторівневого блоч-
ного пошуку розподіл імовірностей звертання до записів враховують лише при роз-
битті записів файлу на блоки та підблоки однакової довжини у випадку побудови
оптимальних схем блочного пошуку. Тому постає задача побудови такого методу
УДК 519.68
169
Григорій Цегелик, Андрій Мельничин
Метод пошуку інформації у файлах баз даних, який враховує розподіл імовірностей...
170
пошуку, який би враховував розподіл імовірностей звертання до записів. Саме
такий метод пошуку і пропонується в даній роботі. Досліджується також ефек-
тивність цього методу порівняно з методами послідовного перегляду та двійко-
вого пошуку для згаданих законів розподілу ймовірностей звертання до записів.
1. Постановка задачі
Розглянемо послідовний упорядкований файл, записи якого характеризуються
значеннями деякого ключа. Нехай N — кількість записів файла, pi — ймовірність
звертання до і-го запису файла, Ki — значення ключа, яким характеризується і-ий
запис файла. Треба побудувати такий метод пошуку записів у файлі, алгоритм
якого враховував би розподіл імовірностей звертання до записів, та дослідити
ефективність цього методу порівняно з ефективністю методів двійкового пошуку
та послідовного перегляду для різних відомих законів розподілу ймовірностей
звертання до записів.
2. Алгоритм методу
Для опису алгоритму методу введемо поняття умовно середнього запису серед
записів файла. Вважатимемо, що умовно середнім серед записів із порядковими
номерами від m до n, де Nnm ≤<≤1 , є запис із номером r, якщо
∑∑
+=
−
=≤≤
−
n
ki
i
k
mi
inkm
pp
1
1
min
досягається для k = r. Якщо мінімум досягається для двох значень індексу k, то за r
приймаємо менший із них. Зазначимо також, що якщо k = m або k = n, то суми
∑
−
=
1k
mi
ip або ж ∑
+=
n
ki
ip
1
є невизначеними. Тому приймаємо, що 0
1
=∑
−
=
k
mi
ip , якщо k = m;
,0
1
=∑
+=
n
ki
ip якщо k = n.
Нехай у файлі потрібно знайти запис із значенням ключа К. Алгоритм ме-
тоду складається з низки кроків. На першому кроці К порівнюється зі значенням
ключа запису, який є умовно середнім у файлі. Якщо порівняння успішне (два
значення, що порівнюються, співпадають), то на цьому робота алгоритму завер-
шується. Якщо значення, що порівнюються, не співпадають, то з їх порівняння
бачимо, в якій частині файла треба продовжувати пошук. Тоді, на наступному
кроці К порівнюється зі значенням ключа запису, який є умовно середнім у ви-
браній частині файла. У разі успішного порівняння робота алгоритму завершу-
ється. При неуспішному — пошук продовжується вже у меншій частині файла.
І т. д. Через скінченну кількість кроків шуканий запис буде знайдено, якщо він
міститься у файлі.
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2006, вип. 4, 169-177
171
3. Формули для знаходження умовно середнього запису
1. Якщо розподіл ймовірностей звертання до записів є рівномірним, то метод
співпадає з методом двійкового пошуку. Тоді серед записів із номерами від m до n
включно середнім буде запис із номером r, де [ ]2/)( nmr += .
2. Нехай ймовірності звертання до записів розподілені за «бінарним» законом,
тобто
( ),1,121 −== Nip i
i 121 −= N
Np .
Тоді умовно середнім серед записів із номерами 2k – 1, 2k, 2k + 1, ..., N
[ ]
= 2,1 Nk буде запис із номером r = 2k.
3. Приймемо, що ймовірності звертання до записів розподілені за законом Зіпфа,
тобто
( )Ni
iH
p
N
i ,11
== ,
де ∑
=
=
N
k
N k
H
1
1 — частинна сума гармонічного ряду. Оскільки
,111
1
1
1
1
−=− ∑∑∑∑
+=
−
=+=
−
=
n
ki
k
miN
n
ki
i
k
mi
i iiH
pp
то умовно середнім серед записів із номерами від m до n включно ( 1+> mn ),
буде запис із номером r = k, де k — індекс, для якого досягається
∑∑
+=
−
=≤≤
−
n
ki
k
minkm ii 1
1 11min .
Для n = m + 1 умовно середнім буде запис із номером m.
Одержану формулу для знаходження індексу k можна замінити простішою.
Справді,
),(ln)1ln()(1
11
11
kmkk
x
dx
i
k
m
k
mi
ε+−−=ε+= ∫∑
−−
=
),()1ln(ln)(1
22
11
kknk
x
dx
i
n
k
n
ki
ε++−=ε+= ∫∑
++=
де )(1 kε та )(2 kε — похибки апроксимації відповідних сум. Тоді
Григорій Цегелик, Андрій Мельничин
Метод пошуку інформації у файлах баз даних, який враховує розподіл імовірностей...
172
)(ln)1ln(11 2
1
1
knmk
ii
n
ki
k
mi
ε+−−=− ∑∑
+=
−
=
,
де )()()( 21 kkk ε−ε=ε . Тому для відшукання k використаємо наближену формулу
1+≈ nmk . Оскільки k повинно бути цілим числом, то приймаємо [ ]1+= nmk .
4. Якщо ймовірності звертання до записів задовольняють узагальнений закон
розподілу, тобто
Ni
Hi
p c
N
ci ,1,1
)( == ,
де ,10 << c ∑
=
=
N
k
c
c
N k
H
1
)( 1 — частинна сума узагальненого гармонічного ряду, то
серед записів із номерами від m до n включно для n > m + 1 умовно середнім буде
запис із номером r = k, де k — індекс, для якого досягається
∑∑
+=
−
=≤≤
−
n
ki
c
k
mi
cnkm ii 1
1 11min .
При n = m + 1 умовно середнім буде запис із номером m. Оскільки
( ){ } ),(1
1
1)(1 )(
1
11)(
1
11
kmk
c
kdxx
i
cccc
k
m
c
k
mi
c ε+−−
−
=ε+= −−
−
−
−
=
∫∑
( ){ } ),(1
1
1)(1 )(
2
11)(
2
11
kkn
c
kdxx
i
cccc
n
k
c
n
ki
c ε++−
−
=ε+= −−
+
−
+=
∫∑
де )()(
1 kcε і )()(
2 kcε — похибки апроксимації відповідних сум, то
( ) ( ){ } )(11
1
111 )(1111
1
1
knmkk
cii
ccccc
n
ki
c
k
mi
c ε+−−++−
−
=− −−−−
+=
−
=
∑∑ .
Тут ).()()( )(
2
)(
1
)( kkk ccc ε−ε=ε
Із рівності
( ) ( ) ,11 1111 cccc nmkk −−−− +=++−
або
cc
c
c
c
c nm
k
k
k
k −−
−
−
−
− +=
++
− 11
1
1
1
1 1111
одержуємо таку наближену формулу для знаходження k
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2006, вип. 4, 169-177
173
( ) .
2
1 1
1
11 ccc nmk −−−
+≈
Оскільки k повинно бути цілим числом, то приймаємо
( )
+=
−−− ccc nmk
1
1
11
2
1 .
Зокрема, при с = 0 (тобто за рівномірного розподілу ймовірностей) із одержаної
формули дістаємо [ ]2/)( nmk += .
4. Математичне сподівання кількості порівнянь,
необхідних для пошуку запису
Для дослідження ефективності методу за критерій ефективності приймемо мате-
матичне сподівання кількості порівнянь, необхідних для пошуку запису у файлі.
Запишемо формули математичного сподівання для деяких законів розподілу
ймовірностей звертання до записів.
У разі рівномірного розподілу ймовірностей звертання до записів середня
кількість порівнянь, необхідних для пошуку запису у файлі, визначається за фор-
мулою [12]
,12
N
llE
l −−
−=
де [ ]Nl 2log1+= .
Якщо ймовірності звертання до записів задовольняють «бінарний» закон
розподілу, то для математичного сподівання кількості порівнянь, необхідних для
пошуку запису у файлі, одержуємо вираз
k
k
i
ii
kiE 2
2
2322 2
23
2
1
2
1
2
1 +
+
++= ∑
=
−
при N = 2k та
k
k
i
ii
kiE 2
2
2322 2
33
2
1
2
1
2
1 +
+
++= ∑
=
−
при N = 2k + 1.
У разі закону Зіпфа й узагальненого розподілу для знаходження матема-
тичного сподівання кількості порівнянь, необхідних для пошуку запису у файлі,
будемо застосовувати алгоритм методу, описаний вище.
Григорій Цегелик, Андрій Мельничин
Метод пошуку інформації у файлах баз даних, який враховує розподіл імовірностей...
174
5. Порівняльна ефективність методу
У табл. 1 із використанням методу, який враховує розподіл імовірностей звер-
тання до записів, приведені результати розрахунку математичного сподівання
кількості порівнянь, необхідних для пошуку запису у файлі для різних законів
розподілу ймовірностей і деяких N. У табл. 2 і табл. 3 для тих же законів розпо-
ділу ймовірностей звертання до записів і N наведено результати розрахунку
математичного сподівання у разі використання методів послідовного перегляду
та двійкового пошуку відповідно.
Зауважимо, що у табл. 2 при обчисленні математичного сподівання кіль-
кості порівнянь використані формули для математичного сподівання, записані в [7].
Для обчислення математичного сподівання у випадку методу двійкового пошуку
(див. табл. 3) використано формулу [4]
,
1
2
1
)12(
1
∑ ∑
= =
−
−
=
l
i k
nk
i
i
ipE
яка справджується при 12 −= lN , де l — будь-яке натуральне число )2( ≥l ,
12/ −= i
i mn , 1]2/[ += Nm (у загальному випадку можна скористатися алгорит-
мом методу).
Таблиця 1
Математичне сподівання кількості порівнянь, необхідних для пошуку запису у файлі.
Метод із врахуванням розподілу ймовірностей звертання до записів
Закон розподілу
N
с=0 с=0,2 с=0,4 с=0,6 с=0,8 Зіпфа (с=1) «Бінарний»
3 1,667 1,674 1,685 1,697 1,711 1,727 1,750
7 2,429 2,442 2,471 2,423 2,381 2,264 1,984
15 3,267 3,306 3,313 3,219 3,123 2,926 2,000
31 4,161 4,199 4,159 4,055 3,847 3,655 2,000
63 5,095 5,131 5,068 4,900 4,630 4,265 2,000
127 6,055 6,082 6,004 5,779 5,431 4,901 2,000
255 7,031 7,055 6,951 6,678 6,210 5,554 2,000
511 8,018 8,039 7,918 7,598 7,033 6,164 2,000
1023 9,010 9,027 8,894 8,529 7,843 6,814 2,000
2047 10,005 10,021 9,877 9,471 8,673 7,413 2,000
4095 11,003 11,018 10,866 10,426 9,502 7,999 2,000
8191 12,002 12,016 11,858 11,386 10,355 8,589 2,000
16383 13,001 13,014 12,852 12,352 11,205 9,174 2,000
32767 14,000 14,013 13,847 13,326 12,075 9,755 2,000
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2006, вип. 4, 169-177
175
Таблиця 2
Математичне сподівання кількості порівнянь, необхідних для пошуку запису у файлі.
Метод послідовного перегляду
Закон розподілу
N
с=0 с=0,2 с=0,4 с=0,6 с=0,8 Зіпфа (с=1) «Бінарний»
3 2 1,93 1,85 1,78 1,71 1,79 1,750
7 4 3,75 3,49 3,22 2,96 2,77 1,984
15 8 7,36 6,67 5,95 5,22 4,57 2,000
31 16 14,53 12,91 11,17 9,40 7,73 2,000
63 32 28,81 25,23 21,28 17,21 13,35 2,000
127 64 57,36 49,65 41,02 31,99 23,43 2,000
255 128 114,35 98,21 79,77 60,19 41,68 2,000
511 256 288,25 194,96 156,20 114,39 75,00 2,000
1023 512 455,94 387,94 307,43 219,20 136,26 2,000
2047 1024 911,20 773,24 607,47 422,93 249,60 2,000
4095 2048 1821,60 1542,96 1203,90 820,55 460,40 2,000
8191 4096 3642,25 3081,23 2391,24 1599,36 854,32 2,000
16383 8192 7283,37 6156,22 4757,61 3129,37 1593,52 2,000
32767 16384 14565,40 12304,20 9477,81 6142,71 2985,83 2,000
Таблиця 3
Математичне сподівання кількості порівнянь, необхідних для пошуку запису у файлі.
Метод двійкового пошуку
Закон розподілу
N
с=0 с=0,2 с=0,4 с=0,6 с=0,8 Зіпфа (с=1) «Бінарний»
3 1,45 1,67 1,68 1,70 1,71 1,73 1,75
7 2,35 3,02 3,05 3,09 3,14 3,19 3,28
15 3,24 5,71 5,77 5,87 5,98 6,10 6,50
31 4,15 11,07 11,19 11,36 11,62 11,93 13,06
63 5,09 21,77 21,97 22,30 22,79 23,45 26,12
127 6,05 43,14 43,45 44,03 44,97 46,33 52,24
255 7,03 85,86 86,32 87,30 89,07 91,80 104,47
511 8,02 171,25 171,93 173,54 176,80 182,26 208,94
1023 9,01 341,98 342,96 345,58 351,53 362,36 417,88
2047 10,01 683,39 684,77 689,54 699,76 721,15 835,76
4095 11,01 1366,15 1368,07 1374,79 1394,16 1436,28 1671,53
8191 12,01 2731,58 2734,24 2744,87 2779,55 2862,29 3343,05
16383 13,00 5462,36 5466,01 5482,71 5544,56 5706,81 6686,11
32767 14,00 10923,8 10928,03 10954,90 11064,90 11362,60 13372,20
Григорій Цегелик, Андрій Мельничин
Метод пошуку інформації у файлах баз даних, який враховує розподіл імовірностей...
176
Висновки. Запропоновано метод пошуку записів у файлах баз даних, який вра-
ховує розподіл імовірностей звертання до записів. Для порівняння ефективності
побудованого методу і методів послідовного перегляду та двійкового пошуку для
розглянутих законів розподілу ймовірностей звертання до записів проведено роз-
рахунок математичного сподівання кількості порівнянь, необхідних для пошуку
запису у файлі, для різної кількості записів N. Побудований метод за ефектив-
ністю значно переважає методи двійкового пошуку та послідовного перегляду
для всіх розглянутих законів розподілу ймовірностей звертання до записів, окрім
рівномірного для методу двійкового пошуку та «бінарного» для методу послідов-
ного перегляду. Метод, який враховує розподіл імовірностей звертання до записів,
у випадку рівномірного розподілу ймовірностей співпадає з методом двійкового
пошуку, а у випадку «бінарного» розподілу — з методом послідовного перегляду.
Література
[1] Кнут Д. Искусство программирования для ЭВМ. Т. 3: Сортировка и поиск. —
М.: Издательский дом «Вильямс», 2000. — 832 с.
[2] Мартин Дж. Организация баз данных в вычислительных системах. — М.: Мир,
1980. — 644 с.
[3] Мельничин А. В., Цегелик Г. Г. Аналіз методів пошуку інформації в файлах баз да-
них для різних законів розподілу ймовірностей звертання до записів // Комп’ютерні
технології друкарства. — 2006. — № 16. — С. 220-236.
[4] Мельничин А. В., Цегелик Г. Г. Ефективність методу двійкового пошуку інформації
у файлах баз даних для різних законів розподілу ймовірностей звертання до запи-
сів // Вісн. Львів. ун-ту. Сер. прикл. математика та інформатика. — 2006. — Вип. 11. —
С. 213-218.
[5] Філяк М. І., Цегелик Г. Г. Ефективність методів послідовного перегляду і блочного
пошуку для різних законів розподілу ймовірностей звертання до записів // Вісн.
Львів. ун-ту. Сер. мех.-мат. — 1998. — Вип. 50. — С. 200-203.
[6] Філяк М. І., Цегелик Г. Г. Ефективність методу дворівневого блочного пошуку у
впорядкованих файлах для різних законів розподілу ймовірностей звертання до за-
писів // Вісн. Львів. ун-ту. Сер. прикл. математика та інформатика. — 1999. —
Вип. 1. — С. 227-230.
[7] Філяк М. І., Цегелик Г. Г., Дороцька Х. С. Порівняльний аналіз ефективності методу
послідовного перегляду для різних законів розподілу ймовірностей звертання до
записів // Вісн. НУ «Львівська політехніка». Сер. інформаційні системи та мережі. —
2000. — № 406. — С. 226-231.
[8] Філяк М. І., Цегелик Г. Г. Метод r-рівневого блочного пошуку записів у впорядко-
ваних файлах і його ефективність // Вісн. Львів. ун-ту. Сер. прикл. математика та
інформатика. — 2000. — Вип. 3. — С. 169-173.
[9] Цегелик Г. Г., Мельничин А. В. Ефективність методу r-рівневого блочного пошуку
для різних законів розподілу ймовірностей звертання до записів // Вісн. НУ
«Львівська політехніка». Сер. інформаційні системи та мережі. — 2006. — № 415. —
С. 211-221.
[10] Цегелик Г. Г., Філяк М. І. Про ефективність методу r-рівневого блочного пошуку
записів у впорядкованих файлах // Вісн. Львів. ун-ту. Сер. прикл. математика та
інформатика. — 2002. — Вип. 5. — С. 174-177.
ISSN 1816-1545 Фізико-математичне моделювання та інформаційні технології
2006, вип. 4, 169-177
177
[11] Цегелик Г. Г., Філяк М. І., Дороцька Х. С. Порівняльний аналіз ефективності мето-
ду блочного пошуку для різних законів розподілу ймовірностей звертання до запи-
сів // Комп’ютерні технології друкарства. — 2000. — № 5. — С. 320-326.
[12] Цегелик Г. Г. Методы автоматической обработки информации. — Львов: Вища шк.,
1981. — 132 с.
The Method of the Information Search in Database Files, which
Considers the Probability Distribution of Requests to Records
Hryhoriy Tsehelyk, Andriy Melnytchyn
The method of the information search in database files, which considers the probability distribu-
tion of request to records, has been constructed. Formulas for identification of record, which is lo-
cated in the middle of the file, under certain conditions have been proposed for different laws of
distribution. The comparative analysis of efficiency of method with the linear search method and
binary search method for different laws of probability distribution of requests to records has been
investigated. The mathematical expectation of number of comparisons was used as an efficiency
criterion.
Метод поиска информации в файлах баз данных,
учитывающий распределение вероятностей
обращения к записям
Григорий Цегелик, Андрей Мельничин
Предлагается метод поиска информации в файлах баз данных, учитывающий распределе-
ние вероятностей обращения к записям, в основании которого лежит понятие условно
средней записи. Выведены формулы для определения условно средней записи для разных за-
конов распределения вероятностей. Исследуется эффективность метода по сравнению с
методами последовательного пересмотра и двоичного поиска для таких законов распреде-
ления вероятностей обращения к записям, как равномерный, «бинарный», Зипфа, обобщен-
ный, частным случаем которого является распределение, приближенно удовлетворяющее
правило «80-20». За критерий эффективности принято математическое ожидание коли-
чества сравнений, необходимых для поиска записи в файле.
Отримано 22.03.06
|
| id | nasplib_isofts_kiev_ua-123456789-21152 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1816-1545 |
| language | Ukrainian |
| last_indexed | 2025-12-07T17:05:15Z |
| publishDate | 2006 |
| publisher | Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України |
| record_format | dspace |
| spelling | Цегелик, Г. Мельничин, А. 2011-06-15T11:48:02Z 2011-06-15T11:48:02Z 2006 Метод пошуку інформації у файлах баз даних, який враховує розподіл імовірностей звертання до записів / Г. Цегелик, А. Мельник // Фіз.-мат. моделювання та інформ. технології. — 2006. — Вип. 4. — С. 169-177. — Бібліогр.: 12 назв. — укр. 1816-1545 https://nasplib.isofts.kiev.ua/handle/123456789/21152 519.68 Пропонується метод пошуку інформації у файлах баз даних, який враховує розподіл імовірностей звертання до записів, в основі якого лежить поняття умовно середнього запису. Виводяться формули для визначення умовно середнього запису у випадку різних законів розподілу ймовірностей. Досліджується ефективність цього методу порівняно з методами послідовного перегляду та двійкового пошуку для таких законів розподілу ймовірностей як рівномірний, "бінарний", Зіпфа, узагальнений, частковим випадком якого є розподіл, що наближено задовольняє правило "80-20". За критерій ефективності прийнято математичне сподівання кількості порівнянь, необхідних для пошуку запису у файлі. The method of the information search in database files, which considers the probability distribution of request to records, has been constructed. Formulas for identification of record, which is located in the middle of the file, under certain conditions have been proposed for different laws of distribution. The comparative analysis of efficiency of method with the linear search method and binary search method for different laws of probability distribution of requests to records has been investigated. The mathematical expectation of number of comparisons was used as an efficiency criterion. Предлагается метод поиска информации в файлах баз данных, учитывающий распределение вероятностей обращения к записям, в основании которого лежит понятие условно средней записи. Выведены формулы для определения условно средней записи для разных законов распределения вероятностей. Исследуется эффективность метода по сравнению с методами последовательного пересмотра и двоичного поиска для таких законов распределения вероятностей обращения к записям, как равномерный, "бинарный", Зипфа, обобщенный, частным случаем которого является распределение, приближенно удовлетворяющее правило "80-20". За критерий эффективности принято математическое ожидание количества сравнений, необходимых для поиска записи в файле. uk Центр математичного моделювання Інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України Фізико-математичне моделювання та інформаційні технології Метод пошуку інформації у файлах баз даних, який враховує розподіл імовірностей звертання до записів The method of the information search in database files, which considers the probability distribution of requests to records Метод поиска информации в файлах баз данных, учитывающий распределение вероятностей обращения к записям Article published earlier |
| spellingShingle | Метод пошуку інформації у файлах баз даних, який враховує розподіл імовірностей звертання до записів Цегелик, Г. Мельничин, А. |
| title | Метод пошуку інформації у файлах баз даних, який враховує розподіл імовірностей звертання до записів |
| title_alt | The method of the information search in database files, which considers the probability distribution of requests to records Метод поиска информации в файлах баз данных, учитывающий распределение вероятностей обращения к записям |
| title_full | Метод пошуку інформації у файлах баз даних, який враховує розподіл імовірностей звертання до записів |
| title_fullStr | Метод пошуку інформації у файлах баз даних, який враховує розподіл імовірностей звертання до записів |
| title_full_unstemmed | Метод пошуку інформації у файлах баз даних, який враховує розподіл імовірностей звертання до записів |
| title_short | Метод пошуку інформації у файлах баз даних, який враховує розподіл імовірностей звертання до записів |
| title_sort | метод пошуку інформації у файлах баз даних, який враховує розподіл імовірностей звертання до записів |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/21152 |
| work_keys_str_mv | AT cegelikg metodpošukuínformacííufailahbazdanihâkiivrahovuêrozpodílímovírnosteizvertannâdozapisív AT melʹničina metodpošukuínformacííufailahbazdanihâkiivrahovuêrozpodílímovírnosteizvertannâdozapisív AT cegelikg themethodoftheinformationsearchindatabasefileswhichconsiderstheprobabilitydistributionofrequeststorecords AT melʹničina themethodoftheinformationsearchindatabasefileswhichconsiderstheprobabilitydistributionofrequeststorecords AT cegelikg metodpoiskainformaciivfailahbazdannyhučityvaûŝiiraspredelenieveroâtnosteiobraŝeniâkzapisâm AT melʹničina metodpoiskainformaciivfailahbazdannyhučityvaûŝiiraspredelenieveroâtnosteiobraŝeniâkzapisâm |