Cтраница 3
Рис, 27.9. Инвертированные списки ( представленные битовыми строками, Эта организация файла подобна тойв которая представлена на рис. 27.7, Исключением здесь является то, что битовая строка используется для индикации содержимого участка. Использование битовой строки приводит к более компактному индексу по сравнению с рис. 27.7. Однако это не всегда так. Экономичность этого способа ( по сравнению с предыдущим) зависит от общего числа участков записей и от доли тех участков, в которых присутствуют значения всех вторичных ключей ( рис. 18.9), Использование индекса в виде совокупности битовых строк отличается тем, что в этом случае сортировка и разбиение записей данных на связанные множества ( рис. 27.8) не дает выигрыша в использовании памяти, но уменьшает число участков записей, которые необходимо просматривать при ответе на конкретный запрос. [31]
Они образуют связанное множество определяющих пучков. Очевидно, что в плане D никакие три фактора не имеют всех своих комбинаций. Это эквивалентно тому, что найдется определяющий пучок с любой нулевой координатой. Имеется четыре связанных множества неопределяющих пучков, каждое из которых содержит по 9 пучков. [32]
Нельзя, однако, предположив, что любые три эффекта равны нулю, получить невырожденную матрицу порядка пять и, таким образом, оценить оставшиеся эффекты. Легко видеть, что невырожденная матрица получится тогда и только тогда, когда будут вычеркнуты три столбца и три строки любых трех из имеющихся четырех пар. План делит все эффекты на связанные пары. В каждом связанном множестве для плана D2 находятся четыре такие пары. Если же имеется хотя бы две пары, в которых ни один эффект не равен нулю, то эффекты не могут быть оценены, независимо от того, сколько ненулевых эффектов осталось. [33]
Мы не можем, однако, предположив, что любые три из эффектов незначительны, получить невырожденную матрицу порядка пять и, таким образом, оценить оставшиеся эффекты. Легко увидеть, что невырожденная матрица может быть получена тогда и только тогда, когда мы вычеркнем три столбца ( и три строки) из любых трех из имеющихся четырех пар. Полуреплика делит все эффекты ( в том числе и эффекты, находящиеся в связанном множестве относительно 1 / 8-реплики) на связанные пары. В каждом связанном множестве относительно 1 / 8-реплики находятся четыре такие пары. [34]
В этом случае будем говорить, что контраст в Ш порождает в D. В этом случае порождает в D вектор I. Очевидно, что вектор I порождают те и только те контрасты % f, которые соответствуют определяющим пучкам нлана D. Относительно определяющих пучков D также будем говорить, что они находятся в одном связанном множестве. [35]
Образцы являются важным типом данных в Сноболе 4 благодаря той ключевой роли, которую играет операция сопоставления с образцом. Любая операция сопоставления с образцом управляется структурой данных типа образец. Программа, реализующая сопоставление, декодирует и интерпретирует образец, одновременно выполняя поиск соответствующей цепочки литер, указанной образцом. Детально образцы рассматриваются в следующем разделе, где мы разбираем операцию сопоставления саму по себе. Наличие образцов, как явных типов структур данных, означает, что образцы могут быть значениями переменных, элементов массивов и элементов таблиц. Во время выполнения образец представляется во внутренней форме, удобной для эффективной его интепретации программой сопоставления; обычно такой формой является связанное множество областей памяти, образующее древовидную структуру, которая отражает естественную структуру образца как набора альтернатив и конкатенации подобразцов. [36]