chewing / libchewing

libchewing - The intelligent phonetic input method library
https://chewing.im/
GNU Lesser General Public License v2.1
357 stars 89 forks source link

Bound the complexity of recursive phrase partition #493

Closed kanru closed 3 months ago

kanru commented 3 months ago

Is your feature request related to a problem? Please describe.

目前用 鍵觸發的重新分詞演算法在遇到極端的案例時會變成 O(2^N) 的演算法,N 是 preedit 的長度。

Describe the solution you'd like

改用新的 partition 的方法,並限制總共可以發現的分詞方式上限,讓輸入的時候絕對不會卡頓。

Describe alternatives you've considered

用同樣的演算法,如果發現可能的分詞方式太多的時候就直接 abort 並退回第一種「最佳解」的選項。