Способ и устройство кодирования и

Изобретение относится к области техники обработки изображений и, в частности, к кодированию и декодированию видеоинформации без потерь. Техническим результатом является собственно создание системы кодирования/декодирования видеоинформации без потерь в которой при выполнении внутреннего предсказания блока, имеющего заранее заданный размер, коэффициент сжатия возрастает за счет использования элемента изображения в предсказываемом блоке. Предложен способ кодирования видеоинформации без потерь, в котором для каждого из множества элементов изображения в блоке M times;N элементов изображения, для которого выполняется предсказание, определяют в блоке M times;N элементов изображения по меньшей мере один элемент изображения, который является наиболее близким к предсказываемому элементу изображения в направлении предсказания, определенном режимом кодирования; предсказывают значение предсказываемого элемента изображения с использованием значения упомянутого по меньшей мере одного элемента изображения, который является наиболее близким к предсказываемому элементу изображения в направлении предсказания; определяют разность между предсказанным значением элемента изображения и предсказываемым значением элемента изображения; выполняют энтропийное кодирование разности между предсказанным значением элемента изображения и предсказываемым значением элемента изображения. 5 н. и 10 з.п. ф-лы, 16 ил., 2 табл.

1. Способ кодирования видеоинформации без потерь, содержащий следующие операции: для каждого из множества элементов изображения в блоке M times;N элементов изображения, для которого выполняется предсказание определяют в блоке M times;N элементов изображения по меньшей мере один элемент изображения, который является наиболее близким к предсказываемому элементу изображения в направлении предсказания, определенном режимом кодирования; предсказывают значение предсказываемого элемента изображения с использованием значения упомянутого по меньшей мере одного элемента изображения, который является наиболее близким к предсказываемому элементу изображения в направлении предсказания; определяют разность между предсказанным значением элемента изображения и предсказываемым значением элемента изображения; и выполняют энтропийное кодирование разности между предсказанным значением элемента изображения и предсказываемым значением элемента изображения.2. Способ по п.1, в котором в том случае, если предсказываемым блоком из M times;N элементов изображения является блок информации о яркости или блок G, то блоком из M times;N элементов изображения является любой из следующих блоков: блок 4 times;4 элемента изображения, блок 8 times;8 элементов изображения и блок 16 times;16 элементов изображения, а если блоком из M times;N элементов изображения является один из следующих блоков: блок информации о цветности, блок R и блок В, то M times;N равно 8 times;8.3. Способ по п.1, в котором для блока информации о яркости или блока G режимом кодирования является один из следующих: режим «по вертикали» (Vertical), режим «по горизонтали» (Horizontal), режим «постоянная составляющая» (DC), режим «по диагонали вниз влево» (Diagonal_Down_Left), режим «по диагонали вниз вправо» (Diagonal_Down_Right), режим «по вертикали вправо» (Vertical_Right), режим «по горизонтали — вниз» (Horizontal_Down), режим «по вертикали — влево» (Vertical_Left) и режим «по горизонтали’ — вверх» (Horizontal_Up), которые представляют собой режимы внутреннего кодирования яркости по блокам 4 times;4 элемента изображения согласно стандарту Н.264.4. Способ по п.1, в котором для одного из следующих блоков: блока информации о цветности, блока R и блока В, режимом кодирования является один из следующих режимов: режим «по вертикали» (Vertical), режим «по горизонтали» (Horizontal) и режим «постоянная составляющая» (DC), которые представляют собой режимы внутреннего кодирования цветности по блокам 8 times;8 элементов изображения согласно стандарту Н.264.5. Способ по п.1, в котором операция энтропийного кодирования разности между предсказанным значением элемента изображения и предсказываемым значением элемента изображения содержит следующую операцию: определяют режим кодирования, имеющий самую низкую скорость, путем выполнения внутреннего предсказания для предсказания значений элементов изображения для блока из M times;N элементов изображения в режиме внутреннего кодирования согласно стандарту Н.264, и выполняют энтропийное кодирование разности между предсказанным значением элемента изображения, которое предсказано согласно определенному таким способом режиму кодирования, и предсказываемым значением элемента изображения.6. Способ кодирования видеоинформации без потерь, содержащий следующие операции: для каждого из множества элементов изображения в блоке M times;N элементов изображения, для которого выполняется предсказание определяют по меньшей мере один элемент изображения соседний с блоком из M times;N элементов изображения в направлении, определенном согласно режиму кодирования, предсказывают значение предсказываемого элемента изображения с использованием значения упомянутого по меньшей мере одного элемента изображения, соседнего с упомянутым блоком из M times;N элементов изображения в направлении, определенном согласно режиму кодирования; определяют разность между предсказанным значением элемента изображения и предсказываемым значением элемента изображения, тем самым получая блок M times;N элементов, сформированный из упомянутых разностей; выполняют кодирование упомянутого блока M times;N элементов, сформированного из упомянутых разностей с использованием способа по п.1.7. Способ декодирования видеоинформации без потерь, содержащий следующие операции: принимают поток битов, полученный путем выполнения энтропийного кодирования на основании множества предсказанных значений, причем каждый элемент изображения предсказан с использованием ближайшего элемента изображения в направлении предсказания, определенном согласно режиму кодирования, в блоке из M times;N элементов изображения, который представляет собой единичный предсказываемый блок; выполняют энтропийное декодирование потока битов; и восстанавливают без потерь первоначальное изображение согласно декодированным значениям.8. Способ по п.7, в котором в том случае, если блоком из M times;N элементов изображения является блок информации о яркости или блок G, то блоком из M times;N элементов изображения является любой из следующих блоков: блок 4 times;4 элемента изображения, блок 8 times;8 элементов изображения и блок 16 times;16 элементов изображения, а если блоком из M times;N элементов изображения является один из следующих блоков: блок информации о цветности, блок R и блок В, то блоком из M times;N элементов изображения является блок 8×8 элементов изображения.9. Способ по п.7, в котором для блока информации о яркости или блока G режимом кодирования является один из следующих: режим «по вертикали» (Vertical), режим «по горизонтали» (Horizontal), режим «постоянная составляющая» (DC), режим «по диагонали вниз влево» (Diagonal_Down_Left), режим «по диагонали вниз вправо» (Diagonal_Down_Right), режим «по вертикали вправо» (Vertical_Right), режим «по горизонтали — вниз» (Horizontal_Down), режим «по вертикали — влево» (Vertical_Left) и режим «по горизонтали — вверх» (Horizontal_Up), которые представляют собой режимы внутреннего кодирования яркости по блокам 4 times;4 элемента изображения согласно стандарту Н.264.10. Способ по п.7, в котором для одного из следующих блоков: блока информации о цветности, блока R и блока В, режимом кодирования является один из следующих режимов: режим «по вертикали» (Vertical), режим «по горизонтали» (Horizontal) и режим «постоянная составляющая» (DC), которые представляют собой режимы внутреннего кодирования цветности по блокам из M times;N элементов изображения согласно стандарту Н.264.11. Устройство кодирования видеоинформации без потерь, содержащее модуль предсказания движения, который для каждого из множества элементов изображения в предсказываемом блоке M times;N элементов изображения, определяет в блоке M times;N элементов изображения по меньшей мере один элемент изображения, который является наиболее близким к предсказываемому элементу изображения в направлении предсказания, определенном режимом кодирования; предсказывает значение предсказываемого элемента изображения с использованием значения упомянутого по меньшей мере одного элемента изображения, который является наиболее близким к предсказываемому элементу изображения в направлении предсказания; причем модуль предсказания движения выполняет определение разности между предсказанным значением элемента изображения и предсказываемым значением элемента изображения; и модуль энтропийного кодирования, который выполняет энтропийное кодирование разности между предсказанным значением элемента изображения и предсказываемым значением элемента изображения.12. Устройство по п.11, в котором модуль предсказания движения дополнительно содержит: модуль вычисления разностного значения, который для каждого из множества элементов изображения в блоке M times;N элементов изображения, для которого выполняется предсказание определяет по меньшей мере один элемент изображения соседний с блоком из M times;N элементов изображения в направлении, определенном согласно режиму кодирования, предсказывает значение предсказываемого элемента изображения с использованием значения упомянутого по меньшей мере одного элемента изображения, соседний с упомянутым блоком из M times;N элементов изображения в направлении, определенном согласно режиму кодирования; определяет разность между предсказанным значением элемента изображения и предсказываемым значением элемента изображения, тем самым получая блок M times;N элементов, сформированный из упомянутых разностей, используемый при дальнейшей обработке в модуле предсказания движения.13. Устройство по п.11, в котором в том случае, если предсказываемым блоком из M times;N элементов изображения является блок информации о яркости или блок G, то блоком из M times;N элементов изображения является любой из следующих блоков: блок 4 times;4 элемента изображения, блок 8 times;8 элементов изображения и блок 16 times;16 элементов изображения, а если блоком из M times;N элементов изображения является один из следующих блоков: блок информации о цветности, блок R и блок В, то блоком из M times;N элементов изображения является блок 8 times;8 элементов изображения.14. Устройство декодирования видеоинформации без потерь, содержащее: модуль энтропийного декодирования, который принимает поток битов, полученный путем выполнения энтропийного кодирования на основании значений, предсказанных путем использования ближайшего элемента изображения в направлении предсказания, определенном согласно режиму кодирования, в блоке из M times;N элементов изображения, который представляет собой единичный предсказываемый блок, и выполняет энтропийное декодирование потока битов; и модуль восстановления видеоинформации, который восстанавливает первоначальное изображение без потерь согласно декодированным значениям.15. Устройство по п.14, в котором в том случае, если предсказываемым блоком из M times;N элементов изображения является блок информации о яркости или блок G, то блоком из M times;N элементов изображения является любой из следующих блоков: блок 4 times;4 элемента изображения, блок 8 times;8 элементов изображения и блок 16 times;16 элементов изображения, а если блоком из M times;N элементов изображения является один из следующих блоков: блок информации о цветности, блок R и блок В, то блоком из M times;N элементов изображения является блок 8 times;8 элементов изображения.

Область техники, к которой относится изобретениеУстройства и способы, соответствующие настоящему изобретению, относятся к кодированию и декодированию видеоинформации и, в частности, к кодированию и к декодированию видеоинформации без потерь, посредством которых обеспечено увеличение коэффициента сжатия при выполнении внутреннего предсказания для блока заранее заданного размера с использованием элемента изображения в предсказываемом блоке.Предшествующий уровень техникиСогласно стандарту H.264, установленному для кодирования и декодирования видеоинформации, кадр содержит множество макроблоков, а кодирование и декодирование выполняют по единичным макроблокам, или по единичным субблокам, которые получены путем разделения макроблока на два или на четыре единичных элемента. Существует два способа предсказания движения макроблока текущего кадра, подлежащего кодированию: временное предсказание, в котором опорными макроблоками являются макроблоки соседнего кадра, и пространственное предсказание, в котором опорным макроблоком является соседний макроблок.Пространственное предсказание также именуют внутренним предсказанием. Внутреннее предсказание основано на следующем свойстве: когда элемент изображения предсказан, то, наиболее вероятно, что соседний элемент изображения имеет максимально сходное с ним значение.Между тем, кодирование может быть подразделено на кодирование с потерями и кодирование без потерь. Для выполнения кодирования видеоинформации без потерь предсказанное значение элемента изображения, вычисленное путем предсказания движения, вычитают из текущего значения элемента изображения. Затем выполняют энтропийное кодирование без дискретного косинусного преобразования (ДКП) или квантования и выводят результат.РАСКРЫТИЕ СУЩНОСТИ ИЗОБРЕТЕНИЯТехническая задачаВ обычном способе при выполнении кодирования без потерь каждое значение элемента изображения в предсказываемом блоке предсказывают с использованием значения элемента изображения из блока, являющегося соседним с предсказываемым блоком, и, следовательно, коэффициент сжатия является намного более низким, чем при кодировании с потерями.Техническое решениеВ настоящем изобретении предложены способ и устройство кодирования и декодирования видеоинформации без потерь, посредством которых при выполнении внутреннего предсказания блока, имеющего заранее заданный размер, коэффициент сжатия возрастает за счет использования элемента изображения (пикселя) в предсказываемом блоке.Согласно одному из объектов настоящего изобретения, в нем предложен способ кодирования видеоинформации без потерь, содержащий следующие операции: предсказывают значения каждого из элементов изображения в предсказываемом блоке из М times; N элементов изображения с использованием того элемента изображения в блоке из М times; N элементов изображения, который является наиболее близким к значению элемента изображения в направлении предсказания, определенном режимом кодирования; и выполняют энтропийное кодирование разности между предсказанным значением элемента изображения и предсказываемым значением элемента изображения.Когда предсказываемым блоком является блок информации о яркости или блок G, то блоком из М times;N элементов изображения может являться любой из следующих блоков: блок 4 times;4 элемента изображения, блок 8 times;8 элементов изображения и блок 16 times;16 элементов изображения, а когда им является любой из следующих блоков: блок информации о цветности, блок R и блок B, то блоком из М times;N элементов изображения может являться блок 8 times;8 элементов изображения.Для блока информации о яркости или блока G режимами кодирования могут являться следующие: режим «по вертикали» (Vertical), режим «по горизонтали» (Horizontal), режим «постоянная составляющая» (DC), режим «по диагонали вниз влево» (Diagonal_Down_Left), режим «по диагонали вниз вправо» (Diagonal_Down_Right), режим «по вертикали — вправо» (Vertical_Right), режим «по горизонтали — вниз» (Horizontal_Down), режим «по вертикали — влево» (Vertical_Left) и режим «по горизонтали — вверх» (Horizontal_Up), которые представляют собой режимы внутреннего кодирования яркости по блокам 4 times;4 элемента изображения согласно стандарту H.264.Для любого из блоков информации о цветности, блока R и блока B, режимами кодирования могут являться следующие режимы: режим «по вертикали» (Vertical), режим «по горизонтали» (Horizontal) и режим «постоянная составляющая» (DC), которые представляют собой режимы внутреннего кодирования цветности в блоках M times;N элементов изображения согласно стандарту H.264.Согласно другому объекту настоящего изобретения, в нем предложен способ декодирования видеоинформации без потерь, содержащий следующие операции: принимают поток битов, полученный путем выполнения энтропийного кодирования на основании предсказанных значений, при этом каждое из них предсказано с использованием ближайшего элемента изображения в направлении предсказания, определенного согласно режиму кодирования, в блоке из М times;N элементов изображения, который представляет собой единичный предсказываемый блок; выполняют энтропийное декодирование потока битов и восстанавливают без потерь первоначальное изображение согласно декодированным значениям.Согласно еще одному объекту настоящего изобретения, в нем предложено устройство кодирования видеоинформации без потерь, содержащее: модуль предсказания движения, предсказывающий значение каждого элемента изображения в предсказываемом блоке из М times;N элементов изображения с использованием того элемента изображения в блоке из М times;N элементов изображения, который является ближайшим к значению элемента изображения в направлении предсказания, определенном режимом кодирования; и модуль энтропийного кодирования, который выполняет энтропийное кодирование разности между предсказанным значением элемента изображения и предсказываемым значением элемента изображения.Согласно еще одному объекту настоящего изобретения, в нем предложено устройство декодирования видеоинформации без потерь, содержащее: модуль энтропийного декодирования, который принимает поток битов, полученный путем выполнения энтропийного кодирования на основании значений, предсказанных путем использования ближайшего элемента изображения в направлении предсказания, определенном согласно режиму кодирования, в блоке из М times;N элементов изображения, который представляет собой единичный предсказываемый блок, и выполняет энтропийное декодирование потока битов; и модуль восстановления видеоинформации, который восстанавливает первоначальное изображение без потерь согласно декодированным значениям.ПОЛЕЗНЫЕ ЭФФЕКТЫ ИЗОБРЕТЕНИЯПри выполнении кодирования без потерь может быть улучшен коэффициент сжатия. В частности, при использовании только режима внутреннего предсказания коэффициент сжатия является намного более высоким, чем при обычном способе.ОПИСАНИЕ ЧЕРТЕЖЕЙНа Фиг.1 изображена блок-схема устройства кодирования согласно варианту осуществления настоящего изобретения, который приведен в качестве примера;на Фиг.2 изображена диаграмма, на которой показаны режимы внутреннего предсказания для блока 4 times;4 элемента изображения согласно стандарту H.264;на Фиг.3A проиллюстрировано предсказание элементов изображения из блока информации о яркости и блока G в режиме «по вертикали» (в режиме 0);на Фиг.3B проиллюстрировано предсказание элементов изображения из блока информации о яркости и блока G в режиме «по горизонтали» (в режиме 1);на Фиг.3C проиллюстрировано предсказание элементов изображения из блока информации о яркости и блока G в режиме «по диагонали вниз влево» (в режиме 3);на Фиг.3D проиллюстрировано предсказание элементов изображения из блока информации о яркости и блока G в режиме «по диагонали вниз вправо» (в режиме 4);на Фиг.3E проиллюстрировано предсказание элементов изображения из блока информации о яркости и блока G в режиме «по вертикали — вправо» (в режиме 5);на Фиг.3F проиллюстрировано предсказание элементов изображения из блока информации о яркости и блока G в режиме «по горизонтали — вниз» (в режиме 6);на Фиг.3G проиллюстрировано предсказание элементов изображения из блока информации о яркости и блока G в режиме «по вертикали — влево» (в режиме 7);на Фиг.3H проиллюстрировано предсказание элементов изображения из блока информации о яркости и блока G в режиме «по горизонтали — вверх» (в режиме 8);на Фиг.4A проиллюстрировано предсказание элементов изображения из блока информации о цветности, блока R и блока B, в режиме «постоянная составляющая» (DC);на Фиг.4B проиллюстрировано предсказание элементов изображения из блока информации о цветности, блока R и блока B в режиме «по горизонтали»;на Фиг.4C проиллюстрировано предсказание элементов изображения из блока информации о цветности, блока R и блока B в режиме «по вертикали»;на Фиг.5 проиллюстрирован способ предсказания при выполнении кодирования и декодирования в вышеупомянутых режимах;на Фиг.6 изображена блок-схема устройства декодирования согласно варианту осуществления настоящего изобретения, который приведен в качестве примера; ина Фиг.7 изображена схема последовательности операций способа кодирования согласно настоящему изобретению.НАИЛУЧШИЙ ВАРИАНТ ОСУЩЕСТВЛЕНИЯ ИЗОБРЕТЕНИЯДля объяснения вариантов осуществления настоящего изобретения, которые приведены в качестве примеров, сначала здесь приведено пояснение определения предсказываемого значения и разностного значения.Предполагая, что положением элемента изображения в верхнем левом углу является x=0, y=0, величина p[x,y] указывает значение элемента изображения в относительном положении (x,y). Например, на Фиг.3A положение элемента «a» изображения выражено как [0, 0], положение элемента «b» изображения — как [1,0], положение элемента «c» изображения — как [2,0], положение элемента «d» изображения — как [3,0], а положение элемента «e» изображения — как [0,1]. Положения остальных элементов изображения от «f» до «p» могут быть выражены тем же самым способом.Предсказанное значение в том случае, когда элемент изображения предсказан исходным способом согласно стандарту H.264 без видоизменения способа предсказания, выражено как predL[x, y]. Например, предсказанное значение элемента «a» изображения на Фиг.3A выражено как predL[0,0]. Тем же самым образом, предсказанным значением элемента «b» изображения является predL[1,0], предсказанным значением элемента «c» изображения является predL[2,0], предсказанным значением элемента «d» изображения является predL[3,0], а предсказанным значением элемента «e» изображения является predL[0,1]. Предсказанные значения остальных элементов изображения от «f» до «p» могут быть выражены тем же самым способом.Предсказанное значение в том случае, когда элемент изображения предсказан согласно настоящему изобретению, исходя из соседних элементов изображения, выражено как predL'[x,y]. Положение элемента изображения выражено тем же самым способом, как и в predL[x,y]. Разностное значение для положения (i,j), полученное путем вычитания предсказанного значения элемента изображения в положении (i,j) из значения элемента изображения в положении (i,j), выражено как ri,j. Значение элемента изображения в положении (i,j), восстановленное путем суммирования предсказанного значения элемента изображения в положении (i,j) и разностного значения в положении (i,j) при выполнении декодирования, выражено как ui,j.Теперь будет приведено более полное описание настоящего изобретения со ссылкой на сопроводительные чертежи, на которых показаны варианты осуществления настоящего изобретения, приведенные в качестве примеров.Со ссылкой на Фиг.1, на котором показано устройство кодирования согласно варианту осуществления настоящего изобретения, приведенному в качестве примера, при вводе изображения выполняют предсказание движения. В настоящем изобретении элементы изображения из блока информации о яркости и блока G получают путем выполнения внутреннего предсказания по блокам 4 times;4 элемента изображения, а элементы изображения из блока информации о цветности, блока R и блока B получают путем выполнения внутреннего предсказания по блокам 8 times;8 элементов изображения. Соответственно, модуль 110 предсказания движения выполняет внутреннее предсказание по блокам 4 times;4 элемента изображения для элементов изображения из блока информации о яркости и из блока G в предсказываемом макроблоке и внутреннее предсказание по блокам 8 times;8 элементов изображения для элементов изображения из блока информации о цветности, блока R и блока B. Объяснение вычисления предсказанных значений элементов изображения при выполнении внутреннего предсказания по блокам 4 times;4 элемента изображения и внутреннего предсказания по блокам 8 times;8 элементов изображения приведено ниже. Модуль 120 выбора режима выбирает один оптимальный режим из множества режимов предсказания. То есть, при выполнении внутреннего предсказания по блокам 4 times;4 элемента изображения и внутреннего предсказания по блокам 8 times;8 элементов изображения из множества имеющихся режимов кодирования выбирают один режим. Как правило, один режим выбирают согласно способу оптимизации искажений в зависимости от скорости передачи (RD), который сводит к минимуму искажения в зависимости от скорости передачи. Поскольку при кодировании без потерь из настоящего изобретения искажения отсутствуют, то один режим кодирования определяют путем оптимизации скоростей передачи.Модуль 130 энтропийного кодирования выполняет энтропийное кодирование значения разности, поступившего с выхода модуля 110 предсказания движения, то есть, разности между значением элемента изображения в макроблоке текущего кадра, который желают закодировать, и предсказанным значением элемента изображения, и производит вывод результата. Термин «энтропийное кодирование» означает способ кодирования, которым меньшее количество битов присвоено более часто встречающимся данным, и большее количество битов присвоено менее часто встречающимся данным, что приводит к увеличению коэффициента сжатия данных. Способы энтропийного кодирования, использованные в настоящем изобретении, содержат контекстно-адаптивное кодирование кодами переменной длины (CAVLC) и контекстно-адаптивное двоичное арифметическое кодирование (CABAC).РЕЖИМ ДЛЯ НАСТОЯЩЕГО ИЗОБРЕТЕНИЯНа Фиг.2 изображена диаграмма, на которой показаны режимы внутреннего предсказания для блока 4 times;4 элемента изображения согласно стандарту H.264.Внутреннее предсказание элементов изображения в блоке информации о яркости и в блоке G выполняют по единичным блокам 4 times;4 элемента изображения. Существует девять типов режимов внутреннего предсказания по блокам 4 times;4 элемента изображения, соответствующие различным направлениям предсказания, в том числе: режим «по вертикали» (Vertical) (режим 0), режим «по горизонтали» (Horizontal) (режим 1), режим «постоянная составляющая» (DC) (режим 2), режим «по диагонали вниз влево» (Diagonal_Down_Left) (режим 3), режим «по диагонали вниз вправо» (Diagonal_Down_Right) (режим 4), режим «по вертикали — вправо» (Vertical_Right) (режим 5), режим «по горизонтали — вниз» (Horizontal_Down) (режим 6), режим «по вертикали — влево» (Vertical_Left) (режим 7) и режим «по горизонтали — вверх» (Horizontal_Up) (режим 8). Стрелки на Фиг. 2 указывают направления предсказания. Теперь будет приведено более подробное объяснение вычисления элемента изображения в каждом режиме.На Фиг.3A проиллюстрировано предсказание элементов изображения из блока информации о яркости и блока G в режиме «по вертикали» (в режиме 0).Элемент «a» 302 изображения предсказывают исходя из элемента «A» изображения, который является соседним элементом изображения в вертикальном направлении, а элемент «e» 304 изображения предсказывают исходя не из элемента «A» изображения, соседнего с предсказываемым блоком 300, а исходя из элемента «a» 302 изображения, который является соседним с элементом «e» 304 изображения в блоке 300. Элемент «i» 306 изображения также предсказывают исходя из элемента «e» 304 изображения, а элемент «m» 308 изображения предсказывают исходя из элемента «i» 306 изображения.Таким же самым образом, элемент «b» изображения предсказывают исходя из элемента «B» изображения, элемент «f» изображения — из элемента «b» изображения, элемент «j» изображения — из элемента «f» изображения, элемент «n» изображения — из элемента «j» изображения, элемент «c» изображения — из элемента «С» изображения, элемент «g» изображения — из элемента «c» изображения, элемент «k» изображения — из элемента «g» изображения, элемент «o» изображения — из элемента «k» изображения, элемент «d» изображения — из элемента «D» изображения, элемент «h» изображения — из элемента «d» изображения, элемент «l» изображения — из элемента «h» изображения и элемент «p» изображения — из элемента «l» изображения. Термин «предсказание» означает здесь вывод разности (разностной величины) значений элементов изображения и энтропийное кодирование этой разности. То есть, для элементов «a», «e», «i» и «m» изображения в предсказываемом блоке 300, осуществляют вывод и энтропийное кодирование разностных значений, соответственно, (a-A), (e-a), (i-e) и (m-i). Способ предсказания элементов изображения в режиме «по вертикали» (в режиме 0) может быть выражен следующим уравнением:pred4 times;4L'[x,y]=p[x,y-1], x,y=0,…, 3На Фиг.3B проиллюстрировано предсказание элементов изображения из блока информации о яркости и блока G в режиме «по горизонтали» (в режиме 1).Элемент «a» 312 изображения предсказывают, исходя из элемента «I» изображения, который является соседним элементом изображения в горизонтальном направлении, а элемент «b» 314 изображения предсказывают не исходя из элемента «I» изображения, соседнего с предсказываемым блоком 300, а исходя из элемента «a» 312 изображения, который является соседним с элементом «b» 314 изображения в блоке 300. Элемент «c» 316 изображения также предсказывают исходя из элемента «b» 314 изображения, а элемент «d» 318 изображения предсказывают исходя из элемента «c» 316 изображения.Таким же самым образом, элемент «e» изображения предсказывают исходя из элемента «J» изображения, элемент «f» изображения — из элемента «e» изображения, элемент «g» изображения — из элемента «f» изображения, элемент «h» изображения — из элемента «g» изображения, элемент «i» изображения — из элемента «K» изображения, элемент «j» изображения — из элемента «i» изображения, элемент «k» изображения — из элемента «j» изображения, элемент «l» изображения — из элемента «k» изображения, элемент «m» изображения — из элемента «L» изображения, элемент «n» изображения — из элемента «m» изображения, элемент «o» изображения — из элемента «n» изображения и элемент «p» изображения — из элемента «o» изображения. Способ предсказания элементов изображения в режиме «по горизонтали» (в режиме 1) может быть выражен следующим уравнением:pred4 times;4L'[x,y]=p[x-1,y], x,y = 0,…,3.На Фиг.3C проиллюстрировано предсказание элементов изображения из блока информации о яркости и блока G в режиме «по диагонали вниз влево» (в режиме 3).Элемент «a» 322 изображения предсказывают исходя из элемента «B» изображения, который является соседним элементом изображения в диагональном направлении, указанном на Фиг.3C стрелкой, а элемент «e» 324 изображения предсказывают исходя из элемента «b» изображения, который в блоке 300 является элементом изображения, соседним с элементом «e» 324 изображения по направлению стрелки. Элемент «i» 326 изображения также предсказывают исходя из элемента «f» изображения, а элемент «m» 328 изображения предсказывают исходя из элемента «j» изображения.Таким же самым образом, элемент «b» изображения предсказывают исходя из элемента «C» изображения, элемент «c» изображения — из элемента «D» изображения, элемент «d» изображения — из элемента «E» изображения, элемент «f» изображения — из элемента «c» изображения, элемент «g» изображения — из элемента «d» изображения, элемент «h» изображения — из элемента «d» изображения, элемент «j» изображения — из элемента «g» изображения, элемент «k» изображения — из элемента «h» изображения, элемент «l» изображения — из элемента «h» изображения, элемент «n» изображения — из элемента «k» изображения, элемент «o» изображения — из элемента «l» изображения и элемент «p» изображения — из элемента «l» изображения. Способ предсказания элементов изображения в режиме «по диагонали вниз влево» (в режиме 3) может быть выражен следующим уравнением:если x=3, y ne;0, то predL'[x,y]=p[x1,y-1],в противном случае predL'[x,y]=p[x+1,y-1].К тому же, когда предсказание элементов изображения производят в режиме «по диагонали вниз влево» (в режиме 3), то предсказание может быть выполнено с использованием надлежащего фильтра для элементов изображения в направлениях предсказания. Например, при использовании фильтра типа 1:2:1 элемент «a» 322 изображения предсказывают исходя из значения (A+2B+C+2)/4, которое сформировано с использованием значений элементов изображения, расположенных в диагональном направлении, указанном на Фиг. 3C стрелками, а элемент «e» 324 изображения предсказывают исходя из значения (a+2b+c+2)/4, которое сформировано с использованием значений элементов изображения, расположенных в блоке 300 рядом с элементом «e» 324 изображения в диагональном направлении. Элемент «i» 326 изображения также предсказывают исходя из значения (e+2f+g+2)/4, а элемент «m» 328 изображения предсказывают исходя из значения (i+2j+k+2)/4.Таким же самым образом, элемент «b» изображения предсказывают исходя из значения (B+2C+D+2), элемент «c» изображения — исходя из значения (C+2D+E+2)/4, элемент «d» изображения — исходя из значения (D+2E+F+2)/4, элемент «f» изображения — исходя из значения (b+2c+d+2)/4, элемент «g» изображения — исходя из значения (c+2d+d+2)/4, элемент «h» изображения — исходя из значения (d+2d+d+2)/4, элемент «j» изображения — исходя из значения (f+2g+h+2)/4, элемент «k» изображения — исходя из значения (g+2h+h+2)/4, элемент «l» изображения — исходя из значения (h+2h+h+2)/4, элемент «n» изображения — исходя из значения (j+2k+l+2)/4, элемент «o» изображения — исходя из значения (k+2l+l+2)/4 и элемент «p» изображения — исходя из значения (l+2l+l+2)/4.На Фиг.3D проиллюстрировано предсказание элементов изображения из блока информации о яркости и блока G в режиме «по диагонали вниз вправо» (в режиме 4).Элемент «a» 322 изображения предсказывают исходя из элемента «X» изображения, который является соседним элементом изображения в диагональном направлении, указанном на Фиг.3D стрелкой, а элемент «f» 334 изображения предсказывают исходя из элемента «a» изображения, который в блоке 300 является элементом изображения, соседним с элементом «f» 334 изображения в направлении стрелки. Элемент «k» 336 изображения также предсказывают исходя из элемента «f» изображения, а элемент «p» 338 изображения предсказывают исходя из элемента «k» изображения.Таким же образом, элемент «b» изображения предсказывают исходя из элемента «A» изображения, элемент «c» изображения — из элемента «B» изображения, элемент «d» изображения — из элемента «C» изображения, элемент «e» изображения — из элемента «I» изображения, элемент «g» изображения — из элемента «b» изображения, элемент «h» изображения — из элемента «c» изображения, элемент «i» изображения — из элемента «J» изображения, элемент «j» изображения — из элемента «e» изображения, элемент «l» изображения — из элемента «g» изображения, элемент «m» изображения — из элемента «K» изображения, элемент «n» изображения — из элемента «i» изображения и элемент «o» изображения — из элемента «j» изображения. Способ предсказания элементов изображения в режиме «по диагонали вниз вправо» (в режиме 4) может быть выражен следующим уравнением:pred4 times;4L'[x,y] = p[x-1,y-1], x,y = 0,…, 3.К тому же, когда предсказание элементов изображения производят в режиме «по диагонали вниз вправо» (в режиме 4), то предсказание может быть выполнено с использованием надлежащего фильтра для элементов изображения в направлениях предсказания. Например, при использовании фильтра типа 1:2:1 элемент «a» 332 изображения предсказывают исходя из значения (I+2X+A+2)/4, которое сформировано с использованием значений элементов изображения, расположенных в диагональном направлении, указанном на Фиг.3D стрелками, а элемент «f» 334 изображения предсказывают исходя из значения (I+2a+b+2)/4, которое сформировано с использованием значений элементов изображения, расположенных в блоке 300 рядом с элементом «f» 334 изображения в направлении стрелки. Элемент «k» 336 изображения также предсказывают исходя из значения (e+2f+g+2)/4, а элемент «p» 338 изображения предсказывают исходя из значения (j+2k+l+2)/4.Таким же самым образом, элемент «b» изображения предсказывают исходя из значения (X+2A+B+2)/4, элемент «c» изображения — исходя из значения (A+2B+C+2)/4, элемент «d» изображения — исходя из значения (B+2C+D+2)/4, элемент «e» изображения — исходя из значения (J+2I+a+2)/4, элемент «g» изображения — исходя из значения (a+2b+c+2)/4, элемент «h» изображения — исходя из значения (b+2c+d+2)/4, элемент «i» изображения — исходя из значения (K+2J+e+2)/4, элемент «j» изображения — исходя из значения (J+2e+f+2)/4, элемент «l» изображения — исходя из значения (f+2g+h+2)/4, элемент «m» изображения — исходя из значения (L+2K+i+2)/4, элемент «n» изображения — исходя из значения (K+2i+j+2)/4 и элемент «o» изображения — исходя из значения (i+2j+k+2)/4.На Фиг.3E проиллюстрировано предсказание элементов изображения из блока информации о яркости и блока G в режиме «по вертикали — вправо» (в режиме 5).Элемент «a» 342 изображения предсказывают исходя из значения (X+A+1)/2, которое сформировано с использованием значений элементов, расположенных в диагональном направлении под углом 22,5 deg; от вертикали, указанном на Фиг.3E стрелками, а элемент «e» 344 изображения предсказывают исходя из значения (I+a+1)/2, которое сформировано с использованием значений соседних элементов изображения, расположенных в блоке 300 изображения рядом с элементом «e» 344 изображения в направлении стрелки под углом 22,5 deg; от вертикали. Элемент «j» 346 изображения также предсказывают исходя из значения (e+f+1)/2, а элемент «n» 348 изображения предсказывают исходя из значения (i+j+1)/2.Таким же самым образом, элемент «b» изображения предсказывают исходя из значения (A+B+1)/2, элемент «c» изображения — исходя из значения (B+C+1)/2, элемент «d» изображения — исходя из значения (C+D+1)/2, элемент «f» изображения — исходя из значения (a+b+1)/2, элемент «g» изображения — исходя из значения (b+c+1)/2, элемент «h» изображения — исходя из значения (c+d+1)/2, элемент «i» изображения — исходя из значения (J+e+1)/2, элемент «k» изображения — исходя из значения (f+g+1)/2, элемент «l» изображения — исходя из значения (g+h+1)/2, элемент «m» изображения — исходя из значения (K+i+1)/2, элемент «o» изображения — исходя из значения (j+k+1)/2 и элемент «p» изображения — исходя из значения (k+l+1)/2. Способ предсказания элементов изображения в режиме «по вертикали — вправо» (в режиме 5) может быть выражен следующими уравнениями:pred4 times;4L'[0,0] = (p[-1,-1]+p[0,-1]+1) gt; gt;1pred4 times;4L'[1,0] = (p[0,-1]+p[1,-1]+1) gt; gt;1pred4 times;4L'[2,0]= (p[1,-1]+p[2,-1]+1) gt; gt;1pred4 times;4L'[3,0] = (p[2,-1]+p[3,-1]+1) gt; gt;1pred4 times;4L'[0,1] = (p[-1,0]+p[0,0]+1) gt; gt;1pred4 times;4L'[1,1] = (p[0,0]+p[1,0]+1) gt; gt;1pred4 times;4L'[2,1]= (p[1,0]+p[2,0]+1) gt; gt;1pred4 times;4L'[3,1] = (p[2,0]+p[3,0]+1) gt; gt;1pred4 times;4L'[0,2] = (p[-1,1]+p[0,1]+1) gt; gt;1pred4 times;4L'[1,2]= (p[0,1]+p[1,1]+1) gt; gt;1pred4 times;4L'[2,2] = (p[1,1]+p[2,1]+1) gt; gt;1pred4 times;4L'[3,2]= (p[2,1]+p[3,1]+1) gt; gt;1pred4 times;4L'[0,3]= (p[-1,2]+p[0,2]+ 1) gt; gt;1pred4 times;4L'[1,3]= (p[0,2]+p[1,2]+1) gt; gt;1pred4 times;4L'[2,3] = (p[1,2]+p[2,2]+1) gt; gt;1pred4 times;4L'[3,3] = (p[2,2]+p[3,2]+1) gt; gt;1На Фиг.3F проиллюстрировано предсказание элементов изображения из блока информации о яркости и блока G в режиме «по горизонтали — вниз» (в режиме 6).Элемент «a» 352 изображения предсказывают исходя из значения (X+I+1)/2, которое сформировано с использованием значений элементов, расположенных в диагональном направлении под углом 22,5 deg; от горизонтали, указанном на Фиг.3F стрелками, а элемент «b» 354 изображения предсказывают исходя из значения (A+a+1)/2, которое сформировано с использованием значений соседних элементов изображения, расположенных в блоке 300 изображения рядом с элементом «b» 354 изображения в направлении стрелки под углом 22,5 deg; от горизонтали. Элемент «g» 356 изображения также предсказывают исходя из значения (b+f+1)/2, а элемент «h» 358 изображения предсказывают исходя из значения (c+g+1)/2.Таким же самым образом, элемент «i» изображения предсказывают исходя из значения (J+K+1)/2, элемент «m» изображения — исходя из значения (K+L+1)/2, элемент «f» изображения — исходя из значения (a+e+1)/2, элемент «j» изображения — исходя из значения (e+i+1)/2, элемент «n» изображения — исходя из значения (i+m+1)/2, элемент «c» изображения — исходя из значения (B+b+1)/2, элемент «k» изображения — исходя из значения (f+j+1)/2, элемент «o» изображения — исходя из значения (j+n+1)/2, элемент «d» изображения — исходя из значения (C+c+1)/2, элемент «l» изображения — исходя из значения (g+k+1)/2 и элемент «p» изображения — исходя из значения (k+o+1)/2. Способ предсказания элементов изображения в режиме «по горизонтали — вниз» (в режиме 6) может быть выражен следующими уравнениями:pred4 times;4L'[0,0] = (p[-1,-1]+p[1-,0]+ 1) gt; gt;1pred4 times;4L'[0,1]= (p[-1,0] +p [-1,1]+1) gt; gt;1pred4 times;4L'[0,2] = (p[-1,1]+p[-1,2]+1) gt; gt;1pred4 times;4L'[0,3] = (p[-1,2]+p[-1,3]+1) gt; gt;1pred4 times;4L'[1,0] = (p[0,-1]+p[0,0]+1) gt; gt;1pred4 times;4L'[1,1] = (p[0,0]+p[0,1]+1) gt; gt;1pred4 times;4L'[1,2] = (p[0,1]+p[0,2]+1) gt; gt;1pred4 times;4L'[1,3] = (p[0,2]+p[0,3]+1) gt; gt;1pred4 times;4L'[2,0] = (p[1,-1]+p[1,0]+1) gt; gt;1pred4 times;4L'[2,1] = (p[1,0]+p[1,1]+1) gt; gt;1pred4 times;4L'[2,2] = (p[1,1]+p[1,2]+1) gt; gt;1pred4 times;4L'[2,3] = (p[1,2]+p[1,3]+1) gt; gt;1pred4 times;4L'[3,0] = (p[2,-1]+p[2,0]+1) gt; gt;1pred4 times;4L'[3,1] = (p[2,0]+p[2,1]+1) gt; gt;1pred4 times;4L'[3,2] = (p[2,1]+p[2,2]+1) gt; gt;1pred4 times;4L'[3,3] = (p[2,2]+p[2,3]+1) gt; gt;1На Фиг.3G проиллюстрировано предсказание элементов изображения из блока информации о яркости и блока G в режиме «по вертикали — влево» (в режиме 7).Элемент «a» 362 изображения предсказывают исходя из значения (A+B+1)/2, которое сформировано с использованием значений элементов, расположенных в диагональном направлении под углом 22,5 deg; от вертикали, указанном на Фиг.3G стрелками, а элемент «e» 364 изображения предсказывают исходя из значения (a+b+1)/2, которое сформировано с использованием значений соседних элементов изображения, расположенных в блоке 300 изображения рядом с элементом «e» 364 изображения в направлении стрелки под углом 22,5 deg; от вертикали. К тому же, элемент «i» 366 изображения предсказывают исходя из значения (e+f+1)/2, а элемент «m» 368 изображения предсказывают исходя из значения (i+j+1)/2.Таким же самым образом, элемент «b» изображения предсказывают исходя из значения (B+C+1)/2, элемент «c» изображения — исходя из значения (C+D+1)/2, элемент «d» изображения — исходя из значения (D+E+1)/2, элемент «f» изображения — исходя из значения (b+c+1)/2, элемент «g» изображения — исходя из значения (c+d+1)/2, элемент «h» изображения — исходя из значения элемента «d» изображения, элемент «j» изображения — исходя из значения (f+g+1)/2, элемент «k» изображения — исходя из значения (g+h+1)/2, элемент «l» изображения — исходя из значения элемента «h» изображения, элемент «n» изображения — исходя из значения (j+k+1)/2, элемент «o» изображения — исходя из значения (k+l+1)/2 и элемент «p» изображения — исходя из значения элемента «l» изображения. Способ предсказания элементов изображения в режиме «по вертикали — влево» (в режиме 7) может быть выражен следующими уравнениями:pred4 times;4L'[0,0] = (p[0,-1]+p[1,-1]+1) gt; gt;1pred4 times;4L'[1,0] = (p[1,-1]+p[2,-1]+1) gt; gt;1pred4 times;4L'[2,0] = (p[2,-1]+p[3,-1]+1) gt; gt;1pred4 times;4L'[3,0] = (p[3,-1]+p[4,-1]+1) gt; gt;1pred4 times;4L'[0,1] = (p[0,0]+p[1,0]+1) gt; gt;1pred4 times;4L'[1,1] = (p[1,0]+p[2,0]+1) gt; gt;1pred4 times;4L'[2,1] = (p[2,0]+p[3,0]+1) gt; gt;1pred4 times;4L'[3,1] = p[3,0]pred4 times;4L'[0,2] = (p[0,1]+p[1,1]+1) gt; gt;1pred4 times;4L'[1,2] = (p[1,1]+p[2,1]+1) gt; gt;1pred4 times;4L'[2,2] = (p[2,1]+p[3,1]+1) gt; gt;1pred4 times;4L'[3,2] = p[3,1]pred4 times;4L'[0,3] = (p[0,2]+p[1,2]+1) gt; gt;1pred4 times;4L'[1,3] = (p[1,2]+p[2,2]+1) gt; gt;1pred4 times;4L'[2,3] = (p[2,2)+p[3,2]+1) gt; gt;1pred4 times;4L'[3,3] = p[3,2]На Фиг.3H проиллюстрировано предсказание элементов изображения из блока информации о яркости и блока G в режиме «по горизонтали — вверх» (в режиме 8).Элемент «a» 372 изображения предсказывают исходя из значения (I+J+1)/2, которое сформировано с использованием значений элементов, расположенных в диагональном направлении под углом 22,5 deg; от горизонтали, указанном на Фиг.3H стрелками, а элемент «b» 374 изображения предсказывают исходя из значения (a+e+1)/2, которое сформировано с использованием значений соседних элементов изображения, расположенных в блоке 300 изображения рядом с элементом «b» 374 изображения в направлении стрелки под углом 22,5 deg; от горизонтали. Элемент «c» 376 изображения также предсказывают исходя из значения (b+f+1)/2, а элемент «d» 378 изображения предсказывают исходя из значения (c+g+1)/2.Таким же самым образом, элемент «e» изображения предсказывают исходя из значения (J+K+1)/2, элемент «i» изображения — исходя из значения (K+L+1)/2, элемент «m» изображения — исходя из значения элемента «L» изображения, элемент «f» изображения — исходя из значения (e+i+1)/2, элемент «j» изображения — исходя из значения (i+m+1)/2, элемент «n» изображения — исходя из значения элемента «m» изображения, элемент «g» изображения — исходя из значения (f+j+1)/2, элемент «k» изображения — исходя из значения (j+n+1)/2, элемент «o» изображения — исходя из значения элемента «n» изображения, элемент «h» изображения — исходя из значения (g+k+1)/2, элемент «l» изображения — исходя из значения (k+o+1)/2 и элемент «p» изображения — исходя из значения элемента «o» изображения. Способ предсказания элементов изображения в режиме «по горизонтали — вверх» (в режиме 8) может быть выражен следующими уравнениями:pred4 times;4L'[0,0] = (p[-1,0]+p[-1,1]+1) gt; gt;1pred4 times;4L'[0,1] = (p[-1,1] +p[-1,2]+1) gt; gt;1pred4 times;4L'[0,2] = (p[-1,2] +p[-1,3]+1) gt; gt;1pred4 times;4L'[0,3]= p[-1,3]pred4 times;4L'[1,0] = (p[0,0]+p[0,1]+1) gt; gt;1pred4 times;4L'[1,1] = (p[0,1]+p[0,2]+1) gt; gt;1pred4 times;4L'[1,2] = (p[0,2]+p[0,3]+1) gt; gt;1pred4 times;4L'[1,3] = p[0,3]pred4 times;4L'[2,0] = (p[1,0]+p[1,1]+1) gt; gt;1pred4 times;4L'[2,1] = (p[1,1]+p[1,2]+1) gt; gt;1pred4 times;4L'[2,2] = (p[1,2]+p[1,3]+1) gt; gt;1pred4 times;4L'[2,3] = p[1,3]pred4 times;4L'[3,0] = (p[2,0]+p[2,1]+1) gt; gt;1pred4 times;4L'[3,1] = (p[2,1]+p[2,2]+1) gt; gt;1pred4 times;4L'[3,2] = (p[2,2]+p[2,3]+1) gt; gt;1pred4 times;4L'[3,3] = p[2,3]Наконец, в режиме «постоянная составляющая» («постоянная составляющая» (DC)) (в режиме 2), все элементы изображения в предсказываемом блоке 300 предсказывают исходя из значения (A+B+C+D+I+J+K+L+4)/8, которое сформировано с использованием значений элементов изображения в блоках, соседних с блоком 300.До сих пор в качестве примеров было приведено описание предсказания элементов изображения из блока информации о яркости и блока G с размером блока, равным 4 times;4 элемента. Однако, когда размер блока информации о яркости равен 8 times;8 элементов или 16 times;16 элементов, то описанный выше способ предсказания элементов изображения из блока информации о яркости также может быть применен тем же самым образом. Например, когда режимом для блока 8 times;8 элементов является режим «по вертикали», описанный со ссылкой на Фиг.3A, то каждый элемент изображения предсказывают исходя из значения ближайшего соседнего элемента изображения в вертикальном направлении. Соответственно, единственное различие состоит в том, что размер блока равен 8 times;8 элементов или 16 times;16 элементов, и за исключением того, что предсказание элемента изображения является таким же, как и в режиме «по вертикали» для блока 4 times;4 элемента.Между тем, в дополнение к элементам изображения, сформированным имеющими яркость и цветность, для блока, характеризующего красный цвет (блока R), и блока, характеризующего синий цвет (блока B), из блоков R, G (характеризующего зеленый цвет) и B, может быть применен описанный ниже способ предсказания элементов изображения для элемента изображения, характеризующего цветность.Ниже приведено подробное объяснение вычисления элементов изображения для блока информации о цветности, блока R и блока B, со ссылкой на чертежи Фиг.4A — Фиг.4C.Предсказание элементов изображения из блока информации о цветности, блока R и блока B выполняют по единичным блокам 8 times;8 элементов, и существует 4 режима предсказания, но в настоящем изобретении плоскостной режим (plane mode) не используют. Следовательно, в настоящем изобретении используют только следующие режимы: режим «постоянная составляющая» (DC) (режим 0), режим «по горизонтали» (режим 1) и режим «по вертикали» (режим 2).На Фиг.4A проиллюстрировано предсказание элементов изображения из блока информации о цветности, блока R и блока B в режиме «постоянная составляющая» (DC).На чертежах Фиг.4A — Фиг.4C проиллюстрировано предсказание для блоков размером 8 times;8 элементов, но при выполнении предсказания элементов изображения в блоке информации о цветности, блоке R и блоке B, такое предсказание элементов изображения может быть аналогичным образом применено и для блока размером M times;N элементов.Со ссылкой на Фиг.4A, элементы a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, l1, m1, n1, o1 и p1 изображения, все из которых представляют собой элементы изображения в блоке 410 4 times;4 элемента из блока 400 8 times;8 элементов, предсказывают исходя из значения (A+B+C+D+I+J+K+L+4)/8. Элементы a2, b2, c2, d2, e2, f2, g2, h2, i2, j2, k2, l2, m2, n2, o2 и p2 изображения также предсказывают исходя из значения (E+F+G+H+2)/4. К тому же, элементы a3, b3, c3, d3, e3, f3, g3, h3, i3, j3, k3, l3, m3, n3, o3 и p3 изображения также предсказывают исходя из значения (M+N+O+P+2)/4, а элементы a4, b4, c4, d4, e4, f4, g4, h4, i4, j4, k4, l4, m4, n4, o4 и p4 изображения предсказывают исходя из значения (E+F+G+H+M+N+O+P+4)/8.На Фиг.4B проиллюстрировано предсказание элементов изображения из блока информации о цветности, блока R и блока B в режиме «по горизонтали».Элемент a1 изображения предсказывают исходя из элемента I изображения, элемент b1 изображения — исходя из элемента a1 изображения, а элемент c1 изображения — исходя из элемента b1 изображения. Таким образом, предсказание выполняют с использованием соседнего элемента изображения в горизонтальном направлении в предсказываемом блоке 400.На Фиг.4C проиллюстрировано предсказание элементов изображения из блока информации о цветности, блока R и блока B в режиме «по вертикали».Элемент a1 изображения предсказывают исходя из элемента A изображения, элемент e1 изображения — исходя из элемента a1 изображения, а элемент i1 изображения — исходя из элемента e1 изображения. Таким образом, предсказание выполняют с использованием соседнего элемента изображения в вертикальном направлении в предсказываемом блоке 400.Выше описано, что предсказание элементов изображения выполняют с использованием соседних элементов изображения в каждом из единичных блоков 4 times;4 элемента при предсказании блока информации о яркости и блока G и выполняют с использованием соседних элементов изображения в каждом из единичных блоков 8 times;8 элементов при предсказании блока информации о цветности, блока R и блока B. Однако, способ предсказания не ограничен блоком 4 times;4 элемента или блоком 8 times;8 элементов и может быть в равной степени применен к блокам произвольного размера из M times;N элементов изображения. То есть, даже в том случае, когда единичным предсказываемым блоком является блок из М times;N элементов изображения, предсказываемое значение элемента изображения может быть вычислено с использованием элемента изображения, ближайшего к значению элемента изображения в направлении предсказания в блоке.На Фиг.5 проиллюстрирован способ предсказания при выполнении кодирования и декодирования в вышеупомянутых режимах.Теперь, со ссылкой на Фиг.5, приведено объяснение другого способа получения разности путем предсказания элементов изображения. В обычном устройстве кодирования для получения разностного значения используют элемент изображения в соседнем блоке. Например, в режиме «по вертикали», показанном на Фиг.3A, в обычном способе, все из следующих элементов изображения: элемент «a» 302 изображения, элемент «e» 304 изображения, элемент «i» 306 изображения и элемент «m» 308 изображения, предсказывают исходя из элемента «A» изображения, и, следовательно, разностными значениями являются r0=a-A, r1=e-A, r2=i-A и r3=m-A. В настоящем изобретении, используя полученные таким способом обычные разностные значения, вычисляют новые разностные значения. Итак, новыми разностными значениями являются следующие: r’0=r0, r’1=r1-r0, r’2=r2-r1 и r’3=r3-r2. При этом, поскольку новые разностные значения r’0, r’1, r’2 и r’3 равны r’0=a-A, r’1=e-a, r’2=i-e и r’3=m-i, то r’0, r’1, r’2 и r’3 имеют те же самые значения, что и разностные значения, предсказанные исходя из ближайших соседних элементов изображения согласно вышеописанному способу предсказания. Следовательно, с новыми разностными значениями r’0, r’1, r’2 и r’3 в каждом из вышеописанных режимов может быть применен способ предсказания элементов изображения с использованием соседнего элемента изображения.Соответственно, модуль 110 предсказания движения, входящий в состав устройства кодирования из настоящего изобретения, показанного на Фиг.1, может дополнительно содержать модуль вычисления разностного значения, осуществляющий генерацию новых значений r’0, r’1, r’2 и r’3 элементов изображения из разностей.На Фиг.6 изображена блок-схема устройства декодирования согласно варианту осуществления настоящего изобретения, который приведен в качестве примера.Модуль 610 энтропийного декодирования принимает поток битов, закодированный согласно настоящему изобретению, и выполняет декодирование согласно способу энтропийного декодирования, например, контекстно-адаптивное кодирование кодами переменной длины (CAVLC) или контекстно-адаптивное двоичное арифметическое кодирование (CABAC). В передней части принятого потока битов может быть установлен флаг, указывающий, что значения элементов изображения предсказаны согласно настоящему изобретению. В качестве примера этого флага, в стандарте H.264 предусмотрен флаг lossless_qpprime_y_zero_flag.Путем использования этого флага, в модуль 620 восстановления видеоинформации передает информацию о том, что значения элементов изображения предсказаны согласно настоящему изобретению.Согласно этой информации, содержащейся во флаге, и информации о режиме кодирования, модуль 620 восстановления видеоинформации восстанавливает видеоинформацию согласно способу вычисления предсказания элементов изображения в режиме из настоящего изобретения и выводит результат.На Фиг.7 изображена схема последовательности операций способа кодирования согласно настоящему изобретению.Как описано выше, предсказание движения выполняют в различных режимах внутреннего предсказания, предусмотренных согласно видоизмененным способам предсказания, и при операции S710 определяют оптимальный режим. Кроме того, не используя видоизмененные способы предсказания, блок формируют с использованием разностных значений, заново сгенерированных из разностей, полученных обычным способом предсказания, и затем может быть выполнено предсказание движения в режиме кодирования с внутренним предсказанием. Оптимальный режим может быть реализован путем оптимизации искажений в зависимости от скорости передачи (RD), и поскольку в настоящем изобретении использовано кодирование без потерь, то один режим кодирования определяется оптимизацией скорости передачи. При операции S720 выполняют предсказание движения в определенном таким образом режиме кодирования. Затем при операции S730 выполняют энтропийное кодирование результирующего значения и его вывод.Декодирование выполняют в порядке, обратном кодированию. То есть, вводят поток битов, закодированный способом энтропийного кодирования, и выполняют его энтропийное декодирование. Затем на основании информации о режиме кодирования и информации, содержащейся во флаге, выполняют восстановление значений элементов изображения согласно способу вычисления предсказанных значений элементов изображения из настоящего изобретения и вывод видеоинформации.При этом, восстановленные значения элементов изображения могут быть выражены следующими уравнениями:(1) Если при выполнении кодирования использован видоизмененный способ предсказания, описанный выше, и режим кодирования определен как режим «по вертикали», то восстановление значений элементов изображения производят согласно следующему уравнению:uij = predL[x0+j,y0+i]+ i,j=0, …,3 илиuij = predL'[x0+j,y0]+ i,j=0, …,3.(2) Если при выполнении кодирования использован видоизмененный способ предсказания, описанный выше, и режим кодирования определен как режим «по горизонтали», то восстановление значений элементов изображения производят согласно следующему уравнению:uij = predL[x0+j,y0+i]+ i,j=0, …,3 илиuij = predL'[x0+j,y0]+ i,j=0, …,3.(3) Если при выполнении кодирования использован видоизмененный способ предсказания, описанный выше, и режим кодирования определен как режим «по диагонали вниз влево», то восстановление значений элементов изображения производят согласно следующему уравнению:Если i=0 ((i,j)=(0,0), (0,1), (0,2), (0,3)), тоuij = predL'[x0+j,y0+i]+ri,j,если i=1, j lt;3 ((i,j)=(1,0), (1,1), (1,2)), тоuij = predL'[x0+j+1,y0+i-1]+ri-1,j+1,если i=1, j=3 ((i,j)=(1,3)), тоuij = predL'[x0+j,y0+i-1]+ri-1,j+ri,j,если i=2, j lt;2 ((ij)=(2,0), (2,1)), тоuij = predL'[x0+j+2,y0+i-2]+ri-2,j+2+ri-1,j+1+ri,j,если i=2, j=2 ((i,j)=(2,2)), тоuij = predL'[x0+j+1,y0+i-2]+ri-2,j+1+ri-1,j-1+ri,j,если i=2, j=3 ((i,j)=(2,3)), тоuij = predL'[x0+j, y0+i-2]+ri-2,j+ri-1,j+ri,j,если i=3, j=0 ((i,j)=(3,0)), тоuij = predL'[x0+j+3,y0+i-3]+ri-3,j+3+ri-2,j+2+ri-1,j+1+ri,j,если i=3, j=1 ((i,j)=(3,1)), тоuij = predL'[x0+j+2, y0+i-3]+ri-3,j+2+ri-2,j+2+ri-1,j+1+ri,j,если i=3, j=2 ((i,j)=(3,2)), тоuij = predL'[x0+j+1,y0+i-3]+ri-3,j+1+ri-2,j+1+ri-1,j+1+ri,j,если i=3, j=3 ((i,j)=(3,3)), тоuij = predL'[x0+j,y0+i-3]+ri-3,j+ri-2,j+ri-1,j+ri,j.(4) Если при выполнении кодирования использован видоизмененный способ предсказания, описанный выше, и режим кодирования определен как режим «по диагонали вниз вправо», то восстановление значений элементов изображения производят согласно следующему уравнению:Если i=0 или j=0 ((i,j)=(0,0), (0,1), (0,2), (0,3), (1,0), (2,0), (3,0)), тоuij = predL'[x0+j,y0+i]+ri,j,если i=1, j ge;1, илиесли j=1, i gt;1 ((i,j)=(1,1), (1,2), (1,3), (2,1), (3,1)), тоuij = predL'[x0+j,y0+i]+ri-1,j-1+ri,j,если i=2, j ge;2, илиесли j=2, i gt;2 ((i,j)=(2,2), (2,3), (3,2)), тоuij = predL'[x0+j,y0+i]+ri-2,j-2+ri-1,j-1+ri,j,если i=j=3 ((i,j)=(3,3)), тоuij = predL'[x0+j,y0+i]+ri-3,j-3+ri-2,j-2+ri-1,j-1+ri,j.(5) В остальных режимах восстановление значений элементов изображения производят согласно следующему уравнению:uij = predL[x0+j,y0+i]+ri,j.В результате экспериментов, проведенных в соответствии с вышеописанным способом, для различных испытательных изображений, предложенных согласно Объединенной модели типа 73 (JM73), которая разработана группой стандартизации H.264, было достигнуто продемонстрированное ниже улучшение эффективности сжатия. Условия эксперимента показаны в таблице 1.Таблица 1 hairsp;Изображение «News» (формат QCIF — 1/4 формата CIF по разрешению)Изображение «Container» (формат QCIF)Изображение «Foreman» (формат QCIF)Изображение «Silent» (формат QCIF)Изображение «Paris» (формат CIF)Изображение «Mobile» (формат CIF)Изображение «Tempete» (формат CIF)Весь кадр100 (10 Гц)100 (10 Гц)100 (10 Гц)150 (15 Гц)150 (15 Гц)300 (30 Гц)260 (30 Гц)УсловияОптимизация скорости передачи, контекстно-адаптивное кодирование кодами переменной длины (CAVLC) или контекстно-адаптивное двоичное арифметическое кодирование (CABAC), режим внутреннего кодирования по блокам 4 times;4 элемента изображенияДля всех семи испытательных изображений были проведены эксперименты с движущимися изображениями на частоте 10 Гц, 15 Гц и 30 Гц различными способами с количеством кадров от 100 до 300 кадров. В таблице 2 приведено сравнение коэффициентов сжатия при сжатии испытательных изображений, соответственно, обычным способом сжатия и способом сжатия из настоящего изобретения (обозначенным как НИ) при условиях эксперимента, показанных в таблице 1.Таблица 2Изобра-жениеИсходный размер(в битах)СпособКонтекстно-адаптивное двоичное арифметическое кодирование (CABAC)Контекстно-адаптивное кодирование кодами переменной длины (CAVLC)Общее количество битовСжатиеОтносительное количество битов (%)Общее количество битовСжатиеОтносительное количество битов (%)News(300 кадров)91238400JM73490628321,8596100527301841,7303100НИ419090162,177185,4191450489122,025385,4329Container(300 кадров)91233400JM7347865761,9073100519763081,7554100НИ422144962,161388,2473457966561,992388,1098Foreman(300 кадров)91233400JM73504183121,8096100549973441,6590100НИ451265842,021889,5044489812721,862789,0612Silent(300 кадров)91238400JM73542730641,6811100597048321,5282100НИ477613921,910388,0020515956401,768386,4179Paris(300 кадров)364953600JM732247669121,62371002437633121,4972100НИ1940103521,881186,31622092445601,744185,8392Mobile(300 кадров)364953600JM732854236321,27861003103196801,1761100НИ2571436881,419390,09192765172801,319889,1072Tempete(260 Frames)316293120JM732058171921,53681002252914641,4039100НИ1831069681,727488,96581984724241,593688,0959Среднее значение hairsp;JM731310855031,67101001426833751,5357100НИ1158960711.899788,07811250938211,758087,4377Между тем, в таблице 2 показаны результаты для того случая, когда была произведена внутрикадровая генерация испытательных изображений с использованием только внутреннего предсказания, и, можно увидеть, что коэффициент сжатия является более высоким при использовании только внутреннего предсказания.При этом вышеописанный способ кодирования и декодирования видеоинформации может быть реализован в виде компьютерной программы. Коды и сегменты кода, образующие программу, могут быть легко получены компьютерными программистами, являющимися специалистами в области техники, к которой относится настоящее изобретение. К тому же, эта программа может быть запомнена в считываемом посредством компьютера носителе информации и может быть считана и выполнена компьютером таким образом, чтобы реализовать способ кодирования и декодирования видеоинформации. Носителем информации может являться магнитный носитель информации, оптический носитель информации или канал передачи на несущей.Несмотря на то что настоящее изобретение было подробно продемонстрировано и описано со ссылкой на варианты его осуществления, которые приведены в качестве примеров, для обычных специалистов в данной области техники понятно, что могут быть выполнены различные изменения формы и подробностей, не выходя за пределы сущности и объема настоящего изобретения, которые определены приведенной ниже формулой изобретения. Приведенные в качестве примера варианты осуществления изобретения следует расценивать только как изложенные в описательных целях, а не как ограничивающие. Следовательно, объем патентных притязаний настоящего изобретения определяется не приведенным выше подробным его описанием, а прилагаемой формулой изобретения, и вся различия в пределах объема патентных притязаний следует истолковывать как охватываемые настоящим изобретением.Согласно настоящему изобретению, описание которого приведено выше, может быть повышен коэффициент сжатия при выполнении кодирования без потерь. В частности, при использовании только режима внутреннего предсказания коэффициент сжатия является намного более высоким, чем при обычном способе.ПРИГОДНОСТЬ ДЛЯ ПРИМЕНЕНИЯ В ПРОМЫШЛЕННЫХ ЦЕЛЯХНастоящее изобретение может быть применено в устройстве кодирования и в устройстве декодирования видеоинформации без потерь для увеличения коэффициента сжатия.

Устройство и способ для шифрования/дешифрования

Изобретение относится к устройству и способу для шифрования/дешифрования сигнала в системе связи. Техническим результатом является создание устройства и способа для шифрования/дешифрования сигнала, которые позволяют избежать конфликта между начальными значениями счетчика, когда в современной системе связи IEEE 802.16 используется режим счетчика усовершенствованного стандарта шифрования (AES). Указанный результат достигается тем, что в системе связи генерируется вторая информация шифрования с использованием первой информации шифрования, когда генерируются данные для передачи. Данные зашифровываются с использованием второй информации шифрования и третьей информации шифрования, при этом первая информация шифрования соответствует счетчику прокрутки, причем счетчик прокрутки получает приращение при увеличении номера кадра системы связи, и третья информация шифрования представляет собой ключ шифрования графика (МТК) услуги групповой и широковещательной передачи (MBS). Генерируется и передается сигнал, содержащий зашифрованные данные и первую информацию шифрования. 4 н. и 8 з.п. ф-лы, 6 ил.

1. Способ передачи сигнала в системе связи, содержащий этапы генерации второй информации шифрования с использованием первой информации шифрования, когда генерируются данные для передачи; шифрования данных с использованием второй информации шифрования и третьей информации шифрования; и генерации и передачи сигнала, который включает в себя зашифрованные данные и первую информацию шифрования, при этом первая информация шифрования соответствует счетчику прокрутки, причем счетчик прокрутки получает приращение при увеличении номера кадра системы связи, и третья информация шифрования представляет собой ключ шифрования трафика (МТК) услуги групповой и широковещательной передачи (MBS).

2. Способ по п.1, в котором этап генерации второй информации шифрования содержит этап генерации второй информации шифрования путем конкатенации номера кадра и отсчета счетчика прокрутки и повторения результата конкатенации предварительно установленное число раз.

3. Способ по п.1, в котором данные представляют собой данные услуги MBS.

4. Устройство передачи сигнала в системе связи, содержащее генератор второй информации шифрования для генерации второй информации шифрования с использованием первой информации шифрования; блок шифрования для шифрования данных с использованием второй информации шифрования и третьей информации шифрования, когда генерируются данные, подлежащие передаче; и генератор сигнала для генерации сигнала, включающего в себя зашифрованные данные и первую информацию шифрования, и передатчик для передачи сигнала, при этом первая информация шифрования соответствует счетчику прокрутки, причем счетчик прокрутки получает приращение при увеличении номера кадра системы связи, и третья информация шифрования представляет собой ключ шифрования трафика (МТК) услуги групповой и широковещательной передачи (MBS).

5. Устройство по п.4, в котором генератор второй информации шифрования генерирует вторую информацию шифрования путем конкатенации номера кадра и отсчета счетчика прокрутки и повторения результата конкатенации предварительно установленное число раз.

6. Устройство по п.4, в котором данные представляют собой данные услуги MBS.

7. Способ передачи потоков услуги групповой и широковещательной передачи (MBS) в системе связи, включающий в себя этапы генерации начального значения счетчика с использованием номера кадра системы связи и счетчика прокрутки (ROC), для данных услуги MBS, подлежащих передаче; генерации n значений счетчика путем приращения на единицу начального значения счетчика; генерации n блоков шифрования с использованием n значений счетчика и ключа шифрования трафика (МТК) услуги MBS; сегментирования данных услуги MBS на n открытых текстов; генерации n потоков услуги MBS путем выполнения логических операций «исключающее ИЛИ» (XOR) над n открытыми текстами и блоками шифрования; и генерации n полезных данных услуги MBS, которые включают в себя один из n потоков услуги MBS и только отсчет ROC из отсчета ROC, начального значения счетчика и ключа МТК, соответственно, и передачи полезных данных услуги MBS.

8. Способ по п.7, в котором отсчет ROC получает приращение при увеличении номера кадра.

9. Способ по п.8, в котором этап генерации начального значения счетчика содержит этап генерации начального значения счетчика путем конкатенации номера кадра и отсчета счетчика прокрутки и повторения результата конкатенации предварительно установленное число раз.

10. Устройство передачи потоков услуги групповой и широковещательной передачи (MBS) в системе связи, содержащее генератор начального значения счетчика для генерации начального значения счетчика с использованием номера кадра системы связи и счетчика прокрутки (ROC); счетчик для генерации n значений счетчика путем приращения на единицу начального значения счетчика, для данных услуги MBS, подлежащих передаче; n генераторов блоков шифрования для генерации n блоков шифрования с использованием n значений счетчика и ключа шифрования трафика (МТК) услуги MBS, и n логических операторов «исключающее ИЛИ» (XOR) для выполнения логических операций «исключающее ИЛИ» над блоками шифрования и n открытыми текстами, на которые сегментированы данные услуги MBS, и генерации потоков услуги MBS, генератор полезных данных услуги MBS, для генерации n полезных данных MBS, которые включают в себя один из n потоков услуги MBS и только отсчет ROC из отсчета ROC, начального значения счетчика и ключа МТК, соответственно, и передатчик для передачи n сгенерированных полезных данных услуги MBS.

11. Устройство по п.10, в котором отсчет ROC получает приращение при увеличении номера кадра.

12. Устройство по п.10, в котором генератор начального значения счетчика генерирует начальное значение счетчика путем конкатенации номера кадра и отсчета счетчика прокрутки и повторения результата конкатенации предварительно установленное число раз.

Область техники

Настоящее изобретение относится к устройству и способу для шифрования/дешифрования сигнала в системе связи.

Предшествующий уровень техники

Обширные исследования проводятся для создания систем связи следующего поколения для обеспечения пользователей услугами на основе различного качества обслуживания (QoS) на высокой скорости передачи данных.Системы связи беспроводной локальной сети (LAN) и системы связи городской сети (MAN) поддерживают высокую скорость передачи данных. Система связи беспроводной сети MAN служит в качестве системы связи широкополосного беспроводного доступа (BWA) и поддерживает более широкую зону обслуживания и более высокую скорость передачи, чем система связи беспроводной сети LAN. При разработках системы связи следующего поколения обширные исследования проводятся для создания новой системы связи, обеспечивающей мобильность и качество обслуживания (QoS) для абонентских станций (SS) в системах связи сети LAN и сети MAN для достижения относительно высокой скорости передачи, в частности, таким образом, чтобы могли поддерживаться высокоскоростные услуги, обеспечиваемые системой связи следующего поколения.Система для использования мультиплексирования с ортогональным частотным разделением (OFDM) и множественного доступа с ортогональным частотным разделением (OFDMA) для поддержки сети широкополосной передачи в физическом канале системы связи беспроводной сети MAN основана на стандарте связи IEEE (Института инженеров по электротехнике и электронике) 802.16, далее упоминаемой как система связи IEEE 802.16. Поскольку система связи IEEE 802.16 использует схему OFDM/OFDMA в системе связи беспроводной сети MAN, сигнал физического канала может передаваться на множестве поднесущих, и поэтому могут передаваться высокоскоростные данные. Для удобства объяснения система связи IEEE 802.16 будет описана на примере системы связи широкополосного беспроводного доступа (BWA).Как описано выше, обширные исследования проводятся для обеспечения высокоскоростной передачи в системе связи IEEE 802.16, более конкретно, для обеспечения услуги групповой и широковещательной передачи (MBS), которая может обеспечивать множество абонентских станций SS идентичной услугой при минимизации ресурсов. Провайдеры услуг MBS должны учитывать аутентификацию пользователей и расчет за услуги. Для выполнения аутентификации пользователей и расчетов за услуги для абонентской станции SS, принимающей данные услуги MBS, момент времени, когда абонентская станция SS начинает принимать данные услуги MBS, и момент времени, когда прием данных услуги MBS останавливается, должны быть корректно определены. Для этого передатчик (например, базовая станция (BS)) для передачи данных услуги MBS зашифровывает данные услуги MBS, так что данные услуги MBS могут приниматься только в приемниках (например, абонентских станциях SS), и за эту услугу может начисляться оплата. При приеме данных услуги MBS, абонентские станции SS должны дешифровать зашифрованные данные услуги MBS. Базовая станция BS должна посылать дешифрованную информацию к абонентским станциям SS, так что они принимают и дешифруют данные услуги MBS, зашифрованные базовой станцией BS.Операция шифрования/дешифрования в режиме счетчика усовершенствованного стандарта шифрования (AES) (CTR) для определения схем шифрования и дешифрования, используемая в системе связи IEEE 802.16, описана ниже со ссылкой на фиг.1 и фиг.2.Фиг.1 иллюстрирует формат полезной нагрузки услуги MBS, используемый в обычной системе связи IEEE 802.16.Согласно фиг.1 полезная нагрузка услуги MBS включает в себя обычное поле 111 заголовка управления доступом к среде передачи (МАС) (GMH), поле 113 случайного слова (NONCE), поле 115 потока услуги MBS и поле 117 проверки циклическим избыточным кодом (CRC).Поле 111 заголовка GMH включает в себя заголовок GMH, служащий заголовком МАС с предварительно установленной длиной. Поле 113 NONCE включает в себя случайное слово, используемое для генерации начального значения счетчика в режиме AES-CRT. Поле 115 потока услуги MBS включает в себя поток услуги MBS. Поле 117 CRC включает в себя значение CRC для проверки ошибки в полезной нагрузке услуги MBS. Поток услуги MBS, включенный в поле 115 потока услуги MBS, генерируется из зашифрованных данных услуги MBS. Предпочтительным образом, размер случайного слова идентичен размеру данных услуги MBS перед шифрованием. Однако размер случайного слова необязательно должен быть идентичным размеру данных услуги MBS перед шифрованием. В системе связи IEEE 802.16 размер случайного слова установлен на 32 бита.На фиг.2 показана блок-схема, иллюстрирующая структуру устройства шифрования в режиме AES-CRT обычной системы связи IEEE 802.16.Согласно фиг.2 устройство шифрования AES-CRT включает в себя блок 200 шифрования AES-CRT и генератор 211 начального значения счетчика. Блок 200 шифрования AES-CRT включает в себя счетчик 213, n генераторов блоков шифрования, то есть c первого по n-ый генераторы 215-1…215-n блоков шифрования и n логических операторов «исключающее ИЛИ» (XOR), т.е. с первого по n-ый логические операторы 217-1…217-n «исключающее ИЛИ» (XOR).Данные услуги MBS, подлежащие передаче, случайное слово, ключ шифрования трафика услуги MBS (МТК) вводятся в блок 200 шифрования AES-CRT, когда генерируются данные услуги MBS, подлежащие передаче. Данные услуги MBS сегментируются на n фрагментов открытого текста, т.е. с первого по n-ый открытые тексты. Каждый из n открытых текстов вводится в ассоциированный логический оператор «исключающее ИЛИ». То есть первый открытый текст вводится в первый логический оператор 217-1 «исключающее ИЛИ». Таким же способом, n-ый открытый текст вводится в n-ый логический оператор 217-n «исключающее ИЛИ». Случайное число устанавливается на 32-битовое случайное число в современной системе связи IEEE 802.16. 32-битовое случайное слово вводится в генератор 211 начального значения счетчика. Ключ МТК вводится в генераторы 215-1…215-n блоков шифрования с 1-го по n-ый.Генератор 211 начального значения счетчика принимает случайное слово и генерирует 128-битовое начальное значение счетчика путем повторения принятого случайного слова предварительно установленное число раз, например, четыре раза. Затем генератор 211 начального значения счетчика выводит сгенерированное начальное значение счетчика на счетчик 213. Счетчик 213 получает начальное значение счетчика с генератора 211 начального значения счетчика и сообщает приращение начальному значению счетчика на единицу, n раз, тем самым генерируя n значений счетчика. Счетчик 213 выводит каждое из n значений счетчика на ассоциированный генератор блока шифрования. То есть, счетчик 213 выводит на первый генератор 215-1 блока шифрования первое значение счетчика, генерированное путем приращения начального значения счетчика на единицу. Счетчик 213 выводит на второй генератор 215-2 блока шифрования второе значение счетчика, генерированное приращением начального значения счетчика на два. Таким способом счетчик 213 выводит на n-ый генератор 215-n блока шифрования n-ое значение счетчика, генерированное путем приращения начального значения счетчика на n.Каждый из n генераторов блоков шифрования принимает ключ МТК и значение счетчика, выведенное со счетчика 213, генерирует блок шифрования и выводит сгенерированный блок шифрования на ассоциированный логический оператор «исключающее ИЛИ». То есть первый генератор 215-1 блока шифрования генерирует первый блок шифрования с использованием ключа МТК и первого значения счетчика, выведенного со счетчика 213, и затем выводит сгенерированный блок шифрования на первый логический оператор 217-1 «исключающее ИЛИ». Таким же способом, n-ый генератор 215-n блока шифрования генерирует n-ый блок шифрования с использованием ключа МТК и n-го значения счетчика, выведенного со счетчика 213, и затем выводит сгенерированный блок шифрования на n-ый логический оператор 217-n «исключающее ИЛИ».Каждый из n логических операторов «исключающее ИЛИ» принимает ассоциированный открытый текст и блок шифрования, выведенный из ассоциированного генератора блока шифрования, выполняет логическую операцию «исключающее ИЛИ» над открытым текстом и блоком шифрования и генерирует и выводит поток услуги MBS. То есть первый логический оператор 217-1 «исключающее ИЛИ» принимает первый открытый текст и первый блок шифрования, выведенный из первого генератора 215-1 блока шифрования, выполняет логическую операцию «исключающее ИЛИ» над первым открытым текстом и первым блоком шифрования и генерирует и выводит первый поток услуги MBS. Аналогичным способом, n-ый логический оператор 217-n «исключающее ИЛИ» принимает n-ый открытый текст и n-ый блок шифрования, выведенный из n-го генератора 215-n блока шифрования, выполняет логическую операцию «исключающее ИЛИ» над n-ым открытым текстом и n-ым блоком шифрования и генерирует и выводит n-ый поток услуги MBS.Поскольку блок шифрования AES-CTR использует идентичный ключ МТК, как описано выше, более стабильное шифрование t может быть выполнено путем смены начального значения счетчика в течение временного интервала, использующего идентичный ключ МТК. Поскольку современная система связи IEEE 802.16 генерирует случайное слово в форме случайного числа, первоначальное значение счетчика предыдущего временного интервала, прежде чем ключ МТК будет обновлен, может быть повторно использовано в последующем временном интервале. В этом случае стабильность операции шифрования не может быть гарантирована. Важно, чтобы можно было избежать повторения начального значения счетчика или конфликта между начальными значениями счетчика. Поскольку имеется возможность атаки для взлома шифра, когда начальное значение счетчика идентично во временном интервале, использующем идентичный ключ МТК, начальное значение счетчика не должно повторяться во временном интервале, использующем идентичный ключ МТК.Весьма важно, чтобы не только шифрование было устойчивым, но и объем данных, который должен дополнительно передаваться для шифрования и дешифрования, был минимизирован при рассмотрении эффективности системы в целом. Однако пропускная способность для данных снижается из-за случайного слова, поскольку 32-битовое случайное слово должно передаваться в каждом потоке услуги MBS, как в современной системе связи IEEE 802.16.

Сущность изобретения

Поэтому целью настоящего изобретения является создание устройства и способа для шифрования/дешифрования сигнала в системе связи.Другой целью настоящего изобретения является создание устройства и способа для шифрования/дешифрования сигнала, которые позволяют избежать конфликта между начальными значениями счетчика, когда в современной системе связи IEEE 802.16 используется режим счетчика усовершенствованного стандарта шифрования (AES) (CTR).Также целью настоящего изобретения является создание устройства и способа для шифрования/дешифрования сигнала, которые позволяют минимизировать передачу дополнительных данных, когда в современной системе связи IEEE 802.16 используется режим счетчика усовершенствованного стандарта шифрования (AES) (CTR).В соответствии с одним аспектом настоящего изобретения предусмотрено устройство для передачи сигнала в системе связи, включающее в себя генератор второй информации шифрования для генерации второй информации шифрования с использованием первой информации шифрования; блок шифрования для шифрования данных с использованием второй информации шифрования и третьей информации шифрования, когда генерируются данные, подлежащие передаче; и генератор сигнала для генерации и передачи сигнала, содержащего зашифрованные данные и первую информацию шифрования.В соответствии с другим аспектом настоящего изобретения предусмотрено устройство для передачи потоков услуги групповой и широковещательной передачи (MBS) в системе связи, содержащее генератор начального значения счетчика, предназначенный для генерации начального значения счетчика с использованием номера кадра системы связи и счетчика прокрутки (ROC); счетчик для генерации n значений счетчика путем приращения на единицу начального значения счетчика, когда генерируются данные услуги MBS для передачи; n генераторов блоков шифрования, предназначенных для генерации n блоков шифрования с использованием n значений счетчика и ключа шифрования трафика услуги MBS (МТК) и n логических операторов «исключающее ИЛИ» (XOR) для выполнения логических операций «исключающее ИЛИ» над блоками шифрования и n открытыми текстами, на которые сегментированы данные услуги MBS, и генерации потоков услуги MBS.В соответствии с другим аспектом настоящего изобретения предусмотрен способ передачи сигнала в системе связи, включающий в себя этапы генерации второй информации шифрования с использованием первой информации шифрования, когда генерируются данные для передачи; шифрования данных с использованием второй информации шифрования и третьей информации шифрования; и генерации и передачи сигнала, содержащего зашифрованные данные и первую информацию шифрования.В соответствии с еще одним аспектом настоящего изобретения предусмотрен способ передачи потоков услуги групповой и широковещательной передачи (MBS) в системе связи, включающий в себя этапы генерации начального значения счетчика с использованием номера кадра системы связи и счетчика прокрутки (ROC), когда генерируются данные услуги MBS для передачи; генерации n значений счетчика путем приращения на единицу начального значения счетчика; генерации n блоков шифрования с использованием n значений счетчика и ключа шифрования трафика услуги MBS (МТК); сегментирования данных услуги MBS на n открытых текстов; генерации потоков услуги MBS путем выполнения логических операций «исключающее ИЛИ» над n открытыми текстами и блоками шифрования; и генерации и передачи n полезных нагрузок услуги MBS, которые содержат один из n потоков услуги MBS и ROC, соответственно.

Краткое описание чертежей

Вышеописанные и другие цели и преимущества настоящего изобретения поясняются в последующем детальном описании, иллюстрируемом чертежами, на которых показано следующее:Фиг.1 — формат полезной нагрузки услуги MBS, используемый в обычной системе связи IEEE 802.16;Фиг.2 — блок-схема, иллюстрирующая структуру устройства шифрования режима счетчика усовершенствованного стандарта шифрования (AES) (CTR), используемого в режиме AES-CTR современной системы связи IEEE 802.16;Фиг.3 — блок-схема, иллюстрирующая устройство для передачи сигнала в системе связи IEEE 802.16 в соответствии с вариантом осуществления настоящего изобретения;Фиг.4 — формат нагрузки услуги MBS в соответствии с вариантом осуществления настоящего изобретения;Фиг.5 — блок-схема, иллюстрирующая структуру блока 400 шифрования AES-CTR по фиг.3; иФиг.6 — блок-схема, иллюстрирующая процесс шифрования AES-CTR системы связи IEEE 802.16 в соответствии с вариантом осуществления настоящего изобретения.

Детальное описание предпочтительных вариантов осуществления настоящего изобретения

Предпочтительные варианты осуществления настоящего изобретения детально описаны ниже со ссылками на иллюстрирующие чертежи. В последующем описании представлены только элементы, необходимые для понимания операций, согласно настоящему изобретению, а описание иных элементов опущено, в целях ясности и краткости.Настоящее изобретение предусматривает устройство и способ для шифрования/дешифрования сигнала в системе связи. Устройство и способ для шифрования/дешифрования сигнала, раскрытые в настоящем описании, основаны на системе связи IEEE 802.16, соответствующей, в качестве примера, системе связи с широкополосным беспроводным доступом (BWA). Устройство и способ для шифрования/дешифрования сигнала, предложенные в настоящем изобретении, могут быть применены в других системах связи, как и в системе связи IEEE 802.16.На фиг.3 представлена блок-схема, иллюстрирующая устройство для передачи сигнала в системе связи IEEE 802.16 в соответствии с вариантом осуществления настоящего изобретения.Согласно фиг.3 устройство для передачи сигнала содержит устройство шифрования режима счетчика усовершенствованного стандарта шифрования (AES) (CTR), используемого в режиме AES-CTR, и генератор 450 полезной нагрузки. Устройство шифрования AES-CTR содержит генератор 300 начального значения счетчика и блок 400 шифрования AES-CTR. Поскольку структура блока 400 шифрования AES-CTR подробно описана ниже со ссылкой на фиг.4 детальное описание блока шифрования AES-CTR здесь опущено.Активно проводились исследования для обеспечения услуги MBS системы связи IEEE 802.16. Поскольку данные услуги MBS должны зашифровываться и расшифровываться при передаче между передатчиком (например, базовой станцией (BS)) и приемниками (например, абонентскими станциями (SS)), чтобы могла быть обеспечена услуга MBS, определены режим AES-CTR и схемы шифрования и дешифрования для обеспечения услуги MBS. Базовая станция BS должна передавать информацию дешифрования к абонентским станциям SS, чтобы они могли дешифровать зашифрованные данные услуги MBS. В системе связи IEEE 802.16 данные, используемые для генерации начального значения счетчика, такие как информация дешифрования, должны быть включены и должны передаваться в нагрузке услуги MBS. Настоящее изобретение предусматривает счетчик прокрутки (ROC) для предоставления данных для генерации начального значения счетчика. Здесь счетчик ROC получает приращение всякий раз, когда увеличивается номер кадра, используемого на физическом уровне (PHY) системы связи IEEE 802.16. Например, счетчик ROC выражается 8 битами. В системе связи IEEE 802.16 номер кадра выражается 24 битами.Согласно настоящему изобретению генерируются 24 бита с использованием 8-битового счетчика ROC и 24-битового номера кадра; полученные 32 бита повторяются предварительно установленное количество раз, например, четыре раза, и генерируется 128-битовое начальное значение счетчика. В результате настоящее изобретение позволяет выполнять надежное шифрование и дешифрование, поскольку конфликт между начальными значениями счетчика не возникает ввиду смены номера кадра или отсчета счетчика ROC на временном интервале, использующем идентичный ключ шифрования трафика услуги MBS (MTK). То есть, надежные процедуры шифрования и дешифрования возможны, поскольку начальное значение счетчика не используется повторно, когда период, с которым обновляется ключ МТК, установлен на большее значение, чем период, с которым повторяется отсчет счетчика ROC.Согласно фиг.3 генератор 300 начального значения счетчика увеличивает значение ROC всякий раз, когда имеет место увеличение номера кадра физического уровня PHY системы связи IEEE 802.16. Генератор 300 начального значения счетчика выполняет конкатенацию 24-битового номера кадра и 8-битового отсчета ROC для генерации 32 битов и повторяет 32 бита четыре раза для генерации 128-битового начального значения счетчика. Затем генератор 300 начального значения счетчика выводит 128-битовое начальное значение счетчика на блок 400 шифрования AES-CTR. Кроме того, генератор 300 начального значения счетчика выводит отсчет ROC на генератор 450 полезной нагрузки услуги MBS.Когда данные услуги MBS, которые должны передаваться, сформированы, данные услуги MBS, ключ МТК и начальное значение счетчика вводятся в блок 400 шифрования AES-CTR. Блок 400 шифрования AES-CTR принимает данные услуги MBS, ключ МТК и начальное значение счетчика, шифрует данные услуги MBS для генерации потока услуги MBS и выводит генерированный поток услуги MBS на генератор 450 полезной нагрузки данные услуги MBS. Генератор 450 полезной нагрузки услуги MBS генерирует полезную нагрузку услуги MBS, включающую в себя поток услуги MBS, выведенный с блока 400 шифрования AES-CTR, и отсчет ROC, выведенный из генератора 300 начального значения счетчика. Структура передатчика для передачи полезной нагрузки услуги MBS не показана на фиг.3. Полезная нагрузка услуги MBS передается на абонентские станции SS посредством передатчика.На фиг.4 показан формат нагрузки услуги MBS в соответствии с вариантом осуществления настоящего изобретения. Согласно фиг.4 полезная нагрузка услуги MBS включает в себя обычное поле 411 заголовка управления доступом к среде передачи (МАС) (GMH), поле 413 ROC, поле 415 потока услуги MBS и поле 417 проверки циклическим избыточным кодом (CRC).Поле 411 заголовка GMH включает в себя заголовок GMH, соответствующий заголовку МАС с предварительно установленной длиной. Поле 413 ROC включает в себя отсчет ROC, используемый для генерации начального значения счетчика в режиме AES-CRT. Поле 415 потока услуги MBS включает в себя поток услуги MBS. Поле 417 CRC включает в себя значение CRC для проверки ошибки в полезной нагрузке услуги MBS. Поток услуги MBS, включенный в поле 415 потока услуги MBS, генерируется из зашифрованных данных услуги MBS. Размер ROC равен 8 битов, как описано выше. Поскольку размер ROC меньше, чем у 32-битового случайного слова, используемого для генерации начального значения счетчика в обычной системе связи IEEE 802.16, обеспечивается выигрыш в аспекте передачи данных.На фиг.5 показана блок-схема, иллюстрирующая структуру блока 400 шифрования AES-CTR по фиг.3.Согласно фиг.5 блок 400 шифрования AES-CRT включает в себя счетчик 412, n генераторов блоков шифрования, то есть c первого по n-ый генераторы 413-1…413-n блоков шифрования, и n логических операторов «исключающее ИЛИ» (XOR), то есть с первого по n-ый логические операторы 415-1…415-n «исключающее ИЛИ» (XOR).Данные услуги MBS, подлежащие передаче, начальное значение счетчика и ключ МТК вводятся в блок 400 шифрования AES-CRT, когда генерируются данные услуги MBS, подлежащие передаче. Данные услуги MBS сегментируются на n фрагментов открытого текста, то есть с первого по n-ый открытые тексты. Каждый из n открытых текстов вводится в ассоциированный логический оператор «исключающее ИЛИ». Первый открытый текст вводится в первый логический оператор 415-1 «исключающее ИЛИ». Таким же способом, n-ый открытый текст вводится в n-ый логический оператор 415-n «исключающее ИЛИ». Ключ МТК вводится в генераторы 413-1…413-n блоков шифрования с 1-го по n-ый.Счетчик 412 получает начальное значение счетчика и сообщает приращение начальному значению счетчика на единицу, n раз, тем самым генерируя n значений счетчика. Счетчик 412 выводит каждое из n значений счетчика на ассоциированный генератор блока шифрования. То есть, счетчик 412 выводит на первый генератор 413-1 блока шифрования первое значение счетчика, генерированное путем приращения начального значения счетчика на единицу. Счетчик 412 выводит на второй генератор 413-2 блока шифрования второе значение счетчика, генерированное приращением начального значения счетчика на два. Таким способом счетчик 412 выводит на n-ый генератор 413-n блока шифрования n-ое значение счетчика, генерированное путем приращения начального значения счетчика на n.Каждый из n генераторов блоков шифрования принимает ключ МТК и значение счетчика, выведенное со счетчика 412, генерирует блок шифрования и выводит сгенерированный блок шифрования на ассоциированный логический оператор «исключающее ИЛИ». Первый генератор 413-1 блока шифрования генерирует первый блок шифрования с использованием ключа МТК и первого значения счетчика, выведенного со счетчика 412, и затем выводит сгенерированный блок шифрования на первый логический оператор 415-1 «исключающее ИЛИ». Таким же способом, n-ый генератор 413-n блока шифрования генерирует n-ый блок шифрования с использованием ключа МТК и n-го значения счетчика, выведенного со счетчика 412, и затем выводит сгенерированный блок шифрования на n-ый логический оператор 415-n «исключающее ИЛИ».Каждый из n логических операторов «исключающее ИЛИ» принимает ассоциированный открытый текст и блок шифрования, выведенный из ассоциированного генератора блока шифрования, выполняет логическую операцию «исключающее ИЛИ» над открытым текстом и блоком шифрования и генерирует и выводит поток услуги MBS. Первый логический оператор 415-1 «исключающее ИЛИ» принимает первый открытый текст и первый блок шифрования, выведенный из первого генератора 413-1 блока шифрования, выполняет логическую операцию «исключающее ИЛИ» над первым открытым текстом и первым блоком шифрования и генерирует и выводит первый поток услуги MBS. Аналогичным способом, n-ый логический оператор 415-n «исключающее ИЛИ» принимает n-ый открытый текст и n-ый блок шифрования, выведенный из n-го генератора 413-n блока шифрования, выполняет логическую операцию «исключающее ИЛИ» над n-ым открытым текстом и n-ым блоком шифрования и генерирует и выводит n-ый поток услуги MBS в генератор 450 полезной нагрузки услуги MBS.На фиг.6 показана блок-схема, иллюстрирующая процесс шифрования AES-CTR системы связи IEEE 802.16 в соответствии с вариантом осуществления настоящего изобретения.Согласно фиг.6 устройство шифрования AES-CTR на этапе 611 генерирует n начальных значений счетчика с использованием номера кадра и отсчета ROC, когда вводятся данные услуги MBS для передачи. На этапе 613 устройство шифрования AES-CTR сегментирует данные услуги MBS для генерации n открытых текстов. На этапе 615 устройство шифрования AES-CTR генерирует n блоков шифрования с использованием n начальных значений счетчика и ключа МТК. На этапе 617 устройство шифрования AES-CTR генерирует n потоков услуги MBS путем выполнения операции «исключающее ИЛИ» над n открытыми текстами и n блоками шифрования, соответственно. Затем процесс завершается.Как видно из приведенного выше описания, настоящее изобретение обеспечивает возможность устойчивого шифрования/ дешифрования путем изменения начального значения счетчика для шифрования/дешифрования также во временном интервале, использующем идентичный ключ трафика услуги MBS (МТК). Настоящее изобретение предлагает использовать счетчик прокрутки (ROC), соответствующий дополнительным данным, подлежащим передаче для шифрования/дешифрования, тем самым снижая ухудшение пропускной способности для передачи данных, связанное с передачей дополнительных данных, и повышая общую пропускную способность для передачи данных.Хотя в иллюстративных целях выше раскрыты предпочтительные варианты осуществления настоящего изобретения, специалистам в данной области техники должно быть понятно, что возможны различные модификации, дополнения и замены, без отклонения от объема настоящего изобретения. Поэтому настоящее изобретение не ограничено вышеописанными вариантами осуществления, а определяется следующими пунктами формулы изобретения вместе с их полным объемом эквивалентов.

Способ фазового формирования нулей в

Изобретение относится к области антенной техники, а точнее к способам управления формой диаграммы направленности (ДН) фазированной антенной решетки (ФАР) путем изменения лишь фаз возбуждений элементов ФАР. Предлагается способ фазового формирования нулей в диаграмме направленности фазированной антенной решетки, содержащий поиск минимума положительно полуопределенного функционала Q, представляющего собой взвешенную сумму квадратов модулей значений ДН в одном или нескольких угловых направлениях, задающих координаты формируемых нулей, с помощью монотонно сходящейся итерационной покоординатной процедуры, на каждом шаге которой находится минимум взвешенной суммы Q по фазе возбуждения выбранного элемента ФАР и исходные значения комплексной ДН ФАР в направлениях формируемых нулей не вычисляют, а измеряют. При этом на каждом шаге итерационной процедуры определяют минимальное изменение ΔQ минимизируемой взвешенной суммы Q, которое необходимо обеспечить на данном шаге итерационной процедуры, причем величина ΔQ лежит в пределах 0<ΔQ≤ΔQmax, где ΔQmax - максимальное возможное изменение Q среди всех элементов ФАР, и для минимизации выбирают тот исправный элемент ФАР, который может уменьшить Q на величину, не меньшую ΔQ. 1 з.п. ф-лы, 1 табл. 1. Способ фазового формирования нулей в диаграмме направленности (ДН) фазированной антенной решетки (ФАР), содержащий определение комплексных значений ДН ФАР в одном или нескольких угловых направлениях, задающих координаты формируемых нулей, поиск значений фазовых сдвигов фазовращателей элементов ФАР, при которых обеспечивается минимум взвешенной суммы Q квадратов модулей значений ДН ФАР в этих направлениях, с помощью итерационной покоординатной процедуры, на каждом шаге которой выбирается один элемент ФАР и определяется фазовый сдвиг, который обеспечивает минимум взвешенной суммы Q по фазе возбуждения данного элемента ФАР, а фазовые сдвиги элементов ФАР, определенные с помощью такой процедуры, реализуются с помощью фазовращателей элементов ФАР, отличающийся тем, что исходные значения комплексной ДН ФАР в направлениях формируемых нулей измеряют и данные измерений используют в качестве начальной точки итерационной покоординатной процедуры минимизации взвешенной суммы Q, при этом на каждом шаге итерационной процедуры определяют минимальное изменение ΔQ минимизируемой взвешенной суммы Q, которое необходимо обеспечить на данном шаге итерационной процедуры, причем величина ΔQ лежит в пределах 0<ΔQ≤ΔQmax, где ΔQmax - максимальное возможное изменение взвешенной суммы Q среди всех элементов ФАР на данном шаге, и для минимизации взвешенной суммы Q на этом шаге выбирают тот элемент ФАР, который может уменьшить взвешенную сумму Q на величину, не меньшую ΔQ. 2. Способ по п.1, отличающийся тем, что в качестве элементов ФАР допускается использование групп элементов ФАР, каждая из которых управляется как один элемент. Область техникиИзобретение относится к области антенной техники, а точнее к способам управления формой диаграммы направленности (ДН) фазированной антенной решетки (ФАР) путем изменения лишь фаз возбуждений элементов ФАР.Уровень техникиФормирование идеальных нулей в ДН ФАР с использованием только фаз возбуждений элементов представляет собой сложную математическую задачу, которая в общем случае решается лишь приближенно с использованием численных методов [Зелкин Е.Г., Соколов В.Г. Методы синтеза антенн. — М.: Сов. радио, 1980. — 296 с]. В рамках этого направления известны способы формирования «неидеальных» нулей (точнее, глубоких провалов) в ДН ФАР, основанные на управлении исключительно фазами возбуждения элементов ФАР. Такие способы можно условно разделить на три группы. К первой группе относятся так называемые методы фазового синтеза, основанные на использовании численных процедур минимизации положительно полуопределенных функционалов общего вида [Зелкин Е.Г., Соколов В.Г. Методы синтеза антенн. — М.: Сов. радио, 1980. — 296 с]. Вторая группа способов — методы формирования нулей, основанные на использовании методов линеаризации [Steyskal H., Simple method for pattern nulling by phase perturbation // IEEE Trans. Antennas Propagat, 1983, vol. AP-31, pp.163-166]. К третьей группе способов относятся разнообразные эвристические подходы [Березенко А.И., Немировский Э.Э. Фазовый метод уменьшения бокового излучения в заданном направлении в линейке дискретных излучателей // Сборник научных трудов по проблемам микроэлектроники. — М.: МИЭТ, Вып.6., С.51-58]. Способы первой группы являются наиболее надежными и универсальными из вышеперечисленных подходов. Они позволяют сформировать нули или, как минимум, глубокие провалы ДН ФАР практически в любой помеховой ситуации. В то же время их недостатком является использование слишком универсальных алгоритмов, которые не учитывают специфики структуры минимизируемого функционала. Следствие этого — низкая скорость сходимости и чувствительность к погрешностям вычислений. Способы, относящиеся к остальным группам, являются неуниверсальными и имеют ограниченную область применимости.Способом, позволяющим сочетать свойства универсальности и надежности работы с учетом специфики структуры минимизируемого функционала, является так называемый покоординатный метод фазового синтеза [Кондратьев А.С. Метод фазового синтеза антенных решеток с учетом дополнительных требований к форме диаграммы направленности // Радиотехника и электроника, 1990, т.35, №12, с.2530-2540], который и является ближайшим аналогом заявляемого способа синтеза нулей. В этом способе минимизируется функционал Q, представляющий собой взвешенную сумму квадратов модулей значений комплексной ДН в L угловых направлениях (θl,φl), задающих координаты формируемых нулей: где Wl — положительные весовые множители, F(θl,φl) — значения комплексной ДН ФАР в направлениях формируемых нулей.Функционал (1) минимизируется с помощью монотонно сходящейся покоординатной итерационной процедуры, на каждом шаге которой находится минимум функционала (1) по фазе ψm возбуждения (тока или напряжения) выбранного (m-го) элемента ФАР по формуле Формула (2) представляет собой формулу (1), переписанную таким образом, что элементы функционала Qm и Вm не зависят от выбранной фазы. Анализ формулы (2) показывает, что минимум функционала Q по выбранной фазе ψm достигается, когда В силу периодичности фазы оба решения оказываются эквивалентными [1]. Покоординатный способ хорошо учитывает детерминированные погрешности установки фазы и амплитуды элементов ФАР. Известна [Хзмалян А.Д., Кондратьев А.С. Двухкоординатный метод фазового синтеза нулей диаграммы направленности антенной решетки // Радиотехника и электроника, 1996, т.41, №3 и Хзмалян А.Д., Кондратьев А.С. Быстродействующие алгоритмы фазового синтеза нулей в диаграмме направленности антенной решетки // Электромагнитные волны (журнал в журнале Радиотехника, 1996, №2)] оценка предельной глубины изолированного нуля, достижимой при использовании покоординатного способа формирования нулей, учитывающего наличие дискрета фазирования: где P(θо, φо) — оценка модуля ДН по мощности в точке формирования изолированного нуля, Δ — величина дискрета фазирования, а N — число элементов ФАР. Вместе с тем известно, что при реализации ДН ФАР на практике, как правило, появляются случайные погрешности (искажения) АФР. Влияние этих погрешностей выражается, в частности, в появлении случайного фона в ДН ФАР, который приводит к заплыванию нулей ДН, усредненной по ансамблю реализаций искажений АФР. В результате уровень средней ДН может быть оценен по следующей формуле, которая является обобщением формулы, приведенной в [Самойленко В.И., Шишов Ю.И. Управление фазированными антенными решетками. — М.: Радио и связь, 1983. — 240 с], на случай неизотропных элементов ФАР: где σψ — среднеквадратическое отклонение (СКО) относительных фазовых искажений, выраженных в радианах, σА- СКО относительных амплитудных искажений, FР(θо,φо)- значение нормированной ДН по мощности ФАР в отсутствие искажений АФР и Fel(θо,φо) — ДН элемента ФАР в составе решетки, усредненная на множестве элементов. В области нуля неискаженной ДН FР(θо,φо)=0. Сопоставление формул (4) и (5) показывает, что глубина изолированного нуля, связанная с наличием дискрета фазирования, обратно пропорциональна квадрату числа элементов ФАР. В то же время уровень фона ДН, вызванного случайными искажениями АФР, обратно пропорционален первой степени числа элементов ФАР. Поэтому в случае многоэлементной ФАР доминирующим оказывается фон, связанный с наличием случайных погрешностей АФР. Таким образом, наличие случайных погрешностей АФР может существенно снизить эффективность известных методов формирования нулей в ДН многоэлементных ФАР, в том числе известного покоординатного метода синтеза. В первую очередь снижение эффективности выражается в уменьшении достижимой глубины нуля (в среднем глубина нуля находится на уровне случайного фона ДН). Кроме того, в случае неисправности управления одним или несколькими элементами ФАР покоординатный способ может работать только в том случае, если известны не только номера, но и фазы возбуждений отказавших элементов. Заявляемый способ фазового синтеза нулей в ДН ФАР направлен на устранение этих недостатков. В частности, для успешной работы заявляемого способа достаточно знать только то, какие элементы отказали (без знания их фаз).Сущность изобретенияВ ближайшем аналоге вначале рассчитываются комплексные значения ДН ФАР в направлениях помех, причем в расчете участвуют теоретические значения амплитуд и фаз элементов ФАР, заданные без учета случайных погрешностей АФР. Затем на основании проведенных вычислений на некоторых элементах ФАР (при синтезе ограниченного числа нулей в боковых лепестках ДН число таких элементов намного меньше полного числа элементов ФАР) устанавливаются значения фаз, которые минимизируют эти комплексные значения ДН ФАР в математической модели. Если погрешности АФР отсутствуют, то нули, сформированные в реальной ДН ФАР, будут иметь глубины, весьма близкие к оценке, рассчитанной по формуле (4).При наличии случайных погрешностей АФР глубина нуля в многоэлементной ФАР может оказаться существенно меньше, чем оценка по формуле (4). При этом в процессе формирования нуля любым методом фазового синтеза можно выделить два пути влияния погрешностей, определяющих реально достижимую глубину нуля ДН ФАР. Первый — разница между расчетными комплексными значениями ДН ФАР в направлениях помех и их реальными значениями, обусловленная наличием случайных искажений АФР. Второй — наличие случайных погрешностей, возникающих при реализации фаз на элементах, которые используются для подавления помех. Вклад случайных искажений амплитуды и фазы возбуждения одного элемента ФАР в заплывание нуля ДН в обоих случаях одинаков. Важно отметить, что при формировании нулей за пределами главного лепестка ДН ФАР число элементов, вызывающих погрешности, связанные с разницей между расчетной и реальной комплексной ДН ФАР, намного превышает число элементов, вносящих погрешности при реализации фаз. Поэтому на практике доминирует погрешность, связанная с тем, что неточно известно комплексное значение ДН ФАР в направлении помехи, и если это значение измерить с высокой точностью, то можно существенно увеличить глубину синтезируемых нулей.Кроме того, важно снизить и второй фактор влияния случайных искажений АФР. Для этого число элементов, участвующих в формировании нулей, должно быть минимальным.Исходя из изложенного, предлагается следующий способ формирования глубоких нулей в ДН ФАР со случайными погрешностями АФР:1. Измеряют исходные значения комплексной ДН ФАР в направлениях помех.2. Используя измеренные значения комплексной ДН ФАР в качестве исходных данных, начинают итерационную процедуру минимизации функционала (1), на каждом шаге которой:2.1. Задаются минимальным изменением ΔQ минимизируемого функционала Q, которое необходимо обеспечить на данном шаге итерационной процедуры.2.2. Выбирают из исправных элементов один элемент ФАР, который может изменить функционал Q на величину, не меньшую ΔQ.2.3. Рассчитывают новую фазу этого элемента по формуле (3). Допускается реализация новой фазы элемента сразу после ее расчета, однако предпочтительным является реализация фаз на элементах, используемых в формировании нуля, после окончания итерационной процедуры.2.4. Рассчитывают новые значения ДН ФАР в направлениях формируемых нулей, соответствующие новой фазе выбранного элемента.3. Итерационную процедуру повторяют либо до достижения заданных глубин нулей, либо до стабилизации значений фаз (очередной шаг не приводит к изменению значений фаз элементов ФАР).Результат работы описанной выше процедуры в существенной степени зависит от порядка перебора элементов, причем оптимальным представляется такой перебор, при котором на каждом шаге обеспечивается уменьшение величины функционала Q в максимальной степени. Для этого требуется анализ изменения Q как функции каждой фазы. Однако такая процедура может оказаться затратной по времени реализации. В этом случае возможно использование компромиссного варианта, в котором на каждом шаге выбирается такой элемент, который обеспечивает уменьшение функционала на некоторую величину ΔQ. Величина ΔQ лежит в пределах 0<ΔQ≤ΔQmax, где ΔQmax - максимальное возможное изменение функционала Q среди всех элементов ФАР. Чем меньше ΔQ, тем быстрее можно найти подходящий элемент. Однако в этом случае среднее за несколько шагов изменение минимизируемого функционала будет меньше, чем при больших значениях ΔQ. Таким образом, с одной стороны, величина ΔQ определяет число элементов ФАР, участвующих в формировании нулей, и, соответственно, уровень фона ДН, определяемого случайными погрешностями при реализации найденных фаз (т.е. уровень достижимых нулей). С другой стороны, ΔQ задает скорость поиска подходящего элемента и влияет, в конечном итоге, на общую скорость работы заявляемого способа. В частности, анализ показывает, что при формировании изолированного нуля в ДН N-элементной ФАР с равномерным амплитудным распределением нахождение элемента с ΔQ=ΔQmax на каждом шаге требует перебора по всем N элементам ФАР. Если же снизить требование до уровня ΔQ=0,9ΔQmax, то в среднем элемент, удовлетворяющий этому условию, будет найден в N/4 раз быстрее. При этом среднее число элементов, используемых для формирования нуля, увеличивается лишь на 10% по сравнению с оптимальным вариантом и влечет соответствующее уменьшение глубины нуля.Учитывая, что глубина нуля, формируемая предлагаемым способом, напрямую зависит от исходных значений комплексной ДН в направлениях формируемых нулей, целесообразно решать задачу синтеза нулей в два этапа. На первом этапе проводится синтез нулей с использованием одного из известных способов фазового синтеза, например, покоординатного способа. На втором этапе выполняется процедура, реализующая предлагаемый способ. Такой прием обладает следующими преимуществами. Первый этап позволяет снизить уровень ДН в направлениях формируемых нулей до уровня фона, определяемого формулой (5). Таким образом, на втором этапе среднее число элементов, участвующих в синтезе, оказывается минимальным и тем самым глубина формируемого нуля, определяемая случайными погрешностями реализации фаз на элементах ФАР, участвующих в синтезе, оказывается максимальной. Второй этап синтеза можно повторять либо до тех пор, пока для синтеза нуля не потребуется изменение фазы лишь на одном элементе ФАР, либо до достижения предельного уровня ДН ФАР, ограниченного точностью измерения комплексных значений ДН ФАР в направлениях помех. При многократном повторении второго этапа синтеза предельный уровень глубины нуля оказывается также обратно пропорциональным квадрату числа элементов ФАР, как и в случае детерминированных погрешностей.Предложенная схема формирования нулей в ДН ФАР допускает обобщение на тот случай, когда по той или иной причине управление ДН осуществляется по группам фазовращателей, каждая из которых управляется как один элемент. Такая ситуация возникает, например, в модульных ФАР, в которых апертура разбивается на идентичные или неидентичные подрешетки и управление ДН ФАР осуществляется по входам подрешеток. В таком случае ДН всей ФАР можно представить в виде векторной суммы комплексных ДН отдельных подрешеток, рассматриваемых в общей системе координат. Тогда подрешетки представляют собой укрупненные элементы той же ФАР, и описанный выше способ может применяться для формирования глубоких нулей в ДН ФАР с нахождением оптимальной фазовой подставки для каждой из подрешеток.В случае если ФАР содержит неисправные элементы, заявляемый способ также позволяет осуществить формирование нулей, если известны только номера этих элементов. Тогда управление осуществляется только по исправным элементам или исправным группам элементов. Когда же группа содержит неисправные элементы и схема управления допускает изменение элементного состава подрешетки, можно перегруппировать элементы ФАР таким образом, чтобы новые подрешетки, используемые для формирования нулей ДН ФАР, содержали только исправные элементы. В этом случае формирование нулей в соответствии с заявляемым способом может осуществляться с использованием новой системы подрешеток. Если такое перегруппирование ФАР невозможно, заявляемый способ работоспособен, формирование нулей по-прежнему производится с выбором оптимальных фазовых подставок на входах подрешеток, однако достигаемые уровни глубины нулей в среднем уменьшаются с ростом числа неисправных элементов в подрешетках, используемых для формирования нулей ДН ФАР. Заявляемый способ также работоспособен как в том случае, когда для формирования нулей ДН используются все элементы ФАР (все подрешетки модульной ФАР), так и в том случае, когда используется лишь часть элементов ФАР или часть подрешеток (модулей) в модульной ФАР.Сведения, подтверждающие возможность осуществления изобретенияДля подтверждения возможности осуществления изобретения был проведен ряд экспериментов.В качестве испытуемой ФАР была выбрана ФАР с равномерным амплитудным распределением. ФАР состояла из 384 элементов с ферритовыми фазовращателями, расположенных вдоль шестизаходной спирали.Работоспособность заявляемого способа проверяли на примере формирования одного нуля. Эксперименты повторили для 8 угловых направлений формируемого нуля ДН ФАР.Для каждого углового направления выполнялись следующие действия:- На первой стадии выполнялся первый этап - формировался нуль в заданном направлении с использованием ближайшего аналога заявляемого способа - покоординатного метода синтеза.- На второй стадии выполнялся второй этап формирования нуля - формирование нуля заявляемым способом, т.е. измерялось комплексное значение ДН ФАР в заданном направлении, и проводилась итерационная процедура, реализующая заявляемый способ формирования нулей в ДН ФАР с использованием значенияΔQ=ΔQmax.- На третьей и четвертой стадиях повторялись действия, перечисленные в описании второго этапа, используя каждый раз в качестве исходного состояния АФР, полученное на предыдущей стадии.После каждого из этих действий фиксировалась достигнутая глубина нуля. Результаты измерений значений ДН в направлении формируемого нуля (в дБ) приведены в таблице. Глубина достигнутых нулей № углового направления Ближайший аналог Заявляемый способ 1-я реализация 2-я реализация 3-я реализация 1 -35 -58 -58 -58 2 -41 -57 -54 -58 3 -30 -50 -59 -66 4 -28 -45 -65 -65 5 -30 -45 -57 -69 6 -41 -49 -62 -73 7 -32 -55 -65 -59 8 -33 -73 -78 -74 Среднее -32 -49 -59 -62 Выигрыш*   17 10 3 * Выигрыш по сравнению с предыдущей стадией Из результатов, представленных в таблице, можно сделать вывод о работоспособности заявляемого способа формирования нулей, который позволил добиться существенного (на 30 дБ за три стадии) увеличения средней глубины нуля по сравнению с ближайшим аналогом.Помимо этого, на основании данных о статистических характеристиках погрешностей АФР было проведено компьютерное моделирование работы заявляемого способа, которое показало, что предельная достижимая средняя глубина нуля при данном уровне случайных искажений АФР в исследуемой ФАР составляет -62 дБ. Таким образом, сопоставление экспериментальных и теоретических результатов показывает, что данный способ позволяет, во-первых, достичь предельной глубины нуля, а во-вторых, предельная глубина нуля достигается достаточно быстро (в данном случае на третьей стадии применения заявляемого способа).

Способы и системы для реализации

Изобретение относится к прогнозируемым торговым системам, более конкретно к способам и системам для приближенного сравнения строк в базе данных с добавляемой записью в базу данных, находящуюся в сети обслуживания банковских карт. Техническим результатом является повышение эффективности получения приблизительного соответствия символьной строки в базе данных без необходимости вычислять метрику подобия по всей базе данных. В способе сравнения символьных строк, символьной строки кандидата с множеством записей символьных строк, сохраненных в базе данных, идентифицируют набор ссылочных символьных строк в базе данных. Ссылочные символьные строки идентифицируются с использованием оптимизированного поиска набора разнородных символьных строк. Затем генерируют представление n-граммы каждой из ссылочных символьных строк в наборе ссылочных символьных строк и генерируют представления n-граммы символьной строки кандидата. После чего определяют подобие между представлениями n-грамм каждой из ссылочных символьных строк и символьной строки кандидата. Индексируют символьную строку кандидата в базе данных, основываясь на определении релевантности между представлением n-граммы символьной строки кандидата и ссылочными символьными строками в идентифицированном наборе. 3 н. и 17 з.п. ф-лы, 10 ил., 14 табл.

1. Компьютерный способ сравнения символьных строк, символьной строки кандидата с множеством записей символьных строк, сохраненных в базе данных, упомянутый способ, включает:a) идентификацию набора ссылочных символьных строк в базе данных, ссылочные символьные строки идентифицируются с использованием оптимизированного поиска набора разнородных символьных строк;b) генерирование представления n-граммы одной из ссылочных символьных строк в наборе ссылочных символьных строк;c) генерирование представления n-граммы символьной строки кандидата;d) определение подобия между представлениями n-грамм;e) повторение шагов b) и d) для оставшихся ссылочных символьных строк в наборе идентифицированных ссылочных символьных строк; иf) индексацию символьной строки кандидата в базе данных, основанную на определении релевантности между представлением n-граммы символьной строки кандидата и ссылочными символьными строками в идентифицированном наборе.2. Компьютерный способ по п.1, отличающийся тем, что определение подобия между представлениями n-граммы, включает:вычисления двумерного вектора, содержащего частоту возникновения всех уникальных n-грамм в символьной строке кандидата и частоту возникновения всех уникальных n-грамм в ссылочной символьной строке; ивычисление метрики подобия для символьной строки кандидата, относительно ссылочной символьной строки, основанной на двумерном векторе.3. Компьютерный способ по п.2, отличающийся тем, что вычисление метрики подобия для символьной строки кандидата включает использование вычисления структурированного языка запроса для сравнения содержания двумерного вектора.4. Компьютерный способ по п.2, отличающийся тем, что вычисление метрики подобия включает:определение величины вектора, ассоциированного с символьной строкой кандидата, как величины А;определение величины вектора, ассоциированного со ссылочной символьной строкой как величины В;вычисление скалярного произведения между этими двумя векторами; и вычисление метрики подобия согласно (скалярное произведение/(Величина А × Величина В)).5. Компьютерный способ по п.2, отличающийся тем, что вычисление метрики подобия включает реализацию вычисления n-грамм частоты подобия в ASCII структурированного языка запроса.6. Компьютерный способ по п.5, отличающийся тем, что дополнительно включает использование вычисление n-грамм частоты подобия, для формирования двоичного ключа, который указывает на подобие между символьной строкой кандидата и каждой из идентифицированных ссылочных символьных строк.7. Компьютерный способ по п.2, отличающийся тем, что индексирование символьной строки кандидата в базе данных, включает:реализацию вычисления n-грамм частоты подобия;использование вычисления для формирования двоичных ключей, которые указывают на подобие между записью, связанной с символьной строкой кандидата, и записью, связанной с каждой из идентифицированных ссылочных символьных строк;присоединение записей, которые совместно используют то же значение двоичного ключа; и сортировку присоединенных записей по релевантности, суммированием весовых коэффициентов частоты всех сравниваемых n-грамм.8. Компьютерный способ по п.1, отличающийся тем, что индексация символьной строки кандидата, включает генерирование матрицы метрик подобия для символьной строки кандидата по сравнению с набором ссылочных символьных строк.9. Компьютерный способ по п.1, отличающийся тем, что индексация символьной строки кандидата, включает:присвоение двоичному ключу, соответствующего ссылочной символьной строке значения 1, если метрика подобия выше предопределенного порога; иприсвоение двоичному ключу, соответствующего ссылочной символьной строке значение 0, если метрика подобия ниже предопределенного порога.10. Компьютерный способ по п.1, отличающийся тем, что идентификация набора ссылочных символьных строк в базе данных включает использование основного компонентного фактора анализа для идентификации набора разнородных записей символьных строк.11. Компьютер, программированный для:использования оптимизированного поиска для идентификации набора разнородных ссылочных символьных строк в базе данных;генерирования представления n-граммы для символьной строки кандидата; генерирования представления n-граммы для каждой из разнородных ссылочных символьных строк в наборе;определения подобия между представлением n-граммы символьной строки кандидата и каждым представлением n-граммы набора разнородных ссылочных символьных строк; и индексирования символьной строки кандидата в базе данных, основанной на общих символах, определенных в представлениях n-граммы.12. Компьютер по п.11, отличающийся тем, что для определения подобие между представлением n-граммы символьной строки кандидата и каждым представлением n-граммы набора разнородных ссылочных символьных строк, упомянутый компьютер дополнительно программируется длявычисления двумерных векторов, содержащих частоту возникновения всех уникальных n-грамм в символьной строке кандидата и всех уникальных n-грамм в одной из ссылочных символьных строк для каждой из ссылочных символьных строк; ивычисление метрики подобия для символьной строки кандидата относительно каждой ссылочной символьной строки, основанной на двумерных векторах.13. Компьютер по п.12, отличающийся тем, что для вычисления метрики подобия, упомянутый компьютер программируется, чтобы использовать вычисления структурированного языка запроса, чтобы сравнить содержание двумерных векторов.14. Компьютер по п.11, отличающийся тем, что для индексирования символьной строки кандидата, упомянутый компьютер программируется для:присвоения двоичному ключу соответствующей ссылочной символьной строки, значение 1, если определено, что подобие выше предопределенного порога; иприсвоения двоичному ключу соответствующей ссылочной символьной строки, значения 0, если определено, что подобие ниже предопределенного порога.15. Компьютер по п.11, отличающийся тем, что для проведения оптимизированного поиска упомянутый компьютер программируется, чтобы использовать основной компонентный фактор анализа для идентификации набора разнородных ссылочных символьных строк в базе данных.16. Компьютерный способ для приблизительного сравнения символьной строки кандидата с набором ссылочных символьных строк в базе данных, упомянутый способ включает:отдельное сравнение представления n-граммы символьной строки кандидата с представлениями n-граммы каждой ссылочной символьной строки в наборе ссылочных символьных строк; игенерирование двоичного индексного значения, которое ассоциируется с символьной строкой кандидата, причем двоичное индексное значение, указывает на подобие между символьной строкой кандидата и каждой из ссылочных символьных строк.17. Компьютерный способ по п.16, отличающийся тем, что отдельное сравнение представления n-граммы символьной строки кандидата с представлениями n-граммы каждой ссылочной символьной строки включает использование вычисления подобия частоты n-граммы на структурированном языке запросов для сравнения представленных n-грамм.18. Компьютерный способ по п.16, отличающийся тем, что отдельное сравнение представления n-граммы символьной строки кандидата с представлениями n-граммы каждой ссылочной символьной строки включает:a) определение величины (А) вектора ассоциированного с представлением n-граммы символьной строки кандидата;b) определение величины (В) вектора, ассоциированного с представлением n-граммы одной из ссылочных символьных строк как величины В;c) вычисление скалярного произведения между этими двумя векторами; иd) вычисление метрики подобия символьной строки кандидата относительно ссылочной символьной строки согласно (скалярное произведение/(величина А × величина В)); и повторение шагов b), с), и d) для каждой ссылочной символьной строки.19. Компьютерный способ по п.16, отличающийся тем, что символьная строка кандидата — одно из торговых названий, и торговых адресов, а набор ссылочных символьных строк в базе данных — соответственно, больший набор торговых названий и торговых адресов.20. Компьютерный способ по п.16, отличающийся тем, что дополнительно включаетприсоединение записей, которые совместно используют одно двоичное индексное значение; исортировку присоединенных записей по релевантности суммированием результатов представления частотных весовых коэффициентов всех сравниваемых n-грамм.

Уровень техникиПредставленное изобретение в основном относится к прогнозируемым торговым системам и более конкретно к способам и системам для приближенного сравнения строк в базе данных с добавляемой записью в базу данных, находящуюся в сети обслуживания банковских карт.Исторически использование «платежных» карт для транзакций потребительских платежей было самым распространенным и основанным на связи между выдающими кредиты локальными банками и различными локальными продавцами. Отрасль платежных карт с тех пор развилась до формирования ассоциаций банков кредиторов (например, MasterCard) и включает сторонние компании обработки транзакций (например, «Merchant Acquirers»), чтобы позволить владельцам кредитных карточек широко использовать платежные карточки в любых торговых учреждениях, независимо от банковских отношений продавца с банком, выпустившим карту.Например, фигура 1 представленной заявки показывает примерную многостороннюю систему индустрии платежной карты для проведения транзакции оплаты картой. Как показано, у продавца и выпускающего карту не обязательно должна быть непосредственная связь. Все же сегодня существуют различные сценарии в отрасли оплаты картой, где у выпускающего карты есть специальная или специализированная связь с определенным продавцом или группой продавцов.Более 25 миллионов торговых точек принимают к оплате карты. Одна из ассоциаций содержит информацию о названии и адресе для тысяч продавцов и торговых точек в том, что упоминается здесь как хранилище данных. На уровне местонахождения торговых точек в этом хранилище данных имеются миллионы записей. Многие из записей местонахождений, как известно, копируются из-за изменений названия и/или информации об адресах в данных транзакций. Например, один и тот же адрес улицы может быть записан разными способами, все из которых допустимы (например, 400 South Fourth Street, 400 S. Fourth St., 400 South 4th Street и т.д.). Названия могут иногда также представляться многими способами, каждый из которых допустим. Текущая технология баз данных очень ограничена в возможности идентифицировать записи с подобными значениями полей, такими как название и адрес. Таким образом, много близких копий названий торговых точек и местоположений вводятся в хранилище данных.В обычный операционный день для ассоциации поступает приблизительно 15000 местоположений кандидата (например, новые местоположения торговых точек), которые должны быть проверены на соответствие приблизительно пяти миллионам записей местоположений, находящимся уже в хранилище данных. Проверка соответствия служит, по меньшей мере, двум целям. Первая, — местоположения с аналогичными названиями и/или адресами могут быть идентифицированы как один объект, а не несколько. Дополнительно, если названия или адреса слишком отличаются, ассоциация может решить, что объект переместился или что один объект прекратил операции и был заменен другим объектом.С проблемой соответствия названия и местоположения также встречаются в некоторых других контекстах, в случае предоставления третьей стороной хранилища данных с файлами транзакции, поддерживаемого ассоциацией, и соответственно списков торговых точек и адресов (местоположения) для улучшения и/или проверки хранилища данных. В другом примере третьей стороной может быть получен список всех местоположений для крупного национального ретейлера, или могут быть получены списки названий и адресов филиалов. Команда, занимающаяся поддержанием хранилища данных, занимается задачей соответствия полученного списка известным местоположениям для ретейлера или цепочки.Один из способов проверить соответствие между существующими местоположениями и новыми местоположениями является строковый алгоритм соответствия. Поэтому любые решения, которые могут быть использованы для сравнения строк, могут быть масштабируемыми в пределах системы платформы базы данных (хранилища данных). Действительно существуют решения определения приблизительного строкового соответствия. Однако у этих решений обычно есть один или более недостатков, включающих непомерную стоимость решения, специфику сферы деятельности или инструментов, или решение является внешним по отношению к системе базы данных (хранилищу данных).Поэтому существует прежде не решаемая задача разработки способа, который позволил бы команде хранилища данных выполнять проверку названия и адреса на соответствие записям о торговых точках масштабируемым способом в пределах системы базы данных. Достигаемым результатом является компактное и точное хранилище данных, способное к поддержке других зависимых приложений, например, использующих исторические данные транзакций для предсказания будущих транзакций финансовых карт и определения, есть ли корреляция этих данных.Сущность изобретенияВ одном аспекте представлен компьютерно-основанный способ сравнения символьных строк, символьной строки кандидата с множеством записей символьных строк, сохраненных в базе данных. Способ включает а) идентификацию набора ссылочных символьных строк в базе данных, ссылочные символьные строки идентифицируются с использованием оптимизированного поиска набора разнородных символьных строк, b) генерирование представления n-граммы одной из ссылочных символьных строк в наборе ссылочных символьных строк, с) генерирование представления n-граммы символьной строки кандидата, d) определение подобия между представлениями n-грамм, е) повторение шагов b) и d) для оставшихся ссылочных символьных строк в наборе идентифицированных ссылочных символьных строк и f) индексацию символьной строки кандидата в базе данных, основанную на определении релевантности между представлением n-граммы символьной строки кандидата и ссылочными символьными строками в идентифицированном наборе.В другом аспекте представлен компьютер, обеспечивающий посредством программирования использование оптимизированного поиска, чтобы идентифицировать набор разнородных ссылочных символьных строк в базе данных, генерирование представления n-граммы для символьной строки кандидата, генерирование представления n-граммы для каждой из разнородных ссылочных символьных строк в наборе, определение подобия между представлением n-граммы символьной строки кандидата и каждым представлением n-граммы набора разнородных ссылочных символьных строк и индексирование символьной строки кандидата в базе данных, основанное на общих чертах, определенных в представлениях n-граммы.В еще одном аспекте обеспечивается компьютерно-основанный способ для приблизительного сравнения символьной строки кандидата с набором ссылочных символьных строк в базе данных. Способ включает индивидуальное сравнение представления n-граммы символьной строки кандидата с представлениями n-граммы каждой ссылочной символьной строки в наборе ссылочных символьных строк и генерирование двоичного индексного значения, связанного с символьной строкой кандидата, двоичное индексное значение указывает на подобие между символьной строкой кандидата и каждой из ссылочных символьных строк.Краткое описание чертежейФигура 1 — принципиальная схема, иллюстрирующая примерную многостороннюю систему индустрии платежной карты для проведения транзакции оплаты картой.Фигура 2 — упрощенная блок-схема примерного варианта осуществления архитектуры сервера системы в соответствии с одним из вариантов осуществления представленного изобретения.Фигура 3 — расширенная блок-схема примерного варианта осуществления архитектуры сервера системы в соответствии с одним из вариантов осуществления представленного изобретения.Фигура 4 — блок-схема, иллюстрирующая высокоуровневые компоненты объединенной совокупности торговой системы прогноза.Фигура 5 — блок-схема, иллюстрирующая работу механизма, ведущего подсчет, связанного с объединенной совокупностью торговой системы прогноза.Фигура 6 — блок-схема 250, иллюстрирующая данные, которые вводятся в алгоритм, который классифицирует местоположения торговых точек.Фигура 7 — блок-схема, описывающая алгоритм, который классифицирует местоположения торговых точек.Фигура 8 — схема, иллюстрирующая, как торговые точки собираются и размещаются в виде документов в системе классификации.Фигура 9 — блок-схема, иллюстрирующая определение набора ссылочных символьных строк, или основных компонентов, в базе данных.Фигура 10 — блок-схема, иллюстрирующая использование набора ссылочных строк, чтобы определить метрику подобия для символьной строки кандидата.Подробное описание изобретенияВарианты осуществления, описанные здесь, касаются эффективного способа для получения приблизительного соответствия строки (например, символьной строки) в базе данных без необходимости вычислять метрику подобия по всей базе данных. Посредством приблизительного строкового сравнения, например, полученных данных местоположения, которые несколько отличаются по содержанию, может быть определено соответствие в местоположении. Эта эффективность достигается генерированием двоичного индекса, получением относительной позиции (степени соответствия) каждой строки относительно набора ссылочных строк, охватывающих пространство строк для соответствующего поля. В то время как способ описан в контексте названий и местоположений торговых точек, связанных с работой системы финансовых транзакций карт, важно отметить, что способ приблизительного строкового сравнения применим к более общим задачам, таким как информационный поиск, с заменой сравнения символьных строк информации о названии и адресе торговых точек. Один из примеров — использование способа для сравнения документов в компьютерной системе.Технический эффект систем и процессов, описанных здесь, включает, по меньшей мере, один из (а) способ для выполнения приблизительного сравнения названия и адреса, чтобы сравнивать торговые записи масштабируемым способом в системе баз данных; (b) учет для определения метрики подобия символьной строки кандидата относительно каждого множества ссылочных символьных строк; (с) генерирование двоичного индекса, который отражает относительную позицию символьной строки каждого кандидата в наборе ссылочных символьных строк, который охватывает пространство строк в базе данных для соответствующих полей; и (d) получение приблизительного сравнения строки совпадений между символьной строкой кандидата и базой данных, которая содержит множество записей символьных строк, без необходимости вычислять метрику подобия для всей базы данных записей.В одном варианте осуществления обеспечивается компьютерная программа, программа воплощается на компьютерно-читаемом носителе и использует Структурированный Язык Запросов (SQL) с клиентским пользовательским внешним интерфейсом для администрирования и веб-интерфейсом для стандартного ввода данных и отчетов пользователем. В примерном варианте осуществления система представляет собой сеть, включая и осуществляемую на предприятиях сеть интранет. В еще одном варианте осуществления к системе полностью получают доступ пользователи, имеющие санкционированный доступ, вне брандмауэра предприятия, через Интернет. В дополнительном примерном варианте осуществления система выполняется в среде Windows® (Windows — зарегистрированная торговая марка Microsoft Corporation, Redmond, Washington). Приложение гибко и разрабатывается для работы во всевозможных средах без ущерба основной функциональности.Системы и процессы не ограничиваются определенными вариантами осуществления, описанными здесь. Кроме того, компоненты каждой системы и каждого процесса могут быть осуществлены независимо и отдельно от других компонентов и процессов, описанных здесь. Каждый компонент и процесс также может использоваться в комбинации с другими комплектами элементов и процессами.В качестве уровня техники фигура 1 представляет принципиальную схему 20, иллюстрирующую примерную многостороннюю систему индустрии платежной карты для проведения обычных транзакций оплаты картой, в которых история транзакции используется, по меньшей мере, частично с объединенной совокупностью прогноза торговой системы. Как представлено здесь, совокупный продавец обращается к группирующимся на высоком уровне торговым точкам. Более конкретно, различные отдельные торговые точки ретейлера группируются вместе (например, соединены друг с другом в базе данных) для формирования совокупного продавца. Одна торговая точка представляет собой компонент совокупного продавца. Как правило, совокупный продавец используется при обращении к цепочке магазинов и местоположения сгруппированы вместе, как далее описано здесь, основываясь на многих значениях полей, сохраненных в базе данных транзакции.Данное изобретение относится к системам платежных карт, такой как система платежей по кредитной карте, использующая MasterCard® обмен информацией. MasterCard® обмен информации является собственным коммуникационным стандартом, провозглашенным MasterCard International Incorporated®, для обмена данными финансовых операций между финансовыми учреждениями, которые являются элементами MasterCard International Incorporated® (MasterCard — зарегистрированная торговая марка MasterCard International Incorporated, расположенной в Purchase, New York).В обычной карточной платежной системе финансовое учреждение обращалось к «выпускающему» платежную карту, такую как кредитная карта, потребителю, который предоставлял платежную карту в качестве средства оплаты за покупку продавцу. Для приема оплаты с платежной карты обычно торговец должен создавать учетную запись в финансовом учреждении, которое является частью финансовой платежной системы. Это финансовое учреждение обычно называют «инвестиционным банком», «банком получения» или «банком получателя». Когда потребитель 22 производит оплату за покупку посредством платежной карты (также известной как карта финансовой операции), торговец 24 запрашивает авторизацию в инвестиционном банке 26 суммы покупки. Запрос может быть выполнен по телефону, но обычно выполняется с помощью терминала продаж, который считывает информацию об учетной записи потребителя с магнитной дорожки на платежной карте и связывается электронным путем с компьютерами обработки транзакций инвестиционного банка. Альтернативно, инвестиционный банк может разрешить третьей стороне выполнять обработку транзакций от своего лица. В этом случае кассовый терминал будет сконфигурирован так, чтобы связываться с третьей стороной. Такую третью сторону обычно называют «торговым процессором» или «процессором получения».Используя обмен 28, компьютеры инвестиционного банка или торгового процессора связываются с компьютерами банка, выпустившего карту 30, чтобы определить, является ли учетная запись потребителя в положительном положении и покрывается ли покупка доступным кредитным лимитом потребителя. Основываясь на этих определениях, просьба на авторизацию будет отклонена или принята. Если запрос принимается, код авторизации посылается торговцу.Когда запрос на авторизацию принимается, доступный кредитный лимит учетной записи 32 потребителя уменьшается. Обычно запрос средств не сразу отправляется на учетную запись потребителя, потому что ассоциации банковских карт, такие как MasterCard International Incorporated®, провозгласили правила, которые не позволяют торговцу запрашивать средства или «получать» транзакцию, пока товары или услуги не предоставляются. Когда торговец поставляет или предоставляет товары или службы, торговец получает транзакцию, например процедура получения соответствующих данных на терминале продажи. Если потребитель отменяет транзакцию прежде, чем она будет получена, генерируется «пустая операция». Если потребитель возвращает товары после того, как транзакция была получена, то «кредит» генерируется.После того как осуществляется транзакция, транзакция урегулируется между торговцем, инвестиционным банком и выпускающим карту. Урегулирование относится к передаче финансовых данных или фондов, связанных с транзакцией, между учетной записью продавца, инвестиционным банком и выпускающим карту. Обычно транзакции проходят и накапливаются в «пакет», которые урегулируются как группа. Данные, которые связанны с такими транзакциями, как описано далее, используются в области предсказания будущих действий покупателя.Карты финансовых транзакций или платежные карты могут относиться к кредитным картам, дебетовым картам и картам с предоплатой. Все эти карты могут использоваться в качестве способа оплаты за выполнение транзакции. Как описано здесь, термины «финансовая операция карты» или «платежная карта» включают карты, такие как кредитные карты, дебетовые карты и карты с предоплатой, но также включают любые другие устройства, которые могут содержать платежную информацию об учетной записи, такую как мобильные телефоны, персональные цифровые секретари (PDA) и брелки.Фигура 2 — упрощенная блок-схема примерной системы 100 в соответствии с одним из вариантов осуществления представленного изобретения. В одном варианте осуществления система 100 является системой платежной карты, используемой для реализации, например, связи между выпускающим карты и продавцом и в то же время обработки данных, связанных с историей транзакций. В другом варианте осуществления система 100 является системой платежной карты, которая может быть использована владельцами банковского счета для того, чтобы ввести коды обработки, которые будут применены к актам платежа.Более конкретно, в варианте осуществления в качестве примера, система 100 включает систему сервера 112 и множество клиентских подсистем, также называемых клиентскими системами 114, соединенных с системой сервера 112. В одном варианте осуществления клиентские системы 114 являются компьютерами, включающими веб-браузер, так что система сервера 112 доступна для клиентских систем 114 при использовании Интернета. Клиентские системы 114 присоединяются к Интернету через различные интерфейсы, включающие сети, такие как локальная сеть (LAN) или глобальная сеть (WAN), соединения удаленного доступа, кабельные модемы и специальные высокоскоростные линии ISDN. Клиентские системы 114 могут быть любым устройством, способным к соединению с Интернетом, включая сетевой телефон, персональный цифровой секретарь (PDA) или другое сетевое соединяемое оборудование. Сервер базы данных 116 соединяется с базой данных 120, содержащей информацию о множестве тем, как описано ниже более подробно. В одном варианте осуществления централизованная база данных 120 записана в системе сервера 112 и к ней может быть получен доступ потенциальными пользователями в одной из клиентских систем 114 посредством регистрации на системе сервера 112 через одну из клиентских систем 114. В альтернативном варианте осуществления база данных 120 сохранена удаленно от системы сервера 112 и может быть не централизована.Так же как описано ниже, база данных 120 хранит данные транзакции, сгенерированные как часть деятельности по продаже, проводимой по банковской сети, включающей данные, касающиеся продавцов, владельцев банковского счета или клиентов и покупок. База данных 120 дополнительно включает данные, касающиеся программ поощрений и специальных предложений, включая обработку кодов и деловых правил, связанных с различными программами поощрений и специальными предложениями.Фигура 3 — расширенная блок-схема примерного варианта осуществления архитектуры сервера системы 122 в соответствии с одним из вариантов осуществления представленного изобретения. Компоненты системы 122, идентичные компонентам системы 100 (показанной на фигуре 2), обозначены на фигуре 3 с использованием тех же ссылочные цифр, как использовались на фигуре 2. Система 122 включает систему сервера 112 и клиентские системы 114. Система сервера 112 дополнительно включает сервер базы данных 116, сервер приложений 124, веб-сервер 126, факс-сервер 128, сервер каталогов 130 и почтовый сервер 132. Дисковый накопитель 134 связывается с сервером базы данных 116 и сервером каталогов 130. Серверы 116, 124, 126, 128, 130 и 132 связываются в локальной сети (LAN) 136. Кроме того, системная рабочая станция администратора 138, пользовательская рабочая станция 140 и рабочая станция супервизора 142 присоединяются к LAN 136. Альтернативно, рабочие станции 138, 140 и 142 связываются с LAN 136 при использовании соединения Интернет или присоединяются через интранет.Каждая рабочая станция 138, 140 и 142 является персональным компьютером, имеющим веб-браузер. Хотя функции, выполняемые на рабочих станциях, обычно иллюстрируются как выполняемые на соответствующих рабочих станциях 138, 140 и 142, такие функции могут быть выполнены в одном из многих персональных компьютеров, связанных с LAN 136. Рабочие станции 138, 140 и 142 иллюстрируются как связываемые с отдельными функциями, только чтобы облегчить понимание различных типов функций, которые могут быть выполнены пользователями, имеющими доступ к LAN 136.Система сервера 112 конфигурируется так, чтобы быть коммуникативно объединенной с различными пользователями, включая сотрудников 144 и третьи стороны, например владельцев банковского счета, клиентов, аудиторов и т.д., 146, используя интернет-соединения ISP 148. Система взаимодействия в примерном варианте осуществления иллюстрируется как выполняемая с использованием Интернетов, однако любая другая глобальная сеть (WAN), тип передачи могут быть использованы в других вариантах осуществления, то есть системы и процессы не ограничиваются тем осуществлением, в котором используется Интернет. Кроме того, в предпочтительном варианте локальная сеть 136 может быть использована вместо WAN 150.В примерном варианте осуществления любой авторизованный пользователь, имеющий рабочую станцию 154, может получить доступ к системе 122. По меньшей мере, одна из клиентских систем включает рабочую станцию менеджера 156, расположенную в удаленном местоположении. Рабочие станции 154 и 156 являются персональными компьютерами, имеющими веб-браузер. Кроме того, рабочие станции 154 и 156 конфигурируются, чтобы связываться с системой сервера 112. Кроме того, факс-сервер 128 связывается с удаленно расположенными клиентскими системами, включая клиентскую систему 156, используя телефонные линии. Факс-сервер 128 также конфигурируется, чтобы связываться с другими клиентскими системами 138, 140 и 142.Фигура 4 — блок-схема 200, иллюстрирующая высокоуровневые функциональные компоненты объединенной совокупности прогнозируемой торговой системы, где каждый компонент обеспечивает прогноз, касающийся операций сети, операций финансовой карты. Затем прогнозы соединяются в единый прогноз, как описано далее. Это соединение прогнозов иногда упоминается как совмещенный прогноз. Один пример, относящийся к варианту осуществления, описанному здесь, включает комплексные прогнозы, которые касаются полученных торговых данных местоположения. Как представлено на фигуре 4, все алгоритмы прогноза более полно описываются здесь.Первый компонент — алгоритм прогноза подобного местоположения 202 (иногда называемый k-подобный алгоритм прогноза местоположения), который конфигурируется, чтобы получить «k» торговых местоположений, которые являются самыми подобными данному торговому местоположению. Алгоритм прогноза 202 далее функционирует для классификации группы подобных торговых местоположений как режим группировки полученного числа «k» наиболее подобных местоположений.Совмещение Местоположений как алгоритм Прогноза Документов 204 используется, чтобы вычислить релевантности для каждого значения поля и значения поля относительно каждого совмещения местоположений (высокоуровневая группировка данных) в пространстве известных значений, результаты сохраняются как документ. Самые релевантные значения этих документов используются, чтобы генерировать прогноз.Сторонний алгоритм Прогноза Данных 206 включает систему сравнения местоположения, используется, если прогноз ассоциируется с определенным сторонним брендом. По меньшей мере, один ввод алгоритма 206 включает записи транзакции, полученные от третьей стороны, которые используются в генерировании прогноза. В одном варианте осуществления генерирование прогноза выполняется после того, как выполнено сравнение местоположения с данными стороннего источника данных. Числовой алгоритм Прогноза Подписи 208, вариант осуществления которого базируется в значительной степени на законе Бенфорда и дополнительно основан на наблюдаемой тенденции для продавцов, принадлежащих одной группе, отличается от распределения, определяемого законом Бенфорда, включенного в систему 200 относительно последовательным способом. Прогноз, следующий из алгоритма 208, становится группой местоположений, у которых самое подобное числовое распределение по сравнению с каждым торговым местоположением.Статистическая модель верхнего уровня и механизма подсчета 210 в одном варианте осуществления реализована в Oracle, использует прогнозы алгоритмов 202, 204, 206 и 208 для определения состава группы среди данных, которые недавно получены и/или сохранены в базе данных. Пример данных — данные о местоположении торговых точек. По меньшей мере, в одном варианте осуществления и как далее описано, данные о местоположении торговых точек в базе данных описываются с точки зрения местоположения и расстояния, например несколько торговых местоположений, которые находятся на данном расстояния от данного местоположения. По меньшей мере, в одном аспекте местоположение и расстояние являются не обязательно географическими, а скорее основаны на подобии, вычисленном с использованием торговых данных, хранившихся в базе данных. В определенных вариантах осуществления местоположение и расстояние основаны на подобии как измеряемом перекрестном атрибуте, имеющем вес, частоту термина/инверсию частоты документа (TF/IDF), вычисление значений полей и маркировку полей значений в базе данных.Фигура 5 — блок-схема 220, иллюстрирующая работу механизма подсчета 210. Главным образом, механизм подсчета 210 использует 222 прогнозы местоположений торговых точек алгоритмов 202, 204, 206 и 208, наряду с метаданными, относящимися к прогнозированию в интеллектуальном анализе данных Oracle (ODM), приложение 224, для описания обстоятельств, относящихся к каждому отдельному прогнозу, затем производит 226 заключительный прогноз — скомпонованный из отдельных прогнозов. Этот заключительный прогноз может относиться к торговому местоположению. Приложение также производит подсчет доверия, связанный с компоновкой прогнозов, касающихся множества алгоритмов 202, 204, 206 и 208.Каждый из этих четырех алгоритмов 202, 204, 206 и 208 теперь будет описан в дополнительных деталях.К-Подобные Местоположения (алгоритм 202)Фигура 6 — блок-схема 250, иллюстрирующая данные, которые вводятся в алгоритм 202, который классифицирует торговые местоположения, основываясь на подобии, например подобии местоположения. Набор местоположений на уровне полей или координат местоположений 252, которые, как известно, значимы в контексте цепочки получения или участия в наборе (например, группе), идентифицируется в базе данных учреждений 254, которые принимают карту финансовых операций. Дополнительно, данные ежедневно новой/измененной базы данных местоположений 256 наряду с ассоциацией их новым/измененным координатам местоположений 258 обеспечивают для нижеописанного алгоритма классификации местоположения торговых точек.Фигура 7 — блок-схема 280, описывающая один из алгоритмов (алгоритм 202, показанный на фигуре 4), который используется для классификации местоположения торговых точек в составе группы. Алгоритм 202 использует, по меньшей мере, данные, описанные относительно блок-схемы 250 фигуры 6. Определенно, торговые данные местоположений в базе данных ищутся 282 для нахождения нескольких (k) местоположений, которые в пределах данного расстояния от данного местоположения. Дополнительно, для местоположения на данном расстоянии ищется подобие, чтобы определить 284 любые новые и/или измененные местоположения. Значение режима определяется 286 классификацией торговых местоположений, которые фигурируют среди (k) местоположений в пределах определенного пространства функции (область, от которой данные транзакции вводятся в алгоритм 202). Наиболее часто фигурируемое значение, которое следует из классификации (k) записей местоположения, имеет самый высокий весовой коэффициент и выступает как значение режима, определенное как описано ниже. Это значение режима возвращается 288 как прогноз от алгоритма 202.Как описано далее, поля (координаты местоположения 252 и 258) маркируются, и инверсная частота документа вычисляется для всех маркируемых значений полей, охватывающих пространство функции. В одном варианте осуществления для каждого местоположения разреженная матрица метрик весовых коэффициентов вычисляется для каждого значения поля и каждого маркируемого значения поля как частота/инверсия термина в текстовом документе. Значение прогноза вычисляется присоединением данного поля местоположения к любому полю местоположения, основываясь на одном или больше типе поля и значении поля.Разреженная матрица включает местоположения, типы полей и веса для значений термина и маркера термина и генерируется как описано в абзацах ниже.Матрица создается такой, что содержит обратную частоту документа всех значений полей и маркируемых значений полей, и в одном варианте осуществления имеет девять размерностей. В определенном варианте осуществления эти девять размерностей включают торговый код категории, ассоциацию карты Международного банка (код ICA), бизнес-регион, торговое название, торговый номер телефона, торговый идентификатор получателя, идентификатор уровня продавца, торговое официальное название и идентификатор федерального налога. Эти размерности включаются во все торговые записи местоположения. Инверсная частота документа — логарифм (в одной определенной реализации в основе 2) частного числа записей, разделенных на число записей, содержащих определенное значение. Один пример показан в Таблице 1. В одном варианте осуществления это частное значение вычисляется отдельно для каждой из этих девяти размерностей. Число записей вычисляется как число торговых местоположений. Число записей, содержащих определенный термин, вычисляется, считая число торговых местоположений, которые содержат каждый термин в каждом типе поля.Таблица 1Тип поляЗначение поляИнверсная частота документаНомер телефона201423417712.788106546Номер телефона80022858826.0265553135Маркер названия торговой точкиDCC5.0067468324Маркер названия торговой точкиDFQ8.9807516239Бизнес-регион011.4041323134Для каждого местоположения перекрестный атрибут нормализует частоту термина — дважды инверсный вес частоты документа вычисляется для значений и маркировок значений, всех девяти размерностей, как иллюстрировано в Таблице 2, где эти девять размерностей снова включают торговый код категории, код ICA, бизнес-регион, торговое название, торговый номер телефона, получение торгового идентификатора, уровень торгового идентификатора, торговое официальное название и идентификатор федерального налога.Таблица 2МестоположениеТип поляЗначение поляЧастота термина — дважды инверсный весовой коэффициент частоты документа100Номер телефона2014234177.2453254100Маркер названия торговой точкиBE.125859100Маркер названия торговой точкиST.1125445100Идентификатор федерального налога525414152.2155224100Бизнес-регион01.0252546Прогноз состава группы и доверие для данного местоположения вычисляются, присоединяя предсказанное местоположение ко всем другим местоположениям по типу поля и значению поля, суммируя результат частоты термина, двойной/инверсной частоты документа весового коэффициента для сравнения общих типов полей и значений полей. Результаты местоположения тогда сортируются в порядке убывания получающегося результата, и среди сумм происходит группировка, например тринадцать местоположений с самым высоким результатом даются как прогноз. Результат доверия этого прогноза представляется числом местоположений среди лучших тринадцати местоположений, которые содержатся одной группой (ожидаемое значение), отдельных весовых коэффициентов для k местоположений, которые принадлежат предсказанной группе, и колебанием среди весовых компонентов.Совмещение Местоположений как Прогноз Документов (алгоритм 204)Фигура 8 — схема 300, иллюстрирующая местоположения, совмещенные в наборы документов как системы классификации. Алгоритм 204 (показанный на фигуре 4), который генерирует документы совмещенных местоположений, похож на алгоритмы релевантности документов, обычно используемые механизмами поиска в Интернете. Определенно, релевантность данного торгового местоположения к каждому компоненту совмещения или набора торговых местоположений вычисляется как описано ниже.Для генерирования документа 302 релевантных признаков, например адрес улицы, извлекаются из базы данных данные, касающиеся множества местоположений 304, и группируются в наборы, например набор 306. В целях иллюстрации схема 300 включает четыре набора местоположений, 306, 308, 310 и 312. Набор 312 маркируется как Набор М, указывая, что в определенной реализации число наборов может быть больше или меньше четырех проиллюстрированных. Аналогично число местоположений в пределах набора может измениться от одного до «N».Сгенерированные документы 302, 320, 322 и 324, каждый из которых включает извлеченные релевантные признаки, собираются в словаре 330. Используя словарь 330, формируется разреженная матрица 340, посредством чего вычисляется релевантность каждого значения поля и маркируемого значения поля, используя извлеченные признаки, для каждой совмещенной торговой группы, основанной на, по меньшей мере, одном из частоте термина и обратной частоте документа.В разреженной матрице 340 матрица уровней весовых коэффициентов местоположения соединяется с матрицей весовых коэффициентов торговых групп, основанной на типе поля и значении поля. Сумма этих весовых коэффициентов используется в одном варианте осуществления как механизм релевантности 350, чтобы определить релевантность каждого местоположения в каждой торговой группе. Торговая группа с самой высокой уместностью возвращается как ожидаемое значение, описанное выше. Более конкретно генерирование разреженной матрицы групп, типов полей и весовых коэффициентов для правил термина и маркеров термина описано в следующих абзацах.Во-первых, создается матрица, содержащая инверсную частоту документа всех значений полей и маркируемых значений полей, охватывающих эти девять размерностей, перечисленных выше, конкретно торговый код категории, код ICA, бизнес-регион, торговое название, торговый номер телефона, торговый идентификатор получателя, идентификатор уровня продавца, торговое официальное название и идентификатор федерального налога, через все торговые записи местоположения.Относительно совмещения местоположений как алгоритма прогноза документов и как показано в Таблице 3, инверсная частота документа — логарифм (база 2 в одном определенном варианте осуществления) частного: число записей, разделенных на число записей, содержащих определенное значение. В одном варианте осуществления инверсная частота документа вычисляется отдельно для каждой из девяти размерностей. Число записей вычисляется как число торговых местоположений. Число записей, содержащих определенный термин, вычисляется, считая число торговых местоположений, которые содержат каждый термин в каждом поле каждого типа.Таблица 3Тип поляЗначение поляИнверсная частота документаНомер телефона201423417712.788106546Номер телефона80022858826.0265553135Маркер названия торговой точкиDCC5.0067468324Маркер названия торговой точкиDFQ8.9807516239Бизнес-регион011.4041323134Для каждой группы перекрестный атрибут нормализованной частоты термина — дважды инверсной частоты документа, вычисляется для значений и маркированных значений, охватывая девять размерностей торгового кода категории, кода ICA, бизнес-региона, названия торговой точки, номера телефона торговой точки, идентификатор получателя торговой точки, идентификатор уровня торговой точки, официальное название торговой точки и идентификатор федерального налога, как показано в Таблице 4, и всех торговых точек, принадлежащих каждой группе.Таблица 4ГруппаТип поляЗначение поляЧастота термина — дважды инверсный весовой коэффициент частоты документа14420Принимающий продавец0000000774803120.010472116514420Принимающий продавец0000000775195320.005236058314420Идентификатор налога3620233930.652935799814420Бизнес-регион050.062764855714420Маркер названия продавцаTEN0.0011391784Один прогноз состава группы вычисляется для данного местоположения присоединением к строкам матрицы (k)-подобных местоположений, которая описана выше, к матрице групп по типу поля и значению поля, затем суммируя результаты весовых коэффициентов частоты термина — двойная инверсная частота документа для общих типов полей и значений полей. Предсказанные группы и оценка доверия — группа с самой высокой оценкой подобия (данной суммой весовых коэффициентов * весовые коэффициенты значений сравниваемых полей и маркируемых значений). Оценка доверия для прогноза — получающееся значение.Прогноз данных третьей стороны и сравнение местоположения (алгоритм 206)Третий компонент совокупного прогноза — алгоритм 206 (показанный на фигуре 4), который использует данные, обеспеченные третьей стороной, которые были сравнены базой данных финансовых операций торгового местоположения. В одном варианте осуществления сторонним записям присваивается цепочечный идентификатор, который связан, например, с поставщиком. Эти цепочечные идентификаторы связаны с группами торговых местоположений, связанных с брендом карты финансовых операций (например, выпускающим карты). Прогноз поэтому является просто группировкой торговых данных, соответствующих цепочке, с которой была соединена сторонняя запись. Это соединение сопровождает сравнение местоположения, как описано в следующем абзаце.Набор данных торговых местоположений извлекается из стороннего источника данных, причем местоположения были присвоены (поставщиком) к цепочке. Каждой цепочке в пространстве сторонних местоположений продавца присваивается соотнесение с соответствующей группой. Механизм приблизительного сравнения торговых местоположений используется, чтобы присоединить к набору сторонних записей местоположения продавца набор торговых записей местоположения, сохраненных у выпускающего карты. Предсказанная группа для данного местоположения вычисляется тогда как группа, соответствующая цепочке, соответствующей сторонней записи местоположений, которая была сравнена с записью местоположения продавца. Оценка доверия — сравнительная оценка доверия, присвоенная механизмом приблизительного сравнения торгового местоположения.Числовой Прогноз Подписи (алгоритм 208)В одном варианте осуществления алгоритма числовой подписи продавца 208 (показанного на фигуре 4) используется наблюдение за распределением цифр в первой позиции суммы транзакции и объема транзакций за день. В основном распределение имеет тенденцию быть специфическим, когда различные торговые данные совмещены. Кроме того, распределение имеет тенденцию не входить в противоречие с распределением, предложенным законом Бенфорда в натуральных данных. На практике цепочка ресторанов быстрого обслуживания может показывать тенденцию иметь определенную неоднократно появляющуюся цифру как первую цифру количества транзакции. Такая тенденция может быть использована, по меньшей мере частично, чтобы идентифицировать, например, местоположение франшизополучателя цепочки ресторана быстрого обслуживания в определенном местоположении или адресе.Одним примером прогноза, использующего такой алгоритм, является случайная выборка десяти процентов торговых местоположений каждого совокупного продавца (группировка торговых данных). Распределение чисел 1-9, находящихся в первой позиции количества транзакции и объема транзакции, вычисляется и суммируется относительно совокупного продавца. Вычисляется угловое расстояние между распределением и распределением, идентифицированным законом Бенфорда.Распределение чисел 1-9, находящихся в первой позиции количества транзакции и объема транзакции, тогда вычисляется для данного торгового местоположения. Вычисляется угловое расстояние между распределением и распределением, идентифицированным законом Бенфорда. Совокупного торговца с угловым расстоянием, самым близким к угловому расстоянию торгового местоположения, определяют как предсказанного совокупного торговца для данного местоположения.Более конкретно, и для каждой группы распределение частоты возникновения каждого числа (то есть 1, 2, 3, 4, 5, 6, 7, 8, 9), охватывающего все местоположения в пределах группы среди количества транзакции, количество транзакции и среднее количество транзакции, вычисляется и представляется как процент от целого. Упомянутое распределение сохраняется в таблице, представление которой показано в Таблице 5.Таблица 5ГруппаНомерРаспределение14420116%14420214%14420320%14420412%1442055%14420619%1442072%1442088%1442094%5862518%58625214%58625312%5862543%5862555%5862563%58625730%58625818%5862597%Как только вычислены распределения для каждой группы, определяется числовая подпись для каждой группы, вычисляя скалярное произведение вектора распределения группы и вектора распределения, предложенного законом Бенфорда. Скалярное произведение (угол расхождения) делится на сумму квадратов вектора распределения для каждой группы. Распределение, идентифицированное в законе Бенфорда, вычисляется и сохраняется в таблице, представление которой иллюстрируется Таблицей 6.Таблица 6ГруппаСкалярное произведение1442070.95862575.4Для каждого местоположения распределение частоты возникновения каждого числа (1, 2, 3, 4, 5, 6, 7, 8, 9), показывающего количество транзакции, сумму транзакций и среднее количество транзакции, наблюдается во время интервала за один месяц для данного местоположения, вычисляется и представляется как процент от целого. Затем эти распределения сохраняются в таблице, представление которой иллюстрирует Таблица 7.Таблица 7ГруппаНомерРаспределение100116%100214%100320%100412%10055%100619%10072%10088%10094%20018%200214%200312%20043%20055%20063%200730%200818%20097%Как только вычисляются распределения для каждого местоположения, числовая подпись для каждого местоположения определяется вычислением скалярного произведения вектора распределения местоположения и вектора распределения, предложенного законом Бенфорда. Это скалярное произведение (угол расхождения), разделенное на сумму квадратов вектора распределения для каждого местоположения и распределения, идентифицированного в законе Бенфорда, вычисляется и сохраняется в таблицу, представление которой иллюстрируется Таблицей 8.Таблица 8ГруппаСкалярное произведение10070.920075.4Предсказанный состав группы для данного местоположения тогда вычисляется, находя группу с числовой подписью, самой близкой к числовой подписи данного местоположения, с оценкой доверия, вычисленной как расстояние между этими двумя подписями.Статистическая Модель и ОценкаКак было описано выше относительно фигуры 5, каждое ожидаемое значение из четырех прогнозирующих алгоритмов (202, 204, 206 и 208), наряду с большим набором метаданных, описывающих обстоятельства каждого прогноза, собирается 222 и вводится в приложение Oracle Интеллектуальный Анализ Oracle (ODM) 224. Приложение 224 ODM 224 использует в одном из вариантов осуществления статистическую модель (дерево решений), созданную, используя маркированные формирующие данные, чтобы присвоить оценку доверия каждому ожидаемому значению. Ожидаемое значение с самой высокой оценкой доверия тогда определяется как окончательное предсказанное совокупное значение для каждого торгового местоположения.Приблизительное Строковое СравнениеКак описано выше, один компонент совокупного прогноза — алгоритм, который использует данные местоположения, которые были сравнены, например, с местоположением продавца в базе данных финансовых транзакций карты. Некоторые данные могут быть обеспечены сторонними источниками. Варианты осуществления, описанные ниже, относятся к способам и системам получения приблизительной строки (например, символьной строки), сравненной с данными базы данных. В вариантах осуществления сравнение строки используется, чтобы определить, например, представлена ли строка, представляющая местоположение, в базе данных другой строкой. Такой алгоритм подходит различным вариантам осуществления из-за изменений, которые происходят в записях транзакций, тем более что записи касаются торгового названия и местоположения.Система приблизительного сравнения строк базы данных действует, чтобы присоединить один набор записей к другому набору записей, когда нет общего ключа присоединения, такого как точное соответствие, или общих значений полей, которые присутствуют в данных. Предполагается, что есть некоторое подобие в наборах записей.Как правило, когда два набора данных присоединяются в базе данных, они совместно используют идентичные значения в одном или более полях. Когда идентичные значения полей не используются совместно двумя источниками данных (наборы записей) из-за различий в данных, традиционный подход к присоединению наборов данных от соответствующих источников данных реализует функцию, которая принимает два значения, затем вычисляет и возвращает их подобие. Чтобы использовать этот тип функции как основной для присоединения наборов данных, требуется много итераций, количественно равных числу записей в каждом наборе данных, который присоединяется.Как пример, если есть 10000 записей в наборе данных А и 500000 записей в наборе данных В, функция вычисления подобия должна быть вызвана пять миллиардов раз, чтобы присоединить набор данных А к набору данных В. Кроме того, не могут быть использованы индексы, основанные на индексах и функциях оптимизатором базы данных, при вызове такой функции. Этот тип набора данных очень неэффективен и обрабатывается слишком интенсивно для использования при присоединении наборов данных, имеющих нетривиальные объемы данных.Был разработан способ сравнения строк, который реализуется в различных вариантах осуществления, используя один или более следующих компонентов. Специально набор ссылочных строк используется вместе с критерием, который получается, используя основной компонентный факторный анализ (PCFA). PCFA стремится идентифицировать набор очень несходных представленных строк в пространстве известных значений, которые будут использоваться в качестве ссылочных строк.Другой компонент — вычисление n-грамм частоты подобия, реализуемое на чистом ASCII структурированном языке запроса (SQL), чтобы максимизировать производительность в системе управления реляционной базой данных (RDBMS). Дополнительно, процесс реализуется в RDBMS, используя вычисление n-грамм частоты подобия, чтобы сформировать двоичный ключ, как описано ниже, который указывает на подобие данной записи с каждой из ссылочных строк, идентифицированных в PCFA.В одном варианте осуществления набор управляемых данными стандартизованных функций реализуется в RDBMS как таблица, содержащая инверсную частоту документа (IDF) всех n-грамм, и вычисление SQL перекрестного атрибута весовых коэффициентов частоты термина/инверсной частоты документа (TF/IDF).Один из вариантов осуществления способа строкового сравнения включает параметризованный аналитический запрос SQL, который присоединяется к записям, которые совместно используют то же двоичное значение ключа, после чего сортирует их релевантность, суммируя значения весовых коэффициентов TF/IDF всех сравниваемых n-грамм. i-й бит в двоичном ключе устанавливается в логическую 1, если соответствие записи i-й ссылочной строке выше определенного порога.Процесс реализуется в RDBMS для присвоения оценки доверия каждому соответствию, получаемому из присоединения, в то время как включается модель данных RDBMS для хранения данных, включенных в присоединение наборов данных.Одна простая версия проблемы присоединения набора данных — соответствие одного названия (или адреса) большому набору названий (или адресов), содержащихся в базе данных, такой как таблица Oracle. Пример этого n-грамм соответствия иллюстрируется Таблицей 9.Таблица 9Кандидат (или новый) адресСуществующий лист адресов продавцов10014 S Clarkson Rd.100 Manchester Rd 2014 Clarkson Rd 4 Main Street 10014 South Clarkson Rd 1400 Clayton RdЭлемент, необходимый для решения присоединения набора данных, является метрикой измерения любого подобия между строками, n-грамма — просто уникальная строка n символов, и n-грамм сравнение является процессом определения соответствия между n-граммами. Для случая, где n равен двум, адрес кандидата в Таблице 1 состоит из следующих 2 граммов: «10», «00», «01», «14», «4«, «S», «S«,»C», «C1», «1a» …, «Rd».Таблица 10 — суммарный алгоритм сравнения n-грамм, который включает определение вектора частоты n-грамма для строки кандидата (например, массив Кандидата), определение вектора частоты n-граммы для каждой записи в базе данных соответствия кандидата (например, Candidate_Match_Array), измерение степени подобия между Candidate_Array и Candidate_Match_Array и сохранение тех соответствий кандидата, которые превышают указанный порог. Например, «JoJo’s Diner», становитсяТаблица 10Candidate_Array2-граммЧастота1″Jo»22″oJ»13″o»14″s»15″s»16″D»17″Di»18″in»19″ne»112″er»1Таблицы 11, 12 и 13 являются примерами n-грамм Сравнения Метрик. «Скалярное внутреннее произведение» — скалярное произведение массива, «Величины» — корень квадратный суммы квадратов, «Косинус (угла)» — скалярное произведение, деленное на скалярное произведение Величин, и угол — инверсный Косинус скалярного произведения, деленного на скалярное произведение Величин.Ссылочные СтрокиВышеупомянутые таблицы и описание иллюстрируют возможность представить строки количественно и измерить подобие между ними. В этой точке индекс для каждой записи в базе данных может быть создан, основываясь на ее относительной позиции в малом наборе ссылочных строк.При выборе ссылочных строк относительная позиция новой записи к каждой из ссылочных строк может быть вычислена. Дополнительно, у каждой записи в базе данных есть своя собственная предварительно вычисленная позиция относительно ссылочных строк. Поэтому приблизительные соответствия могут быть найдены получением записей, индексированных в близости, без необходимости вычисления полной метрики подобия между новой записью и всех записей базы данных. Одна цель выбора ссылочных строк состоит в том, чтобы выбрать записи, которые являются несходными, таким образом, давая лучшую перспективу. Один подход к выбору ссылочных строк обрисовывается в общих чертах в следующих абзацах.Ссылочные строки идентифицируются взятием выборки строк из индексируемой базы данных. Генерируются n-грамм представления для каждой строки в выборке, создавая вектор частот, где i-й компонент вектора содержит число встреч n-граммы в этой строке. Генерируется матрица подобия, измеряя подобие между каждой парой выбранных строк, используя косинусную метрику подобия.Одним способом нахождения несходных компонентов в наборе подобных данных является основной компонентный анализ. Основной компонентный анализ проводится на матрице подобия, и сохраняется первый k основной компонент. Выбранная строка с максимальной нагрузкой на каждом компоненте сохраняется, формируя набор ссылочных строк.Двоичный Индекс и Информационный поискДля группировки подобных строк вместе, чтобы индекс мог быть создан для обеспечения быстрого извлечение кандидата во время приблизительного сравнения строк, каждой потенциальной записи кандидата и каждой записи сравнения, по сравнению с каждой из ссылочных строк, используется SQL вычисление n-грамм частоты подобия.Если вычисление подобия приводит к значению выше, чем предопределенный порог, позиции двоичного ключа, соответствующего ссылочной строке, присваивается значение 1. Если значение ниже порога, соответствующей позиции двоичного ключа присваивается 0.Вычисление Подобия N-ГРАММЫЗапрос SQL был разработан для формирования двумерного вектора, содержащего частоту возникновения всего представленного уникального N-ГРАММа в двух данных строках. Затем запрос делит каждую получившуюся сумму частоты на квадрат величины вектора частоты каждой размерности для получения нормализованной метрики подобия.Такое вычисление представляется следующим примером, в котором строкой сравнения А является «MASTERCARD» и строкой сравнения В — «MASTERCHARGE». Следующая таблица, Таблица 14, является двумерным вектором, содержащим частоты возникновения каждого уникального n-грамма в пределах двух строк сравнения.Таблица 14 ABМА11AS11ST11ТЕ11ER11RC11CA10ER11RD10CH01HA01RG01GE01Величина строки А вычисляется как квадратный корень суммы квадратов для каждого значения частоты в распределении А, определенно, величина строки А 3.0. Величина строки В вычисляется как квадратный корень суммы квадратов каждого значения частоты в размерности В, определенно, величина В 3.3166247903554. Скалярное произведение вектора вычисляется, и для этого примера скалярное произведение 7.0 (число записей таблицы, где и А и В имеют значение 1). Подобие вычисляется как скалярное произведение/(Величина А × Величина В), или 0.703526470681448 для иллюстративного примера.Формирование значения двоичного ключаЕсли вычисление подобия приводит к значению выше, чем предопределенный порог, позиции двоичного ключа, соответствующего ссылочной строке, присваивается значение 1. Если значение ниже порога, соответствующей позиции ключа присваивается 0. В одном варианте осуществления процесс для определения позиции двоичного ключа реализуется использованием комбинации SQL и PL/SQL. Реализация алгоритма минимизирует число необходимых вычислений сравнений строк при использовании аналитического структурированного языка запроса, чтобы автоматически присвоить данной строке двоичное значение ключа, если двоичное значение ключа было вычислено для точно того же значения в более ранней итерации алгоритма. Эта оптимизация выполняется в SQL.Уникальный идентификатор и каждое двоичное значение ключа сохранены в организованной таблице разделенного индекса (IOT) в RDBMS. Каждый уникальный набор данных сохранен в единственном разделе, и никакие два набора данных не используют совместно тот же раздел. Чтобы максимизировать производительность, нагрузка каждого набора данных в таблице выполняется, используя создание таблицы в качестве выбора (CTAS) и изменения раздела. Данные в каждом разделе хранятся в порядке двоичных значений ключа, чтобы максимизировать производительность присоединения.Стандартизация данныхЧтобы улучшить точность сравнений подобия и распределение двоичных значений ключа, в одном из вариантов осуществления данные стандартизируются для известных сокращений и синонимов. Чтобы выполнить такую стандартизацию данных, таблица составляется так, что содержит все известные сокращения и синонимы для различных типов полей, наряду с их соответствующими стандартными представлениями. Тогда алгоритм работает для маркировки каждого элемента данных и отображения любого известного сокращения или синонима к их стандартным формам.Таблица IDFДля более высокой производительности при вычислении весовых коэффициентов TF/IDF для всех n-грамм, существующих в полях, включенных в соединение приблизительного сравнения, создается таблица, содержащая инверсную частоту документа всех двух символов n-грамм в записи кандидата. Формирование всех n-грамм пространства выполняется через PL/SQL, в то время как вычисление IDF делается в SQL ASCII. Таблица IDF хранит значение IDF для каждого возможного n-грамма для каждой категории данных. Таблица — индекс, организованный согласно категориям данных и n-граммам для максимизации производительности присоединения.Перекрестный Атрибут весовых коэффициентов TF/IDFЧтобы присвоить весовой коэффициент, или значение, к каждым двум символам n-грамм, существующих в данной записи для каждого поля, включенного в соединение по приблизительному сравнению, перекрестный атрибут весового коэффициента частоты термина/инверсной частоты документа TF/IDF, значение вычисляется для каждого значения n-грамма. Вычисляются n-грамм терминов и их частоты возникновения в каждой данной записи и поле, используя конвейерную табличную функцию, которая берет REF_CURSOR как вход. Это вычисление немного отличается от традиционных вычислений весовых коэффициентов TF/IDF тем, что после вычисления TF/IDF для каждого n-грамма в каждом поле корректируется весовой коэффициент для всех n-грамм в каждом поле, увеличивая или уменьшая согласно значению суммы весовых коэффициентов n-граммов, в других полях той же самой записи. Этот способ приводит к динамической корректировке уровня записи относительного весовых коэффициентов соответствия n-граммы согласно общему значению значений в каждом поле.Как упомянуто выше, уникальные идентификаторы для каждой записи в данном наборе данных наряду с их n-граммами терминов и вычисленными значениями весовых коэффициентов сохраняются в разделенной Индексно Организованной Таблице (IOT), чтобы максимизировать производительность присоединения. Таблица организуется согласно уникальному идентификатору, категории данных и значению n-грамма термина. Каждый уникальный набор данных сохранен в отдельном разделе в таблице. Каждый раздел загружается, используя составление таблицы в качестве выбора и изменения раздела, чтобы максимизировать производительность загрузки.Запрос соединенияОднажды вычисленные двоичные ключи и перекрестные атрибуты TF/IDF загружаются в RDBMS, аналитический запрос соединения используется, чтобы получить все записи сравнения кандидата и сортировать их согласно их релевантности или качеству сравнения по сравнению с записью сравнения. Это выполняется, сначала объединяя записи со сравнением значений двоичного ключа, затем присоединением n-грамм значений для получившейся записи кандидата и вычисления суммы результатов их весовых коэффициентов.Присвоение оценки доверияРезультаты запроса соединения отправляются через функцию, реализованную в RDBMS, которая выполняет очень низкоуровневое сравнение каждой входящей записи и записи кандидата, затем присваивает оценку доверия, используя статистическую модель для использования в приложении анализа данных Oracle, описанную выше.Вышеупомянутые описанные процессы, связанные с приблизительным сравнением строки, дополнительно иллюстрируются рисунками 9 и 10, которые являются блок-схемами 400 и 450, соответственно иллюстрирующими определение набора ссылочных символьных строк и иллюстрирующими использование набора ссылочных строк для определения метрики подобия символьной строки кандидата. Выбранные строки с максимальной нагрузкой на каждом компоненте сохраняются для формирования набора ссылочных строк. Эти выбранные строки представляют основной компонент в целях корреляции. Метрика подобия основана на многих соответствиях n-грамм при сравнении символьной строки кандидата и отдельных символьных строк в выбранном наборе ссылочных символьных строк.Обращаясь к фигуре 9, база данных включает пространство данных сравнения потенциального кандидата 402, которое иногда упоминается как база данных символьных строк (например, названия и/или данных местоположения для продавцов). Как описано, генерируется 404 случайная выборка полей сравнения или записей базы данных, основанная на, например, оптимизированном поиске набора разнородных символьных строк. Вычисляется матрица подобия 406, и основной компонентный фактор анализа предназначается 408 с получением основных компонентов 410, каждый из которых обращается к соответствующей ссылочной символьной строке. Этот набор ссылочных символьных строк используется для сравнения с символьными строками кандидатов, потому что набор был специально сгенерирован, чтобы включать несходные данные.Обращаясь к фигуре 10, после получения символьной строки кандидата вычисляется подобие 452 между каждой символьной строкой кандидата и ссылочной строкой, связанной с каждым основным компонентом. Как описано здесь, такое сравнение может быть основано на алгоритме соответствия n-граммы, так что создается двоичный ключ 454, показывающий подобие символьной строки кандидата к каждой ссылочной строке и соответствующему основному компоненту. Для быстрого и эффективного приблизительного сравнения символьной строки записи (ссылочные символьные строки) присоединяются 456 к символьным строкам кандидата, основываясь на сравнении их соответствующих двоичных ключей записей. Такой процесс позволяет пользователю быстро получать соответствия высокой вероятности между ссылочными символьными строками (которые могут включать торговое название и/или данные местоположения) к символьной строке кандидата, которая может представлять торговое название и/или данные местоположения. Создавая 458 двоичный ключ для каждой записи базы данных, которая будет сравниваться, может быть сгенерирован 460 файл соответствия ссылочных символьных строк к символьным строкам кандидата.В то время как изобретение было описано с точки зрения различных определенных вариантов осуществления, специалисту в данной области техники понятно, что изобретение может быть осуществлено с изменениями в пределах сущности и контекста формулы.

Математическая психология в гуманитарных исследованиях.

Процесс математизации психологии начался практически с начальных моментов становления ее как экспериментальной дисциплины. Как и в случае других наук, этот процесс проходит ряд стадий. Первая стадия характеризуется применением математических методов для анализа и обработки результатов экспериментального исследования, а также выведением простых законов (этот период проходил с конца XIX до начала XX века); в это время начал использоваться метод факторного анализа, различные модификации метода кластерного анализа, был предложен психофизический закон, построена кривая научения, разработаны различные модели поведения с использованием теории автоматов и теории игр и др. Вторая стадия — (период 40-х-50-х годов) связана с разработкой множества моделей психических процессов и поведения человека с использованием известного математического аппарата. Третий этап (60-е годы по настоящее время) характеризуется выделением математической психологии как отдельной психологической дисциплины, основной целью которой является разработка математического аппарата для моделирования психических процессов и анализа данных психологического эксперимента. Четвертый этап (еще не наступил) должен характеризоваться становлением теоретической психологии и отмиранием математической психологии . С этой точки зрения имеет смысл коротко рассмотреть саму историю математической психологии. Впервые термин «математическая психология» был предложен И. Гербартом в 1822 г., позже его ученик М. Дробиш написал книгу «Первоосновы учения о математической психологии». Однако дальнейшее развитие математическая психология получила лишь в 1963 г. уже в США, где появился учебник по математической психологии. Там же была организована первая лаборатория по математической психологии, и стал издаваться журнал «Математическая психология», который является единственным и в настоящее время. В России математическая психология начала развиваться в семидесятых годах XX в., и одним из ее основателей был (Савченко, Головина, 1999). В XX в. зарождающаяся неклассическая наука уже не отождествлялась с определенностью и детерминированностью. Это привело к интенсивному развитию новых разделов математики, которые могли описывать различные классы неопределенностей. Применение системного подхода к исследованиям сделало возможным изучение сложных, открытых, динамических, самоорганизующихся систем в рамках синергетической парадигмы: изменения и преобразования различных систем первичны, а структуры, порождаемые ими, носят вторичный характер. Это позволило подойти к моделированию неопределенных, неустойчивых, нелинейных систем — именно к ним и относятся психические системы. Как и в случае других наук, этот процесс проходил ряд стадий. Процесс математизации психологии начался практически с момента выделения ее как экспериментальной дисциплины. Применение математических моделей уже на ранних этапах становления психологиии неслучайно и является следствием общей тенденции математизации наук. Первая стадия характеризовалась применением математических методов анализа результатов экспериментального исследования, а также выведением простых законов (период с конца XIX до начала XX в.); в это время начал использоваться метод факторного анализа, были разработаны различные модификации метода кластерного анализа, был предложен психофизический закон, построена кривая научения, разработаны различные модели поведения с использованием теории автоматов и теории игр и др. Вторая стадия (период 1940-1950-х годов) была связана с разработкой множества моделей психических процессов и поведения человека с использованием уже известного математического аппарата. Третий этап (с 1960-х годов по настоящее время) характеризуется выделением математической психологии как отдельной психологической дисциплины, основной целью которой является разработка математического аппарата для моделирования психических процессов и анализа данных психологического эксперимента. Четвертый этап (еще не наступил), возможно, будет характеризоваться становлением теоретической и отмиранием математической психологии (Леонтьев, 1974). Часто математическую психологию (далее «МП») отождествляют с математическими методами, что является ошибочным. Можно сказать, что математическая психология и математические методы соотносятся друг с другом так же, как психология теоретическая и экспериментальная. Применение математических моделей (далее «МП») уже на ранних этапах развития психологической науки неслучайно и является следствием общей тенденции математизации науки. С этой точки зрения в современной накуке математическая психология является важной для вновь становящихся областей психологии, в частности юридической психологии. Объектами математической психологии являются индивидуальный и коллективный субъекты, обладающие психическими свойствами, а также содержательные психологические теории и математические модели. Предметом математической психологии является разработка и применение формального аппарата для адекватного моделирования систем, обладающих психическими свойствами, а методом — математическое моделирование . В основе любого математического метода анализа данных лежит теоретическая модель изучаемого процесса или явления. Проблема математизации психологии широко обсуждалась в 70-х годах XX века . В частности, в работах того времени, посвященных этой проблеме, высказывалось мнение, что математизация психологии часто является данью моде и что любой результат формализованный с помощью математического языка, можно изложить на обыкновенном языке без употребления математических терминов и формул. Другая, противоположная точка зрения заключается в том, что язык математики — это специфический формализованный язык, что это «язык и логика вместе» и что представление результатов исследования в форме математической модели позволяет легче анализировать проблему, получая возможные следствия из сформулированных утверждений автоматически за счет развитого математического формализма . Как бы там ни было, а уже в 50-60-х годах наблюдается бурная интенсификация математизации психологического знания, приведшая к оформлению специальной психологической дисциплины — математической психологии. Все эти факты показывают, что общая тенденция математизации наук не миновала психологию. Интересно отметить еще один факт, имеющий отношение к математизации психологической науки. Многие исследователи-психологи, в общем далекие от применения в своей работе математики, тем не менее, часто используют некоторые математические термины, такие, как непрерывность, случайность, дискретность, линейность, многомерность, бесконечность, информация и т.д. Хотя в этом случае математические термины применяются на интуитивном уровне, часто соответствующий термин применяется адекватно точному его значению, определенному в математике. В этом случае применение соответствующей математической теории может привести к разработке формализованного метода исследования соответствующей психической реальности. Так, идея многомерного пространства лежит в основе метода многомерного шкалирования, применяющегося для изучения семантических пространств, идея случайности лежит в основе разработки математических моделей обучения, идея сочетания непрерывности и дискретности лежит в основе описания многих психических процессов, например, процесса мышления, и т.д. И еще одно замечание. Под математизацией (в узком смысле) психологической науки естественно понимать, как уже было сказано выше, применение формального математического языка описания психических явлений и процессов. Но возможно и более широкое толкование математизации как проникновение в психологию естественнонаучных традиций логической строгости, научности мышления исследователя. Психология включает в себя очень большое количество различных специальных психологических дисциплин — от практических методик в психокоррекции до тонких количественных методов исследования в психофизике, от, скажем, методов психоанализа до математических моделей восприятия, на которых основывается конструирование технических устройств распознавания в рамках проблематики построения систем искусственного интеллекта и т.д. . Таким образом, в психологии переплетаются методы объективные с субъективными. И, естественно, там, где превалируют научные методы, с большей пользой применяются точные математические методы. Хотя возможно применение математического моделирования не только для анализа результатов работы, например, психоаналитика, но и для прогнозирования . Так или иначе, если сфера интересов специалиста-психолога не ограничивается частной практикой, и он не собирается ограничить свою деятельность исключительно консультированием или 59 Прикладные и экспериментальные исследования другими видами психологической практики, ему необходимо обладать хотя бы базовым представлением о том, как: 1) организовать исследование таким образом, чтобы его результаты были доступны обработке в соответствии с целью исследования; 2) правильно выбрать метод исследования; 3) содержательно интерпретировать результаты обработки полученных данных . Основы высшей математики и статистика необходимы тем психологам, которые считают необходимым собственноручно проверять эффективность своей деятельности, создавать новые методики, проводить исследования по интересующим их проблемам. Проведенный в 90-е годы в лаборатории математической психологии анализ разрабатываемых формальных моделей позволил выявить основные тенденции развития математической психологии : Расширение объектов исследования, усложнение организационных принципов проведения конкретных исследовательских работ, интенсивное развитие междисциплинарных исследований приводит к возр ждению интереса к методологическим и теоретическим проблемам. Изменения в образовании, ориентация на компетентностный подход также стимулирует появление новых направлений в развитии теоретической психологии. Появление работ, посвященных этическим, нравственным, религиозным проблемам, что требует использование адекватного математического аппарата (нечеткая логика, мягкие вычисления, вычисления со словами, качественное интегрирование). Математические модели в психологии по методам исследования операций, в основном можно разделить на : а) детерминированные, в которых используются: теория графов; геометрическое моделирование; логико-математические модели; б) стохастические, в которых используются: теория вероятности; теории игр; теории полезности; динамическое программирование; в) синергетические . Аналогичное основание можно использовать и для классификации методов анализа данных (в основе любого метода лежит математическая модель изучаемого процесса). Детерминированные модели в психологии в основном используются при разработке методов анализа данных, для разработки моделей — реже, так как психологическая реальность очень редко может быть описана детерминированными процессами. Стохастическое моделирование является в психологии основным. Синергетический подход позволил подойти к моделированию динамических процессов в психологии, а также перейти от анализа микродинамических процессов к макромоделированию и использовать математическое моделирование в таких «нестандартных» для математики сферах, как, например, работа психолога-консультанта. Последние 10-15 лет психология в России стремительно развивается. Наиболее явными оказываются изменения в сфере психологической практики и психологического образования. Психологическая практика является стержнем развития психологической науки как системы теоретического знания, поэтому при увеличении практических наработок необходима разработка теоретических оснований решения практических задач, для чего может быть полезен формально-логический поход . В настоящее время множество проведенных эмпирических исследований и результаты, полученные практикующими психологами, позволяют развивать в психологии дескриптивный подход моделирования, используя опыт построения нормативных моделей. Появляется возможность построения интегративных моделей. Движущей силой современного развития математической психологии является интерес к научному обобщению результатов, полученных практическими психологами. Процесс развития современной психологии в России в чемто аналогичен развитию России в социальной сфере. Необходима адаптация огромного количества методов и методик, используемых в практической деятельности и перенесенных из зарубежного опыта в нашу реальность. Это требует новых методических приемов, подходов. Существующие нормативные модели, перенесенные из других наук, не всегда адекватны. Расширение объектов исследований, усложнение организационных принципов проведения конкретных исследовательских работ, интенсивное развитие междисциплинарных исследований приводит к возрождению интереса к методологическим и теоретическим проблемам. Изменения в образовании, ориентация на компетентностный подход также стимулируют появление новых направлений в развитии математической психологии. Любое состояние является результатом процесса, поэтому необходимы адекватные методы изучения динамики, например, моделирование динамики на макроуровне на основе результатов моделирования микродинамических процессов, т.е. когда статические состояния рассматриваются как результат моделирования микродинамических процессов и построения предельных циклов. В последнее время появляются работы, посвященные этическим, нравственным, религиозным проблемам, что требует использование адекватного математического аппарата (нечеткая логика, мягкие вычисления, вычисления со словами, качественное интегрирование). Возможно, главной методологической основой современных исследований в психологии является интеграция системного, синергетического подхода и парадигмы активности. Таким образом, на современном этапе методы и модели математической психологии должны обеспечивать реализацию главных принципов синергетического подхода, в частности принципов целостности (неаддитивности), соответствия, эволюции. Одним из принципов синергетического подхода в психологии является принцип учета и моделирования НЕ-факторов, связанных с человеческой психикой и деятельностью (например, с оценками на шкалах). Важнейшей задачей математической психологии является разработка подходов и моделей динамики взаимодействия психических систем. Для моделирования макродинамических процессов как результата моделирования 61 Прикладные и экспериментальные исследования микродинамики и построения предельных циклов наиболее адекватными будут методы, основанные на мультимножествах, логико-алгебраические методы. Использование динамического подхода в психодиагностике позволит реализовать принципиально иной способ построения экспресс-методик. Современный этап развития математической психологии характеризуется не только применением новых математических принципов и методов, а также новым осмыслением уже известных. Разработкой новых подходов к измерению в психологии моделирования макродинамики как результата микродинамических процессов; разработкой шкал, основанных на мягких вычислениях; на применении качественного интегрирования и др. Разработкой моделей ест