Примечание: я не смог по какой-то причине восстановить свой перевод, за который получил инвайт и он куда-то пропал. Поэтому публикую его снова.
Обычно, когда мы смотрим на текст, мы разбиваем его на слова и используем эти слова для определения языка, на котором он написан. Однако существует достаточно много способов сделать это, сравнивая другие единицы текста. Например, буквенные n-граммы.
N-граммы — это просто n-буквенные последовательности, извлеченные из документа. Например, слово «констебль», разложенное в триграммы (трехбуквенные последовательности) будет выглядеть так: {«кон», «онс», «нст», «сте», «теб», «ебл», «бль»}. Существует большое количество способов извлечения таких последовательностей. Более-менее очевидный приведен ниже. С помощью этой функции можно извлекать n-граммы из входной строки. По умолчанию извлекаются триграммы.
Взглянув на текст, разбитый на n-граммы, можно заметить, что с их помощью достаточно легко определять язык, на котором он написан. Для этого существует множество алгоритмов, использующих дву- или триграммы, рассчитывающих различные коэффициенты «похожести», но все они сходятся в одном: сначала следует построить статистическую модель распределения триграмм в каждом языке, а затем посмотреть, которой из построенных моделей наиболее полно соответствует заданный текст. В нашем примере мы будем использовать триграммы и косинусную меру сходства векторных пространств (vector space style cosine similarity).
Один из наиболее очевидных вопросов — «что делать с пробелами». В нашем примере мы их игнорируем и генерируем триграммы только из слов. Мы также игнорируем слова длиной менее 3-х букв. Учитывать будем только частоту, с которой встречается триграмма в данном тексте. В принципе, мы можем увеличить точность определения, введя в алгоритм, например, глобальный вес триграммы, который показывает, насколько общей данная триграмма является для всех языков нашей модели. Но и без этого метод триграмм работает довольно точно, особенно при небольшом количестве языков.
Ниже приведен небольшой класс, реализующий детектирование. Ключевыми методами являются addDocument, который разбивает входной документ на триграммы и сохраняет частоты, с которыми она встречается в каждом языке во внутреннем словаре (метод обучения нашей модели, прим. пер.), и detect, который разбивает входящий текст аналогичным образом и для каждой встретившейся триграммы проверяет частоту ее присутствия в каждом языке нашей модели.
Продолжение статьи тут.
Обычно, когда мы смотрим на текст, мы разбиваем его на слова и используем эти слова для определения языка, на котором он написан. Однако существует достаточно много способов сделать это, сравнивая другие единицы текста. Например, буквенные 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.
Продолжение статьи тут.