feat: Add fuzzy search to patches search

[cloudflare-pages[bot]]

Deploying with    Cloudflare Pages

Latest commit:	c4c4055
Status:	🚫  Build failed.

View logs

[PalmDevs]

Someone fix deploying, I want to see a preview.

[revanced-bot]

Deployed at https://head.revanced.pages.dev.

[revanced-bot]

Deployed at https://d455e42c.revanced.pages.dev.

[xafn]

this ALMOST LGTM. the only thing is that for some reason if you clear the search string, the parameter in the url doesn't clear. if nobody figures out why this happens by tonight i'll try to fix this.

resolved in #230

[revanced-bot]

Deployed at https://987be635.revanced.pages.dev.

[oSumAtrIX]

I am not sure what kind of parameters cause this, but if i search for video ads, it should not show other results present here

[KTibow]

that's what happens when you have both "adds" and "video" in the description of a patch. now that normally wouldn't be a problem, but the ones that actually have "video ads" in the title are being downranked. that will have to be fixed...

[KTibow]

https://3f823d90.revanced.pages.dev/patches?s=video+ads

[oSumAtrIX]

Can a threshold be used? This way results with a low threshold, weighted down by results with high matches can be hidden

[oSumAtrIX]

Some threshold needs to be adjusted, too many irrelevant results or incorrect ones show up

[KTibow]

@oSumAtrIX I just checked, and the exact same first search results show up on the non-fuzzy version. I think it's worth deploying now, as it makes some situations better without making any worse.

[oSumAtrIX]

If you scroll down on the fizzy search you will find many results that hardly match the search, the thresholds may be adjusted for that. The fuzzy search should slightly aid the search on variations of searches such as spelling mistakes, casing, spaces or characters, and not match results that are hardly expected to show up.

[KTibow]

Well that's a tough one. I see a couple options to add a minimum score:

• Fork the library, make the change, and try to upstream the changes
• Inline/fork the library and make the change
• Inline our own simple, slightly-fuzzy search (eg, just create all possibilities with a levenshtein distance of 1, and show which results match next)
• Use a different library

Which one would you prefer?

[oSumAtrIX]

The first and last option are the only reasonable ones

[KTibow]

FYI looks like someone already tried to contribute scores and it hasn't been merged: https://github.com/wouterrutgers/fuzzy-search/pull/82/files If inlining is still out as an option, we'll have to switch to another library like Fuse. Fuse doesn't have the smallest bundle size (15kb bundled uncompressed, since it uses classes) but it's popular and would work.

[oSumAtrIX]

If there is a fork already, we can use it if it is rebased on upstream (use a commit hash for the dependency and link the PR)

[oSumAtrIX]

Instead of fuze due to its size you should use the fork

[KTibow]

I notice Fuse providing more relevant results, so I think we should use it anyway. It's only a 4kb increase from the previous library over the wire.

Without Fuse: With Fuse:

[oSumAtrIX]

Why does Fuse show different results though? Isn't the algorithm the same?

[KTibow]

No, not all fuzzy search algorithms are the same. I haven't checked all the differences, but the most useful thing I see fuse doing is relying on shorter fields (eg title) more than longer fields.