Организация словаря на основе применения метода построения дополнительного графа-пирамиды
Предлагается метод организации словаря на основе использования графа-пирамиды, который позволяет без увеличения размера словаря учитывать случаи пропуска, замены и наличия лишних букв в распознаваемых словах. Для хранения совпадающих фрагментов слов используется только одна вершина пирамиды-слова...
Збережено в:
| Дата: | 2009 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем штучного інтелекту МОН України та НАН України
2009
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/8058 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Организация словаря на основе применения метода построения дополнительного графа-пирамиды / А.В. Агарков // Штучний інтелект. — 2009. — № 3. — С. 161-169. — Бібліогр.: 5 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-8058 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-80582025-02-10T00:45:29Z Организация словаря на основе применения метода построения дополнительного графа-пирамиды Організація словника на основі застосування методу побудови додаткового графа-піраміди Dictionary Construction on the Basis of Application of Additional Graph-Pyramid Building Method Агарков, А.В. Компьютерная обработка естественноязыковых текстов и семантический поиск Предлагается метод организации словаря на основе использования графа-пирамиды, который позволяет без увеличения размера словаря учитывать случаи пропуска, замены и наличия лишних букв в распознаваемых словах. Для хранения совпадающих фрагментов слов используется только одна вершина пирамиды-словаря, что позволяет определять общие фрагменты слов без проведения дополнительного поиска. Пропонується метод організації словника на основі використання графa-піраміди, що дозволяє без збільшення розміру словника враховувати випадки пропуску, заміни і наявності зайвих букв у словах, що розпізнаються. Для збереження збіжних фрагментів слів використовується тільки одна вершина піраміди-словника, що дозволяє визначати загальні фрагменти слів без проведення додаткового пошуку. It is proposed the dictionary construction method on the basis of the graph-pyramid using which allows to consider without increase in the size of the dictionary cases omission, replacement and presence of superfluous letters in recognized words. For storage of conterminous fragments of words only one pyramid-dictionary vertex is used which allows to define the common word fragments without carrying out of additional search. 2009 Article Организация словаря на основе применения метода построения дополнительного графа-пирамиды / А.В. Агарков // Штучний інтелект. — 2009. — № 3. — С. 161-169. — Бібліогр.: 5 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/8058 004.93 004.89 ru application/pdf Інститут проблем штучного інтелекту МОН України та НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Компьютерная обработка естественноязыковых текстов и семантический поиск Компьютерная обработка естественноязыковых текстов и семантический поиск |
| spellingShingle |
Компьютерная обработка естественноязыковых текстов и семантический поиск Компьютерная обработка естественноязыковых текстов и семантический поиск Агарков, А.В. Организация словаря на основе применения метода построения дополнительного графа-пирамиды |
| description |
Предлагается метод организации словаря на основе использования графа-пирамиды, который позволяет
без увеличения размера словаря учитывать случаи пропуска, замены и наличия лишних букв в
распознаваемых словах. Для хранения совпадающих фрагментов слов используется только одна вершина
пирамиды-словаря, что позволяет определять общие фрагменты слов без проведения дополнительного поиска. |
| format |
Article |
| author |
Агарков, А.В. |
| author_facet |
Агарков, А.В. |
| author_sort |
Агарков, А.В. |
| title |
Организация словаря на основе применения метода построения дополнительного графа-пирамиды |
| title_short |
Организация словаря на основе применения метода построения дополнительного графа-пирамиды |
| title_full |
Организация словаря на основе применения метода построения дополнительного графа-пирамиды |
| title_fullStr |
Организация словаря на основе применения метода построения дополнительного графа-пирамиды |
| title_full_unstemmed |
Организация словаря на основе применения метода построения дополнительного графа-пирамиды |
| title_sort |
организация словаря на основе применения метода построения дополнительного графа-пирамиды |
| publisher |
Інститут проблем штучного інтелекту МОН України та НАН України |
| publishDate |
2009 |
| topic_facet |
Компьютерная обработка естественноязыковых текстов и семантический поиск |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/8058 |
| citation_txt |
Организация словаря на основе применения метода построения дополнительного графа-пирамиды / А.В. Агарков // Штучний інтелект. — 2009. — № 3. — С. 161-169. — Бібліогр.: 5 назв. — рос. |
| work_keys_str_mv |
AT agarkovav organizaciâslovarânaosnoveprimeneniâmetodapostroeniâdopolnitelʹnogografapiramidy AT agarkovav organízacíâslovnikanaosnovízastosuvannâmetodupobudovidodatkovogografapíramídi AT agarkovav dictionaryconstructiononthebasisofapplicationofadditionalgraphpyramidbuildingmethod |
| first_indexed |
2025-12-02T07:25:49Z |
| last_indexed |
2025-12-02T07:25:49Z |
| _version_ |
1850380490163355648 |
| fulltext |
«Штучний інтелект» 3’2009 161
4А
УДК 004.93 004.89
А.В. Агарков
Институт проблем искусственного интеллекта МОН Украины и НАН Украины,
г. Донецк, Украина
aav@iai.donetsk.ua
Организация словаря на основе применения
метода построения дополнительного
графа-пирамиды
Предлагается метод организации словаря на основе использования графа-пирамиды, который позволяет
без увеличения размера словаря учитывать случаи пропуска, замены и наличия лишних букв в
распознаваемых словах. Для хранения совпадающих фрагментов слов используется только одна вершина
пирамиды-словаря, что позволяет определять общие фрагменты слов без проведения дополнительного поиска.
Введение
При автоматическом распознавании текстов и речи зачастую возникает проблема
соотнесения распознанного слова со словом из существующего словаря (далее – тер-
мином). Это позволяет повысить точность распознавания даже в случае неправиль-
ного или неоднозначного распознавания отдельных букв (фонем, визем). Для быстрого
поиска в словаре соответствующего термина применяются различные методы, осно-
ванные на специальной организации словарей – бинарные деревья, красно-чёрные
деревья, слоёные списки [1]. В случае если предполагается, что соответствие между
распознаваемым словом и словом из словаря может быть неполным (пропуск, замена,
наличие лишних букв), то используются метод расширения выборки, trie-деревья [2], [3],
метод n-грамм и др. Для того, чтобы учесть возможность отсутствия начальных и конеч-
ных букв в слове, словарь расширяют за счёт включения всех суффиксов и префиксов.
В работе предлагается метод организации словаря на основе использования
пирамиды, метод построения которой представлен в работах [4], [5]. Данный метод,
в отличие от существующих аналогов, позволяет без увеличения размера словаря
учитывать случаи пропуска, замены и наличия лишних букв в распознаваемых словах.
Линейная пирамида
В работах [4], [5] даны общие свойства пирамид и рассмотрены несколько их
частных случаев. В данной работе используется только один тип пирамид, наиболее
подходящий для организации словаря из терминов, которые представляют собой ко-
нечные последовательности символов алфавита. Данный тип пирамид получил назва-
ние линейных.
Линейной пирамидой на графе G называется граф P, имеющий следующие
свойства:
– каждая вершина пирамиды jiv , принадлежит определённому уровню i ;
Агарков А.В.
«Искусственный интеллект» 3’2009 162
4А
– уровни пирамиды упорядочены от нижнего (первого) до верхнего (последнего)
( Ni ,...,1 );
– каждой вершине jiv , пирамиды соответствует пара смежных вершин )( , jivp , при-
надлежащих предыдущему уровню (кроме вершин графа G, который рассматривается
как самый нижний уровень пирамиды P);
– каждая из вершин, принадлежащая )( , jivp , является родителем для вершины jiv , ,
которая, в свою очередь, является дочерней для вершин множества )( , jivp ;
– вершины одного уровня соединяются ребром только в том случае, если они имеют
общего родителя;
– вершины одного уровня jiv , и kiv , соединяются ребром только в том случае, если
общие родители пар вершин )( , jivp и )( ,kivp не совпадают;
– вершина пирамиды P, не имеющая дочерних вершин, называется верхушкой пи-
рамиды.
Подграф )( , jivp называется родительским для вершины jiv , .
Каждая вершина пирамиды имеет маркер, который зависит только от маркеров
родительских вершин и ребер, соединяющих родителей. То есть по маркеру верши-
ны можно определить маркеры её предков, и наоборот – по маркерам предков можно
определить маркер их потомка (потомков).
Каждой вершине пирамиды P соответствует подграф графа G который в случае
линейной пирамиды представляет собой цепь. Если маркеры двух вершин пирамиды
одного уровня совпадают, то подграфы, им соответствующие, изоморфны.
Пирамида образуется в результате построения, то есть начиная с основного графа
(нулевого уровня) проводится следующая процедура – граф, соответствующий одному
уровню, разбивается на подграфы, для каждого из которых в следующем уровне об-
разуется новая вершина. Эти новые вершины являются дочерними для вершин соот-
ветствующих подграфов предыдущего уровня, которые, в свою очередь, являются
родителями для нововозведенных вершин.
На рис. 1 представлен пример линейной пирамиды, построенной на графе, со-
стоящем из вершин a, b, c, d, который представляет собой цепь. Пунктирными линиями
обозначены уровни пирамиды. В данной пирамиде три уровня (нулевой уровень –
исходный граф). Если рассмотреть отдельную вершину 1,2v , принадлежащую второму
уровню, то для неё родителями являются вершины 1,1v и 2,1v , принадлежащие первому
уровню. Дочерней для данной вершины является 1,3v . Данная вершина имеет с 2,2v об-
щего родителя 2,1v , поэтому 1,2v и 2,2v соединены ребром. Подграф основного графа,
который соответствует 1,2v , образован вершинами a, b, c.
Вершина 1,3v не имеет дочерних вершин, поэтому является верхушкой данной
пирамиды, и ей соответствует весь основной граф. Она является потомком для всех
остальных вершин этой пирамиды, которые, в свою очередь, являются предками для
верхушки.
Таким образом, каждый уровень пирамиды представляет собой граф, каждой вер-
шине которого соответствует подграф предыдущего уровня. Вершины данного подграфа
соединяются рёбрами, если цепи, которые им соответствуют, различаются только па-
рой крайних вершин.
Организация словаря на основе применения метода построения...
«Штучний інтелект» 3’2009 163
4А
Рисунок 1 – Пример линейной пирамиды
Использование графа для представления слов и словаря
Каждое слово может быть представлено в виде графа, каждой вершине которого
соответствует отдельная буква. А дуги (ориентированные рёбра) определяют после-
довательность букв. Данный граф является цепью. Однако если в слове есть одинако-
вые буквы, то различным вершинам данного графа будет соответствовать одна буква.
Для того чтобы этого избежать, можно использовать граф, каждой вершине которого
соответствует одна буква и не существует буквы, которой бы соответствовало более
одной вершины. Дуги определяют последовательность букв в слове. При этом если в
слове есть одинаковые буквы, то в цепь, определяющую слово, входит цикл. Если в
слове подряд идут несколько одинаковых букв, то существует петля, инцидентная
соответствующей вершине.
Таким образом, всякий словарь может быть представлен в виде графа, каждой
вершине которого соответствует буква алфавита (причём не существует двух вер-
шин, которым бы соответствовала одна и та же буква), дуги, соединяющие вершины,
определяют последовательность букв в словах. Каждое слово из данного словаря оп-
ределяется цепью в данном графе. По сути, данный граф является мультиграфом.
Количество вершин в данном графе равно количеству букв в алфавите, а максималь-
ное количество рёбер – его квадрату.
Для того, чтобы обозначить цепи, соответствующие словам, используется линей-
ная пирамида.
Каждая вершина линейной пирамиды имеет ровно двух родителей, которые при-
надлежат одному уровню, являются смежными и, в свою очередь, имеют только одного
общего родителя. Подграфами разбиения для построения линейной пирамиды явля-
ются пары смежных вершин и инцидентная им дуга. Точнее сказать, каждому ребру
(и соответственно инцидентным данному ребру вершинам) соответствует подграф
разбиения и вершина более высокого уровня пирамиды. Это относится и к петлям.
Таким образом, вершинам данной пирамиды соответствуют слова из словаря и
их фрагменты. Если какое-то слово совпадает с фрагментом другого слова или какие-
либо фрагменты слов совпадают, то им соответствует одна вершина данной пирамиды.
Агарков А.В.
«Искусственный интеллект» 3’2009 164
4А
Множество дочерних вершин каждой вершины пирамиды делится на правое и
левое подмножества (считается, что буквы в слове следуют слева направо).
Построение пирамиды-словаря
Каждому слову соответствует цепь в графе. Построение соответствующего
участка пирамиды проводится в результате следующей процедуры – на цепи, кото-
рая соответствует начальному фрагменту слова, строится линейная пирамида, затем
к концу цепи добавляется ещё одна вершина, соответствующая следующей букве в
слове, и пирамида достраивается. Так продолжается до тех пор, пока не закончится
цепь – слово. В начале процедуры цепь инициализируется дугой и инцидентными ей
вершинами, которые соответствуют первым двум буквам слова.
То есть процедура построения участка линейной пирамиды для слова, которому
соответствует цепь ),...,( 1 nvvC , n – количество букв в слове, выглядит следующим
образом:
),( 21 vvCP – инициализация текущей цепи.
Построить линейную пирамиду )( PCLP на PC ;
Цикл от 2i до ni
{
),...,( 1 iiPN vvvCC ;
достроить пирамиду )( PCLP до пирамиды )( NCLP .
NP CC ;
}
Общий алгоритм построения пирамиды-словаря приведен ниже.
Обозначим },...,,{ 21 NAaaaA – алфавит – множество букв, NA – количество букв;
),...,,(
21 wnwww aaaw слово, последовательность букв из алфавита ,A причём
буквы могут повторяться, wn – количество букв в слове w ; ),...,,{ 21 DNwwwD –
словарь, множество слов, DN – количество слов в словаре; ),( EVG – граф алфавита.
Свойства графа алфавита ),( EVG :
– AaVvfvAaffvvvV iiiiNA )(,)(::},...,{ 1
21 , то есть каждой букве из
алфавита A соответствует одна вершина графа G ;
– })(,)(,),(:,:),({
11 jwiwwwji vafvafwaawnkDwvvdE
kkkk
, ),( ji vvd – ду-
га, инцидентная вершинам iv и jv , то есть любым двум соседним буквам любого
слова, принадлежащего словарю ,D соответствует дуга графа G;
– если ),(:),( jijiji vvdvvvvdd – петля.
Обозначим ),( PP EVP – линейная пирамида-словарь. Свойства ),( PP EVP :
– PG ;
–
P
j
PP
i
PP
j
P
i
P
PP
i
PP
i
PPPP
j
PP
i
PP
vevRvevLvvde
родительправыйvRpvродительлевыйvLpv
EeVvVvVVv
)(,)(),(
,)(,)(
:,,\
Организация словаря на основе применения метода построения...
«Штучний інтелект» 3’2009 165
4А
– )}(:{)( P
i
PPP
i
PPP vRpvVvvLsVv ( )( PvLs – множество левых дочерних
вершин Pv );
– )}(:{)( P
i
PPP
i
PPP vLpvVvvRsVv ( )( PvRs – множество левых дочерних
вершин Pv );
– ))(),((:\:)( PPPPPPPPP vRpvLpdeVVvEeveSe ;
– )( Pvmrk – маркер вершины .Pv
Обозначим )( P
w vM – множество слов, которым принадлежит фрагмент, соот-
ветствующий вершине .Pv
Алгоритм построения пирамиды-словаря основан на использовании рекурсивной
функции для создания новых элементов на основе данной дуги. Обозначим данную
функцию ARC_PROC( d , w ). Алгоритм функции ARC_PROC( d , w ) имеет следую-
щий вид:
ARC_PROC( d , w )
{
P
Lv – текущая левая вершина;
P
Rv – текущая правая вершина;
pd – текущая дуга;
если )(dSev P то
{
создать вершину )(dSev P ;
PP
R vv ;
PvdvLRsdvLRs ))(())(( ;
PvdvRLsdvRLs ))(())(( ;
}{)()( wvMvM P
w
P
w ;
}
иначе )(dSev P
R ;
0))(( dvLmrk ;
)())(( windxdvRmrk ;
)()( windxvmrk P
R ;
если )()(:))(( windxvmrkdvLLsv P
i
P
i то
{
P
i
P
L vv ;
если ),( P
R
P
L vvdd то
{
создать ),( P
R
P
L vvdd ;
dd p ;
}
иначе ),( P
R
P
Lp vvdd ;
ARC_PROC( pd , w )
}
}.
Агарков А.В.
«Искусственный интеллект» 3’2009 166
4А
Алгоритм построения пирамиды-словаря имеет следующий вид:
),( EVG ;
for ( DNii ;1 )
{
iw – i -ое слово из словаря D ;
for ( iwnjj ;1 )
{
если ))(),((
1
i
j
i
j ww afafdd
то ))(),((
1
i
j
i
j wwp afafdd
;
иначе
{
создать дугу ))(),((
1
i
j
i
j ww afafdd
;
)),((
1
i
j
i
j wwp aafdd
;
}
ARC_PROC( pd , iw );
}
}
На рис. 2 представлен фрагмент пирамиды-словаря, соответствующий слову «ма-
ма». Для наглядности вершины пирамиды маркированы фрагментами термина, которым
они соответствуют. Пунктирной линией соединены вершина и дуга, которая являет-
ся основой для соответствующего подграфа разбиения.
Рисунок 2 – Пример фрагмента пирамиды-словаря, соответствующий слову «мама»
Поиск по словарю на основе построения
пирамиды поиска
В качестве входных данных выступает последовательность множеств ,( 1LS
),...,2 NLLL , каждое из которых состоит из вариантов букв – },...,,{ 21
i
nl
ii
i i
aaaL . Не-
обходимо из каждого множества выбрать те буквы, последовательность которых сос-
тавляла бы слова из словаря и(или) их фрагменты.
То есть необходимо найти такие последовательности ),...,,( 1
10
i
i
in
ii
nk
m
k
m
k
m
S
i aaaw , где
NLnkk i )(,1 , которые бы соответствовали словам из словаря и их фрагментам.
Организация словаря на основе применения метода построения...
«Штучний інтелект» 3’2009 167
4А
После чего выполняется поиск наиболее подходящей условию задачи последователь-
ности S
iw , что является отдельной задачей и здесь рассматриваться не будет.
Поиск множества }{ S
iw осуществляется с помощью построения пирамиды поис-
ка по образу и подобию пирамиды-словаря.
Обозначим ),( SSS EVP – пирамиду поиска. Свойства ),( SSS EVP :
– PSPPSSSS vvsvVvVvVvsv )(::)( ;
– PSPPSSSS eeseEeEeEese )(::)( ;
– })(:{ GvsvVvV SSSS
G ;
–
\ , , ;
( ) левый родитель, ( ) правыйродитель,
( , ) ( ) , ( ) ;
S S S S S S S S S
G i j
S S S S
i i
S S S S S S S
i j i j
v V V v V v V e E
v Lp v v Rp v
e d v v vL e v vR e v
;
– )}(:{)( S
i
SSS
i
SSS vLpvVvvRsVv ( )( SvRs – множество левых дочерних
вершин Sv );
– )}(:{)( S
i
SSS
i
SSS vRpvVvvLsVv ( )( SvLs – множество левых дочерних
вершин Sv );
– ))(),((:\:)( SSSSSSSSS vRpvLpdeVVvEeveSe ;
–
PPPP
r
PP
l
SPS
r
P
r
S
l
P
l
SP
SSSS
r
SS
l
SS
r
S
l
S
veSevRpvvLpveseevsvvvsvvvsvv
veSevRpvvLpvevvv
)(),(),(:)(),(),(),(
)(),(),(:,,,
;
–
, , : ( ), ( ),
( ), ( ), ( ): ( ), ( ).
S S S S S S S
l r l r
P S P S P S P P P P
l l r r l r
v v v v Ls v v Rs v
v sv v v sv v v sv v v Ls v v Rs v
Каждой вершине Sv пирамиды SP соответствует цепь вершин, принадлежащих
множеству S
GV ):,...,()(\
1
S
G
S
m
S
m
S
m
S
i
S
G
SS
i VvvvvCVVv i
j
i
in
i , причём последователь-
ность букв ))(()),...,(((
1
S
m
S
m i
in
i vsvfvsvf соответствует слову из словаря и(или) фрагменту
слова, которое соответствует вершине VVvsv PS
i \)( .
Алгоритм построения пирамиды поиска основан на использовании рекурсивной
функции SARC_PROC( d ), которая на основе данной дуги создаёт новые элементы
пирамиды. Алгоритм SARC_PROC( d ) имеет следующий вид:
SARC_PROC( d )
{
P
Lv – текущая левая вершина;
P
Rv – текущая правая вершина;
pd – текущая дуга;
если )(dSev P то
{
создать вершину )(dSev P ;
PP
R vv ;
PvdvLRsdvLRs ))(())(( ;
Агарков А.В.
«Искусственный интеллект» 3’2009 168
4А
PvdvRLsdvRLs ))(())(( ;
}
иначе )(dSev P
R ;
если PP
R
P
i
P
i EvsvvsvddvLLsv ))(),((:))(( то
{
P
i
P
L vv ;
если ),( P
R
P
L vvdd то
{
создать ),( P
R
P
L vvdd ;
dd p ;
}
иначе ),( P
R
P
Lp vvdd ;
SARC_PROC( pd )
}
}
В алгоритме построения пирамиды поиска используются следующие вспомога-
тельные множества и переменные – 21 ,GG – вспомогательные множества вершин
графа S
GV ( }{ i
ki vG ), 21 , nGnG – количество элементов во множествах 21 ,GG . Алго-
ритм построения пирамиды поиска имеет следующий вид:
1G ;
2G
for ( NLkk ;1 )
{
for ( knLii ;1 )
{
создать вершину k
i
SSS
G
S avsvfVVv ))((: ;
}{22
SvGG ;
}
for ( 1;1 nGii )
{
for ( 2;1 nGjj )
{
если Gvsvvsvde ji
P ))(),(( 21 то
{
создать дугу ),( 21
jip vvdd ;
SARC_PROC( pd );
}
}
}
21 GG ;
2G ;
}
Организация словаря на основе применения метода построения...
«Штучний інтелект» 3’2009 169
4А
Каждой вершине пирамиды SP , не имеющей дочерних вершин, будет соответ-
ствовать полное слово из словаря или(и) фрагмент слова из словаря. Если в искомом
слове буквы пропущены или заменены на другие – необходимо проанализировать все
найденные фрагменты на предмет возможности составления из них слов с пропуска-
ми букв, что алгоритмически труда не представляет.
Заключение
Предложенный способ организации словаря в виде пирамиды позволяет исполь-
зовать для хранения совпадающих фрагментов различных слов только одну вершину.
Это позволяет определять общие фрагменты слов из словаря без проведения дополни-
тельного поиска, а также кодировать их номером соответствующей вершины. Данный
метод организации словаря в совокупности с поиском, основанным на методе построе-
ния пирамиды, позволяет учитывать случаи отсутствующих, неправильных и лишних
букв в распознаваемых словах. Также данный подход позволяет рассматривать раз-
личные варианты слов в случае неоднозначного введения отдельных букв.
Литература
1. Озкарахан Э. Машины баз данных и управление базами данных / Озкарахан Э. – М. : Мир, 1989.
2. Shang H. Tries for Approximate String Matching / H. Shang, T.H. Merrett // IEEE Trans. on Knowledge
and Data Engineering – special issue on Digital Libraries / ed. Nabil R. Adam. – 1996. – P. 540-547.
3. Merrett T.H. Database Structures, Based on Tries, for Text, Spatial, and General Data / T.H. Merrett,
H. Shang, X. Zhao // International Symposium on Cooperative Database Systems for Advanced Applica-
tions (Kyoto, Dec. 5-7, 1996). – Kyoto, 1996. – P. 316-324.
4. Агарков А.В. Метод сравнения двух графов за полиномиальное время / А.В. Агарков // Искусст-
венный интеллект. – 2003. – № 4. – С. 172-184.
5. Агарков А.В. Поиск изоморфных пересечений двух графов за полиномиальное время / А.В. Агар-
ков // Искусственный интеллект. – 2007. – № 2. – С. 62-74.
А.В. Агарков
Організація словника на основі застосування методу побудови додаткового графа-піраміди
Пропонується метод організації словника на основі використання графa-піраміди, що дозволяє без
збільшення розміру словника враховувати випадки пропуску, заміни і наявності зайвих букв у словах,
що розпізнаються. Для збереження збіжних фрагментів слів використовується тільки одна вершина
піраміди-словника, що дозволяє визначати загальні фрагменти слів без проведення додаткового пошуку.
A.V. Agarkov
Dictionary Construction on the Basis of Application of Additional Graph-Pyramid Building Method
It is proposed the dictionary construction method on the basis of the graph-pyramid using which allows to
consider without increase in the size of the dictionary cases omission, replacement and presence of superfluous
letters in recognized words. For storage of conterminous fragments of words only one pyramid-dictionary
vertex is used which allows to define the common word fragments without carrying out of additional search.
Статья поступила в редакцию 15.06.2009.
|