Приветствую.Сегодня я расскажу о том, какие алгоритмы распознавания языка ввода используются в X Neural Switcher.
Как известно, Punto Switcher использует в своей работе словари, основанные на невозможности конкретного буквосочетания для данного языка. Посмотреть их можно, если у вас установлен Punto, тут — %PROGRAMFILES%\Yandex\Punto Switcher\Data\triggers.dat. По крайней мере, так сообщил мне google. Эти словари зашифрованы (несложно, но все таки).
Дополнительно, Punto использует пользовательские исключения. Сказать, где они хранятся не могу — программа закрытая.
Теперь вернемся к xneur. На момент, когда я перешел к использованию linux (2005 год), программ, которые бы декларировали умение распознать и переключить раскладку, было ровно две — sven (еще живой) и xneur (полумервый). Я выбрал для для допиливания xneur, тогда это была версия 0.0.3 (http://www.linux.org.ru/forum/talks/811959). В тот момент его уже фактически забросили первоначальные разработчики, и более полугода никакого движения там не было.
На тот момент xneur был более чем убог. Для любителей, так сказать, острых ощущений на Народе еще лежит версия 0.0.3 — это было ужасно.
Основной идеей распознавания раскладки тогда была идея о «весе» буквосочетания. Если кратко, то брался некий, достаточно большой, текст и на его основе считалось, как часто конкретное двухбуквеное сочетание встречается. Рассчитывался его «вес» для конкретного языка, и писался в файл.
Xneur должен был разбить слово на буквосочетания и подсчитать «вес» слова для каждой раскладки. Если значение было выше некого порога (определяемого на глазок), то слово переводилось в эту раскладку.
Попробовав то, что было на момент, когда я заинтересовался xneur, я понял, что это никуда не годится. Начал думать, как все это доработать.
Прежде чем устаканились внутренние алгоритмы распознавания, прошла пара лет проб и ошибок. Никакого филологического или лингвистического образования у меня нет, все алгоритмы придумывались на основании логики и наития.
Использовать словари от Punto мне не позволила совесть, а так же то соображение, что xneur я задумал мультиязычным, т.е рус-eng словарь мне просто не подходил.
Дальше я опишу алгоритмы, используемые программой на данный момент.
Алгоритмы
В данный момент xneur использует многоступенчатое определение языка. Т.е. я просто ранжировал алгоритмы по степени их достоверности. Наверное, многие из вас увидят тут некое подобие ранжирования, применяемого в антивирусах.
В качестве входных условий в функции определения раскладки передается массив строк, каждая из которых является буквосочетанием, набранным в каждой из раскладок установленных в системе.
На каждом этапе программа в начале проверяет, можно ли оставить набранное слово в той раскладке, что уже включена. И только если слово не подходит под текущую раскладку, то проверяются остальные раскладки.
Далее пойдут варианты по убыванию достоверности переключения.
Словарь пользователя
На данном этапе слово проверяется по словарям, которые либо предопределил я заранее (например, переключать e-mail, IP, MAC в английскую раскладку), либо были добавлены пользователем, либо были добавлены самой программой в процессе самообучения.
Ранее словари пользователя и регулярные выражения (ip, MAC и др.) были разделены на отдельные файлы настроек, но в дальнейшем, они были совмещены, что позволяет пользователю добавлять правила более гибко. Например, добавив буквосочетание «пед», вы можете указать, где это буквосочетание должно встретиться в слове, чтобы переключение произошло — в начале ("педаль"), в конце («велосипед») или просто слово должно содержать это буквосочетание («википедия»).
Более того, для сильно продвинутых пользователей есть возможность самому создавать регулярные выражения по стандарту регулярных выражений Perl. Но на моей памяти, никто этой возможностью не пользуется. Может не знают люди про неё, а?
Системный словарь
Если слово не встретилось ни в одном из словарей пользователя, программа переходит к следующему уровню проверки — к проверке по спеллчекеру. Как говорится, спасибо тем, кто их придумал и реализовал.
Xneur может, в зависимости от опций сборки, использовать либо библиотеку aspell, либо (по умолчанию) обертку над словарями enchant.
Библиотека aspell достаточно мощная, но уже немного устаревшая библиотека проверки правописания. Если вы используете пакетный дистрибутив linux, то пакеты словарей так и будут называться aspell-ru, aspell-uk или aspell-en в зависимости от вашего языка.
Именно с этой библиотеки начиналась поддержка словарей в xneur. К сожалению, количество доступных словарей для этой библиотеки не увеличивается, и именно поэтому пришлось искать ей замену.
В качестве такой замены взгляд упал на myspell и hunspell, а затем на великолепную обертку над словарями Enchant. Именно эту обертку над словарями используют спеллчекеры AbiWord, LibreOffice и Firefox.
Enchant это именно обертка над различными библиотеками словарей, а не сама библиотека словарей. Она объединяет под своим крылом различные движки словарей, сочетая удобство программирования и скорость работы.
В основном, в Ubuntu, Enchant использует словари Myspell, и только для редких языков подключает другие словари.
Поэтому, xneur по умолчанию тоже использует Enchant.
Эвристический анализ
Если источники достоверных сведений в виде словарей не смогли определить принадлежность слова ни к одной из раскладок, то в действие вступает самая ненадежная, но, по сути, самая интересная ступень — эвристический анализ.
После долгих проб и ошибок, я все таки пришел к существующему варианту. Но в начале расскажу о не подошедших, промежуточных вариантах.
«Вес» буквосочетания. Про данный вариант я уже упоминал в начале статьи, но напишу еще раз. Если кратко, то брался некий, достаточно большой, текст и на его основе считалось, как часто конкретное двухбуквеное сочетание встречается. Буквосочетание должно было быть на латинице. Рассчитывался «вес» буквосочетания для конкретного языка, и писался в файл.
Xneur должен был разбить слово на буквосочетания и подсчитать «вес» слова для каждой раскладки. Если значение было выше некого порога (определяемого на глазок), то слово переводилось в эту раскладку.
В общем-то, от данного алгоритма пришлось сразу отказаться по причине сложности рассчета веса и эфемерности признака переключения. Хотя меня не оставляет ощущение, что данный алгоритм можно доработать и сделать конфетку.
Допустимые для языка буквосочетания. Тут проще. Слово принадлежит той или иной раскладке, если все буквосочетания этого слова, входят в конкретный словарь.
Не покатило — долго и дорого в плане ресурсов. При этом буквосочетания всегда хранились в латинице, что добавляло веселья с перекодировкой.
И вот таким образом мы пришли к современной версии эвристики — недопустимые для языка буквосочетания. В этот момент пришло понимание, что буквосочетания надо хранить в буквах того языка, который мы проверяем, что бы снизить затраты на перевод раскладки.
По нынешним алгоритмам, слово не может принадлежать тому или иному языку, если буквосочетание из этого слова встретилось в списке таких буквосочетаний. Списки буквосочетаний мы назвали прото-языками. На основе именно прото-языков и строится эвристика.
Прото-языки в xneur двух типов — большие и маленькие. Большие — это буквосочетания длиной 3 символа, маленькие — длиной 2 символа. Зачем нужно это разделение? Все просто — большие прото в 10-15 раз меньше. Таким образом сокращается время на обработку слова. Т.е. сначала слово проверяется по большому прото, а потом (если опознания не произошло) по маленькому.
Сами прото-языки получаются с помощью самого xneur. В нем уже есть механизм для из генерации. Просто устанавливаем в систему нужную раскладку, берем текст на данном языке, да подлиннее, запускаем xneur с нужным ключиком, и вперед!
Прото-языки являются последним из алгоритмов распознавания. Если слово прошло все стадии и не встретило препятствий, то оно остается в той раскладке, что и было.
Резюмируя
Как я показал, алгоритмы xneur чудовищно просты.
Наверное, кто-то ожидал, что я раскрою какие-то страшные и сложные алгоритмы, типа цепей Маркова, но этого не произошло.
При разработке xneur я придерживался простого правила KISS — сделай это просто, дурень! И как показала практика, уровень ложных срабатываний при таких алгоритмах очень низок. Разумеется, на данный момент от пользователя требуется поставить системные словари, но это не большая плата за скорость обработки.
Если у вас есть идеи или наработки по данной теме, я с удовольствием обсужу их в комментариях. Ведь именно в сообществе сила open source!
Предыдущие части
X Neural Switcher — Поваренная книга (Часть 0). Введение. Сборка и настройка
X Neural Switcher — Поваренная книга (Часть 1). Предтечи и аналоги
В дальнейших статьях я расскажу о:
- Настройка xneur в качестве кейлогера.
- Глюки и приколы xlib, locale и разных DE.
