Категории: ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника |
Организация информационных массивов.
· Запись информации по полям (наименование единицы данных – поле) · Запись – поименованная совокупность полей. · Файл – поименованная совокупность экземпляров записей одного типа · Набор файлов Схема записи – совокупность имени записи и имён, составляющих её поля. В основе различных схем БД лежат различные (конкретные) схемы файлов, записей, связей между ними. Прямая запись (записи в массиве упорядочены по какому-либо идентификатору – по вертикали, по горизонтали – дескрипторы, участвующие в ПОДах) и инверсная (в качестве исходной записи выступают дескрипторы, в клетках – номера документов, в которые входит этот дескриптор). В чистом виде ни прямая, ни инверсная схемы не используются, чаще используют комбинированную схему, где один файл построен по прямой, а другой – по инверсной схеме. Стратегии поиска. Стратегия поиска – задача, которая требует ответа на вопросы «как наиболее эффективно провести поиск, потратив наименьшее количество времени, учитывая ограничения программных средств». Это организация, подготовка, использование материальных ресурсов для достижения поставленной цели в отведённое на поиск время. 4 стратегии. 1. Поиск прямого просмотра – последовательный просмотр записи за записью. 2. Модифицированный поиск – при последовательном просмотре границы поискового поля огромны. Существуют критерии для его сокращения, например, тематический (поставить новые тематические границы). Производятся предварительные группировки документов в массиве. Центроид описывает самую главную тему каждой группы. Каждый запрос сравнивается с центроидами. Следующий шаг (если запрос близок по смыслу) – работа с конкретным пучком документов. Если этот пучок маленький, то можно просмотреть прямым просмотром, если нет, то можно строить центроиды второго, третьего и т.д. порядка. 3. Итеративный поиск – Ряд повторных операций одноуровнего поиска с очередным совершенствованием поискового предписания. 2 вида: 1. предпоисковый диалог. Формулировка запроса, запуск в систему, которая даёт возможность переформулировать, исправить запрос (вручную). Переформулировку запроса ведёт пользователь. 2. переформулировку запроса делает система, а от пользователя требуется указать степень релевантности выданных документов. 4. Адаптивный поиск - Многоуровневый поиск, который осуществляется итеративно.
ЭЛЕМЕНТЫ ТЕОРИИ Введение. В этом разделе изложены некоторые аспекты теории формальных языков, существенные с точки зрения трансляции. Здесь введены базовые понятия и даны определения, связанные с одним из основных механизмов определения языков - грамматиками, приведена наиболее распространенная классификация грамматик (по Хомскому). Особое внимание уделяется контекстно-свободным грамматикам и, в частности, их важному подклассу - регулярным грамматикам. Грамматики этих классов широко используются при трансляции языков программирования. Здесь не приводятся доказательства сформулированных фактов, свойств, теорем, доказательства правильности алгоритмов; их можно найти в книгах, указанных в списке литературы.
Основные понятия и определения Определение: алфавит - это конечное множество символов. Предполагается, что термин "символ" имеет достаточно ясный интуитивный смысл и не нуждается в дальнейшем уточнении.
Определение:цепочкой символов в алфавите V называется любая конечная последовательность символов этого алфавита.
Определение: цепочка, которая не содержит ни одного символа, называется пустой цепочкой. Для ее обозначения будем использовать символ e.
Более формально цепочка символов в алфавите V определяется следующим образом: (1) e - цепочка в алфавите V; (2) если a - цепочка в алфавите V и a - символ этого алфавита, то aa - цепочка в алфавите V; (3) b - цепочка в алфавите V тогда и только тогда, когда она является таковой в силу (1) и (2).
Определение: если a и b - цепочки, то цепочка ab называется конкатенацией (или сцеплением) цепочек a и b. Например, если a = ab и b = cd, то ab = abcd. Для любой цепочки a всегда ae = ea = a.
Определение: обращением (или реверсом) цепочки a называется цепочка, символы которой записаны в обратном порядке. Обращение цепочки a будем обозначать aR. Например, если a = abcdef, то aR = fedcba. Для пустой цепочки: e = eR.
Определение:n-ой степенью цепочки a (будем обозначать an) называется конкатенация n цепочек a. a0 = e; an = aan-1 = an-1a.
Определение: длина цепочки - это число составляющих ее символов. Например, если a = abcdefg, то длина a равна 7. Длину цепочки a будем обозначать | a |. Длина e равна 0.
Определение: язык в алфавите V - это подмножество цепочек конечной длины в этом алфавите.
Определение: обозначим через V* множество, содержащее все цепочки конечной длины в алфавите V, включая пустую цепочку e. Например, если V={0,1}, то V* = {e, 0, 1, 00, 11, 01, 10, 000, 001, 011, ...}.
Определение: обозначим через V+ множество, содержащее все цепочки конечной длины в алфавите V, исключая пустую цепочку e. Следовательно, V* = V+ È {e}.
Ясно, что каждый язык в алфавите V является подмножеством множества V*.
Известно несколько различных способов описания языков [3]. Один из них использует порождающие грамматики. Именно этот способ описания языков чаще всего будет использоваться нами в дальнейшем.
Определение: декартовым произведением A ´ B множеств A и B называется множество { (a,b) | a Î A, b Î B}.
Определение: порождающая грамматика G - это четверка (VT, VN, P, S), где VT - алфавит терминальных символов ( терминалов ), VN - алфавит нетерминальных символов (нетерминалов), не пересекаю- P - конечное подмножество множества (VT È VN)+ ´ (VT È VN)*; элемент (a, b) множества P называется правилом вывода и записывается в виде a ® b, S - начальный символ (цель) грамматики, S Î VN.
Для записи правил вывода с одинаковыми левыми частями a ® b1 a ® b2 ... a ® bn будем пользоваться сокращенной записью a ® b1 | b2 |...| bn. Каждое bi , i = 1, 2, ... ,n , будем называть альтернативой правила вывода из цепочки a.
Пример грамматики: G1 = ({0,1}, {A,S}, P, S), где P состоит из правил S ® 0A1 0A ® 00A1 A ® e
Определение: цепочка b Î (VT È VN)* непосредственно выводима из цепочки a Î (VT È VN)+ в грамматике G = (VT, VN, P, S) (обозначим a ® b), если a = x1gx2, b = x1dx2, где x1, x2, d Î (VT È VN)*, g Î (VT È VN)+ и правило вывода Например, цепочка 00A11 непосредственно выводима из 0A1 в грамматике G1.
Определение: цепочка b Î (VT È VN)* выводима из цепочки
Определение: последовательность g0, g1, ... , gn называется выводом длины n.
Например, S Þ 000A111 в грамматике G1 (см. пример выше), т.к. существует вывод S ® 0A1 ® 00A11 ® 000A111. Длина вывода равна 3.
Определение: языком, порождаемым грамматикой G = (VT, VN, P, S), называется множество L(G) = {a Î VT* | S Þ a}. Другими словами, L(G) - это все цепочки в алфавите VT, которые выводимы из S с помощью P. Например, L(G1) = {0n1n | n>0}.
Определение: цепочка a Î (VT È VN)*, для которой S Þ a, называется сентенциальной формой в грамматике G = (VT, VN, P, S).
Таким образом, язык, порождаемый грамматикой, можно определить как множество терминальных сентенциальных форм.
Определение: грамматики G1 и G2 называются эквивалентными, если Например, G1 = ({0,1}, {A,S}, P1, S) и G2 = ({0,1}, {S}, P2, S) P1: S ® 0A1 P2: S ® 0S1 | 01 0A ® 00A1 A ® e эквивалентны, т.к. обе порождают язык L(G1) = L(G2) = {0n1n | n>0}.
Определение: грамматики G1 и G2 почти эквивалентны, если Другими словами, грамматики почти эквивалентны, если языки, ими порождаемые, отличаются не более, чем на e.
Например, G1 = ({0,1}, {A,S}, P1, S) и G2 = ({0,1}, {S}, P2, S) P1: S ® 0A1 P2: S ® 0S1 | e 0A ® 00A1 A ® e почти эквивалентны, т.к. L(G1)={0n1n | n>0}, а L(G2)={0n1n | n>=0}, т.е. L(G2) состоит из всех цепочек языка L(G1) и пустой цепочки, которая в L(G1) не входит. |
|
Последнее изменение этой страницы: 2016-08-11 lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда... |