Лингвистика. Частотный анализ — 2.

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

Впрочем у частотного анализа букв есть и более практические применения. Пример — определение кодировок текстов. На тему определения по частоте букв рекомендую статьи Ивана Рощина Автоматическое определение кодировки текста и Автоматическое определение кодировки текста — 2.

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

Я приведу в пример другой подход — определение кодировки по «карте расстояний».

Что это такое? Карта расстояний — это матрица разниц в численном представлении букв. Для каждой буквы мы берём её значение в кодовой таблице, откладываем по осям x и y весь алфавит и прописываем в клетки разницу между значениями букв.

В конечном итоге все они не понадобятся, будут нужны лишь наиболее частые гласные.

Например, для кодировки cp1251 разница расстояний между наиболее частыми буквами:

а-и: -8, а-е: -5, е-и: -3, а-о: -15, е-о: -12, и-о: -7 и обратные им и-а: 8, е-а: 5, и-е: 3, о-а: 15, о-е: 12, о-и: 7

Для кодировки KOI8-R расчёты будут несколько иными, так как буквы там идут не в алфавитном порядке, но незначительно так как это затрагивает только букву расстояния до буквы е.

Алгоритм определения кодировки в этом случае сводится к следующим операциям:

1. Расчёт частоты встречаемости букв в тексте.

2. Выборка 8 наиболее частых букв

3. Наложение матриц расстояний между букв в выборке, на матрицу расстояний между гласными в данной кодировке.

4. При совпадении, определение кодировки и декодирование текста.

Ограничения:

1. Требует доработки для поддержки текстов где много слов из заглавных букв.

2. Алгоритм работает на предположении что 4 наиболее популярные гласные входят в 8-ку наиболее популярных букв. Для небольших текстов это может быть не так.

3. Алгоритм не работает на текстах прошедших многократное преобразование кодировок. Для таких случаев существуют другие алгоритмы.

Примеры кода приводить не буду, желающие могут попробовать свои силы сами. Скажу лишь что и этот алгоритм 100% гарантии не даёт, а приближение к 100% определению возможно уже при использовании словарей, причём относительно небольших по размеру.

P.S. На самом деле даже анализ 8 букв — это с большим запасом. В 99% случаев первые 5 букв по частоте — это о, е, а, н, и.

About This Author

Яндекс.Метрика