Файл: Зубов В.С. Математическое обеспечение цифровых вычислительных машин и систем учеб. пособие.pdf

- 8 5 -

лэняого явно ограничения в списке, естественно рассматри­

вать доступ к ассоциации как двухзТапный процесс, напри­ мер: вначале обнаруживается любая запись, входящая в ас­

социацию, а затем выявляются все входящие в неё записи.'

2. Поиск по близости трактуется обычно как нахожде­ ние единственной записи, значение некоторой функции кото­ рой от значения управляющего слова имеет наименьшее отли­

чие в заданном смысле от значения той же функции для а|>-

гумента, являющегося поисковым образом. Примером различ­ ного смысла отличия для тривиальной функции, значение которой совпадает оо значением аргумента, является поиск по близости сверху и полок по близости снизу. Примером использования нетривиальной функции является поиск по близости модуля значения управляющего слова к модулю поис­ кового образа. Произведём уточнение его оути для случая сложного управляющего слова. В первую очередь выявляется запись с минимальным отличием её старшего управляющего по­

ля от модуля старшего управляющего поля поискового образа. '■

Боли записей с минимальным отличием несколько, из них вы­ бираются записи с минимальным отличием по модулю следую­ щего п$ значимости управляющего поля от модуля соответст­ вующего поля поискового образа. Сужение круга записей-пре-

тендентов происходит до момента выполнения хотя бы одного условия из двух: а)осталась единственная запиоь-претендеят б)рассмотрены все поля управляющего слова; если претенден­ тов несколько, то из них произвольно выбирается одна за­ пись (однако пользователь может трактовать поиск по бли­ зости и как нахождение всех записей с минимальным отклоне­ нием). Действительный процесс поиска может и не быть разде-

- ё б -

лёняым на этапы, умозрительно выделенные наш для облегче­

ния его восприятия, и рассматривать управляющее слово одним

актом.

3. Примером случая, когда затруднительно явно выделять

ассоциации записей для последующего•их поиска, является случай нахождения ассоциации записей со значениями управ­

ляющих слов, попадающих в заданный интервал числовой оси

(предполагается что от случая к случаю поиска интервал мо­ жет изменяться; управляющее слово может быть спроецировано на числовую ось по правилу, рассмотренному в §4 гл .П ). Вы­

деление таких ассоциаций обычно производится в процессе поиска, именуемого поиском по интервалу. Если список запи­

(отрицательной) бесконечности,условие поиска уточняется соответственно в следующее: нахождение всех записей, зна­ чение управляющего слова которых меньше (больше)заданнога

4. Подобно тому, как в п.2 при поиске по близости рассматривается некоторая функция от значений управляюще­ го поля, поиск по совпадению и интервалу может быть рассмо­ трен в обобщённом виде, как поиск по совпадению значений такой функции с заданным значением или поиск по попаданию их в заданный интервал. Подобное обобщение случаев поиска,

рассмотренных в п .п . 1 - 3 , будем именовать поиском по сложному арифметическому условию.

5. Рассматривая логические переменные, соответству­ ющие подобным вышеуказанным условиям поиска, можно обра-

- а ? - ,

эовать из них логические выражения и использовать их в качестве логической переменной, соответствующей сложному условию поиска. Подобный поиск будем именовать поиском по логической совокупности условий. В частности,это мо­ жет быть дизъюнктивная (конъюнктивная) совокупность, ког­ да сложное условие выполняется при выполнении хотя бы од­ ного из составляющих: (обязательно всех составляющих усло­ вий) .Многоаспектный поиск по совпадению может рассматри­ ваться как пример поиска по конъюнктивной совокупности простейших условий. >

6. Как указывалось выше, в состав записей могут вхо­ дить и текстовые элементы данных. При их использовании в составе управляющих слов понятия совпадения, попадания в интервал, близости (минимального отклонения) могут интер­ претироваться не в"арифметическом", а в более сложною.,

условно именуемом семантическим, смысле. Характерным при­ мером может служить библиографический поиск, когда объ­ ектами поиска служат научные публикации, рефераты, тези­ сы публикаций. Условием поиска по аналогии с поиском по совпадению может быть совпадение содержания закодирован­ ного зЙцюса с содержанием публикации, также закодиро­ ванным по определённым правилам, или - по аналогии с по­ иском по интервалу - совпадение содержания публикации с содержанием запрошенного в условии поиска раздела, по существу более широкого, чем содержание отдельной публи­ кации, или - по аналогий с поиоком по близости - не обя­ зательно полное совпадение, но близость содержания запро­ са и содержания публикации. Поиск, осуществляемый по опи­ сываемым условиям будем называть’ поиском по семантическо­

му условию.

Формулировка критерия, позволяющего судить о смысло­ вом совпадении, попадании в интервал или близости, являет­ ся сложной задачей, требующей в разных случаях разного

подхода и далеко не всегда поддающейся разрешению. Кроме

лнительной проверки совпадение, попадание в смысловой ин­ тервал или близость по смыслу. Важнейшей проблемой, подле­ жащей разрешению при разработке информационно-поисковых систем, осуществляющих поиск по семантическому условию,

является выбор языка для кодирования информации внутри ЭВМ и запросов на поиск, позволяющего, во-первых, отразить

существенные черты самой информации и запроса и, во-вторых,

реализовать в рамках этого языка проверку критериев совпа­ дения информации с заданным запросом или близости запроса

иинформации.

б) Поиск с ослаблением ( усилением) условий

ни одного объекта, удовлетворяющего условиям приска. Та­ кой случай' может произойти, например, при поиске по ин­

-89-

лабленяе условия поиска может быть произведено исключением отдельных полей из поискового образа. И в общем случае по­ иска по конъюнктивной совокупности условии ослабление со­ вокупного условия также производится исключением отдельных условий-компонент. Напротив, такое исключение из дизъюнк­ тивной совокупности условий поиска приводит к усилению со ­ вокупного условия.

Особенно часто необходимость динамических изменений

поисковых образов возникает при семантическом поиске.

До сих пор подразумевался вариант поиска с ослаблени­

ем (усилением) условий поиска, при котором результат вы­ полненного этапа используется для управления следующими

шагами поиска. Такое решение, в самом деле, часто оказы-

с

дельное выполнение этапов поиска при поэтапном ослаблении условий поиска может привести к неоправданным затратам машинного времени. В этих случаях оказывается целесооб­ разным выполнять т .н . поиск о незакреплёнными условиями,

предполагающий некоторое совмещение действий по поиску для поисковых условий различной силы.

Допустим, например, что задана конъюнктивная сово­

купность П условий поиска, и необходимо выделить объекты

с наибольшим количеством выполненных условий. Если это ко­

-9 0

конъюнктивных сочетаний условий» Если число к заранее не известно, целесообразно провести упорядочение объектов по числу выполненных в них условий поиска0 поскольку в против­ ном случае пришлось бы выполнять поиск последовательно по

к„

£Г' отдельным поисковым условиям» 'Так как число /П

г=/77 т

обычно невелико, упорядочение следует выполнять отобразите-

льным методом (одноэтапным). Упорядочение, выполняемое в данном случае, не требует выранения всей правильной после­ довательности, так как его целью является нахождение лишь крайних её элементов.

При поиске с незакреплёнными условиями часть составля­ ющих условий поиска может быть задана жёстко, т .е , может иметь место частичное закрепление составляющих условий по­ иска. Ранжирование условий поиска также является частой причиной усложнения реально используемых условий.

П. Поиск в иерархически организованном множестве строк или в списке строк.

а) Поиск подс трок в строках. Специфика такого поиска состоит в последовательном характере отождествления эле­ ментов, составляющих подстроки. Для сокращения числа актов опознания, имеющих отрицательный исход, обычно дополните­ льно привлекаются некоторые грамматические правила.

б) Поиск в списке строк. Обычно такой поиск выполня­ ется по лексикографическому условию, g , значит, способы выражения условий псиска оказываются, как правило, сложны­ ми.

§ 3. Классификация фундаментальных средств информационного поиска

В неупорядоченном множестве объектов нет другого

- 9 f ~

средства поиска, кроме перебора объектов» Поиск перЗбором

осуществляется путём последовательного сопоставления уп­ равляющих слов записей с заданным поисковым образом. Ин­

формационная ценность каждого сопоставления невелика.

Её можно оценить, воспользовавшись результатами §2 гл.П.

Действительно, и в данном случае множество из П объектов

можно рассматривать как систему, способную находиться в разных состояниях (в зависимости от положения в последо­ вательности искомого объекта; случай нахождения несколь­ ких объектов поиска здесь не рассматривается). Её энтро-

пия - так как всего п состояний, согласно разным положениям искомого объекта. Каждый акт поиска - сопос­

тавление записей - уменьшает неопределённость системы в оилу сокращения множества неопределённости (поиска). Пос­ ле 1 -го акта перебора множеством дальнейшего поиска (и

Низкая информационная ценность их объясняется сугубо не­ равномерным делением множества на подмножества определён­ ности и неопределённости.

Естественным путём ускорения поиска поэтому является