Fix PrefixMatch to prefer longest match across dict group members

Background

A DictGroup in OpenCC config is a list of dictionaries applied together in a single conversion pass. The intended semantics — consistent with how conversion results are expected to behave — is that the longest matching key wins, with the earlier dict in the group as the tie-break when two dicts match at the same length.

The current PrefixMatch implementation applies a different rule: lower dictOrder (earlier dict) always wins, even if a later dict has a strictly longer match. In effect, this is a short-circuit: once any entry from an earlier dict is found along the trie path, entries from later dicts at deeper nodes are silently ignored.

Before #1318 this discrepancy was harmless in the official configs, because each group consisted of a single phrase-level dict alongside a single character-level dict. Phrase keys are always longer than character keys, so the two priority rules happened to agree. #1318 introduced STPhrases_GeneratedFromRegionalPhrases as a second phrase-level dict within the same group, which for the first time placed two dicts at the same semantic level and exposed the latent bug.

Semantic ambiguity and cross-implementation inconsistency

The name "group" naturally suggests that all member dictionaries are merged into a unified lookup, where the longest match across all dicts wins and ties are broken by dict order. This is the union interpretation, and it is what several third-party OpenCC-compatible implementations have independently adopted.

opencc-js, a widely used JavaScript port, implements group lookup with union semantics: all member dicts contribute to a single longest-match scan, with earlier dicts winning only on equal key length. Given the same config and dictionaries, opencc-js and the C++ reference implementation therefore produce different output whenever a group contains two dicts where an earlier dict's key is a proper prefix of a later dict's key — which is exactly the situation introduced by #1318. This is a source of observable, reproducible conversion inconsistency between OpenCC implementations that share the same dictionary files.

Fixing the priority rule in PrefixMatch to prefer longer keys globally would align the C++ reference implementation with the union semantics that third-party implementations already assume, and would make conversion results consistent across the OpenCC ecosystem for any given set of dictionary files.

What happened after #1318

After #1318, the s2twp (and related) first-stage conversion group became:

[STPhrases, STPhrases_GeneratedFromRegionalPhrases, STCharacters]

There are 20 cases where a key in STPhrases (dictOrder=0) is a proper prefix of a bridge key in STPhrases_GeneratedFromRegionalPhrases (dictOrder=1). A sample:

With the current rule, 出租 (dictOrder=0, len=2) silently shadows 出租車 (dictOrder=1, len=3). The phrase 出租車 gets split at the wrong boundary, so the subsequent TWPhrases stage cannot match it as a whole and convert it to 計程車.

#1349 addressed this by pre-merging both files into a single STPhrases_WithGeneratedFromRegionalPhrases.ocd2. With both entry sets at dictOrder=0, the longer key wins within the same dict and the 20 conflicts disappear. However, this is a workaround that treats the symptom: the underlying priority rule in PrefixMatch remains unchanged, and the problem will recur whenever any two dicts at the same semantic level are placed in the same group.

Official dictionaries have been accidentally safe so far

Two earlier config changes also expanded groups from two to three members, and neither produced any observable conversion difference:

• tw2sp (commit 5e55bc68, 2020): TWPhrasesRev was moved from a standalone conversion stage into the same group as TWVariantsRevPhrases and TWVariantsRev, forming a three-member group. No key in TWPhrasesRev is a proper prefix of any key in TWVariantsRevPhrases, so the short-circuit rule and the longest-match rule agree on every query.
• s2twp (Reformat config JSON and align s2twp conversion chain #1286, commit 6fd41961, 2026): TWPhrases was moved from a standalone conversion stage into the same group as TWVariantsPhrases and TWVariants, again forming a three-member group. The same accidental safety holds: no key in TWPhrases is a proper prefix of any key in TWVariantsPhrases.

Both transitions went unnoticed precisely because the official dictionaries happen to be structured such that no cross-dict prefix relationship exists within any group. This gives a false impression that the current priority rule is correct. #1318 was the first change that placed two dicts at the same semantic level where such a prefix relationship does exist, making the latent bug observable for the first time.

Impact beyond the official dictionaries

Even if OpenCC's official dictionaries currently avoid this problem, users who maintain their own custom dictionaries are not protected. Any user who constructs a DictGroup with two phrase-level dicts — for example, a domain-specific terminology override alongside a base phrase dict — may silently get wrong conversions whenever a key in the earlier dict is a proper prefix of a key in the later dict, with no error or warning.

Root cause

PrefixMatch::Table::MatchPrefixCandidate (src/PrefixMatch.cpp, lines 175–181) selects the winning candidate by:

node->candidate.dictOrder < matchedCandidate->dictOrder ||
(node->candidate.dictOrder == matchedCandidate->dictOrder &&
 node->candidate.keyLength > matchedCandidate->keyLength)

This places dict priority (dictOrder) above key length. The correct criterion is the reverse: key length first, dictOrder as tie-break.

Proposed fix

Change the candidate selection in MatchPrefixCandidate to:

node->candidate.keyLength > matchedCandidate->keyLength ||
(node->candidate.keyLength == matchedCandidate->keyLength &&
 node->candidate.dictOrder < matchedCandidate->dictOrder)

Why this is safe

• No change to re-processing guarantee. The guarantee that already-matched bytes are not re-processed comes from the scanning loop's pointer advance in Conversion::AppendConverted, not from the dictOrder priority rule. Changing the priority rule does not affect this.
• No observable change for standard phrase-before-character layouts. When a group follows the standard design of phrase dict (multi-char entries) before character dict (single-char entries), a phrase dict's longer key already beats a character dict's shorter key under either rule. Conversion output is unchanged for all existing official configs.
• Pre-merged file remains valid. STPhrases_WithGeneratedFromRegionalPhrases.ocd2 can stay as-is; it is still the segmentation dict and still enables the single-dict MarisaDict fast path in PrefixMatch. After this fix it is no longer required for correctness, but keeping it is not wrong.

What needs updating

• src/PrefixMatch.cpp: change the candidate selection condition in MatchPrefixCandidate
• src/DictGroupTest.cpp: add a test case that puts a short key in dict[0] and a longer overlapping key in dict[1], and asserts the longer key wins
• scripts/compile_to_inline_config_test.py: the test test_group_dict_preserves_short_circuit_priority documents the old (incorrect) semantics; rename it and update its commentary

背景

OpenCC 設定檔中的 DictGroup 是將多個字典合併為一次轉換通道使用的結構。其預期語義——與實際轉換結果應有的表現一致——是最長匹配鍵優先，當兩個字典在相同長度上皆命中時，以排在前面的字典作為決勝依據。

現行 PrefixMatch 實作採用的卻是另一套規則：較低 dictOrder（排前面的字典）永遠優先，即使後面的字典有更長的匹配。實際效果等同於短路邏輯：一旦前面的字典在 trie 路徑上找到任何條目，後面字典在更深節點的條目就會被靜默忽略。

#1318 之前，官方設定檔中的每個 group 都只有一個詞組層字典搭配一個字元層字典，詞組鍵天然比字元鍵更長，兩套優先規則碰巧得出相同結果，問題並不明顯。#1318 將 STPhrases_GeneratedFromRegionalPhrases 作為同一個 group 內第二個詞組層字典引入，第一次讓兩個語義層級相同的字典並列，潛藏的缺陷才因此浮現。

官方字典目前的安全性是偶然的

以下兩次設定檔改動同樣將 group 從兩個成員擴充為三個，卻都沒有產生任何可觀測的轉換差異：

• tw2sp（commit 5e55bc68，2020 年）：TWPhrasesRev 從獨立的轉換階段移入與 TWVariantsRevPhrases、TWVariantsRev 共同組成的 group，形成三成員 group。由於 TWPhrasesRev 中沒有任何鍵是 TWVariantsRevPhrases 中某個鍵的真前綴，短路規則與最長匹配規則對每個查詢的結果一致。
• s2twp（Reformat config JSON and align s2twp conversion chain #1286，commit 6fd41961，2026 年）：TWPhrases 從獨立的轉換階段移入與 TWVariantsPhrases、TWVariants 共同組成的 group，同樣形成三成員 group。同樣的偶然安全性成立：TWPhrases 中沒有任何鍵是 TWVariantsPhrases 中某個鍵的真前綴。

這兩次改動能在無人察覺的情況下落地，恰恰是因為官方字典碰巧使得任何 group 內都不存在跨字典的前綴關係。這給人一種當前優先規則是正確的錯誤印象。#1318 是第一個在同一 group 內放入兩個語義層級相同的字典、且其中存在前綴關係的改動，使潛藏的缺陷首次得以現形。

語義歧義與跨實現的轉換不一致

「group」這個名稱自然地暗示：所有成員字典合併為一個統一的查詢空間，全局取最長匹配，同等長度時以字典順序決勝。這是 union 語義，也是多個第三方 OpenCC 相容實現各自獨立採用的理解。

廣泛使用的 JavaScript 移植版 opencc-js 即以 union 語義實現 group 查詢：所有成員字典共同參與一次最長匹配掃描，只有在鍵長相同時才以字典順序決勝。在相同設定檔和字典的前提下，opencc-js 與 C++ 參考實現對同一輸入可能產生不同結果——只要 group 中某個前面字典的鍵恰好是後面字典某個鍵的真前綴，差異就會出現，而這正是 #1318 所引入的情形。這是 OpenCC 各實現之間可觀測、可復現的轉換不一致，根源在於對 group 語義的不同理解。

將 PrefixMatch 的優先規則修正為全局長鍵優先，能使 C++ 參考實現與第三方實現已採用的 union 語義對齊，讓使用相同字典文件的各 OpenCC 實現在轉換結果上保持一致。

#1318 之後發生了什麼

#1318 之後，s2twp（及相關設定）第一階段的 group 變為：

[STPhrases, STPhrases_GeneratedFromRegionalPhrases, STCharacters]

STPhrases（dictOrder=0）中有 20 個鍵是 STPhrases_GeneratedFromRegionalPhrases（dictOrder=1）橋接條目的真前綴，舉例：

在當前規則下，出租（dictOrder=0，長度 2）靜默遮蔽了 出租車（dictOrder=1，長度 3）。出租車 在錯誤的邊界處被截斷，使後續的 TWPhrases 階段無法將其作為整體匹配，進而轉換為 計程車。

#1349 透過將兩個文件預合并為 STPhrases_WithGeneratedFromRegionalPhrases.ocd2 來繞過此問題：兩組條目共享 dictOrder=0，同一字典內長鍵自然優先，20 個衝突消失。然而這只是繞路修法，PrefixMatch 的底層優先規則並未改變，只要任意兩個語義層級相同的字典並列於同一個 group，問題就可能重現。

對官方字典以外的影響

即使 OpenCC 官方字典目前不受影響，自行維護字典的使用者並無同等保護。任何使用自訂字典、在同一個 DictGroup 中放入兩個詞組層字典的使用者——例如在基礎詞組字典之上再疊加一個領域術語字典——只要前一個字典的某個鍵恰好是後一個字典某個鍵的前綴，就可能在毫無錯誤提示的情況下得到錯誤的轉換結果。

根本原因

PrefixMatch::Table::MatchPrefixCandidate（src/PrefixMatch.cpp，第 175–181 行）以如下條件選出勝出候選：

node->candidate.dictOrder < matchedCandidate->dictOrder ||
(node->candidate.dictOrder == matchedCandidate->dictOrder &&
 node->candidate.keyLength > matchedCandidate->keyLength)

此處將字典優先級（dictOrder）置於鍵長之上。正確的準則應相反：先比鍵長，再以 dictOrder 打平。

建議修法

將 MatchPrefixCandidate 中的候選選擇條件改為：

node->candidate.keyLength > matchedCandidate->keyLength ||
(node->candidate.keyLength == matchedCandidate->keyLength &&
 node->candidate.dictOrder < matchedCandidate->dictOrder)

為何此修改是安全的

• 不影響「不重複處理已匹配字節」的保證。 這個保證來自 Conversion::AppendConverted 掃描循環的指針推進，與 dictOrder 優先級規則無關。修改優先規則不影響此機制。
• 對標準詞組先於字元的 group 佈局無可觀測的行為變更。 當 group 按標準設計將詞組字典（多字條目）置於字元字典（單字條目）之前時，詞組字典的長鍵在任一規則下都會勝出，所有現有官方設定檔的轉換輸出不變。
• 預合并文件仍然有效。 STPhrases_WithGeneratedFromRegionalPhrases.ocd2 可維持現狀，它仍是分詞字典，仍能在 PrefixMatch 中啟用單字典 MarisaDict 快速路徑。修改後它不再是正確性的前提，但繼續保留並無不妥。

需要修改的地方

• src/PrefixMatch.cpp：修改 MatchPrefixCandidate 中的候選選擇條件
• src/DictGroupTest.cpp：新增測試案例，dict[0] 有短鍵、dict[1] 有較長的重疊鍵，斷言長鍵勝出
• scripts/compile_to_inline_config_test.py：測試 test_group_dict_preserves_short_circuit_priority 記錄的是舊的（不正確的）語義，應重新命名並更新說明