Определение языка и кодировки. Компонент для CakePHP

3 December, 2007 at 9:37 pm · CakePHP, Компоненты

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

Сначала система обучается - ей скармливается много текста и указывается, какой это язык. Она разбирает их на части и запоминает наиболее часто встречаемые как эталонные для этого языка.

Потом берётся текст с неизвестным языком и определяются наиболее часто встречаемые части в нём. Эти части сравниваются с эталонными и на основе этого определяется вероятность каждого из языков.

Я взял за основу код с http://boxoffice.ch/pseudo/ng.php, удалил лишнее, немного оптимизировал алгоритм и сделал код красивый и подходящий для CakePHP.

Определим язык для текста

plain text
PHP:
  1. $language = $this->LangDetect->detect('Учи олбанский и убей сибя ап стену.');

Не каждый человек сможет понять, что это за язык :). А компонент понял - russian-utf8.
Кстати, сразу видно бонус - определяется кодировка. Для русского поддерживаются ISO, KOI8-R, UTF-8, Windows-1251.

Если надо определить несколько наиболее вероятных языков, то надо указать второй параметр true.

plain text
PHP:
  1. $language = $this->LangDetect->detect('Учи олбанский и убей сибя ап стену.', true);

Это выдаст:

plain text
PHP:
  2. (
  3.     [russian-utf8] => 30366
  4.     [bulgarian-utf8] => 31619
  5.     [ukrainian-utf8] => 33273
  6.     [serbian_cyrillic-utf8] => 33878
  7.     [belarusian-utf8] => 35596
  8. ...

Чем меньше значение, тем более вероятно, что это тот язык.

Полный список поддерживаемых языков (можно получить с помощью $this->LangDetect->listLanguages()):
afrikaans, albanian, alemannic, amharic-utf8, arabic-iso8859_6, arabic-utf8, arabic-windows1256, armenian, armenian-utf8, basque, belarusian-utf8, belarusian-windows1251, bosnian, breton, bulgarian-iso8859_5, bulgarian-utf8, catalan, chinese-big5, chinese-gb2312, chinese-utf8, croatian-ascii, czech-iso8859_2, czech-utf8, danish, dutch, english, esperanto, estonian, finnish, french, frisian, georgian, georgian-utf8, german, greek-iso8859_7, greek-utf8, hawaian, hebrew-iso8859_8, hebrew-utf8, hindi, hindi-utf8, hungarian, icelandic, indonesian, irish_gaelic, italian, japanese-euc_jp, japanese-shift_jis, japanese-utf8, korean, korean-utf8, latin, latvian, lithuanian, malay, manx, marathi, marathi-utf8, middlefrisian, mingo_iroquois, nepali, nepali-utf8, norwegian, persian, persian_farsi-utf8, persian_farsi-windows1256, polish-iso8859_2, polish-utf8, portuguese_brazil, portuguese_europe, quechua, romanian, rumantsch, russian-iso8859_5, russian-koi8_r, russian-utf8, russian-windows1251, sanskrit, scots, scots_gaelic, serbian-ascii, serbian_cyrillic-utf8, slovak-ascii, slovak-utf8, slovak-windows1250, slovenian-ascii, slovenian-iso8859_2, spanish, swahili, swedish, tagalog, tamil, tamil-utf8, thai, thai-utf8, turkish, turkish-utf8, ukrainian-koi8_u, ukrainian-utf8, vietnamese, welsh, yiddish-utf8

Чтобы компонент заработал, нужно скачать скомпилированную информацию о языках и положить этот fingerprint.dat в app/vendors.

А вот и сам компонент:

plain text
PHP:
  1. <?php
  2.  
  3. /**
  4. * Language detection component
  5. *
  6. * Most of code was copied from http://boxoffice.ch/pseudo/code_expl/code_class.php
  7. * but a lot of things were simplified and beautified
  8. *
  9. * @link http://php.southpark.com.ua
  10. * @author Vladimir Luchaninov
  11. * @version 1.0 (3 Dec 2007)
  12. *
  13. */
  14. class LangDetectComponent {
  15.     protected $fingerprint = null;
  16.     protected $ngrams = array();
  17.  
  18.     //reasonable defaults
  19.     public $ngramCount = 350;     //default nb of ngrams created from analyzed text
  20.     public $maxDelta = 140000;    //stop evaluation deviate strongly
  21.  
  22.     function startup(&$controller) {
  23.         $this->fingerprint = unserialize(file_get_contents(APP . 'vendors' . DS . 'fingerprint.dat'));
  24.     }
  25.  
  26.     /**
  27.      * Main function
  28.      *
  29.      * @param string $text Text with unknown language
  30.      * @param bool $onlyBest
  31.      *   true - detect the best language
  32.      *   false - detect all languages with possibilities
  33.      * @return LangDetect
  34.      */
  35.     function detect($text, $onlyBest = true) {
  36.         if (empty($text)) {
  37.             trigger_error('Text should not be empty');
  38.             return false;
  39.         }
  40.  
  41.         $this->createNGrams($text);
  42.  
  43.         if ($onlyBest){
  44.             return $this->compareNGramsOne();
  45.         } else {
  46.             return $this->compareNGrams();
  47.         }
  48.     }
  49.  
  50.     /**
  51.      * Get list of the available languages
  52.      *
  53.      * @return array List of languages
  54.      */
  55.     function listLanguages() {
  56.         $languages = array_keys($this->fingerprint);
  57.         sort($languages);
  58.         return $languages;
  59.     }
  60.  
  61.     /**
  62.      * Create ngram-array of given string
  63.      *
  64.      * @param string $text
  65.      *
  66.      */
  67.     protected function createNGrams($text) {
  68.         $array_words = explode(" ", $text);
  69.         $ngrams = array();
  70.         foreach($array_words as $word) {
  71.             $word = "_". $word . "_";
  72.             $wordLength = strlen($word);
  73.             for ($i=0; $i <$wordLength; $i++) { //start position within word
  74.                 for ($s=1; $s <4+1; $s++) {  //length of ngram
  75.                     if (($i + $s) <$wordLength + 1) { //length depends on postion
  76.                         $ngrams[] = substr($word, $i, $s);
  77.                     }
  78.                 }
  79.             }
  80.         }
  81.  
  82.         //count-> value(frequency, int)... key(ngram, string)
  83.         $blub = array_count_values($ngrams);
  84.  
  85.         //sort array by value(frequency) desc
  86.         arsort($blub);
  87.  
  88.         //use only top frequent ngrams (def by $ng_number)
  89.         $top = array_slice($blub, 0, $this->ngramCount);
  90.  
  91.         $this->ngrams = array();
  92.         foreach ($top as $keyvar => $valvar){
  93.             $this->ngrams[] = $keyvar;
  94.         }
  95.     }
  96.  
  97.     /**
  98.      * Compare ngrams: Textinput vs lm-files.
  99.      *
  100.      * @return array of languages with lowest deviation
  101.      */
  102.     protected function compareNGrams() {
  103.         $limit = $this->maxDelta;
  104.         foreach ($this->fingerprint as $basename => $language) {
  105.             $delta = 0;
  106.             //compare each ngram of input text to current lm-array
  107.             foreach ($this->ngrams as $key => $ngram){
  108.                 //match
  109.                 if(in_array($ngram, $language)) {
  110.                     $delta += abs($key - array_search($ngram, $language));
  111.                     //no match
  112.                 } else {
  113.                     $delta += 400;
  114.                 }
  115.                 //abort: this language already differs too much
  116.                 if ($delta> $this->maxDelta) {
  117.                     break;
  118.                 }
  119.             } // End comparison with current language
  120.  
  121.             //include only non-aborted languages in result array
  122.             if ($delta <($this->maxDelta)-400) {
  123.                 $result[$basename] = $delta;
  124.             }
  125.         } //End comparison all languages
  126.  
  127.         if(!isset($result)) {
  128.             $result = array('unknown'=>0);
  129.         } else {
  130.             asort($result);
  131.         }
  132.  
  133.         return $result;
  134.     }
  135.  
  136.     /**
  137.      * Variation - COMPARE ng's - Return 1 LANGUAGE only
  138.      *
  139.      * @return string Most probable language
  140.      */
  141.     protected function compareNGramsOne() {
  142.         $limit = 160000;
  143.         foreach ($this->fingerprint as $basename => $language) {
  144.             $delta = 0;
  145.             foreach ($this->ngrams as $key => $ngram){
  146.                 if (in_array($ngram, $language)) {
  147.                     $delta += abs($key - array_search($ngram, $language));
  148.                 } else {
  149.                     $delta += 400;
  150.                 }
  151.                 if ($delta> $limit) {
  152.                     break;
  153.                 }
  154.             }
  155.  
  156.             if ($delta <$limit) {
  157.                 $result[$basename] = $delta;
  158.                 $limit = $delta; //lower limit
  159.             }
  160.         }
  161.  
  162.         if (!isset($result)) {
  163.             return 'unknown';
  164.         } else {
  165.             asort($result);
  166.             //basename of best matching lm file
  167.             list($result_first, $ignore) = each($result);
  168.         }
  169.  
  170.         return $result_first;
  171.     }
  172.  
  173. }
  174. ?>

Картинка по теме: "TOP 10 языков технической документации"
lang_map.gif

Понравилось?

  1. Подпишись через RSS
  2. Расскажи о http://php.southpark.com.ua друзьям.
    Все способы хороши: ICQ, E-mail, свой блог, комментарий в чужом блоге или сообщение на форуме
  3. Добавь статью на news2.ru, Хабрахабр или в закладки

Огромное спасибо!

И не стесняйтесь комментировать - у меня стоит плагин, который убирает rel="nofollow" у людей, которые написали больше 5 комментариев.

RSS feed | Trackback URI

13 комментариев »

Comment by dkrnl Subscribed to comments via email
2007-12-04 07:39:55

интересный алгоритм (:
но не могу представить - где можно применить...

Ответить
 
Comment by Антон Исайкин
2007-12-04 09:16:22

Здорово. Как раз на днях искал решение!
Решил отложить, не напрасно. :-)
Спасибо.

Ответить
 
Comment by Владимир Лучанинов
2007-12-04 11:45:57

@dkrnl:
Взять тот же deli.cio.us. Я подписался на rss по тегу cakephp, но около половины - информация на испанском и японском. Я бы с удовольствием поставил бы галочки "Смотреть информацию только на английском, русском, украинском". Кстати, надо будет сделать себе фильтр и ещё убирать дубликаты с разным названием, когда появится свободное время :))

Также, если брать информацию с других русскоязычных сайтов, то желательно знать кодировку и иногда надо отсеять ненужные для российских пользователей кириллические языки (например, белорусский, украинский). Не кидайтесь камнями, украинский мне очень нравится (по-моему, было какое-то международное исследование и украинский назвали вторым по мелодичности европейским языком после итальянского)

Ответить
 
Pingback by “Звёзды” и Бизнес Или Как Лишиться Всего в Один Момент? Часть 2.
2007-12-04 15:35:30

[...] Как на CakePhp определить язык? [...]

Ответить
 
Comment by Evgeny Sergeev
2007-12-05 04:11:44

Вопрос в том на сколько длинным должен быть текст, чтобы правильно определить язык?

Ответить
 
Comment by Владимир Лучанинов
2007-12-05 08:50:01

Чем длиннее, тем лучше :)
У меня нормально определяет, если есть хотя бы несколько предложений.

Ответить
 
Comment by gns Subscribed to comments via email
2008-01-21 19:36:06

а что с копирайтом/лицензией на этот код и fingerprints ?

Ответить
Comment by Владимир Лучанинов
2008-01-22 09:36:40

Большая часть кода взята с http://boxoffice.ch/pseudo/code_functions.php
Fingerprints тоже оттуда, но я их упаковал в один файл.
На том сайте я не нашёл упоминания о лицензиях. И вроде это просто научный проект, зарабатывать на нём никак не пытаются.

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

Ответить
Comment by gns Subscribed to comments via email
2008-01-22 09:45:32

просто я собираюсь запаковать это для ALT Linux. ОК. поставлю Public Domain :)

ЗЫ.писал такое когда-то на C, но детектил только кодировку русского языка. Вся засада была именно в "хороших" fingerprints для разных языков.

(Comments wont nest below this level)
Ответить
 
 
 
Comment by Mr BoxOffice
2008-01-23 00:02:17

Привет dear Vladimir,

Well done! fantastic work you did with my few lines of code: Congratulations.

Don't worry about the license. I appreciate your reference to http://www.boxoffice.ch/pseudo/

До свидания and Greetings from Швейцария

Mr BoxOffice ;-)

Ответить
 
Comment by Марго
2008-07-06 11:09:20

"Qui prior est tempore, potior est jure" помогите найти перевод этого выражения, пожалуйста. у меня ничего не выходит.

Ответить
 
Comment by Alex Subscribed to comments via email
2008-09-24 16:38:48

> Я взял за основу код с http://boxoffice.ch/pseudo/ng.php, удалил лишнее

Что оказалось лишним?

Ответить
 
Имя (required)
E-mail (required - never shown publicly)
URL
Текст комментария
You may use <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> in your comment.