Abstract:

Հայտնի է մոտակա հարևանների փնտրման հաշ-կոդավորման տիպի Էլիասի ալգորիթմը: Ալգորիթմում կարող են կիրառվել սխալ ուղղող կոդերը՝ հաշ-կոդավորման սխեմա կառուցելու համար: Այդ սխեմաները տվյալները ներկայացնում են ցուցակների տեսքով: Կամայական ցուցակ իրենից ներկայացնում է որևէ գնդի ենթաբազմություն (Հեմինգի տարածությունում), որի կենտրոնը նշված սխալ ուղղող կոդի կոդային բառ է: Ալգորիթմը դիտարկվում է կատարյալ կոդերի համար, հետևաբար կոդային բառերի շուրջ համապատասխան շառավղով գնդերը չեն հատվում, հետևաբար նշված ցուցակները նույնպես չեն հատվի: Քանի որ կատարյալ կոդեր գոյություն ունեն պարամետրերի սպեցիֆիկ արժեքների համար, ալգորիթմը դիտարկվել է կատարյալ կոդերի այլ ընդհանրացումներով ստացվող հաշ-կոդավորման սխեմաների համար, որտեղ, սակայն, միևնույն էլեմենտը կարող է պատկանել մի քանի ցուցակների: Նշված դեպքերի համար ստացվել են ալգորիթ միբարդության բանաձևերը՝ կախված կոդի հարակից դասերի կշռային կառուցվածքներից:
; Известен алгоритм поиска ближайших соседей (алгоритм Элиаса). Алгоритм использует коды, исправляющие ошибки для построения схем хеш-кодирования. Эти схемы представляют данные в форме списков. Каждый список содержится в некоторой сфере, центром которого является некоторое кодовое слово. Алгоритм рассматривается для случаев совершенных кодов, поэтому указанные сферы и, следовательно, списки не пересекаются. Поскольку совершенные коды существуют для очень специфичного набора параметров, алгоритм рассматривается для некоторых обобщений совершенных кодов, когда одна и та же точка данных может содержаться в разных списках. Для указанных случаев получены формулы временной сложности алгоритма с использованием весовой структуры смежных классов кодов.

Identifier:

oai:noad.sci.am:136049

Affiliation:

Ինֆորմատիկայի և ավտոմատացման պրոբլեմների ինստիտուտ ; Институт проблем информатики и автоматизации