このアルゴリズムは、ソースワードと一連のルール（テンプレート）との比較に基づいています。 より多くのルールを作成し、それらを作成するほど、ハイフネーションが改善されます。 TeXパッケージには、多くの言語に対応した既製の無料のルールセットがあります。使用条件と配布条件を注意深く確認するだけです。
ルールの例：
at1 3bで 2および1ve .po3zh2
各ルールは、それらの間の文字と数字、および先頭と末尾の数字で構成されます。 通常、数字の0は省略されます。 たとえば、最初のルールは0001として理解する必要があります。 文字のシーケンスは、翻訳が定義されている単語の一部です。 このシーケンスは単語に存在する必要があります。 番号は「レベル」と呼ばれ、ルール間の優先順位と、対応する位置に転送する能力を設定します。 0を含む偶数は、転送を禁止します。 奇数-許可します。 ルールの先頭にあるドットは、シーケンスが単語の先頭にある場合にのみルールが適用されることを意味します。 同様に、最後にドットが付いている-単語はこのシーケンスで終わる必要があります。 開始点と終了点の両方にポイントがある場合、ルールには単語全体が含まれます。
アルゴリズムの主な段階：
- 選択した単語に適合するすべてのルールを選択し、単語内の各位置に対してレベルのセットを取得します（1つの位置にあったルールの数、つまり多くのレベルが受信されます）。
- 各位置で、最大レベルを選択します。 偶数の場合、ここで転送することはできません。奇数の場合、許容される転送場所です。
- 明らかに受け入れられないハイフン（たとえば、先頭または末尾の1文字）を切り取るため。
例でアルゴリズムがどのように機能するかを見てみましょう。
ソースワード： アルゴリズム
一連のルール（TeXから取得）：
lgo1
1g
o1ri
および1t
i2tm
tm2
単語をすべてのルールと比較し、最高レベルを選択します。
レベル1のポジションでは、キャリーを安全に設定できます。 「al-go-rhythm」という結果が得られます。
実装
次に、このアルゴリズムをC ++で実装します。 iOSで使用するための実用的なアルゴリズムが必要だったので、Cインターフェイスの形ですべてを行いました。 このモジュールは、ロケールやプラットフォームを参照せずに記述されているため、どこでも使用できます。
ルールは次のように保存されます。
struct pattern_t { std::basic_string<unichar> str; std::vector<unsigned char> levels; };
各ルールを「純粋な文字のシーケンス」+「レベルのセット」の形式に変換して、将来適用するのが便利になるようにします。
ルールセット：
struct pattern_list_t { std::vector<pattern_t*> list; };
ルールからレベルを引き出すためのコードは簡単です;記事の最後にあるリンクを使用して、完全なソースコードで見ることができます。
ルールのリストに記入した後、アルゴリズムを正しく効率的に動作させるために、ルールのリストをソートする必要があります。 less関数を記述し、標準のソートアルゴリズムを適用します。
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); }
ハイフネーション検索アルゴリズムを直接：
std::vector<unsigned char> levels; levels.assign(word_string.size(), 0); for (size_t i = 0; i < word_string.size()-2; ++i) { std::vector<pattern_t*>::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; } } } }
文字列word_stringに、文字「。」を追加した元の単語を入れます そのため、単語内の位置に関する指示を含むルールが自動的に選択されます。 ここで、 i = 0からNの各文字のソースワードで、 iで始まり長さが1からNiのすべての部分文字列をソートします。 標準のstd :: lower_boundアルゴリズムを使用して、ルールベクトルの各部分文字列を検索します 。 ルールは必要な方法で並べ替えられ、すべてのステップでもう一度やり直す必要はないと想定しています。 一致が見つかったら、レベルベクトルを取得し、現在の結果に適用します。 ルール内の現在の位置のレベルが高い場合、古い位置ではなく、それを覚えておいてください。
レベルベクトルでは、各位置の最大レベル値が累積されます。 奇数値を確認するために残っています。
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; }
TeXの一連のルールのアルゴリズムの例：
プログラム ki-ber-not-t-ka 悲鳴を上げる in-tu-i-qi 百チャット privet
準備ができたC ++コードとサンプルは、 ここからダウンロードできます 。 main.cファイルのテストケース（Windows-1251をエンコード）、patterns.hファイルのルール。