Liang-Knuth algorithm for arranging soft hyphens

When working with text, there is often a need to correctly arrange hyphens. The task at first glance is not so obvious, you need to take into account the characteristics of each language in order to decide where to break the word. How to formalize such requirements, and how then to apply them in the algorithm? One of the most common solutions to this day has been proposed by Franklin Mark Liang, a student of renowned professor Donald Knuth. The algorithm is called the “Liang-Knuth Algorithm”, it is used in the TeX publishing system , the author of which is again D. Knut.

The algorithm is based on comparing the source word with a set of rules (templates). The more rules and the better they are drawn up, the better hyphenation will be placed. In the TeX package, you can find ready-made free rule sets for many languages, you just need to carefully look at the terms of use and distribution.

Example rules:

at1  
at 3b 
2 and 1ve
.po3zh2

Each rule consists of letters and numbers between them, as well as numbers at the beginning and at the end. The number 0 is usually omitted. For example, the first rule should be understood as 0п0р0и1 . A sequence of letters is a part of a word for which a translation is defined, i.e. this sequence must be present in the word. The numbers are called the "level", they set the priority between the rules and the ability to transfer in the corresponding position. Even numbers, including 0, prohibit transfer. Odd - allow. The dot at the beginning of the rule means that the rule is applied only if the sequence is at the beginning of the word. Similarly with a dot at the end - the word should end with this sequence. If there is a point both at the beginning and at the end, then the rule contains the whole word.

The main stages of the algorithm:

1. Select all the rules that fit the selected word and for each position in the word get a set of levels (how many rules were in one position, so many levels will be received).
2. In each position, select the maximum level. If it is even, it is impossible to transfer here, if it is odd, it is an acceptable place of transfer.
3. To cut off obviously unacceptable hyphens (for example, one letter at the beginning or at the end).

Let's see how the algorithm works on an example:

Source word: algorithm
Ruleset (taken from TeX):

    lgo1
    1g
    o1ri
    and 1t
    i2tm
    tm2

Compare the word with all the rules and choose the highest levels:

In positions with level 1, you can safely set the hyphen. We get the result "al-go-rhythm . "

Implementation

Now we implement this algorithm in C ++. I needed a working algorithm for use in iOS, so I did everything in the form of a C-interface. The module is written without reference to any locale or platform; it can be used anywhere.
The rule will be stored like this:

struct pattern_t
{
    std::basic_string str;
    std::vector levels;
};

We will transform each rule into the form “pure sequence of characters” + “set of levels”, so that it would be convenient to apply in the future.
Ruleset:

struct pattern_list_t
{
    std::vector list;
};

The code for pulling levels out of the rules is simple; you can see it in the full source code using the link at the end of the article.
After we fill out the list of rules, it needs to be sorted in order to ensure the correct and efficient operation of the algorithm. We write our less function and apply the standard sorting algorithm:

bool pattern_compare(const pattern_t* a, const pattern_t* b)
{    
    bool first = a->str.size() < b->str.size();
    size_t min_size = first ? a->str.size() : b->str.size();
    for (size_t i = 0; i < min_size; ++i) 
    {
        if (a->str[i] < b->str[i]) 
            return true;
        else if (a->str[i] > b->str[i]) 
            return false;
    }
    return first;
}
void sort_pattern_list(pattern_list_t* pattern_list)
{
    if (!pattern_list) return;
    std::sort(pattern_list->list.begin(), pattern_list->list.end(), pattern_compare);
}

Now directly the hyphenation finding algorithm:

std::vector levels;
levels.assign(word_string.size(), 0);
for (size_t i = 0; i < word_string.size()-2; ++i)
{
    std::vector::const_iterator pattern_iter = pattern_list->list.begin();
    for (size_t count = 1; count <= word_string.size()-i; ++count)
    {
        pattern_t pattern_from_word;
        pattern_from_word.str = word_string.substr(i, count);
        if (pattern_compare(&pattern_from_word, *pattern_iter))
            continue;
        pattern_iter = std::lower_bound(pattern_iter, pattern_list->list.end(), &pattern_from_word, pattern_compare);
        if (pattern_iter == pattern_list->list.end())
            break;
        if (!pattern_compare(&pattern_from_word, *pattern_iter)) 
        {
            for (size_t level_i = 0; level_i < (*pattern_iter)->levels.size(); ++level_i)
            {
                unsigned char l = (*pattern_iter)->levels[level_i];
                if (l > levels[i+level_i]) 
                levels[i+level_i] = l;
            }
        }
    }
}

In the word_string line we put the original word, with the characters '.' Added along the edges, so that rules are automatically selected containing instructions about their position in the word. Now in the source word for each character with i = 0 to N, we sort through all the substrings starting with i and length from 1 to Ni . We look for each substring in the rule vector with the standard std :: lower_bound algorithm . We presume that the rules are sorted in the way we need and there is no need to go through it all over again at every step. When we find a match, take the level vector and apply it to the current result, i.e. if the level for the current position in the rule is higher, remember it instead of the old one.

In the levels vector, the maximum level values ​​for each position are accumulated. It remains to check it for odd values.

mask_size = levels.size()-2;
mask = new unsigned char[mask_size];
for (size_t i = 0; i < mask_size; ++i)
{
    if (levels[i+1] % 2 && i) 
        mask[i] = 1;
    else 
        mask[i] = 0;
}

Examples of the algorithm for a set of rules from TeX:

programmer
cybernetics
scream
intuition
Sight
Hi

Ready-made C ++ code along with the examples can be downloaded here . Test case in main.c file (encoding Windows-1251), rules in patterns.h file.