ivy用的flx.el模糊搜索質量慘不忍睹

Emacs-general
1

spacemacs，company m匹配[co[m]pany]-mode，what the hell???

doom-emacs，company m匹配[company]-[m]ode，正常些。但是 iv優先列出arch[iv]-*而把前綴匹配的ivy-*放在後面，???

我以前根據fzf和別的什麼地方抄了一個加到 rofi -sort -matching fuzzy。

後來從https://github.com/llvm-mirror/clang-tools-extra/blob/master/clangd/FuzzyMatch.h抄+改(大幅簡化並(自認爲:proud:)質量不差)了一份到cquery

這個問題用subsequence filtering + sequence alignment O(n^2) dynamic programming就好了，不要到處堆heuristics，弄出我都看不出主循環在什麼地方的代碼。(fzf也有這個毛病，heuristics散亂堆在各個地方)

但我寫不來elisp T_T

2

發了 Use O(n*m) sequence alignment algorithm · Issue #98 · lewang/flx · GitHub 希望有大大能實現T_T

3

没毛病啊。像我这种经常把 parinfer-toggle-mode 打成 toglg par 的情况下，这是为了保证就算有 typo 也能匹配嘛。

4

讲道理 ivy不建议用fuzzy search

abo-abo自己不用 所以各方面support都比不过regex-plus backend 速度也慢很多

5

我用M-x有些时候带有探索性质，想知道有哪些命令。如果fuzzy matching智能，知道consecutive matching优先级高(以及我列的其他一些heuristics)，fuzzy matching并不妨碍的。

1 个赞
6

今天研究了ivy代碼才發現flx其實還行，我沒有安裝flx所以ivy.el中(defvar ivy--flx-featurep (require 'flx nil 'noerror))爲nil沒有啓用。

https://github.com/abo-abo/swiper/pull/1518 C-x C-f的問題不知何故

二維動態規劃用

(cl-macrolet ((c0 (i j) `(aref (aref miss ,i) ,j))
             (c1 (i j) `(aref (aref match ,i) ,j)))

還是挺開心的。以後得研究setf gv.el這些到底是怎麼做出來的

7

在 common lisp 里 setf 其实是靠 OOP 做的，对于不同数据类型/结构都要定义一个对应的方法才能用。

8

setf被Stefan Monnier改成gv.el了，原來可能是OOP，現在是getter/setter old-style lens （嗯，Haskell常用的Control.Lens Twan van Laarhoven lens嚴格強於這個)

9

看了下，是利用 Emacs 加入 lexical-binding 以后可以用 Closure 隐式传指针实現的。

10

flx好像是O(n)，它有预处理的cache。

O(n*m)的算法估计有点呛，elisp太慢了。

它没啥启发式的东西，就靠一个评分函数。

现有的模糊最多能容忍一下transpose charcater

transpose word就跪。。

所以要先要确定一下要实现什么样的模糊搜索。。

我感觉flx够用了。

11 
(defun flx-find-best-match (str-info
                            heatmap
                            greater-than
                            query
                            query-length
                            q-index
                            match-cache)
  "Recursively compute the best match for a string, passed as STR-INFO and
HEATMAP, according to QUERY.
This function uses MATCH-CACHE to memoize its return values.
For other parameters, see `flx-score'"

遞歸計算的，沒仔細看用了什麼算法。

這類sequence alignment算法都要保證pattern是text subsequence的，transpose不能容忍

12

速度的问题就用dynamic module来解决 :stuck_out_tongue:

用Rust包装主题所提到的subseq alignment 算法成submodule。给Emacs调用，搜索速度刷刷的。

目前只写了helm的，和helm-flx简单做个对比。

image
image1214×292 45.2 KB

5 个赞
13

用rust肯定速度杠杆的……

只是不太好自动编译安装啊，如果有预编译的binary就好了。另外ivy-fuz.el居然是空的 :joy:

14

WIP :joy:。 在做了（咕咕）

预编译binary要怎么托管？另外有自动发布多平台交叉编译binary的托管工具么？

15

高产哪

很多项目是release到github上的，自动发布的托管工具我也不了解啊，我都是通过CI干的

16

参考 https://github.com/sharkdp/fd/blob/master/appveyor.yml 或者 https://github.com/BurntSushi/ripgrep/blob/master/appveyor.yml

1 个赞
17

已经加入了对ivy的支持，可以参照README.org进行设置，欢迎试用。

用fuz排序我counsel-ffdata读出来的6w条历史记录。在ivy-fuz-sort-limit设置为5000（和flx一样）的情况，比flx流畅到不知哪里去了

2 个赞
18

不太了解dynamic module，能不能搞成自动下载预编译binary？

希望能把这个包提交到 melpa，让更多人能用到

19

你这个库，能否每种系统直接二进制包安装一下？

然后能做成库吗？

比如：

(fuz-match-p “input1 input2 input3” candidate) 返回 t 或者 nil ?

1 个赞
20

目前暴露了4个API，两个算法的各两个，一个计算分值，一个返回fuzzy match找到的字符位置，如果没有匹配，都会返回nil