Страница 1

Разстояние на Хеминг между две последователности еднаква дължинасъответства на броя на позициите, заети от несъответстващи елементи. В случай на поредици с различни дължини, разстоянието на Хеминг се дефинира като минималния брой позиции, заети от несъвпадащи елементи при.

Разстоянието на Хаминг d (u, v) между две думи u и v с еднаква дължина е равно на броя на несъвпадащите битове на тези думи. Използва се в теорията на блоковите кодове (V.

Използвайки метричните свойства на разстоянието на Хаминг, директно се потвърждава, че / l е метрика на Xt, но не е метрика на множеството от смесени периодични последователности.

Тази функция за близост е еквивалентна на разстоянието на Хаминг.

Метриката p в алгоритъма KLOP се дава от разстоянието на Хаминг.

Ако процедурата за търсене може да намери позиция, където разстоянието на Хаминг е нула, проблемът ще бъде решен.

Сравнението на размити подмножества B и B3, степени на размита и разстояние на Хаминг показва, че разглежданите размити подмножества са различни. Ако обаче за изчислена стойност се вземе елементът m2 G Uz, чиято степен на принадлежност към полученото размито подмножество е максимална, тогава използването на изчисленото по този начин размито съотношение R може да бъде оправдано. Наред с факта, че с този подход е възможно да се опише нелинейността на връзката между максимална температуравъв втората зона на реактора и скоростта на потока на полиетиленовата стопилка, този метод не отчита нестационарността на производствения процес на LDPE, което е свързано с промяна в характеристиките на технологичния процес.

Преносната функция на този код показва, че има само един път с разстояние на Хаминг d - от път на всички нули, който се слива с път на всички нули в даден възел. От диаграмата на състоянието, показана на фиг. 6, или диаграмата на пергола, показана на фиг. 5, можете да видите, че пътят с d6 е acbe. Отново от диаграмата на състоянията или решетката можем да видим, че тези пътища са acdbe и acbcbe. Третият член в (8.1.2) показва, че има четири пътя с разстояние d 0 и т.н. Поради това, Функция на предаванени дава свойствата на разстоянието на конволюционния код.

Този резултат е в съответствие с наблюдението, че пътят на изцяло нула (/ 0) има разстояние на Хеминг d3 от получената последователност, докато пътят c / 1 има разстояние на Хеминг от d5 от получената пътека. По този начин разстоянието на Хаминг е еквивалентен показател за декодиране на трудно решение.

Този резултат е в съответствие с наблюдението, че пътят на изцяло нула (/ 0) има разстояние на Хеминг d3 от получената последователност, докато пътят c / 1 има разстояние на Хеминг от d5 от получената пътека. По този начин разстоянието на Хаминг е еквивалентен показател за декодиране на трудно решение.

В книгата на Стефан Цвайг "Звездните часове на човечеството" има чудесен разказ "Геният от една нощ" за френския офицер Руж дьо Лил, който в разгара на вдъхновението си написва прочутата "Марсилиза" през една нощ . Това беше през 1792 г. в революционна Марсилия. Песента се разпространи във Франция в рамките на няколко дни, бързо спечели огромна популярност в целия свят и впоследствие се превърна в национален химн на Френската република. Историята е запазила името Руж в паметта на потомството благодарение на тази единствена песен.

По аналогия с Ричард Хаминг може да се нарече „гений на една идея“. Той го формулира през 1950 г. в своя единствен научна статияпосветен на кодове за коригиране на грешки. Статията съдържаше конструкцията на блоков код, който коригира единични грешки, възникнали по време на предаването на съобщение.

Ричард Хаминг постоянно водеше активно Научно изследване, обаче, единствената му работа в областта на теорията на информацията става известна, съставляваща незначителен процент от научната му работа. Тази статия бързо придоби световна слава и му донесе заслужена слава.

Точно както откритията на Фарадей и Максуел бяха последвани от многобройни изобретения в областта на телекомуникациите, които промениха живота ни, така и след създаването на теорията на информацията от Клод Шанън и Владимир Котельников на теорията за потенциалната устойчивост на шум, се откриха нови възможности за развитие на телекомуникациите. Един от критични секцииТеорията на информацията е теория на кодирането, чиито основи са положени от Хаминг.

Шанън установи, че информацията може да се предава по комуникационен канал без грешка, ако скоростта на предаване не я надвишава честотна лента... Доказателството на Шанън обаче беше неконструктивно. По-късни проучвания от него и друг американски учен С. О. Райс показаха, че почти всеки произволно избран код може да постигне теоретична границаустойчивост на шум при получаване на съобщения. Такъв код обаче имаше висока сложност при декодиране: броят на операциите, необходими за декодиране на получената кодова дума, нараства експоненциално с нейната дължина.

Хаминг беше първият, който предложи конструктивен метод за конструиране на кодове с излишък и просто декодиране. Неговата работа предопредели посоката на по-голямата част от работата в тази област, която последва.

В негова чест Институтът по електротехника и електроника учреди медал, който се присъжда на учени, които имат значителен принос в теорията на информацията.

Кодове, способни да коригират грешки (в комуникационните канали в цифров изчислителни машинии др.) в обработката на сигнали са предложени от Хаминг преди 1948 г., когато е публикувана известната статия на Шанън "Математическа теория на комуникацията", която положи солидна основа на теорията в тази област.

В тази статия Шанън, позовавайки се на изследване, извършено през 1947 г. от неговия колега от Бел Ричард Хаминг, описва като пример прост код с дължина 7, който коригира всички единични грешки. Публикуване на същото оригинален материалХаминг е арестуван по патентни причини до април 1950 г. Трябва да се отбележи, че примерът за код за коригиране на грешки, даден в гореспоменатата статия от Шанън, инициира изследването на друг американски учен, M. E. Golay. Голай, независимо от Хаминг, открива кодове за коригиране на единични грешки. През 1949 г. (т.е. преди Хаминг) той публикува кратка бележка (само половин страница) за резултатите си в Proceedings IEEE. В тази бележка той разглежда не само двоични кодовено и кодове общ изглед, комбинации от които принадлежат на крайно поле (математически набор от елементи с определени операции събиране, изваждане, деление и умножение) с pn елементи (p е просто, а n е цяло число).

Трябва да се отбележи, че редица фундаментални идеи на теорията на комуникацията са били известни като конкретни математически резултати още преди учените да започнат да ги прилагат, разрешаване на проблемипредаване на съобщения по комуникационни канали. В книгата си "Теория на алгебричното кодиране" изтъкнат американски експерт в областта на теорията на кодирането Е. Берлекамп направи много интересна забележка. Той отбеляза, че изграждането на кодовете на Хаминг е описано в различен контекст през 1942 г. от известния американски математик Р.А. Между другото, теоремата на V.A.Kotelnikov, показваща възможността за представяне аналогови сигнали v цифрова форма, също е открит като един от конкретните математически резултати от теорията на интерполацията на функция в началото на ХХ век от английските математици E. T. и J. M. Whitker. Трябва да се подчертае, че нито Фишер, нито споменатите по-горе английски учени свързват своите резултати с най-важните за съвременен святпроблеми с предаването на информация по комуникационните канали.

Волфганг Гьоте е казал: „Не е достатъчно само да придобиеш знание; трябва да намериш приложение за него. Не е достатъчно само да желаеш; трябва да направя". За теорията и технологията ... връзките между теоремата на Котельников и кодовете на Хаминг са от изключително значение, тъй като именно благодарение на тях се появи ясна перспектива за създаване цифрови системи, които в края на ХХ век направиха революция в телекомуникациите и затова с право се наричат ​​имената на тези учени.

Превръщайки се в катализатор, който ускорява развитието на теорията на кодирането, статията на Хаминг привлича вниманието на научната общност. Във всички учебници този клас кодове се нарича кодове на Хаминг и представянето на теорията на кодирането започва с описание на тяхната конструкция. Очевидно все пак би било по-справедливо да наречем тези кодове Hamming - Golay codes, като се има предвид, че Golay дойде до същите идеи като Hamming независимо и ги публикува по-рано. Фактът, че статията му не привлече вниманието, което заслужава, най-вероятно е случайно.

В сравнение с теорията на Шанън, кодовете на Хаминг бяха разочароващо слаби. Въпреки това, предложените от Хаминг редовни методи за конструиране на кодове за коригиране на грешки бяха от основно значение. Те демонстрираха пред инженерите практическа възможностдостигане на тези граници, които бяха посочени от законите на теорията на информацията. Тези кодове бяха открити практическа употребадокато създавате компютърни системи... Хартията на Хаминг също доведе до решение на проблема с по-плътното опаковане за крайни полета. Той въведе в научна употреба най-важните концепции на теорията на кодирането - разстоянието на Хаминг между кодовите комбинации във векторно пространство, дефинирано за двоични кодове като броя на позициите на тези комбинации с различни символи, и границите на Хаминг за коригиращата способност на блоковите коригиращи кодове. Границата на Хаминг за двоични кодове се изчислява по следната формула:

В този израз, броят на грешките e може да бъде коригиран чрез корекционен блоков код с дължина N с M кодови комбинации (CjN е биномен коефициент).

Играта на Хаминг ключова роляв последващото развитие на теорията на кодирането и стимулира задълбочени изследвания, проведени през следващите години. През 1956 г. Дейвид Слепян е първият, който излага теорията на кодовете за проверка на четността върху сериозна математическа основа... Голяма промяна в областта на теорията на кодирането настъпва, когато френският учен А. Хокингам (1959) и американците R.K.Bowes и D.K.Roy-Chowdhury (1960) откриват голям клас кодове (BCH кодове), които коригират множество грешки. Американските изследователи I.S.Reed и G. Solomon (1960) откриха клас кодове за недвоични канали, свързани с BCH кодове.

През 1980 г. Хаминг написва брилянтен учебник "Теория на кодирането и теория на информацията", който е преведен на руски през 1983 г. Тази книга, както и другите му произведения, се отличава с оригиналност на поставянето на въпроси, популярност на представянето, дълбоко разбиране на практическите проблеми, коректност и разумна степен на строгост на математическата интерпретация на повдигнатите въпроси. Представянето на материала е структурирано по такъв начин, че читателят интуитивно да разбере защо тази или онази теорема е вярна.

Обработка на изображение

• Урок

В тази статия ще говорим за алгоритъма HEngine и реализацията на решението на проблема за изчисляване на разстоянието на Хаминг на големи обемиданни.

Въведение

Разстоянието на Хеминг е броят на различните позиции за редове с еднаква дължина. Например HD ( 1 00 , 0 01 ) = 2.

Проблемът за изчисляване на разстоянието на Хаминг за първи път е поставен от Мински и Паперт през 1969 г., където задачата е да се намерят всички редове от базата данни, които са в рамките на дадено разстояние на Хаминг до исканото.

Тази задача е необичайно проста, но търсенето й ефективно решениевсе още остава на дневен ред.

Разстоянието на Хеминг вече е доста широко използвано за различни задачикато намиране на близки дубликати, разпознаване на шаблони, класификация на документи, корекция на грешки, откриване на вируси и др.

Например Манку и колегите му предложиха решение на проблема с групирането на дубликати при индексиране на уеб документи въз основа на изчисляване на разстоянието на Хаминг.
Милър и приятели също така предложиха концепцията за търсене на песни по даден аудио фрагмент.
Подобни решения са използвани за задачата за търсене на изображения и разпознаване на ретината и др.

Описание на проблема

Има база данни с двоични низове T, размер нкъдето е дължината на всеки ред м... Искан низ аи необходимото разстояние на Хеминг к.

Задачата се свежда до намиране на всички линии, които са в рамките на разстоянието к.

В първоначалната концепция на алгоритъма се разглеждат два варианта на задачата: статичен и динамичен.

При статична задача разстоянието k е предварително определено.
- При динамично, напротив, необходимото разстояние не се знае предварително.

Тази статия описва решението само на статичен проблем.

Описание на алгоритъма HEngine за статичен проблем

Тази реализация се фокусира върху намирането на низове вътре к <= 10.

Има три решения на статичния проблем: линейно сканиране, разширяване на заявката и разширяване на таблицата.

В този случай под чрез разширяване на заявкатаИмам предвид генериране на всички възможни варианти на низове, които се вписват в определеното разстояние за оригиналния низ.
Разширяване на основатаданни предполага създаването на много копия на тази база данни, където или се генерират всички възможни варианти, които отговарят на изискваните изисквания за разстояние, или данните се обработват по някакъв друг начин (повече за това малко по-късно).

HEngine използва комбинация от тези три техники за ефективно балансиране на паметта и времето за изпълнение.

Малко теория

Алгоритъмът се основава на малка теорема, която гласи както следва:

Ако за два реда аи бразстояние HD ( а, б) <= к, тогава, ако разделите линиите аи бвърху поднизове по метод rcutизползвайки фактор на сегментиране
r >= ⌊к/2⌋ + 1
сигурно поне ще има q= r − ⌊к/ 2⌋ поднизове, когато разстоянието им не надвишава едно, HD ( ааз, би)<= 1.

Извличане на поднизове от основния низ с помощта на метода rcutсе извършва според следните принципи:
Посочената стойност фактор на сегментиранекоето удовлетворява условието
r >= ⌊к/2⌋ + 1

Дължината на първия r − (ммод r) поднизовете ще имат дължина ⌊ м / r⌋ и последното ммод rподнизове ⌈ м/r⌉. Където ме дължината на низа, ⌊ закръгля до най-близкото дъно, а ⌉ закръгля до най-близкия връх.

Сега същото нещо, само като пример:

Дадени са два двоични низа с дължина м= 8 бита: A = 11110000 и B = 11010001, разстоянието между тях к = 2.
Избор на фактор за сегментиране r= 2/2 + 1 = 2, т.е. общо ще има 2 поднизове с дължина м/r= 4 бита.

A1 = 1111, a2 = 0000
b1 = 1101, b2 = 0001

Ако сега изчислим разстоянието между съответните поднизове, тогава най-малко ( q= 2 - 2/2 = 1) един подниз ще съвпада или разстоянието им няма да надвишава едно.

Какво виждаме:
HD (a1, b1) = HD (1111, 1101) = 1
и
HD (a2, b2) = HD (0000, 0001) = 1

Поднизовете на основния низ са именувани подписи.
Сигнатури или поднизове a1 и b1 (a2 и b2, a3 и b3 ..., a rи б r) са наречени съвместимиедин с друг и ако броят им на различни битове не е повече от един, тогава тези подписи се наричат съвпадащи.

И основната идея на алгоритъма HEngine е да подготви базата данни за намиране на съвпадащи подписи и след това да избере онези редове, които са в рамките на необходимото разстояние на Хаминг.

Предварителна обработка на база данни

Вече знаем, че ако правилно разделим низа на поднизове, тогава поне един подниз ще съвпада със съответния подниз или броят на различните битове няма да надвишава един (сигнатурите ще съвпадат).

Това означава, че не е необходимо да извършваме пълно изброяване на всички редове от базата данни, а първо трябва да намерим онези подписи, които съвпадат, т.е. поднизовете ще се различават най-много с един.

Но как търсите поднизове?

Методът за двоично търсене трябва да свърши доста добра работа за това. Но това изисква списъкът с низове да бъде сортиран. Но получаваме няколко поднизове от един низ. За да извършите двоично търсене в списък с поднизове, всеки такъв списък трябва да бъде сортиран предварително.
Следователно тук се предлага методът за разширяване на базата данни, тоест създаване на няколко таблици, всяка за свой подниз или подпис. (Такава таблица се нарича таблица с подписи... И набор от такива маси - комплект за подписи).

Оригиналната версия на алгоритъма също така описва пермутацията на поднизове по такъв начин, че избраните поднизове са на първо място. Това се прави повече за улесняване на внедряването и за по-нататъшни оптимизации на алгоритъма:

Има низ A, който е разделен на 3 поднизове, a1, a2, a3, пълният списък с пермутации ще бъде съответно:
а1, а2, а3
а2, а1, а3
а3, а1, а2

След това тези таблици с подписи се сортират.

Изпълнение на търсене

На този етап, след предварителна обработка на базата данни, имаме няколко копия от сортираните таблици, всяка за своя подниз.

Очевидно, ако искаме първо да намерим поднизове, трябва да получим подписи от искания низ по същия начин, който беше използван за създаване на таблиците с подписи.

Знаем също, че необходимите поднизове се различават най-много с един елемент. И за да ги намерите, трябва да използвате метода за разширяване на заявката.

С други думи, изисква се избраният подниз да генерира всички комбинации, включително самия този подниз, в който разликата ще бъде най-много един елемент. Броят на такива комбинации ще бъде равен на дължината на подниз + 1.

Такива действия трябва да се извършват за всички поднизове и за всички таблици.

И в самия край ще трябва да филтрирате онези линии, които не се вписват в определената граница на разстоянието на Хаминг. Тези. извършете линейно търсене през намерените линии и оставете само онези линии, които отговарят на HD ( а, б) <= к.

Филтър за цъфтеж

Авторите предлагат използването на филтъра Bloom за намаляване на броя на двоичните търсения.
Филтърът Bloom може бързо да определи дали даден подниз е в таблица с малък процент фалшиви положителни резултати. Което е по-бързо от хеш таблица.

Ако преди двоично търсене на подниз в таблица филтърът върне, че този подниз не е в тази таблица, тогава няма смисъл от търсене.

Съответно трябва да създадете един филтър за всяка таблица с подписи.

Сега същото нещо, само като пример

Има база данни с двоични низове с дължина 8 бита:
11111111
10000001
00111110

Задачата е да се намерят всички редове, в които броят на различните битове не надвишава 2 до целевата линия 10111111.
Означава необходимото разстояние к = 2.

1. Изберете коефициента на сегментиране.
Въз основа на формулата избираме коефициента на сегментиране r= 2 и така ще има два подниза от един низ общо.

2. Създаваме набор от подписи.
Тъй като броят на поднизовете е 2, трябва да бъдат създадени само 2 таблици:
Т1 и Т2

3. Записваме поднизовете в съответните таблици, като запазваме връзката към източника.

T1 T2
1111 1111 => 11111111
1000 0001 => 10000001
0011 1110 => 00111110

4. Сортиране на таблици. Всеки поотделно.
T1
0011 => 00111110
1000 => 10000001
1111 => 11111111

Т2
0001 => 10000001
1110 => 00111110
1111=> 11111111

По този Предварителна обработкаприключи. И започваме да търсим.

1. Вземете подписите на искания низ.
Низът за търсене 10111110 е разделен на подписи. Оказва се съответно 1011 и 1100, първият за първата маса, а вторият за втората.

2. Ние генерираме всички комбинации, които се различават с едно.
Броят на опциите ще бъде 5.

2.1 За първия подниз 1011:
1011
0 011
11 11
100 1
1010

2.2 За втория подниз 1100:
1100
0 100
10 00
111 0
1101

3. Двоично търсене.

3.1 За всички генерирани варианти на първия подниз 1011, ние извършваме двоично търсене в първата таблица за пълно съвпадение.

1011
0011 == 0011 => 00111110
1111 == 1111 => 11111111
1001
1010

Намерени са две поднизове.

3.2 Сега, за всички варианти на втория подниз 1100, ние извършваме двоично търсене във втората таблица.

1100
0100
1000
1110 == 1110 => 00111110
1101

Намерен е един подниз.

4. Комбиниране на резултатите в един списък:
00111110
11111111

5. Проверете линейно за съответствие и филтрирайте неподходящите по условие<= 2:

HD (10111110, 00111110) = 1
HD (10111110, 11111111) = 2

И двете линии отговарят на условието за разлика на не повече от два елемента.

Въпреки че на този етап се извършва линейно търсене, се очаква списъкът с кандидат низове изобщо да не е голям.
При условия, когато броят на кандидатите ще бъде голям, се предлага да се използва рекурсивният вариант на HEngine.

Ясно е

Фигура 1 показва пример за алгоритъм за търсене.
За дължина на низа от 64 и граница на разстояние 4, коефициентът на сегментиране е 3, така че има само 3 поднизове на низ.
Където T1, T2 и T3 са таблици с подписи, съдържащи само поднизове B1, B2, B3, 21, 21 и 22 бита.

Исканият низ се разделя на поднизове. След това се генерира диапазон на подписите за съответните поднизове. За първия и втория подпис броят на комбинациите ще бъде 22. А последният подпис дава 23 опции. И накрая се прави двоично търсене.

Фигура 1. Опростена версия на обработка на заявки за таблица с подписи.

резултати

Сложността на такъв алгоритъм в средния случай О(П* (дневник н+ 1)), където не общият брой редове в базата данни, log н+ 1 двоично търсене и П- броят на двоичните търсения: в нашия случай се счита за броя на комбинациите на таблица, умножен по броя на таблиците: П = (64 / r + 1) * r

В екстремни случаи сложността може да надхвърли линейната.

Отбелязва се, че този подход използва 4,65 по-малко памет и е с 16% по-бърз от предишната работа, описана в. И това е най-бързият известен начин за намиране на всички линии в рамките на даден лимит.

Изпълнение

Всичко това, разбира се, е примамливо, но докато не го докоснете, е трудно да се оцени мащаба.
Създаден е прототип на HEngine и е тестван върху наличните реални данни.

Тества $ ./съвпада с 7 данни / db / table.txt данни / заявка / face2.txt Четенето на набора от данни ........ готово. 752420 db хешове и 343 хешове на заявки. Изграждане със 7 обвързано разстояние на Хеминг ....... готово. Време за изграждане: 12,964 секунди Търсене на съвпадения в HEngine ..... са намерени общо 100 съвпадения. Време на заявка за Hengine: 0.1 секунди Търсене на линейни съвпадения ..... са намерени общо 100 съвпадения. Линейно време за заявка: 6,828 секунди

Резултатите бяха обнадеждаващи, тъй като търсенето на 343 хеша от базата данни в 752420 отнема ~ 0,1 секунди, което е 60 пъти по-бързо от линейно търсене.

Изглежда, че човек може да спре до тук. Но наистина исках да се опитам да го използвам по някакъв начин в реален проект.

От PHP е достатъчно да извикате:
$ list = file_get_contents ("http: //fcgi.local/?". $ хешове);
Което връща резултата за ~ 0,5 секунди. Когато линейното търсене отнема 9 секунди, а чрез заявки към MySQL най-малко 20 секунди.

Благодаря на всички, които го направиха.

Връзки

М. Мински и С. Паперт. Персептрони. MIT Press, Кеймбридж, Масачузетс, 1969.
G. S. Manku, A. Jain и A. D. Sarma. Откриване на почти дубликати за обхождане в мрежата. В Proc. 16-ти WWW, май 2007 г.
M. L. Miller, M. A. Rodriguez и I. J. Cox. Аудио пръстови отпечатъци: Търсене на най-близкия съсед във високомерно двоично пространство. В MMSP, 2002г.
M. L. Miller, M. A. Rodriguez и I. J. Cox. Аудио пръстови отпечатъци: търсене на най-близкия съсед във високомерни двоични пространства. Journal of VLSI Signal Processing, Springer, 41 (3): 285-291, 2005.
J. Landr'e и F. Truchetet. Извличане на изображение с двоично разстояние на Хеминг. В Proc. 2-ри VISAPP, 2007 г.
H. Yang и Y. Wang. Метод за разпознаване на лица, базиран на LBP, с ограничение на разстоянието на Хеминг. В Proc. Четвъртият ICIG, 2007 г.
Б. Блум. Компромиси пространство/време в хеш кодирането с допустими грешки. Съобщения на ACM, 13 (7): 422-426, 1970.
Алекс X. Лиу, Ке Шен, Ерик Торнг. Обработка на широкомащабна заявка на Хеминг от разстояние. Конференция на ICDE, стр. 553 - 564, 2011 г.
github.com/valbok/HEngine Моят HEngine C ++ Внедряване Добавяне на етикети

В тази статия ще се съсредоточим върху алгоритъма HEngine и реализацията на решение на проблема за изчисляване на разстоянието на Хаминг върху големи количества данни.

Въведение

Разстоянието на Хеминг е броят на различните позиции за редове с еднаква дължина. Например HD (100, 001) = 2.

Проблемът за изчисляване на разстоянието на Хаминг за първи път е поставен от Мински и Паперт през 1969 г., където задачата е да се намерят всички редове от базата данни, които са в рамките на дадено разстояние на Хаминг до исканото.

Тази задача е необичайно проста, но търсенето на ефективно решение все още е на дневен ред.

Разстоянието на Хеминг вече се използва доста широко за различни задачи като намиране на близки дубликати, разпознаване на шаблони, класификация на документи, корекция на грешки, откриване на вируси и т.н.

Например Манку и колегите му предложиха решение на проблема с групирането на дубликати при индексиране на уеб документи въз основа на изчисляване на разстоянието на Хаминг.
Милър и приятели също така предложиха концепцията за търсене на песни по даден аудио фрагмент.
Подобни решения са използвани за задачата за търсене на изображения и разпознаване на ретината и др.

Описание на проблема

Има база данни с двоични низове T, размер нкъдето е дължината на всеки ред м... Искан низ аи необходимото разстояние на Хеминг к.

Задачата се свежда до намиране на всички линии, които са в рамките на разстоянието к.

В първоначалната концепция на алгоритъма се разглеждат два варианта на задачата: статичен и динамичен.

При статична задача разстоянието k е предварително определено.
- При динамично, напротив, необходимото разстояние не се знае предварително.

Тази статия описва решението само на статичен проблем.

Описание на алгоритъма HEngine за статичен проблем

Тази реализация се фокусира върху намирането на низове вътре к <= 10.

Има три решения на статичния проблем: линейно сканиране, разширяване на заявката и разширяване на таблицата.

В този случай под чрез разширяване на заявкатаИмам предвид генериране на всички възможни варианти на низове, които се вписват в определеното разстояние за оригиналния низ.
Разширяване на основатаданни предполага създаването на много копия на тази база данни, където или се генерират всички възможни варианти, които отговарят на изискваните изисквания за разстояние, или данните се обработват по някакъв друг начин (повече за това малко по-късно).

HEngine използва комбинация от тези три техники за ефективно балансиране на паметта и времето за изпълнение.

Малко теория

Алгоритъмът се основава на малка теорема, която гласи както следва:

Ако за два реда аи бразстояние HD ( а, б) <= к, тогава, ако разделите линиите аи бвърху поднизове по метод rcutизползвайки фактор на сегментиране
r >= ⌊к/2⌋ + 1
сигурно поне ще има q= r − ⌊к/ 2⌋ поднизове, когато разстоянието им не надвишава едно, HD ( ааз, би)<= 1.

Извличане на поднизове от основния низ с помощта на метода rcutсе извършва според следните принципи:
Посочената стойност фактор на сегментиранекоето удовлетворява условието
r >= ⌊к/2⌋ + 1

Дължината на първия r − (ммод r) поднизовете ще имат дължина ⌊ м / r⌋ и последното ммод rподнизове ⌈ м/r⌉. Където ме дължината на низа, ⌊ закръгля до най-близкото дъно, а ⌉ закръгля до най-близкия връх.

Сега същото нещо, само като пример:

Дадени са два двоични низа с дължина м= 8 бита: A = 11110000 и B = 11010001, разстоянието между тях к = 2.
Избор на фактор за сегментиране r= 2/2 + 1 = 2, т.е. общо ще има 2 поднизове с дължина м/r= 4 бита.

a1 = 1111, a2 = 0000
b1 = 1101, b2 = 0001

Ако сега изчислим разстоянието между съответните поднизове, то поне q= 2 - 2/2 = 1, един подниз ще съвпада или разстоянието им няма да надвишава едно.

Какво виждаме:
HD (a1, b1) = HD (1111, 1101) = 1
и
HD (a2, b2) = HD (0000, 0001) = 1

Поднизовете на основния низ са именувани подписи.
Сигнатури или поднизове a1 и b1 (a2 и b2, a3 и b3 ..., a rи б r) са наречени съвместимиедин с друг и ако броят им на различни битове не е повече от един, тогава тези подписи се наричат съвпадащи.

И основната идея на алгоритъма HEngine е да подготви базата данни за намиране на съвпадащи подписи и след това да избере онези редове, които са в рамките на необходимото разстояние на Хаминг.

Предварителна обработка на база данни

Вече знаем, че ако правилно разделим низа на поднизове, тогава поне един подниз ще съвпада със съответния подниз или броят на различните битове няма да надвишава един (сигнатурите ще съвпадат).

Това означава, че не е необходимо да извършваме пълно изброяване на всички редове от базата данни, а първо трябва да намерим онези подписи, които съвпадат, т.е. поднизовете ще се различават най-много с един.

Но как търсите поднизове?

Методът за двоично търсене трябва да свърши доста добра работа за това. Но това изисква списъкът с низове да бъде сортиран. Но получаваме няколко поднизове от един низ. За да извършите двоично търсене в списък с поднизове, всеки такъв списък трябва да бъде сортиран предварително.
Следователно тук се предлага методът за разширяване на базата данни, тоест създаване на няколко таблици, всяка за свой подниз или подпис. (Такава таблица се нарича таблица с подписи... И набор от такива маси - комплект за подписи).

Оригиналната версия на алгоритъма също така описва пермутацията на поднизове по такъв начин, че избраните поднизове са на първо място. Това се прави повече за улесняване на внедряването и за по-нататъшни оптимизации на алгоритъма:

Има низ A, който е разделен на 3 поднизове, a1, a2, a3, пълният списък с пермутации ще бъде съответно:
а1, а2, а3
а2, а1, а3
а3, а1, а2

След това тези таблици с подписи се сортират.

Изпълнение на търсене

На този етап, след предварителна обработка на базата данни, имаме няколко копия от сортираните таблици, всяка за своя подниз.

Очевидно, ако искаме първо да намерим поднизове, трябва да получим подписи от искания низ по същия начин, който беше използван за създаване на таблиците с подписи.

Знаем също, че необходимите поднизове се различават най-много с един елемент. И за да ги намерите, трябва да използвате метода за разширяване на заявката.

С други думи, изисква се избраният подниз да генерира всички комбинации, включително самия този подниз, в който разликата ще бъде най-много един елемент. Броят на такива комбинации ще бъде равен на дължината на подниз + 1.

Такива действия трябва да се извършват за всички поднизове и за всички таблици.

И в самия край ще трябва да филтрирате онези линии, които не се вписват в определената граница на разстоянието на Хаминг. Тези. извършете линейно търсене през намерените линии и оставете само онези линии, които отговарят на HD ( а, б) <= к.

Филтър за цъфтеж

Ако преди двоично търсене на подниз в таблица филтърът върне, че този подниз не е в тази таблица, тогава няма смисъл от търсене.

Съответно трябва да създадете един филтър за всяка таблица с подписи.

Авторите също така отбелязват, че използването на филтъра Bloom по този начин намалява времето за обработка на заявката средно с 57,8%. На моите тестови проби такъв филтър практически няма ефект върху полученото време за работа. Ще го усетим само в произволно генерирана база данни.

Сега същото нещо, само като пример

Има база данни с двоични низове с дължина 8 бита:
11111111
10000001
00111110

Задачата е да се намерят всички редове, в които броят на различните битове не надвишава 2 до целевата линия 10111111.

Означава необходимото разстояние к = 2.

1. Изберете коефициента на сегментиране.

Въз основа на формулата избираме коефициента на сегментиране r= 2 и така ще има два подниза от един низ общо.

2. Създаваме набор от подписи.

Тъй като броят на поднизовете е 2, трябва да бъдат създадени само 2 таблици:

3. Записваме поднизовете в съответните таблици, като запазваме връзката към източника.

T1 T2
1111 1111 => 11111111
1000 0001 => 10000001
0011 1110 => 00111110

4. Сортиране на таблици. Всеки поотделно.

T1
0011 => 00111110
1000 => 10000001
1111 => 11111111

Т2
0001 => 10000001
1110 => 00111110
1111=> 11111111

Това завършва предварителната обработка. И започваме да търсим.

5. Получаваме подписите на искания низ.

Низът за търсене 10111110 е разделен на подписи. Оказва се съответно 1011 и 1100, първият за първата маса, а вторият за втората.

6. Генерирайте всички комбинации, които се различават с една.
Броят на опциите ще бъде 5.

6.1 За първия подниз 1011:
1011
0 011
11 11
100 1
1010

6.2 За втория подниз 1100:
1100
0 100
10 00
111 0
1101

7. Двоично търсене.

7.1 За всички генерирани варианти на първия подниз 1011, ние извършваме двоично търсене в първата таблица за пълно съвпадение.

1011
0011 == 0011 => 00111110
1111 == 1111 => 11111111
1001
1010

Намерени са две поднизове.

7.2 Сега, за всички варианти на втория подниз 1100, ние извършваме двоично търсене във втората таблица.

1100
0100
1000
1110 == 1110 => 00111110
1101

Намерен е един подниз.

8. Комбиниране на резултатите в един списък:
00111110
11111111

9. Проверете линейно за съответствие и филтрирайте неподходящите по условие<= 2:

HD (10111110, 00111110) = 1
HD (10111110, 11111111) = 2

И двете линии отговарят на условието за разлика на не повече от два елемента.

Въпреки че на този етап се извършва линейно търсене, се очаква списъкът с кандидат низове изобщо да не е голям.
При условия, когато броят на кандидатите ще бъде голям, се предлага да се използва рекурсивният вариант на HEngine.

Ясно е

Фигура 1 показва пример за алгоритъм за търсене.
За дължина на низа от 64 и граница на разстояние 4, коефициентът на сегментиране е 3, така че има само 3 поднизове на низ.
Където T1, T2 и T3 са таблици с подписи, съдържащи само поднизове B1, B2, B3.

Исканият низ се разделя на поднизове. След това се генерира диапазон на подписите за съответните поднизове. И накрая се прави двоично търсене.

Фигура 1. Опростена версия на обработка на заявки за таблица с подписи.

резултати

Сложността на такъв алгоритъм в средния случай О(м(дневник н+ 1)), където не общият брой редове в базата данни, ме броят на двоичните търсения и log н+ 1 двоично търсене.
В екстремни случаи може да надхвърли линейното. Например, при условие q= 1 и когато всички редове от всички таблици с подписи, с изключение на последната, съвпадат с исканата, тогава се оказва О((r - 1)мн(дневник н + 1)).

Отбелязва се, че този подход използва 4,65 по-малко памет и е с 16% по-бърз от предишната работа, описана в.

Изпълнение

Всичко това, разбира се, е примамливо, но докато не го докоснете, е трудно да се оцени мащаба.
Създаден е прототип на HEngine и е тестван върху наличните реални данни.

Тества $ ./съвпада с 7 данни / db / table.txt данни / заявка / face2.txt Четенето на набора от данни ........ готово. 752420 db хешове и 343 хешове на заявки. Изграждане със 7 обвързано разстояние на Хеминг ....... готово. Време за изграждане: 12,964 секунди Търсене на съвпадения в HEngine ..... са намерени общо 100 съвпадения. Време на заявка за Hengine: 0,228 секунди Търсене на линейни съвпадения ....... намерени общо 100 съвпадения. Линейно време за заявка: 6,828 секунди

Резултатите бяха обнадеждаващи, тъй като търсенето на 343 хеша от базата данни в 752420 отнема ~ 0,2 секунди, което е 30 пъти по-бързо от линейно търсене.

Изглежда, че човек може да спре до тук. Но наистина исках да се опитам да го използвам по някакъв начин в реален проект.

Едно щракване до реално приложение

Има база данни с хешове на изображения и PHP бекенд.
Задачата беше по някакъв начин да свърже функционалността на HEngine и PHP.
Беше решено да използвам FastCGI, много ми помогнаха публикациите habrahabr.ru/post/154187/ и habrahabr.ru/post/61532/.

От PHP е достатъчно да извикате:

$ list = file_get_contents ("http: //fcgi.local/?". $ хешове);

Което връща резултата за около 0,5 секунди. Когато линейното търсене отнема 9 секунди, а чрез заявки към MySQL най-малко 20 секунди.

Благодаря на всички, които го направиха.

Разстояние на Хеминг

Американският математик Хеминг изследва от какво зависи дадения код, дали ще открие грешки и кога може да ги поправи. Интуитивно е ясно, че зависи от това как са раздалечени кодовите думи и колко грешки могат да се появят в предаваната дума. Сега формализираме следната идея. При кодиране е необходимо да се съпостави броят на възможните грешки в предаваната дума, така че когато предаваната кодова дума се промени, тя да остане по-близо до оригиналната кодова дума, отколкото до която и да е друга кодова дума.

Определение 13.1.Помислете за набора от всички двоични думи в азбуката V= (0,1) дължина Tразстояние д(х, при), което е равно на броя на несъответстващите позиции на тези думи. Например, За думи NS = 011101, при= 101010 разстоянието е д(х, г) = 5. Това разстояние се нарича Разстояние на Хеминг .

Може да се покаже, че разстоянието на Хаминг удовлетворява аксиомите на метричното пространство:

1) д(х, при) ≥ 0, д(х, при) = 0, ако и само ако NS = y;

2) д(х, г) = д(г, х);

3) д(х, при) ≤ д(х, z) + г(z, при) е неравенството на триъгълника.

Теорема 13.1(относно кода за откриване). Кодът е детектив, когато предадената дума съдържа най-много к

д(б 1, б 2) ≥ к+ 1.

Теорема 13.2(относно коригиращия код.). Кодът коригира всички грешки в случай, че предадената дума съдържа не повече от кгрешки, ако и само ако най-малкото разстояние между кодовите думи

д(б 1, б 2) ≥ 2к+ 1.

Доказателство... Доказателствата на тези теореми са подобни. Следователно ще докажем само последната теорема.

Адекватност... Нека за всички кодови думи, които имаме д(б 1, б 2) ≥ 2к+ 1. Ако по време на предаване на кодовата дума б 1 се случи най-много кгрешки, то за приетата дума с имаме д(б 1, ° С) ≤ к... Но от неравенството на триъгълника за всяка друга кодова дума б 2 имаме д(б 1, с) + д(° С, б 2) ≥ д(б 1, б 2) ≥ 2 к+ 1. Следователно разстоянието от получената дума до всяка друга кодова дума д(° С, б 2) ≥ k + 1, тоест повече от преди б 1. Следователно според приетата дума сможете недвусмислено да намерите най-близката кодова дума б 1 и след това го декодирайте.

Трябва... От противоречие. Да предположим, че минималното разстояние между кодовите думи е по-малко от 2 к+ 1. След това има две кодови думи, разстоянието между които ще бъде д(б 1, б 2) ≤ 2 к... Нека при предаване на дума б 1 приета дума се между думите б 1, б 2 и има точно кгрешки. Тогава д(° С, б 1) = к, д (° С, б 2) = д(б 1, б 2) – д(° С, б 1) ≤ к... По този начин от думата c е невъзможно недвусмислено да се възстанови кодовата дума, която е била предадена, б 1 или б 2. Стигнахме до противоречие.

Пример 13.3 ... Помислете за следните 5-битови кодове на думи с дължина 2 в азбуката V = {0,1}:

б 1= К(00) = 00000, б 2= К(01) = 01011,

б 3= К(10) = 10101, б 4= к(11) =11110.

Минималното разстояние между различните кодови думи е д(би, bj) = 3. По силата на първата теорема за кода за откриване, този код е в състояние да открие най-много две грешки в една дума. По силата на втората теорема кодът е в състояние да коригира най-много една грешка в думата.

Групови кодове

Нека разгледаме по-подробно кодовете на думите в азбуката. V= (0, 1). Ако за думи дълги Tкодови думи с дължина н, тогава такива кодове ще бъдат извикани ( T , NS) -кодове. Общо дълги думи мравно на 2 м... Да попитам ( T , NS) -code, можете да изброите кодови думи за всички възможни думи с дължина мкакто в предишния пример. По-икономичен начин за определяне на кодови думи е присвояването на матрица.

В този случай е дадена генериращата матрица Г= ∣∣ gij∣∣ поръчка T × NSот 0 и 1. Кодовите думи се определят всеки път по дума а = а 1а 2... прикато умножите тази дума отляво като вектор по генериращата матрица

Тук събирането се определя по модул 2. За да отговарят различни думи на различни кодови думи, е достатъчно да има в матрицата Гединица базов ред минор T, например крайния ляв.

Пример 13.4 ... Помислете за генериращата матрица

Тази матрица дефинира (3, 4) -код. В този случай първите три знака в кодовата дума са информационни, а четвъртият е контролен. Това е 0, ако в оригиналната дума има четен брой единици, и 1, ако има нечетен брой единици. Например за думата а= 101 кодът ще бъде б= aG= 1010. Минималното разстояние на Хеминг между кодовите думи е д(би, bj) = 2. Следователно това е код, който открива единична грешка.

Определение 13.2.Кодът се извиква група ако наборът от всички кодови думи образува група. Броят на единиците в думата a се нарича везнидуми и се означават с If б- кодовата дума и думата, получена в комуникационния канал с = b + eслед това дума дНаречен вектор на грешките .

Теорема 13.3.Нека има група ( T , NS)-код. След това комутативната група ДА СЕот всички кодови думи е подгрупа на комутативната група Свсички думи с дължина NSкоито могат да бъдат получени по комуникационния канал. Най-малкото разстояние между кодовите думи е равно на най-малкото тегло на ненулева кодова дума и

Помислете за групата на факторите C/K... Съседните класове тук ще се определят от смяната e + b, б∈ К.

Изберете елемента с най-ниско тегло като представител на косета. Ще наречем такива елементи съюзни класови лидери .

Ако лидерите се тълкуват като вектори на грешки, тогава всеки coset е набор от изкривени думи в комуникационен канал с фиксиран вектор на грешка, по-специално за д= 0 имаме съседен клас думи без изкривяване, т.е. набор от всички кодови думи. Процес на корекция и декодиране на думи се да се намери класацията, към която принадлежи думата с = д + б... Вектор на грешките допределя броя и местоположението на грешките, кодова дума бопределя корекцията на получената дума.

За да се улесни търсенето на косет и по този начин на вектора на грешката, Хаминг предложи използването на групови кодове със специални генераторни матрици.

Кодове за подгъване

Помислете за изграждането на Hamming ( T , NS) -код с най-малкото тегло на кодовата дума равно на 3, т.е. код, който коригира една грешка.

Слагаме NS = 2 r- 1 и нека всяка кодова дума съдържа rконтролни знаци и Tзнаци ( T = NS – r= 2 r– 1– r) - информационен, r≥ 2, например (1, 3) -код, (4, 7) -код и т.н. Освен това във всяка кодова дума б= б 1б 2... б стрсимволи с индекси, равни на степента на 2, ще бъдат контролни, а останалите ще бъдат информационни. Например за (4, 7) -код в кодовата дума б= б 1б 2б 3б 4б 5б 6б 7 символа б 1б 2б 4 ще бъде контрол и символи б 3б 5б 6б 7- информационен. За дефиниране на генерираща матрица Гподгъване ( T , NS) -код, разгледайте спомагателната матрица Мпоръчка r× NS, където NS = 2 r- 1, така че във всяка jматрица колона Мще има символи на двоичното разлагане на числото j, например, за (4, 7) -код, матрицата Мще бъде 3 × 7:

Множеството от всички кодови думи се дефинира като набор от решения на хомогенна система от линейни алгебрични уравнения от вида

b MT= 0.

Например, за (4, 7) -код, такава система ще бъде:

Нека изберем естествен основен минор на системата b MT= 0, стоящи в колони с числа, равни на степента на 2. Така разделяме променливите на основни (код) и свободни (информационни). Сега, след като сте задали безплатни променливи, е лесно да получите основни. Намерете основната система м= NS – rрешения на тази хомогенна система. Тогава всяко решение на системата е линейна комбинация от тях мрешения. Следователно, изписване ред по ред мрешения на фундаменталната система под формата на матрица Гразмерът м× NS, получаваме генериращата матрица на групата на Хаминг ( T , NS) -код, например, за (4, 7) -код, основната система от решения ще бъде 4 = 7 - 3 от следните решения на хомогенната система:

ж 1= 1110000, ж 2= 1001100, ж 3= 0101010, ж 4= 1101001.

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

Сега за всяка дума адължината T= 4 лесно да се изчисли кодовата дума бдължината NS= 7 с помощта на генераторната матрица б= aG... Освен това символите б 3, б 5, б 6, б 7 ще бъде информационен. Те са същите като а 1, а 1, а 3, а 4.Символи б 1, б 2, б 4 ще бъде контрол.

Изход... Кодовете на Хеминг са удобни с това, че косетите се определят лесно по време на декодирането. Нека думата, получена през комуникационния канал, бъде с = д + б, където д- грешка, б- кодова дума. След това го умножаваме по спомагателната матрица SMT= (д + б)MT= eM T... Ако eM T= 0, след това думата с- кодирайте и помислете: няма грешка. Ако eM T≠ 0, след това думата дидентифицира грешката.

Припомнете си, че конструираният подгъв ( T , NS) -кодът дефинира една грешка. Следователно, векторът на грешката дсъдържа една единица в ипозиция. И числото ипозицията се получава в двоичен вид като резултат eM Tсъвпадащ с иколона от матрица М... Остава да промените символа ив думата c, получена по канала, изтрийте контролните знаци и запишете декодираната дума.

Например, нека приетата дума е с= 1100011 за (4, 7) кода на Хеминг. Нека умножим тази дума по матрицата М Т... Получаваме

(1100011) М T=(010).

Следователно има грешка във втория знак. Следователно кодовата дума ще бъде б= 1000011. Зачеркнете контролните знаци б 1, б 2, б 4. Декодираната дума ще бъде а = 0011.

Разбира се, ако е направена грешка в повече от един знак, тогава този код няма да я поправи.