Страница Ивана Рощина > Статьи >

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

ZXNet: 500:95/462.53
E-mail: bestview@mtu-net.ru
WWW: http://www.ivr.da.ru

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

Радиомир. Ваш компьютер» 5, 6/2002, 6/2004)
Исправленная и дополненная версия.
Дата последнего редактирования: 18.01.2004.

В [1] я рассказывал о способе автоматического определения кодировки текста для случая, когда текст может быть в одной из двух кодировок: ALT или WIN. Кратко напомню, в чём этот способ заключался.

Кодам Е0h—EFh в кодировке ALT соответствуют буквы «р»—«я», а в кодировке WIN — «а»—«п» (табл. 1, 2). Можно выбрать такие два кода из этого промежутка, чтобы для одной кодировки буква, соответствующая первому коду, в среднем чаще встречалась в текстах, чем буква, соответствующая второму коду (то есть первый код встречался в текстах чаще второго), а для другой кодировки — наоборот. Тогда, просто посмотрев, какой из этих двух кодов чаще встречается в анализируемом тексте, можно сделать вывод о его кодировке.

Несмотря на то, что такой способ прост, быстр и достаточно надёжен, область его применения ограничена.

Во-первых, анализируемый текст должен состоять в основном из строчных букв, ведь именно на подсчёте их количества основано определение кодировки. А если текст записан прописными буквами, способ ничем нам не поможет.

Во-вторых, способ «привязан» к кодировкам ALT и WIN, и адаптировать его для другой пары кодировок можно не всегда. Пусть, например, мы хотим различать тексты в кодировках ALT и KOI8-R (далее просто KOI). В кодировке ALT русским строчным буквам соответствуют коды A0h—AFh и E0h—EFh, а в KOI — C0h—DFh (табл. 1, 3). Как видите, эти два множества не пересекаются, а значит, способ в данном случае непригоден.

Примечание: а вот пару кодировок WIN и KOI (табл. 2, 3), несмотря на то, что там множества кодов строчных букв также не пересекаются, различить можно. Для этого способ придётся несколько изменить. Заметим, что в кодировке WIN коды C0h—DFh соответствуют прописным буквам, а E0h—FFh — строчным, причём порядок следования прописных и строчных букв один и тот же. В кодировке KOI — точно то же самое, только сначала идут строчные буквы, а затем прописные (разумеется, порядок букв в этих кодировках различен). Так вот, выберем из промежутка C0h—DFh два кода по такому же принципу, как для пары кодировок ALT и WIN. Обозначим их c1 и c2, а их количество в анализируемом тексте — n(c1) и n(c2). При определении кодировки будем подсчитывать общее количество прописных и строчных букв, т.е. n(c1)+n(c1+20h) и n(c2)+n(c2+20h). Сравнив эти две величины, мы сможем сделать вывод о кодировке текста. При этом правильность определения кодировки не будет зависеть от того, прописными или строчными буквами записан текст!

Табл. 1. Кодировка ALT
0 1 2 3 4 5 6 7 8 9 A B C D E F
8 А Б В Г Д Е Ж З И Й К Л М Н О П
9 Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я
A а б в г д е ж з и й к л м н о п
B
C
D
E р с т у ф х ц ч ш щ ъ ы ь э ю я
F
Табл. 2. Кодировка WIN
0 1 2 3 4 5 6 7 8 9 A B C D E F
8
9
A
B
C А Б В Г Д Е Ж З И Й К Л М Н О П
D Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я
E а б в г д е ж з и й к л м н о п
F р с т у ф х ц ч ш щ ъ ы ь э ю я
Табл. 3. Кодировка KOI
0 1 2 3 4 5 6 7 8 9 A B C D E F
8
9
A
B
C ю а б ц д е ф г х и й к л м н о
D п я р с т у ж в ь ы з ш э щ ч ъ
E Ю А Б Ц Д Е Ф Г Х И Й К Л М Н О
F П Я Р С Т У Ж В Ь Ы З Ш Э Щ Ч Ъ

Когда я решил реализовать в своей программе BestView автоматическое определение кодировки при просмотре текстовых файлов (для трёх наиболее часто встречающихся кодировок: ALT, WIN и KOI), возникла необходимость в отыскании нового, свободного от вышеописанных недостатков способа определения кодировки текста.

Размышляя над этой проблемой, я вспомнил о прочитанной достаточно давно статье [2]. Там упоминалось о простейшем способе орфографического контроля текста, заключающегося в следующем: не все возможные сочетания букв встречаются в словах русского языка, и если в слове обнаружено такое невстречающееся или, иными словами, недопустимое сочетание букв — значит, слово написано с ошибкой. И я подумал: может быть, удастся приспособить это для определения кодировки?

Вы, наверное, неоднократно замечали: если кодировка текста определена неправильно, он превращается в какую-то абракадабру. Логично предположить, что при этом появляются недопустимые сочетания букв. Тогда получается, что для определения кодировки достаточно выбрать из трёх возможных вариантов — ALT, WIN и KOI — тот, при котором в тексте не будет недопустимых сочетаний.

Решив проверить это на практике, я начал с того, что построил таблицу допустимых сочетаний из двух букв (табл. 4), обработав для этого 860-килобайтный текстовый файл.

Табл. 4
Вторая буква
а б в г д е ж з и й к л м н о п р с т у ф х ц ч ш щ ъ ы ь э ю я
Первая буква а + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
б + + + + + + + + + + + + + + + + + + + + + + + + + + +
в + + + + + + + + + + + + + + + + + + + + + + + + + + +
г + + + + + + + + + + + + + + + + + +
д + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
е + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
ж + + + + + + + + + + + + + + + + + +
з + + + + + + + + + + + + + + + + + + + + + + + + + + +
и + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
й + + + + + + + + + + + + + + + + + + +
к + + + + + + + + + + + + + + + + +
л + + + + + + + + + + + + + + + + + + + + + + + + + + +
м + + + + + + + + + + + + + + + + + + + + + + + +
н + + + + + + + + + + + + + + + + + + + + + + + + + + +
о + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
п + + + + + + + + + + + + + + + + + + + +
р + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
с + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
т + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
у + + + + + + + + + + + + + + + + + + + + + + + + + + +
ф + + + + + + + + + + + + +
х + + + + + + + + + + + + + + + + + +
ц + + + + + + + + + +
ч + + + + + + + + + + + + + + +
ш + + + + + + + + + + + + + + + + + + + +
щ + + + + + + + +
ъ + + +
ы + + + + + + + + + + + + + + + + + + + + + + + +
ь + + + + + + + + + + + + + + + + + + + + + +
э + + + + + + + + + + + + + +
ю + + + + + + + + + + + + + + + + + + + + + +
я + + + + + + + + + + + + + + + + + + + + + + + + +

Оказалось, что из всех возможных сочетаний (32*32=1024) лишь 709 (чуть больше 69%) являются допустимыми.

С помощью этой таблицы уже нетрудно было проверить, действительно ли при неправильном определении кодировки появляются недопустимые сочетания букв (табл. 5).

Табл. 5
Исходная кодировка текста
ALT WIN KOI
Распознан как ALT
    На примере этого текста вы можете
увидеть, что при неправильном определении
кодировки появляются недопустимые сочетания
букв (они подчеркнуты).
    Этот текст содержит как строчные, так
и ПРОПИСНЫЕ БУКВЫ. СИМВОЛЫ С КОДАМИ В
ДИАПАЗОНЕ 80h-FFh, НЕ ОТНОСЯЩИЕСЯ К
БУКВАМ (ОНИ МОГУТ ПОЯВИТЬСЯ В РЕЗУЛЬТАТЕ
НЕПРАВИЛЬНОГО ОПРЕДЕЛЕНИЯ КОДИРОВКИ ТЕКСТА)
ОБОЗНАЧЕНЫ ВОПРОСИТЕЛЬНЫМИ ЗНАКАМИ.
    ?р я?шьх?х ??юую ?хъ??р т? ьюцх?х
?тшфх??, ??ю я?ш эхя?ртшы?эюь юя?хфхыхэшш
ъюфш?ютъш яю?ты????? эхфюя???шь?х ?ю?х?рэш?
с?ът (юэш яюф?х?ъэ???).
    ??ю? ?хъ?? ?юфх?цш? ъръ ???ю?э?х, ?ръ
ш ????????? ?????. ??????? ? ?????? ?
????????? 80h-FFh, ?? ??????????? ?
?????? (??? ????? ????????? ? ??????????
????????????? ??????????? ????????? ??????)
?????????? ??????????????? ???????.
    ю? ??????? ????? ?????? ?? ??????
???????, ??? ??? ???????????? ???????????
????????? ?????????? ???????????? ?????????
???? (??? ???????????).
    ???? ????? ???????? ??? ????????, ???
? ??я?щ?ю?х т?ы??. ?щэ?яь? ? ыяфсэщ ?
фщс?с?яюх 80h-FFh, юх я?юя???щх?? ы
т?ы?сэ (яющ эяч?? ?я??щ???? ? ?х??ь??с?х
юх??с?щь?юячя я??хфхьхющ? ыяфщ?я?ыщ ?хы??с)
ятя?юс?хю? ?я??я?щ?хь?ю?эщ ?юсысэщ.
Распознан как WIN
    ?? ?а???а? нв??? в??бв? ?л ????в?
г????вм, зв? ?а? ???а????м??? ??а????????
????а???? ??п??повбп ?????гбв??л? б?з?в???п
?г?? (??? ???з?а??гвл).
    ?в?в в??бв б???а??в ??? бва?з?л?, в??
? ????????? ?????. ??????? ? ?????? ?
????????? 80h-FFh, ?? ??????????? ?
?????? (??? ????? ????????? ? ??????????
????????????? ??????????? ????????? ??????)
?????????? ??????????????? ???????.
    На примере этого текста вы можете
увидеть, что при неправильном определении
кодировки появляются недопустимые сочетания
букв (они подчеркнуты).
    Этот текст содержит как строчные, так
и ПРОПИСНЫЕ БУКВЫ. СИМВОЛЫ С КОДАМИ В
ДИАПАЗОНЕ 80h-FFh, НЕ ОТНОСЯЩИЕСЯ К
БУКВАМ (ОНИ МОГУТ ПОЯВИТЬСЯ В РЕЗУЛЬТАТЕ
НЕПРАВИЛЬНОГО ОПРЕДЕЛЕНИЯ КОДИРОВКИ ТЕКСТА)
ОБОЗНАЧЕНЫ ВОПРОСИТЕЛЬНЫМИ ЗНАКАМИ.
    оБ РТЙНЕТЕ ЬФПЗП ФЕЛУФБ ЧЩ НПЦЕФЕ
ХЧЙДЕФШ, ЮФП РТЙ ОЕРТБЧЙМШОПН ПРТЕДЕМЕОЙЙ
ЛПДЙТПЧЛЙ РПСЧМСАФУС ОЕДПРХУФЙНЩЕ УПЮЕФБОЙС
ВХЛЧ (ПОЙ РПДЮЕТЛОХФЩ).
    ьФПФ ФЕЛУФ УПДЕТЦЙФ ЛБЛ УФТПЮОЩЕ, ФБЛ
Й ртпрйуоще вхлчщ. уйнчпмщ у лпдбнй ч
дйбрбъпое 80h-FFh, ое пфопусэйеус л
вхлчбн (пой нпзхф рпсчйфшус ч теъхмшфбфе
оертбчймшопзп пртедемеойс лпдйтпчлй фелуфб)
пвпъобюеощ чпртпуйфемшощнй ъоблбнй.
Распознан как KOI
    ?? ?Ю???Ю? МБ??? Б??АБ? ?К ????Б?
Ц????БЛ, ГБ? ?Ю? ???Ю????Л??? ??Ю????????
????Ю???? ??О??ОНБАО ?????ЦАБ??К? А?Г?Б???О
?Ц?? (??? ???Г?Ю??ЦБК).
    ?Б?Б Б??АБ А???Ю??Б ??? АБЮ?Г?К?, Б??
? ????????? ?????. ??????? ? ?????? ?
????????? 80h-FFh, ?? ??????????? ?
?????? (??? ????? ????????? ? ??????????
????????????? ??????????? ????????? ??????)
?????????? ??????????????? ???????.
    мЮ ОПХЛЕПЕ ЩРНЦН РЕЙЯРЮ БШ ЛНФЕРЕ
СБХДЕРЭ, ВРН ОПХ МЕОПЮБХКЭМНЛ НОПЕДЕКЕМХХ
ЙНДХПНБЙХ ОНЪБКЪЧРЯЪ МЕДНОСЯРХЛШЕ ЯНВЕРЮМХЪ
АСЙБ (НМХ ОНДВЕПЙМСРШ).
    щРНР РЕЙЯР ЯНДЕПФХР ЙЮЙ ЯРПНВМШЕ, РЮЙ
Х опнохямше асйбш. яхлбнкш я йндюлх б
дхюоюгнме 80h-FFh, ме нрмняъыхеяъ й
асйбюл (нмх лнцср онъбхрэяъ б пегскэрюре
меопюбхкэмнцн нопедекемхъ йндхпнбйх рейярю)
нангмювемш бнопняхрекэмшлх гмюйюлх.
    На примере этого текста вы можете
увидеть, что при неправильном определении
кодировки появляются недопустимые сочетания
букв (они подчеркнуты).
    Этот текст содержит как строчные, так
и ПРОПИСНЫЕ БУКВЫ. СИМВОЛЫ С КОДАМИ В
ДИАПАЗОНЕ 80h-FFh, НЕ ОТНОСЯЩИЕСЯ К
БУКВАМ (ОНИ МОГУТ ПОЯВИТЬСЯ В РЕЗУЛЬТАТЕ
НЕПРАВИЛЬНОГО ОПРЕДЕЛЕНИЯ КОДИРОВКИ ТЕКСТА)
ОБОЗНАЧЕНЫ ВОПРОСИТЕЛЬНЫМИ ЗНАКАМИ.

Да, как можно видеть, недопустимые сочетания действительно появляются — но не всегда. Так, если анализируемый текст — в кодировке ALT и записан прописными буквами, то в нём не появится недопустимых сочетаний, если считать, что его кодировка — WIN или KOI. Дело в том, что коды прописных букв в кодировке ALT (80h—9Fh) не являются кодами букв в этих кодировках. Аналогичная ситуация возникает, если мы имеем текст в кодировке WIN, записанный прописными буквами: если считать, что его кодировка — ALT, недопустимых сочетаний также не появится. То же самое будет и в случае, когда текст в кодировке KOI записан строчными буквами, а мы рассматриваем вариант, что его кодировка — ALT.

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

Метод рассчитан на то, что при правильном определении кодировки в тексте не будет недопустимых сочетаний. Но они могут быть по разным причинам: ошибки, опечатки в тексте, использование каких-либо специальных терминов или очень редко встречающихся слов. Это надо учесть. При рассмотрении всех трёх вариантов может не найтись ни одного, где не было бы недопустимых сочетаний, — тогда выбираем тот вариант, где их меньше (а если таких вариантов несколько — выбираем из них тот, где больше общее количество сочетаний).

Может случиться так, что при рассмотрении «правильного» варианта недопустимые сочетания будут — а при рассмотрении «неправильного» их не будет за счёт того, что коды букв текста не будут в этом варианте кодами букв. В результате кодировка будет определена неправильно. Чтобы избежать этого, введём ещё одно условие: если при рассмотрении какого-либо варианта в тексте оказалось не более одного недопустимого сочетания, скажем, на 32 — считаем, что недопустимых сочетаний вообще нет.

Итак, сформулируем окончательный вариант алгоритма определения кодировки текста.

  1. Предположив, что текст в кодировке ALT, подсчитываем в нём количество всех 2-буквенных сочетаний (all_1) и недопустимых сочетаний (bad_1). Аналогично поступаем для кодировок WIN (получаем all_2 и bad_2) и KOI (получаем all_3 и bad_3).
  2. Производим коррекцию: обнуляем bad_1, если bad_1*32<=all_1; аналогично для bad_2 и bad_3.
  3. Сравнив bad_1, bad_2 и bad_3, выбираем из них наименьшее. Если это можно сделать однозначно, то на этом определение кодировки закончено: если меньше всех оказалось bad_1 — значит, текст в кодировке ALT; если bad_2 — WIN, bad_3 — KOI.
  4. Если же среди bad_1, bad_2 и bad_3 оказалось несколько одинаковых наименьших значений, сравниваем соотвествующие им количества всех сочетаний (если, например, наименьшими оказались bad_1 и bad_3, сравниваем all_1 и all_3). Если это можно сделать однозначно, то на этом определение кодировки закончено: наибольшее из сравниваемых значений и соответствует кодировке (скажем, если наибольшим оказалось all_1 — значит, текст в кодировке ALT).
  5. Если же среди all оказалось несколько одинаковых наибольших значений, выбираем из них одно случайным образом; по нему и выдаём ответ.

На рис. 1 показано, как точность определения кодировки с помощью этого алгоритма зависит от длины текста.

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

Если вы сравните этот график с графиками, приведёнными в [1], то увидите, что точность определения кодировки гораздо выше: график гораздо быстрее выходит на уровень 100% правильного распознавания! И это при том, что выбор одной кодировки из трёх (к тому же — для текстов как из прописных, так и из строчных букв!) — более сложная задача, чем выбор одной кодировки из двух.

С помощью данного метода можно также определять кодировку текстов, не содержащих русских букв, но содержащих символы псевдографики (скажем, в тексте имеется изображённая такими символами таблица), если используемые сочетания символов псевдографики при «неправильных» вариантах переходят в недопустимые сочетания букв. Так, в табл. 6 вы можете увидеть, во что превращаются сочетания символов псевдографики, используемые для изображения таблиц, для текста в кодировке ALT при рассмотрении вариантов, что его кодировка — WIN или KOI.

Табл. 6
ALT Здесь должен быть
рисунок.
WIN
ЪДДВДДВДДВДДВДД?
ГДДЕДДЕДДЕДДЕДД?
АДДБДДБДДБДДБДДЩ
ЙННЛННЛННЛННЛННЛНН?
МННОННОННОННОННОНН?
ИННКННКННКННКННКНН?
ЦДДТДДТДДТДДТДД?
ЗДДЧДДЧДДЧДДЧДД?
УДДРДДРДДРДДРДД?
ХННСННСННСННСННСНН?
ЖННШННШННШННШННШНН?
ФННПННПННПННПННПНН?
KOI
зддбддбддбддбдд?
цддеддеддеддедд?
юддаддаддаддадды
иммкммкммкммкммкмм?
лммнммнммнммнммнмм?
хммйммйммйммйммймм?
жддрддрддрддрдд?
гддвддвддвддвдд?
сддпддпддпддпдд?
уммяммяммяммяммямм?
фммьммьммьммьммьмм?
тммоммоммоммоммомм?

Заметим, что в данном случае лучше было бы использовать не двух-, а трёхбуквенные сочетания: тогда недопустимых сочетаний оказалось бы гораздо больше, что позволило бы более уверенно определять кодировку такого текста.

Если псевдографика содержится в тексте на русском языке, это может привести к неправильному определению его кодировки. Пример такой ситуации представлен в табл. 7.

Табл. 7
Вариант Текст Всего сочетаний Из них недопустимо
ALT

   Это пример текста на русском
языке, содержащего таблицу, сформи-
рованную с помощью псевдографических
символов.
Здесь
должен быть рисунок.
80 0
WIN

   ?в? ?а???а в??бв? ?? агбб???
п?л??, б???а??й??? в????жг, бд?а??-
а?????го б ????ймо ?б?????а?д?з?б??е
б???????.

ЪДДДДДВДДДДДДДДДДВДДДДДВДДДДДВДДДДД?
?     ?          ?     ?     ?     ?
ГДДДДДЕДДДДДДДДДДЕДДДДДЕДДДДДЕДДДДД?
?     ?          ?     ?     ?     ?
АДДДДДБДДДДДДДДДДБДДДДДБДДДДДБДДДДДЩ

112 2
KOI

   ?Б? ?Ю???Ю Б??АБ? ?? ЮЦАА???
О?К??, А???Ю??И??? Б????ФЦ, АД?Ю??-
Ю?????ЦН А ????ИЛН ?А?????Ю?Д?Г?А??Е
А???????.

здддддбддддддддддбдддддбдддддбддддд?
?     ?          ?     ?     ?     ?
цдддддеддддддддддедддддедддддеддддд?
?     ?          ?     ?     ?     ?
юдддддаддддддддддадддддадддддаддддды

112 3

Как видите, all_1=80, bad_1=0, all_2=112, bad_2=0 (т.к. 2<112/32), all_3=112, bad_3=0 (т.к. 3<112/32). Определяя кодировку в соответствии с алгоритмом, получим WIN или KOI, в то время как правильный ответ — ALT.

Почему так получается? Дело в том, что в вариантах WIN и KOI символы псевдографики переходят в русские буквы, причём образуя, в подавляющем большинстве случаев, допустимые их сочетания. Допустимых сочетаний в тексте становится гораздо больше, чем недопустимых. Недопустимые сочетания не учитываются, так как они составляют менее 1/32 от общего числа сочетаний, и в результате кодировка текста определяется неправильно.

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

Смотрите: если в тексте находится таблица, построенная с помощью псевдографических символов, например, таких:

Здесь должен быть
рисунок.

то, как нетрудно убедиться, эти символы образуют только 13 различных сочетаний:

Здесь должен быть
рисунок.

При рассмотрении различных вариантов кодировки текста некоторые из этих сочетаний перейдут в сочетания букв. Так вот, если в каждом из вариантов мы будем игнорировать повторяющиеся сочетания, то из всех сочетаний букв, получившихся из псевдографики, в каждом варианте учтены будут не более 13 — независимо от размера таблицы и количества таких таблиц в тексте! Таким образом, общее количество сочетаний в каждом варианте возрастёт за счёт псевдографики не более чем на 13 (а ведь среди этих сочетаний могут быть и недопустимые!), так что проблема решена!

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

В табл. 8 вы можете увидеть, что получается при использовании этого приёма. Отброшенные повторяющиеся сочетания перечёркнуты.

Табл. 8
Вариант Текст Всего сочетаний Из них недопустимо
ALT

   Это пример текста на русском
языке, содержащего таблицу, сформи-
рованную с помощью псевдографических
символов.
Здесь
должен быть рисунок.
74 0
WIN

   ?в? ?а???а в??бв? ?? агбб???
п?л??, б???а??й??? в????жг, бд?а??-
а?????го б ????ймо ?б?????а?д?з?б??е
б???????.

ЪДДДДДВДДДДДДДДДДВДДДДДВДДДДДВДДДДД?
?     ?          ?     ?     ?     ?
ГДДДДДЕДДДДДДДДДДЕДДДДДЕДДДДДЕДДДДД?
?     ?          ?     ?     ?     ?
АДДДДДБДДДДДДДДДДБДДДДДБДДДДДБДДДДДЩ

19 2
KOI

   ?Б? ?Ю???Ю Б??АБ? ?? ЮЦАА???
О?К??, А???Ю??И??? Б????ФЦ, АД?Ю??-
Ю?????ЦН А ????ИЛН ?А?????Ю?Д?Г?А??Е
А???????.

здддддбддддддддддбдддддбдддддбддддд?
?     ?          ?     ?     ?     ?
цдддддеддддддддддедддддедддддеддддд?
?     ?          ?     ?     ?     ?
юдддддаддддддддддадддддадддддаддддды

19 3

Как видите, теперь картина совсем другая: all_1=74, bad_1=0, all_2=19, bad_2=2, all_3=19, bad_3=3, и кодировка определяется правильно.

Дополнение. Приведу ещё один довод в пользу того, что отбрасывание повторяющихся сочетаний улучшает качество определения кодировки текста. Если в тексте несколько раз встречается какое-нибудь редкое слово или специальный термин, в котором содержится недопустимое сочетание букв, или обладающая тем же свойством аббревиатура (в которых возможны любые сочетания букв), то это недопустимое сочетание будет учтено лишь один раз, независимо от того, сколько раз оно встречается в тексте. А это уменьшит вероятность того, что при определении кодировки правильный вариант будет отвергнут из-за большого количества недопустимых сочетаний в нём.

Особенности практической реализации

Как хранить таблицу допустимых двухбуквенных сочетаний (табл. 4)? Удобно представить её в виде битового массива: первый бит соответствует сочетанию «АА», второй — «АБ», …, последний — «ЯЯ»; если сочетание допустимо, бит равен 1, иначе — 0. Тогда таблица займёт 32*32=1024 бита, или 128 байтов. Её дамп приведён ниже.

0000: FFFF FFC7 FEBE F7FB FDBF F7F9 FCBE F180
0010: FFFF F7BB FFFF FFCF DEBF D108 FFBF F1BF
0020: FFFF FFC7 1D3F 7F81 A7B6 F282 FFFF 75DB
0030: FCBF D79D FFAE FBDF FFFF FFC7 84B7 F39F
0040: FFFF FFDB FFBF FFFF FDBF FFFF FFFF E7C7
0050: 849E F012 BCBF F084 A4BA 1010 A4BE B888
0060: ACBF F70A 8486 9008 0400 0003 7FFD F7C1
0070: 7DAE 6FCB 153D FC00 7F7D E7C2 7FFD F7C3

Возможно, для более точного определения кодировки вы решите использовать вместе с таблицей двухбуквенных сочетаний и таблицу трёхбуквенных. Для её хранения, казалось бы, необходимо в 32 раза больше места, т.е. 4 КБ. Но если выбросить из всех возможных трёхбуквенных сочетаний те, которые содержат в себе недопустимое двухбуквенное сочетание (они, понятно, заведомо будут недопустимы), и хранить в таблице только информацию об оставшихся, она займёт почти вдвое меньше места. Правда, при этом доступ к элементам таблицы будет усложнён. Но на время распознавания кодировки таблицу можно «распаковать».

Как видно из графика (рис. 1), для уверенного определения кодировки достаточно проанализировать небольшой фрагмент текста. Понятно, что это гораздо выгоднее, чем просматривать весь текст, который может быть очень длинным. Но какой именно длины должен быть этот фрагмент? Если его длина всегда будет одной и той же, то в одних случаях (например, большие пробелы между словами в тексте) она будет недостаточной, а в других — избыточной. Таким образом, длина анализируемого фрагмента должна зависеть от содержимого текста. Можно предложить следующий способ: обрабатывать текст, параллельно подсчитывая all_1all_3 и bad_1bad_3, до тех пор, пока в одном из вариантов количество обнаруженных сочетаний не достигнет определённой величины (скажем, 100), или пока текст не кончится.

Да, кстати: так как и в кодировке WIN, и в KOI коды русских букв расположены в одном и том же диапазоне C0h—FFh, понятно, что общее число сочетаний в вариантах WIN и KOI будет одинаковым (all_2=all_3). А значит, программу можно упростить, подсчитывая лишь одну из этих величин.

Теперь расскажу о реализации пунктов 3—5 алгоритма. Можно, конечно, запрограммировать их «в лоб», но не советую, поскольку есть гораздо более эффективный способ.

Пусть при определении кодировки мы проходим по тексту до тех пор, пока в одном из вариантов не наберётся n сочетаний, n<256. Тогда каждая из величин all_1, all_2, all_3, bad_1, bad_2, bad_3 будет принадлежать диапазону (0..255), и для её хранения будет достаточно одного байта.

Сформируем величины bad_1', bad_2' и bad_3' следующим образом:

bad_1' = 255 – bad_1,
bad_2' = 255 – bad_2,
bad_3' = 255 – bad_3.

На ассемблере это реализуется особенно просто: чтобы вычислить 255–n, достаточно инвертировать n.

Что при этом получится? Если, скажем, bad_1 был равен нулю, то bad_1' станет равным 255, и наоборот, то есть числа (0..255) перейдут в (255..0).

Если a>b, то (255–a)<(255–b). При выполнении пункта 3, как мы помним, надо проверить, что меньше: bad_1, bad_2 или bad_3. Вместо этого можно проверить, что больше: bad_1', bad_2' или bad_3'.

Смотрите, как можно тогда переформулировать пункт 4: «Eсли среди bad_1', bad_2' и bad_3' оказалось несколько одинаковых наибольших значений, сравниваем соотвествующие им количества всех сочетаний (если, например, наибольшими оказались bad_1' и bad_3', сравниваем all_1 и all_3), определяя наибольшее из них…»

Так вот, тогда пункты 3 и 4 можно реализовать так, что никаких специальных проверок, оказались ли среди bad_1'bad_3' одинаковые наибольшие значения или нет, не потребуется вовсе! Для этого сформируем три числа a, b и c следующим образом:

a = 256 bad_1' + all_1,
b = 256 bad_2' + all_2,
c = 256 bad_3' + all_3.

Т.е. старшим байтом числа a будет bad_1', а младшим — all_1, для b и c — аналогично. После этого остаётся только выбрать из этих трёх чисел наибольшее. У него либо старший байт (т.е. bad') будет больше, чем у других, либо при равенстве старших байтов младший байт (т.е. all) будет больше. Если наибольшее число — a, значит, кодировка текста — ALT; если b — WIN, c — KOI.

Разберём на примере. Пусть all_1=10, all_2=15, all_3=20, bad_1=2, bad_2=2, bad_3=5. Как мы действовали бы, решая задачу «в лоб»? Сначала определили бы наименьшее среди bad_1, bad_2 и bad_3, выяснили бы, что наименьших значений — два: bad_1 и bad_2. Затем сравнили бы all_1 и all_2; так как наибольшее — all_2, следовательно, кодировка текста — WIN. А как действовать по описанному выше способу? Вычисляем a=(255–2)*256+10=64778 (FD0Ah), b=(255–2)*256+15=64783 (FD0Fh), c=(255–5)*256+20=64020 (FA14h). Наибольшее среди них — b, значит, кодировка текста — WIN.

При отыскании наибольшего среди чисел a, b и c нужно ещё проверить, не окажется ли среди них несколько одинаковых наибольших значений, и если так, выбрать из них одно случайным образом (пункт 5 алгоритма). Как упростить эту операцию? Удобно сначала попарно сравнить a и b, a и c, b и c, а затем для получения ответа использовать следующую таблицу (табл. 9):

Табл. 9
a>c a=c a<c
a>b b>c ALT
b=c ALT
b<c ALT ALT, KOI KOI
a=b b>c ALT, WIN
b=c ALT, WIN, KOI
b<c KOI
a<b b>c WIN WIN WIN
b=c WIN, KOI
b<c KOI

Если в клетке таблицы одно наименование кодировки, то это и будет ответом; если несколько — значит, из них надо выбрать одно случайным образом; если в клетке пусто — значит, такой ситуации возникнуть не может (скажем, если a>b и b>c, то не может быть a=c).

Для рассмотренного выше примера: a<b, a>c, b>c; в соответствующей клетке таблицы — «WIN».

При реализации алгоритма на языке высокого уровня удобно хранить в таблице числа от 0 до 7, каждое из которых описывало бы одну из возможных ситуаций (0 — клетка пуста, 1 — «ALT», 2 — «WIN», 3 — «KOI», 4 — «ALT, WIN», и т.д.), а после обращения к таблице — в зависимости от взятого оттуда числа переходить на обработку соответствующей ситуации. При реализации на ассемблере удобнее сразу хранить в таблице адреса переходов.

Итак, пункты 3—5 алгоритма удалось свести к простейшим действиям: формированию трёх чисел, трём сравнениям и одному обращению к таблице. Следовательно, удалось облегчить написание и отладку программы, а сама программа будет короче и быстрее. Не зря всё-таки говорят, что оптимизация программы начинается с оптимизации алгоритма. :–)

А чтобы ещё больше упростить программу, можно при сравнении a, b и c не выделять специально случай равенства, рассматривая лишь два возможных результата сравнения: «меньше» и «больше или равно» (табл. 10). Тогда, если среди a, b и c окажутся одинаковые наибольшие значения, не возникнет необходимости в выборе кодировки случайным образом. На точность определения кодировки такое упрощение практически не окажет влияния.

Табл. 10
a>=c a<c
a>=b b>=c ALT
b<c ALT KOI
a<b b>=c WIN WIN
b<c KOI

Дополнение: в последнем случае лучше не использовать в программе табл. 10 в явном виде, а определять кодировку с помощью сравнений и условных переходов: если a>=b и a>=c, то кодировка — ALT, иначе — WIN или KOI, и чтобы узнать, какая из двух, достаточно проверить результат сравнения b и c: если b>=c, то кодировка — WIN, иначе — KOI. Сравнив первоначальный и оптимизированный варианты процедуры на ассемблере Z80 (см. Приложение 1), вы можете убедиться, что этот способ оптимальнее.

Литература

  1. И.Рощин. «Автоматическое определение кодировки текста». «Радиомир. Ваш компьютер» 10/2001.
  2. А.Шкроб. «Я не любитель, я другой…». «Компьютерра» 24—25/1998.

Приложение 1. Процедура определения кодировки на ассемблере Z80.

Приложение 2. Библиотека на Си для определения кодировки текста.

Другие мои статьи об автоматическом определении кодировки текста:

1. 

«Добавление в HTML-документы информации об их кодировке». «Радиомир. Ваш компьютер» 10/2003.

Страница Ивана Рощина > Статьи >