Наш алгоритм распознавания языка

В процессе разработки сервиса dcde.ru мы столкнулись с интересной алгоритмической задачей.

Дело в том, что в момент обработки запроса нельзя с точностью установить, какая запись (представление) данного термина правильна – та, что вписал пользователь, или выгенерированная автоматическим обработчиком, т.е. нашим сервисом.

Например, если пользователь впишет «руки вверх» и автообработчик перекодирует это в латинскую запись “herb ddth[”, как ему установить, которое из этих представлений является значимой фразой или словом русского или английского языка?

Интуитивный подход к решению данной задачи велит воспользоваться словарём известных терминов, но здесь кроется целый ряд существенных проблем:

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

  2. несмотря на написанное выше, размер словаря, скорее всего, всё равно будет неоправданно большим,

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

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

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

Мы решили использовать тот факт, что различные языки (по крайней мере, те, которые невозможно представить с использованием логограмм) имеют определённые статистические шаблоны (сигнатуры), регулирующие выступление одних знаков (фонограмм) в словах в очерёдности за другими. Например, во множестве слов английского языка вслед за буквой “i” следует буква “n”, то есть последовательность “in” достаточно часто встречается. С другой стороны, последовательность “gk” в словах английского языка встречается относительно редко.

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

Далее, если рассмотреть более длинные комбинации знаков (3, 4 и более знаков), получаются ещё более специфические последовательности, которые будут ещё подробнее отражать характеристики языка. Однако, продолжая в том же духе, мы придем к тому, что начнем создавать словарь полных слов данного языка и размер такой таблицы станет неконтролируемым (как если бы мы пытались составить полный словарь всех возможных слов данного языка).

В связи с этим, для наших нужд мы решили ограничиться составлением четырех отдельных таблиц всех встречающихся в данном языке последовательностей знаков длиной от 2 до 5 букв.

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

Анализируя список всех слов заданного языка или достаточно длинный текст на заданном языке мы будем подсчитывать количество выступлений каждой последовательности знаков заданной длины (например, 3 знака) в словах. После этого мы получим следующую таблицу встречаемости:

…
“lvi”: 20,
“mys”: 15,
…

Далее, все наши таблицы встречаемости будут содержаться в одной общей таблице пар ключ-значение, в которой, в свою очередь, ключами будут являться численные значения длин последовательностей знаков, а значениями, - собственно, таблицы встречаемости последовательностей знаков соответствующей длины.

2:{таблица встречаемости двухбуквенных последовательностей}
3:{таблица встречаемости трехбуквенных последовательностей}
4:{таблица встречаемости четырехбуквенных последовательностей}
5:{таблица встречаемости комбинаций пятибуквенных последовательностей}

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

Таким образом мы создаем сигнатуру для выбранного языка, состоящую из таблиц встречаемости последовательностей букв размером от 2 до 5 знаков и суммы всех численных значений встречаемости всех последовательностей для последующей нормализации.

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

Для этого мы перебираем все последовательности букв различной длины (в нашем случае, от 2 до 5 знаков), присутствующие в данном слове / фрагменте, и для каждой такой последовательности находим значение встречаемости в сигнатуре рассматриваемого языка. Затем добавляем это значение к общему количеству пунктов для анализируемого слова (это вес слова / фрагмента текста).

Если мы не находим обнаруженной в слове или фрагменте текста последовательности букв в сигнатуре языка, это означает, что нам встретилась последовательность знаков, которая не должна встречаться в данном языке. В таком случае, мы “сурово наказываем” слово или фрагмент текста, вычитая пункты из его веса.

Внимательный читатель, наверное, заметит, что согласно такой схеме, языки с бОльшими численными значениями встречаемости в таблицах сигнатуры окажутся в несправедливо привилегированном положении по отношению к языкам с меньшими значениями в таблицах встречаемости только потому, что сигнатуры первых были построены на основании бОльших по объёму текстов или списков слов, чем сигнатуры вторых языков.

Для того, чтобы этого избежать, вес слова (набранное общее количество пунктов для слова или фрагмента текста) нужно нормализовать, то есть просто напросто разделить на вышеупомянутое значение суммы всех численных значений встречаемости, которое является атрибутом сигнатуры рассматриваемого языка.

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

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

Далее, эмпирическим путём мы установили: для того, чтобы чётко разграничить, например, русский и английский языки, описанный алгоритм необходимо дополнить. А именно, в доработке нуждается алгоритм вычисления веса анализируемого слова или фрагмента текста. При вычислении веса каждой анализируемой последовательности букв слова или фрагмента текста нужно учесть длину этой последовательности, ведь более длинные последовательности в большей степени отражают характеристики языка, поэтому их вклад в общий вес анализируемого слова / фрагмента текста должен быть больше. В случае же, если анализируемая последовательность знаков не встречается в рассматриваемом языке, количество пунктов, вычитаемых из общего веса анализируемого слова / фрагмента текста, должно так же непосредственно зависеть о длины этой последовательности.

Приводим формулу, которая оказалась наиболее эффективной в наших экспериментах:

где:

n = длина последовательности знаков (постоянна для одного прохода)

ci = значение встречаемости для данной последовательности знаков

b = количество “плохих” последовательностей знаков (таких, которые не встречаются в рассматриваемом языке и потому не отражены в его сигнатуре)

S = сумма значений всех встречаемостей во всех таблицах сигнатуры данного языка

L = длина анализируемого слова / фрагмента текста

Вероятно, эту формулу можно ещё усовершенствовать, так как мы разрабатывали её в сжатые сроки, пользуясь методом проб и ошибок, но мы уверены, что в результате более скрупулезного математического анализа можно получить ещё более эффективную формулу.

Итак, мы представили здесь очень упрощённое описание использованного при создании нашего сервиса алгоритма, в котором мы умышленно опустили такие рутинные и/или очевидные шаги, как, например, отсеивание ошибочных знаков или опечаток (которые, кстати, могут сделать сравниваемые слова различными по размеру, что в свою очередь, ещё раз подчёркивает необходимость нормализации). Заметим также, что без учета некоторых дополнительный шагов реализации данного алгоритма могут привести к неоптимальным результатам.

English version

Топ 30 опечаток: