Дослідження методів пошуку в словнику термінів
Выполнен анализ эффективности методов поиска в словаре базы знаний. Проведено дослідження ефективності методів пошуку в словнику бази знань. It is investigated search method researching in a dictionary of terms....
Збережено в:
| Дата: | 2009 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/6520 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Дослідження методів пошуку в словнику термінів / О.П. Кургаєв, І.В. Савченко // Комп’ютерні засоби, мережі та системи. — 2009. — № 8. — С. 123-129. — Бібліогр.: 14 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859594891358633984 |
|---|---|
| author | Кургаєв, О.П. Савченко, І.В. |
| author_facet | Кургаєв, О.П. Савченко, І.В. |
| citation_txt | Дослідження методів пошуку в словнику термінів / О.П. Кургаєв, І.В. Савченко // Комп’ютерні засоби, мережі та системи. — 2009. — № 8. — С. 123-129. — Бібліогр.: 14 назв. — укр. |
| collection | DSpace DC |
| description | Выполнен анализ эффективности методов поиска в словаре базы знаний.
Проведено дослідження ефективності методів пошуку в словнику бази знань.
It is investigated search method researching in a dictionary of terms.
|
| first_indexed | 2025-11-27T19:38:33Z |
| format | Article |
| fulltext |
Комп’ютерні засоби, мережі та системи. 2009, № 8 123
A.F. Kurgaev, I.V. Savchenko
SEARCH METHODS
RESEARCHING IN A
DICTIONARY OF TERMS
It is investigated search method re-
searching in a dictionary of terms.
Выполнен анализ эффективности
методов поиска в словаре базы
знаний.
Проведено дослідження ефектив-
ності методів пошуку в словнику
бази знань.
О.П. Кургаєв, І.В. Савченко,
2009
УДК 681.3.016
О.П. КУРГАЄВ, І.В. САВЧЕНКО
ДОСЛІДЖЕННЯ МЕТОДІВ ПОШУКУ
В СЛОВНИКУ ТЕРМІНІВ
1. Актуальність обраної теми та аналіз
останніх досліджень і публікацій. На сьо-
годнішній день системи, які працюють із
знаннями (інтелектуальні системи), відігра-
ють значну роль у житті людства, оскільки
здатні запропонувати необхідне та кваліфі-
коване рішення проблеми за короткий час.
Такі системи використовуються під час кон-
тролю великих промислових процесів, прий-
мають рішення, спираючись на дані сотень
периферійних пристроїв, керують великими
інформаційними мережами, відіграють роль
консультанта в процесі прогнозування про-
цесу, до складу якого входить велика кіль-
кість факторів. Тобто розв’язують задачі, які
під силу тільки групі експертів.
Розробку експертних систем проводить
велика кількість компаній та корпорацій, се-
ред яких: XpertRule® [1] – розробка експерт-
них систем, що використовуються в бізнесі
(XpertRule Knowledge Builder, XpertRule
Servise, ін.); Production Systems Technologies,
Inc.® [2], OPSJ – розробка високоефективних
експертних систем, з використанням мови
Java; A I Developers, Inc.® [3], EZ-Xpert – ро-
зробка систем, що здатні генерувати код
процедури на мові С++; Togai InfraLogic,
Inc.® [4], FuzzyCLIPS – розробка нечітких
експертних систем; Gensym® [5], G2 – плат-
форма використовується для прийняття
рішень в системах реального часу (напри-
клад, моніторинг космічного корабля, проце-
сів автомобілебудування фірми Toyota);
Red Hat, Inc.® [6], JBoss Enterprise BRMS –
автоматизована система керування підпри-
ємством; Jess® [7], Jess – невелика за розмі-
рами та швидка система, що використовує
О.П. КУРГАЄВ, І.В. САВЧЕНКО
Комп’ютерні засоби, мережі та системи. 2009, № 8 124
мову Java, та інше.
Проблемам створення інтелектуальних систем присвячені праці багатьох
вітчизняних та закордонних науковців. Теорії створення та практичному засто-
суванню експертних систем присвячені роботи [8, 9]. Проблемам отримання,
структурування даних, знань та технологічним аспектам розробки систем, осно-
ваних на знаннях, присвячені роботи [10–12].
2. Постановка проблеми. У роботі [12] зазначено, що основною проблемою
сучасних систем обробки знань (СОЗ) є непродуктивні витрати пам’яті та часу
апаратних ресурсів на підтримку програмного забезпечення. Все це зумовлено
невідповідністю існуючих СОЗ людським можливостям обробки, накопичення
та представлення знань [12]. Тому пропонується створення процесора бази
знань, архітектура якого призначена для ефективної роботи з базою знань (БЗ).
Структура БЗ − це гіперграф над системою понять деякої прикладної теорії.
Для інтерпретації понять СОЗ використовує словник, терміни якого структурно
зв’язані із підграфами гіперграфа. Словник БЗ (СБЗ), зважаючи на його розміри
зберігається у вигляді файла.
Оскільки час пошуку в словнику є невід’ємною складовою загального часу
обробки знань у процесі вирішення задач, доцільним є проведення дослідження
методів пошуку в файлових словниках.
Мета роботи – провести аналіз ефективності існуючих методів пошуку
даних у файлових словниках та вибрати такі, що дозволяють підвищити продук-
тивність СОЗ.
3. Виклад основного матеріалу дослідження. Аналіз робіт [13, 14] свідчить
про те, що на сьогоднішній день використовуються такі методи пошуку: послі-
довний, бінарний, пошук за бінарними та збалансованими деревами, цифровий
пошук та хешування.
3.1. Вихідні теоретичні дані пошуку в СБЗ. В табл. 1 наведені результати
теоретичного дослідження ефективності основних методів пошуку, які описані
в [13]. В табл. 1 прийняті такі позначення:
N – кількість заповнених записів в індексній таблиці чи в файлі;
C , 1C – середня кількість порівнянь ключів записів;
D – кількість незбалансованих вузлів;
S – дорівнює 1 при вдалому пошуку, та 0 при невдалому пошуку;
1S – дорівнює 1, якщо перший пошук вдалий, 0 в іншому випадку;
A – коефіцієнт заповнення індексної таблиці;
M – сумарна кількість заповнених та порожніх записів в індексній таблиці
чи в файлі;
u – константа, яка залежить від параметрів системи пошуку.
3.2. Емпіричне дослідження методів пошуку. Для здійснення емпіричного
дослідження розроблено програмне забезпечення, функціональна структура яко-
го подана у вигляді наборів модулів (рис. 1). Керування роботою системи відбу-
вається за допомогою інтерфейсу користувача. Проект програми пошуку реалі-
зовано в програмному середовищі Borland C++ Builder 5.0. Усі модулі, в кінце-
ДОСЛІДЖЕННЯ МЕТОДІВ ПОШУКУ В СЛОВНИКУ ТЕРМІНІВ
Комп’ютерні засоби, мережі та системи. 2009, № 8 125
вому вигляді, представлені в виконавчому файлі Search.exe даного проекту.
В роботі розглянуто СБЗ з кількістю записів 105.
ТАБЛИЦЯ 1. Результати теоретичного дослідження ефективності методів пошуку
Метод пошуку Середній час пошуку даних в СБЗ Визначення констант
1. Послідовний
uSCt ⋅+−≅ )325( 2
1+
=
NC
2. Бінарний ( ) uSCt ⋅+−≅ 121018 NC 2log=
3. Пошук по бінар-
ному дереву
( ) uSCt ⋅+−≅ 45.25.7
NC ln2=
4. Пошук по зба-
лансованому
дереву
( ) uSDCCt ⋅−+++≅ 32210 1
CD
3
1
≈ , ( )SCC +≈
2
1
1 ,
1.0log01.1 2 +⋅≈+ NSC
5. Метод
роздільного
зв’язування
( ) uSSACt ⋅+−++≅ 1231747
( ) 1.21718.2
4
1 2 =+≈C ,
M
NA =
6. Метод лінійного
зондування
( ) uSECt ⋅−++≅ 42197
( ) 1.21718.2
4
1 2 =+≈C ,
M
CE )1( −
=
Результати емпіричного дослідження ефективності методів пошуку в СБЗ
наведені в табл. 2, в якій прийняті наступні позначення: t розрах. – розрахунковий
час пошуку (див. табл. 1); t експер. – середній час пошуку, отриманий експеримен-
тально; N розрах. – розрахункове значення кількості зчитаних записів з СБЗ,
яке відповідає параметру C (див. табл. 1); N експер. – кількість зчитаних записів
з СБЗ, яка отримана експериментально.
Параметри за якими оцінено ефективність кожного із методів пошуку наве-
дені далі:
– кількість прочитаних записів з файла БЗ;
– кількість прочитаних записів в індексній таблиці;
– розмір файла СБЗ, Mb;
– середній час пошуку, мкс.
О.П. КУРГАЄВ, І.В. САВЧЕНКО
Комп’ютерні засоби, мережі та системи. 2009, № 8 126
Головне меню програми
Модуль реалізації метода
послідовного пошуку
Модуль реалізації метода
бінарного пошуку
Реалізація методів пошуку
Модуль реалізації пошуку
по бінарному дереву
Модуль реалізації пошуку
по збалансованому дереву
Модуль реалізації метода
лінійного зондування
Модуль реалізації метода
роздільного зв`язування
СБЗ
Модуль редагування записів
Модуль збереження
результатів
РИС. 1. Функціональна структура програмного забезпечення системи дослідження
ефективності алгоритмів пошуку інформації в СБЗ
Результати оцінки вищезазначених параметрів показані на рис. 2 – 5. На
рис. 2 – 4 найменування стовпців відповідають найменуванням методів, які за-
значені в табл. 2.
ТАБЛИЦЯ 2. Результати емпіричного дослідження ефективності методів пошуку в СБЗ
Метод пошуку t розрах. t експер., мкс N розрах. N експер.
1. Послідовний 250003u 1710.21 50000 56122.16
2. Бінарний 301u 691.81 16.61 15.48
3. Пошук по бінарному
дереву
34.5u
511.87
23.02
20.65
4. Пошук по збалансо-
ваному дереву
82.73u
365.23
15.87
13.45
5. Метод роздільного
зв’язування
32.5u
172.26
2.1
2.16
6. Метод лінійного
зондування
31.7u
176.00
2.1
2.35
ДОСЛІДЖЕННЯ МЕТОДІВ ПОШУКУ В СЛОВНИКУ ТЕРМІНІВ
Комп’ютерні засоби, мережі та системи. 2009, № 8 127
15,48
1,73
1
0
1
0
1
0
1
0
0,00
2,00
4,00
6,00
8,00
10,00
12,00
14,00
16,00
Nекспер.
2 3 4 5 6
Серед. знач.
Серед. кв. відх.
РИС. 2. Кількість прочитаних записів у файлі СБЗ
0 0 0 0
20,65
3,31
13,45
1,59
2,16
1,00
2,35
1,02
0
5
10
15
20
25
N експер.
1 2 3 4 5 6
Серед. знач.
Серед. кв. відх.
РИС. 3. Кількість прочитаних записів в індексній таблиці СБЗ
О.П. КУРГАЄВ, І.В. САВЧЕНКО
Комп’ютерні засоби, мережі та системи. 2009, № 8 128
13,7 13,7 13,7 13,7
15,3
17,5
0
2
4
6
8
10
12
14
16
18
Mb
1 2 3 4 5 6
РИС. 4. Розмір файла СБЗ
0
100
200
300
400
500
600
700
800
900
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31
Номер експерименту, n
t, мкс
Бінарний
Збалансовані дерева
Пошук по бінарному
дереву
Роздільне
зв'язування
Лінійне зондування
РИС. 5. Результати емпіричного дослідження методів пошуку в СБЗ
ДОСЛІДЖЕННЯ МЕТОДІВ ПОШУКУ В СЛОВНИКУ ТЕРМІНІВ
Комп’ютерні засоби, мережі та системи. 2009, № 8 129
Висновки. У роботі проаналізовано наступні методи пошуку в СБЗ: послі-
довний, бінарний, пошук по деревам та пошук методом хешування.
Розбіжність теоретичних даних та результатів емпіричного дослідження по-
яснюється тим, що теоретичний метод не враховує практичну реалізацію алго-
ритмів, в яке входить час на доступ до зовнішніх даних, та особливості архітек-
тури системи.
Аналіз результатів, наведених в табл. 1 та 2 свідчить про те, що методи хе-
шування (роздільне зв’язування, лінійне зондування) є найшвидші. Пошук по
деревам (бінарні дерева, збалансовані дерева) дає дещо гірші результати (див.
табл. 1 та 2).
Однак при роботі із СБЗ пошук по деревах у порівнянні з методами хешу-
вання має переваги, оскільки: 1) дерева не потребують розрахунку хеш-функції,
який може бути досить громіздким, якщо ключ запису великий; 2) дерева мають
простішу абстрактну структуру представлення даних; 3) дерева можуть забезпе-
чити гарантовану продуктивність пошуку; 4) дерева підтримують більш широ-
кий діапазон операцій над даними СБЗ (сортування, пошук).
На підставі викладеного можна зробити висновок, що для роботи із СБЗ до-
цільно використовувати методи пошуку по деревах.
1. http://www.xpertrule.com
2. http://www.pst.com
3. http://www.ez-wpert.com
4. http://www.ortech-engr.com
5. http://www.gensym.com
6. http://www.redhat.com
7. http://www.jessrules.com
8. Джарратано Д. Экспертные системы: принципы разработки и программирование. 4-е.
изд. – М.: Изд. дом Вильямс, 2007. – 1152 с.
9. Джексон П. Введение в экспертные системы. 3-е. изд. – М.: Изд. дом Вильямс, 2001. –
624 с.
10. Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интеллектуальных систем: Учебник для
вузов. – СПб: Питер, 2000. – 384 с.
11. Частиков А., Белов Д., Гаврилова Т. Разработка экспертных систем. Среда CLIPS. –
БХВ-Петербург, 2003. – 608 с.
12. Кургаев А.Ф. Проблемная ориентация архитектуры компьютерных систем. – Киев:
Сталь, 2008. – 540 с.
13. Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск. – М.:
Изд. дом Вильямс, 2000. – 832 с.
14. Седжвик Р. Фундаментальные алгоритмы на C++. Анализ/Структуры данных/Сорти-
ровка/Поиск: Пер. с англ. – К.: Изд-во «ДиаСофт», 2001. – 688 с.
Отримано 25.08.2009
http://www.xpertrule.com/�
http://www.pst.com/�
http://www.ez-wpert.com/�
http://www.ortech-engr.com/�
http://www.gensym.com/�
http://www.redhat.com/�
http://www.jessrules.com/�
http://www.piter.com/publish/authors/19072/0/�
http://www.piter.com/publish/authors/19692/0/�
https://www.ozon.ru/context/detail/id/1098685/�
|
| id | nasplib_isofts_kiev_ua-123456789-6520 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1817-9908 |
| language | Ukrainian |
| last_indexed | 2025-11-27T19:38:33Z |
| publishDate | 2009 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Кургаєв, О.П. Савченко, І.В. 2010-03-05T15:07:37Z 2010-03-05T15:07:37Z 2009 Дослідження методів пошуку в словнику термінів / О.П. Кургаєв, І.В. Савченко // Комп’ютерні засоби, мережі та системи. — 2009. — № 8. — С. 123-129. — Бібліогр.: 14 назв. — укр. 1817-9908 https://nasplib.isofts.kiev.ua/handle/123456789/6520 681.3.016 Выполнен анализ эффективности методов поиска в словаре базы знаний. Проведено дослідження ефективності методів пошуку в словнику бази знань. It is investigated search method researching in a dictionary of terms. uk Інститут кібернетики ім. В.М. Глушкова НАН України Дослідження методів пошуку в словнику термінів Search methods researching in a dictionary of terms Article published earlier |
| spellingShingle | Дослідження методів пошуку в словнику термінів Кургаєв, О.П. Савченко, І.В. |
| title | Дослідження методів пошуку в словнику термінів |
| title_alt | Search methods researching in a dictionary of terms |
| title_full | Дослідження методів пошуку в словнику термінів |
| title_fullStr | Дослідження методів пошуку в словнику термінів |
| title_full_unstemmed | Дослідження методів пошуку в словнику термінів |
| title_short | Дослідження методів пошуку в словнику термінів |
| title_sort | дослідження методів пошуку в словнику термінів |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/6520 |
| work_keys_str_mv | AT kurgaêvop doslídžennâmetodívpošukuvslovnikutermínív AT savčenkoív doslídžennâmetodívpošukuvslovnikutermínív AT kurgaêvop searchmethodsresearchinginadictionaryofterms AT savčenkoív searchmethodsresearchinginadictionaryofterms |