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

Emacs-general
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

21

ln -sv target/release/libfuz_core.so fuz-core.so

macOS下应该是 ln -sv target/release/libfuz_core.dylib fuz-core.so？

排序舒心多了，只是发现一个问题，describe-variable很慢很慢~~~ 似乎ivy-fuz-fuzzy-sort-fn有点问题

22

https://github.com/cireu/fuz.el/blob/improve/maybe-speedup-ivy-fuz/ivy-fuz.el

推送了一个补丁到新branchimprove/maybe-speedup-ivy-fuz上。

原来ivy--flx-sort要先构建模糊正则来筛选candidate，我当时无脑照抄了，其实直接配合memo-fn用计算出来的score来筛选就行，还能避免多次计算分值。

23

自动下载预编译binary还是等release先吧 :joy:

24

这个补丁对于describe-variable还是很慢啊，其他都很好

25

之前一直搞错了一个事情，fuzzy sort应该用ivy-sort-matches-functions-alist来修改，而我错用了ivy-sort-functions-alist。现在我已经更新了README :sweat:

尝试下这个设置。

      (setq ivy-sort-matches-functions-alist '(t . ivy-fuz-sort-fn))
      (setq ivy-re-builders-alist '(t . ivy-fuz-regex-fuzzy))
      (setq ivy-highlight-functions-alist '(ivy-fuz-fuzzy-regex . ivy-fuz-highlight-fn))

      (with-eval-after-load 'ivy
        (require 'ivy-fuz))