Простейший алгоритм разделения слова на слоги

Однажды на проводимом мной практическом занятии [по ЯП] я, скучая, разглядывал список студентов группы. Глаз зацепился за знак ударения в фамилии Лемзекóв, который я поставил [для себя] после того, как произнёс фамилию этого студента неправильно. Я мысленно прочёл эту фамилию по слогам, и тут у меня возник вопрос: «а по какому алгоритму мозг разбивает слова по слогам?» Почему-то интуитивно получается "Лем-зе-ков", а не "Ле-мзе-ков" или "Лем-зек-ов". Я выписал ещё несколько примеров, и разглядывая их размышлял о том, как перевести это в алгоритм.

Алгоритм получился такой (привожу практически тот самый Python-код, который я написал карандашом тогда на занятии).

slog_start = 0
i = 0
while i < len(word):
    if word[i] in vowels_set:
        vowel_pos = i
        i += 1
        while i < len(word):
            if word[i] in vowels_set:
                if i - vowel_pos == 1:
                    hyphens.append(i)
                elif i - vowel_pos == 2:
                    hyphens.append(i - 1)
                else:
                    hyphens.append(vowel_pos + 2)

На этом месте меня осенило: достаточно просто знать расстояние между соседними гласными буквами (пусть они будут в позициях a и b) — если оно равно 1, тогда вставляем перенос в позиции b, если равно 2, то в позиции b − 1, иначе [т.е. когда расстояние больше 2] в позиции a + 2.

Получается такой Python-код:

word = input()

vowels_set = set('аеёиоуыэюяАЕЁИОУЫЭЮЯ')
vowels = []
for i in range(len(word)):
    if word[i] in vowels_set:
        vowels.append(i)

import collections
hyphens = collections.deque()
for i in range(1, len(vowels)):
    a, b = vowels[i-1], vowels[i]
    if b - a == 1:
        hyphens.append(b)
    elif b - a == 2:
        hyphens.append(b - 1)
    else:
        hyphens.append(a + 2)

for i in range(len(word)):
    if len(hyphens) and hyphens[0] == i:
        print('-', end = '')
        hyphens.popleft()
    print(word[i], end = '')

Можно оптимизировать данный код, избавившись от вспомогательного массива `vowels`:

word = input()

vowels_set = set('аеёиоуыэюяАЕЁИОУЫЭЮЯ')
prev_vowel = len(word)
for i in range(len(word)):
    if word[i] in vowels_set:
        prev_vowel = i
        break

import collections
hyphens = collections.deque()
for i in range(prev_vowel + 1, len(word)):
    if word[i] in vowels_set:
        a, b = prev_vowel, i
        if b - a == 1:
            hyphens.append(b)
        elif b - a == 2:
            hyphens.append(b - 1)
        else:
            hyphens.append(a + 2)
        prev_vowel = i

for i in range(len(word)):
    if len(hyphens) and hyphens[0] == i:
        print('-', end = '')
        hyphens.popleft()
    print(word[i], end = '')

Осталось только добавить поддержку букв «й», «ь» и «ъ».
Для этого нужно слегка модифицировать цепочку условий начинающуюся с if b - a == 1::

for i ...:
    ...
    if b - a == 1:
        hyphens.append(b)
    else:
        for j in reversed(range(a + 1, b)):
            if word[j] in specials_set: # specials_set = set('йьъЙЬЪ')
                hyphens.append(j + 1)
                break
        else:
            if b - a == 2:
                hyphens.append(b - 1)
            else:
                hyphens.append(a + 2)

Ещё одна оптимизация (отказ от `hyphens`), и вот что получается в итоге:

word = input()

vowels_set = set('аеёиоуыэюяАЕЁИОУЫЭЮЯ')
specials_set = set('йьъЙЬЪ')

prev_vowel = len(word)
for i in range(len(word)):
    if word[i] in vowels_set:
        prev_vowel = i
        break

pos = 0
for i in range(prev_vowel + 1, len(word)):
    if word[i] in vowels_set:
        a, b = prev_vowel, i
        if b - a == 1:
            print(word[pos:b], end = '-')
            pos = b
        else:
            for j in reversed(range(a + 1, b)):
                if word[j] in specials_set:
                    print(word[pos:j + 1], end = '-')
                    pos = j + 1
                    break
            else:
                if b - a == 2:
                    print(word[pos:b - 1], end = '-')
                    pos = b - 1
                else:
                    print(word[pos:a + 2], end = '-')
                    pos = a + 2
        prev_vowel = i
print(word[pos:])

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

P. S. Кстати, буду признателен если кто даст ссылочку на оригинальный алгоритм П. Христова, т.к. интересно какие именно модификации сделали Дымченко и Варсанофьев.

P. P. S. Поиском по списку всех русских слов обнаружилось не очень большое количество слов с 5-ю подряд идущими согласными буквами {например: агентство, ангстрем, бодрствование, интеллигентство}. В таких случаях (т.е. когда расстояние между соседними гласными буквами равно 6) следует вставлять перенос в позиции a + 3 или [что то же самое] b − 3.
Также можно объединить случаи, когда расстояние между гласными равно 1 или 2: в обоих этих случаях перенос вставляется в позиции a + 1.

Итоговый код выглядит так:

vowels_set = set('аеёиоуыэюяАЕЁИОУЫЭЮЯ')
specials_set = set('йьъЙЬЪ')

word = input()

prev_vowel = len(word)
for i in range(len(word)):
    if word[i] in vowels_set:
        prev_vowel = i
        break

pos = 0
for i in range(prev_vowel + 1, len(word)):
    if word[i] in vowels_set:
        a, b = prev_vowel, i
        for j in reversed(range(a + 1, b)):
            if word[j] in specials_set:
                npos = j + 1
                break
        else:
            if b - a <= 2:
                npos = a + 1
            elif b - a >= 6:
                npos = b - 3
            else:
                npos = a + 2
        print(word[pos:npos], end = '-')
        pos = npos
        prev_vowel = i
print(word[pos:])