304
правки
Изменения
→Алгоритм получения цепного кода для двоичного вектора
[[Файл:chain4.png|thumb|right|Цепной код для двоичного вектора длиной 4]]'''Цепной код''' — это код, каждый следующий столбец которого получается из предыдущего циклическим сдвигом вверх.
== Алгоритм получения цепного кода для двоичного вектора двоичных векторов ==# Берем в В качестве первого слова слово вектора берём вектор из <tex>n </tex> нулей.# Делаем циклический сдвиг предыдущего слова влево с потерей первого разрядаЧтобы получить следующий вектор, берём последний добавленный вектор, пусть <tex>a_1\cdots a_n</tex>.# Приписываем к полученному слову Если в конец единицукоде до этого не встречатся вектор <tex>a_2\cdots a_n 1</tex>, то добавляем его. Проверяем, встречалось ли это слово Иначе проверяем на наличие в коде ранеевектора <tex>a_2\cdots a_n 0</tex>.# Если неттакой не встречался, то записываем добавляем его в код. Если вектор уже встречался, значит, иначе последнюю единицу заменяем на ноль и записываем слово в кодгенерация кода закончена.# Если получено слово из == Псевдокод алгоритма == chain_code(n): current = string('0', n) result = [current] while (true): prefix = current.substring(2, n нулей) if concat(prefix, '1') not in result: current = concat(prefix, то код полностью записан'1') else concat(prefix, иначе возвращаемся к шагу 2 '0') not in result: current =concat(prefix, '0') else: break result.append(current) return result В приведённом выше псевдокоде:* current — последний добавленный битовый вектор* result — список битовых векторов ==Доказательство корректности===
Разобьем доказательство на две части:
# Доказательство того, что одно один и то тот же слово вектор встречается в коде не более одного раза.# Доказательство того, что код перебирает все возможные слова вектора прежде, чем получит слово из <tex>n</tex> нулей. ===Доказательство первого пункта===Покажем, что единственная ситуация, когда требуется сгенерировать новый вектор, а оба возможных варианта (добавление нуля или единицы) уже добавлены — сгенерирован вектор из <tex>n</tex> нулей. Рассмотрим первое такое противоречие: последним добавлен вектор <tex>a_1 a_2 \cdots a_n</tex>, вектора <tex>a_2 \cdots 1</tex> и <tex>a_2 \cdots a_n 0</tex> уже присутствуют в коде. Далее есть две возможных ситуации: вектор<tex>a_2 \cdots a_n 0</tex> состоит из <tex>n </tex> нулейили предшествовал другому вектору в коде. В первой ситуации алгоритм завершает работу. Во второй сутиации каждому из векторов <tex>a_2 \cdots a_n 1</tex> и <tex>a_2 \cdots a_n 0</tex> предшествовали некоторые вектора в коде, пусть <tex>B_1 = b_2 a_2 \cdots a_n</tex> и <tex>B_2 = b_2 a_2 \cdots a_n</tex>. Так как мы рассматриваем первое противоречие, то <tex>b \neq c</tex>.
Покажем, что невозможно вернуться к слову из всех нулей, пока не переберем все <math>2^n</math> слов, где n — длина слова. Допустим, мы всё же получили слово из всех нулей раньше, чем перебрали все слова. Тогда разобьём слова, которые не попали в код на две группы: кончающиеся на единицу и кончающиеся на ноль. Докажем, что второй группы группы нет. Рассмотрим слово {abc..yz}0, не попавшее в код, где {abc..yz} — некоторая последовательность единиц и нулей. Заметим, что слово {bc..yz}00 также не в коде. Оно могло быть получено из слов 1{bc..yz}0 и 0{bc..yz}0, одно из которых есть рассматриваемое {abc..yz}0. Но если другое слово и встретилось в коде, то мы бы получили из него {bc..yz}01, следуя алгоритму (причем это слово точно встретится в первый раз). Таким образом, слово {bc..yz}00 точно не в коде. Такую же цепочку рассуждений можно провести и для слова {c..yz}000, и так далее. На n-ом шаге мы бы получили утверждение, что слова из n нулей тоже нет в коде, и пришли бы к противоречию. Заметим, что исходя из третьего и четвертого шагов, все слова вида {abc..yz}1 встречаются строго раньше {abc..yz}0, которые точно записаны в код. Таким образом, слов, не попавших в код, нет.
