Комбинаторные задачи информационного поиска

Квант 1979, №12 с. 6-12 Тег MD59

М. Цаленко

Научно-техническая революция, проискодающая сейчас в промышленно развитых странах, тесно связана с появлением и развитием электронных вычислительных машин (ЭВМ). Современные ЭВМ могут выполнять миллионы арифметических действия в секунду. Оdnako ЭВМ вторгают также в такие области человекаской деятельности, в которых нет больших и сложных вычислений и которые вводе бы далек от математики. По-учительным примером служит библиотечное дело. В настоящее время рассказывается, почему ЭВМ начали широко применять в библиотеках и какие интересные и трудные математические задачи возникают при этом.

Что такое информационный поиск?

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

Телерь представляет себе читателья, который прищел в библиотеку, чтобы прочесть какую-нибудь популяриую книгу о решении уравнений в радиках. Он может знать, что этой трудной задачей занимались многие математики и что ее решение связано с именами Абеля и Галуа, одnakо его математическое образование не достаточно для чтения специальной

литературы. Таким образом, появление нашей читателя в библиотеке приводит к так называемому информационному запросу: «НАЙТИ ПОПУЛЯРНУЮ ЛИТЕРАТУРУО РЕШЕНИИ УРАВНЕНИЙ В РАДИКАЛAX», и прежде чем читатель удовлетворит своего любозательность, он должен решить задачу информационного поиска: среди всех хранящихся в библиотеке книг отыскать ту, которая в наиболее степени его удовлетворит. Здесь на помощь ему приходит система каталогов. В тематическом каталоге он найдет раздел, содержащий перечень книг по математике, а внутри него — часть, содержащую перечисление книг по алгебре. И вот среди каталогных карточек этой части нужно выбрать те, которые, указывают на отыскиваемую литерару.

Теперь проведем несколько простых расчетов. Допустим, что на ознакомление с карточкой, расходуется в среднем всего 20 секунд. Это значит, что читатель работает очень быстро: считается, что на выполнение одной арифметической операции целевек траит порядка 10 секунд. Если читатель должен просмотреть 200 карточек, то он потратит около 67 минут только на отбор интересующей его литературы. Этот оборот составляет непроизвольную часть общего процесса поиска интересующих читателей сведений. Сам процесс называют информационным поиском; проведенный расчет показывает, что при информационном поиске с помощью каталогов значительная часть времени траится непродуктивно. Так как читательные самые крупных библиотек в течение одного дня посещают сотни лодей, а их информационные запросы бывают города более сложными, чем в приведенном выше примере, непроизвольные затраты времени при информационном поиске выражаются сотнями и тысячи часов.

Что бы пропллюстрировать сложность информационного поиска, приведем еще одну цифру. Сейчас во всем мире изделия свыше 750 журналов и других периодических изданий, посвященных только вычислительной технике. Это значит, что в течение года на различных языках публикуются десяти тысяч статей, занимающих сотни тысяч печатных страниц, которые относятся только к одной области человекаской деятельности. Однако эта область представляется для специалистов самых различных специальностей: инженероконструкторов, физиков, химиков, математиков, социологов, философов и многих других. Разобраться в нарастящем потоке литературы, найти необходимые сведения, использовать их в своей работе и не повторять уже выполненные работы очень трудно. Системы каталогов оказывается недостаточно, и во многих странах мира создаются специальные институты информации.

ЭВМ и информационный поиск

Замечательной особенность ЭВМ является ее умение «читать» и сравнивать слова, установливавать, одинаковы они или различны. Дело в том, что для написания любого слова русского языка нужно уметь изобраться всего 33 буквы. С другой стороны, ЭВМ легко распознавать последовательности из единиц и нуля. Расмотрим, как это принято, во многих современных вычислительных машинах, все последовательности из единиц и нуля, имеющиеровно во всем членов. Например, сюда войдет также последовательности:

00000000, 01010101, 11110000
(для краткости между членами последовательностей запятая не ставится).

Так как в каждой последовательностировно восемь членов, а любой член равен нулю или единице, общее число рассматриваемых последовательностей равно 2⁸=256. Условимся вместе первых букв а, б, в, 2, д, е русского алфавита писать соответственно последовательности:

10000000, 11000000, 11100000, 11110000, 10100000, 10010000

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

«узнавать» ЭВМ. Наример, слово
беда будет выглядеть так:
1100000 10010000 10100000 10000000

Разумеется, подобный способ записи неудобен для человека, но он позволяет ЭВМ «читать». При этом машина может читать тексты на многохых языках, поскольку 256 последовательностей она может запомнить не только русские буквы, но и цифры, латинские буквы и многое специализные знаки, например знаки арифметических действия.

Наученная человеком читать, машина немедленно обгоняет его по скорости чтения: если человеку нужно 67 минут на прочтение 200 каталожных картокек, то ЭВМ справляется с этой работой за несколько секунд. При чтении машина может сравнивать два текста, установливать наличие в них общих слов или выражений, определять частью повлижения отдельных слов и т. д.

Однако естественные языки (русский, английский, немецкий или любой другой) машина «пониматить» очень трудно: каждую мысль на них можно выразить многоими способами. Поэтому лингвистия разрабатывает искусственные языки, называемые информационно-посковыми, которые свободны от этого недостатка.

Основной частью информации поискственных языков является совокупность понятий, терминов, словосочетаний, которые постоянно используются в конкретной предметной области — в математике, химии, биологии и т. д. Составляя аннотацию книги или реферат научной статьи, можно вместе предложенный естественного языка дать перечисление тех терминов, которые в наиболее степени отражают содержание книги или статьи. То же самое можно сделать и с информационными запросами читателей. Например, в серии «Популярные лекции по математике» была выпущена брошюра А. Г. Куроша «Алгебраические уравнения высших степеней». Ее аннотация могла бы быть записана следующим образом:

Комплексные числа, решение в радиалах уравнения второй и третьей степени, теорема Абе-

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

Аннотация статьи Б. Н. Делоне «Алгебра (теория алгебраических уравнений)», помещенной в первом томе коллективного трехтомного труда «Matematika, ее содержание, методы и значение», может выглядеть так:

Решение в радиалах уравнения низших стеленей, формула Кардно, теорема Абея о неразрешимости в радиалах общего уравнения прямой стелени, теорема Галуа, расположение корней уравнения на комплексной плоскости, основная теорема алгебры, приближение вычисление корней.

Вспомним теперь о читателье, желавшем получить литературу о решении уравнения в радиалах. Его запрос можно описать так:

Решение в радиалах уравнения низших стеленей, теорема Абея о неразрешимости в радиалах общего уравнения прямой стелени.

Сравнение запроса с двумя приведенными выше аннотациями показывает, что почти все встречались в нем словосочетания входят в аннотации. Поэтому с большой вероятностью можно предложить, что брошюра А. Г. Куроша и статьи Б. Н. Делоне содержат интересующие читателя сведения.

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

ЭВМ нужно использовать эффективно

Теперь рассмотрим несколько подробнее выполнение операций в ЭВМ. В каждой современной вычислительной машине имеются четые главы

ные компоненты: центральный процессор, оперативная память, внешняя память и устройство ввода — вывода. Центральный процессор управляет работой всей системы, и в нем совершается арифметические и логические операции, причем на отдельную операцию расходится миллионные доли секунды. Данные (числа, слова), с которых операрует процессор, находятся в оперативной памятии. Она имеет сравнительно небольшой объем, поскольку ее стоимость очень высока.

Напомним, что на запись отдельного символа (буквы, цифры, спецалгоритма знака) уходит восмчленная последовательность единиц и нулей. В оперативной памятии совершенных ЭВМ обычно можно записать 256000 или 512000 таких последовательностей, или знаков. Много это или мало? Как показывает практика, библиографическая карточка вместе с аннотацией содержит 1000—1500 знаков. Следовательно, в оперативной памятии можно в лучшем случае размещить около 500 карточек. Ясно, что это очень мало.

Остальные карточки помещаются во внешней памятии, объем которого в сотни раз больше объема оперативной памятии. Однако на передачу данных уходит времени в тысячу раз большие, чем на работу центрального процессора, который во время передачи подросту просстанавел. Ясно, что передача данных неосредственного отношения к информационному понску не имеет и является неопознавательной тратой времени. Таким образом, возникает задача об уменьшении числа обращений к внешней памятии. Существуют различные подходы к ее решению. Однако из них приводит к красной и трудной математической задаче, о которой и будет расссказано в заключение.

Как уменьшить «вес» множества слов?

Пусть $A$ — какое-то множество из $n$ элементов. Элементы будем обозначать малыми латинскими буквами $a, b, c, \dots$ . Произвольное подмножество элементов из $A$ будем называть «словом» и вместе традиционной записи $\{a, b, c, d\}$ будет писать простой $abcd$ ; размещется, с одинаковым успесом можно написать $bdac$ или $dcab$ и т. д. Слово, в котором нет букв, т. е. пустое слово, рассматривается не будет. Поэтому имеется всего $2^n - 1$ слов.

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

Предположим, что некоторое множество слов $M$ размещено во внешней памятии $EBM$ и что необходимо найти все слова из $M$ , в которых встречаются буквы $a, b$ и $c$ . Чтобы справиться с этой задачей, нужно почередно «прочесть» все слова из $M$ , предварительно переписав их в оперативную память. Если $M$ неведено, то можно сразу все множество $M$ переместить туда. В обшем же случае такое перемещение осуществляется порциями, размер которых заранее определен. Следовательно, число обращений размером $M$ и размером передаваемой порции. Это число можно было бы уменьшить, если бы при помещении слов во внешнюю память слова с буквами $a, b$ и $c$ записьвали отдельно. Однако для задачи: найти все слова с буквами $b, c$ и $d$ — продолжанная работа бесполезна.

Тем не менее предварительно сортировка слов при их записи во внешнюю память оказывается полезной, если имеет в виду не отдельный запрос, а все возможные запросы. Разобъем множества $M$ на части и помещим каждую часть в отдельный конверт, а на конверт перечислим все буквы, встретившиеся в положениях в конверт словах. Теперь при поиске слов с буквами $a, b$ и $c$ начинала обращаться конверты, на которых надписаны эти буквы, а потом прочитываются слова из этих конвертов. Слова по конвертам следует разместить таким образом, чтобы общие число «вскрытый» конвертов для

всех возможных запросов оказалось наиболее простым примером. Пусть множество $M$ состоит всего из трех слов $ab, ac$ и $bc$ , а запросы, которые мы будем делать, должны быть неупустыми подмножествами множества $\{a, b, c\}$ . тогда общее число запросов равно семи. Поместим сначала каждое слово в отдельный конверт. Тогда конверт со словом $ab$ откроется три раза: при поиске слов $a$ , слов $c$ и слов $a$ и $b$ . Так как все конверты равновыны, то общее число вскрытый равно 9. Тепер поместим слова $ab$ и $ac$ в один конверт, а слово $bc$ в другой. В этом случае первый конверт придает открытый семь раз, а второй по-прежнему три раза, и общее число вскрытый равно 10.

Наконец, поместим все слова в один конверт. Тогда общее число вскрытый равно 7: при каждом запросе надо открыть конверт, а всего запросов 7. Таким образом, в нашем примере лучше всего держать $M$ в одном конверте. (Изменится ли результат, если к $M$ добавить слова $a$ и $abc$ или удалить из $M$ слова $bc$ ?)

Тепер мы готовы к рассмотрению общей задачи. Пусть $M$ — произвольное множество слов. Число $k$ различных букв, встречающихся в словах из $M$ , называется уровень множества $M$ и обозначается $l(M)$ . Например, если

$M = \{abc, bcd, cde, dea, eab\},$

(1) то уровень $M$ равен 5.

Весом множество $M$ называется число $2^l(M) - 1$ . В приведенном выше примере все $M$ равен 31. Ясно, что все $M$ равен числу слов, которые можно составить из $l(M)$ букв.

Задучу, которая возникает при попытках уменьшить число обращений к внешней памятии ЭВМ, можно формировать так: для любого множества слов $M$ указыва метод его разбиения на такие непересекающие подмножества $S_1, S_2, \dots, S_k$ , что сумма весов

$P = (2^l(S_1) - 1) + \dots + (2^l(S_k) - 1) = \sum_{i=1}^{k} (2^l(S_i) - 1)$

является наименьшей.

ными экземплярами одного и того же минимального блока. В дальнейшем такие блоки для нас равноправны.

Докажем теперь одну из теорем, дающих представление об устройстве минимальных блоков.

Теорема. Minimalные блоки уровня 5, состоящие из трехбуквенных слов, с точностью до замены букв исчерпываются следующим списком:

$S_1 = \{abc, bcd, cde, dea, eab\};$
$S_2 = \{abc, abd, abe, acd, ace, ade\};$
$S_3 = \{abc, abd, abe, acd, ace, bde\}.$

Доказательство. Каждое трехбуквенное слово имеет вес $2^3 - 1 = 7$ . Все любого множества уровня 5 равен 31. Поэтому в любой блоку уровня 5 входит не менее пяты слов: в противном случае сумма весов отдельных слов была бы меньше 31.

Далее, в любом блоке уровня 5 каждая буква должна встречаться не менее трех раз. В самом деле, пусты буква $a$ встречается менее трех раз. тогда все множества слов, в которых нет $a$ , не превозходит 15, а сумма весов слов $a$ не превозходит 14. Значит, общая сумма весов меньше 29, что противоречит определению блока.

Теперь рассмотрим два случая.

Случай 1. Minimalный блок $S$ содержит пять слов. Так как число всех букв в $S$ равно 15, в силу предыдущего замечания каждая буква встречаетсяровно три раза. Введем для наглядности расчёкдений квадратную таблицу размена $5 \times 5$ , в первом столбце которого будет записья буква $a$ , во втором — $b$ и т. д. (см. таблицы 1a—1b).

Предположим, что какая-то пара букв, например $a$ и $b$ , встречается только один раз. Тогда возникает ситuação, изобравенная на таблице 1a. Обозначим через $c$ ту букву, которая входит в первое слово. Эта буква обязана встретиться еще по разу с $a$ и $b$ : если она еще два раза встретилась с $a$ , то в двух последних строках таблицы стояло бы одно и то же слово, что невозможно. Поэтому от таблицы 1a мы переходим к таблице 16.

Ясно, что в третью и пятую строки таблицы нужно поставить слова ade и bde. Но тогда во вторую строку следует поместить $d$ (или $e$ ), а в четвертую — $e$ (или $d$ ); ввиду симметрины между $a$ и $b$ на таблице 16 обе возможности равноправны. Таблица 1в дает возможность кандидата в минимальный блок. Построенное множество слов $S$ действительное является минимальным блоком, поскольку любое его подмножество из трех слов имеет вес 31. Оно переходит в $S_1$ , если $d$ заменить на $e$ , $e$ на $a$ и $a$ на $d$ .

Никакая пара букв не может встретиться три раза, так как не хватит букв для пятого слова; поэтому остается предположить, что каждая пара букв встретиется дважды. Однако и этот вариант невозможен: буквы $a$ , $b$ и $c$ можно разместить только так, как показано на таблице 2, и для последнего слова недостаочно букв.

Случай 2. В минимальном блоке $S$ шесть слов. Тогда в словах

Табл. 2.

из $S$ встреется всего 18 букв. Число 18 можно следующего способами представить в виде суммы пяты слагаемых, каждое из которых равно 3, 4, 5 или 6:
a) $18=6+3+3+3+3$ ;
b) $18=5+4+3+3+3$ ;
c) $18=4+4+4+3+3$ .

При способе a) одна буква, например $a$ , встреется шесть раз. Поэтому $S$ совпадает с $S_2$ ; предполагаем читатель самостояльно доказать, что $S_2$ — минимальный блок.

Перейдем к способу 6). Пусть для определенности путь раз встреется буква $a$ , четыре раза—буква $b$ . тогда сразу получаем таблицу 3a. В четырёх и пятой строках какая-то из букв: $c$ , $d$ или $e$ — появляется дважды; обозначим ее через $c$ . В шестой строке может стоять только слово $bde$ , и в результате мы приходим к таблице 36.

Табл. 3a. Табл. 36.

Для доказательства того, что построенное множество слов $S_3$ является блоком, достаточно заметить, что в $S$ любое подмножество уровня 4 содержит не больше трех слов, а остальные слова образуют подмножество уровня 5 и потому сумма весов не может быть меньше $36=15+7\times 3$ , а вес $S$ равен 31. Minimalность следует из того, что, какое бы слова ни удалить, в оставшихся словах буква $a$ встреется не менее четырех раз, чего не может быть в блоках уровня 5 из пятых слов в силу первого случая.

Переходим к способу b). Пусть буквы $a$ , $b$ и $c$ встреются по четыре раза. тогда либо какая-то пара этих букв встреется три раза, либо любая пара встреетсяровно два раза. В соответствии с этим мы приходим к таблицам 4a и 46 (с точностью до переменования букв).

Первое построение множество является блоком, но неминimalным: после удаления из него слова $abc$ получится блок типа $S_1$ . Второе множество вообще не является блоком, так как оно является объединением своих подмножества {abd, acd, bcd} и {abe, ace, bce} уровня 4, и для этого разбиения сумма весов равна $30<31$ .

Теперь остается доказать, что других минимальных блоков уровня 5 из трех буквенных слов не существует. Если в множество $S$ девять или десять слов, то хотя бы одна буква встреется шесть раз, и потому в $S$ содержится блок типа $S_2$ . Значит, $S$ — всегда минимальный блок.

Если в $S$ семь или восемь слов и ни одна буква не встреется шесть раз, то всегда найдется такая пара букв, скажем $a$ и $b$ , что $a$ встреется пяты раз, $b$ — не менее четырех раз, а пара $a$ , $b$ встреется три раза (проверьте!). Поэтому считать (убедитесь в этом!), что в $S$ входят следующие пять слов: $abc$ , $abd$ , $abe$ , $acd$ , $ace$ . К ним надо добавить не менее двух слов из следующих четырех: $bcd$ , $bce$ , $bde$ , $cde$ . Если добавится одно из слов $bde$ или $cde$ , то в $S$ попадет минимальный блок типа $S_3$ . Если же добавится слова $bcd$ и $bce$ , то в словах из $S$ вообще не встреется пара букв $d$ и $e$ , чего не может быть в блоке (см. ниже задачу 3).

Задание 1.

Описать все минимальные блоки уровня 5 из двух буквенных слов.
Множество $S'$ получено из множества $S$ приписыванием к ним новейшей буквы. Доказать, что если $S$ — минимальный блок, то и $S'$ — минимальный блок.
Если в словах блока $S$ встреется буквы $a$ и $b$ , то в $S$ найдется слово, содержащей $a$ и $b$ .

4.**. Описать все минимальные блоки уровней 6 и 7 из трех буквенных слов.
5*. Доказать, что не существует блоков уровня 8 из трех буквенных слов.