Меня заинтересовала задача, но, признаюсь, я даже нагуглить не смог теории по этому поводу. Этот тест Егорова был упомянут здесь, и на одном НАРОД-сайте.
Скажите, вы можете поделиться чем-нибудь по этому поводу?

Меня заинтересовала задача, но, признаюсь, я даже нагуглить не смог теории по этому поводу. Этот тест Егорова был упомянут здесь, и на одном НАРОД-сайте.
Скажите, вы можете поделиться чем-нибудь по этому поводу?

Никакой информации по этому поводу вообще небыло дано. Только задание и всё. В интернете тоже ничего несмог найти и поэтому обратился сюда.

Попробую систематизировать само задание:
Есть некоторій тескт,

Например, первые семь страниц романа Толстого "Анна Каренина".

Для понимания задания важно, именно количество символов на одной странице, т.е. к примеру приблизительно N символов-знаков, получается 7хN, это позволит Вам составить статистику текста и сравнить её со статистикой русского языка. Это и есть:

Разрешается: Вводить в систему любые правила обработки, предположения об устройстве мира и эволюции, собирать статистическую и прочую информацию с исходного текста и заниматься прочей работой.

Если можно собирать статическую информацию, то думаю, что статистика одного из языком мира будет попадать под правило: предположений об устройстве мира. Сам язык уже известен - русский, его статистика выложена в сети, к примеру: Статистика частотности букв русского языка.

Анализируя 7хN символов можно получить приблизительную статистику текста и сравнить её со статистикой языка, тем самым получить уже сами буквы и т.д., дальше уже нужно становится шпионом.

Алгоритм
Кратко опишем алгоритм приложения анализа статистических свойств языка:
1. Получение размера файла (файлов) и вычисление объема работ.
2. Инициализация счетчиков встречи символов (байт).
3. Цикл чтения файлов с данными. Чтение файла и проверка его на корректность.
4. Цикл чтения блоков байт файла, например размер 4096 байт, из файла. Последовательный анализ каждого блока и увеличение соответствующих счетчиков.
5. Закрытие файла с входными данными. Проверка на корректность.
6. Создание файла с результирующими данными. Проверка на корректность.
7. Запись в результирующий файл значений символов и количество их встреч, а также частоту их появления в данном тексте.
8. Закрытие файлов с выходными данными. Проверка на корректность.

Алгоритм зашифровывания текстового файла:
1. Открытие исходного файла, его чтение и проверка на корректность.
2. Открытие результирующего файла, проверка его на корректность.
3. Цикл чтения блоков байт исходного файла, например размер 4096 байт. Последовательное сложение по модулю 2 каждого символа блока исходного файла с байтом-ключом. Запись сформированного блока в результирующий файл.
4. Закрытие файла с входными данными. Проверка на корректность.
5. Закрытие файла с результирующими данными. Проверка на корректность.

Алгоритм криптоанализа зашифрованного файла. Для простоты, будем рассматривать лишь частоты встречи одного символа, а двойки и тройки использовать в приложении криптоанализа не следует.
1. Открытие файла статистики исходного языка, проверка его на корректность.
2. Чтение частоты появления одиночных символов языка в память и формирование таблицы анализа.
3. Закрытие файла статистики. Проверка на корректность.
4. Открытие файла статистики зашифрованного файла, проверка его на корректность.
5. Чтение частоты появления одиночных символов языка в память и формирование таблицы анализа.
6. Закрытие файла статистики. Проверка на корректность.
7. Открытие зашифрованного файла, его чтение и проверка на корректность.
8. Открытие файла с результирующими данными. Проверка на корректность.
9. Цикл чтения блоков байт зашифрованного файла, например размер 4096 байт.
9.1. Для каждого байта блока следует произвести его поиск в таблице частот (статистика зашифрованного файла).
9.2. Произвести поиск соответствующего ему символа языка в таблице частот (статистика языка).
9.3. Записать восстановленный блок в результирующий файл.
10. Закрытие файла с входными данными. Проверка на корректность.
11. Закрытие файла с результирующими данными. Проверка на корректность.

Приблизительно так.

Мы бы могли придумать какой-нибудь вес символа. Он должен расти, если встречаются вот такие группы

Думаю, приблизительно это(см. выше) Вы хотели сказать.

Ладно, допускаю, что могу ошибаться. Но мне кажется, вы как-то притянули решение к ответу. У нас неизвестно, что язык - русский. И в идеале, у нас может быть массив из каких угодно букв, цифр или символов. Сравнивая полученную статистику для всех символов с википедией мы сможем распознать буквы и отделить их от разделителей. Но это же неверно - потому что "тупая машина" должна сама определить что есть символ, а что разделитель (пробел, запятая или ещё что).

Представьте, у вас есть последовательность 1212121. Что в этом случае можно считать разделителем? Я предполагаю, что число 2. Потому что мы можем задать правило вселенной о том, что с символ-разделитель всегда отделяет сущности (буквы) друг от друга. Слева от первого числа и справа от последнего ничего нет.

И даже если у меня будет статистика букв на руках, но вот такой я плохой и смешиваю разные языки в тексте, все равно придется самому придумывать нечто другое :)

Кстати, скажите, а что означает загадочная фраза в вашем алгоритме: "проверка на корректность".

а больше сделать ничего и нельзя..

*1*считать надо. статистика всё расставит по своим местам.
наверняка можно будет выделить несколько групп
1 - вероятные разделители
2 - вероятные буквы
3 - вероятные специальные символы
количественная разница при подсчёте символов в тексте должна быть весьма заметна.

*2*дальше можно искать символы, которые всегда идут до или после "разделителя" - получатся точки, скобки и прочие из группы №3

*3*символы из группы 3, которые встречаются где угодно нужно отнести к группе 2 - будут типа "ъ"

*4*в группе 2 могут оказаться запятые, например.. их от туда можно вычистить методом *2*

*5* "цифры" могут входить во все 3 группы, но практически всегда идут вместе (отдельно от группы 2)
тут можно использовать порог, например "цифра с 80% вероятностью"

*6* стоит помнить, что один язык может быть скомпонован из нескольких "алфавитов"
буквы, цифры латинские, цифры арабские, символы из высшей математики, знаки из низших миров, загадки пьяного факира, ...
то есть при полном разборе языка недостаточно выделить буквы и разделители
нужно выяснить "алфавиты" до какого-то % точности, выбрать наиболее соответствующую "конструкцию" текста
и уже на её основе уточнять алфавиты.
.... это не потребуется для разбора страниц романа Толстого, но если вместо него попробуешь учебник по физике
получится не весело..

в принципе, выглядит не сложно
... устроит такой ответ?

Меня единственное смущает в наших с вами решениях (я так понимаю у нас они похожие), что если не удастся правильно получить разделитель там, где его количество очень мало. Например, будут какие-нибудь немецкие слова, и их количество небольшое. Тогда какая-нибудь буква О станет разделителем.

Более того, я не совсем понимаю как быть с запятыми, точками и скобками. Теоретически, придётся ввести понятие как знаки препинания и найти их. Допустим, собрав статистику по скобкам, тире, точкам и запятым, мы должны получить что-то вроде: точки чаще, чем запятые (хотя у Толстого может быть наоборот), тире и скобки реже будут букв Ъ и Ы :)

Тогда придётся их отнести к группе разделителей. Какая может быть проблема? Мы можем ошибиться на один-два символа и отнести его неверно. Предположим, мы получили такую вот статистику:

точки - 100
запятые - 90
тире - 40
скобки - 6 (обычно парами)
а потом, бах, видим в этом распределении Ъ и Ё. Или пару арабских букв.

Проблема в том, что мы не можем относить их к разделителям, и более того - не можем задавать искусственные границы вида - кол-во разделителей (или вероятность, все равно) равно от 10 до 100 (чтобы узнать наши с вами точки и запятые).

Можно попытаться поймать сочетания "знак препинания - разделитель" (или наоборот), чтобы найти вот такие совпадения ". ", " ,", ") ", " (". Но если документ набирали с ошибками, и наш шаблон поломается такой вот конструкцией: "абв,где", то будет не айс :)

Скорей всего задачу можно упростить до такого: написать всевозможные правила, позволяющие из набора символов распознать буквы, цифры, знаки препинания, пробелы не залезая в таблицу символов ASCII :)

ну.. если "О" станет разделителем - значит так тому и быть.
просто "немцы" ошибочно считают разделителем пробел, когда на самом деле - это "О"
- то есть подобные методы всегда имеют % точности
никто не может требовать абсолютно точного решения при использовании вероятностных методов.

точки и запятые *2* в моём сообщении
Ъ и Ё - *3* в моём сообщении, конечно, проблема заглавных букв - что всегда стоят после разделителя
и поэтому вполне могут считаться служебным символом...
для подобных случаев - *6* в моём сообщении
то есть, после примерного выяснения алфавита можно составить представление о структуре текста
и используя структуру текста можно выделить заглавные буквы

писать правила.. чем больше правил - тем больше исключений. это палка о двух концах.
но, без правил тоже никуда не денешься...
поэтому я и предлагаю *6* - "структура", "шаблоны", "наборы правил"... назови как хош, лишь бы работало.

Уважаемые эксперты а можете теперь пожалуйста всю Вашу переписку сформулировать в один ответ), а то вся информация предоставленная сдесь мне только частично понятна, чтобы я мог продемонстрировать ответ на поставленный вопрос своему преподавателю. Спасибо за помощь!

К сожалению, я не могу исправить свой ответ. Не могли бы вы мне помочь? Ниже текст ответа:

Так как нельзя явно задавать компьютеру какие входящие символы являются буквами, пробелами и знаками препинания (для цифр и букв иностранных алфавитов эти группы можно расширить), то необходимо составить такое множество условий или правил, которое бы позволяло разгруппировать символы по группам.

Всё что разрешено делать со входящим текстом - это собрать статистику по символам. Статистика будет полезна в том случае, когда невозможно явно определить к какой группе принадлежит символ.

Для начала воспользуемся условными обозначениями: (б)уква, (р)азделитель, знак (п)препинания и (х) - любой символ.

На основе статистики выбрать первые несколько символов, которые наиболее часто употребляются в тексте. И предположить, что текущий символ является разделителем (р). Для них осуществить поиск по шаблону: "рхр", "рххр". Эти правила определяют, что разделитель как минимум отделяет один или два любых символа от остальных. Можно было бы воспользоваться правилом, где три любых символа идут подряд, но это если возникнет противоречивая ситуация.
Отдельно, можно предположить, что разделитель не будет присутствовать в начале или конце текста (или строки). Потому что в задаче ничего не говорится про разрыв строк, и мы можем предположить, что строки непрерывны и отделяются друг от друга клавишами Enter.

Когда мы получаем наиболее вероятных кандидатов в разделители, мы можем поискать вокруг них любые символы и сказать, что они являются знаками препинания. Но, здесь следует наложить условие, что кандидат в знаки препинания всегда расположен с разделителем, и не может находится рядом с буквами. То есть шаблон поиска будет такой: "хпр" или "рпх". Возможно мы столкнемся со знаками препинания следующего вида "хпх", но по статистике символов надо посмотреть как часто такой символ употребляется в тексте.

Другие правила, которые предложил Алексей на форуме позволят помочь вам узнать цифры или специальные символы. Но опять же, надо смотреть на живом примере и экспериментировать.

Спасибо.

Привет!
хорошо бы знать, что именно не понятно в моём сообщении от 05.05.2012...
ладно, будет по-подробнее

(1) подсчёт символов
(1.2) выбор 3-х групп символов
1 - вероятные разделители
2 - вероятные буквы
3 - вероятные специальные символы
* группы должны иметь довольно существенную разницу, например
вес разделителя 100 -90 %
вес буквы 70 - 30 %
вес знака 10-1 % (знак в данном случае - знак препинания или служебный символ)
тут считаешь сколько раз встречается каждый символ и самый большой результат берёшь за 100%
** естественно, может получится несколько символов в группе 1.
в таком случае, если например, в первой группе оказалось 3 символа - каждый из них является разделителем с вероятностью в 33%
***статистику и распределение по группам не выбрасывай - сделай табличку со всеми найденными символами и занеси туда статистику для каждого
(2) уточнить разделитель
в случае, если в группе 1 оказалось несколько символов, нужно отсеять "лишние" (например ' ', о, а)
тут нужно применять правила.. можно придумать кучу правил.
правило 1 - длина слов. смысл в том, что знаки препинания делят цепочки символов на более мелкие слова, чем буквы
нужно просматривать весь текст и искать, например, самое длинное слово, для каждого разделителя.
причём, мы ищем "статистически" - то есть лучше выбрать не одно а 10 самых длинных "слов" и взять их среднюю длину.
например текст "нужно просматривать весь текст и искать, например, самое длинное слово, для каждого разделителя."
даст результат "пробел" - самое длинное слово - 13 символов, 'о' - 46 символов, 'а' - 24 символа.
то есть "о" - 100%, "а" - 52% и пробел - 28%.
разница очевидна.
правило 2 - знаки всегда идут до или после пробела.
тоже хорошее правило... но пока что невозможно быть уверенным на счёт знаков, то есть пробел никогда не будет стоять рядом с "ъ"
с другой стороны, ни "а" ни "о" тоже не стоят рядом с "ъ", что делает это правило оправданным.
нужно считать пары "знак"+"пробел" или "пробел"+"знак" для всех возможных пробелов со всеми возможными знаками
например, тот же текст " нужно просматривать весь текст и искать, например, самое длинное слово, для каждого разделителя. "
для пробела даст 5 совпадений ( ","+" "), ( "ь"+" " ), ("." + " ")
для "о" даст 1 совпадение ("о" + ",")
для "а" даст 0 совпадений
я в этом случае указал и "ь" потому что скорее всего буквы "ь", "ъ" окажутся в группе знаков..
в любом случае - правило однозначно работает
...можно составить сколько угодно правил..
в итоге, используя набор правил можно выбрать наиболее вероятный разделитель
*я рекомендую ВСЕ результаты сохранять в табличке, в которой записана статистика по символам
в разных столбцах, конечно ))

(3) уточнить знаки (знаки препинания и специальные символы)
нужно применить другой набор правил к тексту
например
правило 1 знаки - это символы, которые всегда идут до или после "разделителя"
берёшь список всех символов, которые встретились в тексте и начинаешь просматривать текст
если встречается сочетание "символ"+"пробел" или "пробел"+"символ" - подтверждаешь этот символ
если встречается сочетание "не пробел"+"символ"+"не пробел" - вычёркиваешь этот символ из списка.
получается список из "вычеркнутых", "подтверждённых" и "не подтверждённых" знаков - заносим в ту же табличку со статистикой
"подтверждённые знаки", которые входят в группу 3 - можно считать доказанными
"вычеркнутые знаки" - это буквы типа "ъ"
"не подтверждённых" теоретически быть не должно... если появятся - стоит поискать ошибки

(4) Правила - "заглавные буквы"
можно применить правило поиска "заглавных букв" по шаблону типа
"пробел"+"возможная заглавная буква"+"буква"
бывают одиночные заглавные буквы ( "А", "И"), но их невозможно подтвердить..
подтверждение "заглавных букв" - считать "слово" после "заглавной буквы" и найти совпадение в тексте
если найдётся совпадение, но вместо заглавной буквы будет стоять другая буква - можно считать "заглавную букву" доказанной
и даже занести её в ту же табличку на против соответствующей "строчной буквы"
если одной "заглавной букве" будет соответствовать несколько "строчных букв" то нужно считать, что это исключение
- вычеркнуть символ из списка "заглавных букв" и не применять к нему это правило.
если есть несколько исключений, то можно считать, что это правило не работает на данном тексте.


(5) Дополнительные правила - "цифры" это сложный разбор текста...
"цифры" могут входить во все 3 группы, но практически всегда идут вместе друг с другом
это работа для небольшой базу данных...
нужно прочитать текст и сделать табличку из всех сочетаний всех символов, которые встречаются в тексте,
подсчитав количество таких сочетаний.
при разборе нужно принять во внимание, что, например, "б" скорее всего никогда не встретится с "щ" но оба символа встретятся с "о"
тут можно использовать порог, например "цифра с 80% вероятностью"
но, нужно помнить, что требуется проанализировать БОЛЬШОЙ объём текста
и всё равно - не факт, что удастся корректно выделить "цифры"

Ответ заменил

Но мне кажется, вы как-то притянули решение к ответу.

В задании указано "Анна Каренина" как пример, т.е. язык оригнала - русский. Именно поэтому я написал, что язык известен. Решение я даже и не собирался притягивать, частотный анализ характерен для дешифрации текста закодированного к примеру Шифром Цезаря, только смещение в данном случае нулевое.

Как пример: Александр Бушков. Волчья стая(нет у меня в эл. виде "Анны"). Первые три главы.
Общее количество символов:88789
[table]
[row][col]символ[/col][col]НЕХ-код[/col][col]количество[/col][/row]
[row][col] [/col][col]0A[/col][col]1320[/col][/row]
[row][col] [/col][col]0D[/col][col]1320[/col][/row]
[row][col] [/col][col]20[/col][col]15959[/col][/row]
[row][col]![/col][col]21[/col][col]49[/col][/row]
[row][col]"[/col][col]22[/col][col]140[/col][/row]
[row][col]([/col][col]28[/col][col]33[/col][/row]
[row][col])[/col][col]29[/col][col]33[/col][/row]
[row][col]*[/col][col]2A[/col][col]1[/col][/row]
[row][col],[/col][col]2C[/col][col]1586[/col][/row]
[row][col]-[/col][col]2D[/col][col]1156[/col][/row]
[row][col].[/col][col]2E[/col][col]1038[/col][/row]
[row][col]1[/col][col]31[/col][col]35[/col][/row]
[row][col]3[/col][col]33[/col][col]1[/col][/row]
[row][col]5[/col][col]35[/col][col]1[/col][/row]
[row][col]:[/col][col]3A[/col][col]61[/col][/row]
[row][col];[/col][col]3B[/col][col]4[/col][/row]
[row][col]?[/col][col]3F[/col][col]87[/col][/row]
[row][col]e[/col][col]65[/col][col]1[/col][/row]
[row][col]p[/col][col]70[/col][col]2[/col][/row]
[row][col]r[/col][col]72[/col][col]1[/col][/row]
[row][col]А[/col][col]C0[/col][col]73[/col][/row]
[row][col]Б[/col][col]C1[/col][col]58[/col][/row]
[row][col]В[/col][col]C2[/col][col]185[/col][/row]
[row][col]Г[/col][col]C3[/col][col]78[/col][/row]
[row][col]Д[/col][col]C4[/col][col]64[/col][/row]
[row][col]Е[/col][col]C5[/col][col]20[/col][/row]
[row][col]Ж[/col][col]C6[/col][col]6[/col][/row]
[row][col]З[/col][col]C7[/col][col]32[/col][/row]
[row][col]И[/col][col]C8[/col][col]46[/col][/row]
[row][col]Й[/col][col]C9[/col][col]2[/col][/row]
[row][col]К[/col][col]CA[/col][col]74[/col][/row]
[row][col]Л[/col][col]CB[/col][col]19[/col][/row]
[row][col]М[/col][col]CC[/col][col]58[/col][/row]
[row][col]Н[/col][col]CD[/col][col]96[/col][/row]
[row][col]О[/col][col]CE[/col][col]61[/col][/row]
[row][col]П[/col][col]CF[/col][col]93[/col][/row]
[row][col]Р[/col][col]D0[/col][col]29[/col][/row]
[row][col]С[/col][col]D1[/col][col]122[/col][/row]
[row][col]Т[/col][col]D2[/col][col]55[/col][/row]
[row][col]У[/col][col]D3[/col][col]10[/col][/row]
[row][col]Ф[/col][col]D4[/col][col]18[/col][/row]
[row][col]Х[/col][col]D5[/col][col]7[/col][/row]
[row][col]Ц[/col][col]D6[/col][col]3[/col][/row]
[row][col]Ч[/col][col]D7[/col][col]34[/col][/row]
[row][col]Ш[/col][col]D8[/col][col]18[/col][/row]
[row][col]Ь[/col][col]DC[/col][col]2[/col][/row]
[row][col]Э[/col][col]DD[/col][col]47[/col][/row]
[row][col]Ю[/col][col]DE[/col][col]1[/col][/row]
[row][col]Я[/col][col]DF[/col][col]13[/col][/row]
[row][col]а[/col][col]E0[/col][col]5633[/col][/row]
[row][col]б[/col][col]E1[/col][col]1054[/col][/row]
[row][col]в[/col][col]E2[/col][col]2755[/col][/row]
[row][col]г[/col][col]E3[/col][col]1038[/col][/row]
[row][col]д[/col][col]E4[/col][col]1875[/col][/row]
[row][col]е[/col][col]E5[/col][col]5326[/col][/row]
[row][col]ж[/col][col]E6[/col][col]641[/col][/row]
[row][col]з[/col][col]E7[/col][col]1120[/col][/row]
[row][col]и[/col][col]E8[/col][col]4310[/col][/row]
[row][col]й[/col][col]E9[/col][col]871[/col][/row]
[row][col]к[/col][col]EA[/col][col]2572[/col][/row]
[row][col]л[/col][col]EB[/col][col]3218[/col][/row]
[row][col]м[/col][col]EC[/col][col]1878[/col][/row]
[row][col]н[/col][col]ED[/col][col]4232[/col][/row]
[row][col]о[/col][col]EE[/col][col]7010[/col][/row]
[row][col]п[/col][col]EF[/col][col]1840[/col][/row]
[row][col]р[/col][col]F0[/col][col]3112[/col][/row]
[row][col]с[/col][col]F1[/col][col]3360[/col][/row]
[row][col]т[/col][col]F2[/col][col]3893[/col][/row]
[row][col]у[/col][col]F3[/col][col]1883[/col][/row]
[row][col]ф[/col][col]F4[/col][col]126[/col][/row]
[row][col]х[/col][col]F5[/col][col]576[/col][/row]
[row][col]ц[/col][col]F6[/col][col]234[/col][/row]
[row][col]ч[/col][col]F7[/col][col]963[/col][/row]
[row][col]ш[/col][col]F8[/col][col]636[/col][/row]
[row][col]щ[/col][col]F9[/col][col]223[/col][/row]
[row][col]ъ[/col][col]FA[/col][col]14[/col][/row]
[row][col]ы[/col][col]FB[/col][col]1185[/col][/row]
[row][col]ь[/col][col]FC[/col][col]1227[/col][/row]
[row][col]э[/col][col]FD[/col][col]141[/col][/row]
[row][col]ю[/col][col]FE[/col][col]388[/col][/row]
[row][col]я[/col][col]FF[/col][col]1303[/col][/row]
[/table]