PHP: Определение языка текста с помощью N-грамм. Часть 1

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

Обычно, когда мы смотрим на текст, мы разбиваем его на слова и используем эти слова для определения языка, на котором он написан. Однако существует достаточно много способов сделать это, сравнивая другие единицы текста. Например, буквенные n-граммы.

N-граммы — это просто n-буквенные последовательности, извлеченные из документа. Например, слово «констебль», разложенное в триграммы (трехбуквенные последовательности) будет выглядеть так: {«кон», «онс», «нст», «сте», «теб», «ебл», «бль»}. Существует большое количество способов извлечения таких последовательностей. Более-менее очевидный приведен ниже. С помощью этой функции можно извлекать n-граммы из входной строки. По умолчанию извлекаются триграммы.

<?php

function getNgrams($word, $n = 3) {
        $ngrams = array();
        for($i = 0; $i < strlen($match); $i++) {
                if($i > ($n - 2)) {
                        $ng = '';
                        for($j = $n-1; $j >= 0; $j--) {
                                $ng .= $match[$i-$j];
                        }
                        $ngrams[] = $ng;
                }
        }
        return $ngrams;
        }

Этот исходный код отформатирован с помощью FractalizeR's HabraSyntax Source Code Highlighter.

Определение языка

Взглянув на текст, разбитый на n-граммы, можно заметить, что с их помощью достаточно легко определять язык, на котором он написан. Для этого существует множество алгоритмов, использующих дву- или триграммы, рассчитывающих различные коэффициенты «похожести», но все они сходятся в одном: сначала следует построить статистическую модель распределения триграмм в каждом языке, а затем посмотреть, которой из построенных моделей наиболее полно соответствует заданный текст. В нашем примере мы будем использовать триграммы и косинусную меру сходства векторных пространств (vector space style cosine similarity).

Один из наиболее очевидных вопросов — «что делать с пробелами». В нашем примере мы их игнорируем и генерируем триграммы только из слов. Мы также игнорируем слова длиной менее 3-х букв. Учитывать будем только частоту, с которой встречается триграмма в данном тексте. В принципе, мы можем увеличить точность определения, введя в алгоритм, например, глобальный вес триграммы, который показывает, насколько общей данная триграмма является для всех языков нашей модели. Но и без этого метод триграмм работает довольно точно, особенно при небольшом количестве языков.

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

<?php

class LangDetector {
        private $index = array();
        private $languages = array();

        public function addDocument($document, $language) {
                if(!isset($this->languages[$language])) {
                        $this->languages[$language] = 0;
                }

                $words = $this->getWords($document);
                foreach($words as $match) {
                        $trigrams = $this->getNgrams($match);
                        foreach($trigrams as $trigram) {
                                if(!isset($this->index[$trigram])) {
                                        $this->index[$trigram] = array();
                                }
                                if(!isset($this->index[$trigram][$language])) {
                                        $this->index[$trigram][$language] = 0;
                                }
                                $this->index[$trigram][$language]++;
                        }
                        $this->languages[$language] += count($trigrams);
                }
        }

        public function detect($document) {
                $words = $this->getWords($document);
                $trigrams = array();
                foreach($words as $word) {
                        foreach($this->getNgrams($word) as $trigram) {
                                if(!isset($trigrams[$trigram])) {
                                        $trigrams[$trigram] = 0;
                                }
                                $trigrams[$trigram]++;
                        }
                }
                $total = array_sum($trigrams);

                $scores = array();
                foreach($trigrams as $trigram => $count) {
                        if(!isset($this->index[$trigram])) {
                                continue;
                        }
                        foreach($this->index[$trigram] as $language => $lCount) {
                                if(!isset($scores[$language])) {
                                        $scores[$language] == 0;
                                }
                                $score = ($lCount / $this->languages[$language])
                                                        * ($count / $total);
                                $scores[$language] += $score;
                        }
                }
                arsort($scores);
                return key($scores);
        }

        private function getWords($document) {
                $document = strtolower($document);
                preg_match_all('/\w+/', $document, $matches);
                return $matches[0];
        }

        private function getNgrams($match, $n = 3) {
                $ngrams = array();
                for($i = 0; $i < strlen($match); $i++) {
                        if($i > ($n - 2)) {
                                $ng = '';
                                for($j = $n-1; $j >= 0; $j--) {
                                        $ng .= $match[$i-$j];
                                }
                                $ngrams[] = $ng;
                        }
                }
                return $ngrams;
        }
}
?>

Этот исходный код отформатирован с помощью FractalizeR's HabraSyntax Source Code Highlighter.

Продолжение статьи тут.