Недавно столкнулся с проблемой реализации упрощенного алгоритма разбивки слов на слоги. Текущий алгоритм, который используется в 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. |
Новости >