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

Maxime Zakharov

В работе Cavnar, W. B. and J. M. Trenkle, ``N-Gram-Based Text Categorization'' In Proceedings of Third Annual Symposium on Document Analysis and Information Retrieval, Las Vegas, NV, UNLV Publications/Reprographics, pp. 161-175, 11-13 April 1994 был предложен метод для опредления языка и кодировки документа по его содержимому основываясь на статистиках документов, для которых язык и кодировка известны заранее. Метод основывается на подсчете частот N-грамм (подстрок длины не более N) и предположении, что примернно 300 самых частоиспользуемых N-грамм сильно зависят от языка.

Алгоритм метода заключается в нахождении частот N-грамм для всех тестовых документов, для которых известен язык, а также для каждого документа, язык которого пытаемся определить. После этого среди всех тестовых документов находим тот, для которого расстояние от его N-граммной статистики до статистики тестируемого документа минимально. После этого языком теституемого документа считается язык найденного тестового документа.

Расстояние между статистиками подсчитывается следующим образом: все N-граммы сортируются в порядке убывания частоты их появления, затем для кадой N-граммы вычисляется разница ёё позиций в отсортированном списке N-грамм тестового и тестируемого документов. Расстояние между статистиками определяется как сумма разниц позиций каждой N-граммы.

Значение N предлагается использовать равным 5.

Реализация данного метода на языке Perl: TextCat. .


В поисковой машине MnogoSearch, начиная с версии 3.2.4, используется иной способ вычисления расстояния между списками N-грамм. В качестве расстояния между статистиками используется следующая функция определения количества информации:

            M       2
         SUM     log  ( Pi/Qi )
            i=1

где Qi - частота N-граммы тестируемого документа, а Pi - частота этой же N-граммы в очередном эталонном документе.

Используемое значение N равно 5.

Этот метод в отличие от предыдущего не требует сортировки N-грамм по частоте.


Яндекс цитирования Рейтинг@Mail.ru
 
Изменена: 19.03.2011 06:45 MSK