10 November, 2010

Расстановка переносов

Потребовалось мне тут переносы автоматически расставить в русском тексте. Google сказал что самое лучшее это использовать  алгоритм  Ляна-Кнута. Однако, это хоть и совершенный, но достаточно сложный алгоритм, есть способ несколько проще, его я тоже нашел в сети, и решил описать и популяризовать в своем блоге.
Этот способ применим только для русского языка, но учитывая что английский язык имеет менее строгие правила переноса, ограничимся пока русским. Этот алгоритм носит название алгоритма П.Хpистова в модификации Дымченко и Ваpсанофьева. Он очень прост и включает в себя всего шесть правил, при этом почти полностью покрывает все возможные случаи за редким исключением.
Вот эти шесть правил:
  1. "Х-"
  2. "Г-Г"
  3. "ГС-СГ"
  4. "СГ-СГ"
  5. "ГС-ССГ"
  6. "ГСС-ССГ"
Где: Г - гласная, С - согласная, Х - буква из набора "ьъй".

Применять данные правила нужно в том порядке, в котором они перечислены. То есть от коротких к длинным. Дополнительно для первых двух правил, неплохо бы проверять оставшуюся часть слова, чтобы она содержала не менее двух букв.

Простой пример на Qt (расставляет знак "-" везде, где допустим перенос):
#define RUS_A QString("[абвгдеёжзийклмнопрстуфхцчшщъыьэюя]")
#define RUS_V QString("[аеёиоуыэюя]")
#define RUS_N QString("[бвгджзклмнпрстфхцчшщ]")
#define RUS_X QString("[йъь]")

QString Hyphenator::hyphenate(QString text)
{
    re1 = QRegExp(QString("(") + RUS_X + ")(" + RUS_A + 
                  RUS_A + ")", 
                  Qt::CaseInsensitive);
    re2 = QRegExp(QString("(") + RUS_V + ")(" + RUS_V + 
                  RUS_A + ")", 
                  Qt::CaseInsensitive);
    re3 = QRegExp(QString("(") + RUS_V + RUS_N + ")(" + 
                  RUS_N + RUS_V + ")", 
                  Qt::CaseInsensitive);
    re4 = QRegExp(QString("(") + RUS_N + RUS_V + ")(" + 
                  RUS_N + RUS_V + ")", 
                  Qt::CaseInsensitive);
    re5 = QRegExp(QString("(") + RUS_V + RUS_N + ")(" + 
                  RUS_N + RUS_N + RUS_V + ")", 
                  Qt::CaseInsensitive);
    re6 = QRegExp(QString("(") + RUS_V + RUS_N + RUS_N +
                  ")(" + RUS_N + RUS_N + RUS_V + ")", 
                  Qt::CaseInsensitive);

    QString hypher = "\\1-\\2";

    text = text.replace(re1, hypher);
    text = text.replace(re2, hypher);
    text = text.replace(re3, hypher);
    text = text.replace(re4, hypher);
    text = text.replace(re5, hypher);
    text = text.replace(re6, hypher);

    return text;
}

No comments:

Post a Comment