Cтраница 1
Цифровой поиск отличается в важном отношении от всех других методов, описанных в этой главе: для данного множества имен существует только одно дерево цифрового поиска; таким образом, нет вопроса о построении оптимального дерева. Любой статистический анализ среднего времени поиска зависит только от допущений о содержимом таблицы. Для методов, в которых мы рассматриваем сравнение имен как элементарную операцию, любое множество п имен ведет себя так же, как и любое другое ( в предположении, что все перестановки этого множества равновероятны; см. разд. В деревьях цифрового поиска различные множества имен приводят к борам разного вида и, в частности, длины имен оказывают важное влияние на время поиска и память, необходимую для боров. Анализ и эксперименты только подтверждают естественное заключение о том, что в таблице с п именами над алфавитом из с символов поиск требует в среднем приблизительно logcn шагов с с исходами на каждом шаге. [1]
Дерево цифрового поиска для шести имен. [2]
Дерево цифрового поиска можно представить в ЭВМ многими способами, но для эффективной реализации представление должно позволять одновременное сравнение символа в имени с пометками всех ветвей, выходящих из узла. Разбиением слова на составляющие его буквы ничего не достигается, если эти сравнения осуществляются путем поочередного просмотра всех выходящих из узла ветвей; такой метод был бы почти наверняка медленнее бинарного поиска, который сравнивает два имени целиком в одной элементарной операции. [3]
Методы цифрового поиска заменяют сравнение между двумя именами последовательностью сравнений между символами в их представлениях. Так как на каждый символ представления требуется только по одному такому сравнению, то время поиска пропорционально ( средней) длине имен. [4]
Коэффициент пропорциональности зависит от многих факторов, но на практике цифровой поиск обычно осуществляется быстрее бинарного, так как многопутевое разветвление от одного символа ( для алфавита с с буквами это обычно с-путевое разветвление) в основном не длиннее, чем двухпутевое разветвление при сравнении двух имен. В этом отношении цифровой поиск аналогичен одновременно сильно ветвящимся деревьям из разд. Цифровой поиск аналогичен методам вычисления адреса и в том отношении, что имеет тенденцию к неэффективному использованию памяти - как правило, таблица включает поле для многих несуществующих имен. [5]
Цифровой поиск отличается в важном отношении от всех других методов, описанных в этой главе: для данного множества имен существует только одно дерево цифрового поиска; таким образом, нет вопроса о построении оптимального дерева. Любой статистический анализ среднего времени поиска зависит только от допущений о содержимом таблицы. Для методов, в которых мы рассматриваем сравнение имен как элементарную операцию, любое множество п имен ведет себя так же, как и любое другое ( в предположении, что все перестановки этого множества равновероятны; см. разд. В деревьях цифрового поиска различные множества имен приводят к борам разного вида и, в частности, длины имен оказывают важное влияние на время поиска и память, необходимую для боров. Анализ и эксперименты только подтверждают естественное заключение о том, что в таблице с п именами над алфавитом из с символов поиск требует в среднем приблизительно logcn шагов с с исходами на каждом шаге. [6]
Включение и исключение в бору прямые ( упр. Цифровой поиск обсуждался в связи со статическими таблицами, поскольку у него нет характерного свойства, излагаемых в разд. [7]
Коэффициент пропорциональности зависит от многих факторов, но на практике цифровой поиск обычно осуществляется быстрее бинарного, так как многопутевое разветвление от одного символа ( для алфавита с с буквами это обычно с-путевое разветвление) в основном не длиннее, чем двухпутевое разветвление при сравнении двух имен. В этом отношении цифровой поиск аналогичен одновременно сильно ветвящимся деревьям из разд. Цифровой поиск аналогичен методам вычисления адреса и в том отношении, что имеет тенденцию к неэффективному использованию памяти - как правило, таблица включает поле для многих несуществующих имен. [8]
Пример из рис. 6.9 отличается тем, что ни одно из имен в таблице не является префиксом другого имени. Для многих приложений это нехарактерно, и поэтому мы представляем два метода, с помощью которых можно конструировать деревья цифрового поиска для имен, которые являются префиксами других имен в таблице. Первый метод состоит в том, чтобы добавить разряд конец имени к каждому узлу дерева, отмечая таким способом конец слова в этом узле. Второй метод состоит в том, чтобы слегка модифицировать имена таким образом, чтобы ни одно имя не могло быть префиксом другого. [9]
Алгоритмы поиска ( Часть 4), предназначенные для поиска конкретных элементов в больших коллекциях элементов, также имеют важное значение. Мы рассмотрим основные и расширенные методы поиска с использованием деревьев и преобразований численных ключей, в том числе деревья бинарного поиска, сбалансированные деревья, хеширование, деревья цифрового поиска и методы, которые подходят для очень больших файлов. Мы отметим взаимосвязь между этими методами, приведем статистические данные о их сравнительной производительности и установим соответствие с методами сортировки. [10]
Коэффициент пропорциональности зависит от многих факторов, но на практике цифровой поиск обычно осуществляется быстрее бинарного, так как многопутевое разветвление от одного символа ( для алфавита с с буквами это обычно с-путевое разветвление) в основном не длиннее, чем двухпутевое разветвление при сравнении двух имен. В этом отношении цифровой поиск аналогичен одновременно сильно ветвящимся деревьям из разд. Цифровой поиск аналогичен методам вычисления адреса и в том отношении, что имеет тенденцию к неэффективному использованию памяти - как правило, таблица включает поле для многих несуществующих имен. [11]
Цифровой поиск отличается в важном отношении от всех других методов, описанных в этой главе: для данного множества имен существует только одно дерево цифрового поиска; таким образом, нет вопроса о построении оптимального дерева. Любой статистический анализ среднего времени поиска зависит только от допущений о содержимом таблицы. Для методов, в которых мы рассматриваем сравнение имен как элементарную операцию, любое множество п имен ведет себя так же, как и любое другое ( в предположении, что все перестановки этого множества равновероятны; см. разд. В деревьях цифрового поиска различные множества имен приводят к борам разного вида и, в частности, длины имен оказывают важное влияние на время поиска и память, необходимую для боров. Анализ и эксперименты только подтверждают естественное заключение о том, что в таблице с п именами над алфавитом из с символов поиск требует в среднем приблизительно logcn шагов с с исходами на каждом шаге. [12]