В этой статье будет описан частотный анализ текста. Поскольку в предыдущих статьях уже дан довольно объёмный теоретический материал, то чтобы его усвоить не помешала бы практика. Полезней было бы после каждой теоретической статьи делать что-нибудь практическое для закрепления. Но это было бы довольно скучно. Особенно в самом начале. Поэтому я решил сделать это сейчас.
Частотный анализ текста делается на основе предположения, что для каждого языка существует собственное распределение частоты повторения букв. Например, в русском языке наиболее часто встречаемая буква это О. А наиболее редко — Ъ.
Алгоритм
Для начала объявим две переменные. В одной будет наш текст. В другой буквы по порядку.
(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 не так уж сложно. Разумеется здесь ещё есть некоторые возможности для усовершенствования. Это и чтение из файла, и анализ не только букв, но и биграмм-триграмм. К тому же можно было бы экспортировать данные в разных форматах и строить графики. Это всё оставим для следующей статьи.
Частотный анализ текста: 1 комментарий