Домашний алгоритм разбиения на слова (c картинками)

В этой статье я расскажу и покажу свой способ сегментации строк на слова. Если вам не интересна жизнь сибиряка в тропиках, можете смело пропускать вступление.

image

Вступление


Год назад я работал учителем математики в Таиланде. Учил юных джедаев силе абстракции. Учить детей — это очень интересно и приносит много удовольствия. А вот администрация приносит только головную боль. В тайских школах присутствует строгая иерархия: во-первых, по заслуге лет, во-вторых, по доступу к информации. Тот, кто её создает, находится на вершине, за ним идут верные распространители, заканчивая теми, кто информацию получает в последний момент, а уж если у тебя нет информации, то ты никто.

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

Это жизнь в полной информационной блокаде. При этом общедоступная информация, та которая развешивается по всей школе, вам тоже не доступна, она ведь на тайском. Бывало придешь на работу, а школа закрыта. На следующий день выясняешь у директора, как же так, никто ничего не сообщил. А на это директор удивленно разводит руками, все же знали, мол, приказы-то вот же на стене.

image

Справка: тайская письменность сильно отличается от письменности других языков, потому что она была независимо создана относительно недавно. Тайский содержит 44 символа согласных, а также 15 символов гласных, которые могут соединяться между собой в 28 разных форм. Гласные могут ставиться слева, справа, сверху и снизу согласной. И еще дополнительно 4 тоновых знака, тон — это что-то вроде интонации, с которой слог должен произноситься. Есть слова, которые отличаются друг от друга только тонами и имеют абсолютно разные значения. Пробелы между словами ставятся редко.

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

Поиск по интернетам не принёс результата. Потому как обычные алгоритмы, такие как, например, собраны в этой хабр-статье, опирались на частоту слов. Чтобы собрать эту статистику, нужно было уметь разбивать на слова. А чтобы разбивать на слова, нужна была статистика. Вот такой замкнутый круг.

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

Алгоритм


Итак, нам понадобится словарь (желательно, чтобы по нему можно было ходить по буквам). И пример-строка: “ядочиталэтодоконцанахабре”.

Первый шаг любого алгоритма — это визуализация.

Составим таблицу, где разместим все возможные варианты слов с учетом их длины. Слова “нах” у нас в словаре не будет, зато будет слово “хабр” и “хабре”.

image

Замечательно, теперь мы видим, что вариантов не так много и для программиста перебрать их все не составит труда.

Но как быть в такой ситуации: “яд о читал“ или “я до читал” или “я дочитал”? Какой из вариантов выбрать?

Для этого введем функцию оценки полученного разбиения. Будем выдавать очки за использованные буквы и слова. +3 очка за букву и -1 очко за слово. Чтобы было использовано как можно больше букв с как можно меньшим количеством слов.

И тогда:

image

Победила желаемая строка! Осталось только придумать, как оптимальным образом всё перебрать и получить ОДИН единственный ответ.
В слове “один” кроется разгадка нашего алгоритма.

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

Что означает, что перебор должен проходить на уровне одной буквы, а не всех слов со всеми. Например, возьмём первую букву нашей строки “я”. И выберем между

“” 0 очков + х1
“я” 2 очка + х1
“яд” 5 очков + х2.

Где х1, х2 — предыдущие очки (отсчет с нуля).

Как это сделать ведь иксов у нас нет? Предыдущие очки нам известны только для последней буквы и они равны нулю. Значит нам нужно идти с конца!

Достроим два столбца, где будем хранить очки и длины используемых слов. Будем складывать очки за слово с предыдущими очками (красные коробочки) и искать максимум.

image

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

О том как сделать такой словарь я расскажу в следующей статье. Я дочитал эту статью до конца на Хабре
Share post

Comments 12

    0
    Я дочитал :)
    А о чем объявление, если не секрет? Я понял что это про август — сентябрь 2014-го года, но осилить перевод точно не смогу.
      0
      Это объявление для учителей, чтобы они полугодовые оценки проставили и журналы закончили. Тайский учебный год заканчивается в сентябре. Октябрь каникулы.
      +1
      Критерий странный, а в остальном прикольно. Просто данная система подсчёта «очков» по идее даёт нам вполне определённое множество специфичных строк, и по идее они далеко не всегда будут правильными. Или я неправильно понял разбираемую задачу. Просто, честно говоря, я не вникал в работу алгоритма очень сильно, но мне кажется, что он составляет строку из минимального количества слов. А это далеко не всегда верное решение подобной задачи.
        0
        Алгоритм максимизирует количество использованных букв. А минимизация количества слов позволяет максимизировать их размер. Чтобы «дочитал» > «до читал».
          0
          Но если в контексте будет правильно использовать именно два коротких слова вместо одного? Тогда решение неверно?
            0
            Да, неверно. Но на практике редко встретится. Так уж устроенны языки.
              0
              «Помогитемнеесливамнетрудно» Я не уверен, что скажем на такой строке он даст верный результат (хотя может вы имеете ввиду именно тайский язык)
                0
                Интересный пример.
                «Не трудно» == «Нет рудно».
                Для русского языка можно дополнительные правила ввести для маленьких частичек. В тайском таких проблем нет.
                0
                И в русском языке просто будут допущены ошибки за счёт правил русского языка про раздельное и слитное написание в зависимости от контекста.
                  0
                  Ага. Но такую проблему частота слов или их пар тоже не решит.
                  Нужны конкретные правила.
                  Пример, «не давно» и «недавно».
          0

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

            0
            Решение, приближающие к истине, тоже решение. А приблизительное решение иногда ценнее точного.

            Only users with full accounts can post comments. Log in, please.