Изменена: 19.03.2011 06:45 MSK
В работе 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-грамм по частоте.