RU2294011C2

Movatterモバイル変換

Info

Publication number: RU2294011C2
Application number: RU2004112818/09A
Authority: RU
Inventors: Александр Алексеевич Кибкало (RU); Александр Алексеевич Кибкало; Иван П. Рыжачкин (RU); Иван П. Рыжачкин
Original assignee: Интел Зао
Priority date: 2001-10-19
Filing date: 2001-10-19
Publication date: 2007-02-20
Also published as: RU2004112818A

Abstract

FIELD: statistical language models, used in speech recognition systems.

SUBSTANCE: word indexes of bigrams are stored in form of common base with characteristic shifting. In one variant of realization, memory volume required for serial storage of bigram word indexes is compared to volume of memory, required for storage of indexes of bigram words in form of common base with characteristic shifting. Then indexes of bigram words are stored for minimization of size of data file of language model.

EFFECT: decreased memory volume needed for storing data structure of language model.

7 cl, 4 dwg

Description

Translated fromRussian

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

Данное изобретение относится в целом к области статистических моделей языка, используемым в системах распознавания речи (CSR), в частности касается способа и устройства для более эффективной организации таких моделей.This invention relates generally to the field of statistical language models used in speech recognition systems (CSR), in particular, relates to a method and device for more efficient organization of such models.

Уровень техникиState of the art

Известные из уровня техники системы распознавания слитной речи работают посредством формирования ряда гипотез последовательности слов и вычисления вероятности каждой последовательности слов. Последовательности с низкой вероятностью отсекаются, в то время как последовательности с высокой вероятностью продолжаются. Когда декодирование речевого ввода завершается, то последовательность с наивысшей вероятностью принимается в качестве результата распознавания. Говоря обобщенно, используется отсчет на основе вероятности. Отсчет последовательностей является суммой акустического отсчета (суммы акустических логарифмов вероятности для всех минимальных единиц речи - звуков или слогов) и лингвистического отсчета (суммы лингвистических логарифмов вероятности для всех слов в речевом вводе).Known speech recognition systems of the prior art work by generating a series of hypotheses of a sequence of words and calculating the probability of each sequence of words. Sequences with low probability are cut off, while sequences with high probability continue. When the decoding of the speech input is completed, the sequence with the highest probability is accepted as the recognition result. Generally speaking, a probability-based sample is used. A sequence count is the sum of an acoustic sample (the sum of the acoustic probability logarithms for all the minimum units of speech — sounds or syllables) and a linguistic sample (the sum of the linguistic probability logarithms for all the words in the speech input).

В системах распознавания слитной речи обычно используют статистическую n-граммную модель языка для разработки статистических данных. Такая модель вычисляет вероятность наблюдения n последовательных слов в заданной области, поскольку на практике можно предположить, что текущее слово зависит от n предшествующих ему слов. Униграммная модель вычисляет P(w), которая является вероятностью для каждого слова w. Биграммная модель использует униграммы и условную вероятность P(w₂|w₁), которая является вероятностью слова w₂, при условии, что предшествующее слово является словом w₁, для каждого слова w₁ и w₂. Триграммная модель использует униграммы, биграммы и условную вероятность P(w₃|w₂,w₁), которая является вероятностью слова w₃, при условии, что два предшествующих слова являются w₁ и w₂, для каждого слова w₃, w₂ и w₁. Величины биграммных и триграммных вероятностей вычисляют во время обучения модели языка, что требует огромного количества текстовых данных, текстового корпуса. Вероятность можно точно оценивать, если последовательность слов появляется сравнительно часто в данных обучения. Такие вероятности являются условно существующими. Для n-граммных вероятностей, которые не существуют, используют возвратную формулу для приближения величины.In continuous speech recognition systems, a statistical n-gram language model is usually used to develop statistical data. Such a model calculates the probability of observing n consecutive words in a given area, since in practice it can be assumed that the current word depends on n words preceding it. The unigram model computes P (w), which is the probability for each word w. The bigram model uses unigrams and the conditional probability P (w₂ | w₁ ), which is the probability of the word w₂ , provided that the preceding word is the word w₁ , for each word w₁ and w₂ . The trigram model uses unigrams, bigrams and the conditional probability P (w₃ | w₂ , w₁ ), which is the probability of the word w₃ , provided that the two preceding words are w₁ and w₂ , for each word w₃ , w₂ and w₁ . The magnitudes of the bigram and trigram probabilities are calculated during the training of the language model, which requires a huge amount of text data, a text corpus. Probability can be accurately estimated if a sequence of words appears relatively frequently in training data. Such probabilities are conditionally existing. For n-gram probabilities that do not exist, use the return formula to approximate the magnitude.

Такие статистические модели языка являются особенно полезными для систем распознавания слитной речи с большим словарным запасом, которые распознают произвольную речь (задача речевого ввода). Например, теоретически для словаря, состоящего из 50000 слов, будет 50000 униграмм, миллиарды (50000²) биграмм и более 100 триллионов (50000³) триграмм. На практике числа значительно уменьшаются, поскольку биграммы и триграммы существуют только для пар слов и троек слов, которые появляются относительно часто. Например, в английском языке для хорошо известной задачи Уол Стрит Джорнал (WSJ) со словарем в 20000 слов, в модели языка используется лишь семь миллионов биграмм и 14 миллионов триграмм. Эти числа зависят от конкретного языка, области задачи и размера корпуса текста, используемого для разработки модели языка. Тем не менее, это все еще огромное количество данных, и размер базы данных модели языка и способ доступа к данным оказывает значительное воздействие на жизненность системы распознавания речи. Ниже приводится описание типичной структуры данных модели языка со ссылками на фиг.1.Such statistical language models are especially useful for continuous vocabulary recognition systems that recognize arbitrary speech (speech input task). For example, theoretically, for a dictionary of 50,000 words, there will be 50,000 unigrams, billions (50,000² ) bigrams, and more than 100 trillion (50,000³ ) trigrams. In practice, the numbers are significantly reduced, since bigrams and trigrams exist only for pairs of words and triples of words that appear relatively often. For example, in the English language for the well-known task of the Wall Street Journal (WSJ) with a dictionary of 20,000 words, the language model uses only seven million bigrams and 14 million trigrams. These numbers depend on the specific language, the task area and the size of the body of the text used to develop the language model. Nevertheless, this is still a huge amount of data, and the size of the language model database and the way of accessing the data have a significant impact on the vitality of the speech recognition system. The following is a description of a typical data structure of a language model with reference to FIG.

На фиг.1 показана триграммная структура данных модели языка, согласно уровню техники. Структура 100 данных, показанная на фиг.1, содержит униграммный уровень 105, биграммный уровень 110 и триграммный уровень 115. Запись P(w₃|w₂,w₁), где w₃, w₂ и w₁ являются индексами слов, обозначает вероятность слова w₃, при условии, что два предшествующих слова являются словом w₁ и следующим за ним словом w₂. Для определения такой вероятности слово w₁ расположено на униграммном уровне 105, при этом униграммный уровень содержит связь с биграммным уровнем. Получают указатель к соответствующему биграммному уровню 110 и определяют биграмму, соответствующую w₁|w₂, при этом биграммный узел содержит связь с триграммным уровнем. Отсюда получают указатель к соответствующему триграммному уровню 115 и извлекают вероятность P(w₃|w₂,w₁) триграммы. Обычно, униграммы, биграммы и триграммы структуры данных модели языка, согласно уровню техники, все хранятся в простом последовательном порядке и разыскиваются последовательно. Поэтому, при поиске биграммы получают, например, связь с биграммным уровнем из униграммного уровня, и выполняют последовательный поиск биграммы для получения индекса для второго слова.Figure 1 shows the trigram data structure of a language model, according to the prior art. Thedata structure 100 shown in Figure 1 comprisesunigrammny level 105,level 110 and Bigramtrigram level 115. Recording P (w₃ | w_2, w_1), wherein w_3, w₂ and w₁ are indexes of words, means the probability of the word w₃ , provided that the two preceding words are the word w₁ and the next word w₂ . To determine this probability, the word w₁ is located at theunigram level 105, while the unigram level contains a connection with the bigram level. A pointer is obtained to thecorresponding bigram level 110 and the bigram corresponding to w₁ | w₂ is determined, while the bigram node contains a connection with the trigram level. From this, a pointer to thecorresponding trigram level 115 is obtained and the probability P (w₃ | w₂ , w₁ ) of the trigram is extracted. Typically, unigrams, bigrams, and trigrams of the data structure of a language model, according to the prior art, are all stored in a simple sequential order and searched sequentially. Therefore, when searching for a bigram, they obtain, for example, a connection with the bigram level from the unigram level, and perform a sequential search for the bigram to obtain an index for the second word.

Системы распознавания речи часто осуществляются в небольших, компактных вычислительных системах, таких как персональные компьютеры, компактные персональные компьютеры и даже переносные компьютерные системы. Такие системы имеют ограниченные возможности по скорости обработки и объему хранения данных, так что желательно уменьшить память, необходимую для хранения структуры данных модели языка.Speech recognition systems are often implemented in small, compact computing systems such as personal computers, compact personal computers, and even laptop computer systems. Such systems have limited capabilities in terms of processing speed and data storage volume, so it is desirable to reduce the memory needed to store the data structure of the language model.

Краткое описание чертежейBrief Description of the Drawings

Настоящее изобретение описано с использованием примера, не ограничивающего его. Пример излагается со ссылками на прилагаемые чертежи, на которых подобные элементы обозначены одинаковыми позициями и на которых изображено:The present invention has been described using non-limiting example. An example is set out with reference to the accompanying drawings, in which similar elements are denoted by the same positions and which depict:

фиг.1 - триграммная структура данных модели языка, согласно уровню техники;figure 1 - trigram data structure of the language model, according to the prior art;

фиг.2 - блок-схема примера выполнения вычислительной системы 200 для осуществления базы данных модели языка для системы распознавания слитной речи, согласно данному изобретению;FIG. 2 is a block diagram of an example embodiment of a computing system 200 for implementing a language model database for a continuous speech recognition system according to the present invention; FIG.

фиг.3 - иерархическая структура хранения, согласно варианту выполнения данного изобретения; иfigure 3 - hierarchical storage structure, according to a variant implementation of the present invention; and

фиг.4 - графическая схема процесса, согласно варианту выполнения данного изобретения.4 is a graphical diagram of a process according to an embodiment of the present invention.

Подробное описание вариантов осуществления изобретенияDetailed Description of Embodiments

Ниже приводится описание улучшенной структуры данных модели языка. Способ согласно данному изобретению уменьшает размер файла данных модели языка. В одном варианте осуществления изобретения информацию управления (например, индекс слова) для биграммного уровня сжимают с использованием иерархической биграммной структуры хранения. Данное изобретение направлено на получение технического преимущества от того факта, что распределение индексов слов для биграмм конкретной униграммы часто находятся внутри 255 индексов друг от друга (то есть, смещение может быть представлено одним байтом). Это позволяет хранить множество индексов слов в виде основы из 2 байт со смещением в один байт, в противоположность использованию трех байтов для хранения каждого индекса слова. Схем сжатия данных, согласно данному изобретению, применима, в частности, к биграммному уровню. Это объясняется тем, что каждая униграмма имеет в среднем приблизительно 300 биграмм по сравнению с приблизительно тремя триграммами для каждой биграммы. То есть, на уровне биграмм имеется достаточно информации для практического осуществления иерархической структуры хранения. В одном варианте выполнения используется иерархическая структура для хранения биграммной информации только тех униграмм, которые имеют особенно большое число соответствующих биграмм. Биграммную информацию для униграмм, имеющих непрактично малое количество биграмм, сохраняется последовательно, согласно уровню техники.The following is a description of the improved language model data structure. The method according to this invention reduces the file size of the language model data. In one embodiment of the invention, control information (eg, a word index) for a bigram level is compressed using a hierarchical bigram storage structure. The present invention seeks to obtain a technical advantage from the fact that the distribution of word indices for the bigrams of a particular unigram are often within 255 indices from each other (i.e., the offset can be represented by one byte). This allows you to store multiple word indices in the form of a 2 byte base with an offset of one byte, as opposed to using three bytes to store each word index. The data compression schemes of the present invention are applicable, in particular, to the bigram level. This is because each unigram has an average of about 300 bigrams, compared with about three trigrams for each bigram. That is, at the level of the bigrams there is enough information for the practical implementation of the hierarchical structure of storage. In one embodiment, a hierarchical structure is used to store bigram information of only those unigrams that have a particularly large number of corresponding bigrams. Bigram information for unigrams having an impractically small number of bigrams is stored sequentially according to the prior art.

Способ согласно данному изобретению можно распространять на другие применения поиска на основе индексов, имеющих большое число индексов, где каждый индекс требует значительного объема памяти.The method according to this invention can be extended to other search applications based on indexes having a large number of indexes, where each index requires a significant amount of memory.

На фиг.2 показана блок-схема примера выполнения вычислительной системы 200 для осуществления базы данных модели языка для системы распознавания слитной речи, согласно данному изобретению. Различные способы вычисления и сравнения памяти для хранения данных и иерархическую структуру файлов индексов слов, описываемых здесь, можно осуществлять и использовать внутри вычислительной системы 200, которая может представлять компьютер общего пользования, переносной компьютер или другие подобные устройства. Компоненты вычислительной системы 200 приведены в качестве примера, при этом один или более компонентов могут быть опущены или добавлены. Например, можно использовать одно или более устройств памяти для вычислительной системы 200.FIG. 2 shows a block diagram of an example embodiment of a computing system 200 for implementing a language model database for a continuous speech recognition system according to the present invention. Various methods for calculating and comparing data storage memory and the hierarchical structure of the word index files described herein can be implemented and used within a computing system 200, which may be a public computer, laptop computer, or other similar devices. The components of the computing system 200 are given as an example, wherein one or more components may be omitted or added. For example, one or more memory devices may be used for computing system 200.

Как показано на фиг.2, вычислительная система 200 содержит центральный процессор 202 и сигнальный процессор 203, соединенный с дисплейной схемой 205, основной памятью 204, статической памятью 206 и устройством 207 массовой памяти через шину 201. Вычислительная система 200 может быть также соединена с дисплеем 221, клавиатурой 222 ввода, устройством 223 управления курсором, устройством 224 для получения твердых копий, устройствами 225 ввода/вывода и звуковым/речевым устройством 226 через шину 201.As shown in FIG. 2, the computing system 200 comprises a central processor 202 and a signal processor 203 connected to a display circuit 205, a main memory 204, a static memory 206, and a mass storage device 207 via a bus 201. The computing system 200 may also be connected to a display 221, an input keyboard 222, a cursor control device 223, hard copy devices 224, input / output devices 225, and an audio / speech device 226 via a bus 201.

Шина 201 является стандартной системной шиной для передачи информации и сигналов. Центральный процессор 202 и сигнальный процессор 203 являются блоками обработки для вычислительной системы 200. Центральный процессор 202 или сигнальный процессор 203 или оба можно использовать для обработки информации и/или сигналов для вычислительной системы 200. Центральный процессор 202 содержит блок 231 управления, блок 232 арифметической логики и несколько регистров 233, которые используются для обработки информации и сигналов. Сигнальный процессор 203 может содержать компоненты, аналогичные компонентам центрального процессора 202.Bus 201 is a standard system bus for transmitting information and signals. The central processor 202 and the signal processor 203 are processing units for the computing system 200. The central processor 202 or the signal processor 203 or both can be used to process information and / or signals for the computing system 200. The central processor 202 comprises a control unit 231, an arithmetic logic unit 232 and several registers 233, which are used to process information and signals. The signal processor 203 may comprise components similar to those of the central processor 202.

Основное устройство 204 памяти может быть, например, оперативным запоминающим устройством (памятью с произвольным доступом RAM) или другим устройством динамичной памяти для хранения информации или команд (программных кодов), которые используются центральным процессором 202 или сигнальным процессором 203. Основное устройство 204 памяти может хранить временные переменные или другую промежуточную информацию во время выполнения команд центральным процессором 202 или сигнальным процессором 203. Статическая память 206 может быть, например, постоянным запоминающим устройством (ROM) и/или другим статическим устройством хранения, для хранения информации или команд, которые могут также использоваться центральным процессором 202 или сигнальным процессором 203. Устройство 207 массового хранения может быть, например, приводом жесткого или гибкого диска или приводом оптического диска для хранения информации или команд для вычислительной системы 200.The main memory device 204 can be, for example, random access memory (random access memory RAM) or another dynamic memory device for storing information or instructions (program codes) that are used by the central processor 202 or the signal processor 203. The main memory device 204 can store temporary variables or other intermediate information during execution of instructions by the central processor 202 or the signal processor 203. The static memory 206 may, for example, be permanent a memory device (ROM) and / or other static storage device, for storing information or instructions that can also be used by the central processor 202 or the signal processor 203. The mass storage device 207 may be, for example, a hard disk drive or a flexible disk drive or an optical disk drive for storing information or instructions for computing system 200.

Дисплей 221 может быть, например, катодно-лучевой трубкой или жидкокристаллическим дисплеем. Дисплей 221 отображает информацию или графическую информацию для пользователя. Вычислительная система 200 может взаимодействовать с дисплеем 221 через интерфейс-дисплейную схему 205. Клавиатура 222 ввода является буквенно-цифровым устройством ввода с аналого-цифровым преобразователем. Устройство 223 управления курсором может быть, например, мышью, шаровым манипулятором или клавишами управления курсором для управления перемещением объекта на дисплее 221. Устройство 224 для получения твердых копий может быть, например, лазерным принтером для печати информации на бумаге, пленке или другом подобном носителе. С вычислительной системой 200 может быть соединено несколько устройств 225 ввода/вывода. Иерархическую структуру файлов индексов слов согласно данному изобретению можно осуществлять с помощью аппаратурного обеспечения и/или программного обеспечения, содержащегося внутри вычислительной системы 200. Например, центральный процессор 202 или сигнальный процессор 203 могут выполнять коды или команды, хранящиеся в машинно-считываемом носителе информации, например, в основном устройстве 204 памяти.The display 221 may be, for example, a cathode ray tube or a liquid crystal display. The display 221 displays information or graphic information for the user. Computing system 200 may communicate with display 221 via an interface-display circuit 205. The input keyboard 222 is an alphanumeric input device with an analog-to-digital converter. The cursor control device 223 may be, for example, a mouse, trackball, or cursor keys to control the movement of an object on the display 221. The hard copy device 224 may be, for example, a laser printer for printing information on paper, film, or other similar media. Multiple input / output devices 225 may be coupled to computing system 200. The hierarchical structure of the word index files according to this invention can be implemented using hardware and / or software contained within the computing system 200. For example, the central processor 202 or the signal processor 203 can execute codes or instructions stored in a computer-readable storage medium, for example , in the main memory device 204.

Машинно-считываемый носитель информации может содержать механизм, который обеспечивает (т.е. хранит и/или передает) информацию в считываемом машиной виде, такой как компьютер или цифровое устройство обработки. Например, машинно-считываемый носитель информации может включать постоянную память, оперативную память, средство хранения данных на магнитном диске, средство хранения данных на оптическом диске, устройства флэш-памяти. Коды или команды могут быть представлены сигналами несущей частоты, инфракрасными сигналами, цифровыми сигналами и другими подобными сигналами.A computer-readable storage medium may comprise a mechanism that provides (i.e. stores and / or transmits) information readable by a machine, such as a computer or digital processing device. For example, a computer-readable storage medium may include read only memory, random access memory, magnetic disk data storage means, optical disk data storage means, flash memory devices. Codes or instructions may be represented by carrier signals, infrared signals, digital signals, and other similar signals.

На фиг.3 показана иерархическая структура хранения данных согласно одному варианту выполнения данного изобретения. Иерархическая структура 300, показанная на фиг.3, содержит униграммный уровень 310, биграммный уровень 320 и триграммный уровень 330.Figure 3 shows a hierarchical data storage structure according to one embodiment of the present invention. Thehierarchical structure 300 shown in FIG. 3 comprises aunigram level 310, abigram level 320, and atrigram level 330.

На униграммном уровне 310, униграммная вероятность и возвратный вес - оба являются индексами в таблице величин и не подлежат дальнейшему сокращению.Atunigram level 310, unigram probability and return weight are both indices in the value table and cannot be further reduced.

В среднем униграммы имеют 300 биграмм, что делает иерархическое хранение практичным, однако отдельные униграммы могут иметь слишком мало биграмм для оправдания рабочих полей иерархической структуры. Униграммы разделены на две группы: униграммы 311 с достаточным числом биграмм, для того чтобы иерархическое хранение данных биграмм было практичным, и униграммы 312 со слишком малым числом соответствующих биграмм, для того чтобы иерархическое хранение было практичным. Например, для задачи Уол Стрит Джорнал (WSJ), имеющей 19958 униграмм, 16738 униграмм имеют достаточно биграмм для оправдания иерархического хранения, и поэтому биграммная информация, соответствующая этим униграммам, хранится в иерархическом порядке 321 биграмм. Такие униграммы содержат биграммную связь с иерархическим биграммным порядком 321. Остальные 3220 униграмм не имеют достаточного числа биграмм для оправдания иерархического хранения, и поэтому соответствующая биграммная информация хранится в простом последовательном порядке. Эти униграммы содержат биграммную связь с последовательным биграммным порядком 322. В типичном текстовом корпусе имеется очень немного униграмм, которые не имеют биграмм, и поэтому они не хранятся отдельно.On average, unigrams have 300 bigrams, which makes hierarchical storage practical, but individual unigrams may have too few bigrams to justify the working fields of the hierarchical structure. Unigrams are divided into two groups:unigrams 311 with enough bigrams to make hierarchical storage of bigrams data practical, andunigrams 312 with too few corresponding bigrams to make hierarchical storage practical. For example, for the Wall Street Journal (WSJ) problem with 19958 unigrams, 16738 unigrams have enough bigrams to justify hierarchical storage, and therefore the bigramic information corresponding to these unigrams is stored in a hierarchical order of 321 bigrams. Such unigrams contain a bigramic connection with ahierarchical bigramic order 321. The remaining 3220 unigrams do not have enough bigrams to justify hierarchical storage, and therefore the corresponding bigramic information is stored in a simple sequential order. These unigrams contain a bigramic link with asequential bigramic order 322. In a typical text box there are very few unigrams that do not have bigrams, and therefore they are not stored separately.

На биграммном уровне 320 каждая биграмма (т.е. те, которые имеют соответствующие триграммы) имеет связь с триграммным уровнем 330. Для типичного текстового корпуса имеется сравнительно больше биграмм, которые не имеют триграмм, чем униграмм, которые не имеют биграмм. Например, в задаче Уол Стрит Джорнал (WSJ), имеющей 6850083 биграмм, 3414195 биграмм имеют соответствующие триграммы, а 3435888 биграмм не имеют соответствующих триграмм. В одном варианте выполнения биграммы, которые не имеют триграмм, хранятся отдельно, что обеспечивает устранение четырех байтного поля связей триграмм в этих случаях.At thebigram level 320, each bigram (that is, those that have corresponding trigrams) has a connection with thetrigram level 330. For a typical text case, there are relatively more bigrams that don't have trigrams than unigrams that don't have bigrams. For example, in the Wall Street Journal (WSJ) problem with 6850083 bigrams, 3414195 bigrams have corresponding trigrams, and 3435888 bigrams do not have corresponding trigrams. In one embodiment, the bigrams that do not have trigrams are stored separately, which eliminates the four byte field of the trigram link in these cases.

Обычно, индексы слов биграмм для одной униграммы являются очень близкими друг другу. Близость этих индексов слов является особенностью, присущей языку. Это распределение существующих индексов биграмм позволяет разделять индексы на группы, так что смещение между первым индексом слов биграмм и последним индексом слов биграмм составляет менее 256. Таким образом, это смещение можно сохранять в одном байте. Это позволяет представлять, например, индекс слова из трех байт в виде суммы основы из двух байт и смещения в один байт. Таким образом, поскольку два байта высокого порядка индекса слова повторяются для нескольких биграмм, то эти два байта можно исключить из хранения для некоторых групп биграмм. Такое хранение согласно данному изобретению обеспечивает значительное сжатие на биграммном уровне. Как указывалось выше, это не относится к биграммам, соответствующим каждой униграмме. Согласно данному изобретению вычисляют объем хранения для определения, можно ли его сократить за счет иерархического хранения. Если нет, то индексы биграмм для конкретной униграммы хранят последовательно согласно уровню техники.Typically, bigram word indices for one unigram are very close to each other. The proximity of these word indices is a feature inherent in the language. This distribution of existing bigram indexes allows you to separate the indices into groups, so that the offset between the first bigram word index and the last bigram word index is less than 256. Thus, this offset can be stored in one byte. This makes it possible to represent, for example, a three-byte word index as the sum of a base of two bytes and an offset of one byte. Thus, since two high-order bytes of the word index are repeated for several bigrams, these two bytes can be excluded from storage for some groups of bigrams. Such storage according to this invention provides significant compression at the bigram level. As indicated above, this does not apply to bigrams corresponding to each unigram. According to the present invention, the storage volume is calculated to determine whether it can be reduced by hierarchical storage. If not, then the bigram indices for a particular unigram are stored sequentially according to the prior art.

На фиг.4 показана графическая схема процесса согласно варианту выполнения данного изобретения. Процесс 400, показанный на фиг.4, начинается операцией 405, в которой оценивают биграммы, соответствующие заданной униграмме, для определения объема памяти, необходимого для простой схемы последовательного хранения. В операции 410 требования к памяти для последовательного хранения сравнивают с требованиями к памяти для хранения иерархической структуры данных. Если не имеется сжатия данных (т.е. сокращения требований к памяти), то индексы слов биграмм сохраняют последовательно в операции 415. Если иерархическое хранение данных уменьшает требования к памяти, то индексы слов биграмм сохраняют в виде общей основы с характерным смещением в операции 420. Например, для индекса слова в три байта, общая основа может состоять из двух байтов со смещением в один байт.Figure 4 shows a graphical diagram of a process according to an embodiment of the present invention. Theprocess 400 shown in FIG. 4 begins withoperation 405, in which the bigrams corresponding to a given unigram are evaluated to determine the amount of memory required for a simple sequential storage scheme. Atoperation 410, memory requirements for sequential storage are compared with memory requirements for storing a hierarchical data structure. If there is no data compression (ie, reduction of memory requirements), then the bigram word indexes are stored sequentially inoperation 415. If hierarchical data storage reduces the memory requirements, then the bigram word indexes are stored as a common basis with a characteristic offset inoperation 420 For example, for a word index of three bytes, a common base can consist of two bytes with an offset of one byte.

Степень сжатия зависит от вероятностей биграмм в модели языка. Модель языка, используемая в задаче Уол Стрит Джорнал (WSJ), имеет приблизительно шесть миллионов вероятностей биграмм, что требует объема памяти приблизительно 97 МБайт. Осуществление иерархической структуры хранения, согласно данному изобретению, обеспечивает сжатие в 32% индексов биграмм, что сокращает общий объем памяти на 12 МБайт (т.е. в целом приблизительно на 11%). Для других моделей языка степень сжатия может быть выше. Например, осуществление иерархической структуры хранения биграмм для модели языка для задачи 863 китайского языка обеспечивает степень сжатия индексов биграмм приблизительно на 61,8%. Это дает полную степень сжатия в 26,7% (т.е. 70,3 МБайт сжимаются до 51,5 МБайт). Это сокращение файла данных модели языка значительно уменьшает требования к объему памяти и к времени обработки данных.The degree of compression depends on the probabilities of the bigrams in the language model. The language model used by the Wall Street Journal (WSJ) has approximately six million bigram probabilities, which requires approximately 97 MB of memory. The implementation of the hierarchical storage structure according to this invention provides compression in 32% of the bigram indexes, which reduces the total memory capacity by 12 MB (i.e., in general by approximately 11%). For other language models, the compression ratio may be higher. For example, implementing a hierarchical structure of bigram storage for a language model for Chinese task 863 provides a compression ratio of bigram indices of approximately 61.8%. This gives a full compression ratio of 26.7% (i.e. 70.3 MB are compressed to 51.5 MB). This reduction of the language model data file significantly reduces memory requirements and data processing time.

Технология сжатия согласно данному изобретению не является практичной на триграммном уровне, поскольку здесь имеется, в среднем, только приблизительно три триграммы на одну биграмму для модели языка для задачи Уол Стрит Джорнал (WSJ). Триграммный уровень также не содержит возвратного веса или полей связи, поскольку нет более высокого уровня.The compression technology of the present invention is not practical at the trigram level, since there is, on average, only about three trigrams per big gram for a language model for the Wall Street Journal (WSJ). The trigram level also does not contain return weight or communication fields, since there is no higher level.

Данный патент можно распространить на использование в других сценариях структурированного поиска, где индекс слова является ключом; каждый индекс слова требует значительного объема памяти; и число индексов слов является огромным.This patent can be extended to use in other structured search scenarios, where the word index is the key; each word index requires a significant amount of memory; and the number of word indices is huge.

Хотя изобретение описано применительно к нескольким вариантам выполнения и иллюстративным фигурам, для специалистов в данной области техники понятно, что изобретение не ограничивается приведенными вариантами выполнения или конкретными фигурами. В частности, изобретение может быть реализовано в нескольких альтернативных вариантах выполнения, которые обеспечивают иерархическую структуру данных для уменьшения размера базы данных модели языка.Although the invention has been described with reference to several embodiments and illustrative figures, it will be understood by those skilled in the art that the invention is not limited to the embodiments or specific figures. In particular, the invention can be implemented in several alternative embodiments that provide a hierarchical data structure to reduce the size of the language model database.

Поэтому следует понимать, что способ и устройство согласно изобретению могут быть реализованы с различными модификациями и изменениями, оставаясь в пределах прилагаемой формулы изобретения. Таким образом, настоящее описание следует рассматривать как иллюстрацию, а не ограничение изобретения.Therefore, it should be understood that the method and device according to the invention can be implemented with various modifications and changes, while remaining within the scope of the attached claims. Thus, the present description should be considered as an illustration, and not a limitation of the invention.