Новости‎ > ‎

Алгоритм разбивки слов на слоги

Отправлено 21 апр. 2010 г., 14:32 пользователем Yura Batora   [ обновлено 22 апр. 2010 г., 04:49 ]
Недавно столкнулся с проблемой реализации упрощенного алгоритма разбивки слов на слоги. Текущий алгоритм, который используется в Foliant, реализован на основе шаблонов переносов TeX. Пришлось долго повозится, что бы реализовать его средствами J2ME, но потом оказалось, что этот алгоритм использует много памяти. На многих телефонах открытие книги с включенными переносами вызывало серьезную ошибку, связанную с переполнением памяти. Ведь приходилось загружать в память таблицу правил переносов для русского языка, а он довольно таки увесистый, да и скорость работы реализованного алгоритма оставляла желать лучшего. 

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

Реализация не заставила себя ждать и в течении часа уже проводилось тестирование на телефоне. К моему огорчению, реализация RegExp для J2ME была далека от совершенства, она работала довольно медленно даже по сравнению с предыдущей реализацией. Пересмотрев алгоритм, пришла идея его оптимизации. Она заключалась в следующем:

1. Заменить буквы в слове соответствующими "метками"
    x=йьъ
    g=аеёиоуыэюяaeiouy
    s=бвгджзклмнпрстфхцчшщbcdfghjklmnpqrstvwxz
к примеру слово "подъезд" -> "sgsxgss", "habrahabr" -> "sgssgsgss"

2. Задать правила замены, пришлось немного извратиться
    "xgg" -> "x-gg"
    "xgs" -> "x-gs"
    "xsg" -> "x-sg"
    "xss" -> "x-ss"
    "gssssg" -> "gss-ssg"
    "gsssg" -> "gss-sg"
    "gsssg" -> "gs-ssg"
    "sgsg" -> "sg-sg"
    "gssg" -> "gs-sg"
    "sggg" -> "sg-gg"
    "sggs" -> "sg-gs"

3. Произвести банальную замену в предыдущем слове
    "подъезд" -> "sgsxgss" -> "sgsx-gss"
    "habrahabr" -> "sgssgsgss" -> "sgs-sg-sgss"

4. Нанести расставленные переносы на изначальное слово
    "подъезд" -> "sgsxgss" -> "sgsx-gss" -> "подъ-езд"
    "habrahabr" -> "sgssgsgss" -> "sgs-sg-sgss" -> "hab-ra-habr"

В итоге, получил быстрый алгоритм, который использует минимум памяти и работает как с русским, так и английским языком. Качество разбивки слов не всегда удовлетворительное, хотя, по заявлению создателей алгоритма, он точен на 99.99%, в чем я конечно сомневаюсь...

Реализацию алгоритма можно взять здесь Hyphenator.java.