Статья

Название статьи СРАВНЕНИЕ СЛОВ С ЕДИНИЧНОЙ ВРЕМЕННОЙ СЛОЖНОСТЬЮ
Автор Я.Е. Ромм, Д.А. Чабанюк
Рубрика РАЗДЕЛ VI. ВЫЧИСЛИТЕЛЬНЫЕ КОМПЛЕКСЫ НОВОГО ПОКОЛЕНИЯ И НЕЙРОКОМПЬЮТЕРЫ
Месяц, год 07, 2014
Индекс УДК 681.3:007
DOI
Аннотация Излагается способ сравнения слов числового и строкового типа с применением вертикальной обработки. Способ конструируется на основе разрядного распараллеливания алгебраического сложения двоичных чисел и применяется к алгоритмам сортировки, а также слияния строковых элементов в качестве этапа информационного поиска. Представлен исходный метод поразрядно-параллельного сложения без вычисления переноса, его знакоразрядная модификация для поразрядно-параллельного сравнения чисел и строк. Для выполнения алгебраического сложения без вычисления переноса используется обратный двоичный код отрицательных чисел и дана модификация дополнительного кода, исключающая вычисление переноса. При сравнении строковых элементов все символы слова кодируются двоичными числами в ASCII-коде, набор двоичных кодов символов слова интерпретируется как одно двоичное число в позиционной системе счисления. При сравнении путем алгебраического сложения таких чисел они выравниваются по старшему разряду. Включения способа сравнения в параллельные алгоритмы сортировки и слияния увеличивает глубину распараллеливания до параллелизма на уровне операций сравнения слов и одновременно на уровне разрядных операций. Предложен способ выделения знака старшего ненулевого разряда слова, полученного в результате сравнения. Способ включает алгоритмические и схемные решения, обеспечивающие максимальное разрядное распараллеливание. Дополнительно рассматривается проблема вхождения подстроки в строку. Синтезирован алгоритм максимально параллельного поиска вхождения подстроки в строку. Даны оценки временной сложности, в частности максимальный параллелизм поиска вхождения подстроки в строку характеризуется оценкой времени O(1) , независимо от числа символов в строке. Приводятся примеры, алгоритмы и схемы выполнения предложенного метода.

Скачать в PDF

Ключевые слова Поразрядно-параллельное сложение без вычисления переноса; знакоразрядный код; поразрядно-параллельное сравнение чисел и строк; параллельная сортировка и поиск; временная сложность.
Библиографический список 1. Вирт Н. Алгоритмы и структуры данных. – М.: ДМК Пресс, 2010. – 272 с.
2. Кнут Д. Искусство программирования для ЭВМ. Т. З. Сортировка и поиск. – М.: Вильямс, 2007. – 832 с.
3. Ромм Я.Е. Метод вертикальной обработки потока целочисленных групповых данных. I. Групповые арифметические операции // Кибернетика и системный анализ. – 1998. – № 3. – C. 123-151.
4. Ромм Я.Е. Метод вертикальной обработки потока целочисленных групповых данных. II. Приложение к бинарным арифметическим операциям // Кибернетика и системный анализ. – 1998. – № 6. – С. 146-162.
5. Ромм Я.Е., Чабанюк Д.А. Применение метода вертикальной обработки информации к операциям сравнения и поиска. – Таганрог: ТГПИ, 2013. – 32 c. Деп. в ВИНИТИ 20.05.13, № 141 – В 2013.
6. Ромм Я.Е., Иванова А.С. Вертикальное групповое алгебраическое суммирование применительно к сортировке со слиянием и параллельному поиску. – Таганрог: ТГПИ., 2012.
– 44 с. Деп. в ВИНИТИ 03.09.2012, № 362 – В 2012.
7. Ромм Я.Е., Иванова А.С. Вертикальные групповые арифметические операции над целочисленными данными без вычисления переноса // Фундаментальные исследования. – 2012. – № 11 – С. 960-964.
8. Ромм Я.Е., Чабанюк Д.А. Сравнение слов с единичной временной сложностью. – Таганрог: ТГПИ, 2013. – 30 c. Деп. в ВИНИТИ 30.10.13, № 306 – В 2013.
9. Charras C., Lecroq T. Handbook of Exact String Matching Algorithms. – College Publications. – 2004. – 256 p.
10. Иванова А.С. Расширение диапазона данных для вертикальной обработки применительно к сортировке со слиянием и поиску: Автореф. дис. … канд. техн. наук. – Таганрог: ЮФУ, 2013. – 22 с.

Comments are closed.