Cтраница 1
Таблица разделителей составляется заранее, исходя из предполагаемого объема словаря и данных о распределении длин его элементов. [1]
Процедура выборки из таблицы разделителей начального номера слова, соответствующего сочетанию признаков длина слова и код первой буквы, включает определение участка таблицы разделителей, где этот номер. [2]
В этом случае отпадает необходимость хранить коды признаков в таблице разделителей. Достаточно иметь таблицу начальных адресов участков массива чисел, соответствующих этим кодам. [3]
Если в одной ячейке памяти записывается по три номера слова, то под таблицу разделителей необходимо отвести около трехсот ячеек. При этом для каждого сочетания признаков длина слова и код первой буквы отводится место под начальный номер группы слов независимо от того, имеются ли в действительности в словаре слова, обладающие этими признаками. [4]
Процедура выборки из таблицы разделителей начального номера слова, соответствующего сочетанию признаков длина слова и код первой буквы, включает определение участка таблицы разделителей, где этот номер. [5]
Процесс составления словаря продолжается до тех пор, пока не будет просмотрен весь исходный текст или пока не переполнится один из участков словаря. В последнем случае участки словаря перемещаются, а таблица разделителей корректируется, чтобы образовать резервы памяти, необходимые для обработки всего текста. [6]
При поиске сначала по заданному коду числа определяется значение соответствующего ему признака. Затем полученное значение признака сравнивается последовательно со значениями этого признака, перечисленными в таблице разделителей, и в случае совпадения из таблицы выбирается начальный адрес участка. Далее адрес искомого числа находится последовательным просмотром списка кодов чисел на выделенном участке. Для каждого участка списка чисел, заключенного между двумя разделителями, может быть составлена своя таблица разделителей - разделителей второй ступени. [7]
Существо этого способа состоит в том, что здесь в качестве разделительных признаков используются так называемые свертки кодов. Свертки могут быть получены с помощью различных операций над исходными кодами: путем выделения какой-либо части кода ( начальной, средней или конечной); путем выделения п объединения элементов кода. Свертки могут быть использованы в качестве адресов для обращения к таблице разделителей. [8]
Скорость поиска методом свертывания кодов зависит от различных факторов, и в первую очередь от длины кода свертки, от равномерности разбиения массива исходных кодов на участки и от сложности процедуры получения свертки. С увеличением длины кода свертки уменьшаются размеры участков, на которых поиск ведется последовательным просмотром. Следовательно, увеличивается скорость поиска. С другой стороны, увеличение длины кода свертки ведет к росту объема таблицы разделителей, что не всегда желательно. [9]
При поиске сначала по заданному коду числа определяется значение соответствующего ему признака. Затем полученное значение признака сравнивается последовательно со значениями этого признака, перечисленными в таблице разделителей, и в случае совпадения из таблицы выбирается начальный адрес участка. Далее адрес искомого числа находится последовательным просмотром списка кодов чисел на выделенном участке. Для каждого участка списка чисел, заключенного между двумя разделителями, может быть составлена своя таблица разделителей - разделителей второй ступени. [10]