Таблица разделителей

В качестве признаков, по которым группируются элементы списка, может использоваться длина кодов чисел, начальная часть этих кодов п т. п. При поиске сначала по заданному коду числа определяется значение соответствующего ему признака. Затем полученное значение признака сравнивается последовательно со значениями этого признака, перечисленными в таблице разделителей, и в случае совпадения из таблицы выбирается начальный адрес участка. Далее адрес искомого числа находится последовательным просмотром списка кодов чисел на выделенном участке. Для каждого участка списка чисел, заключенного между двумя разделителями, может быть составлена своя таблица разделителей — разделителей второй ступени. Аналогичным образом может быть 76 [c.76]

Особый интерес представляет такая структура таблицы разделителей, когда по коду искомого числа можно достаточно просто определить место записи (адрес) соответствующего ему разделителя. В этом случае отпадает необходимость хранить коды признаков в таблице разделителей. Достаточно иметь таблицу начальных адресов участков массива чисел, соответствующих этим кодам. [c.77]

Разновидностью способа разделителей является метод свертывания кодов (другое его название — метод сжатия ко д о в [83]). Существо этого способа состоит в том, что здесь в качестве разделительных признаков используются так называемые свертки кодов. Свертки могут быть получены с помощью различных операций над исходными кодами путем выделения какой-либо части кода (начальной, средней или конечной) путем выделения и объединения элементов кода, стоящих на определенных позициях путем деления кода на части фиксированной длины и последующего арифметического сложения этих частей с предварительным сдвигом 5х относительно друг друга или без сдвига и т. п. Обычно свертка имеет значительно меньшую длину, чем длина исходного кода (отсюда название свертка ). Свертки могут быть использованы в качестве адресов для обращения к таблице разделителей. Примеры сверток приведены в табл. 5.1. [c.77]

Скорость поиска методом свертывания кодов зависит от различных факторов, и в первую очередь от длины кода свертки, от равномерности разбиения массива исходных кодов на участки и от сложности процедуры получения свертки. С увеличением длины кода свертки уменьшаются размеры участков, на которых поиск ведется последовательным просмотром. Следовательно, увели-чивается скорость поиска. С другой стороны, увеличение длины кода свертки ведет к росту объема таблицы разделителей, что не всегда желательно. Приближенно длина кода свертки может быть определена по формуле [c.77]

При прямом поиске в словаре длина буквенного кода слова, выраженная в количестве ячеек, используется для обращения к таблице разделителей и определения начального адреса участка словаря, а поиск в пределах найденного участка производится способом деления пополам . При обратном поиске адрес буквенного кода слова вычисляется по формуле [c.89]

Фор.ш запаса двумерной таблицы разделителей в памяти ЭВМ для п = 3 [c.91]

Процедура выборки из таблицы разделителей начального номера слова, соответствующего сочетанию признаков длина слова и код первой буквы , включает определение участка таблицы разделителей, где этот номер, записан, выбор ячейки на участке и выбор нужной позиции в ячейке. [c.92]

Участок таблицы разделителей определяется по формуле [c.92]

Таким образом, в таблице разделителей, особенно в той ее части, которая относится к длинным словам, оказывается значительное количество пустых клеток. [c.92]

Число пустых клеток можно сократить, если двумерную таблицу разделителей построить только для основной массы более коротких слов словаря, а для длинных слов использовать небольшую одномерную таблицу, 92 [c.92]

Таблица разделителей составляется заранее, исходя из предполагаемого объема словаря и данных о распределении длин его элементов. Объем словаря и распреде- [c.197]

Буквенные коды слов имеют различную длину и в зависимости от типа используемой ЭВМ могут быть записаны в одной или нескольких ячейках памяти. Учитывая это обстоятельство, можно объединить слова в группы с одинаковой ячеечностью г, а в пределах каждой группы расположить по алфавиту. Границы групп кодов слов можно отобразить в специальной таблице разделителей, указав в ней для каждого i соответствующие ему начальный адрес Ло группы и начальный номер No слова в группе. [c.89]

Скорость попска в словаре может быть значительно увеличена, если увеличить объем таблицы разделителей и тем самым повысить ее разрешающую способность. Можно, например, расположить все слова по возрастанию их длины сначала группу однобуквенных слов, затем двухбуквенных, за ними трехбуквенных и т. д., а в пределах каждой группы упорядочить слова по алфавиту. В качестве разделительных признаков можно взять длину слова, выраженную в количестве букв, и код первой буквы. [c.89]

Конкретный вид алгоритма составления словаря зависит от ирниятото порядка расположения его элементов и от способа поиска в нем. Можно, например, упорядочить элементы словаря по их длине, а в пределах Г)руппы элементов одинаковой длины — по возрастанию кодов. Тогда нужный участок словаря можно искать по таблице разделителей, а поиск на участке —способом деления пополам . [c.197]

Группи ров1ка элементов словаря по длине удобна при организации поиока в нем и включении в него новых элементов, так как порядок выполнения обеих процедур зависит от ячеечности словоформ и основ слов. Перед включением в словарь нового элемента для лего подготавливается место все коды, превосходящие по величине код нового элемента, перемещаются в сторону резерва. Одновременно в таблице разделителей корректируется объем заполненной части обрабатываемого участка словаря. . [c.198]

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

Справочник химика 21

Химия и химическая технология