Сергей Холодилов (fat_crocodile) wrote,
Сергей Холодилов
fat_crocodile

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

(1) равномерно распределённых английских букв с пробелом
(2) букв с правильными индивидуальными частотами (т.е. как в обычном английском тексте)
(3) с правильными частотами биграмм
(4) правильными частотами триграмм
(5) слов с правильными индивидуальными частотами
(6) слова с правильными вероятностями пар слов

Это просто примеры, так что они не очень длинные: 50-100 букв, 30-45 слов. Помимо того что есть всегда, доступны таблицы частот и книги случайных чисел (занимательные должно быть!).

В чём трудность. Чтобы строить биграммы тривиальным способом по буквам, нужно 27 таблиц условных вероятностей (27 == алфавит + пробел). Вроде обозримо, особенно если таблицы уже есть. Но чтобы строить триграммы, таких таблиц нужно уже 729. Для того чтобы привести пример в статье это кажется несколько избыточно. Со словами всё ещё хуже, таблицу условных вероятностей для слов даже представить страшно. Да даже просто частот слов.

The first two samples were constructed by the use of a book of random numbers in conjunction with (for example 2) a table of letter frequencies. This method might have been continued for (3), (4) and (5), since digram, trigram and word frequency tables are available, but a simpler equivalent method was used. To construct (3) for example, one opens a book at random and selects a letter at random on the page. This letter is recorded. The book is then opened to another page and one reads until this letter is encountered. The succeeding letter is then recorded. Turning to another page this second letter is searched for and the succeeding letter recorded, etc. A similar process was used for (4), (5) and (6). It would be interesting if further approximations could be constructed, but the labor involved becomes enormous at the next stage.
Tags: математика
Subscribe

  • (no subject)

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

  • (no subject)

    Наконец вроде осознал, когда и зачем аксиома выбора нужна, а когда она не нужна. Если у нас есть одно непустое множество X и нам нужно взять…

  • CRC-3: как его обойти

    CRC не криптографически-стойкий алгоритм, он предназначен для обнаружения ошибок, вызванных неразумными обстоятельствами, а не разумным противником.…

  • Post a new comment

    Error

    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 3 comments