前缀函数(KMP) 应用一例

 2024.04.19 20:53  2024.04.19 21:57  技术  KMP  前缀函数  Neovim  Plugins 󰈭 1126字

在我的 Neovim 配置中, 一直使用的是 nvim-cmp 作为补全引擎, 由于其默认支持模糊查找, 因而补全列表中可能会出现前缀匹配优先级不如子序列的乱序问题, 举一个例子:

补全候选项中有 abc_variable 和 xaxbx 这两个词
输入 ab, nvim-cmp 根据传入的比较函数进行逐个比较与排序; 但由于默认支持模糊查找, 且官方的补全函数中貌似没有前缀匹配优先的规定, 而我自己很合理地又添加了一个根据长度排序的比较函数, 因而在补全列表中, 子序列 xaxbx 反而会获得更高的优先级出现在第一个, 这是极为不合理的.

大概在一年前配置这套补全规则的时候就发现了这个问题, 当时的方案是将补全项和输入字串做一个最长公共前缀的长度计算, 越长的优先级越高, 貌似一直还是相安无事的..

 1utils.prefix_cnt = function(s1, s2)
 2	if(s1 == nil or type(s1) ~= "string") then return 0 end
 3	if(s2 == nil or type(s2) ~= "string") then return 0 end
 4
 5	local len = math.min(#s1, #s2)
 6	local cnt = 0
 7	for i = 1, len, 1 do
 8		if(s1:sub(i, i) == s2:sub(i,i)) then
 9			cnt = cnt + 1
10		else break end
11	end
12	return cnt
13end

直到最近在写一些 C++ 代码的时候, 访问类的成员函数时又会出现一些补全项的乱序问题, 下图是一个简化的问题复现(无C++语义, 仅作为字符串展示):

输入 b 后, bbbbbb 并没有理所应当的获胜, 反而是子序列的优先级更高. 反复审查了一下上述的前缀计算函数, 感觉没什么问题, 打印了一下日志, 发现这几个补全项的计算结果都是 0 !

问题的原因在于进行比较的 输入字符串 并不是 b, 而是 a.b, 这与 lua vim 获取光标前的字符串函数有关, 该函数也是开国老将了, 最开始配置的时候从别的某个地方毛下来的:

1utils.words_before_cursor = function()
2	local _ = vim.api.nvim_win_get_cursor(0)
3	local row = _[1]
4	local col = _[2]
5
6	if col == 0 then return nil end
7	local word = vim.api.nvim_buf_get_lines(0, row - 1, row, true)[1]:sub(0, col):match("[^%s]+$")
8	return word
9end

一个解决方案是修改 words_before_cursor 函数, 让其对于一些特殊标点做分隔, 比如这里的成员访问运算符 ., 分隔后再对尾节点做前缀长度计算, 但是总感觉会不会不太优雅, 后续如果又有一个 rqd 语言或者一些特殊的场景使用@, # 作为分隔符的话, 难不成还得每个都硬编码一次..

不打算修改上述函数的话, 就不能计算公共前缀长度了, 另一个想到的办法就是用KMP算法的思想计算最长公共前后缀, 这是极为合理的: 在最开始的问题中, 只需要分别计算 bbbbbba.b 以及 zz_zzba.b 的最长公共前后缀的长度, 就可以无论分隔符是什么都能较好地让候选项符合预期了.

另外, 应该也不用太担心该算法在某些corner case下会出现新的乱序问题, 因为我尝试构造了半天, 感觉都没有找到一组例子能hack该方法, lgtm, 就认为是还不错的了, 后续如果遇到问题了再更新吧~

计算的 Lua 代码如下, 参考 <前缀函数与 KMP 算法 - OI Wiki>:

~~lua字符串随机访问单个字符需要substr(i, i), 太丑了索性直接转换成table了(大雾~~

 1utils.longest_common_prefix_suffix = function(s_)
 2	local s = {}
 3	for i = 1, #s_, 1 do
 4		s[i] = string.sub(s_, i, i)
 5	end
 6
 7	local n = #s;
 8	local pi = {}
 9	for i = 1, n, 1 do
10		pi[i] = 0
11	end
12	for i = 2, n, 1 do
13		local j = pi[i - 1] + 1
14		while j > 1 and s[i] ~= s[j] do
15			j = pi[j - 1]
16		end
17		if s[i] == s[j] then
18			pi[i] = j
19		end
20	end
21
22	return pi[n]
23end