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

Частотный анализ текста делается на основе предположения, что для каждого языка существует собственное распределение частоты повторения букв. Например, в русском языке наиболее часто встречаемая буква это О. А наиболее редко — Ъ.

Алгоритм

Для начала объявим две переменные. В одной будет наш текст. В другой буквы по порядку.

(defparameter *txt* "Частотный анализ текста")
(defparameter *frequency* (make-hash-table))

Для того, чтобы посимвольно пройтись по тексту используем цикл loop:

(loop for chr across *txt* do (format t "~C" chr))

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

(loop for chr across *txt* do 
     (let ((frequency (gethash chr *frequency* 0)))
           (setf (gethash chr *frequency*) (+ 1 frequency))))

Теперь выведем то, что получилось в консоль.

(loop for k being the hash-keys in *frequency* using (hash-value v)
    do (format t "~A ~A ~%" k v))

Как видно, не совсем верный результат получился. Это из-за разного регистра букв. Исправим эту досадную оплошность с помощью функции char-downcase.

Вот, что у нас получилось.

(loop for chr across *txt* do 
    (let* ((lchar (char-downcase chr))
           (frequency (gethash lchar *frequency* 0)))
                      (setf (gethash lchar *frequency*) (+ 1 frequency))))

Если вывести значения в таблице ещё раз, то получится более приемлемый результат. Однако, нам мало что говорит количество вхождений, удобней было бы знать процент.

(loop for k being the hash-keys in *frequency* using (hash-value v)
      do (format t "~A ~,2F% ~%" k (/ (* 100.0 v) (length *txt*))))

Сортировка

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

(defun hash-table-alist (table)
    "Returns an association list containing the keys and values of hash table TABLE."
    (let ((alist nil))
         (maphash (lambda (k v)
                  (push (cons k v) alist))
                  table)
         alist))

Эта функция ещё может пригодится нам.

Теперь выполним сортировку данного списка по значению и выведем его, для вывода используем деструктуризацию.

(loop for (chr . frq) in (sort (hash-table-alist *frequency*) #'> :key #'cdr)
      do (format t "~C ~,2F%~%" chr (/ (* 100.0 frq) (length *txt*))))

 

Итоги

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