© Иван Рощин, Москва

Автоматическое определение кодировки текста

(«Радиомир. Ваш компьютер» 10/2001)
Дата последнего редактирования: 26.11.2002.

При написании программы для работы с текстовыми файлами мне надо было учесть, что они могут быть в одной из двух кодировок: ALT (так называемая альтернативная кодировка) или WIN (кодировка русской версии Windows). Указывать кодировку каждого текстового файла вручную не хотелось, и я решил реализовать в программе автоматическое определение кодировки. Итак, спешу поделиться результатами своих исследований!

Коды русских букв, как известно, расположены во второй половине кодовой таблицы. Посмотрим, как различаются кодировки ALT и WIN (для удобства показаны только русские буквы):

Что мы видим? Коды Е0h—EFh, и только они, в обеих кодировках соответствуют русским буквам, — но разным: для ALT это буквы «р»—«я», а для WIN — буквы «а»—«п».

Теперь вспомним, что в тексте на русском языке различные буквы встречаются с разной частотой (табл. 3). Этим мы и воспользуемся для определения кодировки текста.

Пусть c₁, c₂ — два байта из диапазона Е0h—EFh. В кодировке ALT им соответствуют буквы a₁ и a₂, в кодировке WIN — w₁ и w₂. Частоты встречи этих букв в некотором «среднем» тексте — f(a₁), f(a₂), f(w₁) и f(w₂).

Выберем c₁ и c₂ так, чтобы в кодировке ALT буква, соответствующая c₁, встречалась чаще, чем буква, соответствующая c₂ (т.е. f(a₁) > f(a₂)), а в кодировке WIN, напротив, буква, соответствующая c₁, встречалась реже, чем буква, соответствующая c₂ (т.е. f(w₁) < f(w₂)).

Тогда для определения кодировки достаточно подсчитать, сколько раз в тексте встретится байт c₁ (обозначим это число n(c₁)) и сколько раз — c₂ (обозначим это число n(c₂)). Если n(c₁) > n(c₂), будем считать, что текст в кодировке ALT, иначе — в кодировке WIN. При равенстве n(c₁) и n(c₂) будем выбирать кодировку случайным образом, с равной вероятностью ALT и WIN.

Очевидно, существует не одна пара (c₁, c₂), обладающая указанным выше свойством. Какую же из них выбрать, чтобы вероятность правильного определения кодировки была наибольшей?

При определении кодировки возможны четыре различных варианта:

1. текст в кодировке ALT правильно распознан как ALT;
2. текст в кодировке WIN правильно распознан как WIN;
3. текст в кодировке ALT ошибочно распознан как WIN;
4. текст в кодировке WIN ошибочно распознан как ALT.

Уменьшив вероятности вариантов 3 и 4, мы тем самым увеличим вероятности вариантов 1 и 2, а значит, повысим надёжность определения кодировки.

Как мы можем уменьшить вероятность варианта 3 (текст в кодировке ALT ошибочно распознаётся как WIN)? Очевидно, для этого разница между f(a₁) и f(a₂) должна быть как можно большей. Ведь в реальном тексте, кодировка которого распознаётся, частоты букв a₁ и a₂ не будут точно совпадать с f(a₁) и f(a₂), и если f(a₁) и f(a₂) достаточно близки, то легко может случиться так, что в тексте окажется больше букв a₂, чем a₁, и в результате кодировка будет определена неправильно.

Совершенно аналогично, для уменьшения вероятности варианта 4 разница между f(w₁) и f(w₂) также должна быть как можно большей.

Итак, мы должны максимизировать величины |f(a₁)–f(a₂)| и |f(w₁)–f(w₂)|, или, что то же самое, минимизировать обратные величины. Выберем для этого следующий критерий: сумма квадратов обратных величин должна быть наименьшей.

Переберём (конечно, не вручную, а с помощью специально написанной программы) все возможные пары (c₁, c₂), удовлетворяющие условиям f(a₁) > f(a₂) и f(w₁) < f(w₂), чтобы выбрать из них лучшие в смысле вышеописанного критерия (табл. 4).

Наилучшей парой оказывается (E2h, EEh). Таким образом, если в тексте больше байтов E2h, чем EEh, то считаем, что этот текст в кодировке ALT; если наоборот — в кодировке WIN.

Очевидно, что чем меньше анализируемый текст, тем больше (в среднем) частоты букв a₁ и a₂ в нём будут отличаться от f(a₁) и f(a₂) (а частоты букв w₁ и w₂ — от f(w₁) и f(w₂)), и тем меньше вероятность правильного определения кодировки (рис. 1).

Рис. 1. Зависимость вероятности правильного определения кодировки (P) от длины текста (L). В анализируемых текстах буквы «а»—«я» составляли в среднем 70%, тексты в кодировках ALT и WIN встречались с равной вероятностью, определение кодировки происходило по паре байтов (E2h, EEh).

Как видим, при уменьшении длины текста вероятность стремится к 50% — такой же точности мы могли бы добиться, просто определяя кодировку подбрасыванием монетки.

Также понятно, что при уменьшении доли букв «а»—«я» в тексте (скажем, если текст содержит и русские, и английские слова или насыщен псевдографикой) вероятность правильного определения кодировки снижается.

Чтобы её увеличить, можно последовательно определять кодировку по каждой из трёх наилучших пар: (E2h, EEh), (E1h, EEh) и (E1h, E5h), а окончательный результат устанавливать методом голосования (рис. 2).

Рис. 2. То же, что и на первом графике, но определение кодировки происходило по трём парам байтов: (E2h, EEh), (E1h, EEh) и (E1h, E5h).