Пора расширить наш частотный анализатор текстов, для того, чтобы подсчитывать частоту повторения не только отдельных букв, но и их сочетаний — биграмм и триграмм. Прошлый раз мы получили довольно простой анализатор, но и область применения его не так широка. В этот раз мы нарастим функционал. Здесь мы преследуем две цели, первая — это приобретение практических навыков программирования на языке common lisp. Вторую я озвучу в следующих заметках, поскольку мы ещё вернёмся к анализу текста.

Терминология

Биграмма это сочетание из двух букв алфавита. Триграмма из трёх. Из комбинаторики становится понятно, что количество всевозможных биграмм русского языка равно 1089 (33^2). Тогда как для триграмм это число равно 35937 (33^3). Однако, эти числа не совсем справедливы, например биграммы, состоящей из двух мягких знаков быть не может. Даже если считать биграмму как любые два символа в слепленном тексте без пробелов, то всё равно мы никогда не встретим два идущих подряд мягких знака, аналогично с твёрдыми знаками. Поэтому числа преведённые выше являются скорее верхними границами, чем реальными значениями.

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

Алгоритм

Алгоритм для расчёта частоты триграмм отличается от расчёта частоты каждой буквы тем лишь, что каждый раз мы ищем в хэш-таблице не один символ, а строку из нескольких символов. Идея алгоритма такова, что мы заводим ещё одну переменную в цикле loop. Затем каждую итерацию мы добавляем в конец этой переменной символ и выбрасываем первый символ если нужно. Таким образом, у нас на каждой итерации, кроме нескольких первых, получается строка их нескольких символов. Вот пример кода:

(defun get-n-gramm(text &optional (n 2) (container nil))
  "Returns hash-table with downcased n-grams as keys and frequencies as values"
  (when (null container) (setf container (make-hash-table :test 'equal)))
  (loop
     for chr across text
     for ngram = ""
     then (let
              ((lngram ngram) (lchar (char-downcase chr)))
            (when (alpha-char-p lchar)
              (if (= (length lngram) n)
                  (setf lngram (concatenate 'string (subseq lngram 1) (list lchar)))
                  (setf lngram (concatenate 'string lngram (list lchar))))
              (if (= (length lngram) n)
                  (let ((frequency (gethash lngram container 0)))
                    (setf (gethash lngram container) (+ 1 frequency)))))
            lngram)
     finally (return-from get-n-gramm container)))

Здесь я сразу обернул всё в функцию, которая принимает строку в качестве текста и два опциональных параметра. Это количество букв в строке и хэш-таблица куда всё складывать.

Все исходные коды можно посмотреть в моём репозитории на github.