support fuzzy matching

[lbgws2]

awesome plugin!!!

This plug-in not only helps me complete words quickly, but also can input variable names quickly

Is there a plan to support fuzzy matching, which makes it easier to complete words instead of starting from scratch

[tadashi-aikawa]

Hi, @lbgws2. Thank you for your FR :)

Is there a plan to support fuzzy matching, which makes it easier to complete words instead of starting from scratch

None so far. However, it would be handy to implement it if there is no performance reduction.

[lbgws2]

Hi, @lbgws2. Thank you for your FR :)

Is there a plan to support fuzzy matching, which makes it easier to complete words instead of starting from scratch

None so far. However, it would be handy to implement it if there is no performance reduction.

if it's easy to implement it ,can you consider designing it as an option, and let the user decide to enable it or not

I'm willing to sacrifice some performance for this function

as i say,fuzzy matching is very practical.

[tadashi-aikawa]

OK. I am interested in the implementation of fuzzy search. So I'll implement it as experimental in v7.0.0 :)

[tadashi-aikawa]

@lbgws2 And Could you tell me the concrete case that you want to use the fuzzy search?

[lbgws2]

I have tested the 7.0.0-beta6, I used about 60000 words as a custom dictionary, which looks like this

When I input english words, it can perform fuzzy matching very well

When I input Chinese, it's also match well, which means that I can check the available English words at any time during the input process, which is very helpful to improve my English level

As for performance, after indexing, it can respond quickly when I input,which is when I adjust the max number of suggestions to 100

The response time is in my acceptable range. To be precise, it is about 500ms-1s

Once again, this plug-in is really excellent. Thank you for your selfless dedication!!!

[tadashi-aikawa]

@lbgws2 Thank you for your kind answer :)

Does "fuzzy search" mean Match strategy = partial in any chance? And if it is correct, Don't I have to implement the feature about this issue?

[lbgws2]

@tadashi-aikawa

Does "fuzzy search" mean Match strategy = partial in any chance? And if it is correct, Don't I have to implement the feature about this issue?

I don't know which fuzzy search algorithm you use, Vscode fuzzy matching is good

Vscode fuzzy matching may be using ripgrep,I'm not sure

[aubreyz]

It would mean if you type desa

you will get prompted for disasterous desperate

May be suitable for spell checkers, bit in my opinion is a step too far for a text completion plugin like this. It would hardly work for short trigger strings (less than about 6 characters and where there would otherwise be no matches at all), and for longer strings you might as well rely on the inbuilt spell checker.

[tadashi-aikawa]

Thanks @lbgws2 :)

When I input english words, it can perform fuzzy matching very well

You wrote the above, so I thought, "it already satisfies your demands?" using 7.0.0-beta6. If you want to complete as following like VSCode, I see.

[danrthompson]

I would also LOVE this feature :). Specifically, not using partial but rather fuzzy searching. The advantage to it is that fuzzy searching enables you to more easily get the top completion to the top, and it is faster than using the arrow keys.

For example, if you are trying to autocomplete "advantageous" and you start typing, let's say "advantage" is the one at the very top. You'd either have to use a hotkey to select the next suggestion (which is generally slower than typing the word out if you're a fast typist), or you would need to type out nearly the whole word to get to the right completion.

If fuzzy searching is implemented, however, it enables you to type "adv", then type any letter that is not in "advantage" but is in "advantageous". In practice, you won't calculate that, but rather you'd type "adv", then maybe the end of the word like "ous".

Also, it makes autocompletion way more effective if you are prone to typos.

Typically fuzzy searching algos will give you a number of parameters to choose from, basically mapping to different measures of how different a match can be from the typed string. Or how many "wrong" characters are allowed (if 0, then each letter must be in the matching word, even if not in the same order, if >0, then it's more forgiving of typos). Another common parameter is whether the letters have to be in the correct order (as in, ads would match to advantageous", but "sda" would not).

There are a lot of pre-existing, very fast fuzzy search tools out there. I believe fzf is a good one, although it might be best for you to check what is fastest.

I suspect given the amazing framework you've already built, that integrating this into the plugin probably won't be extremely difficult, but obviously no problem if it isn't worth implementing to you.

Either way, thanks so much for an amazing plugin!

[tadashi-aikawa]

The advantage to it is that fuzzy searching enables you to more easily get the top completion to the top, and it is faster than using the arrow keys.

Right. I never thought about that until you mentioned it just now :)

There are a lot of pre-existing, very fast fuzzy search tools out there. I believe fzf is a good one, although it might be best for you to check what is fastest.

I agree with you. On the other hand, autocomplete, which is always triggered, and search, which is only triggered when necessary, would require different performances. Nevertheless, it is the user who makes those decisions. So I'd like to try to implement it 👍

[tadashi-aikawa]

I measured and compared the performance of some logic.

match: 0.737060546875 ms
match: 0.91ms
startsWith: 1.81201171875 ms
startsWith: 1.891ms
includes: 1.092041015625 ms
includes: 1.182ms
fuzzy: 390.54296875 ms
fuzzy: 390.686ms

According to the results, the speed of fuzzy search is several hundred times slower than the others, so it doesn't seem easy to implement as it is. It would be good if there were a high-speed library other than fast-fuzzy 🤔

Code

import { fuzzy } from "fast-fuzzy";

function getTarget(): string {
  return "Another Quick Switcher Plugin";
}

function main() {
  const target = getTarget();

  console.time("match");
  for (let i = 0; i < 100000; i++) {
    target === "aqs";
  }
  console.timeEnd("match");

  console.time("startsWith");
  for (let i = 0; i < 100000; i++) {
    target.startsWith("aqs");
  }
  console.timeEnd("startsWith");

  console.time("includes");
  for (let i = 0; i < 100000; i++) {
    target.includes("aqs");
  }
  console.timeEnd("includes");

  console.time("fuzzy");
  for (let i = 0; i < 100000; i++) {
    fuzzy("aqs", target);
  }
  console.timeEnd("fuzzy");
}

main();

[tadashi-aikawa]

Good news. A minimum fuzzy search that I made is fast enough😄

import { fuzzy } from "fast-fuzzy";

const COUNT = 100000;

function getTarget(): string {
  return "Another Quick Switcher Plugin";
}

function originalFuzzy(query: string, value: string): boolean {
  let i = 0;
  for (let j = 0; j < value.length; j++) {
    if (value[j] === query[i]) {
      i++;
    }
    if (i === query.length) {
      return true;
    }
  }
  return false;
}

function main() {
  const target = getTarget();

  console.time("match");
  for (let i = 0; i < COUNT; i++) {
    target === "aqs";
  }
  console.timeEnd("match");

  console.time("startsWith");
  for (let i = 0; i < COUNT; i++) {
    target.startsWith("aqs");
  }
  console.timeEnd("startsWith");

  console.time("includes");
  for (let i = 0; i < COUNT; i++) {
    target.includes("aqs");
  }
  console.timeEnd("includes");

  console.time("fuzzy");
  for (let i = 0; i < COUNT; i++) {
    fuzzy("aqs", target);
  }
  console.timeEnd("fuzzy");

  console.time("originalFuzzy");
  for (let i = 0; i < COUNT; i++) {
    originalFuzzy("AQS", target);
  }
  console.timeEnd("originalFuzzy");
}

main();

match: 0.81103515625 ms
match: 0.978ms
startsWith: 2.739013671875 ms
startsWith: 2.957ms
includes: 2.39794921875 ms
includes: 2.553ms
fuzzy: 397.06689453125 ms
fuzzy: 397.192ms
originalFuzzy: 6.27587890625 ms
originalFuzzy: 6.372ms

[tadashi-aikawa]

@lbgws2 @aubreyz @danrthompson I have released 8.0.0-beta10 🚀

The version enables you to fuzzy match by a new option.
If you use BRAT, please confirm it. If not, please wait to release it as official, v8.0.0.

https://user-images.githubusercontent.com/9500018/219951893-7e5cddee-5f69-4546-b4e9-19a181406079.mp4

[danrthompson]

@tadashi-aikawa Thanks so much! You are awesome!!!

[tadashi-aikawa]

@lbgws2 @aubreyz @danrthompson Released in v8.0.0 🚀