Задача 23.
Пусть слово - это последовательность от 1 до 8 заглавных букв латинского алфавита.
Задается множество слов A={a[1], a[2],..., a[n]}, n<10. Из слов множества A составляется текст - последовательность слов, записанных друг за другом без разделителей пробелов. Слова могут встречаться в тексте произвольное число раз.
Дешифровка текста - это разбивка текста на слова множества A. В дешифрованном тексте слова разделяются пробелами.
Необходимо:
1.Определить, существует ли для заданного множества A такой текст, который дешифруется не единственным образом (сам текст приводить не надо).
Примеры:
1) A = { B , C }
Любой текст дешифруется однозначно.
2) A = { B , BC , C }
Существует текст, который дешифруется двумя способами
Текст ---> Дешифровка
BBC ---> B B C
BBC ---> B BC
2. Если такой текст существует, то исключить из множества A минимальное число слов так, чтобы после этого любой текст, составленный из слов полученного множества A, дешифровался однозначно. Напечатать эти исключенные слова. Если такой набор не единственный, то напечатать все наборы.
3.Для введенного текста произвести его дешифровку и, если дешифровка не единственная, вывести все варианты.
Примечания: Порядок выполнения пунктов строго фиксирован.
|
Решение задачи 23.
Один из возможных алгоритмов решения задачи такой:
1. Предположим, что существует текст, дешифровка которого неоднозначна, следовательно, существует и текст минимальной длины, для которого возможны по меньшей мере две разбивки
b[1] b[2]...b[k] = c[1] c[2]...c[m]
на слова множества A. Представляя текст в виде отрезка DE, эти разбивки мы можем изобразить следующим образом
Из того, что текст минимальной длины, следует, что концы слов в разных разбивках не могут лежать на одной вертикали (кроме конца текста), т.к. b[1] <> c[1], то одно из кодовых слов (например b[1]) должно входить в другое в качестве префикса и представляться в виде c[1] = b[1] p[1] , где p[1] - это оставшаяся часть слова (суффикс). Далее, либо p[1] входит в b[2] (b[2] =p[1] p[2]), либо b[2] входит в p[1] (p[1] = b[2] p[1] ) в качестве префикса. Определяем новый суффикс p[2]. Продолжая выделять префиксы и суффиксы, получаем, что на каком-то шаге p[j] совпадет с одним из кодовых слов.
Эти рассуждения являются основой следующего алгоритма :
На нулевом шаге возьмем все пары (a[i], a[j]), i <> j, таких кодовых слов, что одно из них есть префикс другого, и найдем все суффиксы p[0,k].
На j-ом шаге для всех пар (p[j-1,k], a[i]), где одно из слов является префиксом другого, опять находим все суффиксы, и те из них, которые не появлялись на предыдущих шагах алгоритма, обозначим p[j,k].
Эти шаги повторяем либо до тех пор, пока какой-либо суффикс не совпадет с одним из кодовых слов (и тогда существует неоднозначно декодируемый текст), либо пока на очередном шаге не появится ни одного нового суффикса (и тогда для любого текста существует единственная дешифровка).
Т.к. количество кодовых слов ограничено, то и суффиксов также конечное число, и на каком-то шаге алгоритм обязательно остановится.
Этот алгоритм принадлежит в первоначальном варианте A. Сардинасу и Дж. Паттерсону (см. Кибернетический сборник, вып.3 стр. 93102 ).
2. Если существует текст, который, используя A, дешифруется неоднозначно, то начинаем выбрасывать из A слова и их комбинации, пытаясь получить множество A' с максимальным числом слов такое, что все тексты, составленные из слов A' дешифруются однозначно.
Сначала из A удаляем i-ое слово , i = 1, 2, ... , n, и делаем проверку по пункту 1. Если удалением одного слова из A мы не получаем искомого множества A', то тогда генерируем все сочетания по n-2 слова из множества A, и для каждого полученного множества делаем проверку по пункту 1, и т.д.
Воспользуемся следующим алгоритмом генерации сочетаний по i слов из множества A:
В массиве B будут находиться индексы используемых на данном шаге элементов из A (общее их число i). В качестве начальной конфигурацией возьмем следующую: B[j]=j, j=1,...,n.
Ищем B[j] с максимальным индексом j такое,что B[j]<n+j-i, увеличиваем это B[j] на 1, а для всех k>j полагаем B[k]=B[k-1]+1 (B[j] растут с ростом j, и мы ищем и увеличиваем на 1 такое B[j] с максимальным номером j, чтобы при заполнении возрастающими значениями элементов массива B[k], k>j, последний элемент B[i] не превосходил бы n). Если такого B[j] не существует, то генерация сочетаний для данного i закончена.
Начинаем генерацию с i=n-1 и проводим ее с уменьшением i до тех пор, пока либо i не станет равно 1 (тогда A' состоит из единственного слова), либо пока проверка по пункту 1 не даст однозначности декодировки.
3. Этот пункт реализуется следующим рекурсивным алгоритмом поиска с возвращением (все слова массива A упорядочены по номерам):
а) Если строка пустая, то одна из возможных дешифровок найдена, иначе при разборе текста мы проверяем a[i] (при изменении i от 1 до n) на вхождение в начало дешифруемой в данный момент строки.
б) Если какое-то a[i] входит в строку как префикс, то запоминаем номер i этого слова, затем выделяем слово из строки, а с остатком текста производим операцию разбора по пункту а).
Если ни одно из а[i] не входит в качестве префикса в дешифруемую сейчас строку, то осуществляем возврат на пункт а), предварительно добавляя в начало строки последнее удаленное оттуда слово, и пытаемся выделить из текста слово с большим номером в A. Если возврат осуществить невозможно (т. к. мы находимся в начале исходной строки), то алгоритм заканчивает свою работу. Все возможные дешифровки найдены.
Задача 1. Докажите следующую теорему (Марков А. А.):
Для однозначности декодировки текста достаточно выполнения одного из двух следующих условий:
1) не существует ни одной пары кодовых слов (a[i], a[j]), i<>j, такой, что одно из этих слов есть префикс другого.
2) не существует ни одной пары кодовых слов (a[i], a[j]), i<>j, такой, что одно из них есть суффикс другого.
Задача 2. Приведите пример такого множества кодовых слов, что для него не выполняется ни условие 1, ни условие 2 из предыдущего пункта, а декодировка любого текста, составленного при помощи этоих слов - однозначная.
|
