Сравнение слов с единичной временной сложностью

Раздел VI. Вычислительные комплексы нового поколения и нейрокомпьютеры

УДК 681.3:007

Я.Е. Ромм, Д.А. Чабанюк СРАВНЕНИЕ СЛОВ С ЕДИНИЧНОЙ ВРЕМЕННОЙ СЛОЖНОСТЬЮ

Излагается способ сравнения слов числового и строкового типа с применением вертикальной обработки. Способ конструируется на основе разрядного распараллеливания алгебраического сложения двоичных чисел и применяется к алгоритмам сортировки, а также слияния строковых элементов в качестве этапа информационного поиска. Представлен исходный метод поразрядно-параллельного сложения без вычисления переноса, его знакоразрядная модификация для поразрядно-параллельного сравнения чисел и строк. Для выполнения алгебраического сложения без вычисления переноса используется обратный двоичный код отрицательных чисел и дана модификация дополнительного кода, исключающая вычисление переноса. При сравнении строковых элементов все символы слова кодируются двоичными числами в ASCII-коде, набор двоичных кодов символов слова интерпретируется как одно двоичное число в позиционной системе счисления. При сравнении путем алгебраического сложения таких чисел они выравниваются по старшему разряду. Включения способа сравнения в параллельные алгоритмы сортировки и слияния увеличивает глубину распараллеливания до параллелизма на уровне операций сравнения слов и одновременно на уровне разрядных операций. Предложен способ выделения знака старшего ненулевого разряда слова, полученного в результате сравнения. Способ включает алгоритмические и схемные решения, обеспечивающие максимальное разрядное распараллеливание. Дополнительно рассматривается проблема вхождения подстроки в строку. Синтезирован алгоритм максимально параллельного поиска вхождения подстроки в строку. Даны оценки временной сложности, в частности максимальный параллелизм поиска вхождения подстроки в строку характеризуется оценкой времени 0(1), независимо от числа символов в строке. Приводятся примеры, алгоритмы и схемы выполнения предложенного метода.

Поразрядно-параллельное сложение без вычисления переноса; знакоразрядный код; поразрядно-параллельное сравнение чисел и строк; параллельная сортировка и поиск; временная сложность.

Ya.E. Romm, D.A. Chabanyuk COMPARISON OF WORDS WITH THE COMPLEXITY OF IDENTITY

Was described method of comparing words numeric and string type using the vertical processing. The method is constructed on the basis of the discharge parallelization of algebraic addition of binary numbers and applied to sorting algorithms, as well as the merger of strings as an information search step. Presented by the original method was bit by bit parallel addition without calculating transfer in bit code of the sign modification for by bit parallel comparison of numbers and strings. To perform algebraic addition without calculating a reverse transfer binary negative numbers and given additional code modification, eliminating the calculation of transfer. When comparing string elements all word characters encoded binary numbers in ASCII-code set of binary characters per word is interpreted as a binary number in a positional number system. When comparing by algebraic addition of the numbers they are aligned to the senior class. Inclusion in the method of comparing parallel algorithms for sorting and merging increases the maximum

depth parallel to the ideal level parallelism comparisons of words and at the same time based on the level of operations. The method of allocation was the senior non-zero sign bit in the word, the resulting comparison. The method includes algorithmic and schematics, providing maximum bit parallelization. Additionally there was the problem of occurrence of a substring in a string. Was synthesized parallel search algorithm for the maximum occurrence of a substring in a string. Estimates are given for the time complexity, in particular the maximum parallelism occurrence of a substring in search string characterized by the time complexity O(l), regardless of the number of characters per string. Examples are algorithms and schemes implementation of the proposed method.

Bit by bit-parallel addition without calculating transfer; bit code of the sign; Bit by bit-parallel comparison of numbers and strings; parallel sorting and searching; time complexity.

Постановка вопроса. Ускоряющаяся компьютеризация всех областей деятельности и информационных процессов, значительный рост объемов обрабатываемой информации приводит к трудностям при последовательном выполнении информационного поиска на основе классических алгоритмов [1, 2]. Как основу ускорения поиска можно рассматривать разрядное распараллеливание сравнения слов. С этой целью ниже излагается метод вертикального полноразрядного бинарного сложения без вычисления переноса, заимствованный из [3, 4], и его модификация на случай поразрядно-параллельного сравнения чисел и элементов строкового типа. Модифицированный метод применяется к параллельным алгоритмам сортировки в качестве этапа информационного поиска. Целью модификации является максимально параллельное выполнение сравнения, упорядочения и поиска на уровне одновременно алгоритмических и разрядных операций. Новизна предложения сводится к максимально параллельной схеме выделения знака старшего ненулевого разряда в знакоразрядном однорядном коде результата сравнения.

Поразрядно-параллельное алгебраическое сложение в знакоразрядном коде без вычисления переноса. Описание метода поразрядно-параллельного алгебраического сложения заимствовано из [3, 4]. Пусть рассматриваются два двоичных полинома, -

n Го n Го

P = S Р,. 2г , Рг = \ , P, = s Yi 2 , Yi =\. .

i=0 [l i=0 [l

Пусть p и p расположены в двух входных разрядных сетках (РС), РС(0) и

РС^ , номера клеток которых совпадают с индексами коэффициентов из (1).

Синхронно и взаимно независимо (СВН-параллельно) по всем номерам разрядов j из (2) выполняется операция р . + Yj суммирования по вертикали (СВ;).

Результат СВ; представляется в двоичном коде

1 , Го

Р/ + Уу = A(j2 > = [i> /=°’1’~’и•

При каждом j = const коэффициенты из (3) располагаются по диагонали двух выходных РС, - РСы и РСвых, образуя диагональную от j-го разряда запись (Д -запись) вида

Pn Р n—l p l P 0 PC»

Y n Yn-i Yi Yo РС»

СВ,.

Д  - запись:

Pj

Y j

A О j у

A1j

рс;

РС

РС

рс:

(0) вх

(1) вх

(0) вых

(1) вых

За предварительный результат сложения принимается промежуточный набор разрядных значений из РС^Ы, РСВЫх :

An+1 An A n-1 AJ A1 A О pp(0) рсвых

Vn+1 Vn Vn-1 V j V1 V0 PC(1) вых

где Aj = ^j-

V j = A1

из

называются входным набором, пара слагаемых (5) - промежуточным набором.

Все переносы в (5) оказываются взаимно отделенными вертикальными парами нулей:

0 ^

I, к = const,

0 J, ,

;

где Ак, Ук из (5), 0 < к < п +1. Это так потому [4], что при любом у из (4) складываются не более двух единиц одинакового веса. По той же причине в (4) по диагонали Д -записи от 1 в РС£ЫХ не может располагаться 1 в РС^. На этой основе корректным является следующее преобразование промежуточного набора (5). Все разряды, имеющие значение Ау Ф 0, из РС*0^ (и только из РС^) в (5) подвергаются тождественному преобразованию:

А у = 2А у —Ау, у = 0,1,..., п .

При этом правая часть (6) размещается в у-й клетке РС(°^ и в (у +1) -й клетке рСЫх в порядке Д -записи для всех номеров] преобразуемых разрядов:

a4

0 и

J + і

2A,

Aj

J + і

J

-A,.

-U-

ҐСвЬК

pc(1L

Как только что отмечено, в (у +1) -й клетке РС^ до применения (6), при условии, что в РСвы)х А у Ф 0, всегда находится ноль, иначе Д -запись означала бы результат сложения по вертикали трех единиц веса у -го разряда, тогда как их число не больше двух [3, 4].

Вслед за тем СВН-параллельно по всем у = 0,1,..., п, п + 1 выполняется шаг вертикального сложения, результатом которого в каждом разряде всегда будет либо 0, либо + 1 , либо —1 [3, 4]. При этом значение знакоразрядного кода располагается в РСвы)х, где, таким образом, сформируется окончательное значение вычисляемой суммы Р1 и Р2 из (1).

Временная сложность Т СВН-параллельного сложения в знакоразрядном коде составит «2г (г - время переключения логического элемента) при количестве элементов сумматора пропорциональном числу разрядов слагаемых:

+

A

Т* 2т =0

* 4

Оценки (8), (9) инвариантны относительно числа разрядов п + 1.

Сравнение двоичных чисел на основе поразрядно-параллельного алгебраического сложения. Предполагается, что сравниваемые числа имеют формат (1) с нумерацией разрядов справа налево. Пусть число А принимается за уменьшаемое, - В за вычитаемое, В записывается в обратном коде (единицы заменяются нулями, а нули - единицами). Это допустимо [5-7] рассматривать как тождественное преобразование:

А — В = А +

с учетом

2»+1 _1 = 2"+2й-1 + 2й“2+ ... +21 +2°,

или, в позиционной системе,

2Й+1 - 1=1 1 1 ... 1 1.

4-----V----'

П +1

Над числом А и числом В , взятым в обратном коде, СВН-параллельно по всем номерам разрядов выполняется операция СВ^, затем А и В в обратном коде

суммируются по схеме (2)-(7). Для восстановления правильного результата вычитания учитывается (10)-(12): от однорядного знакоразрядного двоичного кода полученного результата следует вычесть 2 п+' — 1 . Это равносильно тому, что с полученным результатом складывается —2 п+1 + 1 , - к младшему разряду добавляется +1 , а к

разряду веса 2 п+1 (к (п + 2) -му справа налево) добавляется — 1 .

Знак сравнения А и В определяется знаком старшего ненулевого разряда

однорядного знакоразрядного двоичного числа, полученного в скорректированном окончательном результате. Если знак этого разряда отрицательный, то А < В, если положительный, то А > В, если все разряды нулевые, то А = В.

Поразрядно-параллельный способ сравнения строк. Метод переносится [5, 6] на сравнение элементов строкового типа, для краткости, - строк. Используется представление всех символов в ASCII-коде и его перевод в двоичный код. Набор двоичных кодов всех символов в порядке расположения интерпретируется как единое числовое значение. Сравнение полученных двоичных кодов выполняется путем алгебраического сложения изложенным поразрядно-параллельным способом, при этом в соответствии с лексикографическим упорядочением слов выравнивание весов разрядов выполняется по старшим разрядам. Например, [5], сравниваются два слова "ПОИСК" и "ПОЯС": каждый символ слова представляется в ASCП-коде в двоичной форме. Набор двоичных кодов символов в последовательном расположении интерпретируется как единое число:

"ПОИСК": 11001111 11001110 11001000 11001010 11010001

"ПОЯС": 11001111 11001110 11011111 11001010 .

Согласно лексикографическому порядку сравнение выполняется с выравниваем старших разрядов, и код слова "ПОЯС" дополняется недостающими в младших разрядах нулями:

"ПОИСК": 11001111 11001110 11001000 11001010 11010001 "ПОЯС": 11001111 11001110 11011111 11001010 00000000 .

Первое слово - уменьшаемое, второе - вычитаемое, двоичный код второго представляется в обратном коде, после чего СВН-параллельно по всем номерам разрядов выполняется операция СВ^:

11001111 11001110 11001000 11010001 11001010

+ 00110000 00110001 00100000 00101110 11111111

11111111 11111111 11101000 11111111 00110101

0 00000000 00000000 00000000 00000001 1001010 .

Промежуточная сумма преобразуется согласно (6), (7) с учетом (10), (12), в окончательном результате: 0000000000000000000-11-1010000000011001010.

Старший ненулевой разряд равен -1, следовательно, "ПОИСК" < "ПОЯС". Сравнение выполняется поразрядно-параллельно с оценками (8), (9) без учета времени выделения знака старшего ненулевого разряда.

Проблема выделения знака старшего ненулевого разряда. Возникает проблема максимально параллельного выделения знака старшего ненулевого разряда. Следующий схемный способ (рис. 1) реализуется за время 0(1) путем синхронного распространения сигнала запрета из каждого ненулевого разряда во все разряды младшего веса [8]. Во избежание детализации абстрактно предполагается, что каждый разряд обрабатывается взаимно однозначно сопоставленным этому разряду процессорным элементом (ПЭ), его структура инвариантна относительно номера разряда.

На рис. 1 изображены основные операции, СВН-параллельно выполняемые ПЭ, и линии связи (ЛС) между ПЭ. Если значение разряда есть "0", от взаимно однозначно сопоставленного этому разряду ПЭ на вход элемента "НЕ" отдельно сопоставленного вертикального набора ПЭ (на вертикали слева, рис. 1) по диагональной ЛС подается сигнал "0", одновременно этот же сигнал подается на все расположенные выше ПЭ вертикального набора путем размножения по вертикали на все выше расположенные ЛС. Выходные ЛС параллельны входным, и по ним в разрядные ПЭ поступает инвертированный сигнал "1". Разрядные ПЭ принимают инвертированные сигналы на вход собственной логической схемы "И", сохраняя свое входное значение и также подавая его на вход своей схемы "И". В результате все нулевые значения разрядов сохранятся.

Если значение разряда есть "±1", от взаимно однозначно сопоставленного ему ПЭ на вход элемента "НЕ" аналогично сопоставленного ПЭ вертикального набора по связующей их диагональной ЛС также подается сигнал "0", но на все расположенные выше ПЭ вертикального набора путем размножения сигнала на все расположенные выше ЛС в этом случае подается сигнал "1". По выходным ЛС обратно в данный разряд поступает инвертированный сигнал "1", а во все разрядные ПЭ справа по расположенным выше ЛС поступает инвертированный сигнал "0". Разрядные ПЭ принимают инвертированные сигналы на вход собственной логической схемы "И", по-прежнему сохраняя свое входное значение и, подавая в этом случае на вход той же схемы "И" значение "1". Таким образом, единичные значения разрядов сохранятся, если впереди стоящими разрядными ПЭ на соответственные ЛС не была подана "1", которая в вертикальном наборе ПЭ инвертируется в "0".

В результате только ПЭ старшего ненулевого разряда примет значение "1", остальные получат значение "0". ПЭ с единичным значением даст на выход схемы сохраненный знак своего разряда [8].

Рис. 1. Схема выделения старшего ненулевого разряда Очевидно, схема максимально параллельна, выделяет знак старшего ненулевого разряда за время Т(Я)=0(1), число ПЭ пропорционально числу разрядов: Я =2п . Эта оценка инвариантна относительно числа символов слова.

Разрядное распараллеливание поиска вхождения подстроки в строку. Даны подстрока £, состоящая из т символов, и строка Т из п символов. Пусть для простоты т < п. Выполнить поиск вхождения подстроки в строку на основе изложенного метода поразрядно-параллельного сравнения слов можно максимально параллельно за единичное время независимо от числа символов Т и £. Для этого нужно одновременно выполнить выравнивание начального символа подстроки £ с каждым последовательным символом строки Т от ее начала. Далее, от каждого отдельно фиксированного символа строки Т, по которому выполнено выравнивание с подстрокой £ , без учета предшествующих символов, сравнение с подстрокой £ выполняется так, как, если бы с этого символа начиналась строка. Собственно бинарное сравнение без изменения повторяет способ сравнения элементов строкового типа, изложенный выше, сравнение выполняется параллельно по всем символам и поразрядно-параллельно в их двоичной кодировке. Кроме того сравнение выполняется параллельно по всем сдвинутым символам.

Например, требуется выполнить поиск вхождения в строку "ПОИСК" строки "ИСК". Выравнивание по всем последовательным символам строки Т начального символа подстроки £ влечет соответственные сдвиги слова £ :

T:

S:

П О И С К

И С К

И С К

И С К

Все сдвинутые слова £ одновременно сравниваются с символами слова Т :

T: П О И С К

S: И С К

О И С К

И С К

S:

И С К

И С К

Сдвиг прекращается, точнее, не выполняется относительно всех тех символов строки, за пределы последнего из которых выходит сдвигаемая подстрока. Такой сдвиг реализуется параллельно и синхронно по всем символам строки.

Далее, выполняются операции предыдущего примера.

Каждый символ строки "ПОИСК" и подстроки "ИСК" представляется в ASCП-коде в двоичной форме. Набор двоичных кодов символов в последовательном расположении интерпретируется как единое число:

"ПОИСК": 11001111 11001110 11001000 11001010 11010001 "ИСК": 11001000 11001010 11010001

"ОИСК": 11001110 11001000 11001010 11010001 "ИСК": 11001000 11001010 11010001

"ИСК": 11001000 11001010 11010001 "ИСК": 11001000 11001010 11010001 .

На представленными парами чисел синхронно выполняется сравнение путем поразрядно-параллельного алгебраического сложения с кодом подстроки, которому приписывается отрицательный знак. Используется перевод вычитаемого в обратный код и корректировка с учетом аналога дополнительного кода (10)-(12).

В знакоразрядном коде получится -

при сравнении "ПОИСК" и "ИСК": 0000001110000010000—1110—11, старший ненулевой разряд равен 1, "ПОИСК" > "ИСК";

при сравнении "ОИСК" и "ИСК": 00000011000000—11000—111001, старший ненулевой разряд равен 1, "ОИСК" > "ИСК";

при сравнении "ИСК" и "ИСК": 0000000000000000000000000, все разряды нулевые, "ИСК" = "ИСК", искомое вхождение идентифицировано.

Таким образом, подстрока 5 в строке Т найдена за один максимально распараллеленный шаг выполнения сравнения.

Более точно, временная сложность предложенного поиска вхождения подстроки в строку оценивается из соотношения:

Т(К) * 2т,

отсюда

Т (К)=0(1),

где т - время переключения логического элемента, число ПЭ не больше значения, пропорционального числу разрядов строки, умноженному на число разрядов подстроки, в данных обозначениях -

К < т х п .

Для сравнения заметим, что типичная оценка времени последовательного алгоритма рассматриваемого поиска составляет [9] Т = 0(тп), наилучшие оценки [1] Т < 2п и Т = п , их различие определяется структурами алгоритмов.

Таким образом, предложенный способ соответственно дает ускорение в 0(mn) и O(n) за счет роста числа разрядных компонентов.

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

Заключение. Представлен метод поразрядно-параллельного алгебраического сложения без вычисления переноса, который применяется для сравнения чисел и слов по знаку старшего ненулевого разряда знакоразрядной алгебраической суммы (арифметической разности). Предложен максимально параллельный схемный способ выделения этого знака. На этой основе вся бинарная операция полноразрядного сравнения выполняется за время T(R)=0(1), которое формально не зависит от числа символов сравниваемых слов. При этом количество процессорных элементов пропорционально наибольшему числу символов пары сравниваемых слов. Метод ориентирован на применение в базовых операциях информационного поиска, в частности для выполнения сравнения в процессах сортировки и слияния. Показано, что применение метода к поиску вхождения подстроки в строку влечет максимальный параллелизм этой операции и ее выполнение с оценкой времени O(1) , которая формально не зависит от количества символов строки.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Вирт Н. Алгоритмы и структуры данных. - М.: ДМК Пресс, 2010. - 272 с.

2. Кнут Д. Искусство программирования для ЭВМ. Т. З. Сортировка и поиск. - М.: Вильямс, 2007. - 832 с.

3. Ромм Я.Е. Метод вертикальной обработки потока целочисленных групповых данных. I. Групповые арифметические операции // Кибернетика и системный анализ. - 1998.

- № 3. - C. 123-151.

4. Ромм Я.Е. Метод вертикальной обработки потока целочисленных групповых данных. II. Приложение к бинарным арифметическим операциям // Кибернетика и системный анализ. - 1998. - № 6. - С. 146-162.

5. Ромм Я.Е., Чабанюк Д.А. Применение метода вертикальной обработки информации к операциям сравнения и поиска. - Таганрог: ТГПИ, 2013. - 32 с. Деп. в ВИНИТИ

20.05.13, № 141 - В 2013.

6. Ромм Я.Е., Иванова А.С. Вертикальное групповое алгебраическое суммирование применительно к сортировке со слиянием и параллельному поиску. - Таганрог: ТГПИ., 2012.

- 44 с. Деп. в ВИНИТИ 03.09.2012, № 362 - В 2012.

7. Ромм Я.Е., Иванова А.С. Вертикальные групповые арифметические операции над целочисленными данными без вычисления переноса // Фундаментальные исследования.

- 2012. - № 11 - С. 960-964.

8. Ромм Я.Е., Чабанюк Д.А. Сравнение слов с единичной временной сложностью. - Таганрог: ТГПИ, 2013. - 30 с. Деп. в ВИНИТИ 30.10.13, № 306 - В 2013.

9. Charras C., Lecroq T. Handbook of Exact String Matching Algorithms. - College Publications. - 2004. - 256 p.

10. Иванова А.С. Расширение диапазона данных для вертикальной обработки применительно к сортировке со слиянием и поиску: Автореф. дис. ... канд. техн. наук. - Таганрог: ЮФУ, 2013. - 22 с.

REFERENCES

1. Virt N. Algoritmy i struktury dannykh [Algorithms and data structures]. Moscow: DMK Press, 2010, 272 p.

2. Knut D. Iskusstvo programmirovaniya dlya EhVM. T. 3. Sortirovka i poisk [The art of computer programming. Vol. 3. Sorting and searching]. Moscow: Vilyams, 2007, 832 p.

3. Romm Ya.E. Metod vertikalnoy obrabotki potoka celochislennykh gruppovykh dannykh.

I. Gruppovye arifmeticheskie operacii [The method of vertical flow of integral group data. I. Group arithmetic operations], Kibernetika i sistemnihy analiz [Cybernetics and Systems Analysis], 1998, No. 3, pp. 123-151.

4. Romm Ya.E. Metod vertikalnoy obrabotki potoka tselochislennykh gruppovykh dannykh.

II. Prilozhenie k binarnym arifmeticheskim operatsiyam [The method of vertical flow of integral group data. II. The Annex to the binary arithmetic operations], Kibernetika i sistemnyy analiz [Cybernetics and Systems Analysis], 1998, No. 6, pp. 146-162.

5. Romm Ya.E., Chabanyuk D.A. Primenenie metoda vertikalnoy obrabotki informatsii k operatsiyam sravneniya i poiska [Application of the method of vertical processing of information for comparisons and searches]. Taganrog: TGPI, 2013, 32 p. Dep. v VINITI

20.05.13, № 141 - V 2013.

6. Romm Ya.E., Ivanova A.S. Vertikalnoe gruppovoe algebraicheskoe summirovanie primenitelno k sortirovke so sliyaniem i parallelnomu poisku [The vertical group of the algebraic summation with respect to merge sort and parallel search]. Taganrog: TGPI., 2012, 44 p. Dep. v VINITI 03.09.2012, № 362 - V 2012.

7. Romm Ya.E., Chabanyuk D.A. Vertikalnye gruppovye arifmeticheskie operatsii nad tselochislennymi dannymi bez vychisleniya perenosa [The vertical group arithmetic integer data without calculation of transfer], Fundamentalnye issledovaniya [Fundamental Research], 2012, No. 11, pp. 960-964.

8. Romm Ya.E., Chabanyuk D.A. Sravnenie slov s edinichnoy vremennoy slozhnostyu [Compared with single time complexity]. Taganrog: TGPI, 2013, 30 p. Dep. v VINITI

30.10.13, № 306 - V 2013.

9. Charras C., Lecroq T. Handbook of Exact String Matching Algorithms. College Publications. 2004, 256 p.

10. Ivanova A.S. Rasshirenie diapazona dannykh dlya vertikalnoy obrabotki primenitelno k sortirovke so sliyaniem i poisku: Avtoref. dis. ... kand. tekhn. nauk [The expansion of the range of data for vertical processing applied to the merge sort and search. Cand. of eng. sc. abstract of thesis]. Taganrog: YuFU, 2013, 22 p.

Статью рекомендовал к опубликованию д.т.н., профессор Г.Е. Веселов.

Ромм Яков Евсеевич - ФГБОУ ВПО "Таганрогский государственный педагогический институт имени А.П. Чехова"; e-mail: romm@list.ru; 347926, г. Таганрог, ул. Инициативная, 48; тел.: 89094081126; кафедра информатики; зав. кафедрой; д.т.н.; профессор; член Европейской Академии естествознания (EuANH).

Чабанюк Денис Андреевич - e-mail: denchabanyuk@gmail.com; тел.: 89508498511; аспирант.

Romm Yakov Evseevich - Taganrog State Pedagogical Institute; e-mail: romm@List.ru; 48, Initsiativnaya street, Taganrog, 347926, Russia; phone: +79094081126; the department of information science; head of department; dr. of eng. sc.; professor; the member of European Academy of Natural History (EuANH).

Chabanyuk Denis Andreevich - e-mail: denchabanyuk@gmail.com; phone: +79508498511; postgraduate student.