ИДЕНТИФИКАЦИЯ БЛОКОВ СВЯЗАННЫХ СЛОВ В ДОКУМЕНТАХ СЛОЖНОЙ СТРУКТУРЫ
IDENTIFICATION OF BLOCKS OF RELATED WORDS IN DOCUMENTS OF COMPLEX STRUCTURE

ОБЛАСТЬ
ТЕХНИКИ
[0001]
Варианты осуществления изобретения относятся в общем к компьютерным системам и, более конкретно, к системам и способам для обнаружения блоков связанных слов или других последовательностей символов в электронных документах сложной структуры с использованием нейронных сетей.
УРОВЕНЬ
ТЕХНИКИ
[0002]
Обнаружение блоков связанных слов в изображении документа является фундаментальной задачей в обработке, хранении и сопоставлении документов. Традиционные подходы обнаружения блоков связанных слов могут включать использование большого количества вручную настраиваемых эвристик и поэтому могут требовать большого количества ручного труда.
РАСКРЫТИЕ
ИЗОБРЕТЕНИЯ
[0003]
Варианты осуществления настоящего изобретения описывают механизмы для обнаружения блоков связанных слов и других последовательностей символов в изображениях документов с использованием нейронных сетей. Способ в соответствии с настоящим изобретением включает в себя: получение множества последовательностей символов документа, где в документе имеется первый блок связанных последовательностей символов, включающий две или более последовательностей символов из множества последовательностей символов; определение множества векторов, при этом вектор из множества векторов представляет одну из множества последовательностей символов; обработку устройством обработки данных множества векторов с использованием первой нейронной сети для: получения множества пересчитанных векторов, при этом каждый из множества пересчитанных векторов пересчитывается на основе значений множества векторов; и определения множества значений связанности, при этом каждое из множества значений связанности соответствует одному из множества соединений между по меньшей мере двумя последовательностями символов из множества последовательностей символов; и определения устройством обработки первого блока связанных последовательностей символов с использованием множества пересчитанных векторов и множества значений связанности.
[0004]
Постоянный машиночитаемый носитель данных в соответствии с настоящим изобретением содержит инструкции, которые при обращении к ним устройства обработки данных приводят к выполнению операций устройством обработки данных, включая: получение множества последовательностей символов документа, где в документе имеется первый блок связанных последовательностей символов, включающий две или более последовательностей символов из множества последовательностей символов; определение множества векторов, при этом вектор из множества векторов представляет одну из множества последовательностей символов; обработку устройством обработки данных множества векторов с использованием первой нейронной сети для: получения множества пересчитанных векторов, при этом каждый из множества пересчитанных векторов пересчитывается на основе значений множества векторов; и определения множества значений связанности, при этом каждое из множества значений связанности соответствует одному из множества соединений между по меньшей мере двумя последовательностями символов из множества последовательностей символов; и определения устройством обработки первого блока связанных последовательностей символов с использованием множества пересчитанных векторов и множества значений связанности.
[0005]
Система в соответствии с настоящим изобретением содержит запоминающее устройство и устройство обработки данных, функционально связанное с запоминающим устройством, при этом устройство обработки данных выполняет следующие функции: получение множества последовательностей символов документа, где в документе имеется первый блок связанных последовательностей символов, включающий две или более последовательностей символов из множества последовательностей символов; определение множества векторов, при этом вектор из множества векторов представляет одну из множества последовательностей символов; обработку устройством обработки данных множества векторов с использованием первой нейронной сети для: получения множества пересчитанных векторов, при этом каждый из множества пересчитанных векторов пересчитывается на основе значений множества векторов; и определения множества значений связанности, при этом каждое из множества значений связанности соответствует одному из множества соединений между по меньшей мере двумя последовательностями символов из множества последовательностей символов; и определения устройством обработки первого блока связанных последовательностей символов с использованием множества пересчитанных векторов и множества значений связанности.
КРАТКОЕ
ОПИСАНИЕ
ЧЕРТЕЖЕЙ
[0006]
Изложение сущности изобретения будет лучше понято из приведенного ниже подробного описания и приложенных чертежей различных вариантов осуществления изобретения. Однако не следует считать, что чертежи ограничивают сущность изобретения конкретными вариантами осуществления; они предназначены только для пояснения и улучшения понимания сущности изобретения.
[0007]
Фиг.
1А
На  представлена схема примера вычислительной системы, в которой могут работать варианты осуществления настоящего изобретения.
[0008]
Фиг.
1B
На  представлен пример документа, который может использоваться для обучения одной или более нейронных сетей, которые могут работать в соответствии с некоторыми вариантами осуществления настоящего изобретения.
[0009]
Фиг.
1C
На  представлен пример предварительной обработки целевого документа, которая может производиться на входе одной или более нейронных сетей, обученных для обнаружения блоков связанных последовательностей символов, в соответствии с некоторыми вариантами осуществления настоящего изобретения.
[0010]
Фиг.
2
На  представлена схема, иллюстрирующая пример системы нейронных сетей, в которой общий контекст документа используется для обнаружения блоков связанных последовательностей символов в электронных документах сложной структуры, в соответствии с некоторыми вариантами осуществления настоящего изобретения.
[0011]
Фиг.
3
На  представлена принципиальная схема, иллюстрирующая пример подсистемы нейронной сети, которая определяет значения связанности и пересчитывает значения векторных представлений для различных последовательностей символов исходного документа на основе общего контекста документа в соответствии с некоторыми вариантами осуществления настоящего изобретения.
[0012]
Фиг.
4A
На  представлена принципиальная схема, иллюстрирующая пример подсистемы нейронной сети, которая прогнозирует классы последовательностей символов и определяет связи блоков в соответствии с некоторыми вариантами осуществления настоящего изобретения.
[0013]
Фиг.
4B
На  представлен пример гипотезы уровня блока, используемой для предсказания блоков связанных последовательностей символов в целевом документе в соответствии с некоторыми вариантами осуществления настоящего изобретения.
[0014]
Фиг.
4C
На  представлен пример гипотезы уровня документа, используемой для предсказания блоков связанных последовательностей символов в целевом документе в соответствии с некоторыми вариантами осуществления настоящего изобретения.
[0015]
Фиг.
5
На  представлена блок-схема, иллюстрирующая пример способа обнаружения блоков связанных последовательностей символов в электронном документе сложной структуры, в соответствии с некоторыми вариантами осуществления настоящего изобретения.
[0016]
Фиг.
6
На  представлена блок-схема последовательности операций, иллюстрирующая один пример способа, в котором нейронные сети используются для определения векторных представлений (например, векторов представления слова) для последовательностей символов, определенных в изображении документа, в соответствии с некоторыми вариантами осуществления настоящего изобретения.
[0017]
Фиг.
7
На  представлена блок-схема последовательности операций, иллюстрирующая другой пример способа, в котором используются нейронные сети для определения связей между последовательностями символов, используя общий контекст документа в соответствии с некоторыми вариантами осуществления настоящего изобретения.
[0018]
Фиг.
8
На  представлена блок-схема последовательности операций, иллюстрирующая способ, в котором используются нейронные сети для создания и проверки множества гипотез о блочных связях последовательностей символов документа, в соответствии с некоторыми вариантами осуществления настоящего изобретения.
[0019]
Фиг.
9
На  представлена схема компьютерной системы в соответствии с некоторыми вариантами осуществления настоящего изобретения.
ОПИСАНИЕ
ПРЕДПОЧТИТЕЛЬНЫХ
ВАРИАНТОВ
РЕАЛИЗАЦИИ
[0020]
Описывается реализация обнаружения блоков связанных слов и других последовательностей символов (например, цифр, графических элементов) в электронных документах сложной структуры с помощью нейронных сетей. Типовой документ может содержать различные блоки информации (например, «номер счета» или «дебитор»), заполненные последовательностями символов (например, 1003572 и «Джон Смит» в виде значений соответствующих полей). Один из традиционных подходов к определению текстовых блоков и их значений в таких документах основан на эвристических правилах. В случае эвристического подхода рассматривается большое количество (например, несколько сотен) документов, например, ресторанных счетов или квитанций, и накапливается статистика относительно того, какой текст (например, ключевые слова) используется рядом с определенным полем и где данный текст можно поместить (например, в поле, справа, слева, выше, ниже). Например, эвристический подход может отслеживать, какое слово или слова часто расположены рядом с полем, указывающим общую сумму покупки, какое слово или слова находятся внутри или рядом с полем, указывающим на применимые налоги, какое слово или слова написаны внутри или рядом с полем, указывающим общую сумму оплаты по кредитной карте и т. д. На основе таких статистических данных при обработке нового счета можно определить, какие данные, обнаруженные в документе, соответствуют определенному полю. Однако эвристический подход не всегда работает точно, поскольку если по какой-либо причине счет был распознан с ошибками, а именно в словосочетаниях «Общий налог» и «Общий платеж» слова «налог» и «платеж» были распознаны плохо, то соответствующие значения могут не пройти классификацию.
[0021]
Дополнительные сложности в распознавании полей в электронных документах возникают в документах, имеющих сложную структуру. В дополнение к полям, которые могут быть заполнены одним или более словами, в документе могут содержаться блоки слов, которые логически связаны между собой. Блок может содержать слова, расположенные в различных позициях внутри документа, которые могут не располагаться рядом друг с другом. Например, документ может содержать различные части адреса отправителя, среди которых «страна», «город», «улица», «номер дома», «почтовый индекс» и другие. Некоторые из этих логически связанных частей могут располагаться в различных строках документа. В некоторых вариантах осуществления блоки связанных слов (или других последовательностей символов) могут располагаться на противоположных концах документа. Например, номер счета продавца может быть расположен в нижней части страницы и может быть логически связан с именем продавца, которое напечатано сверху на странице. В некоторых случаях документ может иметь несколько страниц, и блоки могут содержать связанные последовательности символов, расположенные на нескольких (двух или более) страницах. Эвристические методы в особенности неэффективны при распознавании блоков в документах такой сложной структуры.
[0022]
Варианты реализации настоящего изобретения устраняют отмеченные выше и другие недостатки, предоставляя механизмы идентификации в документах блоков связанных последовательностей символов с использованием нейронных сетей. Описанный механизм может автоматически обнаруживать блоки, содержащиеся в документе, и определять связанные последовательности символов в таких блоках. Используемый в настоящем документе термин «электронный документ» (также называемый в настоящем документе просто «документ») может относиться к любому документу, изображение которого может быть доступно для вычислительной системы, которая выполняет идентификацию блоков связанных последовательностей символов. Изображение может быть отсканированным изображением, сфотографированным изображением или любым другим представлением документа, которое может быть преобразовано в форму данных, доступную для компьютера. Например, под термином «электронный документ» может подразумеваться файл, содержащий один или более элементов цифрового содержимого, которые могут быть переданы визуально для создания визуального представления электронного документа (например, на дисплее или на печатном носителе). В соответствии с различными вариантами осуществления настоящего изобретения документ может быть представлен в виде файла любого подходящего формата, например, PDF, DOC, ODT, JPEG и др. Несмотря на то, что документ может быть представлен в электронном (например, цифровом) формате файла, предполагается, что документ в электронном виде не имеет разделов и что разметка документа - места расположения различных текстовых полей, таблиц, параграфов и т. д. - не указана в электронном файле. (Как, например, было бы, если бы документ был первоначально выпущен в электронном формате - как электронный счет или другие подобные электронные документы - с уже указанным расположением полей и блоков.)
[0023]
«Документ» может представлять собой финансовый документ, юридический документ или любой другой документ, например, документ, который создается путем заполнения полей буквенно-цифровыми символами (например, буквами, словами, цифрами) или изображениями. «Документ» может представлять собой документ, который напечатан, набран или написан от руки (например, путем заполнения стандартной формы). «Документ» может представлять собой форму документа, которая содержит множество полей, таких как текстовые поля (содержащие цифры, буквы, слова, предложения), графическое поле (содержащее логотип или любое другое изображение), таблицы (содержащие строки, столбцы, ячейки) и т. д. Некоторые поля могут быть объединены в логические блоки. При использовании в настоящем документе «поле» может означать любое поле данных в документе, которое содержит буквенно-цифровые знаки, а «блок» может означать логическую связь нескольких полей, даже если соответствующие поля расположены, возможно, в различных частях документа.
[0024]
К документам, содержащим блоки, помимо прочего, могут относиться документы, имеющие стандартное содержимое (предопределяемое официальными правилами или установившейся практикой хозяйственной деятельности), но гибкое распределение этого содержимого в документе - заявки на выдачу кредитов (в т. ч. ипотечных), договоры купли-продажи объектов недвижимости, графики платежей по кредиту, договоры страхования, полицейские рапорты, заказы на закупку, счета и т. д. Документы могут содержать блоки, которые встречаются однажды или повторяются несколько раз в одной форме (например, адреса нескольких покупателей), либо блоки, которые могут иметь несколько значений (например, несколько номеров счетов продавца).
[0025]
«Последовательность символов» в настоящем документе может означать любую последовательность букв, цифр, глифов, графических элементов, знаков пунктуации и других подобных элементов. Последовательность символов может быть набрана, выдавлена, напечатана, нарисована или написана вручную с использованием любого шрифта, набора, рисунка, штампа, курсивного письма и аналогичных средств. Символы в последовательности символов могут разделяться пробелами. Последовательность символов может включать логотип компании, подпись, изображение товара, используемого вместо описания товара (или в дополнение к описанию товара), или любое другое изображение, которое может быть включено в документ. В настоящем описании изобретения иногда, для лаконичности и краткости, «слово» может означать любую последовательность символов.
[0026]
Технология, описанная в настоящем документе, позволяет автоматически обнаруживать в документах блоки из связанных последовательностей символов с помощью искусственного интеллекта. Эта технология может включать в себя обучение искусственной нейронной сети обнаружению последовательностей символов в документах. В некоторых вариантах осуществления после представления последовательностей символов, обрабатываемых некоторой нейронной сетью (сетями), последовательность символов может быть определена как относящаяся к определенному «классу», который может указывать на тип содержимого, выраженного в последовательности символов. Например, последовательность символов может быть классифицирована как «имя», «наименование компании», «телефон», «факс», «улица», «имя поставщика», «тип оплаты», «способ оплаты», «тип товара», «количество товара» или любая другая запись, которая может присутствовать в документе. Искусственная нейронная сеть (сети) может содержать множество нейронов, связанных с получаемыми при обучении весами и смещениями. Эти нейроны могут быть организованы в слои. Нейронная сеть может быть обучена на обучающей выборке документов, содержащих известные блоки логически связанных слов. Например, обучающая выборка данных может содержать примеры документов, имеющих один или более блоков связанных слов в качестве обучающих входных данных, и идентификаторы слов (классы или типы), которые корректно определяют (например, классифицируют) слова в блоках связанных слов, в качестве обучающих выходных данных. Например, логический блок «адрес» может содержать слова, определенные как «улица», «город», «страна» и т.д. Логический блок «информация о покупателе» может содержать слова, которые определены как «коммерческое наименование покупателя», «место регистрации», «номер банковского счета» и другие.
[0027]
Нейронная сеть может построить наблюдаемый результат (тестовую выборку) для входных данных обучения. Наблюдаемый результат работы нейронной сети можно сравнить с результатом обучения, включенным в обучающую выборку данных, и ошибка (отклонение) может распространяться назад на предыдущие слои нейронной сети, параметры которой (веса и смещения нейронов) могут регулироваться соответствующим образом. В ходе обучения нейронной сети параметры нейронной сети могут быть отрегулированы для оптимизации точности предсказания.
[0028]
После обучения нейронная сеть может быть использована для автоматического обнаружения блоков связанных слов и выбора наиболее вероятного класса для каждого из обнаруженных слов. Использование нейронных сетей может избавить от необходимости ручной разметки слов в документах на этапе идентификации. Механизмы, для обнаружения в документе блоков связанных слов, описанные в настоящем документе, позволяют повысить качество обнаружения в результате выполнения обнаружения блоков с помощью обученной нейронной сети таким способом, который учитывает контекст документа в целом. Например, нейронные сети, настроенные и обученные в соответствии с вариантами осуществления настоящего изобретения, могут быть способны обнаруживать блоки из слов и классифицировать слова, принадлежащие к обнаруженным блокам, на основе других слов, имеющихся во всем документе. Например, нейронная сеть может определить числовую последовательность в нижнем левом углу документа, помеченную характерным жирным двоеточием, в качестве кода банка. Следовательно, нейронная сеть, обученная так, чтобы учитывать контекст всего документа, может быть способна найти другие слова, которые, возможно, принадлежат к тому же блоку (например, код банка). Кроме того, основываясь на контексте всего документа, нейронная сеть может быть способна идентифицировать другие логические блоки, которые, возможно, имеются в том же документе. На выходе процесса обнаружения документ может быть разделен на блоки из связанных слов. Внутри каждого идентифицированного блока может быть определена и сохранена информация, которую несут различные слова. Дополнительно могут иметься слова, не связанные в блоки; такие слова могут распознаваться как значения, включенные в несвязанные поля.
[0029]
Нейронная сеть, обученная в соответствии с вариантами осуществления настоящего изобретения, может применяться для идентификации документов любого типа и может обеспечивать эффективное обнаружение блоков, повышая таким образом, как точность идентификации, так и скорость обработки вычислительного устройства, реализующего такую идентификацию.
[0030]
Фиг.
1А
На  представлена блок-схема примера вычислительной системы 100, в которой могут работать варианты осуществления настоящего изобретения. Как показано на изображении, система 100 включает вычислительное устройство 110, хранилище 120 и сервер 150, подключенный к сети 130. Сеть 130 может быть общественной сетью (например, Интернет), частной сетью (например, локальной сетью (LAN) или распределенной сетью (WAN)), а также их комбинацией.
[0031]
Фиг.
9
Вычислительное устройство 110 может быть настольным компьютером, портативным компьютером, смартфоном, планшетным компьютером, сервером, сканером или любым подходящим вычислительным устройством, которое в состоянии использовать технологии, описанные в настоящем изобретении. В некоторых вариантах осуществления вычислительное устройство 110 может быть и (или) включать в себя одно или более вычислительных устройств 1300 с .
[0032]
Документ 140 может быть получен вычислительным устройством 110. Документ 140 может содержать любой текст, изображения или таблицы, например, один или более символов (буквы и (или) цифры), слов, предложений и т. д. Документ 140 может быть любого предопределенного типа, например, «визитная карточка», «счет», «паспорт», «полис медицинского страхования», «опросный лист» и т. д. В некоторых вариантах осуществления тип документа 140 может быть указан пользователем и сообщен вычислительному устройству 110 вместе с документом 140.
[0033]
Документ 140 может быть получен любым подходящим способом. Например, вычислительное устройство 110 может получить цифровую копию документа 140 путем сканирования документа или фотографирования документа. Кроме того, в тех случаях, когда вычислительное устройство 110 представляет собой сервер, клиентское устройство, подключенное к серверу по сети 130, может загрузить цифровую копию документа 140 на сервер. В тех случаях, когда вычислительное устройство 110 является клиентским устройством, соединенным с сервером по сети 130, клиентское устройство может загрузить документ 140 с сервера или из хранилища 120.
[0034]
Документ 140 может быть использован для обучения набора моделей машинного обучения или может быть новым документом, для которого следует выполнить обнаружение и (или) классификацию полей. В некоторых вариантах осуществления при использовании для обучения одной или более моделей (нейронных сетей) 114 машинного обучения для последующего распознавания, документ 140 может быть соответствующим образом подготовлен для облегчения обучения. Например, в документе 140 могут быть вручную или автоматически размечены текстовые последовательности или элементы таблиц, могут быть отмечены символы, текстовые последовательности, графические изображения или элементы таблиц могут быть нормализованы, масштабированы и (или) бинаризованы. В некоторых вариантах осуществления изобретения текст в документе 140 может распознаваться с использованием любой подходящей технологии оптического распознавания символов (OCR).
[0035]
В одном варианте осуществления вычислительное устройство 110 может содержать механизм 111 обнаружения блоков для обнаружения блоков из связанных последовательностей символов. Механизм 111 обнаружения блоков может содержать инструкции, сохраненные на одном или более физических машиночитаемых носителях данных вычислительного устройства 110 и выполняемые на одном или более обрабатывающих устройствах вычислительного устройства 110. В одном варианте осуществления механизм 111 обнаружения блоков может использовать набор обученных моделей 114 машинного обучения. Модели 114 машинного обучения обучаются и используются для обнаружения и (или) классификации полей во входном документе.
[0036]
Механизм 111 обнаружения блоков может предварительно обрабатывать любые документы перед использованием этих документов для обучения моделей 114 машинного обучения и (или) применения обученных моделей 114 машинного обучения к документам. В некоторых случаях обученные модели 114 машинного обучения могут быть частью механизма 111 обнаружения блоков либо могут быть доступны с другой машины (например, сервера 150) через механизм 111 распознавания блоков. На основе выходных данных обученных моделей 114 машинного обучения механизм 111 обнаружения блоков может обнаружить один или более блоков из связанных слов и одно или более несвязанных полей. Механизм 111 обнаружения блоков может определить принадлежность различных слов документа к идентифицированным блокам и (или) к несвязанным полям.
[0037]
Механизм 111 обнаружения блоков может быть клиентским приложением или же сочетанием клиентского компонента и серверного компонента. В некоторых вариантах осуществления механизм 111 обнаружения блоков может быть запущен на исполнение исключительно на вычислительном устройстве клиента, например, это могут быть сервер, персональный компьютер, планшетный компьютер, смартфон, ноутбук, фотокамера, видеокамера и т. д. Альтернативно клиентский компонент механизма 111 обнаружения блоков, исполняемый на клиентском вычислительном устройстве, может получать документ и передавать его на серверный компонент механизма 111 обнаружения блоков, исполняемый на серверном устройстве, где выполняется обнаружение блоков. Затем серверный компонент механизма 111 обнаружения блоков может возвращать результат распознавания (например, множество обнаруженных блоков и множество слов, принадлежащих к обнаруженным блокам) клиентскому компоненту механизма 111 обнаружения блоков, выполняемому на клиентском вычислительном устройстве, для сохранения. Альтернативно серверный компонент механизма 111 обнаружения блоков может передавать результат распознавания другому приложению. В других вариантах осуществления механизм 111 обнаружения блоков может исполняться на серверном устройстве в качестве интернет-приложения, доступ к которому обеспечивается через интерфейс браузера. Серверное устройство может быть представлено в виде одной или более вычислительных систем, например, одним или более серверов, рабочих станций, больших ЭВМ (мейнфреймов), персональных компьютеров (ПК) и т. п.
[0038]
Фиг.
1А
Фиг.
2
3
4A
Сервер 150 может быть стоечным сервером, маршрутизатором, персональным компьютером, карманным персональным компьютером, мобильным телефоном, портативным компьютером, планшетным компьютером, фотокамерой, видеокамерой, нетбуком, настольным компьютером, медиацентром или их сочетанием и (или) содержать указанное оборудование. Сервер 150 может содержать обучающую систему 151. Обучающая система 151 может строить модель (модели) 114 машинного обучения для обнаружения связанных блоков символов. Модель (модели) 114 машинного обучения, приведенная на , может быть обучена обучающей системой 151 с использованием обучающих данных, которые содержат обучающие входные данные и соответствующие обучающие выходные данные (правильные ответы на соответствующие обучающие входные данные). Обучающая система 151 может находить в обучающих данных шаблоны, которые связывают обучающие входные данные с обучающими выходными данными (предсказываемым результатом), и предоставлять модели 114 машинного обучения, которые используют эти шаблоны. Как более подробно будет описано ниже, набор моделей 114 машинного обучения может быть составлен, например, из одного уровня линейных или нелинейных операций (например, машина опорных векторов (SVM)) или может представлять собой глубокую нейронную сеть, например, модель машинного обучения, составленную из нескольких уровней нелинейных операций. Примерами глубоких нейронных сетей являются нейронные сети, включая сверхточные нейронные сети, рекуррентные нейронные сети (RNN) с одним или более скрытыми слоями и полносвязные нейронные сети. В некоторых вариантах осуществления модели 114 машинного обучения могут содержать одну или более нейронных сетей, как описано в связи с ,  и .
[0039]
Модели 114 машинного обучения могут быть обучены для обнаружения блоков связанных слов и несвязанных полей в документе 140 и для определения наиболее вероятных классов различных слов в документе 140. Обучающая система 151 может создавать обучающие данные для обучения моделей 114 машинного обучения. Обучающие данные могут храниться в хранилище 120 и содержать один или более наборов обучающих входных данных 122 и один или более наборов обучающих выходных данных 124. Такие обучающие данные могут также содержать данные 126 о сопоставлении обучающих входных данных 122 с обучающими выходными данными 124. В некоторых вариантах осуществления данные 126 сопоставления могут содержать перечень, состоящий по меньшей мере из нескольких блоков обучающих входных данных 122, и перечень соответствия значениям блоков связанных последовательностей символов. Например, данные сопоставления могут содержать блок «адрес продавца» и перечень из нескольких (или всех) значений, т.е. последовательностей символов, которые могут соответствовать «адресу продавца» в конкретном входном обучающем документе. Обучающие входные данные 122 могут включать обучающую выборку документов, содержащих текст, изображения или таблицы (иначе «обучающие документы»). Каждый из обучающих документов может быть документом, имеющим один или более известных блоков из связанных слов. Выходными данными 124 обучения могут быть классы слов, заполняющих известные блоки (и несвязанные поля). Например, первый обучающий документ в первой обучающей выборке может содержать первый известный блок (например, финансовую информацию продавца). Первый обучающий документ может быть первым из обучающих входных данных 122, который можно использовать для обучения модели (моделей) 114 машинного обучения. Обучающие выходные данные 124, соответствующие первым обучающим входным данным 122, могут содержать некоторый класс, представляющий каждое слово (в первых обучающих входных данных 122), принадлежащее к первому известному блоку слов (например, «номер счета», «код банка», «банк» и т. п.). В ходе обучения обучающая система 151 может находить шаблоны в обучающих данных 126, которые можно использовать для отображения обучающих входных данных на обучающие выходные данные. Такие шаблоны могут быть впоследствии использованы моделью (моделями) 114 машинного обучения для дальнейшего предсказания. Например, при получении на входе документа, который содержит блоки (и несвязанные поля) слов, которые следует идентифицировать, обученная модель (модели) 114 машинного обучения может определить один или несколько блоков связанных слов, предсказать класс, к которому принадлежат различные слова блока, и вывести (сохранить) предсказанные связи слов и их классов. В качестве другого примера обученная модель (модели) машинного обучения может выполнять поиск конкретных блоков, представляющих интерес для клиента (например, блоков, которые были обозначены клиентом как важные), и определять все слова в документе, принадлежащие таким полям. Например, клиента могут интересовать только блоки, которые содержат финансовую информацию, но не перечни товаров.
[0040]
Хранилище 120 может представлять собой постоянную память, которая в состоянии сохранять электронные документы, а также структуры данных для выполнения распознавания символов в соответствии с вариантами осуществления настоящего изобретения. Хранилище 120 может располагаться на одном или более запоминающих устройствах, таких как основное запоминающее устройство, магнитные или оптические запоминающие устройства на основе дисков, лент или твердотельных накопителей, NAS, SAN и т. д. Несмотря на то, что хранилище изображено отдельно от вычислительного устройства 110, в некотором варианте осуществления хранилище 120 может быть частью вычислительного устройства 110. В некоторых вариантах осуществления хранилище 120 может представлять собой подключенный к сети файловый сервер, в то время как в других вариантах осуществления хранилище 120 информации может представлять собой какой-либо другой тип энергонезависимого запоминающего устройства, например, объектно-ориентированную базу данных, реляционную базу данных и т. д., которая может находиться на сервере или на одной или более различных машинах, подключенных к нему через сеть 130.
[0041]
NN
В некоторых вариантах осуществления обучающая система 151 может обучать одну или более искусственных нейронных сетей (модели 114), каждая из которых содержит множество нейронов, для обнаружения полей в соответствии с некоторыми вариантами осуществления настоящего изобретения. Каждый нейрон может получать свои входные данные от других нейронов или из внешнего источника и генерировать результат, применяя функцию активации к сумме взвешенных входных данных и полученному при обучении значению смещения. Нейронная сеть может содержать множество нейронов, распределенных по слоям, включая входной слой, один или более скрытых слоев и выходной слой. Нейроны соседних слоев соединены взвешенными дугами. Веса дуг определяются на этапе обучения сети на основе обучающей выборки данных, которая содержит множество документов с известными блоками и классами слов. В иллюстративном примере все веса дуг могут первоначально назначаться некоторыми случайными значениями. Для всех входящих данных 122 в обучающей выборке система обучения 151 может активировать соответствующую нейронную сеть (выбор соответствующей нейронной сети может выполняться механизмом 112 кластеризации). Наблюдаемый выход нейронной сети OUTPUT (ВХОДНЫЕ ДАННЫЕ ОБУЧЕНИЯ) сравнивается с желаемыми выходными данными 124 обучения, заданными обучающей выборкой данных:
Сравнение
NN
: OUTPUT (ВХОДНЫЕ ДАННЫЕ ОБУЧЕНИЯ) в сравнении с ВЫХОДНЫМИ ДАННЫМИ ОБУЧЕНИЯ.
NN
NN
NN
Фиг.
2
3
4
Полученная погрешность - разница между выходом нейронной сети OUTPUT и желаемым РЕЗУЛЬТАТОМ ОБУЧЕНИЯ - распространяется обратно на предыдущие уровни нейронной сети, в которых веса настраиваются таким образом, чтобы изменить OUTPUT и приблизить его к РЕЗУЛЬТАТУ ОБУЧЕНИЯ. Такая корректировка может повторяться до тех пор, пока ошибка в результатах для конкретных обучающих входных данных 122 не будет удовлетворять заранее определенным условиям (например, станет ниже заранее определенного порогового значения). Впоследствии могут быть выбраны другие обучающие входные данные 122, может быть сгенерирован новый OUTPUT, может быть реализован новый ряд корректировок и т. д. до тех пор, пока нейронная сеть не будет обучена с достаточной степенью точности. В некоторых вариантах осуществления этот метод обучения может применяться для обучения одной или более искусственных нейронных сетей, проиллюстрированных на ,  и .
[0042]
После того, как модели 114 обучены, набор моделей 114 машинного обучения может быть передан механизму 111 обнаружения блоков для анализа целевых документов. Например, механизм 111 обнаружения блоков может ввести целевой документ на вход набора моделей 114 машинного обучения. Механизм 111 обнаружения блоков может получить один или более идентифицирующих выходов от набора обученных моделей машинного обучения и может извлечь из идентифицирующих выходных данных набор предсказанных блоков связанных слов и классы этих слов. Предсказанный класс слова может предположительно (или наиболее вероятно) характеризовать тип, представленный этим словом (например, «имя», «адрес», «наименование компании», «логотип», «адрес электронной почты» и т. п.).
[0043]
Фиг.
1B
Фиг.
1B
На  представлен пример документа 140, который может использоваться для обучения одной или более нейронных сетей, которые могут работать в соответствии с некоторыми вариантами осуществления настоящего изобретения. Как показано, документ 140 (например, заказ на поставку, заполненный продавцом) может содержать разнообразные последовательности символов, таких как имя 150 продавца, логотип 151 продавца, адрес продавца, включая улицу 152, город 154, почтовый код 156, страну 158 и другие данные. Документ может также содержать имя 160 покупателя и адрес покупателя, который может содержать улицу 162, город 164, почтовый код 166, страну 168 и др. Документ 140 может содержать перечень товаров 190-192, которые будут куплены, их соответствующие количества 191-193, промежуточные итоги 196-198, а также общую предложенную сумму 199. Документ 140 может содержать финансовую информацию продавца и покупателя, такую как IBAN 170 продавца, BIC/SWIFT 172 продавца, IBAN 180 покупателя и BIC/SWIFT 182 продавца. Обучающий документ 140 может содержать дополнительную информацию, которая не показана на . В некоторых вариантах осуществления обучающий документ 140 может быть многостраничным документом.
[0044]
Фиг.
1B
Как показано на , некоторые слова, которые могут быть логически объединены в блоки, могут располагаться в различных местах документа 140. Например, первый логический блок (выделенный пунктирными рамками и соединениями) может содержать имя 150 продавца, адрес 152-158 и финансовую информацию продавца 170-172. Второй логический блок (выделенный точечными рамками и соединениями) может содержать имя 160 покупателя, адрес 162-168 и финансовую информацию покупателя 180-182. Товары A 190, количество товаров A 193 и промежуточный итог для товаров A 196 могут представлять третий логический блок (не показан) и так далее. Некоторые слова могут принадлежать к несвязанным полям, например, общая сумма 199. Блочные связи в обучающем документе 140 могут быть определены и использованы в обучении моделей 114 машинного обучения. Блочные связи могут зависеть от выполняемой задачи и целей клиента. Например, в зависимости от задачи, некоторые блоки в документе 140 могут иметь меньше или больше связей. Например, в некоторых вариантах осуществления блок продавца (в пунктирной рамке) может включать только имя 150 продавца и финансовую информацию 170-172, но не включать адрес 152-158. Соответственно, обнаружение блоков можно настроить по потребностям конкретного клиента. Поэтому обучающие документы 140 могут быть выбраны из действительных документов, используемых клиентом. Другой клиент, который может интересоваться другой информацией, может использовать модели 114 машинного обучения, обученные для обнаружения другого набора блочных связей. Если потребности клиента со временем изменяются, модели 114 машинного обучения могут быть повторно обучены с использованием нового набора обучающих документов. Для удовлетворения изменяющихся потребностей различных клиентов обучение (или повторное обучение) может производиться на стороне клиента.
[0045]
Документ 140, подготовленный как обучающие входные данные 122, может содержать данные 126 сопоставления, связанные с документом 140. Данные 126 сопоставления могут определять различные блоки связанных слов и могут дополнительно определять слова в этих блоках как принадлежащие к конкретным классам слов. Например, данные сопоставления могут указывать слово по его координатам (например, координаты ограничительной рамки, содержащей это слово), указывать класс слова и блок связанных слов (если имеется), к которому принадлежит указанное слово.
[0046]
После того как модель 114 обучена на основе обучающего документа 140, модель (модели) 114 могут иметь способность находить и идентифицировать блоки связанных слов в обучающем документе 140, а также в целевых документах, которые не использовались в обучении.
[0047]
Фиг.
1C
N
N!
На  представлен пример предварительной обработки целевого документа 145, который может подаваться на вход одной или более нейронных сетей, обученных на обнаружение блоков из связанных последовательностей символов, в соответствии с некоторыми вариантами осуществления настоящего изобретения. Документ 145 может иметь разметку, отличающуюся от разметки обучающих документов (например, документа 140). Хотя в документе 145 показаны те же блоки, что и в обучающем документе 140, могут иметься дополнительные блоки документа 145, отсутствующие в обучающих документах 140. И наоборот, некоторые блоки обучающего документа 140 могут отсутствовать в документе 145. В некоторых вариантах осуществления перед вводом документа 145 в обученную нейронную сеть (сети) механизм 111 обнаружения блоков может создать множество соединений (показаны пунктирными линиями) между различными словами документа 145. Эти соединения могут служить возможными связями между словами, хотя на этом этапе процесса обнаружения - не обязательно вероятными. В некоторых вариантах осуществления соединения могут быть между всеми словами и всеми другими словами документа 145. Например, если документ содержит  слов, то количество попарных соединений между словами может достигать . В документах с большим количеством слов отслеживание таких соединений и оценка вероятности, что эти соединения указывают вероятные связи между соответствующими словами, может быть чрезмерно сложной вычислительной задачей. Поэтому механизм 111 обнаружения блоков может уменьшить количество соединений, используя алгоритм, который исключает соединения, представляющие маловероятные связи. В некоторых вариантах осуществления такой алгоритм сам может быть основан на модели нейронной сети, которую можно обучить для сохранения только тех соединений, для которых вероятность представления реальной связи не менее 10 %, 20 % или любого другого предварительно заданного значения. Соответствующая модель нейронной сети может быть обучена с помощью некоторого количества обучающих документов с размеченными действительными связями. Модель нейронной сети может обучаться до тех пор, пока не будет постоянно исключать не более, чем определенное первое пороговое значение (например, не более 10 %) действительных связей, и (или) не менее, чем определенное второе пороговое значение (например, не менее 60 %) соединений между словами, которые не связаны между собой. Например, модель может быть обучена для исключения соединений между логотипом 151 продавца и общей суммой 199.
[0048]
Соединения могут быть горизонтальными (как, например, между IBAN 170 продавца и BIC/SWIFT 172 продавца), вертикальными (как, например, между улицей 152 продавца и городом 154 продавца) или произвольными (как, например, между именем 150 продавца и именем 160 покупателя). В некоторых вариантах осуществления соединения могут быть трехсторонними (либо четырехсторонними и т. д.) кластерными соединениями (таким как кластерное соединение, связывающее IBAN 180 покупателя, BIC/SWIFT 182 покупателя и BIC/SWIFT 172 продавца. Помимо исключения соединений, представляющих маловероятные связи, на этом этапе процесса компьютерная система, выполняющая обнаружение блоков, может быть безразлична в отношении вероятности того, что созданные соединения могут представлять действительные связи блоков, которые будут определяться, как описано ниже. В некоторых вариантах осуществления только малая часть всех выявленных соединений будет в конечном итоге определена как действительные связи блоков.
[0049]
Фиг.
2
На  представлена блок-схема, иллюстрирующая пример 200 системы нейронных сетей, в которой общий контекст документа используется для обнаружения блоков связанных последовательностей символов в электронных документах сложной структуры, в соответствии с некоторыми вариантами осуществления настоящего изобретения. Система 200 нейронных сетей может содержать множество нейронов, связанных с получаемыми при обучении весами и смещениями. Эти нейроны могут быть организованы в слои. Некоторые из слоев могут быть скрытыми. Как показано, система 200 нейронных сетей может включать в себя подсистему A 240, подсистему B 260 и подсистему C 280. Каждая из подсистем 240, 260 и 280 может содержать несколько нейронных слоев и может быть настроена для выполнения одной или более функций для обнаружения блоков связанных слов в соответствии с настоящим изобретением.
[0050]
Входом механизма 111 обнаружения блоков может быть один или более документов 210. Если документы 210 имеют физический вид (например, на бумаге, пленке и т. п.), то механизм 111 обнаружения блоков или вычислительное устройство 110 (или сервер 150) могут получать изображения таких физических документов и преобразовывать эти изображения в цифровые изображения (например, путем сканирования) в одном из цифровых форматов (JPEG, TIFF, GIG, BMP, CGM, SVG и др.). Механизм 111 обнаружения блоков может также выполнять оптическое распознавание символов из цифровых изображений.
[0051]
В некоторых вариантах осуществления получение изображения документа может выполняться непосредственно перед обработкой изображения 210 документа системой 200 нейронной сети. В некоторых вариантах осуществления получение изображения документа может выполняться в некоторый момент в прошлом, и изображение 210 документа может быть получено из локального или сетевого (например, облачного) хранилища. С изображением 210 документа может быть выполнено оптическое распознавание символов для получения распознанного текста документа, а в некоторых вариантах осуществления для разделения распознанного текста на множество последовательностей символов, представляющих различные слова, цифры, предложения, изображения и т. д. в документе. Аналогично, оптическое распознавание может быть выполнено непосредственно перед дальнейшей обработкой в системе 200 нейронных сетей либо в той же точке впоследствии. Оптическое распознавание символов может дополнительно сопровождаться предварительной обработкой изображения 210 документа для улучшения его качества, например, масштабирования, изменения соотношения сторон, преобразования цветного изображения в полутоновое, нормализации, выделения данных, усиления, бинаризации и так далее.
[0052]
Результатом оптического распознавания символов изображения 210 документа может быть набор распознанных последовательностей символов SymSeq(x,y), связанных с координатами x, y изображения 210 документа. Последовательности символов SymSeq могут содержать один или несколько буквенно-цифровых символов, которые могут быть объединены в слоги, слова и (или) предложения. Последовательности символов SymSeq могут включать один или несколько знаков препинания, таких как запятая, точка, многоточие или любые другие знаки. Последовательности SymSeq могут быть горизонтальными, вертикальными или наклонными линиями таблиц, либо трехсторонними или четырехсторонними пересечениями линий. Линии могут быть одинарными, двойными и т. д. Последовательности символов SymSeq могут быть любыми комбинациями символов, знаков пунктуации и (или) линий. В некоторых вариантах осуществления для формирования последовательностей символов SymSeq, содержащихся в изображении 210 документа, ядро системы 111 обнаружения блоков (или любой другой компонент, который выполняет или выполнил оптическое распознавание символов на изображении 210 документа) может использовать подходящие способы распознавания символов, разделять текст документа на несколько слов и извлекать несколько последовательностей символов из слов.
[0053]
Выявленные последовательности символов SymSeq могут сопоставляться с соответствующими областями изображения 210 документа, где расположены такие последовательности. Например, каждая последовательность SymSeq может быть связана с одним или несколькими наборами координат (x,y), которые определяют местоположения последовательностей. Координаты могут быть декартовыми или любыми другими (например, полярными) координатами, которые могут быть удобными при определении местоположений последовательностей символов. В одном из вариантов реализации отдельный символ, знак пунктуации или короткая линия могут быть определены одним набором координат (x,y), тогда как более длинные последовательности (слова, предложения, длинные линии) могут быть определены несколькими наборами (x,y), такими как координаты четырех углов области, содержащей последовательность. Линии могут быть определены координатами двух концов линии. Пересечение двух линий (например, трехстороннее или четырехстороннее пересечение) может быть определено по координатам концов всех линий, а также по координатам пересечения. В настоящем изобретении (x,y) обозначает любое определение последовательностей символов с одним или более наборами координат, которые могут потребоваться для конкретной последовательности SymSeq.
[0054]
Механизм 111 обнаружения блоков может подавать последовательности символов SymSeq(x,y) на вход подсистемы A 240 для формирования векторного представления в пространстве признаков для каждой из последовательностей символов: SymSeq(x,y) → vec(x,y). Каждый из векторов в пространстве признаков vec(x,y) может представлять собой символическое векторное представление (эмбеддинг) одной из последовательностей символов (например, слов/предложений, знаков пунктуации и (или) линий), что также упоминается как вектор представления слова. В некоторых вариантах осуществления каждое векторное представление символа в таблицах может иметь определенную длину (то есть заранее заданную длину). Если длина последовательности символов меньше определенной длины, то к ней могут быть добавлены заранее заданные значения для того, чтобы создать векторное представление символа заранее заданной длины (например, к векторам могут быть добавлены нули). Термины «векторное представление символа» или «векторное представление», используемые в данном документе, могут означать вектор действительных чисел или любое другое цифровое представление последовательности символов. Векторное представление слова можно получить, например, с помощью нейронной сети, реализующей математическое преобразование символов (слов/знаков пунктуации/строк таблиц) с помощью функций эмбеддингов, отображая такие символы на их цифровые представления.
[0055]
Эмбеддинги слов vec(x,y) - также называемые в настоящем документе как векторные представления последовательностей символов SymSec(x,y) или просто как «векторы» - могут быть созданы с использованием любой подходящей модели или комбинации моделей, таких как Word2Vec, GloVe, FastText и др. Подсистема A 240 может использовать множество нейронных слоев, таких как входной слой, выходной слой и один или несколько скрытых слоев. Подсистема A 240 может представлять собой рекуррентную нейронную сеть (RNN), RNN на уровне символов, долгую краткосрочную память (LSTM) или любую другую подобную сеть, в том числе любую комбинацию таких сетей. Подсистема A 240 может работать со словарем эмбеддингов, который может включать в себя векторные представления типичных слов, найденных в документах соответствующих типов. Подсистема A 240 может быть обучена генерировать такие векторные представления последовательностей символов SymSeq(x,y), которые имеют близкие числовые значения vec(x,y) для слов, имеющих близкие семантические значения (например, «число» и «количество»), или которые могут быть найдены в непосредственной близости друг от друга (например, «сумма» и «предложенная»). Подсистема A 240 может быть предварительно обучена с использованием входных обучающих входных данных 122 и обучающих выходных данных 124, как описано выше. Документы, используемые на этапе обучения, - обучающие входные данные 122 и обучающие выходные данные 124 - могут быть документами того же типа, что и целевые документы (например, счета-фактуры, чеки, заказы на закупку и т. д.), которые следует использовать на этапе прогнозирования. Соответственно, несмотря на то, что словарь для векторных представлений слов SymSec(x,y) может разрабатываться на этапе обучения для конкретного класса целевых документов, векторные представления слов SymSec(x,y) не обязательно должны принадлежать словарю эмбеддингов, предварительно обученному на некотором более широком классе документов (например, книги, газеты, журналы), которые не связаны с конкретным классом целевых документов. Обученная первая подсистема 240 может быть способна предсказать, какая последовательность символов SymSeq следует (или предшествует, или примыкает в вертикальном или горизонтальном направлении) за конкретной последовательностью SymSeq. Прогнозы первой подсистемы 240 могут быть представлены в виде вероятностей. Например, обученная подсистема A 240 может быть способна предсказать, что слову «сумма» предшествует слово «общая» с вероятностью 30 %, а за ним следует слово «предложенная» с вероятностью 15 %.
[0056]
В некоторых вариантах осуществления выходные векторные представления в пространстве признаков vec(x,y) могут быть независимыми от конкретного местоположения (x,y) последовательности символов SymSeq. Более конкретно, координаты (x,y) последовательности символов SymSeq(x,y) могут служить геометрическим идентификатором последовательности, но ее векторное представление vec(x,y) может быть одинаковым независимо от того, где на изображении находится последовательность. Например, подсистема A 240 может назначать одинаковые вероятности того, что различные последовательности символов SymSeq (например, «город», «штат») находятся в непосредственной близости от слова «улица». В других вариантах осуществления векторные представления vec(x,y) одной и той же последовательности символов SymSeq могут отличаться в зависимости от местоположения последовательности в документе (или в пределах изображения документа 210). Например, выходные данные подсистемы A 240 - векторные представления слов, например, «условное депонирование», - могут варьироваться в зависимости от местоположения (x,y) слова внутри изображения документа 210. Соответственно, векторное представление фразы «условное депонирование» может быть ближе (в векторном пространстве) к представлениям одного множества слов, если «условное депонирование» встречается в середине документа, но ближе к представлениям другого множества слов, если «условное депонирование» находится в нижней части документа. Векторные представления конкретного слова могут также зависеть от типа документа. Например, слово «сумма» может быть по-разному представлено в договоре купли-продажи недвижимости и в заказе на покупку.
[0057]
M
M
M
В результате, если  последовательностей символов (символов, знаков пунктуации, слов, предложений) идентифицированы на изображении документа 210 и введены в подсистему A 240, выходные данные первой подсистемы могут представлять собой множество из  векторов (векторов в пространстве признаков) {vec(x,y)}. Каждый из  векторов vec(x,y) может зависеть от контекста всего документа - типа документа, количества слов в документе, разметки текста в документе, расположения некоторых или всех слов в документе и так далее.
[0058]
N
N
N
N
N
1
2
N
j
Векторное пространство для векторов vec(x,y) может иметь измерений, выбранных в зависимости от сложности документа. В некоторых вариантах осуществления  может быть равно 128 (32, 64 или любому другому числу). Число  может быть выбрано бóльшим для представления последовательности символов сложного документа и, наоборот, меньшим для более простых документов, имеющих ограниченный словарный запас слов. Для заданного числа измерений N каждый вектор может иметь  компонентов, vec(x,y) = (z, z, … z), где z может быть двоичным числом, десятичным числом или любым другим числом, доступным для компьютера. В некоторых вариантах осуществления некоторые из векторов vec(x,y), определенных подсистемой A 240, например, более короткие слова или знаки пунктуации, могут содержать меньше  чисел. В таких вариантах осуществления остальным компонентам вектора могут быть назначены нулевые значения, так что общая длина всех векторов может быть одинаковой.
[0059]
Фиг.
2
x
y
p
x
s
p
s
s
p
N
1
2
N
Выходные данные подсистемы A 240 могут быть схематически представлены в виде параллелепипеда (куба) 250, составленного из компонентов отдельных векторов в множестве {vec(x,y)}. В направлениях  и  горизонтальных плоскостей область изображения 210 документа может быть дискретизирована на  ячеек в направлении  и  ячеек в направлении y (например,  = 32 и  = 64 в одном примере варианта осуществления). Слово (символ, предложение) с центром в конкретной ячейке (x,y) может иметь свое векторное представление vec(x,y) = (z, z, … z), изображенное в виде последовательности блоков (ячеек), расположенных в третьем направлении, как схематически показано на  для углового вектора. Другие векторы могут быть аналогичным образом размещены в других ячейках параллелепипеда 250, называемого в данном документе «кубом», при этом следует помнить, что число ячеек в каждом из трех направлений может отличаться от количества ячеек в двух других направлениях, где  x  x  - общее количество ячеек в «кубе». Для формирования куба можно использовать функцию Map (например, Gather).
[0060]
j
Некоторые ячейки (или вертикальные грани) куба 250 могут быть пустыми (например, заполнены нулями). Например, ячейки, расположенные над координатами (x,y), которые соответствуют пустым пространствам изображения 210 документа, могут содержать все нули. Строка (в направлении x) или столбец (в направлении y) могут содержать все нули для всех своих векторов, если такая строка или столбец не содержит символов (например, попадает между строками текста). Даже в тех строках/столбцах, которые содержат символы, некоторые ячейки (или даже большинство ячеек) могут быть заполнены нулями. Например, если -я строка содержит десять слов, а горизонтальный размер изображения 210 документа дискретизирован на 32 ячейки, то в данной строке могут присутствовать только 10 ненулевых векторов vec(x,y), разделенных 22 нулевыми векторами. В некоторых вариантах осуществления векторы (x,y), которые не имеют по меньшей мере одного ненулевого компонента, могут быть исключены из куба.
[0061]
Фиг.
3
Фиг.
1C
s
p
N
M
1
2
2N
1
2
2N
Куб 250, имеющий  x  x  ячеек, содержащих множество {vec(x,y)} из  выявленных векторов, соответствующих выявленным последовательностям символов, может быть введен в подсистему B 260 для пересчета векторов {vec(x,y)} → {VEC (x,y)} с учетом общего контекста всего документа. Подсистема B 260 может содержать одну или более нейронных сетей (как поясняется ниже со ссылкой на ), которые могут модифицировать компоненты векторных представлений vec(x,y) последовательностей символов с учетом всех других векторов куба 250. В результате пересчитанные значения VEC(x,y)=(Z, Z, … Z) могут учитывать контекст всего документа. Более конкретно, пересчитанные значения VEC(x,y)=(Z, Z, … Z), выводимые подсистемой B 260, могут учитывать наличие всех других последовательностей символов в документе, а также содержимое каждого из таких символов последовательности. Дополнительно подсистема B 260 может выполнить выявление набора значений связанности {U(x,y; x’,y’)}, соответствующего ранее определенным соединениям, как показано на , между последовательностями символов SymSeq(x,y) и SymSeq(x’,y’). Первоначально все значения связанности могут быть установлены в нуль (или любое другое постоянное число, например, 0,5) и могут вычисляться совместно с пересчитанными значениями {VEC(x,y)}, так что набор выходных значений {U(x,y; x’,y’)} учитывает контекст всего документа.
[0062]
Фиг.
4A
C
Новый куб 270, содержащий множество пересчитанных векторов {VEC(x,y)}, может быть введен в подсистему C 280 для прогнозирования класса каждой последовательности символов, выявленной в изображении 210 документа. В некоторых вариантах осуществления механизм 111 обнаружения блоков может использовать модель (модели) 114 машинного обучения для формирования гипотез о последовательностях символов SymSeq 220 в документе (представляются набором векторов {VEC(x,y)}), принадлежащих различным блокам из последовательностей связанных символов во входном документе 210, как описано более подробно ниже в отношении -. Классами последовательностей символов могут быть «имя поставщика», «тип товара», «количество товара», «номер заказа», «тип поставки», «адрес доставки», «дата заказа», «тип оплаты» и др. В некоторых вариантах осуществления различные классы, предположительно имеющиеся во входном документе 210, могут быть предварительно заданы для по меньшей мере некоторых типов документов и введены в третью подсистему 280 в виде множества внешних параметров. В других вариантах осуществления различные классы, которые могут присутствовать в документе, могут быть определены третьей подсистемой 280, которая может быть обучена определять тип исходного документа 210 (например, «счет-фактура», «заказ», «счет» и т. д .) и предсказывать классы последовательностей символов, которые могут присутствовать в определенном типе исходного документа.
[0063]
Фиг.
2
Некоторые из компонентов, показанных на , могут быть объединены. Например, в одном из вариантов осуществления подсистемы A, B и C могут быть реализованы в виде одной нейронной сети. В некоторых вариантах осуществления подсистемы A и B могут быть реализованы как одна сеть, в то время как подсистема C может быть реализована как отдельная сеть. В некоторых вариантах осуществления подсистемы B и C могут быть реализованы как одна сеть, в то время как подсистема A может быть реализована как отдельная сеть. В тех вариантах осуществления, где множество подсистем реализуются объединенной единой сетью, функции разных подсистем объединенной сети могут быть реализованы отдельными выделенными уровнями или совместно используемыми уровнями или их комбинацией.
[0064]
Фиг.
3
На  представлена принципиальная схема, иллюстрирующая пример подсистемы 300 нейронной сети, которая определяет значения связанности и пересчитывает значения векторных представлений для различных последовательностей символов исходного документа на основе общего контекста документа в соответствии с некоторыми вариантами осуществления настоящего изобретения. В одном из вариантов осуществления подсистема 300 нейронной сети может быть подсистемой B 260. Подсистема 300 нейронной сети может быть реализована механизмом 111 распознавания блоков.
[0065]
Фиг.
1C
Куб 250, содержащий набор {vec(x,y)} векторов, соответствующих выявленным последовательностям символов SymSeq, может быть введен в подсистему 300. Дополнительно входные данные подсистемы 300 могут содержать промежуточные последовательности символов, выявленные ранее, как показано на . Некоторые последовательности символов SymSeq(x,y) могут иметь соединения с одной или более последовательностями символов SymSeq(x’,y’). Некоторые последовательности символов могут не иметь соединений. Первоначально в набор значений связанности {U(x,y; x’,y’)}, соответствующий выявленным соединениям между последовательностями символов SymSeq(x,y) и SymSeq(x’,y’), могут быть введены некоторые фиксированные значения (например, 0 или 0,5), которые одинаковы для всех соединений. Подсистема 300 может содержать одну или более нейронных сетей; каждая из сетей содержит множество слоев нейронов. В некоторых вариантах осуществления подсистема 300 может включать в себя две нейронные сети, сеть 310 горизонтального прохода и сеть 320 вертикального прохода. В некоторых вариантах осуществления сеть 310 горизонтального прохода и сеть 320 вертикального прохода могут быть сетями с долгой краткосрочной памятью (LSTM). В других вариантах осуществления сеть 310 горизонтального прохода и сеть 320 вертикального прохода могут быть сетями RNN либо сетями LSTM на основе механизма внимания.
[0066]
х
у
s
p
1
2
N
1
2
N
1
2
N
Сеть 310 горизонтального прохода и сеть 320 вертикального прохода могут выполнять множество проходов в горизонтальном () и вертикальном () измерениях куба 250. Более конкретно, сеть 310 горизонтального прохода может выбирать в последовательных итерациях каждый из  столбцов основания (нижняя плоскость ячеек), а сеть 320 вертикального прохода может аналогично выбирать каждую из  строк основания. Нулевые векторы (те, которые содержат все нули) могут игнорироваться, например, могут быть пропущены. Сеть 310 горизонтального прохода и сеть 320 вертикального прохода могут пересчитывать векторные компоненты, vec(x,y)=(z, z, … z) → VEC(x,y)=(Z, Z, … Z) для некоторых или всех векторов {vec(x,y)}, так что значения VEC(x,y)=(Z, Z, … Z) пересчитываются на основе значений всех векторов {vec(x,y)} документа, и, следовательно, новые значения {VEC(x,y)} могут зависеть от контекста (типа, содержимого) всего документа.
[0067]
j
j
s
j
j
k
j
j
j
1
j
k
1
j
k
N
j
k
1
j
k
1
j
k
N
j
k
1
j-1
k
1
j-1
k
N
j-1
k
1
j
k
1
j
k
N
j
k
1
j+1
k
1
j+1
k
N
j+1
k
В одном примере варианта осуществления пересчет векторов может быть выполнен следующим образом. Сеть 310 горизонтального прохода может итеративно выбирать последовательные значения столбцов , так что 1 ≤  ≤ . Для каждого сеть 310 горизонтального прохода может определять плоскость векторных компонентов z (x,y), z (x,y), … z (x,y), расположенных в ячейке куба 250, имеющих один и тот же индекс столбца , но разные возможные индексы строк . Сеть 310 горизонтального прохода может затем использовать параметры (например, весовые коэффициенты и смещения) сети 310 для изменения значений векторных компонентов z (x,y), z (x,y), … z (x,y) на основе значений в предыдущей плоскости, z (x,y), z (x,y), … z (x,y) или фиксированного числа (два, три, десять или любое другое число) предыдущих плоскостей. В некоторых вариантах осуществления значения для плоскости столбца  могут быть пересчитаны на основе всех предыдущих плоскостей, имеющих индексы от 1 до -1. После пересчета значений компонентов вектора z (x,y), z (x,y), … z (x,y) для плоскости столбца  сеть 310 горизонтального прохода может приступить к пересчету значений компонентов вектора для следующей плоскости, z (x,y), z (x,y), … z (x,y) и т. д., пока все столбцы куба 250 не будут пересчитаны.
[0068]
j
s
j
j
Сеть 310 горизонтального прохода может выполнять несколько горизонтальных проходов, как описано выше. В некоторых вариантах осуществления некоторые из проходов могут выполняться в обратном направлении, например, начиная с = и продолжая в направлении меньших значений , пока столбец =1 не будет достигнут и пересчитан.
[0069]
p
k,
k
p
k
k
j
k
k
k
1
j
k
1
j
k
N
j
k
1
j
k
1
j
k
N
j
k
1
j
k-1
1
j
k-1
N
j
k-1
1
j
k
1
j
k
N
j
k
1
j
k+1
1
j
k+1
N
j
k+1
Сеть 320 вертикального прохода может также выбирать в последовательных итерациях каждую из  строк базовой плоскости ячеек куба 250 и аналогичным образом пересчитывать векторные компоненты на основе значений всех векторов {vec(x,y)} документа. Например, сеть 320 вертикального прохода может итеративно выбирать последовательные значения строк  так что 1 ≤  ≤ . Для каждого  сеть 320 вертикального прохода может определять плоскость векторных компонентов z (x,y), z (x,y), ≤ z (x,y), расположенных в ячейке куба 250, имеющих один и тот же индекс строки , но различные возможные индексы столбцов . Сеть 320 вертикального прохода может затем использовать параметры (например, весовые коэффициенты и смещения) сети 320 для изменения значений компонентов вектора z (x,y), z (x,y), … z (x,y) на основе значений в предыдущей плоскости, z (x,y), z (x,y), … z (x,y) или фиксированного числа (два, три, десять или любое другое число) предыдущих плоскостей. В некоторых вариантах осуществления значения для плоскости строк  могут быть пересчитаны на основе всех предыдущих плоскостей строк, имеющих индексы от 1 до -1. После пересчета значений компонентов вектора z (x,y), z (x,y), … z (x,y) для плоскости строк  сеть 310 горизонтального прохода может приступить к пересчету значений компонентов вектора для следующей плоскости, z (x,y), z (x,y), … z (x,y) и т. д., до тех пор пока все строки куба 250 не будут пересчитаны.
[0070]
Когда сеть 310 горизонтального прохода и сеть 320 вертикального прохода выполняют многочисленные проходы вперед и назад, как описано выше, для определения пересчитанных значений {VEC(x,y)}, аналогично могут быть пересчитаны значения связанности {U(x,y; x’,y’)}. После каждого прохода вперед и (или) назад могут быть скорректированы значения связанности {U(x,y; x’,y’)}. В результате для некоторых соединений значения связанности могут уменьшиться относительно начальных значений, а для других соединений значения связанности могут увеличиться. Более высокое (низкое) значение U(x,y; x’,y’) может указывать более (или менее) вероятную связь между последовательностями символов SymSeq(x,y) и SymSeq(x’,y’).
[0071]
Параметры сети 310 горизонтального прохода могут отличаться от параметров сети 320 вертикального прохода. Параметры этих двух сетей могут быть определены на этапе обучения путем выбора одного или более наборов обучающих входных данных 122, определения выходных данных объединенной сети (подсистемы 300), сравнения выходных данных с результатами обучения 124 и обратного распространения ошибок через уровни сетей по сети 310 горизонтального прохода и сети 320 вертикального прохода.
[0072]
На этапе обучения сеть 310 горизонтального прохода и сеть 320 вертикального прохода могут выполнять множество проходов, пока ошибка выходных данных подсистемы 300 не станет ниже некоторой предварительно заданной ошибки. Проходы по сети 310 горизонтального прохода и по сети 320 вертикального прохода могут выполняться в различном порядке. Например, в одной реализации первый проход может быть прямым проходом по сети 310 горизонтального прохода, второй путь может быть обратным путем по сети 310 горизонтального прохода, третий проход может быть прямым путем по сети 320 вертикального прохода, четвертый проход может быть обратным путем по сети 320 вертикального прохода и т. д. Этот процесс может повторяться несколько раз. Альтернативно, в другом варианте осуществления первый проход может быть прямым проходом по сети 310 горизонтального прохода, второй путь может быть прямым путем по сети 320 вертикального прохода, третий проход может быть обратным путем по сети 310 горизонтального прохода, четвертый проход может быть обратным путем по сети 320 вертикального прохода и т. д. В другом варианте реализации каждая из двух сетей может выполнять несколько (например, два, три или более) проходов в одном и том же направлении (вперед или назад), прежде чем одна и та же сеть сможет выполнить несколько проходов в противоположном направлении или перед тем, как другие сети выполнят несколько проходов (в любом направлении). Специалист в данной области техники поймет, что возможно реализовать практически неограниченное количество различных комбинаций двух сетей, выполняющих проходы в двух направлениях.
[0073]
Результатом этапа обучения может быть набор параметров (например, смещения и весовые коэффициенты) для сети 310 горизонтального прохода и множество параметров для сети 320 вертикального прохода. Эти два набора могут быть различными. Кроме того, каждая из двух сетей может содержать множество параметров, которые отличаются для прямых и обратных проходов. Кроме того, несмотря на то, что в некоторых вариантах осуществления параметры (например, для обратных проходов сети 310 горизонтального прохода) могут быть независимыми от того, где находится пересчитанная плоскость столбца, в других вариантах реализации осуществления могут зависеть от таких местоположений. Например, параметры могут отличаться для плоскостей столбцов (плоскостей строк), расположенных вблизи краев документа, от плоскостей, расположенных вблизи середины документа.
[0074]
Фиг.
3
Фиг.
3.
1
2
N
N+1
2N
N
N
Выходные данные сети 310 горизонтального прохода и сети 320 вертикального прохода могут быть объединены для получения пересчитанного куба 270. (Операция объединения обозначена на  белым крестом.) Связанные векторы могут иметь пересчитанные значения VEC(x,y)=(Z, Z, … Z, Z, … Z), содержащие первые  компонентов, которые представляют выходные данные сети 310 горизонтального прохода, и последние  компонентов, которые представляют выходные данные сети 320 вертикального прохода (или наоборот). Например, в одном примере варианта осуществления, если входные векторы vec(x,y), которые формируют (исходный) куб 250, содержат 128 компонентов, то пересчитанные векторы VEC(x,y), которые формируют (выходной) куб 270, могут содержать 256 компонентов. Компоненты пересчитанного куба 270, которые имеют выявленные связи, обозначены связывающими многоточиями на  Каждое соединение может иметь собственное значение связанности U(x,y; x’,y’).
[0075]
В одном из вариантов осуществления на этапе прогнозирования подсистема 300 может работать в том же порядке комбинаций, что и на этапе обучения. В других вариантах осуществления количество проходов на этапе прогнозирования может быть меньше (или больше), чем на этапе обучения. Например, если количество анализируемых документов является значительным, число проходов (на один документ) на этапе прогнозирования может быть значительно уменьшено по сравнению с этапом обучения.
[0076]
1
2
N
N+1
2N
1
2
N
N+1
2N
k
N+k
k.
1
2
N
N+1
2N
1
2
N
N+1
2N
1
2
N
N
2N
N
N
N
N
2N
N
2N
N
В ходе этапа прогнозирования после завершения предопределенного числа проходов (количество проходов может быть предварительно определено в ходе этапа обучения как число, достаточное для достижения необходимой точности) подсистема 300 может вывести куб 270, имеющий пересчитанные значения векторных компонентов VEC(x,y)=(Z, Z, … Z, Z, … Z). Функция 330 Unmap (например, Scatter) может отменить отображение пересчитанного куба 270 на множество пересчитанных несопоставленных векторов 340, имеющих исходную длину ( компонентов). К примеру, в некоторых вариантах осуществления функция 330 Unmap может объединять два компонента вектора (Z, Z, … Z, Z, … Z), например, согласно Z+ Z → Z, или согласно некоторой другой схеме установления соответствия, которая уменьшает количество компонентов вектора от  до . В других вариантах осуществления функция 330 Unmap может сначала исключить нулевые компоненты вектора (Z, Z, … Z, Z, … Z) и выбрать  первых ( последних,  наибольших и т. д.) из оставшихся компонентов. В другом варианте осуществления слой плотной нейронной сети, имеющий  входов и  выходов, может сокращать вектор VEC(x,y)=(Z, Z, … Z, Z, … Z) до упрощенного вектора VEC(x,y)=(Z, Z, … Z). Упрощенные (несопоставленные) векторы 340 могут содержать координаты соответствующих последовательностей символов SymSeq. В некоторых вариантах осуществления уменьшение длины каждого из векторов с  до  может включать только один данный вектор; а именно, определение компонентов упрощенного вектора, определенного по координатам (x,y), может не включать компоненты других векторов (например, определенных по другим координатам). Поскольку несопоставленные векторы 340, выводимые подсистемой 300, пересчитываются на основе значений всех векторов документа, несопоставленные векторы 340 зависят от контекста всего документа. В дополнение к несопоставленным векторам выходные данные подсистемы 300 могут содержать набор значений связанности {U(x,y; x’,y’)} 350 между выявленными соединениями.
[0077]
Фиг.
4A
Фиг.
4A
1
2
N
На  представлена принципиальная схема, иллюстрирующая операции 400 примера подсистемы 410 нейронной сети, которая прогнозирует классы последовательностей символов и определяет связи блоков в соответствии с некоторыми вариантами осуществления настоящего изобретения. Подсистема 410 нейронной сети, показанная на , в одном из вариантов осуществления может быть подсистемой C 280. Подсистема 410 нейронной сети может быть реализована механизмом 111 распознавания блоков. Подсистема 410 нейронной сети может использовать в качестве входных данных выходной сигнал подсистемы B (например, подсистемы 300). Более конкретно, подсистема C 410 нейронной сети может получать на входе пересчитанные значения 340 векторных компонентов VEC(x,y)=(Z, Z, … Z), соответствующих выявленным последовательностям символов SymSeq(x,y). Подсистема C 410 нейронной сети может также получать на входе рассчитанные значения связанности U(x,y; x’,y’) 350, соответствующие потенциальным связям между последовательностями символов SymSeq(x,y) и SymSeq(x’,y’). Подсистема C 410 может иметь один или более полносвязных/плотных нейронных слоев, например, слои 412, 414, 416. Некоторые из полносвязных слоев могут использовать функцию softmax. В некоторых вариантах осуществления один или более полносвязных слоев 412, 414 и (или) 416 могут быть соединены друг с другом слоями, которые не являются полносвязными.
[0078]
В некоторых вариантах осуществления подсистема C 410 может классифицировать каждую из последовательностей символов SymSec(x,y) в качестве одного из множества классов, которые могут быть определены заранее. Каждый из предопределенных классов может соответствовать одному из типов последовательностей символов (слов), которые необходимо обнаружить (это могут быть, например, типы, которые интересуют клиента). В некоторых вариантах осуществления подсистема 410 может использовать дополнительный вход 420, который может содержать списки предопределенных классов для различных типов документов. Например, в некоторых вариантах осуществления вход 420 может содержать информацию о том, что документ счет-фактуры может включать в себя такие классы, как «продавец», «покупатель», «адрес продавца», «адрес покупателя», «тип товара», «количество товара», «способ оплаты», «сумма депозита», «дата доставки», «дата доставки», «подпись» и т. д. В некоторых вариантах осуществления классификация классов может основываться на семантических значениях слов и групп слов, имеющих одинаковое значение в одном классе. В некоторых вариантах осуществления, где одно и то же слово может иметь несколько значений, при классификации может также учитываться, используется ли слово как глагол или как существительное, и контекст, в котором используется это слово (например, другие слова, используемые в той же строке, параграфе и документе). В некоторых вариантах осуществления классы могут быть основаны на предметной области, к которой они относятся. Например, слова могут быть сгруппированы в классы «финансовый», «географический», «относящийся к продукту» и др. В некоторых вариантах осуществления вход 420 может быть предусмотрен как часть обучающего входа (входов) 122 и обучающего выхода (выходов) 124, а подсистема 410 может определять количество и классы слов, встречающихся в документах различных типов, как часть процесса (этапа) обучения.
[0079]
Фиг.
4A
Для классификации последовательностей символов подсистема C 410 может строить гипотезы о том, что некоторые или каждая из выявленных последовательностей символов, описанных соответствующими векторами 340, принадлежат одному из классов. Далее подсистема C 410 может определить вероятности того, что конкретные последовательности символов принадлежат различным классам. Выход 430 прогнозирования класса слова подсистемы C 410 может содержать связь каждой из последовательностей символов SymSeq(x,y) с различными классами K1, K2, K3, K4 и т. д. Например, как указано на , связи могут оцениваться посредством назначения последовательностям SymSeq(x,y) различных вероятностей принадлежности к соответствующим классам. Например, подсистема C 410 может определить, что конкретная последовательность SymSeq(x,y) может принадлежать классу K3 с вероятностью 60 %, классу K1 с вероятностью 20 %, классу K6 с вероятностью 15 % и классу K2 с вероятностью 5 %.
[0080]
Для определения прогноза 430 класса слова для различных последовательностей символов документа подсистема C 410 может сначала построить множество гипотез, определяющих различные SymSeq(x,y) как принадлежащие различным классам Kn. Например, гипотеза может состоять в том, что множество из нескольких слов, расположенных рядом друг с другом (например, в одной и той же строке), может принадлежать одному и тому же блоку (например, адресу поставщика). Другая гипотеза может заключаться в том, что одни и те же слова могут принадлежать адресу покупателя. Гипотеза для слова может быть построена на основе одной или более характеристик слова (или предложения), которые известны достоверно, таких как местоположение слова, количество символов в слове и т. д. Генератор гипотез, реализованный подсистемой C 410 и (или) механизмом 111 распознавания блоков, может строить множественные гипотезы для каждого SymSeq(x,y) на основании известных признаков данной последовательности.
[0081]
Затем множество сгенерированных гипотез может быть введено в одну или более нейронных сетей подсистемы C 410 для оценки/проверки сгенерированных гипотез и для присвоения значений вероятности каждой сгенерированной гипотезе. Для проверки гипотез может использоваться функция тестирования. Функция тестирования может быть определена на основе оценки обучающих входных данных 122, сравнения фактических выходных данных подсистемы C 410 с результатами 124 обучения и коррекции параметров функции тестирования таким образом, чтобы минимизировать разницу между фактическими выходными данными подсистемы 410 и результатами 124 обучения. Обучение функции тестирования может выполняться с использованием методов повышения градиента, методов дерева решений или аналогичных методов.
[0082]
После выбора наиболее вероятной гипотезы последовательность символов SymSeq(x,y) может быть классифицирована по классам Kn в соответствии с гипотезой, которая определена как имеющая наивысшую вероятность.
[0083]
Фиг.
3
В дополнение к выводу прогнозов 430 по классам слов подсистема C 410 может выводить прогнозы 440 для связей блоков. Для определения наиболее вероятных связей между различными словами в документе подсистема C 410 может формировать гипотезы о том, что некоторые слова принадлежат к блокам связанных слов. Предположения могут быть основаны на значениях связанности U(x,y; x’,y’) 350 между ранее выявленными соединениями, как показано на .
[0084]
Фиг.
4B
Фиг.
4B
На  представлен пример 450 гипотезы уровня блока, используемой для предсказания блоков связанных последовательностей символов в целевом документе, в соответствии с некоторыми вариантами осуществления настоящего изобретения. Показаны гипотезы уровня блока, представляющие различные потенциальные связи различных последовательностей символов в целевом документе 145. Также показаны значения связанности U(x,y; x’,y’) 350, поскольку они могут формироваться подсистемой B 260. В одном из вариантов осуществления значения связанности 350 могут показывать вероятность того, что последовательности символов, указанные координатами (x,y) и (x’,y’), принадлежат к одному блоку связанных последовательностей символов, причем большее значение U показывает более высокую вероятность. Например, значение связанности U=0,9 между именем 160 покупателя и IBAN 180 покупателя может показывать высокую вероятность того, что имя покупателя и IBAN покупателя принадлежат к одному блоку связанных слов. Аналогично, значение связанности U=0,3 между именем 150 продавца и именем 160 покупателя может показывать значительно меньшую вероятность связи имени продавца с именем покупателя. Тот факт, что в этом примере отношение двух значений связанности равно трем, не обязательно показывает, что наличие связи с U=0,9 в три раза более вероятно, чем связи с U=0,3. В некоторых вариантах осуществления вероятность связи может быть нелинейной функцией от U. В примере, показанном на , значения связанности изменяются между 0 и 1. В других вариантах осуществления значения связанности могут изменяться между 0 и 100 либо между любыми другими пределами.
[0085]
Основываясь на значениях связанности, характеризующих потенциальные связи между различными словами в документе, подсистема C 410 может формировать несколько гипотез уровня блока, где каждая гипотеза уровня блока представляет потенциальный блок связанных слов. Далее подсистема C 410 может вычислить для каждой потенциальной связи блока значение уровня блока, представляющее вероятность того, что этот потенциальный блок соответствует действительной связи между словами. Значение уровня блока может быть определено с помощью значений связанности для различных соединений между словами в потенциальном блоке. К примеру, подсистема C 410 может сформировать первую гипотезу о том, что имя 160 покупателя, почтовый код 166 покупателя, IBAN 180 покупателя и BIC/SWIFT 182 покупателя составляют первый потенциальный блок, и присвоить этому блоку значение уровня блока W=0,9+0,7+0,8=2,4. Затем подсистема C 410 может сформировать вторую гипотезу о том, что имя 160 покупателя, имя 150 продавца, промежуточная сумма A 196 и IBAN 170 продавца составляют второй потенциальный блок, и присвоить этому блоку значение уровня блока W=0,2+0,3+0,4=0,9. Более высокое значение уровня блока для первой гипотезы уровня блока может указывать более высокую вероятность того, что первый потенциальный блок является действительно блоком связанных слов, по сравнению с вероятностью для второго потенциального блока. В некоторых вариантах осуществления подсистема C 410 может генерировать тысячи или десятки тысяч (и более) гипотез уровня блока, при этом каждое слово может включаться в множество гипотез.
[0086]
Фиг.
4C
На  представлен пример 460 гипотез уровня документа, используемых для предсказания блоков связанных последовательностей символов в целевом документе в соответствии с некоторыми вариантами осуществления настоящего изобретения. Показаны гипотезы уровня документа, показывающие различные потенциальные блоки связанных последовательностей символов в целевом документе 145. Также показаны значения W уровня блока, которые могут формироваться подсистемой C 280, как описано выше. Например, потенциальный блок 1 (связи которого показаны сплошными линиями) может содержать адрес 152-158 продавца и имя 160 покупателя и может иметь значение уровня блока W=3,2, в то время как потенциальный блок 2 (пунктирные линии) может иметь значение уровня блока W=4,4, что показывает более высокую вероятность появления. Аналогично, другие гипотезы могут содержать потенциальные блоки 3 (точечно-пунктирные линии), 4 (пунктирные линии), 5 (сплошные линии) и так далее, причем каждый из них имеет свое значение уровня блока.
[0087]
В некоторых вариантах осуществления значения W уровня блока могут быть суммой значений связанности U для различных слов потенциального блока, указанного в гипотезе. В некоторых вариантах осуществления для отражения относительного правдоподобия (вероятности) появления потенциальных блоков, которые имеют неравное количество слов, значения W уровня блока могут масштабироваться по количеству слов. Например, значение W уровня блока для потенциального блока 2 может быть разделено на общее количество слов в нем (пять) W → 4,4/5=0,88, а значение W для потенциального блока 5 может быть масштабировано аналогично W → 3,0/3=1,0. Это может позволить лучше отразить тот факт, что потенциальный блок 2 имеет более высокую вероятность появления, несмотря на то, что имеет значение уровня блока без масштабирования (3,0) ниже, чем значение без масштабирования для блока 1 (4,4).
[0088]
В некоторых вариантах осуществления значения W уровня блока могут также учитывать классы слов, прогнозируемые на выходе 430 прогнозирования классов слов. Например, если все слова в потенциальном блоке определены как принадлежащие к одному классу, то соответствующее значение W уровня блока может быть увеличено на некоторую фиксированную величину, например, W → W+1,0. Если только некоторые слова принадлежат к одному классу, а некоторые слова принадлежат к различным классам, то величина добавки уменьшается (например, W → W+0,7) по сравнению с максимальным значением добавки на величину штрафа (в этом примере 0,3), в зависимости от количества слов, имеющих несоответствующие классы. (В других вариантах осуществления максимальное значение добавки может быть некоторым другим числом.) Более высокие значения добавки могут использоваться в тех случаях, когда соответствие классов важнее, чем связи слов. С другой стороны, более низкие значения добавки могут использоваться в тех случаях, когда связи слов более важны. Специалист в данной области поймет, что имеется практически неограниченное число возможностей назначения относительных весов для соответствия классов и связи слов. Такой специалист поймет также практически неограниченное число способов, которыми может использоваться значение связанности U для вычисления значений W уровня блока. В некоторых вариантах осуществления значения добавки и штрафы за несоответствие классов могут быть определены нейронной сетью, например, одним или более нейронными слоями подсистемы C 410, используя стандартные методы машинного обучения.
[0089]
После идентификации множества гипотез уровня блока подсистема C 410 может сформировать одну или более гипотез уровня документа путем установления согласованности между различными гипотезами уровня блока и вычисления вероятности того, что одна или более гипотез уровня блока могут быть соединены в одном документе. В некоторых вариантах осуществления могут рассматриваться только гипотезы, в которых нет слов, принадлежащих к более чем одной гипотезе уровня блока. Например, первая гипотеза уровня документа может содержать потенциальный блок 1 (первая гипотеза уровня блока) и потенциальный блок 5. Вторая гипотеза уровня документа может содержать потенциальный блок 2 и потенциальный блок 3. Третья гипотеза уровня блока может содержать потенциальный блок 2, потенциальный блок 3 и потенциальный блок 4. С другой стороны, гипотеза уровня документа, которая комбинирует потенциальный блок 2 и потенциальный блок 5, может быть запрещена, поскольку имя 150 продавца имеется в обеих гипотезах уровня блока.
[0090]
В других вариантах осуществления гипотезы уровня документа с совместно используемыми словами по-прежнему рассматриваются, но им может быть назначен штраф за перекрытие. В некоторых других вариантах осуществления, где допускается включение слова в несколько блоков, могут не назначаться штрафы за перекрытие. Например, клиент может быть заинтересован в разборе целевого документа на несколько логических блоков (например, «финансовая информация», «информация о поставке» и др.), в каждый из которых может входить имя покупателя.
[0091]
Z
Z
W
Z
Из набора сгенерированных гипотез уровня документа подсистема C 410 может определить, основываясь на значениях W уровня блока для потенциального блока, включенного в соответствующую гипотезу уровня документа, наиболее подходящую гипотезу уровня документа, которая прогнозирует, как различные слова в документе распределяются между блоками связанных слов. В некоторых вариантах осуществления может быть выбрана гипотеза уровня документа, имеющая наиболее высокое значение вероятности  уровня документа. Значение вероятности  может быть вычислено как сумма значений  уровня блока всех потенциальных блоков, включенных в соответствующую гипотезу. В некоторых вариантах осуществления значение вероятности  может быть вычислено как  с некоторой функцией, которая не обязательно должна быть линейной функцией, а может быть полиномиальной функцией, логарифмической функцией, экспоненциальной функцией или любой другой функцией. В некоторых вариантах осуществления значения вероятности Z могут быть единообразно масштабированы на интервал [0,1] или любой другой интервал.
[0092]
Z
В некоторых вариантах осуществления значение вероятности  может также учитывать количество слов, оставшихся за пределами любого из потенциальных блоков, и те гипотезы, которые объединяют в блоки больше слов (при, возможно, меньшей индивидуальной вероятности), имеют предпочтение перед теми гипотезами, которые объединяют больше слов (но с более высокой индивидуальной вероятностью). Это может быть достигнуто, к примеру, путем увеличения каждого значения Z на коэффициент, который зависит от количества связанных слов в соответствующей гипотезе (либо, наоборот, путем вычитания штрафов на основе количества несвязанных слов). Специалист в данной области поймет, что имеется практически неограниченное число возможностей проектирования таких коэффициентов увеличения (штрафов). В некоторых вариантах осуществления коэффициенты увеличения (штрафы) могут определяться нейронной сетью, например, одним или более слоями подсистемы C 410, используя стандартные методы машинного обучения.
[0093]
В одном из вариантов реализации после выявления в документе блоков связанных последовательностей символов информация о выявленных блоках может быть сохранена, например, в хранилище 120 или любом другом устройстве хранения, включая локальное или сетевое (например, облачное) устройство хранения. Блоки могут идентифицироваться по их абсолютному положению (например, по координатам) или по относительному положению (относительно других блоков или слов). Эта информация может повторно использоваться при вводе последующего документа того же или подобного типа для выявления блоков связанных последовательностей символов. В таких случаях после оптического распознавания следующего документа блоки могут быть заполнены символьными последовательностями SymSeq(x,y) из следующего документа, основываясь на координатах (x,y), если предварительно было определено, что эти координаты (x,y) относятся к этой или к связанным последовательностям символов этого блока. В таких случаях нейронные сети, возможно, не должны использоваться для обнаружения блоков в последующих документах. В некоторых вариантах осуществления для идентификации связанных последовательностей символов в том же блоке координаты последовательностей символов в различных документах не обязательно должны совпадать идеально, но хотя бы с некоторой предустановленной точностью. В других вариантах осуществления, где можно ожидать, что последующий документ (или форма) может иметь другую разметку или макет, блоки связанных слов (и их местоположения), определенные для исходного документа, могут использоваться в качестве гипотез во время выявления блоков последующего документа. Такие гипотезы могут быть проверены вместе с другими гипотезами, которые могут генерироваться нейронными сетями, как описано выше. Новая разметка блоков, обнаруженная в каждом дополнительном документе, может быть аналогичным образом добавлена в пул гипотез для обнаружения блоков в будущих документах.
[0094]
В некоторых вариантах осуществления расположение последовательности символов в блоке может быть определено на основе ее расположения относительно некоторых других последовательностей символов в том же блоке. Например, расположение слова «предложенная» может быть определено относительно местоположения другой последовательности символов, например, «общая сумма».
[0095]
Фиг.
5-8
Фиг.
9
Фиг.
1
Фиг.
5-8
На  показаны блок-схемы, иллюстрирующие примеры способов 500-800, в которых общий контекст документа используется для обнаружения блоков связанных последовательностей символов в электронных документах сложной структуры, в соответствии с некоторыми вариантами осуществления настоящего изобретения. Каждый из способов 500-800 может выполняться логикой обработки, которая может быть выполнена в виде аппаратных средств (электронные схемы, специализированная логика, программируемая логика, микрокоманды и т. д.), программного обеспечения (например, инструкции, выполняемые обрабатывающим устройством), встроенного программного обеспечения или комбинации всех таких средств. В одном из вариантов осуществления способы 500-800 могут выполняться устройством обработки данных (например, устройством обработки данных 902 на ) вычислительного устройства 110 и (или) сервера 150, как показано применительно к . В некоторых вариантах осуществления способы 500-800 могут выполняться в одном потоке обработки. Альтернативно, способы 500-800 могут выполняться в двух или более потоках обработки, при этом в каждом потоке будут выполняться одна или более отдельных функций, процедур, подпрограмм или операций способа. В иллюстративном примере потоки обработки, реализующие способы 500-800, могут быть синхронизированы (например, с использованием семафоров, критических секций и (или) других механизмов синхронизации потоков). Альтернативно, потоки обработки, реализующие способы 500-800, могут выполняться асинхронно друг относительно друга. Поэтому, хотя  и соответствующие описания перечисляют операции способов 500-800 в определенном порядке, в различных вариантах осуществления способов по крайней мере некоторые из перечисленных операций могут выполняться параллельно и (или) в произвольно выбранном порядке.
[0096]
Фиг.
5
На  представлена блок-схема, иллюстрирующая пример способа 500 обнаружения блоков связанных последовательностей символов в электронном документе сложной структуры, в соответствии с некоторыми вариантами осуществления настоящего изобретения. В операции 510 устройство обработки, выполняющее способ 500, может получить множество последовательностей символов документа. Такие последовательности символов могут содержать цифры (например, суммы в долларах), текст (буквы, слова, предложения, абзацы), особые символы, изображения (логотипы), элементы таблиц (линии, ячейки) или любые другие символы, которые могут быть определены в документе (например, с помощью оптического распознавания символов в его изображении). Некоторые из последовательностей символов документа могут быть связаны с одним или более блоков. Например, первый блок связанных последовательностей символов может иметь две или более последовательностей символов, которые связаны между собой функционально или семантически. Аналогично, второй блок может содержать две или более последовательностей символов, которые не входят в первый блок. В операции 520 устройство обработки может определить множество векторов, так что вектор из этого множества векторов представляет одну из множества последовательностей символов.
[0097]
В операции 530 способ 500 может продолжиться с пересчетом некоторых или всех векторов устройством обработки. Некоторые или все пересчитанные векторы могут быть основаны на значениях некоторых или всех из множества векторов. В операции 540 устройство обработки может обрабатывать множество идентифицированных последовательностей символов в документе, используя первую нейронную сеть (например, подсистему В 260). На основе ввода последовательности символов первая нейронная сеть может определить множество значений связанности, причем каждое из множества значений связанности соответствует одному из множества соединений между по меньшей мере двумя последовательностями символов из множества последовательностей символов (операция 540).
[0098]
Фиг.
5
Способ 500 может продолжаться, возможно (как показано пунктирной рамкой на ), с определения (операция 550) устройством обработки класса для каждого из подмножеств последовательностей символов в документе. В некоторых вариантах осуществления подмножество может содержать большинство (или даже все) из последовательностей символов в документе. В других вариантах осуществления подмножество последовательностей символов (для которого определяются классы) может содержать только некоторые из последовательностей символов документа. Способ 560 может продолжаться операцией 560, определением первого блока связанных последовательностей символов с помощью множества пересчитанных векторов и множества значений связанности. В некоторых вариантах осуществления определение первого блока связанных последовательностей символов может дополнительно основываться на классе каждого из подмножеств последовательностей символов, как определяется в ходе операции 550. В операции 570 способ 500 может (возможно) продолжить определение, с помощью устройства обработки, второго (третьего и т. д.) блока связанных последовательностей символов из множества последовательностей символов в документе.
[0099]
В некоторых вариантах осуществления устройство обработки, выполняющее способ 500, может также определить расположение последовательностей символов первого (второго и т. д.) блока из связанных последовательностей символов и сохранить полученные места расположения в хранилище данных. Сохраненные места расположения могут использоваться для обработки последующих документов. Например, после получения последующего документа и обнаружения некоторой последовательности символов в последующем документе устройство обработки может определить, что эта последовательность символов последующего документа имеет такое местоположение в последующем документе, которое совпадает, в пределах заданной точности, с одним из местоположений последовательности символов первого блока из связанных последовательностей символов. Заданная точность может быть выражена конкретным расстоянием (например, 0,5 см, 1 см и т. п.), либо в виде расстояния, измеренного в ширине строки или в интервалах между строками (например, одна строка, две строки и т. п.). На основе обнаруженных мест расположения устройство обработки может ассоциировать последовательности символов последующего документа с первым блоком связанных последовательностей символов.
[00100]
Фиг.
6
На  представлена блок-схема последовательности операций, иллюстрирующая один пример способа 600, который использует нейронные сети для определения векторных представлений (например, векторных представлений слова) для последовательностей символов, определенных на изображении документа, в соответствии с некоторыми вариантами осуществления настоящего изобретения. В операции 610 устройство обработки (например, компьютер), реализующее способ 600, может выполнять оптическое распознавание символов изображения документа, чтобы получить распознанный текст документа.
[00101]
В операции 620 устройство обработки, реализующее способ 600, может разделить распознанный текст на множество последовательностей символов SymSeq(x,y) документа. Последовательности символов могут быть буквенно-цифровыми, графическими или комбинированными. Буквенно-цифровые последовательности могут представлять собой текст (слоги, слова, предложения), цифры, символические знаки и т. д. Графические последовательности могут представлять собой элементы графической таблицы, такие как горизонтальная линия, вертикальная линия, наклонная линия, угол (двухстороннее пересечение линий, которое может указывать на угловой раздел таблицы), трехстороннее пересечение линий (которое может указывать на краевой раздел таблицы) или четырехстороннее пересечение линий (которое может указывать на внутренний раздел таблицы). Комбинированная последовательность может представлять собой комбинацию одного или более буквенно-цифровых символов и одного или более графических элементов таблицы. Последовательность может состоять из множества символов, но в некоторых случаях может быть одним символом.
[00102]
Фиг.
2
Фиг.
2
1
2
N
На шаге 630 устройство обработки, реализующее способ 600, может вводить множество последовательностей символов в нейронную сеть A. Нейронная сеть A может быть подсистемой (подсетью) A 240, описанной со ссылкой на . Целью нейронной сети A может быть определение множества векторов, представляющих последовательности символов, определенные на шаге 620. В частности, на шаге 640 нейронная сеть A может определять векторное представление слова для каждого слова из множества последовательностей символов. Векторные представления слов могут быть векторами vec(x,y)=(Z, Z, … Z), соответствующими идентифицированным последовательностям символов SymSeq(x,y), как описано выше со ссылкой на . Нейронная сеть A может быть предварительно обучена на исходных документах, которые могут быть такого же типа, что и целевой документ.
[00103]
Фиг.
2
1
2
N
Определенные векторы (например, векторное представление слов) vec(x,y)=(Z, Z, … Z) могут быть введены в нейронную сеть B (650). Нейронная сеть B может быть подсистемой B (260), описанной со ссылкой на . Предназначением нейронной сети B может быть пересчет векторов {vec(x,y)} → {VEC(x,y)} с учетом общего контекста всего документа и определение значений связанности, как описано выше.
[00104]
Фиг.
7
На  представлена блок-схема, иллюстрирующая другой пример способа 700, в котором используются нейронные сети для определения связей между последовательностями символов, используя общий контекст документа в соответствии с некоторыми вариантами осуществления настоящего изобретения. В операции 710 устройство обработки, выполняющее способ 700, может получить множество последовательностей символов документа. В одном из вариантов осуществления операция 710 может быть аналогична операциям 610 и 620 из способа 600. В операции 720 устройство обработки данных может определить множество векторов vec(x,y), представляющих последовательности символов.
[00105]
Фиг.
3
В операции 730 способ 700 может продолжать обработку множества векторов {vec(x,y)}, используя нейронную сеть B (подсистема 260). Выходом нейронной сети B может быть множество векторов, {vec(x,y)} → {VEC(x,y)}, пересчитанных на основе значений всех или некоторых векторов из множества векторов (блок 740). Для получения множества пересчитанных векторов устройство обработки данных, выполняющее способ 700, может использовать первую подсеть (например, сеть 310) из множества подсетей для перерасчета множества векторов в направлении увеличения или уменьшения горизонтальных координат векторов. Устройство обработки данных, выполняющее способ 700, может также использовать вторую подсеть (например, сеть 320) из множества подсетей для перерасчета множества векторов в направлении увеличения или уменьшения вертикальных координат векторов, как описано в связи с . Выходные данные сетей 310 и 320 могут быть объединены, и множество пересчитанных векторов {VEC(x,y)} может быть определено по объединенным результатам, как описано выше.
[00106]
Фиг.
8
На  представлена блок-схема, иллюстрирующая способ 800, в котором используются нейронные сети для создания и проверки множества гипотез о блочных связях последовательностей символов документа, в соответствии с некоторыми вариантами осуществления настоящего изобретения. Операционный блок 810 способа 800 может принимать множество пересчитанных векторов {VEC(x,y)} из нейронной сети B. В блоке 820 устройство обработки данных, исполняющее способ 800, может также принимать класс для каждого из подмножеств последовательностей символов. В некоторых вариантах осуществления как пересчитанные векторы, так и классы последовательностей символов могут быть выходом той же нейронной сети B.
[00107]
В операции 830 устройство обработки данных, выполняющее способ 800, может генерировать, например, с помощью нейронной сети C, множество гипотез уровня блока, причем каждая из множества гипотез уровня блока может содержать потенциальные связи некоторого подмножества из множества пересчитанных векторов. Каждая гипотеза может дополнительно содержать некоторое значение уровня блока, представляющее вероятность появления данной потенциальной связи. Значение уровня блока может быть определено с помощью одного или более значений связанности, соответствующих соединениям между последовательностями символов, представленными подмножествами пересчитанных векторов, а также классами последовательностей символов, полученными в операции 820.
[00108]
В операции 840 способ 800 может продолжить выполнение генерацией множества гипотез уровня документа, причем каждая из гипотез уровня документа может содержать первую гипотезу уровня блока и вторую гипотезу уровня блока. Первая гипотеза уровня блока может содержать первую потенциальную связь первого подмножества из множества пересчитанных векторов. Точно так же вторая гипотеза уровня блока может содержать вторую потенциальную связь второго подмножества из множества пересчитанных векторов.
[00109]
В операции 850 устройство обработки данных, выполняющее способ 800, может определить для каждого множества гипотез уровня документа значение вероятности уровня документа, основываясь на значении уровня блока для первой гипотезы уровня блока и значении уровня блока для второй гипотезы уровня блока. Устройство обработки данных может выбрать (операция 860) наиболее вероятную гипотезу уровня документа из множества гипотез уровня документа, основываясь на значениях вероятности уровня документа для каждой из множества гипотез уровня документа.
[00110]
Фиг.
9
На  приведен пример вычислительной системы 900, которая может выполнять один или более способов, описанных в настоящем изобретении. Данная вычислительная система может быть подключена (например, по сети) к другим вычислительным системам в локальной сети, внутренней сети, внешней сети или сети Интернет. Данная вычислительная система может выступать в качестве сервера в сетевой среде клиент-сервер. Данная вычислительная система может представлять собой персональный компьютер (ПК), планшетный компьютер, телевизионную приставку (STB), карманный персональный компьютер (PDA), мобильный телефон, фотоаппарат, видеокамеру или любое устройство, способное выполнять набор команд (последовательно или иным способом), который определяет действия этого устройства. Кроме того, несмотря на то, что показана система только с одним компьютером, термин «компьютер» также включает любой набор компьютеров, которые по отдельности или совместно выполняют набор команд (или несколько наборов команд) для реализации любого из описанных в настоящем изобретении способов или нескольких таких способов.
[00111]
Пример вычислительной системы 900 содержит устройство обработки 902, основную память 904 (например, постоянное запоминающее устройство (ПЗУ), флэш-память, динамическое ОЗУ (DRAM), например, синхронное динамическое ОЗУ (SDRAM)), статическую память 906 (например, флэш-память, статическое оперативное запоминающее устройство (ОЗУ)) и устройство хранения данных 916, которые взаимодействуют друг с другом по шине 908.
[00112]
Фиг.
1А
Фиг.
5-8
Устройство обработки 902 представляет собой одно или несколько универсальных устройств обработки, таких как микропроцессор, центральный процессор и т. п. В частности, устройство обработки данных 902 может представлять собой микропроцессор с полным набором команд (CISC), микропроцессор с сокращенным набором команд (RISC), микропроцессор со сверхдлинным командным словом (VLIW) или процессор, в котором реализованы другие наборы команд, или процессоры, в которых реализована комбинация наборов команд. Устройство обработки данных 902 также может представлять собой одно или более устройств обработки специального назначения, такое как специализированная интегральная схема (ASIC), программируемая пользователем вентильная матрица (FPGA), процессор цифровых сигналов (DSP), сетевой процессор и т. п. Устройство обработки данных 902 реализовано с возможностью выполнения инструкций 926 для реализации механизма 111 обнаружения блоков и (или) обучающей системы 151 на , а также для выполнения операций и шагов, описанных в данном документе (то есть способов 500-800 на ).
[00113]
Вычислительная система 900 может дополнительно содержать устройство сопряжения с сетью 922. Компьютерная система 900 также может содержать блок видеодисплея 910 (например, жидкокристаллический дисплей (LCD) или электронно-лучевой монитор (CRT)), алфавитно-цифровое устройство ввода 912 (например, клавиатуру), устройство управления курсором 914 (например, мышь) и устройство генерации сигналов 920 (например, громкоговоритель). В качестве одного из иллюстративных примеров устройство визуального отображения 910, буквенно-цифровое устройство ввода 912 и устройство управления курсором 914 могут быть объединены в один компонент или устройство (например, сенсорный жидкокристаллический дисплей).
[00114]
Устройство 916 хранения данных может содержать машиночитаемый носитель данных 924, в котором хранятся инструкции 926, реализующие одну или более из методик или функций, описанных в настоящем изобретении. Инструкции 926 могут также находиться полностью или, по меньшей мере, частично в основном запоминающем устройстве 904 и (или) в устройстве обработки 902 во время выполнения вычислительной системой 900, в основном запоминающем устройстве 904 и устройстве обработки 902, также представляющем собой машиночитаемый носитель информации. В некоторых вариантах осуществления инструкции 926 могут дополнительно передаваться или приниматься по сети через устройство сопряжения с сетью 922.
[00115]
Несмотря на то, что машиночитаемый носитель данных 924 показан в иллюстративных примерах как единичный носитель, термин «машиночитаемый носитель данных» следует понимать и как единичный носитель, и как несколько таких носителей (например, централизованная или распределенная база данных и (или) связанные кэши и серверы), на которых хранится один или более наборов команд. Термин «машиночитаемый носитель данных» также следует рассматривать как термин, включающий любой носитель, который способен хранить, кодировать или переносить набор команд для выполнения машиной, который заставляет эту машину выполнять любую одну или более методик, описанных в настоящем изобретении. Соответственно, термин «машиночитаемый носитель данных» следует понимать как включающий, среди прочего, устройства твердотельной памяти, оптические и магнитные носители.
[00116]
Несмотря на то, что операции способов показаны и описаны в настоящем документе в определенном порядке, порядок выполнения операций каждого способа может быть изменен таким образом, чтобы некоторые операции могли выполняться в обратном порядке или чтобы некоторые операции могли выполняться (по крайней мере частично) одновременно с другими операциями. В некоторых вариантах осуществления операции или подоперации различных операций могут выполняться с перерывами и (или) попеременно.
[00117]
Следует понимать, что приведенное выше описание носит иллюстративный, а не ограничительный характер. Различные другие варианты реализации станут очевидны специалистам в данной области техники после прочтения и понимания приведенного выше описания. Поэтому область применения изобретения должна определяться с учетом прилагаемой формулы изобретения, а также всех областей применения эквивалентных способов, которые покрывает формула изобретения.
[00118]
В приведенном выше описании изложены многочисленные детали. Однако специалистам в данной области техники должно быть очевидно, что аспекты настоящего изобретения могут быть реализованы на практике и без этих конкретных деталей. В некоторых случаях хорошо известные структуры и устройства показаны в виде блок-схем, а не подробно, для того чтобы не усложнять описание настоящего изобретения.
[00119]
Некоторые части подробных описаний выше представлены в виде алгоритмов и символического изображения операций с битами данных в компьютерной памяти. Такие описания и представления алгоритмов являются средством, используемым специалистами в области обработки данных, чтобы наиболее эффективно передавать сущность своей работы другим специалистам в данной области. Приведенный в данном документе (и в целом) алгоритм сконструирован в общем как непротиворечивая последовательность шагов, ведущих к требуемому результату. Такие шаги требуют физических манипуляций с физическими величинами. Обычно, но не обязательно, такие величины принимают форму электрических или магнитных сигналов, которые можно хранить, передавать, комбинировать, сравнивать, а также выполнять другие манипуляции. Иногда удобно, прежде всего для обычного использования, описывать такие сигналы в виде битов, значений, элементов, символов, терминов, цифр и т. д.
[00120]
Однако следует иметь в виду, что все такие и подобные термины должны быть связаны с соответствующими физическими величинами и что они являются лишь удобными обозначениями, применяемыми к таким величинам. Если прямо не указано иное, как видно из последующего обсуждения, то следует понимать, что во всем описании такие термины, как «прием» или «получение», «определение» или «обнаружение», «выбор», «хранение», «анализ» и т. п., относятся к действиям и процессам вычислительной системы или подобного электронного вычислительного устройства, причем такая система или устройство манипулирует данными и преобразует данные, представленные в виде физических (электронных) величин, в регистрах и памяти вычислительной системы в другие данные, также представленные в виде физических величин в памяти или регистрах компьютерной системы или в других подобных устройствах хранения, передачи или отображения информации.
[00121]
Настоящее изобретение также относится к устройству для выполнения операций, описанных в настоящем документе. Такое устройство может быть специально сконструировано для требуемых целей, либо оно может представлять собой универсальный компьютер, который избирательно приводится в действие или дополнительно настраивается с помощью программы, хранящейся в памяти компьютера. Такая вычислительная программа может храниться на машиночитаемом носителе данных, включая, среди прочего, диски любого типа, в том числе гибкие диски, оптические диски, CD-ROM и магнитно-оптические диски, постоянные запоминающие устройства (ПЗУ), оперативные запоминающие устройства (ОЗУ), программируемые ПЗУ (EPROM), электрически стираемые ППЗУ (EEPROM), магнитные или оптические карты или носитель любого типа, пригодный для хранения электронных команд, каждый из которых соединен с шиной вычислительной системы.
[00122]
Алгоритмы и изображения, приведенные в настоящем документе, не обязательно связаны с конкретными компьютерами или другими устройствами. Различные системы общего назначения могут использоваться с программами в соответствии с изложенной в настоящем документе информацией, возможно также признание целесообразности конструирования более специализированного устройства для выполнения необходимых шагов способа. Необходимая структура различных систем такого рода определяется в порядке, предусмотренном в описании. Кроме того, изложение вариантов осуществления настоящего изобретения не предполагает ссылок на какие-либо конкретные языки программирования. Следует принимать во внимание, что для реализации принципов настоящего изобретения могут быть использованы различные языки программирования.
[00123]
Варианты осуществления настоящего изобретения могут быть представлены в виде компьютерного программного продукта или программы, которая может содержать машиночитаемый носитель данных с сохраненными на нем инструкциями, которые могут использоваться для программирования компьютерной системы (или других электронных устройств) в целях выполнения процесса в соответствии с настоящим изобретением. Машиночитаемый носитель данных включает механизмы хранения или передачи информации в машиночитаемой форме (например, компьютер). Например, машиночитаемый (то есть считываемый компьютером) носитель данных содержит носитель данных, считываемый машиной (например, компьютером) (например, постоянное запоминающее устройство (ПЗУ), оперативное запоминающее устройство (ОЗУ), накопитель на магнитных дисках, накопитель на оптическом носителе, устройства флэш-памяти и пр.).
[00124]
Слова «пример» или «примерный» используются в настоящем документе для обозначения использования в качестве примера, отдельного случая или иллюстрации. Любой вариант осуществления или конструкция, описанная в настоящем документе как «пример», не должна обязательно рассматриваться как предпочтительная или преимущественная по сравнению с другими вариантами осуществления или конструкциями. Слово «пример» лишь предполагает, что идея изобретения представлена конкретным образом. В настоящей заявке термин «или» предназначен для обозначения, включающего «или», а не исключающего «или». Это означает, если не указано иное или не очевидно из контекста, что «X содержит А или В» используется для обозначения любой из естественных включающих перестановок. То есть если X содержит А, Х содержит B или Х содержит и А, и В, то высказывание «X содержит А или В» является истинным в любом из указанных выше случаев. Кроме того, неопределенные артикли, использованные в настоящей заявке и прилагаемой формуле изобретения, должны, как правило, означать «один или более», если иное не указано или из контекста не следует, что это относится к форме единственного числа. Использование терминов «вариант осуществления» или «один вариант осуществления», либо «реализация» или «одна реализация» не означает одинаковый вариант осуществления или реализации, если это не указано в описании. Кроме того, в описании термины «первый», «второй», «третий», «четвертый» и т. д. используются как метки для обозначения различных элементов и не обязательно имеют смысл порядка в соответствии с их числовым значением.
[00125]
Принимая во внимание множество вариантов и модификаций настоящего изобретения, которые, без сомнения, будут очевидны лицу со средним опытом в профессии после прочтения изложенного выше описания, следует понимать, что любой частный вариант осуществления изобретения, приведенный и описанный для иллюстрации, ни в коем случае не должен рассматриваться как ограничение. Таким образом, ссылки на подробности различных вариантов осуществления изобретения не должны рассматриваться как ограничение объема притязания, который содержит только признаки, относящиеся к сущности изобретения.